# Sharp detection boundaries on testing dense subhypergraph

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 37 references that are in the map.
- First posted on arXiv 12 Jan 2021.

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

- [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020)
- [Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration](https://mlsanity.com/paper/1909.06503/) (2019)
- [Consistency of Spectral Hypergraph Partitioning under Planted Partition Model](https://mlsanity.com/paper/1505.01582/) (2015)
- [Hypergraph Spectral Clustering in the Weighted Stochastic Block Model](https://mlsanity.com/paper/1805.08956/) (2018)
- [Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares](https://mlsanity.com/paper/1705.02973/) (2017)
- [Spectral Detection on Sparse Hypergraphs](https://mlsanity.com/paper/1507.04113/) (2015)
- [Community Recovery in Hypergraphs](https://mlsanity.com/paper/1709.03670/) (2017)
- [Community Detection in Sparse Random Networks](https://mlsanity.com/paper/1308.2955/) (2013)
- [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)
- [Spectral Thresholds in the Bipartite Stochastic Block Model](https://mlsanity.com/paper/1506.06737/) (2015)
- [Optimal Adaptivity of Signed-Polygon Statistics for Network Testing](https://mlsanity.com/paper/1904.09532/) (2019)
- [Testing Network Structure Using Relations Between Small Subgraph Probabilities](https://mlsanity.com/paper/1704.06742/) (2017)
- [Improved approximation algorithm for the Dense-3-Subhypergraph Problem](https://mlsanity.com/paper/1704.08620/) (2017)

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

- [Detection of Dense Subhypergraphs by Low-Degree Polynomials](https://mlsanity.com/paper/2304.08135/) (2023)
- [Heterogeneous Dense Subhypergraph Detection](https://mlsanity.com/paper/2104.04047/) (2021)
- [Information Limits for Detecting a Subhypergraph](https://mlsanity.com/paper/2105.02259/) (2021)
- [Community detection in censored hypergraph](https://mlsanity.com/paper/2111.03179/) (2021)
- [Optimal community detection in dense bipartite graphs](https://mlsanity.com/paper/2505.18372/) (2025)

## Abstract (arXiv)

We study the problem of testing the existence of a dense subhypergraph. The null hypothesis is an Erdos-Renyi uniform random hypergraph and the alternative hypothesis is a uniform random hypergraph that contains a dense subhypergraph. We establish sharp detection boundaries in both scenarios: (1) the edge probabilities are known; (2) the edge probabilities are unknown. In both scenarios, sharp detectable boundaries are characterized by the appropriate model parameters. Asymptotically powerful tests are provided when the model parameters fall in the detectable regions. Our results indicate that the detectable regions for general hypergraph models are dramatically different from their graph counterparts.