Testing network correlation efficiently via counting trees
Cheng Mao, Yihong Wu, Jiaming Xu, Sophie H. Yu
The Annals of Statistics · 2024 · Volume 52 · Issue 6
Abstract
We propose a new procedure for testing whether two networks are edge-correlated through some latent vertex correspondence. The test statistic is based on counting the cooccurrences of signed trees for a family of nonisomorphic trees. When the two networks are Erdős–Rényi random graphs G(n,q) that are either independent or correlated with correlation coefficient ρ, our test runs in n2+o(1) time and succeeds with high probability as n→∞, provided that nmin{q,1−q}≥n−o(1) and ρ2>α≈0.338, where α is Otter’s constant so that the number of unlabeled trees with K edges grows as (1/α)K. This significantly improves the prior work in terms of statistical accuracy, running time and graph sparsity.
Keywords
05C80, 05C85, 62H15, 68Q87, correlated Erdős–Rényi graphs, counting signed trees, Detecting network correlation, Graph matching, Low-degree polynomials
Enable JavaScript for citation tools and additional paper interactions.