Simple and scalable constrained clustering: A generalized spectral method

Mihai Cucuringu; Ioannis Koutis; Sanjay Chawla; Gary Miller; Richard Peng

Simple and scalable constrained clustering: A generalized spectral method

Mihai Cucuringu, Ioannis Koutis, Sanjay Chawla, Gary Miller, Richard Peng

Computer Science

Research output: Contribution to conference › Paper › peer-review

41 Scopus citations

Abstract

We present a simple spectral approach to the well-studied constrained clustering problem. It captures constrained clustering as a generalized eigenvalue problem in which both matrices are graph Laplacians. The algorithm works in nearly-linear time and provides concrete guarantees for the quality of the clusters, at least for the case of 2-way partitioning. In practice this translates to a very fast implementation that consistently outperforms existing spectral approaches both in speed and quality.

Original language	English (US)
Pages	445-454
Number of pages	10
State	Published - Jan 1 2016
Event	19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016 - Cadiz, Spain Duration: May 9 2016 → May 11 2016

Conference

Conference	19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016
Country/Territory	Spain
City	Cadiz
Period	5/9/16 → 5/11/16

All Science Journal Classification (ASJC) codes

Artificial Intelligence
Statistics and Probability

Cite this

@conference{2c31f16aff7646849618f6c0292b7784,

title = "Simple and scalable constrained clustering: A generalized spectral method",

abstract = "We present a simple spectral approach to the well-studied constrained clustering problem. It captures constrained clustering as a generalized eigenvalue problem in which both matrices are graph Laplacians. The algorithm works in nearly-linear time and provides concrete guarantees for the quality of the clusters, at least for the case of 2-way partitioning. In practice this translates to a very fast implementation that consistently outperforms existing spectral approaches both in speed and quality.",

author = "Mihai Cucuringu and Ioannis Koutis and Sanjay Chawla and Gary Miller and Richard Peng",

year = "2016",

month = jan,

day = "1",

language = "English (US)",

pages = "445--454",

note = "19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016 ; Conference date: 09-05-2016 Through 11-05-2016",

}

TY - CONF

T1 - Simple and scalable constrained clustering

T2 - 19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016

AU - Cucuringu, Mihai

AU - Koutis, Ioannis

AU - Chawla, Sanjay

AU - Miller, Gary

AU - Peng, Richard

PY - 2016/1/1

Y1 - 2016/1/1

N2 - We present a simple spectral approach to the well-studied constrained clustering problem. It captures constrained clustering as a generalized eigenvalue problem in which both matrices are graph Laplacians. The algorithm works in nearly-linear time and provides concrete guarantees for the quality of the clusters, at least for the case of 2-way partitioning. In practice this translates to a very fast implementation that consistently outperforms existing spectral approaches both in speed and quality.

AB - We present a simple spectral approach to the well-studied constrained clustering problem. It captures constrained clustering as a generalized eigenvalue problem in which both matrices are graph Laplacians. The algorithm works in nearly-linear time and provides concrete guarantees for the quality of the clusters, at least for the case of 2-way partitioning. In practice this translates to a very fast implementation that consistently outperforms existing spectral approaches both in speed and quality.

UR - https://www.scopus.com/pages/publications/85029732175

UR - https://www.scopus.com/inward/citedby.url?scp=85029732175&partnerID=8YFLogxK

M3 - Paper

SP - 445

EP - 454

Y2 - 9 May 2016 through 11 May 2016

ER -

Simple and scalable constrained clustering: A generalized spectral method

Abstract

Conference

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this