# Scalable Constrained Clustering: A Generalized Spectral Method

arXiv: https://arxiv.org/abs/1601.04746 · HTML: https://mlsanity.com/paper/1601.04746/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jan 2016.

## Built on by (most cited first, 3 of 3)

- [SSSNET: Semi-Supervised Signed Network Clustering](https://mlsanity.com/paper/2110.06623/) (2021)
- [DIGRAC: Digraph Clustering Based on Flow Imbalance](https://mlsanity.com/paper/2106.05194/) (2021)
- [Fast and Featureless Node Representation Learning with Partial Pairwise Supervision](https://mlsanity.com/paper/2605.19916/) (2026)

## Abstract (arXiv)

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.