# Statistical Limits for Testing Correlation of Hypergraphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 26 references that are in the map.
- First posted on arXiv 11 Feb 2022.

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

- [Efficient random graph matching via degree profiles](https://mlsanity.com/paper/1811.07821/) (2018)
- [(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs](https://mlsanity.com/paper/1805.02349/) (2018)
- [Seeded Graph Matching via Large Neighborhood Statistics](https://mlsanity.com/paper/1807.10262/) (2018)
- [Testing correlation of unlabeled random graphs](https://mlsanity.com/paper/2008.10097/) (2020)
- [Testing network correlation efficiently via counting trees](https://mlsanity.com/paper/2110.11816/) (2021)
- [Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model](https://mlsanity.com/paper/1907.08880/) (2019)
- [An efficient reconciliation algorithm for social networks](https://mlsanity.com/paper/1307.1690/) (2013)
- [Graph Matching with Partially-Correct Seeds](https://mlsanity.com/paper/2004.03816/) (2020)
- [An Efficient Multilinear Optimization Framework for Hypergraph Matching](https://mlsanity.com/paper/1511.02667/) (2015)

## Abstract (arXiv)

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"os-R'enyi 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≥3) becomes easier than testing correlation of graphs (m=2)