mlsanityData to 14 Oct 2026

Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs

arXiv 1501.06087 ↗First posted 24 Jan 2015math.PR cs.SIcited by 26

Not on the map. Why?

Abstract (arXiv)

A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count non-backtracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we study the largest eigenvalues of the non-backtracking matrix of the Erdos-Renyi random graph and of the Stochastic Block Model in the regime where the number of edges is proportional to the number of vertices. Our results confirm the "spectral redemption" conjecture that community detection can be made on the basis of the leading eigenvectors above the feasibility threshold.

Key facts. Cited by 26 papers in the map (data through 14 Oct 2026). First posted on arXiv 24 Jan 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 8; 2022: 6; 2023: 3; 2024: 2; 2025: 5; 2026: 2.

26 papers.

Sort:

  1. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  2. 2022Effects of Graph Convolutions in Multi-layer Networkscited by 24
  3. 2021Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communitiescited by 22
  4. 2021Robust recovery for stochastic block modelscited by 18
  5. 2021Learning Parametrised Graph Shift Operatorscited by 16
  6. 2022Exact Community Recovery in Correlated Stochastic Block Modelscited by 8
  7. 2023Non-backtracking Graph Neural Networkscited by 7
  8. 2021Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphscited by 6
  9. 2021Estimating Graph Dimension with Cross-validated Eigenvaluescited by 6
  10. 2021Community detection using low-dimensional network embedding algorithmscited by 4
  11. 2022Nonbacktracking spectral clustering of nonuniform hypergraphscited by 4
  12. 2025Phase Transition for Stochastic Block Model with more than √n Communities (II)cited by 4
14 more
  1. 2024Low coordinate degree algorithms II: Categorical signals and generalized stochastic block modelscited by 3
  2. 2025Phase Transition for Stochastic Block Model with more than √n Communitiescited by 3
  3. 2021Exact Recovery of Community Structures Using DeepWalk and Node2veccited by 2
  4. 2023Consistency of Lloyd's Algorithm Under Perturbationscited by 2
  5. 2025Sparse corruption in low-rank matrix inference: the PCA benchmarkcited by 2
  6. 2026Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Modelscited by 2
  7. 2022Stratified Graph Spectracited by 0
  8. 2022A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPscited by 0
  9. 2022Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Thresholdcited by 0
  10. 2023Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Modelcited by 0
  11. 2024Multi-View Stochastic Block Modelscited by 0
  12. 2025Synthetic Image Detection via Spectral Gaps of QC-RBIM Nishimori Bethe-Hessian Operatorscited by 0
  13. 2025A Smooth Computational Transition in Tensor PCAcited by 0
  14. 2026HOPPER: Learnable Hop Extraction for Linearized Graph Sequence Modelscited by 0