Partially Resolved

Exact information-theoretic detection threshold for correlated SBM vs Erdos-Renyi pair

Sourced from the work of Guanyi Chen, Jian Ding, Shuyang Gong, Zhangsong Li

§ Problem Statement

Setup

Fix constants k2k\ge 2, λ>0\lambda>0, and ϵ[1/(k1),1]\epsilon\in[-1/(k-1),1], and for each nn define

pin=λ(1+(k1)ϵ)n,pout=λ(1ϵ)n.p_{\mathrm{in}}=\frac{\lambda(1+(k-1)\epsilon)}{n},\qquad p_{\mathrm{out}}=\frac{\lambda(1-\epsilon)}{n}.

Assume nn is large enough that pin,pout[0,1]p_{\mathrm{in}},p_{\mathrm{out}}\in[0,1]. Let [k]={1,,k}[k]=\{1,\dots,k\}.

Under H1H_1 (correlated SBM with latent matching), sample a parent graph GG^\star on latent vertices [n][n] by first drawing labels σ1,,σni.i.d.Unif([k])\sigma_1,\dots,\sigma_n\overset{i.i.d.}{\sim}\mathrm{Unif}([k]), then conditionally on σ\sigma sampling edges independently with

P((i,j)E(G)σ)={pin,σi=σj,pout,σiσj.\mathbb P\big((i,j)\in E(G^\star)\mid \sigma\big)= \begin{cases} p_{\mathrm{in}},&\sigma_i=\sigma_j,\\ p_{\mathrm{out}},&\sigma_i\ne \sigma_j. \end{cases}

Generate A,BA^\star,B^\star by independent edge subsampling from GG^\star with parameter s[0,1]s\in[0,1] (keep each parent edge independently in each child with probability ss, and never add non-parent edges). Then draw a latent uniform permutation πSn\pi\in S_n, independent of everything else, and observe

A:=A,B:=π(B),A:=A^\star,\qquad B:=\pi(B^\star),

where π(B)\pi(B^\star) is the relabeled graph. Let Pn=Pn,λ,k,ϵ,sP_n=P_{n,\lambda,k,\epsilon,s} be the law of observed (A,B)(A,B).

Under H0H_0, let QnQ_n be the law where A,BA,B are independent Erdos-Renyi graphs G(n,λs/n)G(n,\lambda s/n) (equivalently, independent even after an unknown relabeling of one graph).

Unsolved Problem

For a test ϕn\phi_n (measurable map from pairs of adjacency matrices to {0,1}\{0,1\}, with ϕn=1\phi_n=1 meaning H1H_1), define

Rn(ϕn)=Pn(ϕn=0)+Qn(ϕn=1).R_n(\phi_n)=P_n(\phi_n=0)+Q_n(\phi_n=1).

Determine the exact information-theoretic threshold sIT(λ,ϵ,k)[0,1]s_{\mathrm{IT}}(\lambda,\epsilon,k)\in[0,1] such that

infϕnRn(ϕn)0 as ns>sIT(λ,ϵ,k),\inf_{\phi_n}R_n(\phi_n)\to 0\ \text{as }n\to\infty\quad\Longleftrightarrow\quad s>s_{\mathrm{IT}}(\lambda,\epsilon,k),

and for s<sIT(λ,ϵ,k)s<s_{\mathrm{IT}}(\lambda,\epsilon,k) no sequence of tests has vanishing total error.

§ Discussion

Loading discussion…

§ Significance & Implications

With known alignment, the problem is effectively trivialized by edge-overlap statistics; the latent-permutation formulation is the nontrivial model studied in the source line of work. The exact information-theoretic threshold in this corrected model is still not pinned down, but post-2024 results (including arXiv:2503.06464v2) now give additional algorithmic/impossibility evidence in specific parameter regimes.

§ Known Partial Results

  • Chen et al. (2025): Proven: (i) For low-degree polynomial tests, arXiv:2409.00966v2 establishes a sharp threshold at s>min{α,1/(λϵ2)}s>\min\{\sqrt{\alpha},1/(\lambda\epsilon^2)\} (Theorem 1.3 / abstract). (ii) Recent work, arXiv:2503.06464v2, proves additional algorithmic achievability and impossibility statements in sparse-regime parameter slices (see its abstract for exact quantified regimes).

  • Chen et al. (2025): Heuristic evidence (not yet a full IT characterization): arXiv:2409.00966v2, Remark 1.4 (p. 4) argues plausibility of strong detection at least when s>min{C(k)/(λϵ2),α,1/λ}s>\min\{C^*(k)/(\lambda\epsilon^2),\sqrt{\alpha},\sqrt{1/\lambda}\} by combining prior SBM and correlated-ER intuitions.

  • Chen et al. (2025): Net status after correcting the model to include latent permutation: the exact information-theoretic threshold sIT(λ,ϵ,k)s_{\mathrm{IT}}(\lambda,\epsilon,k) remains open.

§ References

[1]

A Computational Transition for Detecting Correlated Stochastic Block Models by Low-Degree Polynomials

Guanyi Chen, Jian Ding, Shuyang Gong, Zhangsong Li (2025)

arXiv preprint

📍 Introduction: model definition of correlated SBM pair with latent vertex correspondence and testing setup against independent $G(n,\lambda s/n)$; Theorem 1.3 (low-degree threshold); Remark 1.4 (plausibility formula $s>\min\{C^*(k)/(\lambda\epsilon^2),\sqrt{\alpha},\sqrt{1/\lambda}\}$), p. 4 in v2 PDF.

Primary source for the correlated-SBM-vs-ER detection problem and the low-degree threshold; includes an explicit plausibility discussion for stronger detection bounds.

[2]

Correlated SBM Detection and Matching in the Sparse Regime

Guanyi Chen, Jian Ding, Shuyang Gong, Zhangsong Li (2025)

arXiv preprint

📍 Abstract (v2): computationally efficient strong detection above roughly $s>\lambda^{-1/2+\gamma}$ under stated signal conditions, and information-theoretic impossibility below roughly $s<\lambda^{-1/2-\gamma}$ in a complementary sparse-signal regime.

Recent follow-up giving additional sparse-regime detection/matching results relevant to the IT-threshold landscape.

§ Tags