# Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models

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

## Key facts

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

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [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)
- [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)
- [Effects of Graph Convolutions in Multi-layer Networks](https://mlsanity.com/paper/2204.09297/) (2022)
- [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)
- [Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/1510.05956/) (2015)
- [Unperturbed: spectral analysis beyond Davis-Kahan](https://mlsanity.com/paper/1706.06516/) (2017)
- [Spectral Detection on Sparse Hypergraphs](https://mlsanity.com/paper/1507.04113/) (2015)
- [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)
- [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)
- [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)
- [Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm](https://mlsanity.com/paper/1811.06931/) (2018)
- [Joint Spectral Clustering in Multilayer Degree-Corrected Stochastic Blockmodels](https://mlsanity.com/paper/2212.05053/) (2022)
- [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)
- [Multisection in the Stochastic Block Model using Semidefinite Programming](https://mlsanity.com/paper/1507.02323/) (2015)
- [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)

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

- [Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks](https://mlsanity.com/paper/2412.13754/) (2024)
- [Achieving the Kesten-Stigum bound in the non-uniform hypergraph stochastic block model](https://mlsanity.com/paper/2604.20907/) (2026)

## Abstract (arXiv)

We investigate the unsupervised node classification problem on random hypergraphs under the non-uniform Hypergraph Stochastic Block Model (HSBM) with two equal-sized communities. In this model, edges appear independently with probabilities depending only on the labels of their vertices. We identify the threshold for strong consistency, expressed in terms of the Generalized Hellinger distance. Below this threshold, strong consistency is impossible, and we derive the Information-Theoretic (IT) lower bound on the expected mismatch ratio. Above the threshold, the parameter space is typically divided into two disjoint regions. When only the aggregated adjacency matrices are accessible, while one-stage algorithms accomplish strong consistency with high probability in the region far from the threshold, they fail in the region closer to the threshold. We propose a new refinement algorithm which, in conjunction with the initial estimation, provably achieves strong consistency throughout the entire region above the threshold, and attains the IT lower bound when below the threshold, proving its optimality. This novel refinement algorithm applies the power iteration method to a weighted adjacency matrix, where the weights are determined by hyperedge sizes and the initial label estimate. Unlike the constant degree regime where a subset selection of uniform layers is necessary to enhance clustering accuracy, in the scenario with diverging degrees, each uniform layer contributes non-negatively to clustering accuracy. Therefore, aggregating information across all uniform layers yields better performance than using any single layer alone.