# Sparse random hypergraphs: Non-backtracking spectra and community detection

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

## Key facts

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

## Builds on (most cited first, 30 of 42)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [Nonconvex Low-Rank Tensor Completion from Noisy Data](https://mlsanity.com/paper/1911.04436/) (2019)
- [The landscape of the spiked tensor model](https://mlsanity.com/paper/1711.05424/) (2017)
- [Provable Tensor Factorization with Missing Data](https://mlsanity.com/paper/1406.2784/) (2014)
- [Spectral algorithms for tensor completion](https://mlsanity.com/paper/1612.07866/) (2016)
- [Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration](https://mlsanity.com/paper/1909.06503/) (2019)
- [Spectral Clustering of Graphs with the Bethe Hessian](https://mlsanity.com/paper/1406.1880/) (2014)
- [Consistency of Spectral Hypergraph Partitioning under Planted Partition Model](https://mlsanity.com/paper/1505.01582/) (2015)
- [Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach](https://mlsanity.com/paper/1807.02884/) (2018)
- [Hypernetwork Science via High-Order Hypergraph Walks](https://mlsanity.com/paper/1906.11295/) (2019)
- [Hypergraph Spectral Clustering in the Weighted Stochastic Block Model](https://mlsanity.com/paper/1805.08956/) (2018)
- [Robust recovery for stochastic block models](https://mlsanity.com/paper/2111.08568/) (2021)
- [Information-theoretic thresholds for community detection in sparse networks](https://mlsanity.com/paper/1601.02658/) (2016)
- [Spectral Detection on Sparse Hypergraphs](https://mlsanity.com/paper/1507.04113/) (2015)
- [Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques](https://mlsanity.com/paper/1602.06516/) (2016)
- [Exact Recovery in the General Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2105.04770/) (2021)
- [Community Recovery in Hypergraphs](https://mlsanity.com/paper/1709.03670/) (2017)
- [Community Detection in General Hypergraph via Graph Embedding](https://mlsanity.com/paper/2103.15035/) (2021)
- [On the Minimax Misclassification Ratio of Hypergraph Community Detection](https://mlsanity.com/paper/1802.00926/) (2018)
- [Community detection in the sparse hypergraph stochastic block model](https://mlsanity.com/paper/1904.05981/) (2019)
- [Graph powering and spectral robustness](https://mlsanity.com/paper/1809.04818/) (2018)
- [On Estimating Rank-One Spiked Tensors in the Presence of Heavy Tailed Errors](https://mlsanity.com/paper/2107.09660/) (2021)

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

- [Nonbacktracking spectral clustering of nonuniform hypergraphs](https://mlsanity.com/paper/2204.13586/) (2022)
- [Community detection with the Bethe-Hessian](https://mlsanity.com/paper/2411.02835/) (2024)
- [Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models](https://mlsanity.com/paper/2412.21155/) (2024)
- [Multilayer hypergraph clustering using the aggregate similarity matrix](https://mlsanity.com/paper/2301.11657/) (2023)
- [Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2304.13139/) (2023)

## 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.