# A Performance Guarantee for Spectral Clustering

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2020.

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

- [Generalized Dirichlet Energy and Graph Laplacians for Clustering Directed and Undirected Graphs](https://mlsanity.com/paper/2203.03221/) (2022)
- [Spectral Clustering of Categorical and Mixed-type Data via Extra Graph Nodes](https://mlsanity.com/paper/2403.05669/) (2024)

## Abstract (arXiv)

The two-step spectral clustering method, which consists of the Laplacian eigenmap and a rounding step, is a widely used method for graph partitioning. It can be seen as a natural relaxation to the NP-hard minimum ratio cut problem. In this paper we study the central question: when is spectral clustering able to find the global solution to the minimum ratio cut problem? First we provide a condition that naturally depends on the intra- and inter-cluster connectivities of a given partition under which we may certify that this partition is the solution to the minimum ratio cut problem. Then we develop a deterministic two-to-infinity norm perturbation bound for the the invariant subspace of the graph Laplacian that corresponds to the k smallest eigenvalues. Finally by combining these two results we give a condition under which spectral clustering is guaranteed to output the global solution to the minimum ratio cut problem, which serves as a performance guarantee for spectral clustering.