# A Tighter Analysis of Spectral Clustering, and Beyond

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 31 references that are in the map.
- First posted on arXiv 2 Aug 2022.

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

- [The Impact of Random Models on Clustering Similarity](https://mlsanity.com/paper/1701.06508/) (2017)
- [Hermitian matrices for clustering directed graphs: insights and applications](https://mlsanity.com/paper/1908.02096/) (2019)
- [Higher-Order Spectral Clustering of Directed Graphs](https://mlsanity.com/paper/2011.05080/) (2020)
- [Distributed Graph Clustering and Sparsification](https://mlsanity.com/paper/1711.01262/) (2017)
- [Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap](https://mlsanity.com/paper/1301.5584/) (2013)
- [Flow-Based Algorithms for Local Graph Clustering](https://mlsanity.com/paper/1307.2855/) (2013)
- [Improved Analysis of Spectral Algorithm for Clustering](https://mlsanity.com/paper/1912.02997/) (2019)
- [Partitioning into Expanders](https://mlsanity.com/paper/1309.3223/) (2013)
- [Testing Cluster Structure of Graphs](https://mlsanity.com/paper/1504.03294/) (2015)
- [Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs](https://mlsanity.com/paper/1904.09710/) (2019)
- [Average Sensitivity of Spectral Clustering](https://mlsanity.com/paper/2006.04094/) (2020)
- [Spectral concentration and greedy k-clustering](https://mlsanity.com/paper/1404.1008/) (2014)
- [Communication-Optimal Distributed Clustering](https://mlsanity.com/paper/1702.00196/) (2017)
- [Planted Models for k-way Edge and Vertex Expansion](https://mlsanity.com/paper/1910.08889/) (2019)

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

- [Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs](https://mlsanity.com/paper/2306.09950/) (2023)
- [Fast and Simple Spectral Clustering in Theory and Practice](https://mlsanity.com/paper/2310.10939/) (2023)
- [Riemannian Optimization on Relaxed Indicator Matrix Manifold](https://mlsanity.com/paper/2503.20505/) (2025)
- [Spectral Toolkit of Algorithms for Graphs: Technical Report (1)](https://mlsanity.com/paper/2304.03170/) (2023)
- [Fast Approximation of Similarity Graphs with Kernel Density Estimation](https://mlsanity.com/paper/2310.13870/) (2023)
- [High-dimensional Clustering onto Hamiltonian Cycle](https://mlsanity.com/paper/2304.14531/) (2023)
- [Explainable Graph Spectral Clustering of Text Documents](https://mlsanity.com/paper/2308.00504/) (2023)
- [TANGO: Clustering with Typicality-Aware Nonlocal Mode-Seeking and Graph-Cut Optimization](https://mlsanity.com/paper/2408.10084/) (2024)
- [Structure-Aware Spectral Sparsification via Uniform Edge Sampling](https://mlsanity.com/paper/2510.12669/) (2025)
- [On Learning the Structure of Clusters in Graphs](https://mlsanity.com/paper/2212.14345/) (2022)
- [Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser](https://mlsanity.com/paper/2305.06541/) (2023)
- [Dynamic Spectral Clustering with Provable Approximation Guarantee](https://mlsanity.com/paper/2406.03152/) (2024)
- [An Improved and Generalised Analysis for Spectral Clustering](https://mlsanity.com/paper/2511.23261/) (2025)

## Abstract (arXiv)

This work studies the classical spectral clustering algorithm which embeds the vertices of some graph G=(VG, EG) into ℝk using k eigenvectors of some matrix of G, and applies k-means to partition VG into k clusters. Our first result is a tighter analysis on the performance of spectral clustering, and explains why it works under some much weaker condition than the ones studied in the literature. For the second result, we show that, by applying fewer than k eigenvectors to construct the embedding, spectral clustering is able to produce better output for many practical instances; this result is the first of its kind in spectral clustering. Besides its conceptual and theoretical significance, the practical impact of our work is demonstrated by the empirical analysis on both synthetic and real-world datasets, in which spectral clustering produces comparable or better results with fewer than k eigenvectors.