# Exact Recovery in the General Hypergraph Stochastic Block Model arXiv: https://arxiv.org/abs/2105.04770 · HTML: https://mlsanity.com/paper/2105.04770/ ## Key facts - Cited by 13 papers in the map (data through 14 Oct 2026). - Builds on 32 of its 58 references that are in the map. - First posted on arXiv 11 May 2021. ## Builds on (most cited first, 30 of 32) - [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017) - [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014) - [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015) - [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014) - [Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration](https://mlsanity.com/paper/1909.06503/) (2019) - [Minimax Rates of Community Detection in Stochastic Block Models](https://mlsanity.com/paper/1507.05313/) (2015) - [Consistency Thresholds for the Planted Bisection Model](https://mlsanity.com/paper/1407.1591/) (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) - [Hypergraph Spectral Clustering in the Weighted Stochastic Block Model](https://mlsanity.com/paper/1805.08956/) (2018) - [Information Limits for Recovering a Hidden Community](https://mlsanity.com/paper/1509.07859/) (2015) - [Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/1510.05956/) (2015) - [A simple SVD algorithm for finding hidden partitions](https://mlsanity.com/paper/1404.3918/) (2014) - [Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares](https://mlsanity.com/paper/1705.02973/) (2017) - [Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery](https://mlsanity.com/paper/1501.05021/) (2015) - [On the Complexity of Random Satisfiability Problems with Planted Solutions](https://mlsanity.com/paper/1311.4821/) (2013) - [Spectral Detection on Sparse Hypergraphs](https://mlsanity.com/paper/1507.04113/) (2015) - [Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms](https://mlsanity.com/paper/1412.7335/) (2014) - [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) - [Community Recovery in Hypergraphs](https://mlsanity.com/paper/1709.03670/) (2017) - [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) - [Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence](https://mlsanity.com/paper/1509.06418/) (2015) - [Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm](https://mlsanity.com/paper/1811.06931/) (2018) - [A semidefinite program for unbalanced multisection in the stochastic block model](https://mlsanity.com/paper/1507.05605/) (2015) - [Mutual Information in Community Detection with Covariate Information and Correlated Networks](https://mlsanity.com/paper/1912.05375/) (2019) - [Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE](https://mlsanity.com/paper/2003.10038/) (2020) - [Recovering a Single Community with Side Information](https://mlsanity.com/paper/1809.01738/) (2018) - [Multisection in the Stochastic Block Model using Semidefinite Programming](https://mlsanity.com/paper/1507.02323/) (2015) ## Built on by (most cited first, 13 of 13) - [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021) - [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022) - [Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix](https://mlsanity.com/paper/2208.12227/) (2022) - [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) - [Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models](https://mlsanity.com/paper/2306.06845/) (2023) - [Degree Heterogeneity in Higher-Order Networks: Inference in the Hypergraph boldsymbolβ-Model](https://mlsanity.com/paper/2307.02818/) (2023) - [Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Models](https://mlsanity.com/paper/2412.15496/) (2024) - [Community Detection in the Multi-View Stochastic Block Model](https://mlsanity.com/paper/2401.09510/) (2024) - [Matrix Completion with Hypergraphs:Sharp Thresholds and Efficient Algorithms](https://mlsanity.com/paper/2401.08197/) (2024) - [Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithms](https://mlsanity.com/paper/2501.11139/) (2025) - [Consistent line clustering using geometric hypergraphs](https://mlsanity.com/paper/2505.24868/) (2025) - [Exact Recovery in the Data Block Model](https://mlsanity.com/paper/2602.05852/) (2026) ## Abstract (arXiv) This paper investigates fundamental limits of exact recovery in the general d-uniform hypergraph stochastic block model (d-HSBM), wherein n nodes are partitioned into k disjoint communities with relative sizes (p1,..., pk). Each subset of nodes with cardinality d is generated independently as an order-d hyperedge with a certain probability that depends on the ground-truth communities that the d nodes belong to. The goal is to exactly recover the k hidden communities based on the observed hypergraph. We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below the threshold (apart from a small regime of parameters that will be specified precisely). This threshold is represented in terms of a quantity which we term as the generalized Chernoff-Hellinger divergence between communities. Our result for this general model recovers prior results for the standard SBM and d-HSBM with two symmetric communities as special cases. En route to proving our achievability results, we develop a polynomial-time two-stage algorithm that meets the threshold. The first stage adopts a certain hypergraph spectral clustering method to obtain a coarse estimate of communities, and the second stage refines each node individually via local refinement steps to ensure exact recovery.