Low-degree evidence for computational transition of recovery rate in stochastic block model
Authors: Jingqiu Ding
Yiding Hua
Lucas Slot
David Steurer
Venue: NeurIPS 2025 spotlight ()
Keywords: low-degree lower bound
stochastic block model
computational complexity
Primary area: theory

Abstract: We investigate implications of the (extended) low-degree conjecture (recently formalized in [moitra et al2023]) 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 $n^{-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  [massoulie et al 2014,abbe et al 2015]. 

To our knowledge, we provide the first rigorous evidence for such 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 - o(1)$ success probability [Hopkins 18, bandeira et al 2021] under the low-degree conjecture, or (ii) degree-$\text{poly}(k)$ polynomials for learning the stochastic block model [Luo et al 2023].

For this, we design a hypothesis test which succeeeds with constant probability under symmetric stochastic block model, and $1-o(1)$ probability under the distribution of \Erdos \Renyi random graphs.
Our proof combines low-degree lower bounds from [Hopkins 18, bandeira et al 2021]  with graph splitting and cross-validation techniques. 
In order to rule out general recovery algorithms, we employ the correlation preserving projection method developed in [Hopkins et al 17].

iamputationll-tostttiiiiiti Low-degree evidence for computational transition of recovery rate in stochastic block model
Jingqiu Ding ETH Zürich dinggin. ethz.ch ethz.
Yiding Hua
Lucas Slot ETH Zürich
ETH Zürich yiding. chh.ch
lucas.slot@inf.eet
David Steurer
ETH Zürich
david. ethz.cc
Abstract
We investigate implications of the (extended) loro-derree conjecture (recently formalized in [MW23]) in the context of the symmetric stochastic block model. Assuming the conjecture holds, we establish that no polynomia-tiie algorithm can weakly recover community labels below the Keslen-Stigum (KS) threshold. In particular, we rule out polynomial-time estimators that, with constant probability, achieve -0.9 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, AS15J.
To our knowledge, we provide the first rigorous evidence for such a sharp transition in recovery rate for polynomial-time algorithms the KS thresh- old. Notably, under stronger version of the low-degree conjecture, lower bound remains valid even when the number of blocks diverges. Furthermore, our results provide evidence of gap in learning the parameters of stochastic block models.
In contrast, prior work either (i) rules out polynomial-time algorithms with 1 o(()) success probability [Hop18, BBK under the low-degree conjecture, (ii) degree-poly(k) polynomials for learning the stochastic block model [LG24].
For this, we design hypothesis test which succeeeds with constant prob- ability under symmetric stochastic block model, and 1 1 o(1) probability under the distribution of Erdós Rényi random graphs. Our proof combines low-degree lower bounds from [Hop18, BBK*2la] with graph splitting and cross-validation techniques. In order to rule out general recovery algo- rithms, we employ the correlation preserving projection method developed in [HS17].
1 Introduction
The stochastic block model (SBM) is among the most fundamental models in (social) network analysis and information theory, and has been intensively studied for decades
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

[HLL883, MNS12, ABH15, 13M* Abb18] A fascinating phenomenon in the SBM is the sharp computational threshold for weak recovery of its hidden community structure: efficient algorithms are known for achieving constant correlation with the hidden signal when the signal-to-non ratio is above a certain threshold [CO10, DKMZ11, Mas14, AS15], while no polynomial-time algorithms have been discovered below this threshold despite significant research effort. This computational threshold is known as the Kesten-Stigum threshold (KS threshold) in the statistical physics literature [DKMZ11], and it is important topic in both probability theory and theoretical computer science.
Kesten-Stigum threshold in the symmetric stochastic block model. For simplicity, focus on the following special case of the stochastic block model.
Definition 1.1 (Symmetric k-stochastic block model SSBM(n, á e, k)). Let k E N+ be the number of communities, d E N+ be the average degree of the graph, parameter, and л E No be multiple of k. A graph Y E {0, 1) 1) follows the symmetric k-stochastic block model distribution SSBM(n, L n E, k) if it is sampled in the following way: assign each vertex a label uniformly at random from [k], then independently add edges with probability (1 + =) between vertices with the same label and with probability (1 - f between vertices with different labels.
[0, 1] be the bias
Note that, when the bias parameter & = 0, the model reduces to Erdös-Rényi random graphs with average degree d, denoted by G(n, at).
Given graph sampled from SSBM(n, k),, the most fundamental problem to recover the hidden community labels of the vertices, or equivalently to recover the community membership matrix M given by
M := 1, (n))
where x² E [k] is the label of the i-th vertex. In this work, we consider weak recovery of M that is to find a matrix M which correlates with M in the following sense.
Definition 1.2 (Recovery rate and weak recovery in the SBM). For any d E [0, 11, an algorithm achieves recovery rate ò in the k-stochastic block model, if given a random graph sampled d' from SSBM(n, 7 &, k), it outputs a nonzero matrix M E Roxa such that with constant probability,
(M,M) > |||||||||M|||
If the recovery rate 0 satisfies ò Q11,, then the algorithm is said to achieve weak recovery.
The difficulty of achieving weak recovery in the SBM appears to be closely related to the choice of parameters e, k. In particular, [Mas14, 4, MS15] give polynomial-time algorithms for weak recovery above the KS threshold e²d a k22 On the other hand, while it is known that exponential-time algorithms can achieve weak recovery below this threshold (when k > 5) [BMNN16], it is widely believed that no polynomial algorithms exist that achieve weak recovery when e2d k2.
Rigorous evidence for average case complexity. To provide rigorous rigorous evidence for the innate hardness of weak recovery below the Kesten-Stigum threshold, one could follow two general approaches. The first is construct reduction from problems widely believed be hard (such as planted clique [BBH19, BB20] learning with errors (LWF.) [BRST20, GVV22, Tie24J). However, this approach is unlikely to be successful for our problem as no such reductions are known for (other) average-case problems with constant sharp statistical threshold. The second approach is to prove unconditional lower bounds that rule out certain classes of algorithms. For example, those based on sums of squares [BHK*19, KMOW17, JPR*22,
For ease of notation, we will use the adjacency matrix and the graph interchangeably.

---

MRX20], statistical queries [BKW03, Fei17, BBH* or low-degree polynomials [HKP**7, HS17, Hop18, KWB19]. As it appears that significant technical barriers have to be overcome to prove lower bounds against the former two classes for average-case problems with sharp statistical threshold, we focus on the latter.
The low-degree method for hypothesis testing. recent years, the low-degree method has emerged as standard tool for providing rigorous evidence for computational hardness in average-case problems [Hop18, KWB19]. Inspired by the fact that thresholding the likelihood ratio function provides optimal algorithms for hypothesis testing, the low-degree method provides a heuristic for average-case computational hardness by proving lower bounds against the low-degree projection of the likelihood ratio between two distributions from the hypothesis class. In fact, previous works[Hop18, BBK*21a] has provided low-degree hardness evidence for the related hypothesis testing problems on distinguishing the stochastic block model and Erdōs-Rény' distribution with probability 1- o(1). However, significant barrier needs to be overcome for extending their computational lower bound to weak recovery below KS threshold. The reason is that want to rule out recovery algorithms which only need to succeed with constant probability, while below the Kesten-Stige Stigum threshold, the two distributions considered in [8, BBK+ can be distinguished with probability strictly larger than 1/2 by counting triangles in the graph [BM17].
Low-degree recovery lower bound. In this paper, we focus on the implications of the following conjecture of [MW23] in the context of the SBM
Conjecture 1.3 (Low-degree conjecture). Let be distribution from the k-stochastic block model and Q be distribution of Erdōs- Rényi random graphs. For (randomizedd funclions f R R, consider the parameter
Ey-p B(-
Rv,e()==
(1.1)
((x-)((())
Suppose that for any arbirary constant ò E (0, 11, and every polymomial f()) of degree at most n we have R Rf, < O(1). Then, for any function f(-) computable in time exp(1 0.990 taking values in [0, 1] satisfying Ey-p f(Y) > Q(1), we have R2,a(f) & O(1).
The parameter (-) in (1.1) is motivated by Le Cam's method: if the maximum of ( over all computable functions f is bounded by O(1), no algorithm can distinguish between the distributions P and Q with high probability. Intuitively, Conjecture 1.3 tells us that, the maximum of Rr,o (f) is bounded over all low-degree polynomials, it is in fact bounded over all efficiently computable functions.
Assuming this conjecture for P given by the symmetric SBM and Q given by the Erdós-Rényi graph distribution, we aim to clarify the relation between the upper bounds for the low-degree likelihood ratio (proved in [Hop18, BBK BBK+21a]) and lower bounds for computationally efficient algorithms for the SBM. Specifically, we address the following question:
Question 1.4. Assuming Conjecture 1.3, can we rule out polynomial-time algorithms achieving weak recovery (or even non-trivial error rate) in the stochastic block model below the Kesten-Stigum threshold, when the number of communities is universal constant?
Implications for learning stochastic block model. A potential computational-statiitii gap similar to weak recovery can also be observed in the closely related problem of learning the parameters of the stochastic block model [Xu17]. Although [L.G24] established a low- degree recovery lower bound for learning the probability matrix in the symmetric SBM, their result does not imply a lower bound for learning the parameters d, E, as their hard
zSimilar detection-reoovery gap in success probabilities also recently revealed by [HS24] in the context of planted cliques.
'The original conjecture is stated for the closely related spiked Wigner model.
3

---

instance is given by symmetric SBM with fixed parameters. Moreover, when k s log(1) (rather than constant), their lower bound cannot rule out polynomial-time algorithms for achieving the minimax error rate.
As such, address the following question in this paper:
Question 1.5. Assuming Conjecture 1.3, can we provide rigorous evidence for computational--tatistii gap in the error rate of learning the parameters of the stochastic block model?
Main result
2.1
Computational lower bound for weak recovery stochastic block model
We provide the first rigorous evidence that no polynomial-time algorithms can achieve recovery rate ı -0.99 with constant probability below the Kesten-Stigun threshold, assum-
ing Conjecture 1.3.
Theorem 2.1 (Computational lower bound below the KS threshold, see Theorem B.1 for the full statement). Lef k, d E N be such that k & O(1), d & O(1). Assume that for any d' e N such that 0.999d & d' & d, Conjecture 1.3 holds with distribution P given by SSBM(n, d' H E, and distribution Q given by the Erdös-Rényi graph model G(n, 4). Then, no exp(n0.99) time algorithm can achieve recovery rate n -0.99 in the k-stochastic block model when e2d & 0.99k2.
Note that the algorithm which outputs a matrix M reflecting a random partition of the vertices into k communities only achieves vanishing recovery rate 5 s 1/v1i. In contrast, recall that above the KS threshold (when ddd/k2 > 1), polynomial-time algorithms can achieve a recovery rate in ((1) (i.e., weak recovery). To our knowledge, this is the first result showing such sharp transition in the recovery rate that can be achieved by efficient algorithms above and below the KS threshold
Impossible Regime (1 < AsT)
Hard Regime
Easy Regime (1 AAig)
(ATT < < AAig) A
Arr
SNR de2/k2
No algorithm achieves constant correlation
Sub- Sub-exponentia time algo- Polynomial time algorithms rithms cannot achieve achieve Q(11 correlation.
-0.49 correlation.
Under a strengthened low-degree conjecture (see Conjecture A.2 below), our lower bound extends to the regime where the number of communities can be as large as o1))
Theorem (Computational lower bound for diverging number of blocks). Let k, d E N+ be such that k (1), d & (1), Assume that for any d' E N such that 0.999d d' d, Conjecture A.2 holds with distribution P given by SSBM(n, d' и E, k) and distribution Q given by the Manōs--ééniiae graph model G(n, 4 Then no exp(n time algorithm can achieve recovery rate -0.99 in the k-stochastic block model when 22d < 0.99k2.
concurrent work [SW25] also provides rigorous evidence for com- putational lower bound below KS threshold based on low-degree polynomials. They give the first unconditional low-degree recovery lower bound below the KS threshold in the stochastic block model. In our setting, for the task of weak recovery (which is say, achieving constant recovery rate), their lower bound directly rules out estimators based on degree n²
Concurrent work.
For small number of communities k = 2,3,4, 4, there is no iitommationcompptaaii gap, and thus no hard regime. these scenarios, we suspect that there is sharp phase transition recovery rate from n -0.49 to constant

---

polynomials, which captures many natural candidates of algorithmss Such a lower bound is beyond reach with techniques from [Hop18, BBK 21a]. For this, they introduce significantly new techniques in analyzing the low-degree polynomials.
In comparison, we give evidence that sub-exponential time algorithms cannot achieve recovery rate n 0.49 with constant probability below the KS threshold, while polynomial time algorithms are known to achieve weak recovery above the threshold. Our techniques are based on relating the rate of recovery to the low-degree conjecture formulated in [MW23]. Notably, we did not prove new low-degree lower bounds for our main results, but exploited the existing results from [Hop18, BBK 21a].
In a concurrent work, [Li25] established computational lower bounds for random graph matching below sharp thresholds, also based strengthened version of the low-degree conjecture. However, their polynomial-time reduction between hypothesis testing with lopsided success probability and recovery differs significantly from ours.
As we discuss next, our result also has implications for other learning tasks in the stochastic block model.
2.2 Computational lower bound for learning stochastic block model
We give computational lower bounds for learning the stochastic block model under two different error metrics: learning the edge connection probability matrix and the block graphon function.
Definition 2.3 (Edge connection probability matrix for the SBM). In the symmetric stochastic block model SSBM(nn,
d n/ E, k), the edge connection probability matrix 0 [0, 1|mM" has
entries 0 = (1 + [k-1 if i, belong to the same community and 07 (1 - f i, belong to different communities.
Given random graph sampled from distribution SSBM(E, d, k, n), the simple polynomial- time algorithm based on k-SVD outputs a matrix 0 E [0, 1] such that B||0-0'|| < O(2k-d) [Xu17, LG24]. On the other hand, exponential- algorithms based can give estimator which achieves the optimal error rate Elle 1 (log(k) d k2). We give rigorous evidence for the hardness of learning the edge connection probability matrix of symmetric SBMs, by proving the following computational lower bound.
maximum-likelihood
Theorem 2.4 (Computational lower bound for learning the SBM). Let k, d E No be such that k n d & o(r). Assume that for any d' IN such that 0.999d d' & d, Conjecture A.2 holds with distribution P given by SSBM(n, T E, k) and distribution Q given by Erdös-Rényi graph model G(n, )) Then given graph G ~ SSBM(n, & E, k), no ( time algorithun can output O [0, 1 mxn= achieving error rate ||0 - 1 & 0.99kd /4 with constant probability, where 0 is the sampled edge connection probability matrix.
Our computational lower bound matches the guarantees of known efficient algorithms in [Xu17] up to constant factors. $ In comparison, [LG24] show that degree- polynomials cannot give error rate better than O(kd/(*). For standard low-degree conjectures [Hop18, KWB19, SW221, to give evidence of hardness for polynomial-time algorithms, the polynomial degree f needs to be taken as large as log(1). Therefore, their lower bound on the error rate can only match the guarantees of existing algorithm up to logarithmic factors. As a result, they cannot give evidence of a computational-statist
gap for the error rate when Ollog())..
Another error metric considered in [KTM+15, BCS15, BCSZ18, CDD*24] is learning the graphon function. In the context of the symmetric SBM, the graphon function is block-wise constant and given by:
'For completeness, we state this algorithmic result in Appendix F2. WWe also obtain an unconditional low-degree recovery lower bound for learning the k-stochastic block model when k 00001 in Appendix D.

---

Definition 2.5 (Graphon in the symmetric SBM), Let d, k E N* and E E []. Consider the symmetric stochastic block model SSBM(n, & k), Let B E [0, 1 1] be the community
connection probability matrix with diagonal entries given by (1 - =(--)))) ) and non-diagonal entries given by (1 f Let y [0, 1] [k] be mapping such that y(x) [kx]. Then
function W [0, x [0, 1] - [0, 1] is a graphon generating distribution SSBM(n, e,
W y) B 7(0)77)))
We note that in contrast with the edge connection probability matrix, the graphon function only depends on the parameters of the distribution E, d, k. Previous works [BCS15, BCSZ18, KTM*15, CDD consider the following distance metric between graphons:
Definition 2.6 (Gromov- Wasnoo--sssertteinn distance between graphons). Let functions Wi, W2 [0,1] x [0, [0, 1]. We consider the Gromov-Wassersten distance metric
GW(W,, W2) min L.' "" (Wi(((x),((y)) (M(xx,)) dxdy dxdy
where the minimum taken over all measure-preserving bijective mappings.
Given a graph sampled from SSBM(n1 & e, k), our goal is to output a graphon W minimizing GW(W, Wº). [KTM*15] obtains the minimax error rate
k2 +
log(k)
GW(W,W9 s
n2
nd
However, existing polynomial-time algorithms [Xu17, CDD*24] can only achieve error rate
d² n
k
GW(W,W' W $
Although there is lower bound showing that the error term _(k/n)/44 is information- theoretically necessary[BCSII it is not clear whether polynomial time algorithms can achieve better error rate than á kk/d, especially the graph is sparse.
In this paper, we give the first rigorous evidence for a computational-staiittii gap in sufficiently large constant. Theorem 2.7 (Computational lower bound for learnnng block graphon function). Let k, d e N be such that k & O(1), d & o(n). Assume that Conjecture 1.3 holds with distribution P given by SSBM(n, d .. E, k) and distribution Q given by Erdős- Erdős-Rényi Rényi graph model G(n, $). Then no 9x9(1 time algorithon can output a poly(11) (ity(kt--lock graphon function W [0, 1] [0, - [0 with o(1) probability under distribution and distribution Q-
learning the graphon function when the number of blocks
such that GW(W, Wo)
In comparison, [LG24] do not provide any lower bound for learning the graphon function
since their hard instance is a symmetric SBM with fixed distribution catabbuttonpaammmemtt parameters E, e, k.
3 Techniques
3.1 Lower bounds for weak recovery
In this section, we give an overview of the techniques we use to prove lower bounds for weak recovery in the stochastic block model with constant number of blocks and constant average degree d. That is, an overview of our proof of (a special case of) Theorem 2.1.
Suppose for contradiction that have polynomial-time recovery algorithm for SSBM(n, 4 k),, e²d & 0.99k2, that achieves recovery rate ò > Q(n 0.49), in the sense

---

of Definition 1.2. Using this algorithm, we will construct function f(-), which can be evalu- ated in polynomial time, such that (f) > n0 Here, R+ is the parameter (1.1) for the distributions P = SSBM(n, E, k) and Q G(d, n). Assuming the low-degree conjecture (Conjecture 1.3) for this P and Q this implies that there exists a low-degree polynomial f' with ( > ((1). But, since e²d & 0.99k2 is below the KS threshold, this leads to contradiction with the low-degree lower bound of [Hop18] (Theorem A.1).
In the remainder of this section, we show how to construct the function f(), and give sketch of the proof that Rr,e(f) > n0())
Regularization via correlation iecelaation-reeerving projection. We begin with the following tool, which allows us regularize the estimators of the community membership matrix M provided by the recovery algorithm. Suppose that Mo is a matrix achieving correlation with M i.e., satisfying (Mo, M*) || We show that Mn can be projected into a (small) convex set K S Ro containing M", while preserving the correlation (up to constant). Concretely, the convex set K here is given by
K = M |MM M
11 O, TH(M kō
117) n/6 kō
1
(3.1)
In particular, elements of have bounded entries and bounded nuclear norm, which will be crucial in later steps of the proof where we apply Bernstein inequality. To achieve this, make of the correlation preserving projection from [HS17] (see Theorem F.1), which
projects Mo onto a matrix M E K satisfying
(M, > Q(1) ||MM|
In addition, Theorem F.1 promises that || O(Il))I)s) Thus, we find that
(M, M³) > Q(1) |||M|||||| M" Q(1) 6||M 8 2-12)
(3.2)
Importantly, the correlation preserving projection can be implemented in polynomial time via semidefinite programming. See Lemma B.5 for details.
Testing statistics via cross validation. The basic idea is construct f(-) via cross validation.
Given a random graph G, we c G1 with the same vertex set by subsampling each edge in G independently with probability 1-11, where > 0s small constant. Note that if G is drawn from SSBM(n, á 7 e, k), then G1 is distributed according to SSBM(n, (1-1) T k).
G is drawn from G(n, 4), then G₁ is distributed according G(n, (1- ()) We run the polynomial-time recovery algorithm on G1 to obtain an estimate M E R of the community membership matrix M which we regularize using the correlation preserving projection discussed above. Let Y2 denote the adjacency matrix of G2 == G E(G,). Our function f(.) is then defined as
1, if (M, Y, 0, otherwise.
qd 11T) > 0.51
fM)
(3.3)
See Algorithm 3.1 for an overview of the construction of f()). It remains to show that Rf, n01) For this, we establish a lower bound on the expectation Ey-p f(Y) of f under graphs drawn from the SBM and upper bound on the expectation Ey-0 f() of ff under Erdós-Rényi random graphs.

---

Algorithm 3.1 (Test function f()) used in the proof of Theorem 2.1).
Input: A graph G with vertices, given by its adjacency matrix Y.
Output: Test function f(Y) e {0,1}.
Algorithm:
1. Obtain a subgraph G1 of G by subsampling each edge with probability 17-
2. Obtain an estimator Mo by running recovery algorithm on the graph G1-
3. Obtain M by projecting Mo onto the set K defined in (3.1) using the correlation preserving projection.
4. Return f(Y 1(M, Y/ qd 10T> > n,,1), where Y2 is the adjacency matrix of G G(G))
Lower bound on the expectation under the SBM.. First, give lower bound on the expectation of under the distribution SSBM(n, n k), i.e, on
nd 11T) > n 0.51
E Y-P
fY)
P Y-P
(M, Y2
To do so, note that we may decompose Y2 matrix whose entries are independent with mean zero. Then, we have
nd 11
and
M W2, where W2 is random
n
a
End (12 11T, M)
nd 11
(M", M) + MW)
n
The first term on the RHS above is large with constant probability by (3.2). We would like to apply Bernstein inequality the second term, but the matrices W2 and M are not independent. However, as show in Lemma E.3, they are approximately independent in the sense that there exists zero-mean symmetric matrix W2 with independent entries, independent of M, that each entry in W₂- W2 has variance bounded by O(d2/n3)
For ease of presentation, we ignore the difference between W2 and W2 for now, and assume that W2 and M are independent. In this case, note that (W2, M) be written the summation of independent zero-mean random variables, namely
(W2, M) Σ i,J
Wa(i,
where M((,,) j) & O(1/8) for each i, E [n]. (Here, we have used that M. K). Moreover, since [I @[[M)]||) (n))), we have
Σ M n & n i LJ
d Σ
M(i < O(n ..22.. 9 O(nd).
"
By the Bernstein inequality, and using the fact that d Q(n 0.49), then have
P Σ (2(i,))Mi,)) > 0.501
& <exp(=n0001)
As result, when d O(1), O(1), O(1), with constant probability, have
(Y2 nd M Therefore, we have Ey-p fY) Q(1)
ned
(M M) n 0.501 z ōn n 0,501
2 n 0.51 n 0,501
2115.1 0.51).
π
8

---

Upper bound under the null distribution. of f under the Erdós-Rényi distribution G(n, # Our proof shares many ingredients with the proof of the lower bound in the previous section. We show that with high probability under the distribution G(d, n), we have
Next, we give upper bound on the expectation
nd 10 ,M) = 0(15. n
g (12
To do so, we again apply the argument that Y/2 04 11 and M are approximately independent. In particular, let W2 Y/2 ud 11 for some i.i.d. zero-mean symmeriii matrix W2, independent of M, so that each entry in W2 W2 has variance bounded by d2 /22 By the triangle inequality, have
ad 11 M) < < W2, (
(Y2
For simplicity, we again ignore the difference between W2 and W2 here. By the same reasoning as above, and again relying on the properties of M guaranteed by the correlation preserving projection, we have the Bernstein inequality
P[[,W, My > 0 exp(-n001)
As result, when d & O(1) and k & 0(1,, we have g(Y) < 0010 with probability least 1 - exp(-n000) and thus e exp(-n001).
Finishing the proof. Using the lower and upper bound established above, and the fact that f(.) E (0,1), 1}, we get that
Ey-p -y------000
Q(1)
exp(-n0001) > exp(n > w(1).
v (Vary-Q((M))
3.2 Lower bound for learning the stochastic block model
In this section, we give an overview of the techniques used to prove our results on learning the stochastic block model, stated in Section 2.2.
Lower bound for learning edge connection probability matrix. We sketch the proof of Theorem 2.4. We show that if an O(exp(ri) ) >-time algorithm can learn the edge connection probability matrix 0" such that with constant probability, the error rate || - 00 & 0.99kd, then an algorithm with running time exp(ri (n.99. can achieve weak recovery when e²d 0.99k2. The key observation is that, for the symmetric stochastic block model, the edge connection probability matrix is given by 0 (L-rled M + [1-qid where M {1 1/k, -1/k) is the community membership matrix. Therefore, when the estimation error is smaller than 0k99 the estimator Ô Ô-E å achieves weak recovery under the distribution SSBM(n, & E, k), which contradicts the extended low-degree conjecture (Conjecture A.2).
Lower bound for learning graphon function. We sketch the proof of Theorem 2.7. Let Wo be the graphon function underlying the distribution G(n, 2 and W1 be the graphon function underlying the distribution SSBM(n, & E, k). We then have GW(W,, Wi) e2d > 0.99)22
00.99 when
d
Now suppose there is polynomial-time algorithm which, given random graph G sampled from an arbitrary symmetric k-stochastic block model, outputs an n-block graphon function

---

w |0, 1] [0,1] [0, achieving error 3/ v with probability 1 o(1). Then one can construct a testing statistic by taking
(0)= 1 0, otherwise.
1, if & 244 V
We have f(Y) with probability o(1) under the distribution SSBM(n, n' E, k) and f(Y) = with probability - o(1) under the distribution G(n, #). Therefore, we have (f > ((1. Since the function f()) can be evaluated in polynomial time, this contradicts the low-degree lower bound (Theorem A.1), assuming Conjecture 1.3.
References
[Abb18]
Emmanuel Abbe, Communitty defection and stochastic block models: Recent develop- ments, Journal of Machine Learning Research 18 (2018), no. 177, 1-86. 2
[ABH15]
Emmanuel Abbe, Afonso Bandeira, and Georgina Hall, Exact recovery in the stochastic block model, IEEE Transactions on information theory 62 (2015), no. 471-483 2
[AS15]
Emmanuel Abbe and Colin Sandon, Community delection in general stochastic block models: Fundamental limits and efficient algorithms for recovery, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, IEEE, 2015, Pp. 670-688. 1,2
[BB20]
Matthew Brennan and Guy Bresler, Reducibility and statistical-compputaaionnn gaps from secret leakage, Conference on Learning Theory, PMLR, 2020, pp. 648-847.
[BBH19]
Matthew Brennan, Guy Bresler, and Wasim Huleihel, Reducibility and compula- tional lower bounds for problems with planted sparse structure, 2019. 2
[BBH*20] Matthew Brennan, Guy Bresler, Samuel B. Hopkins, Jerry Zheng Li, and Tselil Schramm, Statistical query algorithms and low-degree tests are almost equizalent, ArXiv abs/2009.06100 (2020).3 3
[BBK Afonso S Bandeira, Jess Banks, Dmitriy Kunisky, Christopher Moore, and Alex Wein, Spectral planting and the hardness of refuting cuts, colorability, and communities random graphs, Conference on Learning Theory, PMLR, 2021, pp. 410-473. 1, 3, 5, 13, 14
[BBK+21b]
Spectral planting and the hardness of refuting cuts, colorability, and commu- nities in random graphs, Proceedings of Thirty Fourth Conference on Learning Theory (Mikhail Belkin and Samory Kpotufe, eds.), Proceedings of Machine Learning Research, vol. 134, PMLR, 15-19 Aug 2021, pp. 410-473. 25
[BCS15]
Christian Borgs, Jennifer Chayes, and Adam Smith, Private graphon estination for sparse graphs, Advances in Neural Information Processing Systems 28 (2015). 5,
[BCSZ18]
Christian Borgs, Jennifer Chayes, Adam Smith, and Ilias Zadik, Revealing network structure, confidentially: Improved rates for node-prioate graphon estimation, 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), TEEE, 2018, pp. 533-543. 5,
[BGBK20]
Florent Benaych-Georges, Charles Bordenave, and Antti Knowles, Spectral radii of sparse random matrices. 23
[9KK+19] Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin, A nearly tight sum-of-squares lower bound for the planted clique problem, SIAM Journal on Computing 48 (2019), no. 2, 687-735. 3
10

---

[BKW03] Avrim Blum, Adam Kalai, and Hal Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model, Journal of the ACM (JACM) 50 (2003), no. 4, 506-519. 3
[BM17] Debapratim Banerjee and Zongming Ma, Optimal hypothesis testing for stochastic block models with growing degrees, 2017. 3
[BMNN16] Jessica E. Banks, Cristopher Moore, Joe Neeman, and Praneeth Netrapalli, Information--heerrtte thresholds for community detection in sparse networks, ArXiv
hts/1607.01766 (2016). 2
[BRST20] Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang, Continuous lwe, 2020. 2
[CDD*24] Hongjee Chen, Jingqiu Ding, Tommaso D'Orsi, Yiding Hua, Chih-Hung Liu, and David Steurer, Private graphon estimation via sum-of-squrree Proceedings of the 56th Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC 2024, Association for Computing Machinery, 2024, p. 172-182. 5, 6
[CO10]
Amin Coja-Oghlan, Graph partitioning via adaptive spectral techniques, Combina- torics, Probability and Computing 19 (2010), no. 2, 227-284. 2
[DKZZ11] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová, Asymptotic analysss of the stochastic block model for modular networks and its algorithmic applications, P'hysical Review E 84 (2011), no. 6. 2
[Fel17]
Vitaly Feldman, A general characterization of the statistical query complexity, Confer- ence on learning theory, PMLR, 2017, pp. 785-830. 3
[GJW24]
David Gamarnik, Aukosh Jagannath, and Alexander S. Wein, Hardness of random optimization problems for boolean circuits, low-degree polynomials, and langevin dynamics, SIAM Journal on Computing 53 (2024), no. 1, 1-46. 13
[GVV22] Aparna Gupte, Neekon Vafa, and Vinod Vaikuntanathan, Continuous Iwe is as hard as lwe & applications learning gaussian mixtures, 2022 IEEE 63rd Annual Symposium Foundations of Computer Science (FOCS), IEEE, 2022, pp. 1162- 1173. 2
[HKP*17] Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer, The power of sum-of-squares for detecting hidden structures, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp- 720-7307
[HLL83] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt, Stochastic blockmodels: First steps, Social networks 5 (1983), no. 2, 109-137. 2
[Hop18]
Samuel.B Hopkins, Statistical inference and the sum of squares method, Cornell University, 2018 1, 3, 5, 7, 13, 17, 21
[HS17]
Samuel B. Hopkins and David Steurer, Efficient bayesian estimation from few samples: Community detection and related problems, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017, pp. 379-390. 1, 1,,,,,15,2 24
[HS24]
Shuichi Hirahara and Nobutaka Shimizu, Planted clique conjectures are equivalent, Proceedings of the 56th Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC 2024, Association for Computing Machinery, 2024, 3..556666. 3
[]P Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, and Jeff Xu, Sun-of-squares lower bounds for sparse independent set, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2022, pp. 406- 416.3 3
KMM*13] Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang, Spectral redemption in clustering sparse networks,
11

---

Proceedings of the National Academy of Sciences 110 (2013), no. 52, 20935-20940.
2
[KMOW17] Pravesh K Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer, Sum of squares lower bounds for refuting any csp, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 132-145. 3
[KTM115] Olga Klopp, A. Tsybakov, Nicolas Verzelen MODALX, Crest, and Mistea, Oracle inequalities for network models and sparse graphon estimation, arXiv: Statistics Theory (2015). 5,
[WB199] Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira, Notes on computa- tional hardness of hypothesis tesfing: Predictions using the low-degree likelihood ratio, arXiv preprint arXiv:1907.11636 (2019). 3, 5, 13
[LG24]
Yuetian Luo and Chao Gao, Computational lower bounds for graphon estimation via log-ee polynomials, The Annals of Statistics (2024), no. 5, 2318-2348. 1, 6, 25
[Li25]
Zhangsong Li, Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs, 2025. 5
[Mas14]
Laurent Massoulié, Communitty detection thresholds and the weak ramanujan property, Proceedings of the forty-sixth annual ACM symposium on Theory of computing, 2014, pp. 694-703. 1,2
[MNS12] Elchanan Mossel, Joe Neeman, and Allan Sly, Stochastic block models and recon- sfruction, arXiv preprint arXiv:1202.1499 (2012). 2
[MR220]
Sidhanth Mohanty, Prasad Raghavendra, and Jeff Xu, Lifting sum-of-squares lower bounds: degree-2 degree-4, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020, pp. 840-853.
[MS15]
Andrea Montanari and Subhabrata Sen, Semidefinite Programs on Sparse Random Graphs and their Application to Community Detection, 2015. 2
[MW23]
Ankur Moitra and Alexander Wein, Precise error rates for computationally efficient testing, arXiv preprint arXiv:2311 1.00289 (2023). 1,3, 13
[SW22]
Tselil Schramm and Alexander S Wein, Computational barriers to estimation from low-degree polynomials, The Annals of Statistics 50 (2022), no. 3, 1833-1858. 5
[SW25]
Youngtak Sohn and Alexander S. Wein, Sharp phase transitions in estimation with low-degree polynomials, arXiv preprint (accepted to STOC 2025) (2025). 4
[Tie24]
Stefan Tiegel, Improved hardness results for learning intersections of halfspaces, arXiv preprint arXiv:2402.15995 (2024).
[Xu17]
Jiaming Xu, Rates of convergence of spectral methods for graphon estimation, Interna- tional Conference on Machine Learning, 2017. 3, 5,
12

---

A Preliminaries
A.1 Low-degree framework
Low-degree likelihood ratio lower bound in the SBM. lower bound is a standard framework to provide evidence of hardness for hypothesis testing problems. [8, BBK 2 prove the following theorem on the low-degree lower bound for the stochastic block model:
The low-degree likelihood ratio
Theorem A.1 (Low-degree lower bound for SBM, Thm. 2.20 in [BBK*21a], Let d o(n), n and & [o, 1]. Let μ {0, 1) R be the relative density of SSBM(nn d, E, k) with respect
n1 x Let js be the projection of y to the degree-l polynomials with respect to the norm
induced by G (n, # For any constant ó > 0,
> ni
ife²d (1 8)k, if < 6)k? < 0.99
{ O(log
x is
Oolexp(12)),
Assuming the low-degree conjectures in [Hop18, KWB19), this gives rigorous hardness evidence for distinguishing
planted distribution P: symmetric k-stochastic block model SSBM( 4, e, k),
null distribution Q: Erdós-Rényi random graph G(n, 4),
with probability - o(1) when k is a universal constant and e²d & 0.99k2. However, even assuming the low-degree conjectures for hypothesis testing from [Hop18, KWB19], these works do not rule out polynomial-time weak recovery algorithms under our definition (i.e., algorithms that achieve constant correlation with constant probability).
Extended low-degree hypothesis. To show our lower bounds in the regime where k is polylogarithmic, Conjecture 1.3 is not sufficient. Instead, we rely on the following stronger low-degree hypothesis from [MW23].
Conjecture A.2 (Extended low-degree conjecture). Let P be distribution from the k-stochastic block model and Q be distribution of Erdós Rényi random graphs. Consider the hypothesis testing
problem between Y ~ and ~ Q for distribution P and Q. Let Rp = By-p f(Y
Let
(f
d E (0, 1]. For any (randomizedd function f(-) computable in time exp(11..99) taking values in [0, 1] and satisfying Ep f(Y) > Q(1), we have
Rp.o(f) S max RP.o(f). deg(f)
When aaXdeegf Rf O(1), the conjecture is reduced to Conjecture 1.3. The tended low-degree hypothesis is closely related to the low-degree lower bound for random optimization problems (see [G]W24]).
A.2 Organization
The rest of the paper is organized as follows. We present our main proof ideas in Section 3. In Appendix B, give the formal proof of our computational lower bounds for recovery algorithms conditional on the low-degree conjectures (i.e., the proof of Theorem 2.1). In
Although the original theorem statement is for constant k d, it is easy to see in their analysis that the lower bound holds when = o(1). Also a weaker version the theorem stated in Thm. 8.6.1 of [Hop18].
13

---

Appendix C, we give proofs of our computational lower bounds for parameter learning algorithms conditional on the low-degree conjectures (i.e., the proof of Theorem 2,4 and Theorem 2.7). In Appendix E, we introduce some facts from probability theory used in our paper. In Appendix F, we introduce some existing algorithms from the literature that are used in our paper. In Appendix G, we clarify the upper bound on the low-degree likelihood ratio when the number of blocks diverges, which implicitly obtained in [BBK*21a].
B Computational lower bound for recovery
In this section, prove Theorem 2.1 by showing that there exists an efficient algorithm that reduces testing to weak recovery in SBM. We will show that there exists efficiently computable testing function (shown in Algorithm B.2) that is large with constant probability d if the input is sampled from SSBM(n, n' k) and is small with high probability if the input is sampled from G(n, d/n). This will lead to contradiction with low-degree lower bounds of testing we assume Conjecture 1.3.
Before describing the algorithm, we restate Theorem 2.1 here for completeness.
Theorem B.1 (Full version of Theorem 2.1). Let k, d E N+ be such that k & O(1), & n0)), Assume that for any d' N' such that 0.999d & d' & d, Conjecture 1.3 holds for distribution = SSBM(n, d' E, and distribution Q = G(n, f Then for any small constants 81, 82, no exp(n (n 0.99) time algorithm can achieve recovery rate nt -0.5+b) in the k-stochastic block model when edd & (1 - k2)
The reduction that we consider is the following.
Algorithm B.2 (Reduction from testing to weak recovery).
Input: A random graph G with equal probability sampled from Erdós-Rényi model or stochastic block model, and target recovery rate 6, parameters e, k, d.
Output:
Testing statistics g(Y) E R, where Y is the adjacency matrix.
Algorithm:
1. Let 1 = 0.001 where 82 1 dd/k22 Obtain subgraph G1 by subsampling each edge with probability 1 1J, and let G2
Gj.
2. Obtain estimator Mo by running weak recovery algorithm graph G1.
3. Obtain M by applying correlation preserving projection (see Theorem F.1) on Mo to the set K = (M e
:M + ko 11 2 0, Tr(M + R5 11T) < n/8].
4. Return testing statistics g(Y) (M, Y2 for the graph G2.
nd 1 11T), where Y2 is the adjacency matrix
To prove Theorem B.1, we will show that the testing statistics g(Y) from Algorithm B.2 satisfies the following two lemmas.
Lemma B.3. Let Y be the adjacency matrix of the graph sampled from the symmetric k-stochastic block model SSBM(n, & k) and M E {-1/k, 1/k}nkn be the corresponding community membership matrix. Suppose that (Mo, (M) > -0.++ |I || and [| @(I)M)))..
Then Algorithm B.2 outputs testing statistics g(Y) e R such that g(Y) > ((1050000)
Lemma B.4. Let Y he the adjacency matrix of the graph sampled from Erdós-Rénn Rényi random graph G(n, d/n). With probability at least 1 1 -exp(( exp(-n0.00f,, Algorithm B.2 outputs g(Y) & On 0.5+,133 in polynomial time.
Combining Lemma B.3 and Lemma B.4, Theorem 2.1 follows as corollary.
14

---

Prouf of Theorem 2.1. Suppose that there is exp(n time algorithm which outputs esti- mator Mo such that (Mo, M\) n --55+66 || M Let f(Y) ((V)30.0011/55-0.21 When
edd Q(k2), combining Lemma B.3 and Lemma B.4, we have
Ep fM
exp(n0001b))
v (far
By the low-degree likelihood ratio upper bound Theorem A.1, when e & (1 022k2, we have
E((Y)
& exp(kk).
max ann
Varo(f()))
Since f(Y) can be evaluated in 0(exp(n099)) time, assuming Conjecture 1.3, then have
EfM
ESM & O(1),
S max
(arr(f(M))
d
Varo(f(M)
which leads to contradiction. As result, assuming Conjecture 1.3, we cannot achieve weak recovery in 9x) time when e2d & (1 -
B.1 Correlation preserving projection
In this part, we prove that we can project the estimator into the set of matrices with bounded entries and bounded nuclear norm, while preserving correlation.
Lemma B.5. Let M (-1/k, 1 1/k] uxx be symmetric matrix with rank-(k + 1). For any ô < O(1), given matrix Mo such that (Mo, M > d|[Mo]|F||M there is polynomial time algorithm which outputs M K such that (M, M 1 S|| [||[|M l|s and ||M]| > Ill),))))) where
K M M
11 2 20, Tr(M + k5
20,Tr(M
11") < n/6
Proof. We apply the correlation preserving projection from [HS17] (restated in Theorem F.1). By definition, M ( - 11 is in K. Let N be the matrix that minimizes ||N]| subject to N K' and (N,Ma, > |||M"]]|||Mal where
K' 1 M - 11T O, Tr(M
1 11") <n k
Using ellipsoid method, this semidefinite program can solved in polynomial time. By Theorem F.1, we have (N) Q(1) |||M and ||N]|p > ||I We let M [M N. Then follows that M K, ||M][F ||M|]| and (M, MD) [( |N
B.2
Proof of Lemma B.3
In this section, we prove Lemma B.3.
Proof of Lemma B.3. We consider the decomposition that Y2 nM 11 =nd M W2 where end
W2 a symmetric random matrix with independent and zero mean entries. By Lemma E.3, there exists i.i.d zero mean symmetric matrix W2 that independent with Y,, and satisfies that the entries in W2 W2 are independent with zero mean and have variance bounded by Old3/n² n)²,, conditioning on the subsampled graph Y and community matrix M As result, we have
(Y2
1ld 11T MM n
< n
M M) (W2 W2,,, (W)
15

---

For the first term < end M M,MMM, ,M,, it follows from Lemma B.5 that
end
(M M)
Q
n
dend ||
> Q
n
As with probability at least exp(-n"000), we have ||M > Q(n²), and as result (M', M) > (ndeed)
For bounding the second term (W2 W2, M), condition the subsampled graph Yι and the community matrix M With probability at least - exp(-nx") we have
KW2 - WW, M)I < I[W WallF
[MM]F $
n 2 n² = Vni
For the third term (W2, M), we again conditional on the subsampled graph Yı and the community matrix M We note that it can be written the summation of independent zero-mean random variables
(W2, M) = Σ
Wa(i, (i.
1
where (i,, are independent zero mean variables bounded by O(1/8) for all i & Moreover, we have
Σ
E & n E
d Σ
M(i & Onn 2 π
L =(nd).
By Bernstein inequality, we have
P
Wali, (M.. > 100!
& <xpl exp(-t2/nd (n/(dd++11/))))))
Taking = (12611122 vd and > 0,5t,, we have
Σ iJJ
> p5(4tiii < <exp(-n11)) Wali, (Mi.
P
As a result, when d & (1)) k & ol)) 8 > n 015+0 = ((1/Vd), with constant probability,
we have
nd 11 My > Q(n 0.5t0 Vol. (22
B.3 Proof of Lemma B.4
In this section, we prove Lemma B.4.
11T and M are approximately indepen- dent. More precisely, let W2 = Y2 nd 11 by Lemma E.3, there exists symmetric zero mean matrix W2 with independent entries such that each entry in W2 W2 has zero mean variance bounded by O(d) Od23/n) conditioning on M. By triangle inequality, we have
Proof of Lemma B.4. We will use the fact that Y2 11 "
17d n T1 M)
g(Y) (Y22
(W2 W2. (WW,, M\
16

---

For bounding the first term (W2 - W2, M), we condition on the subsampled graph Y1. With probability at least -
we have
d3 n2+d./3. n²² = Vd
IW2 W2, M) < 1| W2llF |MilE
& n3
V
For the second term, we note that (W2, M) can be written as the summation of independent zero-mean random variables
(W2, M)
Σ Wali
where Wa(i, (i, are independent zero mean variables bounded by O(1/6) for i < Moreover, we have
Σ
d Σ
Mii & On 1 O(nd).
By Bernstein inequality, we have
W2(1, Mi, Σ 1
> 100#
> exp(-F/(nde t/0)
Taking 0.+0 Vd and 8 055+01, we have
P
Wa(i,)M(ii))
< (exp(-n0.001 > 0.55./3
B.4 Proof of Theorem 2.2
In this part, we give the proof of Theorem 2.2, which is the same as the proof of Theorem 2.1 except that we assume stronger low-degree conjecture.
Proof of Theorem 2.2. Suppose that there is polynomial time algorithm which outputs estimator Mo such that (Mo, Mo) > n -0.+bb [MMlll//MMll Let f(Y) 0550 When 0.001k2 & e2d < k2)k,, combining Lemma B.3 and Lemma B.4, we have
fPY 0.00)
Varr(f(Y))
Since f(Y can be evaluated in 000 time, assuming Conjecture 1.3, by [Hop18](stated in Theorem A.1), we have
Ef())
exp((k).
max degif)<n
(ar)(((Y))
(aro(f(Y)
When k2 < n 0.001 this leads to contradiction. As result, assuming Conjecture A.2, we cannot achieve recovery rate n -05++h in polynomial time when e2d < (1 - Q(1))²2
C Computational lower bound for learning stochastic block model
C.1 Computational lower bound for learning the edge connection probability matrix
In this section, prove Theorem 2.4 by showing that there exists an efficient algorithm that reduces testing to learning in SBM. The reduction of algorithm Algorithm C.2 is similar to
17

---

that of Algorithm B.2. The proof of Theorem 2.4 is also similar proof by contradiction to the proof of Theorem 2.1.
Before describing the algorithm, we restate Theorem 2.4 here for completeness.
Theorem C.1 (Restatement of Theorem 2.4). Let k, d N* be such that k & n d & o(n).
Assume that for any d' e N such that 0.999d d' & d, Conjecture A.2 holds with distribution P given by SSBM(n, d' a. k) and distribution Q given by Brdōs-Rémy, graph model G(n, #) Then given graph G SSBM(n, # E, k), no exp(n time algorithm can output O [0, 1 achieving error rate ||e - 1 & 0.99 0.99kd/4 with constant probability, where O is the ground truth sampled edge connection probability matrix.
The reduction that consider is the following.
Algorithm C.2 (Reduction from testing learning).
Input: A random graph G with equal probability sampled from Erdös-Rényí model stochastic block model.
Output: Testing statistics g(Y) E R, where Y is the centered adjacency matrix Algorithm:
1. Obtain subgraph G1 by subsampling each edge with probability 1 17 0.999, and let = G1.
2. Run learning algorithm on G1, and obtain estimator Ô E R
3. Obtain M by running correlation preserving projection on _ 11 to the set
K {M [-1, : | 11 z 0, Tr(M 11") < n).
4. Construct the testing statistics g(Y) (M, Y2 nd 11T), where Y2 is the adjacency matrix for the graph G2.
Before proving Theorem 2.4, we first show the relationship deeteeennearring edge connection probability and weak recovery.
Lemma C.3. Consider the distribution of SSBM(n, & k) with d & ol1), Suppose give graph
Y ~ SSBM(n, & k), the estimator Ô E R achieves error rate ||0 - 0 & 1 vo.99kd with constant probability, then Ô -
-d/nn d/n achieves weak recovery when e2d > 0.99k2.
Proof. By the relation between edge connection probability matrix 0 and the community matrix M We have
11 1,",,"" M = (Ô - 0 M²) + ( d 11T Md) = (6 -Ô-0% M²) + (0
Ed
MM,M² MD)
π1
For the first term, since with constant probability, 11 -0 < v0.99kd, we have
|@- 0 |M> < || 0-I|F < || V0.99kd.
For the second term, since with overwhelming high probability, ||M > 1 - }), we have
Ed < M MD)
ed 1
Ed
|F..
n
m
2vk
Therefore, when e2d 0.99912,
we have
ed
V0.99kd
Ed Md
( 11 MD)
M -
Ω
2vk
2
Vk
On the other hand, by triangle inequality
d
1 11"
& ||@
0-1|
0
d 1
$ O(Vkk
ed
$ <O(ed/vi).
F
n
F
Vk
18

---

Therefore we have
d (Ô d 11", ,M) Q(I IF 110 11 11)).)) π
n
We thus conclude that with constant probability, θ _ 111T achieves weak recovery when edd > 0.99k2.
With Lemma C.3, the proof of lower bound for learning the edge connection probability matrix of stochastic block model follows as corollary.
Proof of Theorem 2.4. By Lemma C.3, suppose an exp(n time algorithm achieves error rate less than 0.99 kkd in estimating the edge connection probability probbbbbilioooobbiliiiityyyy matrix, then in Algorithm C.2,
- achieves weak recovery when e2d 0.99k2. We let f(Y) g00)))0.00124///
We show that with constant probability under P, we have f(Y) 1. We essentially follow the proof of Lemma B.3 with taken as a constant, except that we take a different strategy for bounding (W2 W2, M). By Lemma E.2, we have, with probability at least 1 - o(1), the following spectral radius bounds on the symmetric random matrices
||W - W2llop & O ddogg())
d
Therefore, by Trace inequality, we have
1
- (W2 We, 1
KW2 - W2, MY = I(W2 W2, M
+
11
K1
kō
kō
1
< 1(W2 W2, M +
11
||
1(W2 W2, ko
11
kō
1
1
I|W: W2llop Tr(M
11
+I[W2 Wallop Tr( 11
ko
kō
R n
0
dlog(n)) V=11
(1+
0 (d R
n log(n)
With the same reasoning, by Lemma B.4, with probability at least 1 exp(-, under distribution Q, we have f(Y) = 0. Therefore, we have R > exp(n0.001). Since f(A) can
Since
be evaluated in ((exp(n time, assuming conjecture 1.3 we have
Ef(A)
E E(AA)
RP.2(f) = ((r)(f(A))
max 0990
Varo(f(A))
On the other hand, by low-degree lower bound stated in Theorem A.1, we have
Ef((A & exx(kk?).
deg 9.99
Varo(f(A))
Since we have exp(1 > exp(k?) when k & (1),, this leads to contradiction.
C.2 Computational lower bound for learning graphon
In this part, we give formal proof of Theorem 2.7.
19

---

Theorem C.4 (Restatement of Theorem 2.7). Let k, E N be such that k & O(1), d & o(n). Assume that Conjecture 1.3 holds with distribution P given by SSBM(n, H k) and distribution Q given by Erdös Rényi graph model G(n, 4). Then no exp(n time algorithm
output
4 V with poly(n)-block graphon function W x [0, - [0, 1] such that GW(W,W") < 3H
1 1- (1) probability under distribution and distribution Q(where W is the underlying graphon of the corresponding distribution).
Proof. Let Wo be the graphon function underlying the distribution G(n, 4 and Wi be the graphon function underlying the distribution SSBM(n1, $ E, E),,, we have GW(Wo, Wi) >
0.99 when edd > 0.99)2.
Now suppose there is polynomial time algorithm, which given random graph G sampled from an arbitrary symmetric k-stochastic block model, outputs an n-block graphon function
W: : |0, 1| x [o, 1] [0, 1] achieving error 3n v & with probability 1-o0 o(1). Then one can construct the testing statistics by taking
11, (o,
if GWW,, Wo) < St
f())
l, otherwise
We have f(Y)= with probability 1 1- o(1) under the distribution of symmetric stochastic block model SSBM(n,
& k). By triangle inequality, we have f(Y) 0 with probability 1- o(1) under the distribution G(n, (). Therefore we have R > w(1).
Now since the function W can be represented symmetric matrix with poly(n) number of rows and columns, and moreove since Wo is a constant function,
GW(W, Wo) = -6' J. (W - Wo(x, ())
Therefore, the function f() can be evaluated in polynomial time. This contradicts the low-degree lower bound (Theorem A.1) assuming Conjecture 1.3.
D Low-degree recovery lower bound for learning dense stochastic block model
In this part, we give unconditional lower bound against low-degree polynomial estimators for the edge connection probability matrix in stochastic block model, via implementing reduction from hypothesis testing weak recovery using low-degree polynomials. For simplicity, we focus on the dense graph.
Theorem D.1 (Low-degree lower bound for learning). Let n E No and l & 0001 Let d O(z).
Let I be the set of degree-& polynomials mapping from n symmetric matrices to X symmetric matrices. Suppose 6 E [0, 1|m Y E {0, 1) are edge connection probability matrix and adjacency matrix sampled from symmetrrc stochastic block model SSBM(n, & e, k). Then for k & 0,00 we have
min max fEr
(1f(Y) > Q(k- n).
D.1 Construction of the low-degree polynomial
For simplicity, we define the community matrix of symmetric stochastic block model. Definition D.2 (Community matrix for stochastic block model). Under symmetric stochastic á block model SSBM(n, n &, k), define the community matrix X E (=1) following: (i 1 if vertex i, have the same community label and (i 0 otherwise.
20

---

Given the polynomial function f R R We consider graph with 2n nodes and randomly partition the nodes into two equal-sized sets S1 and S2. Let X à (f(n) / where Y is the subgraph induced by vertices in Sj. We construct the polynomial function
g: RExe - R as following:
g0 aM-((Mp
d X1-12- - Y12 11 ) 11
1. 1/
d
d
(D.1)
// 1
where V12 E Rax= is the adjacency matrix of the bipartite graph between vertices in S and S2, and Y/2 the adjacency matrix of the induced subgraph supported on S2.
We show the lower bound of this polynomial under the symmetric stochastic block model, and the upper bound of this polynomial under the Erdós-Rényi graph model.
Lemma D.3. Let 0", Y be the edge connection probability matrix and adjacency matrix sampled from the planted distribution SSBM(n, A n k). Let X be the community matrix of the subgraph induced
by vertices in Sj. Suppose in Eq. (D.1), BII II < o(n²), then we have Eg(
n
Lemma D.4. When the graph is sampled from the null distribution G(n, 4), we have E Eg(Y) = 0
and VVrr(g(T)) & 1 122011)
Combining Lemma D.3 and Lemma DA,, Theorem D.1 follows as a corollary:
Proof of Theorem D.1. Suppose there is a degree-n polynomial f R R which gives error rate o(n k). Let X
n. ed f()) 4) Then we have
n1 [l 11
n²
k
|| -
kn
& 0
n²
22d2
22
edd
When e²d > 0.001k2 and d = (n)) we have E| X - 1 < o( combining Lemma D.3 and Lemma D.4, we have
Eg()) 0.00
Var(g(Y))
Since g(Y) is degree- polynomial with & & 000 by [Hop18], we have
Eg(Y) & exp(k3))
Var(g((Y)
When exp(k2) & 0.001 this leads to a contradiction. As result, we conclude that no degree- 0.001 polynomial can achieve error rate o(nk).
D.2 Proof of Lemma D.3
In this section, we analyze the property of the polynomial in Eq. (D.1) under the k-symmetric stochastic block model, and give a proof for Lemma D.3.
Proof of Lemma D.3. Let X; E [ be the community matrix for the bipartite graph between S1 and S2, ie for i E S1 and E S2, we have (i, = if j, belongs to the same community and (i, = -1 if i, belongs different communities. Moreover, we let X be the community matrix for the induced subgraph on S₁ and let X; be the community matrix for the induced subgraph on S2. Then we have Y12 Ed x + W12, Y1 = 3d x; Wi and Y/2 ed X + W2, where
n
Wiz, Wi, W2 are independent,
21

---

(W12, W1, W2) is independent with (X Xi, X2),
every entry in W12, Wi, W2 has zero mean.
Then we have
d Eg(Y) = EE (Y12
Xx(222 4 Y/2 xxxi2xXxp x2) + E(W12XWW2, W2) + 2nd
n
ed
E(W12XXx22 W2)
3
ed
E FxX xx X2)
Since XxX X X2) Q(+*t and
(X - xi)X xi) < B|| Xill x & o(n").
Therefore, we have XX x > Qnn+). and the claim follows.
D.3 Proof of Lemma D.4
In this section, we analyze the property of the polynomial defined in Eq. (D.1), under the Erdós-Rényi graph distribution, and give a proof for Lemma D.4.
Proof of Lemma D.4. Under the Erdōs-Rénye graph distribution, the entries in Y/2 á are i.id zero mean random variables, independent with Y12 and (2 the rest of the graph). As result, we have Eg((= 0.
remains bound the variance of the polynomial under the Erdös-Rény Rényi graph distribution, which is say, bound
(1112 =/(MS=
d x
d 11
Eg(r) =
Y12
1/2
Let W12 Y12 1 and W2 Y/2 f. The main observation is that X, Wiz, W2 are all independent. As result, let Z = W12XW12, we have
E(W12XW12, W3) Σ E
Σ EWG d
" BIZZI
As ||||| < O(r) without loss of generality, and || < Vdlog(n) with overwhelming high probability, we have
E|ZZ < 0 nn" (og (m))
Therefore we have
E(W12XW12, 23) o log
By taking the square root, we conclude the proof.
E Probability theory facts
In this section, we provide probability tools that will need in the paper.
22

---

E.1 Concentration of spectral radii of random matrices
The following concentration inequality for the spectral norm of the centered adjacency matrix of stochastic block model will be useful for our proofs.
Theorem E.1 (Spectral norm bound for random matrices, theorem 2.7 in [BGBK20]). Let H E R be symmetrri matrix whose upper triangular entries are independent zero mean random variables. Moreover, suppose that there exist q > 0 and K > 1 such that
max Σ H < 1,
max
H| & k</n
b/
Hy 1/4 4)
Then we have
E|| 2 Vlo((n)
9
Moreover, we have
P[III E||H||| 1] < 2 exp((ccq
As corollary, for stochastic block model, we have the following concentration inequality:
Lemma E.2. Let be the adjacency matrix of random graph with vertex i, independently connected with probability O(i,)) Q(1/n). Lef d = ==1 Ei, O(i,)) j) and suppose O(i, & 2d/ n.
Let H 1 (A- -0. 0). Then for every 10000 lo)( for some small universal constant 0, we V2d
have
|[||||| > t] < 2 2exp(-cfP)
Proof. We vertify that the matrix H here satisfies the conditions in Theorem E.1. Crucially, since ji & 2d/n, we have EE H?, < 1/n First for each i [n], have Σjen E|Hr, 2 1. Finally, we have max;;; |Hiyl < 1. Therefore by taking = 1 and & = 1 in Theorem E.1, we have E||H|| Co/lognn,, and the concentration bound
P[[H|]] > H|| +f] < exxp(_c't2)
where c' is a universal constant. Taking > 1000 log(n) we have the claim.
E.2 Decoupling edge partition
In this section, we give lemma that describes the approximate independence between edge sets of the subsampling process.
Lemma E.3. Let X Ber(p), and let Xı be obtained from X by subsampling with probubility 1-11, ie X1 X,, where & ~ Ber(1 1111) 11) is independent of X. Let X₂ X X,, and X₂ X2 Xx=
Then we have E[ [[X2|X] [1] = E[X2] up and [[ x2) Olp?). Moreover, have
182 X2 < np.
Proof. We first note that
E| 2[X = np = [[[x]]
Next we note that
tpp
E[X2|X1] 1- (1 - n)p (1 X1),
Therefore, we have
np(1- Xi)
2
E[ -2)-
np
<
0(1pp3)
(1 - n)p)
23

---

Corollary E.4. Let Y be the adjacency matrix of random graph with each edge (i, i) sampled with probability p(i, i). Suppose that p(i, i) & for each j [n]. Let Yi be the adljacncc matrix of the graph obtained by subsampling each edge in Y with probability 1 Let Y2 Y1. Then there is a matrix Y/ such that
for every > log(n), 11:22 Y2ll & tnp2n² with probability at least 1 exp(-t),
for every j, E [n], E Y2,1, f) = EE (2 moreover Y2 and are independent,
and finally the entries in Y2 are independent.
Proof. We construct the matrix Y2 in the following way. For each i, we let Yz(i, j) Y2(i, i) H[Y((i, DI n)(i, Then by Lemma F.3, have E. Y22(i,) = E Y2(i, and (( Y2(i, i)) & Olr²p²) In addition, we have (2((i,) Y2(i, i) O(p)).
Furthermore Yg(i, i) and Yı are independent.
Finally since the upper triangular entries in Y are independent, we have the upper triangular entries in Y/ are independent. By Hoeffding bound, with probability at least - exp(-f), we have 11 121l & 'np log(n).
F Useful algorithmic results
In this section, we provide two algorithmic results from previous work that will be useful in our paper.
F.1 Correlation preserving projection
Given vector that has constant correlation with unknown vector Y, [HS17] shows that one project the vector P into convex set containing Y, and preserve the constant correlation with Y.
Theorem F.1 (Correlation preserving projection, theorem 2.3 in [HS17]). Let ò E R* Let C be convex set and Y C. Let be vector with (P, Y) 8 ||P|| ||Y]]- Then, if we let be the vector that minimizes ||[|| subject to C and (P, Q) 8 |[P|| [|Y]|, have
(Q,Y) > 6/2 IIQII ||Y]].
(F.1)
Furthermore, Q satisfies ||QII
8||
We include their proof here for completeness.
Proof. By construction, Q is the Euclidean of into the set (Q CI Q) |III) By Pythagorean inequality, the Euclidean projection into set decreases distances to points into the set. Therefore, ||Y- -112 < ||Y- - - which implies that (Y, Q) > |IQ11 Moreover, (P, Q) > ||[P]||||||, which implies IIQII > S||Y|| by Cauchy-Schwartz. Thus, we can conclude that (Y, Q) > 0/2 ||Y|| |IQ]].
Learning edge connection probability matrix via SVD
Theorem F.2. When > log(n), there is a polynomial time algorithm which given the adjacency matrix of a graph sampled from symmetric k-stochastic block model SSBM(n, 4, e, k), returns an estimator E [0, 1| such that -100 - 01I < kd with high probability.
24

---

Proof. We take as the best rank-k approximation for the adjacency matrix. Then since ||A - l0lopp Vkd with high probability, we have - Vkd with high probability. By triangle inequality, we have ||0 0* llopp & 2vd. As result, we have || 0 & 2Vkd.
G Low-degree lower bound beyond constant number of blocks
By extending the result of [BBK*21b]] we can get more general bound (with respect to k) on low degree likelihood ratio of k-SBM. The proof the extended result follows trivially from the proof of Theorem 2.20 of [BBK*21b] Therefore, we only provide a proof sketch by pointing out the simple modifications that we need from the original proof.
Theorem G.1 (Restatement of Theorem A.1). Let d o(n), k n and E [0, 1]. Let be the relative density of SBM (n, d, E, k) with respect G(n, # Let μ be
:: {0, 1 pxn
d the projection of to the degree-f polynomials with respect to the norm induced by G n, n constant > 0,
For any
> n n0))
if (1+ 8)k,
>> O(logn)
| is
< Os(ex((k3)),
if:2d (1 (1-8)k2 << n.99
Proof. In this proof, we stick to the notations of [BBK+ The only modification we need is that the size of the ô-net of the unit sphere in R denoted by C(6, k), is equal to exp(Os((k), The size the ò-net C(O, k) is crucial in Proposition 6.4 and Proposition 6.5 of [BBK+21b] and is treated as constant the proof of Theorem 2.16 and Theorem 2.20 of [BBK*21b].
By plugging k) = Os(exp(k)) (k)) into the upper bound of the small deviation term L1 in the proof of Theorem 2.16 of [BBK*21b], it follows that we have ||=00| Os(exp(k)) for the likelihood ratio L and D & o(n/log(n) Then, the bound on low-degree likelihood ratio of k-SBM follows from the same reduction as in proof of Theorem 2.20 of [BBK' 21b], and we get edd/(1 d/n) & 1. As o(n), we get the claimed bound on low-degree likelihood ratio.
H Conclusion and future directions
Based on low-degree heuristics, paper gives rigorous evidence for computational phase transition of recovery at the Kesten-Stigum threshold. We view our work as a first step in studying this phenomenon, leaving open many interesting questions:
Below the Kesten-Stigum threshold, suppose we are given an initalization achieving recovery rate n 0.49 could we boost the accuracy in polynomial time to get a weak recovery algorithm?
Can we show a computatiionalssattitiiaa gap for learning the graphon function when the number of blocks satisfies vn (as in [LG24])?
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All the theorems in the introduction section are later formally proved in later sections. See Appendix A.2.
Guidelines:
The answer NA means that the abstract and introduction do not include the
claims made in the paper.
The abstract and/ or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Does the paper discuss the limitations of the work performed by the authors?
Question:
Answer:
[Yes]
Justification: Yes, we dicussed about the limitations in the result section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g,, independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e-g., if the approach was only tested on few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
taken in low lighting. Or speech-to-text
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in
26

---

favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assump- tions and a complete (and correct) proof?
Answer: [Yes]
Justification: Please see Appendix A.2 for the related proofs for each theorem stated in the result section.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be com- plemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: It is pure theoretical paper with no experiments, so the question is not applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
the contribution is a dataset and/ or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways, For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or the contribution is specific model and empirical evaluation, may be necessary either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlP' does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
27

---

(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., large language model), then there should either be a way to access this model for reproducing the results or way to reproduce the model (e.g,, with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibile case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited some way (e.g,, to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
may be tricky in some cases, in which
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: there is experiments in the paper, so the question is not applicable.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. crubllc/guides/Coeeeieee
ssi ssionPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submis- cc/publicc /uudiiis/////eeuuumiii
sion guidelines titt::://iip..ccppblii////////// for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e-g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: It is theoretical paper paper which does not include experiments.
28

---

Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question:
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train /test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should given (e.g,, Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA]
Justification: The paper does not include experiments
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
29

---

9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htttps///eerrisss.cppplcc/tcccce
Answer: [Yes]
Justification: The paper follows the Neurips Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdittion.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses about potential computational complexity in statistical physics model and there is no societal impact implications in the short term.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness con- siderations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security consider- ations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there direct path to any negative applications, the authors should point out. For example, it is legitimate to point out that an improvement the quality of generative models could be used generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technol- ogy being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
30

---

Answer:
[NA]
Justification:
The paper does not pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines restrictions to access the model or implementing safety filters.
Datasels that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g,, code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g,, CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. this information is not available online, the authors are encouraged reach out the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset code/ moodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
31

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [No]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [No]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: the core method development in this research does not involve LLMs any important, original, or non-slandard components.
Guidelines:
32

---

The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy http:://eerrrss.ccooofeeeeeeeee/ for what should should not be described.
33


Reviews:
[{"review_id": "hObt69HM5d", "reviewer": "Reviewer_ZnPh", "summary": "This paper deduces strong lower bounds against recovery (estimation) in the sparse stochastic block model from a precise and strengthened version of the low-degree conjecture proposed in the recent work [MW23]. In particular, the authors' main result shows that, if there existed an estimation algorithm that estimated the matrix of community memberships (more precisely, the matrix whose entries show which nodes belong to the same community) even slightly better than a random guess of the partition into communities, for parameters slightly away from the boundary of the regime where the problem is conjectured to be computationally hard, then the conjecture formulated by [MW23] would be false. That conjecture is quite far from directly implying such a statement, so a rather subtle construction is required to translate the conjecture into this result. The authors also include some ancillary lower bounds that this implies for learning the parameters (in particular, the connection probabilities) of a stochastic block model, in various metrics.", "questions": "- I would like to see some more discussion of how one might arrive at the cross-validation idea. What goes wrong if one does not partition the given network into essentially two independent samples correlated with the same community structure? I assume that on a technical level it is this independence that plays an important role, but it is hard to pinpoint where that is so important.\n\n- If I understand correctly, the authors' construction of the function f(Y) involves not just the input graph Y, but also some ancillary randomness, in order to perform the subsampling involved in the cross-validation construction. So, in order for the argument to go through, Conjecture 1.3 should also allow for such randomized algorithms f? (As an aside, it is an interesting question whether this extra randomness is necessary or not, and while sometimes papers about low-degree algorithms mention that randomized algorithms might equally well be allowed in formulations of such conjectures, I am not aware of a situation where it has played such an important role before.)\n\n- The discussion of the concurrent work [SW25] is a little confusing---the setups and conclusions are rather different, because that work directly considers how well low-degree polynomial algorithms can perform estimation, while this work considers how well arbitrary algorithms can perform, conditional on the conjecture of [MW23]. Could the authors clarify this point? Perhaps mentioning the \"low-degree MMSE\" that [SW25] analyze might be helpful.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths: The main result is interesting and non-trivial to prove, coming from a clever construction of a function giving a good hypothesis test (in a certain precise \"$L^2$ sense\" adapted to the low-degree polynomials analysis) starting from a function estimating the community assignment. The authors' construction is based on cross-validating a given estimator, an idea I found intuitive but surprising, and that seems entirely original to this work as far as I can tell. I think this is a worthwhile contribution that deserves some attention and further study. The paper is also well-written and does a good job surveying related work and explaining the significance of the main result, which is rather technical-looking and might otherwise be difficult to contextualize for a reader who is not very familiar with either stochastic block models or low-degree algorithms.\n\nWeaknesses: As far as I can tell, the above construction of a testing function is the only substantial theoretical innovation in the paper. The rest of the argument follows fairly directly with straightforward probability tools and one important tool from related literature (the correlation-preserving projection from the early work of Hopkins and Steurer) that is used in a black-box fashion. Relatedly, the main hardness result differs from previous similar results mostly in the details: what probability of success can an algorithm have, precisely how much estimation error can it make, etc. Thus it is a bit \"in the weeds\" of the stochastic block model and maybe of more interest to specialists. But, counterbalancing that, this style of proof has not been used before for the stochastic block model (or generally for discrete problems, to my knowledge), so I think the introduction of this argument together with the cross-validation construction may well turn out to inspire some follow-up work.", "was_revised": true, "final_justification": "I did not raise any substantial issues but just a few clarifying questions, and the authors replied to my satisfaction. I am leaving my positive rating of the paper unchanged.", "rebuttal": "Thank you for your review and constructive feedback!\n\n1. Our proof relies on the fact that the weak recovery estimator and the graph for cross validation are almost independent. Without the graph splitting procedure, the weak recovery estimator and the graph edges can be arbitrarily correlated. As a result, the testing statistics under null distribution can be very large since the inner product of the centered adjacency matrix and the estimator can be very large. Particularly, the almost independence is required to upper bound the inner product of the centered adjacency matrix and the weak recovery estimator with Bernstein inequality.\n\n2. Yes, conjecture 1.3 should allow randomized algorithms, we will clarify this in the final version of the paper. We totally agree that derandomizing our sample splitting algorithm is an interesting open problem. \n\n3. Indeed, [SW25] directly provides unconditional lower bound on the low-degree MMSE, while our results rely on the low-degree conjecture. We list it as concurrent work, as both work provides computational lower bounds for weak recovery below the sharp Kesten-Stigum threshold, under the low-degree framework."}, {"review_id": "pbpFEr6fk5", "reviewer": "Reviewer_91pb", "summary": "This work studies the computational hardness for weak recovery in Stochastic Block Models (SBMs). It has been conjectured that the Kesten-Stigum (KS) threshold is the computational efficiency threshold for beating the random guess on community labels on SBM. The main result of this paper states that for a slowly growing number of communities, no sub-exponential time algorithm can achieve weak recovery assuming a low-degree conjecture. This computational hardness result also implies computational lower bounds for learning the edge connection probability matrix of symmetric SBMs and learning block graphon function. These results establish interesting computational-statistical gaps with solid contributions to the literature.", "questions": "1. I notice a very recent paper on the same topic, by Chin, Mossel, Sohn, and Wein [1]. They establish the low-degree polynomial hardness result on weak recovery for $k \\ll \\sqrt{n}$. Do you believe the techniques used in your submission can potentially extend Theorem 2.2 to a wider regime on $k$, or we can actually find sub-exponential algorithms succeed on weak recovery when $n^{o(1)} \\ll k\\ll \\sqrt{n}$?\n\n2. Is the exponential of the rate $n^{-0.49}$ kind of arbitrary depending on the specific constants you choose in the analysis, as long as it is negative?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\n1. This is one of the recent breakthroughs on providing rigorous evidence [1,2] for a sharp phase transition at the KS threshold.\n2. Although the main result is not an unconditional lower bound on the weak recovery, the assumption on the low-degree conjecture makes it possible to rule out all algorithms run in time $\\exp(n^{0.99})$.\n3. The computational lower bounds on learning SBM are either new or better (in the regimes discussed in this paper) than prior works.\n4. The writing is very clear, well-organized, and easy to follow.\n\n**Weaknesses**\n\nThe techniques used in this paper seemingly limit the generalization of the results to a faster growing $k$.\n\n\n---\nReference\n\n[1] Sohn, Youngtak, and Alexander S. Wein. \"Sharp phase transitions in estimation with low-degree polynomials.\" Proceedings of the 57th Annual ACM Symposium on Theory of Computing. 2025.\n\n[2] Chin, Byron, et al. \"Stochastic block models with many communities and the Kesten--Stigum bound.\" arXiv preprint arXiv:2503.03047 (2025).", "was_revised": true, "final_justification": "My questions have been resolved by the authors' responses. Those points were relatively minor and my review remains very positive. I keep my score as accept.", "rebuttal": "Thank you for your constructive feedback and pointing out related literature!\n\n1. This is a very good question! It is not clear to us whether sub-exponential time algorithms exist in this regime. For hardness, we would expect that significantly new techniques are required to prove low degree lower bounds in this regime.\n\n2. We can get lower bound for recovery rate $n^{-0.5+\\delta}$ for any small constant $\\delta$. We cannot get lower bound below the rate $n^{-0.5}$ , as such rate is achieved by algorithms which output random labelling. So our lower bound is essentially tight with respect to the rate."}, {"review_id": "fAEZkJ7fna", "reviewer": "Reviewer_4FGD", "summary": "This paper identifies several implications of the (extended) low-degree conjecture for the sparse SBM, recently put forward by Moitra and Wein (2023). The first implication (Theorem 2.1) is that efficient weak recovery below the Kesten-Stigum threshold is impossible. The second implication (Theorem 2.4) is a computational lower bound for learning the parameters of the SBM at a rate that is markedly better than the (suboptimal) SVD-based algorithm. Finally, Theorem 2.7 provides a computational lower bound for the related block graphon learning problem. \n\nThe proofs proceed by contradiction. For example, the proof of Theorem 2.1 begins by assuming a polynomial-time algorithm achieving weak recovery. The proof then constructs a function f which contradicts the assumption of Conjecture 1.3.", "questions": "N/A", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The area of computations/statistical thresholds has received significant interest in recent years. Few results rule out the possibility of efficient algorithms- the current state-of-the-art is to rule out e.g. algorithms based on low-degree polynomials. While the paper relies on a conjecture for its results, I feel this is nevertheless a strong contribution. Indeed, there are many works that rely on the Planted Clique Conjecture.", "was_revised": true, "final_justification": "I maintain my positive view of this paper, as the authors adequately responded to the questions raised.", "rebuttal": "Thank you for your review and constructive feedback!"}, {"review_id": "mIloYiLWum", "reviewer": "Reviewer_owhx", "summary": "This paper shows a reduction from a strong form of computational hardness of testing block models vs. ER null to strong computational hardness of recovery of block models. \nThe computational hardness is related to a conjecture of Moitra and Wein on low-degree hardness.", "questions": "0. It is very important to state the conjectured hardness that lead to the results of the paper. This is not conjecture 1.3 to be the best of my knowlege. It should be something like: There is no algorithm that runs in time 2^{O(n)} that can test between ER graphs and random graphs. Please be very explicit in the constant in the O here: \nis it 2^{10 n} or 2^{0.9999 N}\n\n1.Please discuss when are the intervals at the figure at page 4 empty. \n\n2. Can you please provide an intuitive explanation for the advantage of cross validation", "limitations": "The main limitation is the strong computational conjecture (that is never stated explicility ...) that is at the basis of this work.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The reduction is definitely interesting and a good contribution to the area.\nThe paper feels a bit rushed. I think the following could help the presentation and context:\n\nConjectures 1.3 as stated has a free parameter \\delta: It says something along the lines that if the problem is hard for \ndegree n^{\\delta} polynomials then it takes \\exp(n^{\\delta}) time.\nHowever, I believe that the Theorems actually assuming the conclusion of the conjecture for every \\delta in [0,1].\nIt is very important to clarify this as the starting point of the paper is not the MW conjecture but the outcome of this conditional conjecture assuming low-degree hardness for testing block model in exponential time. \n\nI believe that the paper \"Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs\" by Mossel, Sly and Sohn show similar reductions for information theory variants of the problem. The authors should compare the results (and possibly proofs) to this setting.\n\nThere is no discussion of when is the interval below the KS bound where recovery is possible non-empty especially as the results are stated for parameters < 0.99 KS bound.\n\nSome relevant papers here are: \n\nExact phase transitions for stochastic block models and reconstruction on trees by Mossel, Sly and Sohn as well as the more recent: \n\nhttps://arxiv.org/abs/2503.03047 which discusses the case of multiple communities.", "was_revised": true, "final_justification": "The paper makes nice progress in the low-degree hardness framework. The writing could be a little better, ideally better explaining the context and some of the main ideas of the proof.", "rebuttal": "Thank you for your constructive feedback and pointing out related literature!\n\n0. Thank you for pointing out the ambiguity in the conjecture statement! You are absolutely right that conjecture 1.3 should be stated for every $\\delta$ in [0,1], and our proof exploits conjecture 1.3 via the parameter $\\delta$. We will make this more clear in the final version of the paper.\n\n1. The hard interval can be empty when the number of communities k=2,3,4 (where there is no information-computation gap), or, if the conjecture stated in the paper is false and there are sub-exponential time algorithms whenever weak recovery is information-theoretically possible.\n\n2. Our proof relies on the fact that the weak recovery estimator and the graph for cross validation are almost independent. Without the graph splitting procedure, the weak recovery estimator and the graph edges can be arbitrarily correlated. As a result, the testing statistics under null distribution can be very large, since the inner product of the centered adjacency matrix and the estimator can be very large. In particular, the almost independence is required to upper bound the inner product between the centered adjacency matrix and the weak recovery estimator with Bernstein inequality."}]

Author rebuttal:

Meta-review: The paper gives a computational lower bound on weak recovery of community labels in a symmetric stochatic block model, as common in this literature by reducing to a specific conjecture.

The reviewer opinions are so unanimously positive that there is not much left to say. Although the topic is arguably not machine learning per se, it is a strong result in an area that is broadly of interest to machine learning. This is a clear accept.
Decision: Accept (spotlight)