Sharp detection boundaries on testing dense subhypergraph
This work addresses a fundamental statistical testing problem in hypergraph analysis, with implications for network science and data mining, though it is incremental in extending graph-based results to hypergraphs.
The paper tackles the problem of detecting dense subhypergraphs in random hypergraphs, establishing sharp detection boundaries for both known and unknown edge probabilities, and shows that these boundaries differ significantly from those in graph models.
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.