# Information Limits for Detecting a Subhypergraph

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 27 references that are in the map.
- First posted on arXiv 5 May 2021.

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

- [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)
- [The Densest k-Subhypergraph Problem](https://mlsanity.com/paper/1605.04284/) (2016)
- [Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection](https://mlsanity.com/paper/2009.05870/) (2020)
- [Testing Graph Clusterability: Algorithms and Lower Bounds](https://mlsanity.com/paper/1808.04807/) (2018)
- [Sharp detection boundaries on testing dense subhypergraph](https://mlsanity.com/paper/2101.04584/) (2021)
- [Improved approximation algorithm for the Dense-3-Subhypergraph Problem](https://mlsanity.com/paper/1704.08620/) (2017)
- [Information Theoretic Limits of Exact Recovery in Sub-hypergraph Models for Community Detection](https://mlsanity.com/paper/2101.12369/) (2021)
- [Heterogeneous Dense Subhypergraph Detection](https://mlsanity.com/paper/2104.04047/) (2021)

## 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)
- [Detection of Dense Subhypergraphs by Low-Degree Polynomials](https://mlsanity.com/paper/2304.08135/) (2023)

## Abstract (arXiv)

We consider the problem of recovering a subhypergraph based on an observed adjacency tensor corresponding to a uniform hypergraph. The uniform hypergraph is assumed to contain a subset of vertices called as subhypergraph. The edges restricted to the subhypergraph are assumed to follow a different probability distribution than other edges. We consider both weak recovery and exact recovery of the subhypergraph, and establish information-theoretic limits in each case. Specifically, we establish sharp conditions for the possibility of weakly or exactly recovering the subhypergraph from an information-theoretic point of view. These conditions are fundamentally different from their counterparts derived in hypothesis testing literature.