Testing network correlation efficiently via counting trees

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 co-occurrences of signed trees for a family of non-isomorphic trees. When the two networks are Erdős-Rényi random graphs $\mathcal{G}(n,q)$ that are either independent or correlated with correlation coefficient $\ddot{I}$, our test runs in $n^{2+o(1)}$ time and succeeds with high probability as $n\to \infty$, provided that $n\min \{q,1-q\}\ge n^{-o(1)}$ and $\ddot{I}{}^2>\hat{I}\pm \approx 0.338$, where $\hat{I}\pm$ is Otter's constant so that the number of unlabeled trees with $K$ edges grows as $(1/\hat{I}\pm {)}^K$. This significantly improves the prior work in terms of statistical accuracy, running time, and graph sparsity.