Home Page

Papers

Submissions

News

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Login



RSS Feed

Simple and Scalable Constrained Clustering: a Generalized Spectral Method

Mihai Cucuringu, Ioannis Koutis, Sanjay Chawla, Gary Miller, Richard Peng
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pp. 445–454, 2016

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.

Related Material