Simple and scalable constrained clustering: a generalized spectral method

Conference item

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.

Authors: Cucuringu, M

• Publication status: Published
• Peer review status: Reviewed (other)
• Publisher: Microtome Publishing
• Host title: Proceedings of Machine Learning Research: Editors: Arthur Gretton, Christian C. Robert Volume 51: Artificial Intelligence and Statistics, 9-11 May 2016, Cadiz, Spain
• Journal: Proceedings of Machine Learning Research
• Volume: 51
• Pages: 445-454
• Publication date: 2016-05-09
• Acceptance date: 2015-12-24
• ISSN: 2640-3498
• Keywords: SBTMR