mlsanityData to 7 Oct 2026

Spectral redemption: clustering sparse networks

arXiv 1306.5550 ↗First posted 24 Jun 2013cs.SI cond-mat.stat-mech physics.soc-phcited by 54

Not on the map. Why?

Abstract (arXiv)

Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal, in some cases completely failing to detect communities even when other algorithms such as belief propagation can do so. Here we introduce a new class of spectral algorithms based on a non-backtracking walk on the directed edges of the graph. The spectrum of this operator is much better-behaved than that of the adjacency matrix or other commonly used matrices, maintaining a strong separation between the bulk eigenvalues and the eigenvalues relevant to community structure even in the sparse case. We show that our algorithm is optimal for graphs generated by the stochastic block model, detecting communities all the way down to the theoretical limit. We also show the spectrum of the non-backtracking operator for some real-world networks, illustrating its advantages over traditional spectral clustering.

Key facts. Cited by 54 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 Jun 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 13; 2022: 10; 2023: 10; 2024: 5; 2025: 10; 2026: 6.

54 papers.

Sort:

By area:

  1. 2021A Comprehensive Survey on Community Detection with Deep Learningcited by 63
  2. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 17
  3. 2021Learning Parametrised Graph Shift Operatorscited by 16
  4. 2021Correlation detection in trees for planted graph alignmentcited by 14
  5. 2023Curvature-based Clustering on Graphscited by 14
  6. 2021Spectral embedding for dynamic networks with stability guaranteescited by 13
  7. 2021Graph neural network initialisation of quantum approximate optimisationcited by 13
  8. 2023A Comprehensive Review of Community Detection in Graphscited by 12
  9. 2022Towards Digital Twin Oriented Modelling of Complex Networked Systems and Their Dynamics: A Comprehensive Surveycited by 8
  10. 2021Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clusteringcited by 7
  11. 2023Non-backtracking Graph Neural Networkscited by 7
  12. 2026A solvable high-dimensional model where nonlinear autoencoders learn structure invisible to PCA while test loss misaligns with generalizationcited by 7
38 more
  1. 2021Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphscited by 6
  2. 2021Estimating Graph Dimension with Cross-validated Eigenvaluescited by 6
  3. 2025Optimal Spectral Transitions in High-Dimensional Multi-Index Modelscited by 6
  4. 2022Matrix Completion with Hierarchical Graph Side Informationcited by 5
  5. 2022Sparse random hypergraphs: Non-backtracking spectra and community detectioncited by 5
  6. 2021Nonparametric Modeling of Higher-Order Interactions via Hypergraphonscited by 4
  7. 2021Community detection using low-dimensional network embedding algorithmscited by 4
  8. 2022Nonbacktracking spectral clustering of nonuniform hypergraphscited by 4
  9. 2023Neural-prior stochastic block modelcited by 4
  10. 2024Optimal thresholds and algorithms for a model of multi-modal learning in high dimensionscited by 4
  11. 2021Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truthscited by 3
  12. 2021A Spectral Method for Joint Community Detection and Orthogonal Group Synchronizationcited by 3
  13. 2022Implicit models, latent compression, intrinsic biases, and cheap lunches in community detectioncited by 3
  14. 2025Phase Transition for Stochastic Block Model with more than √n Communities (II)cited by 3
  15. 2021Bayesian reconstruction of memories stored in neural networks from their connectivitycited by 2
  16. 2022Approximate sampling and estimation of partition functions using neural networkscited by 2
  17. 2023Zoo Guide to Network Embeddingcited by 2
  18. 2023Explainable Graph Spectral Clustering of Text Documentscited by 2
  19. 2023Consistency of Lloyd's Algorithm Under Perturbationscited by 2
  20. 2024Community detection with the Bethe-Hessiancited by 2
  21. 2025Low degree conjecture implies sharp computational thresholds in stochastic block modelcited by 2
  22. 2023A Network Science perspective of Graph Convolutional Networks: A surveycited by 1
  23. 2023GRANDE: a neural model over directed multigraphs with application to anti-money launderingcited by 1
  24. 2024Estimating the number of clusters of a Block Markov Chaincited by 1
  25. 2024Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphscited by 1
  26. 2025Stationary distribution of node2vec random walks on household modelscited by 1
  27. 2025Sparse corruption in low-rank matrix inference: the PCA benchmarkcited by 1
  28. 2025Orthogonal Approximate Message Passing with Optimal Spectral Initializations for Rectangular Spiked Matrix Modelscited by 1
  29. 2022Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Thresholdcited by 0
  30. 2022Multi-Frequency Joint Community Detection and Phase Synchronizationcited by 0
  31. 2022One Node at a Time: Node-Level Network Classificationcited by 0
  32. 2022Exact Recovery of Community Detection in dependent Gaussian Mixture Modelscited by 0
  33. 2023Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Modelcited by 0
  34. 2025Complex non-backtracking matrix for directed graphscited by 0
  35. 2025Unfolded Laplacian Spectral Embedding: A Theoretically Grounded Approach to Dynamic Network Representationcited by 0
  36. 2025Phase Transition for Stochastic Block Model with more than √n Communitiescited by 0
  37. 2025A roadmap for curvature-based geometric data analysis and learningcited by 0
  38. 2026Graph energy as a measure of community detectability in networkscited by 0

50 most cited of 54 All 54 (JSON)