A computational transition for detecting correlated stochastic block models by low-degree polynomials

What the paper says

Detection of correlation in a pair of random graphs is a fundamental statistical and computational problem that has been extensively studied in recent years. In this work, we consider a pair of correlated (sparse) stochastic block models S(n,λn;k,ϵ;s) that are subsampled from a common parent stochastic block model S(n,λn;k,ϵ) with k=O(1) symmetric communities, average degree λ=O(1), divergence parameter ϵ, and subsampling probability s. For the detection problem of distinguishing this model from a pair of independent Erdős–Rényi graphs with the same edge density G(n,λsn), we focus on tests based on low-degree polynomials of the entries of the adjacency matrices, and we determine the threshold that separates the easy and hard regimes. More precisely, we show that this class of tests can distinguish these two models if and only if s>min{α,1λϵ2}, where α≈0.338 is the Otter’s constant and 1λϵ2 is the Kesten–Stigum threshold. Combining a reduction argument in (Li (2025)), our hardness result also implies low-degree hardness for partial recovery and detection (to independent block models) when s<min{α,1λϵ2}. Finally, our proof of low-degree hardness is based on a conditional variant of the low-degree likelihood calculation.