Testing Correlation in Graphs by Counting Bounded Degree Motifs

Abstract

We investigate the problem of detecting correlation between two Erdős-Rényi graphs $G(n,p)$, formulated as a hypothesis testing problem: under the null hypothesis, the two graphs are independent, while under the alternative hypothesis, they are correlated through a latent bijective mapping between their vertex sets. We develop a polynomial-time test by counting bounded degree motifs and prove its effectiveness for any constant correlation coefficient $\ddot{I}$ when the edge connecting probability satisfies $p\ge n^{-1+\hat{I}´}$ for some constant $\hat{I}´>0$. In particular, our guarantee improves the constrain of motif-counting methods from $\ddot{I}\ge \sqrt{\hat{I}}\pm$ to any constant $\ddot{I}=\hat{I}\text{c◯}(1)$, where $\hat{I}\pm \approx 0.338$ is the Otter's constant.

46 pages, 8 figures