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,λ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.