# Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 19 references that are in the map.
- First posted on arXiv 25 Apr 2023.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Concentration and regularization of random graphs](https://mlsanity.com/paper/1506.00669/) (2015)
- [Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit](https://mlsanity.com/paper/2012.09996/) (2020)
- [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)
- [Community detection in the sparse hypergraph stochastic block model](https://mlsanity.com/paper/1904.05981/) (2019)
- [Global and Individualized Community Detection in Inhomogeneous Multilayer Networks](https://mlsanity.com/paper/2012.00933/) (2020)
- [Fundamental Limits of Spectral Clustering in Stochastic Block Models](https://mlsanity.com/paper/2301.09289/) (2023)
- [Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Bound](https://mlsanity.com/paper/2212.08642/) (2022)
- [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)
- [Multiway Spherical Clustering via Degree-Corrected Tensor Block Models](https://mlsanity.com/paper/2201.07401/) (2022)

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

- [Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models](https://mlsanity.com/paper/2306.06845/) (2023)
- [Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks](https://mlsanity.com/paper/2412.13754/) (2024)

## Abstract (arXiv)

Consider the community detection problem in random hypergraphs under the non-uniform hypergraph stochastic block model (HSBM), where each hyperedge appears independently with some given probability depending only on the labels of its vertices. We establish, for the first time in the literature, a sharp threshold for exact recovery under this non-uniform case, subject to minor constraints; in particular, we consider the model with multiple communities. One crucial point here is that by aggregating information from all the uniform layers, we may obtain exact recovery even in cases when this may appear impossible if each layer were considered alone. Besides that, we prove a wide-ranging, information-theoretic lower bound on the number of misclassified vertices for any algorithm, depending on a generalized Chernoff-Hellinger divergence involving model parameters. We provide two efficient algorithms which successfully achieve exact recovery when above the threshold, and attain the lowest possible mismatch ratio when the exact recovery is impossible, proved to be optimal. The theoretical analysis of our algorithms relies on the concentration and regularization of the adjacency matrix for non-uniform random hypergraphs, which could be of independent interest. We also address some open problems regarding parameter knowledge and estimation.