On the Power of SVD in the Stochastic Block Model
Authors: Xinyu Mao
Jiapeng Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: Clustering Algorithms
Stochastic Block Model
Spectral Algorithms
TL;DR: We show that, in (symmetric) stochastic block model, PCA/SVD itself is a good clustering algorithm; this explains why using PCA/SVD before running clustering algorithms improves clustering results in practice.

Abstract: A popular heuristic method for improving clustering results is to apply dimensionality reduction before running clustering algorithms.
It has been observed that spectral-based dimensionality reduction tools, such as PCA or SVD, improve the performance of clustering algorithms in many applications. This phenomenon indicates that spectral method not only serves as a dimensionality reduction tool, but also contributes to the clustering procedure in some sense. It is an interesting question to understand the behavior of spectral steps in clustering problems.

As an initial step in this direction, this paper studies the power of vanilla-SVD algorithm in the stochastic block model (SBM). We show that, in the symmetric setting, vanilla-SVD algorithm recovers all clusters correctly. This result answers an open question posed by Van Vu (Combinatorics Probability and Computing, 2018) in the symmetric setting.

On the Power of SVD in the Stochastic Block Model
Xinyu Mao University of Southern California xi xinyumaoQusc.ede edu
Jiapeng Zhang University of Southern California j jiaengzzusc.edd .du
Abstract
A popular heuristic method for improving clustering results is to apply dimension- ality reduction before running clustering algorithms. has been observed that spectral-based dimensionality reduction tools, such PCA SVD, improve the performance of clustering algorithms in many applications. This phenomenon indicates that spectral method not only serves but also contributes to the clustering procedure in some sense. is an interesting question to understand the behavior of spectral steps in clustering problems.
dimensionality reduction tool,
As an initial step in this direction, this paper studies the power of vanilla-SVD algorithm in the stochastic block model (SBM). We show that, in the symmetric setting, vanilla-SVD algorithm recovers all clusters correctly. This result answers open question posed by Van Vu (Combinatories Probability and Computing, 2018) in the symmetric setting.
1 Introduction
Clustering is fundamental task in machine learning, with applications in many fields, such as biology, data mining, and statistical physics. Given set of objects, the goal partition them into clusters according their similarities. Objects and known relations can be represented in various ways. In most cases, objects are represented as vectors in IRd, forming a data set D C RRd each coordinate is called a feature, whose value is directly derived from raw data.
In many applications, the number of features is very large. has been observed that the performance of classical clustering algorithms such as K-means may be worse on high- -igh-dimensional datasets. Some people call this phenomenon curse of dimensionality in machine learning [SEK04] popular heuristic method to address this issue is to apply dimensionality reduction before clustering. Among tools for dimensionality reduction, is noted in practice that spectral methods such as principal component analysis (PCA) and singular value decomposition (SVD) significantly improve clustering results, e.g., SEK00 KAH19].
A natural question arises: why do spectral methods help to cluster high-dimensional datasets? Some practitioners believe one reason is that the spectral method filters some noise from the high- dimensional data [ARS 04 SEK04, ZLW209 KAH19] Simultaneously. many theory works also (partially) support this explanation [FWZ22 EBWIS LZK22 MZ22a). With this explanation in mind, people analyzed the behavior of spectral based algorithms with noise perturbation. Based on these analyses, many algorithms were proposed to recover clusters probabilistic generative models. Among them, well-studied model is the
-rsetral-based
model.
Hignal-Plus-Noisss model In this model, we assume that each observed sample 02 has the form 0 E% + e;, where U; is a ground-truth vector and e, is a random noise vector. For any two sample vectors 02 0j if they are from the same cluster, their corresponding ground-truth vectors are identical, model very general; it has plentiful variants with different types of ground-truth vectors and noise distribution. In this paper, we focus an important instance known as
i.e. 222 = By. Signal-plus-nor
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the stochastic block model (SBM). Though SBM is not as broad as general signal sariaalppu-ooooeo noise model, it usually serves as a benchmark for clustering and provides preliminary intuition about random graphs.
Stochastic block model The SBM is first introduced by [LL883 and is widely used as a theoretical benchmark for graph clustering algorithms. the paper, we focus on the symmetric version of stochastic block model (SSBM), described as follows. Given set of n vertices V, we uniformly partition them into disjoint sets (clusters), denoted by Vi,..., , Vg.
Based on this partition, a random (undirected) graph G = (V; F) is sampled in the following way: for all pairs of vertices u, E V, an edge {u, e) is added independently with probability p. if u, Vi for some & otherwise, edge {u, b) is added independently with probability 9.
We usually assume that p > q. The task is to recover the hidden partition Vi,..., V& from the random graph G. We denote this model as SSBM(V, k,
SBM as a signal-plus-noise model Though SBM was originally designed for graph clustering, view it special form of vector clustering. Namely, given the adjacency matrix of graph
G E {0, VVV, the columns of G form a of n [V] vectors. To see that SBM fits into the
signal- noise model, note that in the SBM, the adjacency matrix G E {0. 1] VxV can be viewed
as a fixed matrix G plus a random noise, i.e., G G + E, where G def G is the mean and E is a zero-mean random matrix. More precisely, in the case of SSBM,
(P if u, U Ve for some É, and Gav = 4 otherwise,
[1 Gue with probability Gavs Euv { G-uu
with probability Guvr
where the random variables {Eue r) are independent and E = Euv for all u.
1.1 Motivations: Analyzing Vanilla Spectral Algorithms
many spectral-basee algorithms have been proposed and studied in the SBM [G005 Vu 8 LRIS EBWI8 8 Col19 AFWZ20 MZ22b] and even more general Signal-plus-nol are largely based on the spectral analysis of random matrices. The purpose of designing and analyzing such algorithms is twofold.
Since the seminal work by McSherry McS01
models AFWZ20 EBWIS CTP19, LZK22 MZ22a] These algorithms
Understanding the limitation of spectral-based algorithms SBM is specified by parameters, such as n, k, p.P.q q in the symmetric case. Clustering is usually getting harder for larger & and smaller gap (p- 9)- Many existing works aim to understand in which regimes of these parameters it is possible to recover the hidden partition. In this regard, the otate-of-the-art bound is given by Vu [Vu18]. Concretely, [Vu18] proved that, in the symmetric setting, there is algorithm that recovers
all clusters if 2 C (avT+yyTog> p-q
2
where o² def max {p(1 10p-p). p), q(1 - g}} and is a constant.
Understanding spectral-based algorithms in practice Besides analyzing spectral algorithms in theory, the other purpose, which is the primary purpose of this paper, is to explain the usefulness of such algorithms practice. Indeed, as we mentioned before, many spectral-based algorithms, as observed in practice, can filter the noise and address the curse of dimensionality [ARS 04, SEK04] ZLWZ09 KAHI9]. Some representative algorithms are PCA and SVD. Furthermore, it has been observed that spectral algorithms used in practice, such as PCA or SVD, are usually very simple: they just project data points into some lower-dimension subspace, and no extra steps are conducted.
In stark contrast, most of the aforementioned theoretical algorithms have pre-processing or post- processing steps. For example, the idea in [L.15) is that one first applies SVD, and then runs variant of K-means to clean up the clustering; the main algorithm in [Vu18) partitions the graph into several parts and uses these parts in different ways. As noted in [Vu18), these extra steps are only for the purpose of theoretical analysis: From the perspective of algorithm design. these extra steps appear redundant. Later on, [AFWZ20] coined the phrase vanilla spectral algorithms describe spectral algorithms that do not include any additional steps. Both Vu 8 and [FFW22 conjectured
Assume fix an order of the vertices in V.

---

that vanilla spectral algorithms are themselves good clustering algorithms. In practice, this is widely-used heuristic; however, in theory, the analysis of vanilla spectral algorithms not satisfactory due to the lack of techniques for analysis. We refer to [M22b for a detailed discussion on barriers of the current analysis.
Why do study vanilla algorithms? for two reasons:
Our main focus is particularly on vanilla spectral algorithms
1. Vamilla spectral algorithms are the most popular in practice- no extra steps are widely used. Plus, their performance seems good enough. The lack of theoretical analysis is mostly due to technical obstacles.
2. A vanilla spectral algorithm is often simple and not specifically designed for theoretical models such SBM. In contrast, some complicated algorithms use extra steps which are designed for SBM. These steps made the analysis of SBM go through (as commented by [Vu18]). Meanwhile, these extra steps exploit specific structures and may cause 'overfittings" on SBM, which makes these algorithms less powerful in practice.
The main purpose of this paper is to theoretically understand the power of practically successful vanilla spectral algorithms. To this end, we study SBM as a preliminary demonstration. We do not aim design algorithms for SBM that outperforms existing algorithms.
1.2
Our Results
The contribution of this paper is twofold. On the one hand, we show that vanilla algorithms (alg. L is
indeed clustering algorithm in the SSBM for a wide range of parameters, breaking previous barrier on analyzing on only constant number of clusters. On the other hand, we provide a novel analysis on matrix perturbation with random noise. We discuss more details on this part in Section 1.4
Recall that parameters of SBM specified by SSBM(V, n, ki 9), where n = -V.. Let o² =
max {p(1- - p), q(1 - Our main result is stated below.
Theorem 1.1. There exists constant C 0 with the following property. In the model <//p-logg nt /ooon 2 then alg. recov-
SSBM(V, n, k. p. p).), of 2 C'logn/n and n 2 C. k ((Shp-los ers all clusters with probability 1).
Here describe the vanilla-SVD algorithm in more detail. Algorithms in MeeS0 Vu18 Col19 share a common idea: they both use SVD-based methods to find a clear-cut vector representation of vertices. That is, every node v V is associated with a vector p(v), and we say vector representation P is clear-cut if the following holds for some threshold A: if u, v E V4 for some f, then (lp(u) p(u)l S A/4; otherwise, Ilp(u) p(u)ll 2 A.
Once a clear-cut representation is found, the clustering task is easy: If the parameters n, k. p. all known, we can calculate A and simply decide whether two vertices are in the same cluster based on their distance; in the case where A is unknown, we need one more step. P Following [Vu18) we denote by ClusterByDistance representation. One natural representation is obtained by SVD as follows. Let G E 13 1 be the adjacent matrix of the input graph, and let P be the orthogonal projection matrix onto the space
algorithm that recovers the partition from a clear-cut
spanned by the first & eigenvectors of G. Then set p(u) def Pa. G,,, where G, is the column index by V. This yields alg. I the vanilla-SVD algorithm.
1.3 Comparison with Existing Analysis for Vanilla Spectral Algorithms in the SBM
To the best of our knowledge, there are very few works on the analysis of vanilla spectral algorithms [AFW220 EBWIS 19). All of them only apply to the case = O(1). In this work, we obtain the first analysis for general parameters n, k p, q, in the symmetric SBM setting.
FFor example, one possible implementation is as follows: create a minimal spanning tree according to the distances under then remove the heaviest (k- 1) edges, resulting in & connected components, and output these components as clusters.
3

---

Algorithm 1: Vanilla-SVD algorithm for graph clustering
Input: adjacent matrix G E {0, 1) VXV
13
2 Output: a partition V
1. Compute p(u) def Pg. G. for each E V.
2. Run ClusterByDistance with representation
Davis-Kahan approaches To study spectral algorithms in signal-plus-noise models, key step is to understand how random noise perturbs the eigenvectors matrix. A commonly-used technical ingredient is the Davis Kahan sin & theorem (or its variant). However, this type of approach faces two challenges in the SBM.
Davis-Kahan Kahan leads to worst-case perturbation bounds. For perturbations caused by ran- dom noises, such as signal-plus-noise models, Davis-Kahan sin θ theorem is sometimes suboptimal.
These sin theorems only lead to bound on 2-norm. However, the SBM analysis, we may need (2 + on)mmorm bounds. See CTP19 for more discussions.
Previous works such as [AFW220, EBWI8 PPV 19 mainly followed this approach. They proposed some novel ideas to (partially) address these two challenges, but only apply to the case of k 0(1). In contrast, our approach, following the power-iteration-ban completely avoids Davis-Kahan sin θ theorem and can handle the case of k = (1).
analysis proposed by [MZ22h),
Inspired by power iteration methods, Mukherjee and Zhang MM22bb proposed new approach analyze the perturbation random matrices. The idea approximate the eigenvectors of matrix by its power. In fact, this method has been widely used in practice as fast algorithm to approximate cigenvectors. However, there are two limitations of [MZ22b]
Comparison with M
Their analysis requires nice structure of the mean matrix, i.e., all large eigenvalues more or less the same.
Their algorithm is not vanilla as it has 'centering step'. Moreover, their algorithm requires the knowledge of parameters p. q, and particularly, the centering step alone requires the knowledge of q. In comparison, we only need to know k; further, we can also guess ls (by checking the number of large eigenvalues) and then make alg. fully parameter-fiee
To overcome these limitations, we introduce novel 'polynomial approximation + entrywise analysis' method, which makes this analysis more robust and requires less structure. More details will be discussed in Section 1.4
The difference between the parameters in our results and those in Vu's paper is that we replaced a by Vplog" n. If < 0.9, a and /p are equal up to constant, our bound is essentially the same as [Vu18] except for the log 6 faccorr We believe the extra log factor can be improved by future works. This term stems from the new concentration inequality we used as a black box. refined analysis of this concentration inequality may remove this factor. Here are two example settings of parameters that satisfy the conditions in Theorem [.I.
Regarding parameters in Theorem 1.1
Vi = O logn ),P = (2( log" log"n) ");
(1) and = O
v log"
1.4 Proof Outline and Technical Contributions
Let denote the size of the cluster to which u belongs. Assume for now that all V,'s are of size roughly n/k Indeed, this happens with high probability inasmuch as the partition uniformly sampled.

---

Our goal is to show that there exists some threshold A > 0 such that for every u E V: if
u, E Ve for some l, then
PG. Gu - PG Go & //4; otherwise,
Pa, G. Pa. G. 2 A.
Write e(u) def Pa. G. G.
| Then
Then Pl. G - Pg. G. IG, - G.ll S <(u) + E(U). Note
that |G,, - G. = 0 u, E V for some f, otherwise, ||, - Gull = (p 9) V8, + 8, > (p
D//kk Therefore, setting A = 0.8(p g)y/n n/k,, k, it suffices to show that e(u) - 50.(pp - 9) n//k for every uEW V.
We decompose s(u) into two terms:
E(u) S Pa. (.C.-GGa. -w>)| - Gw]||+|(PG..
- P Em + - -
nG.. "noise term"
PP.
(I)
"deviation term"
We shall bound the two terms from above separately. Intuitively, the noise term is small means Pax reduces the noise, while the deviation term is small means PG2 preserves the data.
Upper bound of the noise term It is known that Pag (resp., Pa.)) can be write as a polynomial of & (resp., G). By Weyl's inequality, the eigenvalues of G are not too far from those of G. Therefore, in our case, one can find a simple polynomial yp which only depends on G, such that (o()) (resp., (GG))
a good approximation of Pa. (resp., ) this is formalized in Lemma 3.2 Then we have the
following decomposition:
|Pa E., S 2 (()) Em S (l) + 2
(v(C) p()) E.
where the first inequality follows from Lemma 3.2 which roughly says ((G) is good approximation of .
1. The first term, [G) small with high probability. To see this, we use Lemma 3.2 again: Eull I Pc, Eull. According to a known result (c.f. Proposition 2.4p.
[Pa Eul is small with high probability, largely because the projection Pa. and the vector Ey are independent.
2. The second term is the tricky part, and we draw on an entrywise analysis. Namely, we study every entry of (vo(G) ((G) E.., using the new inequality from [M722h] See Lemma 3.3 for more details.
The upper bound for the noise term is encapsulated in Lemma 3.4
Upper bound of the deviation term The following argument is reminiscent of [Vul8]. Say u E Vy.
Note that Gxe Vau Gu where X -e. lv; is the normalized characteristic vector of Ve (i.e.. (v) = + v V2). It follows that
IPP.. n) < ( - -na|, + IPG. - DE s (lc-@"1,+10 - -ne 2 E
where the second inequality holds because Pa. & is the best k-rank approximation of G and ra) = k, and in the third inequality, we use IPa. - -1/l8 S 1, as Pa. is a projection matrix. Therefore,
|Pa - IJG. = V
1
(Pa. - IJGx s V
1 iPa. | ng|
2 2
(2)
Su
A typical result in random matrix theory (c.f. Proposition 2.3) states that with high probability, || = ((v)). Combining Equation (2 and R n/k, we get by our assumption on n, we have Vh o((p g)n/k) o()).
(Pa. T)G O(VR). And
Technical contribution The major novelty of our analysis is using the polynomial yp M used a centering step to make the mean matrix nicely structured, while our analysis, we used polynomial approximation to address this issue. Another difference is that in MM22bb, the centering
5

---

step appears explicitly in the algorithm. By contrast, our polynomial approximation only appears in the analysis the algorithm vanilla.
As byproduct, we developed new techniques for studying eigenspace perturbation, a typical topic in random matrix theory. Our high-level idea is "polynomial approximation + entrywise analysis". That is, we reduce the analysis of cigenspace perturbation to the analysis of simple polynomial (of matrix) under perturbation. We have more tools to deal with the latter.
1.5 Discussion and Future Directions
In this paper, we studied the behavior of vanilla-SVD the SSBM, benchmark signal-plus-noise model widely studied in random matrix theory. We showed that vanilla-SVD indeed filters noise in the SSBM. In fact, our analysis technique, 'polynomial approximation + entrywise analysis', not very limited to SSBM. A direct and interesting question yet to be answered is: Can our method be extended to prove that vanilla-SVi works in the general SBM where partitions are not uniformly sampled and edges appear with different probabilities? Moreover, our method may be useful for analyzing some other realistic, probabilistic models such as the factor model - a model which has been widely used in economies and model portfolio theory.
In the long term, it would be very interesting to understand the behavior of vanilla spectral algorithms on real data: 1) Why does it succeed in some applications? 2) How could we fix it if it has failed in other cases? A deeper understanding of vanilla spectral algorithms will provide guidelines for using them in many machine learning tasks.
2 Preliminaries
Let I,, denote the n-dimensional vector whose entries are all I's, and let Jn, be the n matrix whose entries are all I's. Let 8y denote the size of the cluster to which u belongs. For a matrix A. Ali] denotes the row of A indexed by i, and A, denotes the column indexed by i: (A)) is the i-th largest eigenvalue of A; let PAa denote the orthogonal projection matrix onto the space spanned by def
Notations
the first l: eigenvectors of A. For a vector x E TR",, ||>||| norm.
V + x denotes the Fuclidean
max =|=1 ||Az|| and Definition 2.1 (Matrix operator norms). Let A E Rux", Define ||A||, def
||Al|--00 def max,:||a [=1 [|Ax]loo
Proposition 2.1 (e.g., (CTP19). For all matrices A, Raxn, it holds that (1) ||A1|2-000 max [[]]: (2) ||BB] I ||Al| |BIl2-
Proposition 2.2 (Weyl's inequality). For all A, E E Rax", we have (Mx(A) AA + E)1 S || Proposition 2.3 (Norm of a random matrix [uu18). ). There is a constant Co > O. Let E be a symmetric matrix whose upper diagonal entries esj are independent rundom variables where
ei- = 1 Pig PPs with probabilities Pij and 1 Pij respectively, where Pij [0.1]. Let ² (P (1)))) If o² Co logn/n. n, then Pr[]| 2 C/ S n3
Proposition 2.4 (Projection of a random vector, lemma 2.1 in [V118). There exists a constant C such that the following holds. Let X =EL,...., be random vector in IR" whose coordinates & are independent random variables with mean 0 and variance at most o² & L. Assume furthermore that the &, are bounded by I in absolute value. Let H be subspace of dimension d and let I be the length of the orthogonal projection of onto H. Then Pr
1l 2 ovd + C1 Civlog S n
Proposition 2.5. For a E [0,2] and r E N, if 1| S < 2r then la" - 1| 2rô.
3 Analysis of Vanilla SVD Algorithm
Write St
def [V].
We say the partition Vi,..., Vv is balanced if (1- 16logn
(1+ Iologn bility least - n -1; hence, we assume that the partition balanced in the following argument.
R Vi E [k:) By Chernoff bound, the partition Vi...., Vv balanced with proba-
Since 2² 2 C' Clog /n, the event ||=ر|| O(vn) holds with high probability (sec Proposition 2.3

---

Recall the decomposition into deviation term and noise term in Equation 1 We first state our upper bound of the deviation term, which readily follows from the argument in Section and the complete proof is in Appendix B
Lemma 3.1 (Upper bound of deviation term). Let Co be the constant in Proposition 2.3 If the
partition is balanced and Z 10 C k²o² then with probability at least 1
have
(p-q)ar
IP'. -I) - 0.04(p q)
Section 3.1 and Section 3.2 lead to an upper bound of the noise term, and Section 3.3 is the proof of main theorem.
3.1 An Approximation of Pa. and Pg.
In order to give some intuition on the choice of yo we first analyze the spectrum of G, and the result is summed up in Theorem 3.1
(p-g)Jor
0
0
0
(p Ja2
0
The eigenvalues of G Note that G = = where H-
0 (p-q)J.;
Without loss of generality, assume that 81 82 ..... Sk. It easy see that the eigenvalues of H are (p (y--))a -)8)).-..,, (p-g)ss, O. Viewing G as rank-one perturbation of H, we have the following theorem that characterizes eigenvalues of G. Its proof, in Appendix C readily follows from theorem in [BNS79], which studies cigenvalues under rank-one perturbation.
Theorem 3.1. Write def
[Val and assume that $1 2 $2 2 ... 2 Sk. Define ö, def X₂(G)) - (p g)ss,
then (1) 6, 0 Σ === 5; nq; (2) (G) 2 ng+ (p q) k. and hence Σ 6g S (p-q)(s1 ))
The choice of the polynomial yp Let u def (v - g) x. and vbl be the quadratic polynomial such that
= (14) = (0) = 0, i... (t) def where A Ar(
(G) (t (G)) 14) + def At + Bt,
1 J. Finally, let (pt) def (v(t))" where def log n.
Here we give some intuition for the choice of p. Let G =G Ei Reazyy be the spectral decomposition of G. Then ((G) = Ei= ((A))oe , Pa. = =E, 0001
The spectral decomposition of ((G))
Pa. is ( - Pa. = (p - -1)b,0 T + Ei=41 (AA)),, Hence,
|(( Pā = max(l((A)) - 11,.....,44.
1/, (x I....., ((,))
(3)
Recall that & (G) is bounded by Weyl's inequality. Plus, when the partition is balanced, Theorem 3.1 shows that the eigenvalues of G is nicely distributed: Except for X (G), other eigenvalues
all close to μ. Hence, our choice of & makes (()) Pa. ll, small, and thus (p()) is good
approximation of Pa.- Formally, we have the following lemma.
Lemma 3.2 (Polynomial approximation). Assume that the partition is balanced and n 2 10 C? 1..p-log n (p-4)=, where Co the constant in Proposition 2.3 Then with probability least n ||| | a < (G) Pa. x
holds that for all x E R",
+ || deell/ndo /ndog log and 2 PG. x/|| S
[kx( 5 ||
Proof. Let G G Apury (resp.. G= Ei )eoioT) be the spectral decomposition of G (resp..
G). We shall use the following claim.
Claim 3.1. The following holds with probability - n -3 (over the choice of E): for every i E [k].
((AA)) - 1 < 1,,)(A,) - -1| < 1/; and for every i = k: + 1...., (xxx)) < n log log
7

---

Fix x E R". On the one hand, 2/ s ((x))
- 3
2 V. [kc] and hence
| Σ (2,
Σ ((,)) u1) 2 Σ Σ (z, vs)
Pa
which means | 2 2/2
Pa. 2/
On the other hand,
|())
2
Σ (()))) (x, v2) 1
2
(x,, 02)
Σ
(s, 0))2
9
Pa x
2
+
||
2
n log
4
2 log
:=1
i=k+1
Since va+bs Va + vb, we have part.
S
Pa
x
+ nlogiog
le
This establishes the first
Note that || = V (2,)) uz)a and we also have 1 S ((Ac) S 3. Vi [k:] and thus
similar argument goes for G. This finishes the proof of Lemma 3.2
The claim readily follows from the choice of yp and the fact that A, A are close. A complete proof can be found in Appendix
remains to prove Claim 3.1
3.2 The Upper Bound of the Noise Term
According to Equation
[ in order to derive an upper bound of [|,a, Eull. it remains to bound from above. This done by the following lemma.
(x(G) 1p0 +p(G) Em
Lemma 3.3. Let Co be the constant in Proposition 2.3 Assume that the partition is balanced and 'on"" For every E V, it holds that
(100 + Co)2 (0-0)=
[1( [v(() (()) En S C2(y CalVkplog' n) + logn
Pr
2 1 - 10nOnnn
where C2 def 7- 10 is a constant.
Combining Lemma 3.2 and Proposition 2.4 we get an upper bound of the noise term:
Lemma 3.4 (Upper bound of noise term). Let Co be the constant in Proposition 2.3 Assume that n 2 (100 + ) (p-q)=
1o Then with probability at least 1 - 00 )) we have Pa En S
Cs(vkp log 2 + vlogn) for all u E V, where C3 is a constant.
The proof of Lemma
3.3 is deferred to Section 4 We use it to prove Lemma 3.4 here.
Proof of Lemma
3.4 It follows from Lemma 3.2 that
Po. Eu
22 B
2 (oGG)-((G)) E. + [l)
$2 [p(() - (0(66)-((00 -(()) E. + P E.ll
By Proposition 2.4 with high probability at least 1 1 IPG E..ll is bounded by o To Ci Vlog where C₁ a universal constant. Meanwhile, by Lemma 3.3 and union bound over all u, with
probability at least O(n-1), [(((O) (G)) E., 7 10 (v log" n + 1/ log n) for every
E V. Therefore, with probability O( holds that Paa E,, S 1.4 10 Vkplog" 30 Th 3C1 vlogn for all E V. Setting C3 def (1.4 10 + 3C1), we have the desired result.
D
8

---

3.3 Putting It Together
Now we are well-equipped to prove Theorem I.I
Proof of Theorem 1.1 Let C def (100 100C, + 100C3)² where Co, C3 are the constants in Propo-
sition 2.3 and Lemma
3.4 By our assumption on nt we have (p q) m//k/// > 100C /Kp Kollgg n
Vlogni n. It is easy to verify satisfies the conditions in Lemma 3.4 and Lemma 3.1
Write A def 0.8(p 4)
()/n/k n/k. We aim to show that for every u, v E V: uf E Vi for some
then Pa. G. Pa, G. I A/4; otherwise, Pa. GT Pa Go 2 A. Then by calling
ClusteryDDistance, alg. recovers all large clusters correctly.
Let su)
def P Gul According to the argument in Section 1.4 suffices to show that
E(u) S 0.1(p 1) nn/k for all E V. We further decompose E(u) into noise term and deviation term, i.e., e(u) < noise(u) + dev(u). where noise(u) def | and dev(u) def P G)Gu|
By Lemma and and Lemma 3.1 with probability at least 1-0(n ). the following hold for all E V: (I) noise(u) (u) Ca(vkp log" vlogn) n) 0.01(pp g)/n/k: k: (2) dev(u) I 0.04(p 9) n/k. Therefore, with probability at least O(n=()n) "), we indeed have e(u) S 0.1 4) 2)/kk/ Vu eV. This completes the proof.
4 Proof of Lemma 3.3: Entrywise Analysis
This section is dedicated to proving Lemma Since both (p(G) p(G)) and E are symmetric, we have ((0(0)-((Gi)
3.3
The high-level idea is to write ((((ā) - ((G) as a sum of ma- trices, where each matrix is of the form SQ such that ||Q]/, = O(). This way, we have
[ - (G)) 2-500
|E SQ112-00 S || O(1), and E 2 is bounded by lemma from MZ226).
Let D del ((() (G)) = A(EG + GE + + + BE and write F def (GG), F def (G). Then
( (G) - ~(G)" = (F + D)" F
= =F D F DF + FDF 2
where the last step is decomposition based on the first location of D in the product terms, And
DF +(D+F) D" DFF + D2FF F
+
+ F
del M'
That is, ( =MM)) + ED" + EM'. We bound the three terms respectively. Here we first list some definitions and estimations of the quantities involved.
According to Proposition 2.3 with probability at least - we have || I Coa Vn, where Co is constant. In the following argument, we always assume this holds.
4 /)nkk. /k. By our assumption on n, we have μ 2 (100 + Co) n.
A
1
B (x1())
21, r = log Az > and thus B < n
2
||| < n²a
(G)
By Claim 3.1
||F1|2 & 1 4logn'
1+ Alog By Proposition 2.5
|F
| s
2, Vt < logn..

---

Upper bound of |EM 1 2-000 Note that |EF* D 2-000 & |E 2 | 1-1 D| and | 1-1 < 2 for all & I r.
Moreover, | I
[ || |G]|
(لاا + B | S
3 جاكاق | bound of
4 + 2 4 | 4(log" n)- < Ing" n
And the following lemma gives an upper
1
Lemma 4.1. Prg
2 I 10( loggnloon + Vlogn] 2 - 2n -
Therefore, by union bound, we have the following holds with probability at least n
40(
|BMil r.. 10 10(ykkllggg kplog n + Vlog n)) 2 log"
(4)
log n
Upper bound of |EDD) 112400 Since |D1|| log n have
|ED* 2-120 S ||E|l2 ||D|| S vn (log* n)) log
(5)
n2
Lemma 4.2 (Upper bound of 1FM With probability 1 O(n 2) (over the choice of E),
we have ||MM 12-20 & 6C2vkp log" n, where C2 = 10 a constant.
2-+20
Finally, combining Equation 4 Equation (5. and the above lemma, conclude that with probability at least 1 1 On 2).
[((((() - - ( 2-+00
40 (k(vpppe + 1)
+ n
kC2//plog" 7C2(Vkplup log n log n
1
log n
This establishes Lemma 3.
Proofs of Lemma 4.1 and Lemma 4.2 are deferred to Appendix D
Acknowledgments and Disclosure of Funding
We are grateful anonymous NeurIPS reviewers for their helpful comments. This research is supported by NSF CAREER award 2141536.
References
[AFWZ20] Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvec- tor analysis of random matrices with low expected rank. Ann. Statist., 48(3):1452-1474, 2020.
[ARS*04] Paolo Antonelli, HE Revercomb, LA Sromovsky, WL Smith, RO Knuteson, DC Tobin, RK Garcia, HB Howell, H-L Huang, and FA Best. A principal component noise filter for high spectral resolution infrared measurements. Journal of Geophysical Research: Atmospheres, 109(D23), 2004.
[BNS79] James Bunch, Christopher P. Nielsen, and Danny C. Sorensen. Rank-one modification of the symmetric eigenproblem. Numer. Math., 31(1):31-48, 1978/79.
[Col19] Sam Cole. Recovering nonuniform planted partitions via iterated projection. Linear Algebra and its Applications, 576:79- 176:79-107, 2019.
[CTP19]
Joshua Cape, Minh Tang, and Carey E Priebe. The two-to-infinity norm and singular subspace geometry with applications Statistics, 47(5):240-2244
digeddimensional statistics. The Annals of
2019.
[EBW18] Justin Eldridge, Mikhail Belkin, and Yusu Wang. Unperturbed: spectral analysis beyond Davis-Kahan In Algorithmic learning theory 2018, volume 83 of Proc. Mach. Learn. Res. (PMLR), page 38. Proceedings of Machine Learning Research PMLR, [place of publication not identified], 2018.
[GM05]
Joachim Giesen and Dieter Mitsche. Reconstructing many partitions using spectral techniques. In International Symposium on Fundamentals of Computation Theory, pages 433 133.444. Springer, 2005.
10

---

[HLL83] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic block- models: First steps. Social networks, 5(2):109-137, 1983.
[KHH19] Vladimir Yu Kiselev, Tallulah S Andrews, and Martin Hemberg. Challenges in unsuper- vised clustering of single-cell rna-seq data. Nature Reviews Genetics, 20(5):273-282, 2019.
[LR15] Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. The Annals of Statistics, 43(1):215-237, 2015.
[LZZK22] Boris Landa, Thomas TCK Zhang, and Yuval Kluger. Biwhitening reveals the rank of count matrix. SIAM Journal on Mathematics of Data Science, 4(4):1420-1446, 2022.
[McS01]
Frank McSherry. Spectral partitioning of random graphs. In 42nd IEEE Symposium Foundations of Computer Science (Las Vegas, NV, 2001), pages 529-537. IEEE Computer Soc., Los Alamitos, CA, 2001.
[MZ22a]
Chandra Sekhar Mukherjee and Jiapeng Zhang. Compressibility: Power of pea in clustering problems beyond dimensionality reduction. arXiv preprint arXiv:2204.10888, 2022.
[M722b] Chandra Sekhar Mukherjee and Jiapeng Zhang. Detecting hidden communities by power iterations with connections to vanilla spectral algorithms, 2022.
19] Carey E Priebe, Youngser Park, Joshua T Vogelstein, John M Conroy, Vince Lyzinski, Minh Tang, Avanti Athreya, Joshua Cape, and Eric Bridgeford. On a two-truths phe- nomenon in spectral graph clustering. Proceedings of the National Academy of Sciences, 116(13):5995-60) 2019.
[SHK04]
Michael Steinbach, Levent Ertöz, and Vipin Kumar. The challenges of clustering high dimensional data. In New directions in statistical physics, pages 273-309. Springer, 2004.
[Vu18]
Van Vu. A simple SVD algorithm for finding hidden partitions. Combin. Probab. Comput., 27(1):124-140, 2018.
[ZLWZ09] Lei Zhang, Rastislav Lukae, Xiaolin Wu, and David Zhang. Pca-based spatially adaptive denoising of cfa images for single-sensor digital cameras. IEEE transactions on image processing, 18(4):797-81 2009.

---

A Useful inequalities
Proposition A.1 (Chernoff bound). Let X1...., ,......,,..... be i.id random variables that can take values in {0, 1}. with E E[X;] S ffrrr I sis S m. Then it holds that
3t
Pr
Σ t=1
X,
mp 2t
exp
mp
Proposition A.2 (Hoeffding bound). Let X1,... Xmm be independent random variables such that a, S X1 & by, and write S def
Ei=l X,, Then it holds that
212
Pr [|S E[S)
exxp
-nT (b, a;)
Definition A.1. Let be Bernoulli random variable with parameter p. i.e., Pr(X=1] =
p. P.Pr [ 0 1--p p. The random variable Y def X x-p X E [X] is called centered Bernoulli random variable with parameter p.
Proposition A.3 (Adapted from M7.225)). Let E Ruxn, and let = (Eij) be an n x n symmetric random matrix, where
(&ij EGglgiiiiin
are independent, centered Bernoulli random variables with parameter at most for all i, Suppose that every entry of takes value in [-3, B). and each column of has at most oy non-zero entries. Then for every E [logn] it holds that
Pr [[(ES))y] > C. = On ",,,t),iii, Vi, [m].
where
C. def
5003 (100 1-1
By union bound,
Pr [|
Vn(logn) S O)
Remark A.1. The parameter a is determined by E, which equals to p in our case. The above bound particularly useful when 8, y are small, that is, we want the matrix sparse columns.
have either small entries or
Proposition A.4 (Proposition 2.5 restated), For E [0,2] and r E N, if a - 1| s 8 < 2r' then
la" 1 2rô.
Proof. Let - l [-8,0 If0 a we have 1 2 a" = x> 2 1 + 1 1<a < + 1/r, then < x < 1/r and hence
r5. If
2
N
15 a" = (1+ (1+x) x¹
(rx)
< 1 2r8.
Fx
B Bounding the Deviation Term
Proof of Lemma 3.7 Our assumption implies that (p g)n/k: 100C vn. By Proposi-
tion 2.3 with probability at least 1 - n we have
E|1 < Caavá s 0.01 - ///kk.
According to Equation
and Su 2
n 2
we have
2 E| < 0.04(p g)nkk.
[[a T)Gul| <
Vsu
12

---

C Polynomial Approximation
The proof of Theorem 3.1 rely on the following result on rank-one pertuebation.
Proposition C.1 (Eigenvalues under rank-one perturbation, Theorem in (BNS79)). ) Let C
D + p22" where D is diagonal, ||=||2 1. Let d1 2 d2 2 2 dn be the eigenvalues of D, and let di 2 d2 2 ... 2 dn be the eigenvalues of C. Then
d. = d + phs,
isisn,
where E #4 1 and S 14 I 1.
Proof of Theorem 3.1 Let X E {0, 1) be the indicator vector for Vi, i.., Xi(u) = 1 u E V, It
easy to see that the cigenvectors of H are XI....... - Xu. Write U = Voi XI........ v Xx E
RVVV D = diag((p 1)$1,..... ..... (p 8)8;;00 0)...))).)) U(
.), then we have H UDUT. Note that
1, = 51. (an) and hence
G = H 11 = U(D + pzz pZZTIUT.
where p == nq. vn ( v
This means the eigenvalues of G are the same as those of D + pz=__ Since || Item 1 follow directly from Proposition C.1 To see Item 2, we use the
Rayleigh quotient characterization of the largest eigenvalue:
v. TG
1 G1,
Σx,ex Guv
n²g + (p q) (sf +
(G) = max
||01
n
2 ni + (p 4) n
K
where the last inequality follows from =
8 V Σラ= s4
1i=1
Proof of Claim 3.1 The assumption on n in Lemma 3.2 implies that f1 = (D-g)m/k2 100C
log By Weyl's inequality, we have
N >x
|| S Coavi
Vi E [n].
100 n
Meanwhile, by Theorem 3.1
|Λ - 14 S (a(G)) (p 4)81 + 1p 9)s; - 11 -11
(p q)n/k:
(p q)n/k
I
1
16 log n
16 n
8 8log n
for = 2,3,.... k. Hence, write def
Blog we have
1. 2r - 21 Sc:
2. A ,, de, Se,..., da [u- E, e, s];
3. for every i 2 k ++ Ae Se.
First, (Ai) = 1 according to the definition of vh, and hence (p(1) 1. As for XT
(A)
(v(A.)) - (())))
|A|=2 + +12A1 + Ble
(by definition of yb)
82 E
1
1
(since 2AA + B
App
1
11
(as E
+ 36 log
6log n
/
6 n
4 lognn
13

---

Consequently, (x((11) 11 <
1logn S 1/2 by Proposition 2.5
2r
Next, for (2,...., AR, 2 the argument is similar:
c2
-1
- (wb(aa))))(a - (+²م = |A|E² + |2A + Bl 5
+ E
\1 /
4 llogn
where the second inequality follows from 2A + B = A by Proposition 2.5 Finally, for i 2 k + 1, it holds that
S 1
This yields 1 - 1| 1/2
p=
S
|Ale²
+ Be
s²
+ 8
1
A1
4logn
which means (xxi)) = |0(2)|'
Tlogn
log
< 1
log log n2
D Bounding the Noise Term
Proof of Lemma 4.7 The lemma readily follows from the following entrywise bound and Chernoff bound.
Claim D.1 (Entries of (G)) For every u X, if uu Ve for some f, then 0 S Fuv S 5k
otherwise, |Fael
We decompose == F' + F", where F" is the intra-cluster part, i.e., Fu, = Fuv if u, u E Ve for some f, and Fy 0 otherwise. Since for every column of F". its non-zero entries are identical and at most 5k/n by the above claim. Hence, every entry of EF equals to the sum of at most 2n independent, centered Bernoulli variables with parameter p. scaled by some factor at most 5k
By Chernoff bound, Præ
n2 Vu, E V, and we have - n2 by union bound. Analogously, by Hoeffding bound, S 10 1- n 2, Since |EF]] S [1E211220 + +|EFF"| [| 20000 the
(EF))
10 kp kogng//n
Pre
[EF
2-100 2- |EF
10 k0 log
Prg
lemma follows from the above two inequalities and union bound.
Proof of Claim D.I Write (G) and recall that (i) (p- q)s,, S 2p for all (ii) nq + P S S ng + (p 4)81 + 2yr, (iii) >> p. n. Assume that u, V2 for some f. Then
ng² + (p² )
(1
FuN AGT G. + BG
11 )
Ap
nqq (p² -92)s (p 1)(A + 11) a(A +
Ap
al + X nq) + (p
-A(2 + (p + g)su))
Ap
Since ng 2 14, the numerator least
2qp + () μ (p g)sw)= (p 9) (2qm/ + X - (p + 9)su).
Because 5 2m2kk > ng + (p 4)n/k: K. we have
2qn/h: + μ (p g). > 2qn 1: + nq (p 2n l- (p - 2)mm2/2m//2 ls = (n 22/k)g 2 0,
which means F,,. 2 0. Meawhile,
Fav < (l - nq)
(p q)(A +
Ap
A/a
where the first term is at most Fuvl
by (ii); second term is most
2p--) <
23 n
Therefore,
n
5k
14

---

For the second part, assume that u, are not in the same cluster. Then
Fuv AG Go BG ng² (pq (su se) + (1 + 10 q-
Ap
Hence,
g(A + 1e (nn)))
q(p (8 + 80)
Fuol 1
+
Ap1
Ap
By (ii), the first term is at most [L n
3g X
3.
by (i), the second term is most 41
4. hence,
Upper bound of || 11 (Proof of Lemma 4.2 Write L def
R(E def + BE
Then D'F = (L + = R LF R to derive good upper bound of L and | as R can be further expressed as
F'F
LDF +... LD' It suffices
sum of powers of E. This is done by the following lemma:
Lemma D.1. The following holds with probability 1 1- On over the choice of E: for all S log holds that
12 S Cc///np(100///p))>>>>> n,
|E C
where C2 def 10 is an absolute constant.
Specifically.
ED'F FR
(t)
E Σ 1=0
A' EittF
A A
0=0 j=0
ddt Mr
Note that |A |A$ Bw < 2 1 (w+t) < 2 (100 log n) -w+(w) It follows that for every
E [r - 1..
|M 11
20000
1 Σ
A | Fl 2-100
1=0
$ Σ
2t (10 log n) 11+55) kp (100 log 5(++s) n
1 ( (logn)-((4))
I CaVkp kp 2t Σ
C2vkp- 2' (logn) + (1+
) C2v
log n
15

---

where the second inequality is by Lemma D.1 and the last step follows from Proposition 2.5 Similarly, for every [r 1].
Nilla -
|AA
|
B 20 D
=
2 2
6-
Σ
())
B' 1 2
5=
2 Σ
()
1
2' .100 (100/mplon log nn)(1+)) C2/kp (100/np)(tz log ((t)))))
= ==
S 22CVV kp
(log n1 -(++)
1=0
< kC 1 S 2C2 / kp log n,
where the second inequality follows from |DD-1-iFl/ S 2, and the third inequality is by
Lemma D.I In sum,
EM 12 20
[1lMell2-s + 11Noll2--oo
I 6C2 Vooekpplo'' n,
(6)
where in the last inequality we also use | |=|1 $2
It remains prove Lemma D.I the proof draws on the entrywise bound in Proposition A.3
Fix an 7 S log n. Write s* def n/k for the of notation. Observe that G*G = A(E++H H + E HF) + Ag( iggF++I,, Jn + FT F). We can apply Proposition A.3 to E H and E" H, with p, p q, 2s". That is, with probability at
Proof of Lemma
D.I I
E I, = A( E
least 1 ((
E 11 112-00 < 500 8/ VTlp VDv22* (100 for 17. 17. 1.
Our assumption 1/8* (C log n) Therefore,
yields/ C./pllog n; moreover, |A[(p 9) s p2 S 1/8" 1 s 12a
|| A( H + F (T) 20000
< A (1) ( H1 2000 + | H 1l
00 (121)
< 8 (C./pp log n) 500(logn) 5n+55
Vn. vp -2- ((100/np)) - (100>'p))"~ Coa vT²
500000 /1p//00//p/////////////// (log (1000
Similarly. by applying Proposition A.3 to E EJJn with a = p. = =,,=1,77 = n, we have, with probability
least 1 O(n 2)
|| F Jn 2 S (0) vp n. (100/mp)--1 .j = 17 + 1.
Since [Aql = 2 1 < 1/2 (Ovnllgg -1 we have
|| Ag Jn + E J) 2+000
< |Aql (|| Jml 20:00 + | Jn Jull (l11)
< 1 (CCmpplogh log n) -1. 500 (log m5y n ((100/mp)) + (100vnpp)*~ 8-1 Coa Coovn
< 500000,/7(ogg n) (100m
(8)
16

---

Combining Equation 7 and Equation 8 we have, with probability at least - O -), npp/ ||2- S C2 C S" (log (100, (100/mp)""" where C2 def
10c.
For the second part, we decompose F = F + F", where F' is the intra-cluster part, i.e., F F if U, E Vj for some E; and F = 0 otherwise. Equipped with Claim D.I we can apply Proposition A.3
on E" F" (with p. 10/s", 7 2s*), and E F" (with p. 7 1 n)):
12 S || 1 20 + "1
FE"F"I.
12
10 2200001og S VūVDD
25
10
Vn (100
n
I C) nM
where the second inequality holds with probability at least 1 - O(n 2)). The lemma follows from union bound over all I log n.
17


Reviews:
[{"review_id": "D7ojRh0CZI", "reviewer": "Reviewer_qMce", "summary": "This paper provides rigorous, theory-based evidence that vanilla spectral algorithms (i.e., methods that run SVD on the adjacency matrix without any further processing) succeed in finding many communities in symmetric stochastic block models. In contrast to Davis-Kahan approaches, the authors adopt an analysis similar to [MZ22b], which is inspired by power iteration. The key technical novelty of the authors' method is a new way to study eigenspace perturbation by using a polynomial approximation of the operator that projects a vector onto the space of the first k eigenvectors of the adjacency matrix. ", "questions": "- I would mention in the abstract that your main contribution is on vanilla algorithms with a large number of communities. This would emphasize the difference between your work and that of [AFWZ20]. \n- What should the value of $\\Delta$ be in Algorithm 1?\n- If there is space, could you elaborate on the connections between your polynomial approach and the power iteration method of [MZ22b]? From a quick read of [MZ22b] it seems there may be some similar ideas and it would be valuable for readers in the field to understand those connections further. ", "limitations": "Limitations have been adequately addressed. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "While there are many community recovery algorithms for SBMs at this point, this paper provides an important analysis of vanilla algorithms for community recovery, showing that pre or post processing steps are unnecessary, thereby validating practical approaches. This is the key strength of the paper, in my view. \n\nA secondary strength, which is of significance to researchers working on random matrix theory, is the use of the polynomial approximation method for the projection operator. This interestingly allows one to circumvent usage of the Davis-Kahan theorem (which is the standard way to handle eigenspace perturbation), and I expect this technique will be useful in various other settings. \n\nThe paper is also very well written, with clear comparisons to related work, and key contributions highlighted.", "weaknesses": "The main weakness I found was that there is little to no discussion of the condition under which Algorithm 1 recovers communities (Theorem 1.1). At face value, it seems like a similar condition as [Vu18], with a few changes, like $\\sigma \\sqrt{k}$ replaced by $\\sqrt{kp} \\log^6 n$. A few questions are:\n- Is this change an artifact of the proof, or is it something more fundamental? In most situations, I'd expect the $\\sqrt{\\log n}$ term to dominate. \n- What are commonly considered regimes for p, q, k in which this threshold is satisfied? For instance, it seems like the regime $p, q = \\Theta ( \\log (n) / n)$ is not covered by the theorem. What's the minimum scaling of $p, q$ that would work here? And what is the maximum number of communities that can be tolerated? Understanding such qualitative cases would make your results much more interpretable. In a similar vein, it was unclear to me whether the condition you have here is optimal in some sense, or if it's just to prove that vanilla methods succeed in just *some* regime.\n\nFinally, I have a question related to how your work compares to [MZ22b]. \n- It seems that your work and [MZ22b] tackle a similar parameter regime for community recovery. How do the achievability regions compare between their work and yours? In particular, does the vanilla algorithm work in almost the same parameter regime, or is the parameter regime more restricted?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank this reviewer for their appreciation of our work, useful suggestions and relevant questions.\n\n**Regarding weakness:**\n\nWe believe the extra $\\log^6 n$ factor can be improved by future works. This term stems from the concentration inequality we used as a black box. A refined analysis of this concentration inequality may remove this factor. However, as you also observed, the $\\sqrt{\\log n}$ factor seems more fundamental in that it comes from Prop. 2.4. \n\nWe can handle the case where  $q = \\Theta(\\log n / n)$. As you observed, the difference between our paper and Vu’s paper is to replace $\\sigma$ by $\\sqrt{p} \\cdot \\log^6 n$.  If $p < 0.9$, $\\sigma$ and $\\sqrt{p}$ are equal up to constant, so our bound is essentially the same as [Vu18] except for the $\\log^6 n$ factor. Here are some example setting of parameters:\n- In the regime $q = \\Theta(\\log n / n)$,  $p = \\Omega(\\frac{k \\log^6 n}{\\sqrt{n}})$ would be sufficient. \n- In the regime $p - q = \\Theta(1)$, we can recover up to  $k = O\\left(\\frac{\\sqrt{n}}{\\log^6 n}\\right)$ clusters. \n\nCompared to [MZ22b], we have an extra $\\sqrt{\\log n}$ factor because we use Prop. 2.4 as did in [Vu18].\n\nThanks for your suggestion. We will add more explanations in our paper.\n\n---\n\n**Regarding questions:**\n\nThanks for the suggestion! We will improve our abstract accordingly. \n\nWe can choose $\\Delta := 0.8(p − q) n / k$ (please see Section 3.3).\n\nTo make their analysis work, [MZ22b]’s power iteration requires the matrix to be nice, i.e., all large eigenvectors are very close. Therefore, in SSBM, they first ``shift’’ the adjacency matrix by considering $G':= G - q\\boldsymbol{1}\\boldsymbol{1}^\\top$. Only the shifted matrix $G’$ has this nice structure and the original $G$ doesn’t have. This shifting step makes analysis simpler at the cost of not being vanilla. \n\nIn contrast, we introduced a polynomial $\\psi$ and analyzed the eigenspace of $G$ through the power iteration of $\\psi(G)$, which is our main novelty.  There are two benefits of using this polynomial: (i) $\\psi(G)$ has a nice structure; (ii) $\\psi$ only appears in our analysis, keeping our algorithm vanilla.\n"}, {"review_id": "cZNSMpxYHF", "reviewer": "Reviewer_89Uu", "summary": "The manuscript mention that the paper contributes by providing a theoretical understanding of the power of vanilla spectral algorithms in clustering problems, specifically in the stochastic block model (SBM).  It also presents a novel analysis of matrix perturbation with random noise.  These contributions suggest that the document offers new insights into the application of SVD in clustering problems, particularly in the context of SBM. It focuses on the stochastic block model (SBM), a benchmark for clustering, and treats it as a form of vector clustering. The manuscript proposes and analyzes a vanilla-SVD algorithm for graph clustering and demonstrates its effectiveness in SBM.", "questions": "1] The paper focuses on the power of the vanilla-SVD algorithm in the stochastic block model (SBM).  It would be interesting to know if the algorithm's effectiveness is limited to the SBM or if it can be applied to other clustering problems as well.  Is there any generalization of its performance to different datasets? \n2] The authors mention that the lack of theoretical analysis for vanilla spectral algorithms is due to technical obstacles.  Could you elaborate on these obstacles and explain why the theoretical analysis is challenging?  What are the main difficulties in analyzing vanilla spectral algorithms?\n3] The authors state that the lack of theoretical analysis is partly due to the simplicity of vanilla spectral algorithms, which are not specifically designed for theoretical models like SBM.  How do these algorithms compare to more complicated algorithms designed for SBM in terms of performance and practicality?  Are there any trade-offs between simplicity and performance?\n4] The authors mention the potential application of vanilla spectral algorithms in real-world data, but there is no analysis or discussion on this topic.  Can you provide any insights into the behavior of these algorithms on real data?  How do they perform in different applications?  Are there any challenges or limitations when applying vanilla spectral algorithms in practice?\n", "limitations": "This work should design some experiments to fully illustrate the application value of the model.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main topic of the manuscript is the analysis of the power of Singular Value Decomposition (SVD) in clustering problems. The manuscript discusses the use of dimensionality reduction techniques, specifically PCA and SVD, to improve clustering results in high-dimensional datasets. It explains that classical clustering algorithms like K-means may perform poorly in such datasets due to the curse of dimensionality. Spectral methods like PCA and SVD have been observed to significantly enhance clustering results. The manuscript explores the reasons behind this improvement, including filtering noise from high-dimensional data. It focuses on the stochastic block model (SBM), a benchmark for clustering, and treats it as a form of vector clustering. The manuscript proposes and analyzes a vanilla-SVD algorithm for graph clustering and demonstrates its effectiveness in SBM. The authors present their results, including a clustering algorithm and an analysis of matrix perturbation with random noise. They compare their approach with existing analysis methods and highlight the advantages of their approach. The document concludes with a proof outline and technical contributions, outlining the steps taken to analyze the power of vanilla spectral algorithms for clustering.\n\n", "weaknesses": "There are many formulas that make the readability not very strong. Some experiments should be designed to evaluate the significance of the model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really appreciate this review’s feedback and questions. We answer them below.\n\n**Regarding the weakness:**\n\nSince this is a theoretical paper, some formulas are necessary. However, we will try our best to make this paper accessible to most readers. In fact, results and proofs in random matrix theory are often mathematically intensive. Compared to previous papers, our analysis is quite concise. For example, the paper we cited [AFWZ20] (https://arxiv.org/pdf/1709.09565.pdf) has 58 pages and way more formulas.\n\nThe SBM model is a well-known benchmark for graph clustering problems (according to wikipedia, https://en.wikipedia.org/wiki/Stochastic_block_model). So we didn’t run experiments to validate this model. \n\n\n**Regarding the questions:**\n\n1] Regarding the algorithm's effectiveness in other clustering problems. \n\nThis paper focuses on vanilla spectral algorithms — specifically SVD (singular value decomposition) algorithm, which is already a very popular algorithm in practice.  We did not propose a new algorithm. Instead, we provided new theoretical insight into why this widely-used algorithm is successful.\n\n2] On the obstacles of theoretical analysis for vanilla spectral algorithms.\n \nWe have discussed on major reasons in our paper. One main reason is that many previous analyses used a key component called Davis-Kahan theorem. Davis-Kahan theorem is suboptimal in analyzing vanilla spectral algorithms in SBM (please see Page 4 of our paper). In fact, such obstacles have also been discussed in previous papers. The reason that we can analyze SVD is that we fully avoid Davis-Kahan theorem. We believe this is a highly non-trivial step since a majority of papers in random matrix theory used Davis-Kahan (or its variants) to analyze matrix perturbations. Our new approach has a potential to give more applications in different settings.\n\n3] Compared to more complicated algorithms designed for SBM in terms of performance and practicality.\n\nThese complicated algorithms perform well in SBM. However, they were not popular in practice because their performance on real datasets is no better (usually worse) than vanilla ones. In contrast, we analyzed vanilla spectral algorithms such as PCA and SVD which are successful in practice.\n\n\n 4] Application of vanilla spectral algorithms in real-world data.\n\nVanilla algorithms such as PCA and SVD (the algorithm we analyzed in this paper) are widely used in practice. There are many papers/blogs which have discussed their performance in all kinds of real scenarios. Given this reason, we didn’t repeat these discussions. Instead, we focus on the performance of SVD in theoretical models.\n\nOverall, thanks again for these comments and questions :-)\n"}, {"review_id": "4JIcIZUvnD", "reviewer": "Reviewer_bCxf", "summary": "This paper investigates the effectiveness of the vanilla-SVD algorithm in the stochastic block model (SBM) and demonstrates that it can accurately recover all clusters in the symmetric setting. The authors address an open question raised by Van Vu in the symmetric setting.\n", "questions": "1. What advantages does the SVD approach in this paper offer compared to the terminal version of the Johnson-Lindenstrauss Lemma mentioned in ``Optimal terminal dimensionality reduction in Euclidean space''?\n\n2. Is the proposed  scheme  efficient for large $n$ and $k$? If $n$ and $k$ are large, can the algorithm handle them efficiently?\n", "limitations": "Overall, this paper provides some valuable contributions to the study of the vanilla-SVD algorithm in the SBM. However, addressing the weaknesses mentioned above, such as conducting experiments, comparing complexities, and improving readability, would enhance the quality and impact of the research.\n", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The vanilla algorithms employed in this study are applicable to a wide range of parameters, surpassing previous limitations that only allowed analysis on a constant number of clusters.\n\n2. They also provide a novel analysis on  matrix perturbation with random noise. \n", "weaknesses": "1. The paper lacks experimental evaluation to demonstrate the effectiveness of the proposed scheme.\n\n2. The time and space complexity analysis are not compared with previous schemes, which could provide insights into the efficiency of the proposed approach.\n\n3. Lots of proofs are omitted in the main paper (I understand that this is due to the space limit). Maybe the theory conferences like COLT is a better venue for this paper?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank this reviewer for useful comments and questions.\n\n**Regarding weakness:**\n\nWe did not propose a new scheme. Instead, we provided a theoretical analysis for a very popular algorithm — SVD (singular value decomposition). Given this algorithm has already been widely used in practice. We did not run experiments further to demonstrate the effectiveness.\n\nThe time and space complexity of our algorithm is simply the same as the time and space complexity of SVD.\n\nAll proofs are included in the supplementary. Even though the main paper has a page limitation, we will prepare an improved full version in arXiv once this paper has been accepted. COLT is a good conference, but we also love NeurIPS :-)\n\n**Regarding questions:**\n\n**Comparison to JL projections.** JL is also a good dimensionality reduction algorithm. However, it only preserves $\\ell_2$ norm distance after projection. By contrast, SVD can do something more, namely, SVD also filters the noise. In fact, this is the main reason why SVD can recover clusters in SBM, but JL projection can not.\n\n**Efficiency when $k$ and $n$ are large.** The main part of our algorithm is to find the top $k$ eigenvectors of a $n\\times n$ matrix. This can be implemented within $O(k n^2)$ time and $O(n^2)$ space. \n\n"}, {"review_id": "BrdRf97REc", "reviewer": "Reviewer_Qju9", "summary": "In order to understand the behavior of spectral steps in clustering problems, this paper studies the power of vanilla-SVD algorithm in the SBM. This work shows that vanilla-SVD algorithm recovers all clusters correctly in the symmetric setting. ", "questions": "1. Experiments are suggested to conduct from the perspectives of practical applications. \n2. Considering this paper as purely theoretical work, then based on Weaknesses #3, it is recommended to provide quantitative experimental analysis to supplement and demonstrate the limitations of the theoretical analysis of the comparison methods.\n3. The arguments of this paper need verifying by more settings, not only in symmetric version of SBM.\n4. It is recommended to use reference citation format that complies with the guidelines specified by this conference. Additionally, it would be beneficial to gain a better understanding of the contributions of spectral methods in the field of machine learning or data mining. ", "limitations": "The authors have adequately addressed the limitations.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. To theoretically understand the power of practically successful vanilla spectral algorithms, this paper studies SBM as a preliminary demonstration. Then, some proofs are presented for the proposed Theorem 1.1.\n2. This work shows that vanilla algorithms is indeed a clustering algorithm in SSBM for a wide range of parameters.\n3. The authors give another analysis on matrix perturbation with random noise.\n4. Detailed comparisons with existing analysis for vanilla spectral algorithms in SBM are presented in this paper.", "weaknesses": "1. In real applications, it is common in practice that spectral embeddings obtained by spectral clustering algorithm need a post-processing, e.g., k-means. It is reasonable that spectral embeddings themselves are clustering-friendly. Thus, the contributions of analyzing vanilla spectral methods could be highlighted.\n\n2. From Section 1.3, it can be observed that there is limited work on the vanilla spectral algorithm. Could the authors provide an explanation for the reasons behind analyzing the parameters in the SSBM setting in this paper?\n\n3. From the comparisons, it is apparent that there are some issues with the related theoretical analyses, such as [AFWZ20], [EBW18], [PPV+19], etc. Since these weaknesses are evident, could the authors consider providing quantitative experimental analysis in addition to the theoretical analysis?\n\n4. Between lines 48 and 49, '...can be view as a fixed matrix...' should be corrected to '...viewed...'.\n\n5. The coherence in the review content in the Introduction section is insufficient. The authors seem to focus more on the mathematical advancements rather than considering the theoretical and practical applications of spectral methods in the field of machine learning, especially the related work in both theoretical understandings and practical applications.\n\n6. The argument is verified using a specific setting in a typical model, SSBM,  to demonstrate that vanilla spectral algorithm is powerful and prectically successful. It may not be comprehensive enough.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for pointing out the typo and your suggestion on the citation format; we shall certainly improve our paper accordingly. \n\n**Regarding experiments (Weakness #3 and Question #1, #2):**\n\nWe study the same algorithm (SVD) as in  [AFWZ20], [EBW18] [PPV+19] and we give better analysis. Since it is the same algorithm, we are not sure how to run quantitative experimental analysis for comparison. Please let us know if you have any suggestion. For practical applications, the fact that SVD is widely-used in machine learning and data mining has already validated the effectiveness of the algorithm, so we only focus on theoretical analysis.\n\n**Regarding other issues:**\n\n- **Weakness #1.**  Even if post-processing, say K-means, is used in practice. There are a lot of practical observations that, in some scenarios, vanilla spectral algorithm + K-means is much better than K-means itself.  (There are many references. If you want, we can provide some of them.) The main reason is that vanilla spectral algorithms can remove noise in these applications. This phenomenon is exactly what we have analyzed in the SSBM model. We think this is also a good contribution.\n\n- **Weakness #2 #6 & Question #3.** SBM is a well-known benchmark for clustering tasks. SSBM is indeed a further simplification, but it is a good starting point. Analyzing parameter settings in SSBM could help understand under what conditions SVD works well theoretically.  As you suggested in Weakness #6 and Question #3, we expect future works to analyze more general settings. But even for SSBM, it is highly non-trivial. This problem has been open for several years, and some great mathematicians, such as the authors of [AFWZ20], [EBW18],[Vu18], [PPV+19]  didn’t solve it.\n\n- **Weakness #5.** We will definitely improve our introduction part to highlight the relevance to machine learning and append more related works. \n"}, {"review_id": "W9uOokqIoc", "reviewer": "Reviewer_b4S2", "summary": "This paper studies the power of vanilla-SVD algorithm, algorithm without any pre-processing or post-trimming steps, in the symmetric stochastic block model and proves it recovers all clusters in the balanced case, which answers an open question in [Vu18].", "questions": "This work argues that its analysis can handle the case of $k = \\omega(1)$ while [MZ22b] considers a stronger case of $k = \\omega(\\log n)$. Can the analysis in this work also handle the case of $k = \\omega(\\log n)$?", "limitations": "There seems to be no discussion of limitations or potential societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The main contribution of this work lies in its demonstration of the effectiveness of a truly vanilla SVD algorithm in recovering all clusters of the symmetric stochastic block model in the balanced case with high probability theoretically. Some noticeable distinctions from existing works include a truly vanilla SVD algorithm without any additional pre-processing steps and the ability of handling of cluster numbers $k = \\omega(1)$. Also, from a technical standpoint, the authors introduce a novel \"polynomial approximation + entrywise analysis\" approach, which simplifies the analysis of eigenspace perturbation by reducing it to the analysis of a simple polynomial under perturbation thus makes the analysis more robust and requires less structure.\n", "weaknesses": "The presentation of this work could be improved. First, it might be better to explicitly mention in the Abstract and Section 1that the analysis is within the balanced case and not directly extended to other cases. Second, [MZ22b] also claims answering the open question in [Vu18] in the balanced case. The authors point out that the centered-SVD algorithm proposed in [MZ22b] is not truly vanilla, containing a pre-processing centering step which depends on the knowledge of $q$. But it would still be beneficial to compare the condition and bounds in [MZ22b] to have a more complete understanding. Third, adding more background information and necessary theoretical knowledge would make this work more accessible to a broader audience. Lastly, the analysis in Section 4 may be better positioned prior to Section 3.3, which already wraps up the entire analysis, or included within the supplementary material.\n\nOthers:\n- In Lemma 3.1, it should be $1 - n^{-3}$ rather than $1- n^3$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank this reviewer for the suggestions on improving our presentation. We will improve our writing accordingly.\n\n**Regarding the question about  $k=\\omega(\\log n)$:**\n\nYes, our proof works perfectly in this case. As long as the parameters $n,p,q,k$ satisfy the requirement in Theorem 1,  our algorithm is able to recover the clusters. For example, if $p=0.51, q=0.49, k = n^{0.1}$, our algorithm can recover all clusters.\n"}]

Author rebuttal:

Meta-review: Generally reviewers felt positively about this paper. it resolves an important open theoretical question about stochastic block model (SBM) recovery with `vanilla' spectral algorithms. Given the theoretical importance of the SBM model, and the importance of spectral clustering methods in practice, this result should be impactful. 

During discussion it was agreed that a lack of empirical results in the paper was not a concern, due to the paper addressing a theoretical question about a very empirically well-established approach.
Decision: Accept (poster)