mlsanityData to 14 Oct 2026

Consistency of spectral clustering in stochastic block models

arXiv 1312.2050 ↗First posted 7 Dec 2013math.ST stat.ML stat.THcited by 129

Not on the map. Why?

Abstract (arXiv)

We analyze the performance of spectral clustering for community extraction in stochastic block models. We show that, under mild conditions, spectral clustering applied to the adjacency matrix of the network can consistently recover hidden communities even when the order of the maximum expected degree is as small as log n, with n the number of nodes. This result applies to some popular polynomial time spectral clustering algorithms and is further extended to degree corrected stochastic block models using a spherical k-median spectral clustering method. A key component of our analysis is a combinatorial bound on the spectrum of binary random matrices, which is sharper than the conventional matrix Bernstein inequality and may be of independent interest.

Key facts. Cited by 129 papers in the map (data through 14 Oct 2026). First posted on arXiv 7 Dec 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 35; 2022: 30; 2023: 21; 2024: 14; 2025: 14; 2026: 15.

129 papers.

Sort:

By area:

  1. 2021Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Losscited by 313
  2. 2022Connect, Not Collapse: Explaining Contrastive Learning for Unsupervised Domain Adaptationcited by 67
  3. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  4. 2022FedGCN: Convergence-Communication Tradeoffs in Federated Training of Graph Convolutional Networkscited by 24
  5. 2021Optimal Full Ranking from Pairwise Comparisonscited by 16
  6. 2022Scalable Spectral Clustering with Group Fairness Constraintscited by 16
  7. 2022Differentially Private Community Detection for Stochastic Block Modelscited by 15
  8. 2022Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clusteringcited by 15
  9. 2021Spectral embedding for dynamic networks with stability guaranteescited by 13
  10. 2021Latent Space Model for Higher-order Networks and Generalized Tensor Decompositioncited by 13
  11. 2021Community Detection in General Hypergraph via Graph Embeddingcited by 12
  12. 2023What functions can Graph Neural Networks compute on random graphs? The role of Positional Encodingcited by 12
38 more
  1. 2021Residual2Vec: Debiasing graph embedding with random graphscited by 11
  2. 2022From Local to Global: Spectral-Inspired Graph Neural Networkscited by 11
  3. 2021Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitionscited by 10
  4. 2021Asymptotics of Network Embeddings Learned via Subsamplingcited by 10
  5. 2022Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clusteringcited by 9
  6. 2023Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphscited by 9
  7. 2021ALMA: Alternating Minimization Algorithm for Clustering Mixture Multilayer Networkcited by 8
  8. 2021Community detection for weighted bipartite networkscited by 8
  9. 2021Spectral clustering under degree heterogeneity: a case for the random walk Laplaciancited by 7
  10. 2021Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Modelcited by 7
  11. 2023Non-backtracking Graph Neural Networkscited by 7
  12. 2021Matrix factorisation and the interpretation of geodesic distancecited by 6
  13. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  14. 2021Hypothesis Testing for Equality of Latent Positions in Random Graphscited by 5
  15. 2021On the Stability of Low Pass Graph Filter With a Large Number of Edge Rewirescited by 5
  16. 2022Matrix Completion with Hierarchical Graph Side Informationcited by 5
  17. 2022Sparse random hypergraphs: Non-backtracking spectra and community detectioncited by 5
  18. 2022The Multivariate Community Hawkes Model for Dependent Relational Events in Continuous-time Networkscited by 5
  19. 2021Joint Community Detection and Rotational Synchronization via Semidefinite Programmingcited by 4
  20. 2021Nonparametric Modeling of Higher-Order Interactions via Hypergraphonscited by 4
  21. 2021Network Estimation by Mixing: Adaptivity and Morecited by 4
  22. 2021Optimal Orthogonal Group Synchronization and Rotation Group Synchronizationcited by 4
  23. 2021Community detection using low-dimensional network embedding algorithmscited by 4
  24. 2022Nonbacktracking spectral clustering of nonuniform hypergraphscited by 4
  25. 2022Sparse Subspace Clustering in Diverse Multiplex Network Modelcited by 4
  26. 2022Bipartite mixed membership distribution-free model. A novel model for community detection in overlapping bipartite weighted networkscited by 4
  27. 2021SDP Achieves Exact Minimax Optimality in Phase Synchronizationcited by 3
  28. 2021Informative core identification in complex networkscited by 3
  29. 2021A useful criterion on studying consistent estimation in community detectioncited by 3
  30. 2021Spectral learning of multivariate extremescited by 3
  31. 2022Entropic Optimal Transport in Random Graphscited by 3
  32. 2022Exact Community Recovery over Signed Graphscited by 3
  33. 2022Lost in the Shuffle: Testing Power in the Presence of Errorful Network Vertex Labelscited by 3
  34. 2022Consensus Knowledge Graph Learning via Multi-view Sparse Low Rank Block Modelcited by 3
  35. 2023Efficient and Accurate Learning of Mixtures of Plackett-Luce Modelscited by 3
  36. 2023A Unified Framework for Fair Spectral Clustering With Effective Graph Learningcited by 3
  37. 2024Community detection by spectral methods in multi-layer networkscited by 3
  38. 2024Community detection with the Bethe-Hessiancited by 3

50 most cited of 129 All 129 (JSON)