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 , , and , and for each define
Assume is large enough that . Let .
Under (correlated SBM with latent matching), sample a parent graph on latent vertices by first drawing labels , then conditionally on sampling edges independently with
Generate by independent edge subsampling from with parameter (keep each parent edge independently in each child with probability , and never add non-parent edges). Then draw a latent uniform permutation , independent of everything else, and observe
where is the relabeled graph. Let be the law of observed .
Under , let be the law where are independent Erdos-Renyi graphs (equivalently, independent even after an unknown relabeling of one graph).
Unsolved Problem
For a test (measurable map from pairs of adjacency matrices to , with meaning ), define
Determine the exact information-theoretic threshold such that
and for no sequence of tests has vanishing total error.
§ 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 (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 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 remains open.
§ References
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.
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.