mlsanityData to 7 Oct 2026

Sparse random hypergraphs: Non-backtracking spectra and community detection

arXiv 2203.07346 ↗First posted 14 Mar 2022math.PR math.CO stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

We consider the community detection problem in a sparse q-uniform hypergraph G, assuming that G is generated according to the Hypergraph Stochastic Block Model (HSBM). We prove that a spectral method based on the non-backtracking operator for hypergraphs works with high probability down to the generalized Kesten-Stigum detection threshold conjectured by Angelini et al. (2015). We characterize the spectrum of the non-backtracking operator for the sparse HSBM and provide an efficient dimension reduction procedure using the Ihara-Bass formula for hypergraphs. As a result, community detection for the sparse HSBM on n vertices can be reduced to an eigenvector problem of a 2n× 2n non-normal matrix constructed from the adjacency matrix and the degree matrix of the hypergraph. To the best of our knowledge, this is the first provable and efficient spectral algorithm that achieves the conjectured threshold for HSBMs with r blocks generated according to a general symmetric probability tensor.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 42 of its 87 references that are in the map. First posted on arXiv 14 Mar 2022.

Builds on

42 of 87 references.

References · 42

  1. 2017Community Detection and Stochastic Block Modelscited by 317
  2. 2013Consistency of spectral clustering in stochastic block modelscited by 128
  3. 2016Higher-order organization of complex networkscited by 109
  4. 2014Exact Recovery in the Stochastic Block Modelcited by 77
  5. 2014A statistical model for tensor PCAcited by 72
  6. 2013Spectral redemption: clustering sparse networkscited by 54
  7. 2021Generative hypergraph clustering: from blockmodels to modularitycited by 48
  8. 2013Community detection thresholds and the weak Ramanujan propertycited by 47
  9. 2013A Proof Of The Block Model Threshold Conjecturecited by 35
  10. 2019Nonconvex Low-Rank Tensor Completion from Noisy Datacited by 35
  11. 2017The landscape of the spiked tensor modelcited by 34
  12. 2014Provable Tensor Factorization with Missing Datacited by 31
30 more
  1. 2016Spectral algorithms for tensor completioncited by 27
  2. 2019Community Detection for Hypergraph Networks via Regularized Tensor Power Iterationcited by 26
  3. 2015Consistency of Spectral Hypergraph Partitioning under Planted Partition Modelcited by 23
  4. 2014Spectral Clustering of Graphs with the Bethe Hessiancited by 22
  5. 2018Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approachcited by 20
  6. 2019Hypernetwork Science via High-Order Hypergraph Walkscited by 20
  7. 2018Hypergraph Spectral Clustering in the Weighted Stochastic Block Modelcited by 19
  8. 2021Robust recovery for stochastic block modelscited by 18
  9. 2016Information-theoretic thresholds for community detection in sparse networkscited by 17
  10. 2015Spectral Detection on Sparse Hypergraphscited by 14
  11. 2016Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniquescited by 13
  12. 2021Exact Recovery in the General Hypergraph Stochastic Block Modelcited by 13
  13. 2017Community Recovery in Hypergraphscited by 12
  14. 2021Community Detection in General Hypergraph via Graph Embeddingcited by 12
  15. 2018On the Minimax Misclassification Ratio of Hypergraph Community Detectioncited by 11
  16. 2019Community detection in the sparse hypergraph stochastic block modelcited by 11
  17. 2018Graph powering and spectral robustnesscited by 10
  18. 2021On Estimating Rank-One Spiked Tensors in the Presence of Heavy Tailed Errorscited by 10
  19. 2015Spectral Thresholds in the Bipartite Stochastic Block Modelcited by 9
  20. 2018Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithmcited by 9
  21. 2017Higher-order clustering in networkscited by 7
  22. 2020Robust Hypergraph Clustering via Convex Relaxation of Truncated MLEcited by 7
  23. 2018Robustness of spectral methods for community detectioncited by 6
  24. 2019Deterministic tensor completion with hypergraph expanderscited by 6
  25. 2021Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphscited by 6
  26. 2020Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walkscited by 5
  27. 2020Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessiancited by 4
  28. 2020Learning Sparse Graphons and the Generalized Kesten-Stigum Thresholdcited by 2
  29. 2021A simpler spectral approach for clustering in directed networkscited by 2
  30. 2014Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP'scited by 1

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 2; 2024: 2.

5 papers.

  1. 2022Nonbacktracking spectral clustering of nonuniform hypergraphscited by 4
  2. 2023Multilayer hypergraph clustering using the aggregate similarity matrixcited by 2
  3. 2023Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Modelcited by 2
  4. 2024Community detection with the Bethe-Hessiancited by 2
  5. 2024Low coordinate degree algorithms II: Categorical signals and generalized stochastic block modelscited by 2