# Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 66 references that are in the map.
- First posted on arXiv 23 Aug 2022.

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

- [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)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [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)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration](https://mlsanity.com/paper/1909.06503/) (2019)
- [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)
- [Strong Consistency, Graph Laplacians, and the Stochastic Block Model](https://mlsanity.com/paper/2004.09780/) (2020)
- [Hypergraph Spectral Clustering in the Weighted Stochastic Block Model](https://mlsanity.com/paper/1805.08956/) (2018)
- [Faster Eigenvector Computation via Shift-and-Invert Preconditioning](https://mlsanity.com/paper/1605.08754/) (2016)
- [Spectral Detection on Sparse Hypergraphs](https://mlsanity.com/paper/1507.04113/) (2015)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions](https://mlsanity.com/paper/1502.07738/) (2015)
- [Recovering communities in the general stochastic block model without knowing the parameters](https://mlsanity.com/paper/1506.03729/) (2015)
- [Exact Recovery in the General Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2105.04770/) (2021)
- [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)
- [Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm](https://mlsanity.com/paper/1811.06931/) (2018)
- [Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery](https://mlsanity.com/paper/1404.4749/) (2014)
- [Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE](https://mlsanity.com/paper/2003.10038/) (2020)
- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)

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

- [Consistent line clustering using geometric hypergraphs](https://mlsanity.com/paper/2505.24868/) (2025)
- [Query-Limited Community Recovery in Stochastic Block Models](https://mlsanity.com/paper/2606.02055/) (2026)

## Abstract (arXiv)

Community detection is a fundamental problem in network science. In this paper, we consider community detection in hypergraphs drawn from the hypergraph stochastic block model (HSBM), with a focus on exact community recovery. We study the performance of polynomial-time algorithms which operate on the similarity matrix W, where Wij reports the number of hyperedges containing both i and j. Under this information model, while the precise information-theoretic limit is unknown, Kim, Bandeira, and Goemans derived a sharp threshold up to which the natural min-bisection estimator on W succeeds. As min-bisection is NP-hard in the worst case, they additionally proposed a semidefinite programming (SDP) relaxation and conjectured that it achieves the same recovery threshold as the min-bisection estimator. In this paper, we confirm this conjecture. We also design a simple and highly efficient spectral algorithm with nearly linear runtime and show that it achieves the min-bisection threshold. Moreover, the spectral algorithm also succeeds in denser regimes and is considerably more efficient than previous approaches, establishing it as the method of choice. Our analysis of the spectral algorithm crucially relies on strong entrywise bounds on the eigenvectors of W. Our bounds are inspired by the work of Abbe, Fan, Wang, and Zhong, who developed entrywise bounds for eigenvectors of symmetric matrices with independent entries. Despite the complex dependency structure in similarity matrices, we prove similar entrywise guarantees.