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 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.
Cite
Text
Cucuringu et al. "Simple and Scalable Constrained Clustering: A Generalized Spectral Method." International Conference on Artificial Intelligence and Statistics, 2016.Markdown
[Cucuringu et al. "Simple and Scalable Constrained Clustering: A Generalized Spectral Method." International Conference on Artificial Intelligence and Statistics, 2016.](https://mlanthology.org/aistats/2016/cucuringu2016aistats-simple/)BibTeX
@inproceedings{cucuringu2016aistats-simple,
title = {{Simple and Scalable Constrained Clustering: A Generalized Spectral Method}},
author = {Cucuringu, Mihai and Koutis, Ioannis and Chawla, Sanjay and Miller, Gary L. and Peng, Richard},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2016},
pages = {445-454},
url = {https://mlanthology.org/aistats/2016/cucuringu2016aistats-simple/}
}