Low-degree evidence for computational transition of recovery rate in stochastic block model

We investigate implications of the (extended) low-degree conjecture (recently formalized in [MW23]) in the context of the symmetric stochastic block model. Assuming the conjecture holds, we establish that no polynomial-time algorithm can weakly recover community labels below the Kesten-Stigum (KS) threshold . In particular, we rule out polynomial-time estimators that, with constant probability, achieve 𝑛 − 0 . 49 correlation with the true communities. Whereas, above the KS threshold, polynomial-time algorithms are known to achieve constant correlation with the true communities with high probability [Mas14, AS15]. To our knowledge, we provide the first rigorous evidence for such a sharp transition in recovery rate for polynomial-time algorithms at the KS threshold. Notably, under a stronger version of the low-degree conjecture, our lower bound remains valid even when the number of blocks diverges. Furthermore, our results provide evidence of a computational-to-statistical gap in learning the parameters of stochastic block models. In contrast, prior work either (i) rules out polynomial-time algorithms with 1 − 𝑜 ( 1 ) success probability [Hop18, BBK + 21a] under the low-degree conjecture, or (ii) degree-poly ( 𝑘 ) polynomials for learning the stochastic block model [LG24]. For this, we design a hypothesis test which succeeeds with constant probability under symmetric stochastic block model, and 1 − 𝑜 ( 1 ) probability under the distribution of Erdős Rényi random graphs. Our proof combines low-degree lower bounds from [Hop18, BBK + 21a] with graph splitting and cross-validation techniques. In order to rule out general recovery algorithms, we employ the correlation preserving projection method developed in [HS17].