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

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,tfracλn;k,ε;s) that are subsampled from a common parent stochastic block model mathcal S(n,tfracλ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 ErdHos-R'enyi graphs with the same edge density G(n,tfracλ 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 √α, frac1λ ε2 , where α≈ 0.338 is the Otter's constant and frac1λ ε2 is the Kesten-Stigum threshold. Combining a reduction argument in citeLi25+, our hardness result also implies low-degree hardness for partial recovery and detection (to independent block models) when s< min √α, frac1λ ε2 . Finally, our proof of low-degree hardness is based on a conditional variant of the low-degree likelihood calculation.