2016/01/18 by Mihai Cucuringu, Cucuringu, Mihai, Ioannis Koutis +7
Computer Science · #FOS: Computer and information sciences #Social and Information Networks (cs.SI) #cs.SI
paper · pdf · doi:10.48550/arxiv.1601.04746
accepted to appear in AISTATS 2016. arXiv admin note: text overlap with arXiv:1504.00653
arxiv created 2016/01/18 · arxiv updated 2016/01/20
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.