# Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 66 references that are in the map.
- First posted on arXiv 11 May 2023.

## Builds on (most cited first, 22 of 22)

- [Deep Spectral Methods: A Surprisingly Strong Baseline for Unsupervised Semantic Segmentation and Localization](https://mlsanity.com/paper/2205.07839/) (2022)
- [SpectralNet: Spectral Clustering using Deep Neural Networks](https://mlsanity.com/paper/1801.01587/) (2018)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [A variational approach to the consistency of spectral clustering](https://mlsanity.com/paper/1508.01928/) (2015)
- [Continuum limit of total variation on point clouds](https://mlsanity.com/paper/1403.6355/) (2014)
- [Algorithms and Hardness for Linear Algebra on Geometric Graphs](https://mlsanity.com/paper/2011.02466/) (2020)
- [Understanding Regularized Spectral Clustering via Graph Conductance](https://mlsanity.com/paper/1806.01468/) (2018)
- [Eldan's Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixing](https://mlsanity.com/paper/1612.01507/) (2016)
- [A Tighter Analysis of Spectral Clustering, and Beyond](https://mlsanity.com/paper/2208.01724/) (2022)
- [A Slightly Improved Bound for the KLS Constant](https://mlsanity.com/paper/2208.11644/) (2022)
- [Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap](https://mlsanity.com/paper/1301.5584/) (2013)
- [Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering](https://mlsanity.com/paper/2102.12293/) (2021)
- [Consistency of Cheeger and Ratio Graph Cuts](https://mlsanity.com/paper/1411.6590/) (2014)
- [The Kannan-Lov'asz-Simonovits Conjecture](https://mlsanity.com/paper/1807.03465/) (2018)
- [Expander Decomposition and Pruning: Faster, Stronger, and Simpler](https://mlsanity.com/paper/1812.08958/) (2018)
- [Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues](https://mlsanity.com/paper/2203.06168/) (2022)
- [A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond](https://mlsanity.com/paper/1910.08025/) (2019)
- [Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile](https://mlsanity.com/paper/1504.00686/) (2015)
- [Cheeger-type approximation for sparsest st-cut](https://mlsanity.com/paper/1410.3889/) (2014)
- [A Schur Complement Cheeger Inequality](https://mlsanity.com/paper/1811.10834/) (2018)
- [Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues](https://mlsanity.com/paper/1812.02841/) (2018)
- [Weighted Cheeger and Buser Inequalities, with Applications to Clustering and Cutting Probability Densities](https://mlsanity.com/paper/2004.09589/) (2020)

## Abstract (arXiv)

Spectral clustering is one of the most popular clustering algorithms that has stood the test of time. It is simple to describe, can be implemented using standard linear algebra, and often finds better clusters than traditional clustering algorithms like k-means and k-centers. The foundational algorithm for two-way spectral clustering, by Shi and Malik, creates a geometric graph from data and finds a spectral cut of the graph. In modern machine learning, many data sets are modeled as a large number of points drawn from a probability density function. Little is known about when spectral clustering works in this setting -- and when it doesn't. Past researchers justified spectral clustering by appealing to the graph Cheeger inequality (which states that the spectral cut of a graph approximates the ``Normalized Cut''), but this justification is known to break down on large data sets. We provide theoretically-informed intuition about spectral clustering on large data sets drawn from probability densities, by proving when a continuous form of spectral clustering considered by past researchers (the unweighted spectral cut of a probability density) finds good clusters of the underlying density itself. Our work suggests that Shi-Malik spectral clustering works well on data drawn from mixtures of Laplace distributions, and works poorly on data drawn from certain other densities, such as a density we call the `square-root trough'. Our core theorem proves that weighted spectral cuts have low weighted isoperimetry for all probability densities. Our key tool is a new Cheeger-Buser inequality for all probability densities, including discontinuous ones.