Testing Network Correlation Efficiently via Counting Trees

• Activity Number: 504 - Computational Challenges in Modern Statistical Inference
• Type: Invited
• Date/Time: Thursday, August 11, 2022 : 8:30 AM to 10:20 AM
• Sponsor: IMS
• Author(s): Cheng Mao and Yihong Wu and Jiaming Xu* and Sophie H. Yu
• Companies: Georgia Institute of Technology and Yale University and Duke University and Duke University
• Keywords: Graph alignment; tree counting; hypothesis testing; color coding

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 ER random graphs 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 diverges, provided that the network is not overly too sparse or dense and rho^2>alpha~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.