Detecting Correlation Efficiently in Stochastic Block Models: Breaking Otter's Threshold in the Entire Supercritical Regime
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_ | 1866911172663443456 |
|---|---|
| author | Chen, Guanyi Ding, Jian Gong, Shuyang Li, Zhangsong |
| author_facet | Chen, Guanyi Ding, Jian Gong, Shuyang Li, Zhangsong |
| contents | Consider a pair of sparse correlated stochastic block models $\mathcal S(n,\tfracλ{n},ε;s)$ subsampled from a common parent stochastic block model with two symmetric communities, average degree $λ=O(1)$, divergence parameter $ε\in (0,1)$ and subsampling probability $s$. For all $ε\in(0,1)$ and $Δ>0$, we construct a statistic based on the combination of two low-degree polynomials and show that there exists a sufficiently small constant $δ=δ(ε,λ,Δ)>0$ such that if $ε^2 λs>1+Δ$ and $s>\sqrtα-δ$ where $α\approx 0.338$ is Otter's constant, this statistic can distinguish this model and a pair of independent stochastic block models $\mathcal S(n,\tfrac{λs}{n},ε)$ with probability $1-o(1)$. We also provide an efficient algorithm that approximates this statistic in polynomial time.
The crux of our statistic's construction lies in a carefully curated family of multigraphs called \emph{decorated trees}, which enables effective aggregation of the community signal and graph correlation by leveraging the counts of the same decorated tree while suppressing the undesirable correlations among counts of different decorated trees. We believe such construction may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_06464 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Detecting Correlation Efficiently in Stochastic Block Models: Breaking Otter's Threshold in the Entire Supercritical Regime Chen, Guanyi Ding, Jian Gong, Shuyang Li, Zhangsong Data Structures and Algorithms Probability Statistics Theory Consider a pair of sparse correlated stochastic block models $\mathcal S(n,\tfracλ{n},ε;s)$ subsampled from a common parent stochastic block model with two symmetric communities, average degree $λ=O(1)$, divergence parameter $ε\in (0,1)$ and subsampling probability $s$. For all $ε\in(0,1)$ and $Δ>0$, we construct a statistic based on the combination of two low-degree polynomials and show that there exists a sufficiently small constant $δ=δ(ε,λ,Δ)>0$ such that if $ε^2 λs>1+Δ$ and $s>\sqrtα-δ$ where $α\approx 0.338$ is Otter's constant, this statistic can distinguish this model and a pair of independent stochastic block models $\mathcal S(n,\tfrac{λs}{n},ε)$ with probability $1-o(1)$. We also provide an efficient algorithm that approximates this statistic in polynomial time. The crux of our statistic's construction lies in a carefully curated family of multigraphs called \emph{decorated trees}, which enables effective aggregation of the community signal and graph correlation by leveraging the counts of the same decorated tree while suppressing the undesirable correlations among counts of different decorated trees. We believe such construction may be of independent interest. |
| title | Detecting Correlation Efficiently in Stochastic Block Models: Breaking Otter's Threshold in the Entire Supercritical Regime |
| topic | Data Structures and Algorithms Probability Statistics Theory |
| url | https://arxiv.org/abs/2503.06464 |