%0 Journal Article
%T Scalable Constrained Clustering: A Generalized Spectral Method
%A Mihai Cucuringu
%A Ioannis Koutis
%A Sanjay Chawla
%J Computer Science
%D 2015
%I arXiv
%X We present a principled spectral approach to the well-studied constrained clustering problem. It reduces clustering to a generalized eigenvalue problem on Laplacians. The method 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. We support this claim with experiments on various data sets: our approach recovers correct clusters in examples where previous methods fail, and handles data sets with millions of data points - two orders of magnitude larger than before.
%U http://arxiv.org/abs/1504.00653v2