Testing Correlation in Graphs by Counting Bounded Degree Motifs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908892179464192 |
|---|---|
| author | Huang, Dong Yang, Pengkun |
| author_facet | Huang, Dong Yang, Pengkun |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_25289 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Testing Correlation in Graphs by Counting Bounded Degree Motifs Huang, Dong Yang, Pengkun Social and Information Networks Statistics Theory 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. |
| title | Testing Correlation in Graphs by Counting Bounded Degree Motifs |
| topic | Social and Information Networks Statistics Theory |
| url | https://arxiv.org/abs/2510.25289 |