# Fundamental Limits of Spectral Clustering in Stochastic Block Models

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2023.

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

- [Heteroskedastic Tensor Clustering](https://mlsanity.com/paper/2311.02306/) (2023)
- [Optimal Clustering of Discrete Mixtures: Binomial, Poisson, Block Models, and Multi-layer Networks](https://mlsanity.com/paper/2311.15598/) (2023)
- [Community detection with the Bethe-Hessian](https://mlsanity.com/paper/2411.02835/) (2024)
- [Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2304.13139/) (2023)
- [Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models](https://mlsanity.com/paper/2306.06845/) (2023)
- [QDCNN: Quantum Deep Learning for Enhancing Safety and Reliability in Autonomous Transportation Systems](https://mlsanity.com/paper/2503.01916/) (2025)
- [Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/2306.12968/) (2023)
- [Community Detection Guarantees Using Embeddings Learned by Node2Vec](https://mlsanity.com/paper/2310.17712/) (2023)
- [Bias-Corrected Joint Spectral Embedding for Multilayer Networks with Invariant Subspace: Entrywise Eigenvector Perturbation and Inference](https://mlsanity.com/paper/2406.07849/) (2024)
- [Optimal Graph Clustering without Edge Density Signals](https://mlsanity.com/paper/2510.21669/) (2025)
- [Query-Limited Community Recovery in Stochastic Block Models](https://mlsanity.com/paper/2606.02055/) (2026)

## Abstract (arXiv)

Spectral clustering has been widely used for community detection in network sciences. While its empirical successes are well-documented, a clear theoretical understanding, particularly for sparse networks where degrees are much smaller than log n, remains unclear. In this paper, we address this significant gap by demonstrating that spectral clustering offers exponentially small error rates when applied to sparse networks under Stochastic Block Models. Our analysis provides sharp characterizations of its performance, backed by matching upper and lower bounds possessing an identical exponent with the same leading constant. The key to our results is a novel truncated ℓ2 perturbation analysis for eigenvectors, coupled with a new analysis idea of eigenvectors truncation.