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

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

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
Pages	445-454
Number of pages	10
Publication status	Published - 2016
Externally published	Yes
Event	19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016 - Cadiz, Spain Duration: 9 May 2016 → 11 May 2016

Conference

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

Cite this

@conference{a7f6202ed5204be58ba39414fffaea80,

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",

language = "English",

pages = "445--454",

}

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

Y1 - 2016

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

M3 - Paper

AN - SCOPUS:85029732175

SP - 445

EP - 454

Y2 - 9 May 2016 through 11 May 2016

ER -

Simple and scalable constrained clustering: A generalized spectral method

Abstract

Conference

Other files and links

Fingerprint

Cite this