{"ID":2848472,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.25289","arxiv_id":"2510.25289","title":"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 $ρ$ when the edge connecting probability satisfies $p\\ge n^{-1+δ}$ for some constant $δ\u003e0$. 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.","short_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...","url_abs":"https://arxiv.org/abs/2510.25289","url_pdf":"https://arxiv.org/pdf/2510.25289v2","authors":"[\"Dong Huang\",\"Pengkun Yang\"]","published":"2025-10-29T08:45:14Z","proceeding":"cs.SI","tasks":"[\"cs.SI\",\"math.ST\"]","methods":"[]","has_code":false}