论文标题
测试超图的统计限制
Statistical Limits for Testing Correlation of Hypergraphs
论文作者
论文摘要
在本文中，我们考虑了$ n $未标记节点上两个$ m $均匀超图之间相关性的假设检验。在零假设下，超图是独立的，而在替代假设下，高度的边缘分布与零假设中的边缘分布相同，但在一些未知的节点置换量后是相关的。我们专注于两种情况：超图是由高斯敌人模型和密集的Erdös-Rényi模型生成的。我们得出尖锐的信息理论测试阈值。在阈值之上，存在一个强大的测试，以区分替代假设和无空假设。在阈值以下，替代假设和零假设是无法区分的。阈值涉及$ m $，并且随着$ m $变大随着$ m $的减少。这表明测试超图（$ M \ geq3 $）的测试相关性比测试图表相关（$ 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$)
