Testing Correlation in Graphs by Counting Bounded Degree Motifs
This addresses a hypothesis testing problem in graph theory for detecting correlations, representing an incremental improvement over existing motif-counting methods.
The paper tackles the problem of detecting correlation between two Erdős-Rényi graphs by developing a polynomial-time test based on counting bounded degree motifs, proving effectiveness for any constant correlation coefficient when edge probability is above a threshold, improving constraints from requiring ρ ≥ √α to any constant ρ = Ω(1) where α ≈ 0.338.
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 $Ï$ when the edge connecting probability satisfies $p\ge n^{-1+δ}$ for some constant $δ>0$. In particular, our guarantee improves the constrain of motif-counting methods from $Ï\ge \sqrtα$ to any constant $Ï= Ω(1)$, where $α\approx 0.338$ is the Otter's constant.