# Information Theoretic Limits of Exact Recovery in Sub-hypergraph Models for Community Detection

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 20 references that are in the map.
- First posted on arXiv 29 Jan 2021.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [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)
- [Community Recovery in Hypergraphs](https://mlsanity.com/paper/1709.03670/) (2017)
- [Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm](https://mlsanity.com/paper/1811.06931/) (2018)
- [Statistical and computational thresholds for the planted k-densest sub-hypergraph problem](https://mlsanity.com/paper/2011.11500/) (2020)
- [Exact Partitioning of High-order Planted Models with a Tensor Nuclear Norm Constraint](https://mlsanity.com/paper/2006.11666/) (2020)

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

- [Exact Recovery in the General Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2105.04770/) (2021)
- [Information Limits for Detecting a Subhypergraph](https://mlsanity.com/paper/2105.02259/) (2021)

## Abstract (arXiv)

In this paper, we study the information theoretic bounds for exact recovery in sub-hypergraph models for community detection. We define a general model called the m-uniform sub-hypergraph stochastic block model (m-ShSBM). Under the m-ShSBM, we use Fano's inequality to identify the region of model parameters where any algorithm fails to exactly recover the planted communities with a large probability. We also identify the region where a Maximum Likelihood Estimation (MLE) algorithm succeeds to exactly recover the communities with high probability. Our bounds are tight and pertain to the community detection problems in various models such as the planted hypergraph stochastic block model, the planted densest sub-hypergraph model, and the planted multipartite hypergraph model.