# Achieving the Kesten-Stigum bound in the non-uniform hypergraph stochastic block model

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 60 references that are in the map.
- First posted on arXiv 21 Apr 2026.

## Builds on (most cited first, 13 of 13)

- [Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration](https://mlsanity.com/paper/1909.06503/) (2019)
- [Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach](https://mlsanity.com/paper/1807.02884/) (2018)
- [Spectral Thresholds in Correlated Spiked Models and Fundamental Limits of Partial Least Squares](https://mlsanity.com/paper/2510.17561/) (2025)
- [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)
- [Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models](https://mlsanity.com/paper/2306.06845/) (2023)
- [Quartic quantum speedups for community detection](https://mlsanity.com/paper/2510.08494/) (2025)
- [The Algorithmic Phase Transition in Correlated Spiked Models](https://mlsanity.com/paper/2511.06040/) (2025)
- [Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models](https://mlsanity.com/paper/2602.08173/) (2026)
- [Exact Community Recovery under Side Information: Optimality of Spectral Algorithms](https://mlsanity.com/paper/2406.13075/) (2024)
- [Consistent spectral clustering in sparse tensor block models](https://mlsanity.com/paper/2501.13820/) (2025)
- [Higher order trade-offs in hypergraph community detection](https://mlsanity.com/paper/2601.10502/) (2026)
- [Achievability of Heterogeneous Hypergraph Recovery from its Graph Projection](https://mlsanity.com/paper/2603.01268/) (2026)

## Abstract (arXiv)

We study the community detection problem in the non-uniform hypergraph stochastic block model (HSBM), where hyperedges of varying sizes coexist. This setting captures higher-order and multi-view interactions and raises a fundamental question: can multiple uniform hypergraph layers below the detection threshold be combined to enable weak recovery? We answer this question by establishing a Kesten--Stigum-type bound for weak recovery in a general class of non-uniform HSBMs with r blocks, generated according to multiple symmetric probability tensors. In the case r=2, we show that weak recovery is possible whenever the sum of the signal-to-noise ratios across all uniform hypergraph layers exceeds one, thereby confirming the positive part of a conjecture in (Chodrow et al., 2023). Moreover, we provide a polynomial-time spectral algorithm that achieves this threshold via an optimally weighted non-backtracking operator. For the unweighted non-backtracking matrix, our spectral method attains a different algorithmic threshold, also conjectured in (Chodrow et al., 2023). Our approach develops a spectral theory for weighted non-backtracking operators on non-uniform hypergraphs, including a precise characterization of outlier eigenvalues and eigenvector overlaps. We introduce a novel Ihara--Bass formula tailored to weighted non-uniform hypergraphs, which yields an efficient low-dimensional representation and leads to a provable spectral reconstruction algorithm. Taken together, these results provide a principled and computationally efficient approach to clustering in non-uniform hypergraphs, and highlight the role of optimal weighting in aggregating heterogeneous higher-order interactions.