Statistical Limits for Testing Correlation of Hypergraphs
This work addresses a fundamental statistical problem for researchers in network analysis and hypothesis testing, providing theoretical limits that are incremental but specific to hypergraph correlation.
The paper tackles the problem of testing correlation between two hypergraphs under null and alternative hypotheses, deriving sharp information-theoretic thresholds that show testing becomes easier for higher-order hypergraphs (m≥3) compared to graphs (m=2).
In this paper, we consider the hypothesis testing of correlation between two $m$-uniform hypergraphs on $n$ unlabelled nodes. Under the null hypothesis, the hypergraphs are independent, while under the alternative hypothesis, the hyperdges have the same marginal distributions as in the null hypothesis but are correlated after some unknown node permutation. We focus on two scenarios: the hypergraphs are generated from the Gaussian-Wigner model and the dense Erdös-Rényi model. We derive the sharp information-theoretic testing threshold. Above the threshold, there exists a powerful test to distinguish the alternative hypothesis from the null hypothesis. Below the threshold, the alternative hypothesis and the null hypothesis are not distinguishable. The threshold involves $m$ and decreases as $m$ gets larger. This indicates testing correlation of hypergraphs ($m\geq3$) becomes easier than testing correlation of graphs ($m=2$)