Testing network correlation efficiently via counting trees

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.