AISTATS 2016poster64 citations
Simple and Scalable Constrained Clustering: a Generalized Spectral Method
Mihai Cucuringu, Ioannis Koutis, Sanjay Chawla, Gary Miller, Richard Peng
Abstract
We present a simple spectral approach to the well-studied constrained clustering problem. It captures constrained clustering as a generalized eigenvalue problem with 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.
BibTeX
@InProceedings{pmlr-v51-cucuringu16,
title = {Simple and Scalable Constrained Clustering: a Generalized Spectral Method},
author = {Cucuringu, Mihai and Koutis, Ioannis and Chawla, Sanjay and Miller, Gary and Peng, Richard},
booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics},
pages = {445--454},
year = {2016},
editor = {Gretton, Arthur and Robert, Christian C.},
volume = {51},
series = {Proceedings of Machine Learning Research},
address = {Cadiz, Spain},
month = {09--11 May},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v51/cucuringu16.pdf},
url = {https://proceedings.mlr.press/v51/cucuringu16.html},
abstract = {We present a simple spectral approach to the well-studied constrained clustering problem. It captures constrained clustering as a generalized eigenvalue problem with 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.}
}