Test dense subgraphs in sparse uniform hypergraph

In network data analysis, one of the fundamental data mining tasks is to find dense subgraphs, which has wide applications in biology, finance, graph compression and so on. In practice, given network data, it’s unknown whether a dense subgraph exists or not. Statistically, this problem can be formulated as a hypothesis testing problem: under the null distribution, there is no dense subgraph while under the alternative hypothesis, a dense subgraph exists. In the graph regime, this problem has been well studied. However, in the hypergraph case, to our knowledge, it’s still open. In this paper, we study the problem in the context of uniform hypergraphs. Specifically, we propose a test statistic, derive its asymptotic distributions under the null and alternative hypothesis, and show the power may approach one when the sample size goes to infinity. Then we use simulation and real data to evaluate the finite sample performance of our test.