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 $\rho$, 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 ${\rho }^2>\alpha \approx 0.338$, where $\alpha$ is Otter's constant so that the number of unlabeled trees with $K$ edges grows as $(1/\alpha {)}^K$. This significantly improves the prior work in terms of statistical accuracy, running time, and graph sparsity.

References in corpus (11)

• De-anonymizing Social Networks
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Testing for Global Network Structure Using Small Subgraph Statistics
• Optimal hypothesis testing for stochastic block models with growing degrees
• Efficient random graph matching via degree profiles
• Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality
• Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model
• From tree matching to sparse graph alignment
• Bayesian estimation from few samples: community detection and related problems
• Testing correlation of unlabeled random graphs
• Exact Matching of Random Graphs with Constant Correlation

Cited by in corpus (4)

• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Statistical limits of correlation detection in trees
• Faster algorithms for the alignment of sparse correlated Erdös-Rényi random graphs
• Graph Matching via convex relaxation to the simplex