# Strong Consistency, Graph Laplacians, and the Stochastic Block Model

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

## Key facts

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

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

- [On the Stability of Low Pass Graph Filter With a Large Number of Edge Rewires](https://mlsanity.com/paper/2110.07234/) (2021)
- [A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization](https://mlsanity.com/paper/2112.13199/) (2021)
- [ReSync: Riemannian Subgradient-based Robust Rotation Synchronization](https://mlsanity.com/paper/2305.15136/) (2023)
- [Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix](https://mlsanity.com/paper/2208.12227/) (2022)
- [Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models](https://mlsanity.com/paper/2306.06845/) (2023)
- [Improved theoretical guarantee for rank aggregation via spectral method](https://mlsanity.com/paper/2309.03808/) (2023)
- [Statistical Guarantees for Link Prediction using Graph Neural Networks](https://mlsanity.com/paper/2402.02692/) (2024)
- [Bridging Domains with Approximately Shared Features](https://mlsanity.com/paper/2403.06424/) (2024)
- [On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models](https://mlsanity.com/paper/2412.14315/) (2024)
- [When does the mean network capture the topology of a sample of networks?](https://mlsanity.com/paper/2408.03461/) (2024)
- [Structure Amplification on Multi-layer Stochastic Block Models](https://mlsanity.com/paper/2108.00127/) (2021)
- [Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold](https://mlsanity.com/paper/2205.11677/) (2022)
- [Community Detection Guarantees Using Embeddings Learned by Node2Vec](https://mlsanity.com/paper/2310.17712/) (2023)
- [Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models](https://mlsanity.com/paper/2406.05340/) (2024)
- [The Spectral Barycentre of a Set of Graphs with Community Structure](https://mlsanity.com/paper/2502.00038/) (2025)
- [Unfolded Laplacian Spectral Embedding: A Theoretically Grounded Approach to Dynamic Network Representation](https://mlsanity.com/paper/2508.12674/) (2025)
- [Robust Tangent Space Estimation via Laplacian Eigenvector Gradient Orthogonalization](https://mlsanity.com/paper/2510.02308/) (2025)
- [Grassmanian Interpolation of Low-Pass Graph Filters: Theory and Applications](https://mlsanity.com/paper/2510.23235/) (2025)
- [Query-Limited Community Recovery in Stochastic Block Models](https://mlsanity.com/paper/2606.02055/) (2026)
- [Mathematics of Data Science](https://mlsanity.com/paper/2607.11938/) (2026)
- [Exact Community Recovery in Bipartite Networks](https://mlsanity.com/paper/2609.12445/) (2026)

## Abstract (arXiv)

Spectral clustering has become one of the most popular algorithms in data clustering and community detection. We study the performance of classical two-step spectral clustering via the graph Laplacian to learn the stochastic block model. Our aim is to answer the following question: when is spectral clustering via the graph Laplacian able to achieve strong consistency, i.e., the exact recovery of the underlying hidden communities? Our work provides an entrywise analysis (an ℓ∞-norm perturbation bound) of the Fielder eigenvector of both the unnormalized and the normalized Laplacian associated with the adjacency matrix sampled from the stochastic block model. We prove that spectral clustering is able to achieve exact recovery of the planted community structure under conditions that match the information-theoretic limits.