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 co-occurrences of signed trees for a family of non-isomorphic 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 n^2+o (1) time and succeeds with high probability as n, provided that n\q, 1-q\ n^-o (1) and ρ²>α 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.