On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
Authors: Aditya Bhaskara
Agastya Vibhuti Jha
Michael Kapralov
Naren Sarayu Manoj
Davide Mazzali
Weronika Wrzos-Kaminska
Venue: NeurIPS 2024 poster (2024)
Keywords: stochastic block model
clustering
spectral algorithms
random matrices
semirandom model
monotone adversary
Primary area: learning_theory
TL;DR: We investigate the robustness of spectral clustering algorithms against various semirandom adversaries.

Abstract: In a graph bisection problem, we are given a graph $G$ with two equally-sized unlabeled communities, and the goal is to recover the vertices in these communities. A popular heuristic, known as spectral clustering, is to output an estimated community assignment based on the eigenvector corresponding to the second-smallest eigenvalue of the Laplacian of $G$. Spectral algorithms can be shown to provably recover the cluster structure for graphs generated from probabilistic models, such as the Stochastic Block Model (SBM). However, spectral clustering is known to be non-robust to model mis-specification. Techniques based on semidefinite programming have been shown to be more robust, but they incur significant computational overheads. 

In this work, we study the robustness of spectral algorithms against semirandom adversaries. Informally, a semirandom adversary is allowed to ``helpfully'' change the specification of the model in a way that is consistent with the ground-truth solution. Our semirandom adversaries in particular are allowed to add edges inside clusters or increase the probability that an edge appears inside a cluster. Semirandom adversaries are a useful tool to determine the extent to which an algorithm has overfit to statistical assumptions on the input. 

On the positive side, we identify a wide range of semirandom adversaries under which spectral bisection using the _unnormalized_ Laplacian is strongly consistent, i.e., it exactly recovers the planted partitioning. On the negative side, we show that in many of these settings, _normalized_ spectral bisection outputs a partitioning that makes a classification mistake on a constant fraction of the vertices. Finally, we demonstrate numerical experiments that complement our theoretical findings.

On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
Aditya Bhaskara
Agastya Vibhuti Jha
Michael Kapralov 1
Naren Sarayu Manoj
Davide Mazzali
Weronika
Abstract
In graph bisection problem, we are given graph G with two equally-sized un- labeled communities, and the goal is to recover the vertices these communities. A popular heuristic, known as spectral clustering, is to output an estimated com- munity assignment based on the eigenvector corresponding to the second smallest eigenvalue of the Laplacian of G. Spectral algorithms can be shown to provably recover the cluster structure for graphs generated from certain probabilistic mod- els, such as the Stochastic Block Model (SBM). However, spectral clustering is known to be non-robust to model mis-specification. Techniques based on semidef- inite programming have been shown to be more robust, but they incur significant computational overheads.
In this work, we study the robustness of spectral algorithms against semirandom adversaries. Informally, a semirandom adversary allowed "helpfully" change the specification of the model in a way that is consistent with the ground-truth so- lution. Our semirandom adversaries in particular are allowed to add edges inside clusters or increase the probability that edge appears inside cluster. Semiran- dom adversaries are a useful tool to determine the extent to which an algorithm has overfit statistical assumptions on the input.
On the positive side, we identify classes of semirandom adversaries under which spectral bisection using the unnormalized Laplacian is strongly consistent, i.e., it exactly recovers the planted partitioning. On the negative side, we show that in these classes spectral bisection with the normalized Laplacian outputs parti- tioning that makes a classification mistake on constant fraction of the vertices. Finally, we demonstrate numerical experiments that complement our theoretical findings.
Introduction
Graph partitioning clustering is fundamental unsupervised learning primitive. In graph par- titioning problem, one seeks to identify clusters of vertices that are highly internally connected and sparsely connected to the outside. This task is of particular significance when the given graph presents a latent community structure. In this setting, the goal is to recover the communities as accurately as possible. Various statistical models that attempt capture this situation have been pro- posed and studied in the literature. Perhaps the most popular of these is the Symmetric Stochastic Block Model (SSBM) [HLL83]].
University of Utah. Email: thaskaraaditya@gmaae com.
t University of Chicago. Email: agastyavjha. 208gma81..l.cc ggastyavjha.288mmaa1..
fcooe Polytechnique Fédérale de Lausanne. Email: michael wwwpallvweppll.cmmmmmmmm ch.
Toyota Technological Institute at Chicago. Email: nam@ttic.edu.
École Polytechnique Fédérale de Lausanne. Email: davide www.mlleeeellll..mmm ch.
|| fcole Polytechnique Fédérale de Lausanne. Email: veronika. urzos-kaminskaeepfl)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Following the notation of previous works [AFWZ20; DLS21], in this paper we describe an SSBM with specifications n, P1, P2.P. P. q. where n an even positive integer, P1 and P3 are a partitiooning of the vertex set V = {1 ....... n into subsets of equal size, and p and q are probabilities. Without loss of generality, we may assume that the partitions P1 and P2 consist of vertices I..... n1/2 and n/2- 1, I....., respectively. Hence, with a mild abuse of notation, we write an SSBM with parameters n, P: q only and write it as SSBM p. q). Now, let (n,M p, q) be a distribution over random undirected graphs G (V, where each edge (u, w) E Pi Pi and (v, w) E P22 x P2 (which we refer to as "internal edges") appears independently with probability p, and each edge (v, w) E refer as "crossing edges") appears independently with probability q. When p >>> q, there should be many more internal edges than crossing edges. Hence, we expect the community structure to become more evident as p tends away from q.
Pi x P2 (which
In such scenarios, our general algorithmic goal is to efficiently identify P1 and P2 when given G without any community labels. This task is hereafter referred to as the graph bisection problem. In this work, we will be interested in exact recovery, also known as strong consistency, in which we want an algorithm that, with probability at least 1 1/n over the randomness of the instance, exactly returns the partition (PI,P2) for all n sufficiently large. Other approximate notions of recovery (such almost exact, partial, and weak recovery) are also well-studied but are beyond the scope of this work.
Although the SSBM(n. P. 9) distribution over graphs is useful starting point for algorithm design and has led to deep theory about when recovery is possible and of what nature [Abb18], may not be representative of all scenarios in which we should expect our algorithms to succeed. To remedy this, researchers have proposed several different random graph models that may be more reflective of properties satisfied by real- real-world networks. These include the geometric block model [GNW24], the Gaussian mixture block model [LS24], and others.
In this paper, we take a different perspective to graph generation by considering various semiran- dom models. At a high level, a semirandom model for statistical problem interpolates between an weraae--case input (for example produced by model such as the SSBM) and a worst-case in- put, in a way that still allows for meaningful notion of ground-truth solution. In our context of graph bisection, this can be achieved by an adversary adding internal edges or by the distribution of internal edges itself being nonhomogeneous (i.e., every internal edge (v, w) appears independently with probability Pew 2 p. where the Pew may be chosen adversarially for each internal edge). Re- searchers have studied similar semirandom models for graph bisection [beyondclusterin; FK01; MMV12; MPW Moi21] and other statistical problems such as classification under Massart noise [MN06], detecting a planted clique in a random graph [FK01; CSV17; MMT20; BKS23], sparse recovery [KLLST23], and top-K ranking [YCOM24).
These modeling modifications are not necessarily meant to capture a real-worke data generation process. Rather, they are useful testbed with which we can determine whether commonly used algorithms have overfit to statistical assumptions present in the model. In particular, observe that these changes in model specification are ostensibly helpful, in that increasing the number of internal edges should only enhance the community structure. Perhaps surprisingly, it is known that a number of natural algorithms that succeed in the SSBM setting no longer work under such helpful modifi- cations [Moi21]. Therefore, it is natural to ask which algorithms for graph bisection are robust in semirandom models.
At this point, the performance of approaches based on convex programming is well-understood in various semirandom models [FK01; MMV12; MPW 16; Moi21; CdM24]. However, in practice, it is impractical to run such an algorithm due to computational costs. Another class of algorithms, that we call spectral algorithms,, is more widely used in practice. Loosely speaking, spectral algorithm constructs a matrix M that is a function of the graph G and outputs a clustering arising from the embedding of the vertices determined by the eigenvectors of M. Popular choices of matrices include the unnormalized Laplacian LG and the normalized Laplacian LG (we will formally define and intuit these notions in the sequel) [Von07]. This is because structural properties of both Le and La imply that the second smallest eigenvalue of each, denoted as A2 and A2(Ca), serves as continuous proxy for connectivity, and the corresponding eigenvector, un (La) and (L(a)) has entries whose signs reveal a lot of information about the underlying community structure. This motivates Algorithm 1. It can be run, for example, with Matrix(G) == LG Matrix (G) = Cc. Following this discussion, we arrive at the question we study in this paper.
2

---

Algorithm SpectralBisection: given G = (V, E), outputs bipartition of V
procedure SpectralBisection((G)
D (V, E) is the input graph P E RVXV is matrix with real eigenvalues ((); U;) )= < eigenvalue-digeeveetoo pairs with A S ... S An
2:
M < Matrix(G)
3:
D =
4:
S (v E EV= u2 < 0)
5: return {S, V 5}
Question 1. Under which semirandom models do the Laplacian-based spectral algorithms, using the second eigenvector of LG or LG, exactly recover the ground truth communities P1 and Pg?
Main contributions. Our results show a surprising difference the robustness of spectral bi- section when considering the normalized versus the unnormalized Laplacian. We summarize our results below:
Consider nonhomogeneous symmetric stochastic block model with parameters g < < D. where every internal edge appears independently with probability Pur E [p. and every crossing edge appears independently with probability g. We show that under an appropriate spectral gap condition, the spectral algorithm with the unnormalized Laplacian exactly re- covers the communities P1 and Pz. Moreover, this holds even an adversary plants < mp internal edges per vertex prior to the edge sampling phase.
Consider stronger semirandom model where subgraphs on the two communities Pi and P2 adversarially chosen and the crossing edges sampled independently with probability q. We show that if the graph is sufficiently dense and satisfies a spectral gap condition, then the spectral algorithm with the unnormalized Laplacian exactly recovers the communities Pi and P2.
We show that there is family of instances from nonhomogeneous symmetric stochastic block model in which the spectral algorithm achieves exact recovery with the unnormalized Laplacian, but incurs constant error rate with the normalized Laplacian. This is surprising because it contradicts conventional wisdom that normalized spectral clustering should be favored over unnormalized spectral clustering [Von07].
We also numerically complement our findings via experiments various parameter settings.
Outline. The rest of this paper is organized as follows. In Section 2, we more formally define our semirandom models, the Laplacians L and L, and formally state our results. In Section 3, we give sketches of the proofs of our results. In Section 4, we show results from numerical trials suggested by our theory. In Appendices A. and A.5 we prove important auxiliary lemmas we need for our results. In Appendix A.6, we prove our robustness results for the unnormalized Laplacian. Appendix A.8, we prove our inconsistency result for the normalized Laplacian. In Appendix B, we give additional numerical trials and discussion.
Models and main results
In this paper, we study unnormalized and normalized spectral clustering in several semirandom SSBMs. These models permit richer family of graphs than the SSBM alone.
Matrices related to graphs. Throughout this paper, all graphs are to be interpreted as being undirected, and assume that the vertices of nevertex graph coincide with the set fl..... n... With this in mind, we hegin with defining various matrices associated with graphs, building up to the unnormalized and normalized Laplacians, which are central to the family of algorithms we analyze (Algorithm 1).
Definition 2.1 (Adjacency matrix). Let = (V, E) be a graph. The adjacency matrix Ag VVV of G is the matrix with entries defined Ag [V, wi = 1 {v,, E).
Definition 2.2 (Degree matrix). Let G (V, E) be graph. The degree matrix DE E VVV of the diagonal matrix with entries defined as D u] = dG(v). where dalv) is the degree of

---

The NSSBM family generalizes the symmetric stochastic block model described in the previous section this is attained by setting Pew = for all internal edges (u, w). However, can also encode biases for certain graph properties. For instance, distribution from the NSSBM family may Definition 2.3 (Unnormalized Laplacian), Let G = E) be graph. The unnormalized Laplacian
LG E VXV of G is the matrix defined as LG == D A Eionoee ee,) Cv,) where denotes the i-th standard basis vector.
Definition 2.4 (Normalized Laplacians). Let G = (V, E) be a graph. The symmetric normalized Laplacian LG.sym E <RV XV and the random walk Laplacian L E ERVX of G are defined as
Gy == I D 1/2 AGD 1/2
LG.0 I Ag.
For all notions above, when the graph G clear from context, we omit the subscript G. Furthermore, when discuss normalized Laplacians, intend its symmetric version Lsym unless otherwise stated. So, we omit this subscript as well and simply write L.
Next, we define the spectral bisection algorithms. We will discuss some intuition for why these algorithms are reasonable heuristics in Section 3.
Definition 2.5 (Unnormalized and normalized spectral bisection). Let G = (V, E) be graph, and let its unnormalized and normalized Laplacians be L and L, respectively. We refer to the algorithm resulting from running Algorithm on with Matrix(G)= = LG as unnormalized spectral bisection. We refer the algorithm resulting from running Algorithm I on G with Matrix(G) = La as normalized spectral bisection.
Our goal is to understand when the above algorithms, applied to a graph with a latent community structure, achieve exact recovery strong consistency, defined as follows.
Definition 2.6. Let (P1, P2)
be partitioning of = - n and let D D(( P2}) be
distribution over n-vertex graphs G = -V,E). We say that an algorithm is strongly consistent or achieves exact recovery on D if given a graph G D it outputs the correct partitioning {P1, P2) with probability at least 1 - 1/n over the randomness of G.
2.1 Nonhomogeneous symmetric stochastic block model
Our first model is a family of nonhomogeneous symmetric stochastic block models, defined below.
Model 1 (Nonhomogeneous symmetric stochastic block model). Let n. be an even positive integer, V [I,...n.} n). {PI, }2) be partitioning of V into two equally-sized subsets, and q < p S p be probabilities. Let 'D be any probability distribution over graphs G = (V, E) such that for every (v. w) Pi Pi and (v, w) E P2 Pz, the edge (v, w) appears in E independently with some probability Pew E. [p.p), for every (v. w) E x Ps, the edge (v, w) appears in E independently with probability q. We call such a nonhomogeneous symmetric stochastic block model (which we will abbreviate as NSSBM), We call the set of all such 'D the family of nonhomogeneous stochastic block models with parameters p. p. q. written as NSSBM p. p. q)-
To visualize Model 1, consider the expected adjacency matrix of some NSSBM distribution. We then have the relations
p J n/2
9- J
n/2
Pp.
9 Jn/2 Pp.
p J J
q Ja/2
<
<
q Jn/2
Jn/2
J-
q Jn/2
P
D-Jn/2
where the leftmost matrix denotes the expected adjacency matrix of SSBM(n. q). the rightmost matrix denotes the expected adjacency matrix of SSBM P, q). Jj denotes the x le all-ones matrix, and Pp, and Pr, denote the edge probability matrices for edges internal to P1 and Pz, respectively.
The above also shows that the rank of the expected adjacency matrix for SSBM P, q) is 2. How- ever, the rank for the expected adjacency matrix for some NSSBM distribution may be as large as ((n). Perhaps surprisingly, this will turn out be unimportant for our entrywise eigenvector perturbation analysis. In particular, the tools we use were originally designed for low-rank signal matrices or spiked low-rank signal matrices [AFWZ20; DLS21; BV24], but we will see that they can be adapted to the signal matrices we consider.
encode the idea that certain subsets of P; are expected to be denser than P1 as a whole.
With this definition in hand, we are ready to formally state first technical result in Theorem 1.

---

Theorem 1. Let P.P.q q be probabiliries such that 9 < S P and such that a := p/(p - q) is an
arbitrary constant. Let &NSSBM(n, P.P.P.P.). p. P).. Let n Z N(a) where the function N(a) only depends a. There exists universal constant C > O such that if
n(p - q) 2 (= (Vnplogn log logn):
(gap condition)
then unnormalized spectral bisection is strongly consistent on D.
We prove Theorem in Appendix A.7.1. In fact, we show a somewhat stronger statement in addition to the process described above, we also allow the adversary to, before sampling the graph. set small number of the Pow to (at most npy log log edges per vertex). We detail this further in Appendix A.7.1.
We now remark on the tightness of our gap condition in Theorem 1. A work of Abbe, Bandeira, and Hall [ABH16] identifies exact information-theone high probability is possible and below which no algorithm can be strongly consistent. In particu- lar, the threshold states that for any p and q satisfying vp- / > / log n/n, exact recovery is impossi-
threshold above which exact recovery with
possible, and when p and do not satisfy this, exact recovery is information-theorrtiial ble. Furthermore, Feige and Kilian [FK01] prove that the information -hhooretic threshold does not change in somewhat stronger semirandom model that includes the NSSBM family. Additionally, Deng. Ling, and Strohmer [DLS21] show that unnormalized spectral bisection strongly consistent all the way to this threshold in the special case where the graph is drawn from SSBM(n, P. p.g). By contrast, our gap condition holds in the same critical degree regime as in the ieformation-theoreee threshold (namely, p = Oloog n/n)) but our constant is not optimal. We incur this constant loss be- cause for the sake of presentation, we opt for cleaner argument that can handle the nonhomogeneity and generalizes more readily across degree regimes. To our knowledge, none of these features are present in prior work analyzing spectral methods an SSBM setting [AFWZ20; DLS21].
2.2 Deterministic clusters model
Given Theorem it is natural to ask what happens the structure of the graphs in Pi and P2 instead of simply allowing the adversary to perturb the edge probabilities, In this section, we answer this question. We first describe a more adversarial semirandom model than the NSSBM family. We call this model the deterministic clusters model, defined as follows.
allow the adversary full control over
Model 2 (Deterministic clusters model). Let be an even positive integer, = (1...,. n...
(P1, P2] be a partitioning of V into two equally-sized subsets, q be probability, and din be an integer degree lower bound. Consider graph G = (V,E) generated according to the following process.
1. The adversary chooses arbitrarily graphs G[Pi] and G[Pa] with minimum degree dini
2. Nature samples every edge (v,w) E P1 x Ps to be in E independently with probability q.
3. The udversary arbitrarily adds edges (v, w) E P1 x Pi and (v, w) E P2 x P2 to E after observing the edges sampled by nature.
We call distribution 'D of graphs generated according to the above process a deterministic clus- ters model (DCM). We call the set of all such the family of deterministic clusters models with parameters din and 9. written as DCM(n, din, q).
The DCM graph generation process is heavily motivated by the one studied by Makarychev. Makarychey, and Vijayaraghavan [MMV12]. This model is much more flexible than the SSBM and NSSBM settings in that the graphs the adversary draws on P1 and P2 are allowed to look very far from random graphs. This means the DCM is particularly good benchmark for algorithms to ensure they are not implicitly using properties of random graphs that might not hold in the worst case.
Within the DCM setting, we have Theorem 2.
Theorem 2. Let be a probability and din be an integer, and let D E DCM(n, din q). For G ~ D. let L denote the expectation of L after step (2) but before step (3) in Model 2. There exists constants
5

---

C1, C2, C3 > 0 such that for all sufficiently large, if
din 2 C1
(2
and
>L( x2 vn C2nq O3 (Vnglogn + logn):
then unnormalized spectral bisection is strongly consistent on D.
We prove Theorem 2 in Appendix A.7.2. We remark that, as in Theorem 1, the constants that appear Theorem 2 are somewhat arbitrary. They are chosen to make our proof's cleaner and can likely be optimized.
As basic application of Theorem 2, note that in the SSBM, p w(1/vn) and q 1/ then for n sufficiently large, with high probability, the resulting graph satisfies the conditions needed to apply Theorem 2. For a more interesting example, let P1 and Pa be two d-regular spectral expanders with d w(vn) and let q S 1/vn. On top of both of these two graph classes, one can further allow arbitrary edge insertions inside P1 and P2 while still being guaranteed exact recovery from unnormalized spectral bisection.
2.3 Inconsistency of normalized spectral elustering
Notice that in Theorem and Theorem 2, only address the strong consistency of the unnormal- ized Laplacian in our nonhomogeneous and semirandom models. But what happens when we run spectral bisection with the normalized Laplacian?
In Theorem 3, we prove that there a subfamily of instances belonging to NSSBM(n, p, P, q) with 6p, p/2 2 which unnormalized spectral bisection is strongly consistent (following from Theorem 1) but normalized spectral clustering inconsistent in a rather strong sense. Thus, one cannot obtain results similar to Theorem and Theorem 2 for normalized spectral bisection.
Theorem 3. For all n sufficiently large, there exists a nonhomogeneous stochastic block model such that unnormalized spectral bisection strongly consistent whereas normalized spectral bisection (both symmetric and sandom-wall, incurs misclassification rate of at least 24% with probability 1 1/n.
We prove Theorem 3 in Appendix A.8. Furthermore, expect that it is straightforward to adapt the example in Theorem to prove an analogous result for our DCM setting.
The result of Theorem 3 may run counter to conventional wisdom, which suggests that normalized spectral clustering should be favored over the unnormalized variant [Von07]. Perhaps a more nu- anced view in light of Theorem 1 and Theorem 2 is to acknowledge that the normalized Laplacian and its eigenvectors enjoy stronger concentration guarantees [SB15; DLS21], but the unnormalized Laplacian's 's second eigenvector is more robust to monotone adversarial changes.
2.4 Open problems
Perhaps the most natural follow-up question inspired by our results is determine whether the restriction that every internal edge probability Pew S P can be lifted entirely while still maintaining strong consistency of the unnormalized Laplacian (Theorem 2). Another exciting direction for future work is to lower the degree and/or spectral gap requirement present in our results in the DCM setting (Theorem 2). Finally, only study insertion-only monotone adversaries, crossing edge deletions change the second eigenvector the expected I Laplacian. It would be illuminating to understand the robustness of cappaciin-baseed spectral algorithms against monotone adversary that also allowed to delete crossing edges. We are optimistic that the answers to one or more of these questions will further improve our understanding of the robustness of spectral clustering to "helpful" model misspecification.
Analysis sketch
First, let us give some intuition as why one may expect that unnormalized spectral bisection is robust against our monotone adversaries. Here and in the sequel, let u = [1n/2 + - 1,//2/ n. where 1 denotes the all-ls vector dimensions and @ denotes vector concatenation. Let be the unnormalized Laplacian of the graph we want to partition, L' == E [L]. = L - L and A = (L*)) for S n. For an edge (w, w), let evw == Cy Cw. so that eve is an edge incidence vector corresponding to the edge (v, w). Let Pow be the probability that the edge (v. w)

---

appears in G' and observe that L can be written as
L
Σ E
T Dowe Evw vew
+
Σ Euroits
T q: Evw vy
where Einternal (Pi X1) x P2) and Ecrossing = Pi P. We can verify that uz is an eigenvector of L* indeed, we do sO in Lemma A.14, And, for now, assume that u. does correspond to the second smallest eigenvalue of L (in our NSSBM family, this is easily ensured by enforcing p 9). Moreover, for every internal edge (u, w) E Emmernal: changes in internal edges do not change the fact that u is an eigenvector of the perturbed matrix. Thus, if the sampled L is close enough L', then it is plausible that the second eigenvector of L, denoted as u2, is pretty close to uz. In fact, the following conceptually stronger statement holds. If the subgraph formed by selecting just the crossing edges of G is regular, then u. is an eigenvector of L. This follows from the fact that u² is an eigenvector of the unnormalized Laplacian of any regular bipartite graph where both sides have size n and the previous observation that every internal edge is orthogonal to 2.z.
have (Cewr Uzz 0. Hence, any
To make this perturbation idea more formal, we recall the Kavis-Kahan Theorem. Loosely, it states that || u 1l2 x II(L- L' LL')llll2 (23 X5) (we give more formal statement in Lemma 15).
Expanding the entrywise absolute value (L - L=] reveals that its entries can be expressed as
2 |dout [u] E [cboe(()) [e]]l/ /Vn, where dour(u [v] denotes the number of edges incident to e crossing to the opposite community as v. This is unaffected by any increase in the number of edges incident that stay within the same community as v, denoted as [v]. Hence, regardless of how many internal edges we add before sampling what substructures they encourage/create, if we have X < Xg. then we get ||22- uall S. o(1). This immediately implies that U2 is correct classifier on all but an o1) fraction of the vertices.
Entrywise analysis of u2 and NSSBM strong consistency. In order to achieve strong consis- tency, we need that for all sufficiently large, uy is a perfect classifier. Unfortunately, the above argument does not immediately give that. In particular, in the density and spectral gap regimes we consider, the bound of o(1) yielded by the Davis-Kahan theorem is not sufficiently small to di- rectly yield ||u] U2l1 < 1/Vn. Instead, we carry out an entrywise analysis of u2. A general framework for doing is given by Abbe, Fan, Wang, and Zhong [AFW720] and is adapted to the unnormalized and normalized Laplacians by Deng, Ling, and Strohmer [DLS21].
At high level, we adapt the analysis of Deng, Ling. and Strohmer [DLS21] to our setting. We consider the intermediate estimator vector (D A²I) Auž. This is natural choice because we can verify (D - >21) Au = U2. We will see that it is enough to show that this interme- diate estimator correctly classifies all the vertices while satisfying I(D -2
u2)l s ID 1 Aug (again, the absolute value is taken entrywise). With this in mind, taking some entry indexed by v E V and multiplying both sides by d(v} X2 (which we will show is positive with high probability), we see that it is enough to show
dd [u] douc[u]]
(av, un u2)1 S Ka 26ح1
(I)
where a, denotes the v-th row of A. The advantage of this rewrite is that the right hand side can be uniformly bounded, so it is enough to control the left hand side.
To argue about the left hand side of (1), it may be tempting to use the fact that a is Bernoulli random vector and use Bernstein's 's inequality to argue about the sum of rescalings of these Bernoulli random variables. Unfortunately, we cannot do this since U2 and a, are dependent. To resolve this, we use a lcave-one-out trick [AFWZ20; BV24]. We can think of this as leaving out the vertex v corresponding to the entry we want to analyze and sampling the edges incident to the rest of the vertices. The second eigenvector of the resulting L (("), denoted as uz is a very good proxy for u2 and is independent from a.. Hence, we may complete the proof of Theorem 1.
One of our main observations is that although this style of analysis was originally built for low-rank signal matrices [AFWZ20; BV24], it can be adapted to handle the nonhomogeneity inside P1 and Pz. In particular, the nonhomogeneity we permit the NSSBM family may make L look very far from spiked low-rank signal matrix. Furthermore, our entrywise analysis of eigenvectors under perturbations one of the first that we are aware of that moves beyond analyzing low-rank signal matrices or spiked low-rank signal matrices.
7

---

L1
L2
R
L1 Kp. nn-1n/axn/4
p- In/axu/4
a' 1//2x//2
L2 p. p-1n/4xn/4
Kp- 1n/Axn/4
R
1/220/22
p 1//2x//2
Table 1: A for Theorem 3 is defined to have the above block structure.
Extension deterministic clusters. To prove Theorem 2, we start again at (1), An alternate way to upper bound the left hand side is to use the Cauchy-Schwarz inequality. A variant of the theorem gives us control over ||u -uăll while ||a=Il = Vdlu.. The advantage of this is that we get worst-case upper bound on the left hand side of (1) it holds no matter what edges orthogonal to u. are inserted before or after nature samples the crossing edges (which are precisely the internal edges). Combining these and using the fact that the right hand side of (1) is increasing in din[v]] (and increases faster than ||a.||2 = /d(= allows us to complete the proof of Theorem 2.
Inconsistency of normalized spectral bisection. Finally, we describe the family of hard in- stances we use to prove Theorem 3. To motivate this family of instances, recall that by the graph version of Cheeger's 's inequality, the second eigenvalue of L and the corresponding eigenvector can be used to find sparse cut in G. Thus, if we create sparse cuts inside P1 that are sparser than the cut formed by separating P1 and P2, then conceivably the normalized Laplacian's 's second eigenvector may return the new sparser cut.
To make this formal, consider the following graph structure. Let n be a multiple of 4. Let Li consist of indices 1,...,n// n144 Le consist of indices n/4 + I,..., n//2, and R consist of indices n/2 1/2+11. 1, n. Consider the block structure induced by the matrix A E [A] shown in Table
Intuitively, as K gets larger, the cut separating L1 from V \ L1 becomes sparser. From Cheeger's inequality, this witnesses small Ag(C) and therefore the corresponding u2 (C) may return the cut L1, V L1. We formally prove that this is indeed what happens when K is a sufficiently large constant and then Theorem 3 follows.
4 Numerical trials
We programmatically generate synthetic graphs that help illustrate our theoretical findings using the libraries NetworkX 3.3 (BSD 3- 3-Clause license), SciPy 1.13.0 (BSD 3- 3-Clause License), and NumPy 1. 1.26.4 (modified BSD license) [HSS08; 20; HMvdW 20]. We ran all our experiments on a free Google Colab instance with the CPU runtime, and each experiment takes under one hour to run. In this section we focus on setting that allows relating Theorem 1 and Theorem 3, and defer more experiments that investigate both NSSBM and DCM graphs Appendix B.
To put Theorem and Theorem 3 in perspective, we consider graphs generated following the process outlined in the proof of Theorem 3, which gives rise to the following benchmark distribution.
Benchmark distribution. Let be divisible by 4 and let (Pt, P P-2} be a partitioning of V [n] into two equally-sizee subsets. Let { L1, L2} } be a bipartition of P1 such that [ا = |L2l = n/4 and call L P1,
P2 for convenience as the proof of Theorem 3. Then, for some p. P. q E [o. 1] such that S S p. consider the distribution Dp.j.g over graphs G = (V, E) obtained by sampling every edge (u, v) E (L1 x [1) (I2 x L2) independently with probability p. every edge (u, E
(Ia x U [x R) independently with probability p. and every edge (u, v) E L R independently with probability q. One can see that Pp.p.q is in fact in the set NSSBM(nn,.. p. q).
Setup. Let us fix n = 2000, = 24 24g n/n, = 8 logn/n. For varying values of p in the 10 independent draws G from D D.. For each of them, we run spectral bisection (i.e. Algorithm 1) with matrices L, Lsym: Liw. A. Then, we compute the agreement of the bipartition hence obtained (with respect to the planted bisection), that is the fraction of correctly classified vertices. We average the agreement across the t independent draws. The results are shown in the top left plot of Fig. 1. Another natural way to get a bipartition of V from the eigenvector is a sweep cul. In a sweep cut, we sort the entries of and take the vertices corresponding to the smallest n/2 entries be on one side of the bisection and put the remaining on the other side. The average agreement obtained in this other fashion is shown in the bottom left plot of Fig. 1.
range [p, 1]. we sample
8

---

Theoretical framing. As per Theorem 1, we expect unnormalized spectral bisection to achieve exact recovery (i.e. agreement equal to 1) whenever p S Pmax where
(n(p 9) logn)²
Pmax
(2)
72 logg n
is obtained by rearranging the precondition of Theorem 1, ignoring the constants and disregarding
the fact that a should be O(1). On the contrary, the proof of Theorem 3 shows that normalized
spectral bisection misclassifies constant fraction of vertices provided that p/q 2 2 (which our
choice of parameters satisfies) and p 2 Pinr where
Phr 3
In Fig. I, the solid vertical line corresponds to the value of Pihr on the z-axis, and the dashed vertical line corresponds to the value of Pmax the z-axis. In particular, observe that in our setting Ptr < Pmax so there is an interval of values for p where we expect Theorem I and Theorem 3 to apply simultaneously.
Empirical evidence: consistency. One can see from the top left plot in Fig. 1 that the agreement of unnormalized spectral bisection is 100% for all values of p. even beyond Per and Pmax- On the other hand, the agreement of the bipartition obtained from all other matrices (hence including nor- malized spectral bisection) drops below 70% well before the threshold Pthr predicted by Theorem 3. From the right plot in Fig. 1, we see that computing the bipartition by taking a sweep cut of n/2 vertices does not change the results U2 of the unnormalized Laplacian continues to achieve 100% agreement, while for all other matrices the corresponding U2 remains inconsistent.
Empirical evidence: embedding variance. From the setting of the experiment we just illustrated, observe that as we increase p. we expect the subgraph G[L] have increasing volume. As illustrated in Fig. 1, this seems to correlate with decrease in the "variance" of the second eigenvector u2 of the unnormalized Laplacian with respect to the ideal second eigenvector u.z More precisely, we compute the average distance squared of the embedding of a vertex in Un from its ideal embedding uz. i.e. the quantity
1
u2
(4)
This suggests that not only does the second eigenvector of the unnormalized Laplacian remain robust to monotone adversaries, but it actually concentrates more strongly around the ideal embedding ug-
Empirical evidence: example embedding. Let fix the value p Phhr, for which we see in Fig. 3 that all matrices except the unnormalized Laplacian fail to recover the planted bisection. We generate a graph from D Pp.p.go and plot how the vertices are embedded in the real line by the second eigenvector of all the matrices we consider. The result is shown in Fig. 1, where the three horizontal dashed lines, from top to bottom, respectively correspond to the value of 1/ 1/VT.O0 0, 1// vn on the y-axis.
4.1 Related work
Community detection. Community detection has garnered significant attention in theoretical computer science, statistics, and data science. For a general overview of recent progress and related literature, see the survey by Abbe [Abb18]. In what follows, we discuss the works we believe are most related what we study in this paper.
As mentioned in the introduction, perhaps the most fundamental and well-studied model is the sym- metric stochastic block model (SSBM), due to [HLL83]] The celebrated work of Abbe, Bandeira, and Hall [ABH16] gives sharp bounds on the threshold for exact recovery for the SSBM setting. They complement their result by showing that SDP based methods oretic lower bound for the planted bisection problem, even with a monotone adversary [Moi21]. A line of work [AFWZ20; DLS21] demonstrates that natural spectral algorithms achieve exact recov- ery for the SSBM all the way to the information- -hoomation-theoreticc threshold.
achieve the information the-
Generalizations of the symmetric stochastic block model. Since the introduction of SBMs [HLL83), numerous variants have been proposed that are designed to better reflect real-world graph properties. For instance, real-life social networks are likely to contain triangles. To address this, Sankararaman and Baccelli [SB17] introduced spatial stochastic block model, sometimes known as the geometric stochastic block model (GSBM). Other variations were introduced in the works of

---

O-cut
Unnormelized Laplacien
Sym. normalizeed Laplacian Cayn
Agjnne with planted treection
0.0
0.04
0.02
0.02
0.00
0.00
-0.02
-0.02
022
0.6
0.6
1,2
1000
1500
1500
Intracc kaster edge probubility
Swzep bisection
R.W. normalized Laplacia 4yn
Agreemeen with plantee Irsetion
1U
1.6
21.
0.02
2.8
0.00
0.7
1.2
2.6
1.0
0.5
-0.44
Hg
300
1003
1300
2000
0.2
0.9
Largest intrarcluster edge probability& D
Ver Uere
Largest Intrewlttterr edge probasilty F
Figure Top left, bottom left: Agreement with the planted bisection of the bipartition ob- tained from several matrices associated with an input graph generated from distribution in NSSBM(n, p. P.P, P.9) 4) for fixed values of n. p, q and varying values p. In the top left plot, the biparti- tion is the O-cut of the second eigenvector, as in Algorithm 1. In the bottom left plot, the bipartition the sweep cut of the first n1/2 vertices in the second eigenvector. The dashed vertical line corre- sponds to Pmax Pmmax (., (see (2)), and the solid vertical line corresponds to 7tr 7thr(",, P: ④) (see (3)). Top middle, top right, bottom middle: Embedding of the vertices given by the second eigenvector u2 of several matrices associated with a graph sampled from Dp.p.q with Phh Hor- izontal dashed lines, from top to bottom, correspond to /ī, 0, -1 /TV respectively. Bottom right: Variance of the embedding in the second eigenvector uz of the unnormalized Lapla- cian with respect to the ideal eigenvector uzz (see (4)), for input graphs generated from a distribution in NSSBM p. q) with fixed values of n. p, q and varying values of p.
[GPMS18; GMPS19]. Subsequent work studies the performance of spectral algorithms on certain Gaussian Geometric Mixture block models [ABRS20; ABD21; LS24; GNW24).
Studying community detection with a semirandom model approaches this modeling question differ- ently. Rather than implicitly encouraging a particular structure within the clusters like the models just mentioned, semirandom adversary (including the ones we study in this paper) can more di- rectly test the robustness of the algorithm to specially designed substructures.
Semirandom and monotone adversaries. As far as we are aware, Blum and Spencer [BS95] were the first to introduce a semirandom model. Within this model, they studied graph coloring problems. Feige and Kilian [FK01] demonstrated that semidefinite programming methods can ac- curately recover communities up to certain threshold, even in the semi-randon setting. Other problems, such as detecting planted clique [Jer92; Ku95; BHKKMP19], have also been studied in the semi-random model of [FKO1]. J.. In the setting of planted clique, natural spectral algorithm fails against monotone adversaries [MMT20; BKS23]. Monotone adversaries and semirandom models have also been extensively studied for other statistical and algorithmic problems (VA18; KLLST23; GC23; NGLMSY24J, Finally, [SL17] shows that a spectral heuristic due to Boppana [Bop87] is robust under monotone adversary that is allowed to both insert internal edges and delete crossing edges. However, as far as we are aware, this algorithm does not fit in the framework of Algorithm I.
We remark that the models we study in this paper are most closely related to models studied by [MN06] and [MMV12]. In particular, allowing increased internal edge probabilities is analogous to Massart noise in classification problems. and our model with adversarially chosen internal edges can be seen as the same model as that studied [MMV12 12] (although without allowing crossing edge deletions). Finally, note that Cohen-Addad, d' O'Orsi, and Mousavifar [CdM24] give near-linear time algorithm for graph clustering in the model of [MMV12] though they do not explicitly show their algorithm is strongly consistent on instances that are information-thhoreticall theoretically exactly recoverable.
10

---

Acknowledgments. AB was partially supported by the National Science Foundation under Grant Nos. CCF-2008688 and CCF-2047288. NSM was supported by National Science Foundation Graduate Research Fellowship. We thank Avrim Blum and Yury Makarychev for helpful discussions. We thank Nirmit Joshi for pointing us to the reference [DIS221].
References
[Abb18]
Emmanuel Abbe. Community detection and stochastic block models: recent de- velopments. Journal of Machine Learning Research, 18(177):1-86, 2018, arXiv: 1703. 10146 (math.PR) URL: http: //mlr./mrr..///////m org/ hat//papes//// v18/ 166 480 html (cited on pages 2, 9).
[ABH16]
Emmanuel Abbe, Afonso S. Bandeira, and Georgina Hall. Exact recovery in the stochastic block model. IEEE Transactions on Information Theory, 62(1):471-443 [cs.S]] SI] (cited on
2016. DOI: 10. 1109/TIT 2.09/ 2490670. arXiv: 1405. 3267
pages 5, 9, 36).
[ABRS20]
Emmanuel Abbe, Enric Bdix-Adserà, Peter Ralli, and Colin Sandon. Graph pow- ering and spectral robustness. SIAM Journal Mathematics of Data Science, 2(1):132-157, 2020. DOI: 10. 1137 1951121151. arXiv: 1809. 04818 [cs.DS]. URL: https: httd/di.rrggg/ 1rg/10..... 1137 1137/1912557155 (cited on page 10).
[AFW720]
Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector analysis of random matrices with low expected rank. Annals of statis- tics, 48(3):1452, 2020. arXiv: 1709.09565 [math. ST] (cited on pages 2, 4, 5, 9, 23).
[ABD21]
Konstantin Avrachenkov, Andrei Bobu, and Maximilien Dreveton. Higher-order spectral clustering for geometric graphs. Journal of Fourier Analysis and Appli- cations, 27(2):22, March 2021. DOT: 10. 1007 / s00041 021 09825 - 2. arXiv: 2009 11353 .L]. URL:: https : / / doi org/ / 1007 / s00041 021 09825-2 (cited page 10).
[BHKKMP19]
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 Computing, 48(2):687-735, 2019. arXiv: 1604. 03084 [cs (cited on page 10).
[B224]
Abhinav Bhardwaj and Van Vu. Matrix perturbation: davis-kahan in the infinity norm. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Al- gorithms (SODA). Jamuary 2024, pages 880-934. arXiv: 2304.00328 [math. PR] (cited on pages 4, 7).
[BGLMSY24]
Avrim Blum, Meghal Gupta, Gene Li, Naren Sarayu Manoj. Aadirupa Saha, and Yuanyuan Yang. Dueling optimization with monotone adversary. In Proceedings Thirty Fifth Conference on Algorithmic Learning Theory (ALT), February 2024.
arXiv: 2311. 11185 [cs DS] (cited on page 10).
[BS95]
Avrim Blum and Joel Spencer. Coloring random and semi-random k-colorable
graphs Journal of Algorithms, 19(2):204-234 1995. ISSN: 0196-6774, DOI:
https doi. org 10 1006 / jagm 1995 1034. URL: https / www
sciencedirect. com / science article /pti/ 2211//01996674857008444 (cited
on page 10).
[Bop87]
Ravi B. Boppana. Figenvalues and graph bisection: an average-case analysis. In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987),
pages 280-285, 1987. DOI: 10. 1ww./99FFCC.... 1987. 22 (cited on page 10).
[BKS23]
Rares-Darius Buhai, Pravesh K. Kothari, and David Steurer. Algorithms approach- ing the threshold for semi-random planted clique. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 1918- 1926, Orlando, FL., USA. Association for Computing Machinery, 2023. ISBN: 978 9781450399135 arXiv: 2212. 05619 [Cs.DS] (cited on pages 2, 10).
[CSV17]
Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 47-60, Montreal, Canada. Association for Comput- ing Machinery, 2017. ISBN: 978 4550345286. arXiv: 1611. 02315 [Cs.LG] (cited page 2).

---

[CdM24]
Vincent Cohen- Addad, Tommaso d'Orsi, and Aida Mousavifar. A near-linear time approximation algorithm for seyond-worst-cen ternational Conference on Machine Learning, 2024. arXiv: 2406. 04857 [cs .D].. URT.: https:: https://openrevier openreview.ev.e.eee net forum ? dowooouuddddssii M (cited on pages 2, 10).
graph clustering. In Forty-first In-
[DLS21]
Shaofeng Deng, Shuyang Ling, and Thomas Strohmer. Strong consistency, graph laplacians, and the stochastic block model. Journal of Machine Learning Revearch, 22(117):1-44, 2021, arXiv: 2.04.09788 [stat. MML] (cited on pages 2, 4.7,799 9, 11, 27, 35).
[FK01]
Uriel Feige and Joe Kilian, Heuristics for semirandom graph problems. J. Comput. Syst. Sci., 63(4)6639 1711339671,,--- December 2001. ISSN: 0022-0000. DOI: 10. 1006/ cess.
2001 1773. URL: https: / /oii org/10 10. 1006 jcss. 2001 1773 (cited on
pages 5, 10).
[GMPS19]
Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, and Barna Saha. Connec- tivity of Random Annulus Graphs and the Geometric Block Model. In Dimitris Achlioptas and László A. Végh, editors, Approximation, Randomization, and Com- binatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 of Leibniz International Proceedingy in Informatics (LIPlcs), 53:1- 53:23, Dagstuhl, Germany. Schloss Dagstuhl LeibnizzZZnntrum für Informatik, 2019. ISBN: 978- 978-3-95977-125-2 arXiv: 1804.05013 05013 [cs. [D] (cited on page 10). Sainyam Galhotra, Soumyabrata Pal, Arya Mazumdar, and Barna Saha. The geo- metric block model and applications. 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1147-1150, 2018. DOI: 10. 1ww.11109LLARRE ALLERTON 2018 8635938 (cited on page 10).
[GPMS18]
[GC23]
Xing Gao and Yu Cheng. Robust matrix sensing in the semi-random model. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL:
wwtpe/rweieeweeeeeeeeeee wwee/foorumiieeee http:/ooromniiinseeeeeeeeeeee (cited on page 10).
[GNW24]
Julia Gaudio, Xiaochun Niu, and Ermin Wei. Exact community recovery in the geo-
metric shm. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2024, pages 2158-2184 DOT: 10. 1137 111771.77811119779991
78. arXiv: 2307 11196 [cs. SI]. URL: https: //tpp//ppbbb.../ siam org//oi/abs:
10. 1137/1 0tt.///97781111979911199 78 (cited on pages 2, 10).
(HSS08)
Aric Hagberg, Pieter Swart, and Daniel S Chult. Exploring network structure, dy- namics, and function using NetworkX. Technical report, Los Alamos National Lab.(LANI),, Los Alamos, NM (United States), 2008 (cited on page 8).
[HMvd
Charles Harris, K. Jarrod Millman, Stéfan van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiehe, Pearu Peterson, Pierre
Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array pro- gramming with NumPy. Nature, 585(7825):337-362. September 2020. DOr: 10. (038/s41586- 020-2649-2 URL: htttps://don org/ 10. 1038//4458660000 2649-2 (cited on page 8).
[HLL83)
Paul W. Holland, Kathryn Blackmond I Laskey, and Samuel Leinhardt. Stochastic blockmodels: first steps. Social Networks, 5(2):109-137, 1983. ISSN: 0378-8733, DOL: https : // doi. org/ 10. /01///00111111111111111111111111 8733 (83) 9000000002000000 URL: https: // //www. sciencedirect. com/ http///cinnceeeeea /ttp:///ee/p/////7///3333000001 (cited on pages 9).
[Jer92]
Mark Jerrum. Large cliques elude the metropolis process. Random Struct. Algo- rithms, 344):377-360, 1992 DOE: 10. 1002 / RSA 3240030402. URL: https //doi www.///gg...... 100200............ 3240030402 020 (cited on page 10).
[KLLST23]
Jonathan Kelner, Jerry Li, Allen X. Liu, Aaron Sidford, and Kevin Tian. Semi- random sparse recovery in nearly-linear time. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings Thirty Sixth Conference on Learning Theory, vol- ume 195 of Proceedings of Machine Learning Research, pages 2352-2398, PMLR,
12

---

July 2023, arXiv: 2203. 04002 [cs DS]. URL: https: // pttpc//dcccceeesss///oo mlr.
press/v196/xeenerr22a html (cited on pages 2, 10).
[Ku95]
Ludk Kuera. Expected complexity of graph partitioning problems. Discrete Ap- plied Mathemarics, 57(2):193-215 1995. ISSN: 0166-218X. DOr: https : /
doi org / 10 1016 0166 (94 00103 K. URl: https www sciencedirect. com /onineiene/// article / 0t11/06662111944000300 Combi- natorial optimization 1992 (cited on page 10).
[LLV17]
Can M Le, Elizaveta Levina, and Roman Vershynin. Concentration and regular- ization of random graphs. Random Structures & Algorithms, 51(3):538-555 561,, 2017. arXiv: 1506. 00669 [math. PR] (cited on page 17).
[LS24]
Shuangping Li and Tsclil Schramm. Spectral clustering in the gaussian mixture block model, 2024. arXiv: 2305 00979 [stat.ML] (cited on pages 2, 10).
[MMV12]
Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Ap- proximation algorithms for semi-random partitioning problems. In Proceedings of the Porty-Fourth Annual ACM Symposium on Theory of Computing, STOC '12 pages 367-384, New York, New York. USA. Association for Computing Machin- ery, 2012. ISBN: 978 145011531220 12455. 5, 10).
arXiv: 1205. 2234 [cs .D]] (cited on pages 2,
[MN06]
Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statisties, 34(5), October 2006. ISSN: 0090-5364. DOI: 10 1214 / 009053306000000078.. URL: http : / dx doi org / 10 1214 / 0090536060000000788 (cited pages 10).
[MMT20]
Theo McKenzie, Hermish Mehta, and Luca Trevisan. A new algorithm for the robust semi-random independent set problem. In Proceedings of the Thirty-First Annual ACM-SIAM. Symposiun on Discrete Algorithms, SODA '20, pages 738- 746, Salt Lake City, Utah. Society for Industrial and Applied Mathematics, 2020. arXiv: 1808. 03633 DS] (cited on pages 10).
[Moi21]
Ankur Moitra. Semirandom stochastic block models. In Beyond the Worst-Case Analysis of Algorithms. Tim Roughgarden, editor. Cambridge University Press, 2021, pages 212-233. DOL: 10. 1017 9711//8871111817355 014 (cited on pages 2, 9).
[MPW16]
Ankur Moitra, William Perry, and Alexander S. Wein. How robust are re- construction thresholds for community detection? In Proceedings of the Forty- Eighth Annual ACM Symposium on Theory of Computing, STOC 16, pages 828- 841, Cambridge, MA, USA. Association for Computing Machinery, 2016. ISBN: 9781450341325. DOI: 1145 / 2897518 2897573. arXiv: 1511 01473
[cs.DS] URL: https : doi. org/ / 10. 1145 2897518 2897573 (cited on page 2).
[SB17]
Abishek Sankararaman and François Baccelli. Community detection on euclidean random graphs. In 2017 55th 55th Anmual Allerton Conference Communication. Con- trol, and Computing (Allerton), pages 510-517, 2017. DOI: 10. 1109/11LE00RS ALLERTON. 2017. 8262780 (cited page 9).
[SB15]
Purnamrita Sarkar and Peter J. Bickel. Role of normalization in spectral clustering for stochastic blockmodels. The Annals of Statistics, 43(3), June 2015. ISSN: 0090- 188..
5364. DOI: 10. 1211 ao- aos 285. arXiv: 1310. 1495 [stat. ML]. URL: http:
//dx. doi. org/10.000.... 1214/1114441 14144/14-AS1285 (cited on page 6).
[SL17]
Martin R. Schuster and Maciej Liskiewicz. New Abilities and Limitations of Spec- tral Graph Bisection. In Kirk Pruhs and Christian Sohler, editors. 25th Annual Eu- ropean Symposium Algorithms (ESA 2017), volume 87 of Leibniz International Proceedings in Informatics (LJPlcs), 66:1-16: Dagstuhl, Germany. Schloss Dagstuhl Seiibizz-Zentrun für Informatik, 2017. ISBN: 978-3- 31133-39577--999 DOI: 10. 4230 / LIPIcs. ESA 2017 66. URL: https / drops dagstuhl de enti tiet /tc.m/nt/10000//// 4ww0/222000...1.1. ESA. 2017. 66 (cited on page 10).
[Ver18]
Roman Vershynin. High-dimensional probability: An introduction with applica- tions in data science, volume 47. Cambridge university press, 2018 (cited on
page 14).
13

---

[VA18]
Aravindan Vijayaraghavan and Pranjal Awasthi. Clustering semi- mix- tures of Gaussians. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceed- ings of Machine Learning Research, pages 5055-5064. PMLR, July 2018. arXiv: 1711 08841 [cs.DS], DS]. URL: https / proceedings mlr press / v80 / vij vijayaraghavan 8a. html (cited on page 10).
[VGO*20]
Pauli Virtamen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser. Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C Carey, Ihan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Comput- ing in Python. Nature Methods, 17:261-272, 2020. DOE: 10. 1038/ 11111///////----/0 -41992-01- 0686-2 2 (cited on page 8).
[Von07]
Ulrike Von Luxburg. tutorial on spectral clustering. Statistics and computing, 17:395 416, 2007. arXiv: 0711.0189 0189 [cs.DS] (cited on pages 2, 3, 6).
[YCOM24]
Yuepeng Yang, Antares Chen, Lorenzo Orecchia, and Cong Ma. Top-K ranking with a monotone adversary. In Shipra Agrawal and Aaron Roth, editors, Proceed- ings of Thirty Seventh Conference Learning Theory, volume 247 of Proceed- ings of Machine Learning Research, pages 5123-5162. PMLR, July 2024. arXiv: 2402. 07445 [stat.Mi URL: https : proceedings mlr press /v247 yang24b. html (cited on page 2).
A Deferred proofs
In this section, we build the tools we need to prove Theorem 1, Theorem 2, and 3. Through- out, it will be helpful refer to the overview (Section 3) for proof roadmap.
Notation in the proofs. (Section 3). Additionally, for vertex V, let P(v) denote the community that & belongs to.
all proofs, we adopt the notation used in the technical overview
A.1 Concentration inequalities
Our proof strategy for Theorem 1 and Theorem 2 is to appeal to Lemma A.23, which guarantees strong consistency provided that d(e] A2 > din [v] > dout [u], and (a,, uē u2)l S (d [u] dout//])/ /n for all vertices v. Proving that the first two conditions hold is relatively easy. In the setting of Theorem 1, it essentially follows from concentration of the degrees, which is proved in Appendix A.2. In the setting of Theorem 2, it follows from the assumptions of the Theorem. Proving that the third condition holds the main technical challenge.
For all three parts, our proofs rely on several auxiliary concentration results. We prove these in Appendix A.3 and Appendix A.4.
We extensively use the following variants of Bernstein's Inequality, which can be derived from [Ver18, Theorem 2.8.4].
Lemma A.1. Let X En X, where X; 1 with probability ps and X; 0 with probability 1 - Pt and all the X, are independent. Let μ = E [X]. Then, for all t > 0 we have
(-min min
12
31 }
Pr Pr| - 4l < 2exp
4 m 1 (1-pp)
From this, we get the following very useful corollary.
Lemma A.2. Let X = Em Xi where X, = 1 with probability p: and X; = 0 with probability
1 Pt and all the X; are independent. Let μ E [X]. Then, for all > with probability at least
1 we have
X - M1 E
4
(1 - log (2/6) + 4/3 log (2/8).
14

---

A.2 Concentration of degrees
In this Section, we give concentration statements regarding the number of internal vertices incident each vertex and the number of crossing edges incident to each vertex. We then compare these against 22
Lemma A.3. Suppose the crossing edges sampled identically and independently with probability Then, for some universal constant > O, with probability at least we have that
Vo E V, dout [v] -E [oor S C (Vnqlog (7/6) + log (1/6)).
Proof of Lemma A.3. Choose some E V. Consider the random variable doje[u]. Using Lemma A.2, we have that there constant C 0 such that with probability at least 1 6/n one has
|out [o]
[oou [o]] S SC (VAnq/2 log (2n/6) log (2n/b)
Taking union bound over all vertices completes the proof of Lemma A.3.
Note that Lemma A.3 above applies in both settings of Theorem and Theorem 2.
Lemma A.4. Suppose the internal edges are sampled independently with probabilities pow such that p S Pow Then, for some universal constant C. >> 0, with probability 2 1 we have that
Ve V, [dn [dnnee]] SC
Σ
Pow Pow) log (1/6) + log (1/6)
(EP()))(o)
Proof of Lemma A.4. As before, choose some # E Vnd consider the random variable dm[[v] By Lemma A.2, have that there is constant C such that with probability least 1 ö/n one has
[u] - E [dinn(u
[u]]] SC
Σ wEP(v){(o)
Pow Pow log (2n/8) + log (2n/s)
Taking union bound over all vertices completes the proof of Lemma A.4.
Combining the above lemmas, we obtain a lower-bound [in[u] dour[u]. [u]. In particular, the following lemma implies that in the setting of Theorem 1, we have din [v] > dout[u]. This will be required for applying Lemma A.23.
Lemma A.5. There exists universal constant > such that with probability 2 in the same settings as Lemma A.3 and Lemma A.4 and assuming the gap condition in Theorem 1, if 2 then for all we have
n(p 9)
-c (1/8) + log (n/8))
dmlu) dout[u]
2
Proof of Lemma A.S. Let u E V. First, we call Lemma A.3 with failure probability of 5/(2n) to conclude that
dout (v] <
ng
CA. (v
ng
log (2n²/o) + log (2n?
2
2
15

---

Next, we call Lemma A.4 with failure probability of (2() to conclude that
d/ll2] 2
Σ
Pow -AAa
Pew (1 Pow log (2n²/) + log (2n²/)
"EP(v)\(r)
(EP(n))(r)
Σ
Dowe -AA
Σ
Por log (2n²/o) - log (2n²/)
wEP(o)Mot
wEP(O)((U
np - 2CA4
(VT
np 2
log (n²/6) + log (2n²/b)
2 2
where the last line uses the fact that x cv / is increasing in r whenever x 2 c² and > 0. We subtract and conclude the proof of Lemma A.5 by union bound.
The following lemma will be useful for lower-bounding d(v] X2 in Theorem 1.
Lemma A.6. Suppose every crossing edge appears independently with probability 9. Then, with probability 2 1 11-6 8, for all v E V we have
2 S 2vl + (Vnggloo (n/6) + log (n/6))
Proof of Lemma A.6. Observe that with probability least 1 o, dout [w] E [clot [v]]
S
v 22n log(2n/6) + 2 2og((2n/0) for all V by Lemma A.2. Then, for every V have
2
Σ WEP())
dout [m] dout/u]
2
Σ
[our[w]] [dout[ul]]
(E [dout[ [v]] dout
71
n ((P(
2
dour [1c] E (dout(()) + (doue [v]] dout(u) [v]]
WE ((v)
2nq log (2n/a) + 2ng log (2n/8) + llog (2n/6)
< / nq log (n/6) + 10 log (n/8).
Next, by the min-max principle, we have
A S
Σ
(ui[w) u u²(wd')²²
Σ WE P(o)
dout
n
(W.,"))
Combining everything, we get
2 Σ dout [w] 2 (dourlu) + 3/ ng log (w/8) + 10 10 (1/6))
A 2 2
(())())
completing the proof of Lemma A.6.
We can now lower-bound d[u] X2. Note that the following lower bound implies that d(u) X2, as required by Lemma A.23.
Lemma A.7. In the setting of Theorem with probability 2 8, for all v E V, we have d[u] X2 n(p 44.
Proof of Lemma A.7. Recall that the gap condition in Theorem tells us that p and q are such that for universal constant C,
"(p 9) 2 C (Vmpllo (1/6) + log (m/6)
16

---

We have for all sufficiently large (specifically, n 2 N(a, 8) for some N that is a function only of the constant a, and we take 2 1/n that with probability at least 8,
d(v] - X2 dn [v] dour + (2cbouluv A2)
2 din [v] doar [c] - Ca.6 (Vng log (1/6) + log (*/6))
p 9) (CA.5 + CA.o) ( (Vnplog(//)) (1/6) + log (s/6))
2
so insisting
nlp - 9) 2 (CA.5 + CA.e)
( (Vnplog (7/6) log (*/6))
4
gives the condition required to complete the proof of Lemma A.7.
The following technical lemma will be useful for upper-bounding ||u2ll in Lemma A.22.
Lemma A.8. In the setting of Theorem 1, there exists a universal constant C. such that with proba- bility 2 1 for all V have
np + log (7/6)
< 4a C. d(v] - X2
Proof of Lemma A.8. By Lemma A.7, we have with probability 6 that for all V.
n(p 4)
d(u] A2
This gives
np + log (1/6)
4(np log (1/6))
4p
4 4log (*/6) n(p ②)
S4 C.
d(c
X2
n(p ②)
This completes the proof of Lemma A.8.
A.3 Concentration Laplacian and eigenvalue perturbations
For the matrix concentration lemmas, need result due Le, Levina, and Vershynin [LLV We reproduce it below.
Lemma A.9 ([LLV17, Theorem 2.1]). Consider a random graph from the model G(n, {piy Ler d = max.j nPij. For any r 2 1, the following holds with probability at least 1-n for a universal constant C. Consider any subset consisting of 10m /d vertices, and reduce the weights of the edges incident to those vertices in arbitrary way. Let d' be the maximal degree of the resulting gruph. Then, the udjacency matrix A' of the new weighted graph satisfies
|A' - E [Alllop SCr312 [V[+va)
Moreover, the same holds for d' being the maximal E norm of the rows of A'.
Lemma A.10. Let be a Laplacian sampled from the nonhomogeneous Erdös-Rény' model where each edge (i,5) is present independently with probability Pij. Then, there exists universal constant C' such that for all n sufficiently large, with probability 2 1 - 8 for any 8 2 n 10
L --EE LL So 50(1
( max Più log (1/6) + log (1/6)
(()): p1
Proof of Lemma A. Without loss of generality, for all Pt that are 1, reset their probabilities to 0. To see that this valid, L' be Laplacian sampled from this modified distribution and notice that
L' -'- EE E [L]
17

---

By Lemma A.9 and Lemma A.2, we have with probability 2 8/2 that
A - o[ I A 2n max Pij + CA.2
n Immax
max Psg log(8n/5) + log( (8n/6)
I 4000
n mmaxp; + (og($n/6)
< 4000
n. max Pij log(5n/6) + (8n/6)
and by Lemma A.3 and Lemma A.4, have with probability 1 - 6/22 that
[D D-EpDloop
I max |dour [u] [dout [u]]] max d [u] [d [+]] vEV
wEV
s 2max (CA.3. CAah mmaa Pij log (2n/a) + log (2n/a)
Now, observe that with probability 2 1 (following from union bound),
L - [Llllop
|D - - - (A - B[A])llop & [D E [D]llpp + ||A E [A]llop
< 800CA.9CA3 max {CA.3, CAah (1 m P.j log (8n/6) + log ($n/6)
completing the proof of Lemma A.10.
By applying the above lemma, we can show that there a gap between A and X3 which will allow us apply Davis-Kahan style bounds. More concretely, Lemma A.11 and Lemma A. 12, together with Lemma A. show that Ilue uill2 is small. This will be useful for proving that in the context for Theorem the condition (a., u u2)l S (di[v) dow (v)) V in Lemma A.23 is satisfied.
Lemma A.11. In the setting Theorem there exists universal constant C such that the following holds.
Let p and g be such that we have
m(p 9) C (Vnplog (7/6) + log(n/6))
Then, for any 8 2 n n-10, with probability 2 1 5, we have Ag X 2 n(p 4)/4
Proof of Lemma A.II. By Weyl's inequality and Lemma A.10, we have with probability 2 that
n(p - q) CA.10 (Vnplog (M/8) + log((//))
Aa-
13 2 A/ N3 IL
1lp 2
2
Let C 2 4CA.10- Then.
n(p - 4)
2 CA.10
(Vnplog (1/8) + log(1/8))
4
Subtracting completes the proof of Lemma A.11.
Next, we bound |utlllg which we will need in order apply our Davis-Kahae style bound in Lemma A.16. We remark that Lemma A.12 below holds both in the setting of Theorem 1 and of Theorem 2.
Lemma A.12. Suppose each crossing edge in our graph appears independently with probability
There exists universal constant C such that for all sufficiently large, with probability 2 we have
log (1/6)
3/2
(vng + (nq lnglog (1/ + Vlog (1/6)
Euull2 s S
log n
18

---

Proof of Lemma A.12. Observe that |uaz = 2 dout - E [ouue] /vn. By Lemma A.3, for all E V. with probability 2 - 8/2, we have dour[u] v ng/2 + CA.3 (Vnq ni log (2n/6) + log (2n/a)
So, if we let Aout and Aut denote the adjacency matrices consisting only of the crossing edges and the expected value of that, respectively, then invoking Lemma A.9, with probability 2 1 8, we have
|uull2 = ||ouuu E [dout]] ll|
2 2|l(A Ao)))
S 2
Auellop
Vn
vn
log (2/6) S 2Ca9
3/2
(v (v22
nq
VVC33Vng ng ng+ Vnqlog (2n/6) log (2m/6)
log n
completing the proof of Lemma A.12.
Finally, we apply Lemma A.9 in order to bound bound ||a, -a atil2-
Lemma A.13. In the setting of Theorem I, with probability 2 6, we have
log (16)
3/2 (Vnp+ (np
a. a,,l2 SC
(nplog log (1/6)) + Vlog (1/6))
log
Proof of Lemma A.13. We use similar proof to that Lemma A.12. Indeed, invoke Lemma A.9 (observe that we can set Psj for the deterministic internal edges to 0 as they do not affect A - E [A]) and notice that
log (2/6)
3/2
aa, alll2 S |A- - A'loop CA.
(Vnp + (nplog (2n/6)) + vlog (2n/6)
log
where we used d' < n(p + 4)/2 + 2 max (CA.3, CLaB (v (Vrp loploo (2n/8) + log (2n/6) from com- bining Lemma A.3 and Lemma A.4. This completes the proof of Lemma A.13.
A.4 Eigenvector perturbations In this Appendix, give our Buclidean norm eigenvector perturbation bounds. First, we verify that uz is indeed the second eigenvector of L*
Lemma A.14. In the setting of Theorem 1, we have L L'u (L nquž, where L E LL). In the setting of Theorem 2, we have L'u = >2(L Yuž = nqui, where I denotes the Laplacian matrix that agrees with L on all internal edges and agrees with E. [L] on all crossing edges.
Proof of Lemma A. 14. In both cases, one can check that uz is an eigenvector of L* with eigenvalue ng: for any P2 (i.e. uzfu] = 11 without loss of generality), one has
(L'u Vn (ddi[l) (ng/))
Σ
(-1)+
Σ (-9)
14 = =nq u
Vn
W LE
E
By virtue of the above observations, suffices to argue that ng Aa S S (L*)..
In the setting Theorem 1, we claim Xद 2 n(ota) > ng. This is because because Pew 2 p. which implies that if we consider L to be the expected Laplacian for SSBM(n, p. and L to be the expected Laplacian for NSSBM(n, p. P. 4). then L > Li
In the setting of Theorem 2, we have A (L) A2 X2( (L) > ng. by the theorem assumption. Since L' is obtained from Σ by adding the adversarial edges, we have >;(L*) 2 Ax(L) for all i. In particular, have (L*) 2 AL AI + (L) xx) nq, where the last inequality is using
the fact (I. 2 Therefore, ny must be the second eigenvalue of L', completing the proof of
Lemma 1.
19

---

Next, we prove general Davis-Kahan style bound.
Lemma A.15. Let L and L be weighted Laplaciann matrices. Let u2 and U2 be the second eigenvectors of and L, respectively. Then,
( - L)uu2 Aa(L) 12(
| L) 2
min lu2 -22l22 S 2 min
>s((L) X2 22(
Proof of Lemma A.15. One can get this sort of guarantee from variants of the Davis- Kahan theorem, but it is more illuminating to write eigenvalue decomposition and observe it from there. Without loss of generality, assume that (u2, u2) 2 (indeed, otherwise we can always negate U2 if this is not the case). Notice that
[ L22 - = ( --(())) 2z ?
= (A2( - 22((1)) (Ti,, (U)))))² + Σ
(Ar(t) - ->((1)) (u:, u2)
1=3
2 Σ (Aa(C) - >e(Li) (ū,, uz)² (As(I) ->e(1)) 2 (1 (ū2 u2)
1=3
which rearranges to
2
[I. [ L-)
i22 uz) 21 1
da (L) - (L)
(t-Lius) is
Now, if - L)
2 ML( >22( then the condition || -u2ll S V2.
As(L)) -2((L)
trivially satisfied, since ||u2 222122 S /2 2 (u2 uz) I 22. Otherwise, taking the square roots of both sides, we obtain
[I | L)ue
(22 uz) 2
As(L Ae(L)
which gives
[ L)uz Aa( 22(
[ ( L)uz
122 U2 u2l2 = (i12, U2) S 2 -
1
2
Az(L.) >2
Taking the square root of both sides and repeating this argument by exchanging the roles of and yields the statement of Lemma A.15.
This immediately implies the following upper- upper-bound bound on |mu uEllz. We will use it repeatedly, both in Theorem and Theorem
Lemma A.16. We have
E Eu
U2
uTlla < V2.
Aa Ag
Proof. Lemma A.16 immediately follows from Lemma A.15 by letting L L
20

---

Combining with Lemma A. 11 and Lemma A.12, we can now upper- bound U2y ualle in the setting of Theorem
Lemma A.17. In the setting of Theorem 1, there exists universal constant such that, for 8 2 3n 10, 3n-11, with probability 2 1 11-60 6, we have
C
U2 2اll2 S
llg (n/6)
Proof of Lemma A.17. Using Lemma A.1 Lemma A.11 and Lemma A.12, we have
U22 - uالl 400v2CA.11 (vnq (nq log (3x/6)) Vlog (3n/6)
n(p 9)
At this point, it is enough to show that there exists universal constant C such that
Cnlp- q) 2 400 (Vng log (n/8) + (nq) 1/4 (log (*/6)) + log (1/6)
To this, that for any nonnegative real numbers have 2///411/44 S vb Va, which implies 20//21344 < b + vab. Let = nq and log (3n/5), and we get
400V/2CA.12 ( log log (3n/6) (nq) (log (1/6)) log (3n/b)
800022CA.12
Igg (3n/8) log ($m//o)
- 800v2CCA.12
(V log (3n/6) log (3n/6) I Cn(p 4),
where the last inequality follows from the assumption we gave in Theorem 1. We therefore conclude the proof of Lemma A.17.
Next, we prove l norm concentration for the rows of A and for the rows of L in the setting of Theorem We will use this in Lemma A.19, where we will bound U u2
Here u, (r)
denotes the second eigenvector of the leave-one-out Laplacian (())
Lemma A.18. In the setting of Theorem 1, there exists universal constant C such that with prob- ability 2 1 8, for all u E V, we have
||a atll SC C np + V np log (*/6) + log (1/6)
||, [t]]] C mp + v npplog (m/6) + log (1/6)
Proof of Lemma A.18. It is easy to see that
||, E [r,1]l [d(u] E [d[e]]] [oll|+10 l1a a;ll
Let us consider the second term above. By Lemma A.4 and Lemma A.3, we have with probability
2 1- 8/22 that for all v E V
||a, a < ||avl1 + ||at|||
< np
max (CA.3, CAAY (oaaaaVVVnnlia (Vnūlog (4n/8) + log (un//)) np
2np + 2 max (CA.3, CAs) (Vuplog (4n/8) + log (4n/6)
Finally, by Lemma A.3 and Lemma A.4, we have with probability 1 - 5/2 that for all E V,
[d[y] E [d[v]]]
I max (dour(u) [v] [[dou[(u]] [u]] max [d,n[u] wEV
[d [v]]
veV
< 2 max (CA.,, CA.A) (Vnzlog lo (4n/s) + log (4m/6)
Adding everything up means that with probability 2 - 6, for all v E V. we have
||, - E [1.ll, < 2np 4 max (CA., CAs} (v nploo (1n/6) log (1n/6)
which completes the proof of Lemma A.18.
21

---

Having established Lemma A.18, we can now upper-bound [uy" u2
Lemma A.19. In the setting of Theorem for 8 2 2n-9 with probability 2 - ô, for all E V, we have
C (++ V Flog (1/6) / log (1/6)/1)
u2 (1)
22
U2 ol
p
Proof of Lemma A.19. Recall that the gap condition in Theorem means that p and are such that for universal constant C,
<pp 9) 2 (Vnplog (7/6) + log (1/6)
To appeal to Lemma A.15, we need to understand the entries the matrix L L(w), It is easy to that this matrix only has nonzero entries on the diagonal and in the uth row and column. There, the uth row and column of L - ((t) are exactly equal to those of L L". Moreover, the o eth diagonal entry of L (t) is exactly 1 {(V, w) E E} Pew.
Hence, we have
L - (())
212
1/2
n
L - [(0)
2
_22)
w=
1/2
(L- ; +
Σ ((a ((a[[w) - pow)) [22[w]] (a,, [w] Pve)) 22 (v))
1/2
<(L L*),, u2)1
Σ (aa.ww] Pow) uzz [u][w] Pow) u2 (2l))
(114 E [4.]1| + 2 laa a;ll2)
|
(11, E [1.] + ag 0,1|
|222 1222lo0
|22l 3CAA..
np + / //pplo log (2n*/s) + log (2n²/6)
Now, let C > SCA.10- Using Lemma A.10 to understand the concentration of sampling the graph except edges incident to v. along with Weyl's inequality, we have with probability 2 that for all E V and for all sufficiently large,
22) 2 (AS" 13) (A2 25) + (Aī - X5)
2 - CAJoy nollo (2n2/a) + log (2n²/a)
n(p 9) >
n(pp 9)
4
Now, using Lemma A.15, get
(L ((t) uzll2 < |/2lll00
12CA.18 np + /nplog (n/6) + log (n/6)
u2 (v)
u2
(2 d2l
n(p 4)
12CA18 ( /plog (2n²/s) /n + log (2n²/s) /n)
9
completing the proof of Lemma A.19.
22

---

A.5 Leave-one-out and bootstrap
The main goal of this section is to establish an upper-bound on ((a, a U2 - u2) in the setting of Theorem 1. To this end, will need the following concentration inequality from [AFWZ20].
Lemma A.20 (Lemma 7 from [AFWZ20)). Let w E R" and X; Ber(p:). Ler 2 for all i E [n]. Let X E IR" be the vector formed by stacking the X,. Then,
(2 + a a)pm
Pr kw,, X - |
||
- 2exp (-anp)
(1, 1,, /n w
max
[[
Lemma A.21. In the setting of Theorem 1, suppose ar is such that a. [w]] ~ Bernoulli(Pow) and let
p 2 maX.s Pou Pow. With probability
2 6 for 2 for all
V, we have
1|22 log log n
1
(a, oi U2
u22i S C' (np + log (n/6))
+
vn loglogn
Proof of Lemma A.2I. Ideally, one would treat Ug u fixed and then apply Bernstein's 's inequal- ity to argue that the sum of centered Bernoulli random variables as written above concentrates well. Unfortunately, since u2 depends a a cannot express this inner product as the sum of independent random variables.
To resolve this, we use the leave-one-out method. Let u² be the second eigenvector of the leave- onc-out Laplacian ((t) of A ("), where A (") is chosen to agree with A everywhere except for the uth row and uth column. The oth row and oth column of A (e) are replaced with those of A Now, ag does not depend on L (#) and therefore u
We therefore write
(a, a; u2 u S a2
ayg u2 - U1
-u
+ a, a (n) - -n²)
- | atll2
u22
(v)
u2
2
+ | (a. a, uu (0)
< | atll2
CA.19D
||2 + (a. a u2 (0)
p
To bound the rightmost term of the RHS, we use Lemma 7 of [AFWZ20], reproduced in Lemma A.20. In that, let w == u - uz. Let a up log (20n/6) that 2 (annp) < 6/(10n). Note that for the deterministic entries, have a,, a = 1 0, in Lemma A.20, we
set X., ~ (e) for these entries. Now, by Lemma A.20, with probability 2 5/n, we have
2np log 20m
Kul"" un a. a:)l
||211
(5)
/n // 1
max
1,
Let us first bound || 1oo = |
(v)
U
We write
20
u2
(v)
U
U2
(1)
u2
+ U22 uillo
(6)
00
(0)
u2
||u2lloo +||u51 llo
(7)
2
S max Ca.io(a, 8) ||0l Vn
(8)
In what follows, we omit the arguments a and d in mentions CA.19. Next, using Lemma A.17, the triangle inequality, and 8 > 1/n², 3 we have
||0||2
u2 (v)
< 1CA.91lu2l1 + 4CAA.17
Vlog
23

---

(0) w2
us
We now have two cases based on the value of vn.
Case is too "flat."
Let us first handle the case where
vn.
u2
(0)
u2
log n.
u2
22
We plug this into (5) and get
K u2 (0) uz au a;)
S
2np + log
20n
||
/
max log
1|wll2
np + log (20m/6)
1
<
4-
1112ll0
+ Vn
log log
where the last inequality follows from (8). Case 2 - w is "flat." We now assume
(v)
v n
U2
U
S
log
(e)
u2
U2
We can easily check that the function
max (1, log
increasing, so its maximum will be attained at the largest value of x in the domain. Let /n ||/l ||/||2 and write
2np log
20n
|| |o
/nllw/ll..
max
1, log
||
2np log
(220L
n
| 1|
/Tallwo |
1 10112 vn
max
1,,
2np log
log n
w l
log log n
2np log
20m
logn
1
CA.19
120 luzloo
log log n
n
llg (20m²/)
2np + log
20
log n
2npo + log
(2)))
= CA.19
|
log log
v log log
All of this tells us that
Ka.- a un (v)
uz)
< 4CA.19 (np log (20n/))
||
log log
vn log logn
It remains to handle the term
aa aillz ||2021100
Indeed, using Lemma A. A.13, we have with probability 2 1 - that
log (20m//) logn
3/2
|a -ail2 ||u2|loo S CA.13
v ||
24

---

Combining everything tells us that
olog (20m/6) 3/2
Ka, 0, u2 uz)1 - 3.1
Vnp. np ||22ll
log
|
+ 4CA.19 (np + log (20m/6))
+ vn log log
log logn
||wellas
S C (np + log (20m/a))
+
log log
vn log log
Taking a union bound over all concludes the proof of Lemma A.21.
Finally, we establish an upper-bound on |/22 This will be used repeatedly in the proof of Theo- rem 1.
Lemma A.22. In the same setting as Theorem 1, with probability 2 for 8 2 10n2, we have for some constant C(a, 8) that
C(a,8)
U2
Vn
Proof of Lemma A.22. First, observe that
(D - A)u2 = A2
which means that
(D (D-121) Au u2
By Lemma A.7, with probability 2 1 - 8, for all v V we have
d(u) - A n(p 9)
Combining with Lemma A.6, we have
din [u] dout [v]
2dout [v]
A2
=1
dip [0] dout [2] + (2dout [0] - A22)
d [0]
douel [b] + (2dout [u] - Az)
CΛ.6
V/nq loglog (10m/6) + log (10m/))
< 1 +
d [+]
- dout [v] + (2dout (1) A22
4CA.8
(Vig log (10m/8) + log (10n/6)
< 1+
S S
n(p 9)
for some constant C' > where the penultimate line follows from Lemma A.7 and the last line follows from the gap assumption in Theorem 1. Furthermore, by Lemma A.8 and Lemma A.17, we have with probability 2 1 that for all v E
(a,, u, u2)l
DVn d(u) A2 Vlog (10n/6)
CA.17
Cas((a) CA.7 n log (10n/8)
d|u] - X2
25

---

Now, using Lemma A.8 (and using Lemma A.7 to ensure that d - X2 > 0 0 all v E V), we have
U22l
(D
X²1)
Aug
(D A21)
Au
(D 121) Auj + (D - A21)
Aug
< D A21)
Aug
+
(D x Al uz)
la., U22)
(a,, u -22)
max
max 15o5"
d/u] A2
d/u) - A2
1
|dnn [0] dour [1|]
(( Ug U2)
max
max 1se5n
V
ISuSn
d(u) X2
d( X2
C
u2)1 (a. a, u2
|a ui u2)l
Vn
Isusa
d(v] x2
max 1se5a
dlo
A2
C
CA.21 (np + log (10m/6))
|
CA.s(a) CA.17
vn
d'u] X2
V n
log Doglogn
(1log(10n8))
C
(
U22ll
+ CA.s(a)) CA17
+ CA.11 Cas(a)
vn
Vn log
log log
Vn (10n/6)
Note that any large enough
CA.21 CAs((a) /uullac <
||22|100
log log n
2
Thus, rearranging and solving for l| yields
C
(vrloglogm)
+ Crs(a) CA.17 Vnlog (10n/8)
u22lo0 S 2
+ CAn Cas(a).
vn
completing the proof of Lemma A.22.
A.6 Strong consistency of unnormalized spectral bisection
In this section, prove our main positive results Theorem and Theorem It will be helpful to recall the proof sketches given in Section 3 while reading this section.
At high level, the proof plan is as follows.
1. We first establish a sufficient condition for a particular vertex to be classified cor- rectly. We can think of this as simultaneously showing that the intermediate estima- tor (D - A²1) Auu strongly consistent and that the corresponding "noise" term (D (D- Auu U2) is lower-order term in comparison to this. For more formal way to see this, see Lemma A.23.
2. For the proof of Theorem 1, the main technical challenge in showing that the noise term above is small amounts to analyzing the random quantity Ka,, u³ u2)l This is where we will have use the leave-one-out method decouple the dependence between a, and U2 The relevant lemmas for the leave-one-on out analysis are Lemma A.21 and Lemma A.22.
3. Finally, for the proof of Theorem 2, we again appeal to Lemma A.23 but use a different approach to show that the noise term is small.
A.6.1 A sufficient condition for exact recovery and proof
The main result of this subsection is Lemma A.23, which gives general condition under which particular vertex will be classified correctly. The proofs of Theorem and Theorem will follow by invoking Lemma A.23. We remark that the point of this lemma is mostly conceptual; the crux of the analysis lies in establishing that these conditions are satisfied our models.
Lemma A.23. Let E V be some vertex. If d[wcc A2 > for all E V, din[v]] > doue [v], and (a., u. - u2)1 S (din[v] dou (v])/ /n, then sign (uz(v)) = sign (ug(u)), ie., u2 correctly classifies vertex
26

---

The goal of the rest of this section is to prove Lemma A.23. Our approach is to study the intermediate estimator
D -211 Auj.
At a high level, our goal is to show that this correctly classifies all the vertices with high probability and also is very close to u2 in fe norm with high probability. Deng, Ling, and Strohmer [DLSS2] used this intermediate estimator to prove the strong consistency of unnormalized spectral bisection for (BM(n, P, q) instances.
Next, we show that this estimator is consistent and prove Lemma A.23.
Proof of Lemma A.23. Observe that
U2 (D X2I)
Aug (D 1--12I)- ( u2)
Without loss of generality, suppose P1. In partieular, this means that uz uz(r] = 1/V7. Our goal is to show that uz[e] > 0. And, as per the above, this means that it is enough to show that
(D
Aug
[w] N (D- x21)
A ( uz) [e].
or equivalently, using the fact that d(u)
A2 > 0,
(a., U 2 aa, u2)
where ag denotes the e-th row of A. To see that the above holds, use the fact that we know that din [u] dour(() [o] > O, which gives
din doue [u]
(awy uz))
2 (av, un u2)1 2 (av: u.z U22
/n
This is exactly what we needed, and we conclude the proof of Lemma A.23.
A.7 Proofs of main results
At this point, we are ready prove our main results.
A.7.1 Nonhomogeneous symmetric stochastic block model (Proof of Theorem 1) We are finally ready to prove Theorem 1. For convenience, we reproduce its statement here.
Theorem 1. Let p. P. q be probabilities such that q < p S P and such that a = pp - q) is an arbitrary constant. Let D E NNSSBM(n, p.P. g). Let n 2 N(a) where the function N(a) only depends on a. There exists universal constant C > such that if
n(p q) 2 C (Vnplogn + log
(gap condition)
then unnormalized spectral bisection is strongly consistent on D.
Proof of Theorem 1. As mentioned in Section we actually prove a slightly stronger statement we will allow the adversary to set at most np/ log log of the Pew to per vertex (in other words, the adversary can commit at most npp log log n edges per vertex that are guaranteed appear in the final graph).
Our plan is apply Lemma A.23. In order do so, start with showing that for all v, have d (u] > [out[w]. By Lemma A.5, with probability 2 1 - ó, we have for all v E V that
dil [v] - dour[v] n(p 9) CA.s (Vnplog (*/6) + log (1/6)) 0.
2
Additionally, by Lemma A.7, we have for all v that d(p] X2-
The final item we need is to show that for all v E V, we have (ar, un - u2)l S (a.. uz}l. Observe that
(a,, uz - -22) I (ay, uz u2)) + ka - a uz -22)1
27

---

where a denotes the v-th row of E [A]. We handle the terms one at time. First, note that by Lemma A.11, with probability 2 have
(p 9)
A X
Now, let E == L E [L), and let ar[rand] E RRV correspond to the vector that entrywise agrees with a wherever a, is not 1 and is zero elsewhere. This corresponds the edges incident to o that will be sampled randomly from the distribution over graphs. This means that for all n 2 (6) and choosing 8 1/(10n), we have
v2 Eu
[[t] un u2)1 - ||a]rand]]l
(Lemma A.16)
Ag x
40v2CA.11 (yng + (nq log vlogn) (Lemmas A.11 and A.12)
< Pvn-
n(p ②)
1000C
(gap in Theorem I)
Vol log
To handle the oblivious insertions, let daet E RRV denote the degree vector that counts the number of deterministic edges inserted incident v, for all V. Under this notation, we have
np
np u2
(a, a [rand], un u2)l S ddet/o] || willox
V loglog
n
log log
where the last inequality follows from using
U2
u ooo I
U2
+ ||
oo Combining yields
np vn log log n
np u22 Ila.
(at, un u2)l S C²
log log n
for some constant C' 0. Now, notice that for all sufficiently large. ka, a un u2)
| loo
1
< CA.21 (np + log (1/6))
+
(Lemma A.21)
log log n (a,6) vn
/n log log
< CA.21 (nOp + log (n/6))
(Lemma A.22)
log log
vn logn
< Ci(a,)) (np + log (n/6)
Volog log
Adding yields for n 2 N(a, 8),
(a,, u² - -2z) < |a un - u2) + (a, - a; us uz)
C2 C2 8) (np log (v/6)
/n log log
n(p - 4)
Ca.s (Vnploog (n/8) + log (11/))
(gap condition)
Vni
2
din [w]
dout(u) [u]
(a,, un)l,
which means satisfy the conditions required by Lemma A.23. Taking union bound over all our (constantly many) probabilistic statements, setting 5 = @(1/n), and rescaling completes the proof of Theorem 1.
D
A.7.2 Deterministic clusters model
For convenience, we reproduce the statement of Theorem 2 here.
28

---

Theorem 2. Let be a probability and din be an integer, and let D E DCM(n, dins q). For G ~ D, let L denote the expectation of L after step (2) but before step (3) in Model 2. There exists constants C1, C2,C2,CO C3 > such that for all n sufficiently large, if
din 2 2C1 (2 + +Vn)
and >a(L) - >2( 2 vn C2nq + Cs (Vnqlogn + logn)
then unnormalized spectral bisection is strongly consistent on DD
Proof of Theorem 2. In this proof, let L* be the Laplacian matrix that agrees with L on all internal edges and agrees with E [L] on all crossing edges. Let L (cros) denote the Laplacian matrix corr-- sponding to the cross edges, so we can write L = L. L (eros)) - -E (eres))] Although L' & E [L] due to the adaptive adversary, by Lemma A.14, we still have L'u X2u1 nguz-. Moreover, (L L' L is the vector whose entries are of the form 2(d - E [doue (v]])/ vn. Thus, we will
be able to apply Lemma A.16 and Lemma A. later on. Finally, observe that X >,(L)) > xL( for
all i 2 3 and (L) (2() = nq. Thus, one can use the spectral gap Aa(L) - (L) to reason about A3 A/-
Let 2 1/(1. We will apply Lemma A.23 to get strong consistency. First, let us verify that d[u] > A for all v. Applying Lemma A.10 the matrix L (emes)) gives
LL 1'
|| (cros))
E [ (cross)
CA.10 (Vng log (*/6) + log(n/8))
Thus, using Weyl's inequality, for > (0)), we have
dlu] - 2 2 dm [r] - X5 - [L - 10
C1 nd C1 v nq CA.10 (Vng log (w/6) log(n/8)) 0.
Next, verify that [ dour|u] for all v. By Lemma A.3, with probability 1 6, for all e E V, we have
dout [b]
n2
s CA.
(Vng (v/6) + log (1/6))
2
So for n > N(8), we obtain
din [v] - [ouel 2 C1 nQ
+ Ci
Civn
nQ
CA.a (Vng (7/6) + log (1//)) > 0.
2
2
Here, the last inequality we used the fact that v nq /nqloo log (1/8) S max log(n/////// (n/5)) Finally, we need to show that for all v E V,
Ka., us uz) S (ap, الحس = dnn [u] doue(y) [u]
vn
By Cauchy-Schward have
Kav; uz - u2)س < ||a 1l2 1/ - u2l12 -02l-u2
v din(v) + dout [u] 1/ - u2 122122
Thus, is enough show that for all u E V we get
vn [ uellz S dnl[c] dout [v]
Vd
[/] dout
Observe that the RHS above is decreasing function in dout(v) [v] and an increasing function in dha [u] Now, by Lemma A.16 and Lemma A.1 we have
6CA.IV7 (vnq + (ng log (1/8)) + /log (a/8)
/n Eug
Vn | uall2 <
1g Ag
AAg A01
We now do casework on the value of
29

---

Case 1: S. log (n/6) /n. Carrying on from (9) and applying Lemma A.10 (we can set Pij for the deterministic internal edges they do affect L all 2 (6) we have
E LJ) along with Weyl's inequality, for
18C
TO log (1/8)
18C 1. log (7/6)
Vūllus, uzl12
A3
25
vn 3 log (7/5)
din [0] dout
Co (n/8) <
V din [u] + dout(u]
as required. Here the last inequality follows using the fact that din[v] 2
Ci
ng
Vn)
and
dout [u] s mq + A.s. log(n/6).
2 Case 2: log (1/6) /n S q.
Similar to the previous case, we get
18CA.12V n
18CA.12V n
/ -22ll2 S
(10)
Ag -
Vn+ (C2 2C
S 18CA.12 max
VT4, - 2cA
(11)
Additionally, we can use the conclusion of Lemma A.3 to write with probability 2 for all E V and 2 (6) that
d
dout[v]
+ Civa
(12)
din + dout 11)
V(C//222CA++ 1/2)mg
C/2-2Cmn 1/2
max [vng
(13)
/ + 1/2
From this, it is clear that one can choose constants C₁ and C2 such that (11) is at most (13). Taking a union bound over all our (constantly many) probabilistic statements, setting = (1/nn). and rescaling completes the proof of Theorem 2.
A.8 Inconsistency of normalized spectral bisection
In this section, design family of problem instances which unnormalized spectral bisection is strongly consistent whereas normalized spectral bisection is inconsistent. Specifically, our goal is to prove Theorem 3.
Theorem 3. For all n sufficiently large, there exists a nonhomogeneous stochastic block model such that unnormalized spectral bisection strongly consistent whereas normalized spectral bisection (both symmetric and (adomm-wakk) incurs misclassification rate of at least 24% with probability 1 1/n.
A.8.1
The nested block example
We first state the family of instances which we will prove our inconsistency results. Let n be multiple 4. Let L1 consist of indices 1, 1,...,n/44, n//4 La consist indices n/4 + 1,...,71/2 and consist of indices n/2 ,,.
As mentioned in Section 3, consider the following block structure determined by the A written below, where g < p and K 2 3p/q.
L1 Kp- 1 1n/axn/4
L2 p. 1n/4xn/4
R
L1
a 1n/2xn/2 Kp 1n/Axn/1
La p. 1n/xn/11
R
Ln/2xn/2
p 1n/2xn/2
Table 2: A is defined to have the above block structure.
will draw our instances from the nonhomogeneous stochastic block model according to the probabilities prescribed above. Note that within the two clusters L L1 U L2 and R, each edge
30

---

appears with probability at least Moreover, each edge in L x R appears with probability exactly q. However, there are also two subcommunities L1 and L2 that appear within L. Furthermore, observe that unnormalized spectral bisection is consistent on this family of examples with probability 1/n by Theorem 1.
A.8.2 Technical lemmas We next show some technical statements that we will need later in the proof of Theorem 3.
Lemma A.24. Let M E R Then,
| max [M +
mmax [M[]]]]
inj
Proof of Lemma A.24. For matrix E R it is easy to check that
S N
S max N
op
Next, let diag (M) denote the matrix that agrees with M on the diagonal and is elsewhere. Notice that
o < diag (M) + ||M - diag (M)llop
max
M + mmx [M]][]
iSk
completing the proof Lemma A.24.
Lemma A.25. Let Eg be a constant where S Ex < x. Let By be defined similarly. The function f(z, y) defined as
[(x,8) = -x--/V11 Ey V
is decreasing in and y-
Proof of Lemma A.25. It is enough to just check the inequality for x. We take the derivative of [(, y) with respect to æ and get
2 Ex--e,)3/2(0 k2)2/2 +
0.
22222/1/2
where the inequality follows from observing 0 < x Ex I x and similarly for y. This completes the proof of Lemma A.25.
A.8.3 Proof of Theorem 3 First, we construct L*
Lemma A.26. Let L = (D*) 112 (D*)-1/2 structure.
(D*)-1/2
Then, I L' has the following block
L
La
R
L1
Kp
1/4xn/41
1/4x//4
to)
1//2X//2
(. KJ1 +9) (p+t))
L
1n/4xn/4
1n/4xn/4
[q)
R
(- (p
Kel +g) (p+t))
1n/2xn/2
((ppo Ln/2xn/2
Proof of Lemma A.26. It is easy to see that for any v E L, we have d' for any E R, we have d' [v] = (p + q). Lemma A.26 follows by noting that every element of I I- C* is of the form aj [j/ d b..
[v]
(p-
K+1 + +g) and
Next, analyze the cigenvalues and eigenvectors of L'
31

---

Lemma A.27. Up to normalization and sign, the eigenvector-cigemaate pairs of L correspond- ing to the nonzero eigenvalues of L are
(Ai, uii
(1, In/4 $ 1o/4
@ 4+ 1n/4 E y 1n/41)
(K 1)p
(Ag, u5)) =
[[In/ ① 1/4 + On/4 @ 0n/4]
2 (pp K+1
+q)
2
1
K+1
) [nn/a 1 1n/4 y- 1//4 1y y- 1njal)
(Ag, ug) = -11+ ppq
p(K + 1) + 2q
where y4 and y- are chosen according to the formulas
2(p + 9)
p(K + 11 + 24
U+ V p(K 1)+ 2q
2(p +
Moreover, we have X1 > 23 > \1 > 0 and
p²(K + +3) + 4pg
\ 13 p²(K 3) 4pq + 2q²
Proof of Lemma A.27. As can see from Lemma A.26. I 1--- L- is matrix whose rank is at most 3, since it can be constructed by carefully repeating 3 distinct column vectors. Thus, it can have at most 3 nonzero eigenvalues. In what follows, consider the case where K <>> 1 so that there exactly= 3 nonzero eigenvalues.
The next step is to confirm that the stated eigenvalue-eigenvecoor pairs are in fact valid. We begin with ui. Every entry in the first n/2 entries of (I )+ can be expressed as
2(pto) q P(K+1)+2g
Kp
n
p
4
R 2
(p-
K+1
+
4
n
K+1
1)
2
(p. K+1 + 2) 2 (p
2
2
V
2(p+o)
(K + 1)p
9
p(K +)+22
(K + 1)p
Mk+1y+22
(K + 1)p + 2q
(p.
K+1 + (p+ 2
(K + 1)p + 24
(p
K+1 + 4) 2
(K + 1)p
29
+
= 1,
(K + 1)p + 2q
KK 1)y -2g
and every entry in the second n/2 entries of (I - L* )) can be expressed as
n 2
n
P
2(p + 9)
K+1 4) 3 (p+g) (p.
2
n
2
(p+
V p((K + 1) + 2g
q
p
2(p 9)
( K+1 + (p +4)
(p+ V
p(K + 1) + 29
1
+p. +
V(D
K+1 2
+ 9) (p ()+4) 4)
V (p.
K-1
2 + (p+g)
vp
2(p + p(K + 1) 22
y/+
2 +
For Uz, we can use the block structure and easily verify
(I L))
n
(K 1)p
[In/ @
nn/a @ 0n/1 @ On/s] = Auug.
4
(p
K + q)
32

---

We now address uz. The first n entries of (I )u3 are
p(k +(K+1)+2g 2(p+o)
n
Kp
n
p
+ n
q
4 2 (p.
K+1
9)
4 2
(p-
K+1
q)
2
11
(p.
K+1 2
+ 9)
3/2 (p + q)
(K + 1)p
q V ptq
(K + 1)p
q
+
X3.
(K + 1)p + 2q
VD + 9
(K + 1ip + 24
p + 9
and the second n12 entries of (I - L* )ug are
12 2
q
p
p(K 1) + 29
K+1 (p- 2
q)
-pp+ ②)
2 2 (p + 9)
2(p + 9)
V 2
q
P
p(K + 1) + +29
V(p. K+1 + +2) (p ())
(x+
2(p +
p(K+ + 1) + 2q 2(p + g)
-24
P
+
= y . Xz3-
p(K + 1) + 24
p +
Finally, it remains to check that 1 > X/ > \/ > 0. The fact that X < easily follows from using
p + q > 0. To prepare to bound \; >/. we first use 2 to establish
p² - pq + 29 = plp q) + 2q 2 2g
This implies
24²² 2 3p² p + 29² = 2p² + (p² pq + 24 2 2p² + 24,,
which rearranges
+1 PM
2 (K +3) + 4pg + 20²
Next, we write
(p K+1 + g) ) 2
(K-11) 1)p
p (((1+D)))))))
1 + K +
2 Xg
-1+D
p(K + 1) + 2q
P
2p
p22( + 1) 2pq + 2pp 2pg
p p+g 9
p(K 1) + 24
(p + ()(p(K + +1) +24)
p²(K + 3) + 4pq
1²(K + 3) 4pq
=1 pK + 1) + PK(K + 3) + 2g²
1
>> 0.
p²(K + 3) + 4pq 24
2q²
Finally, to show Xg > 0, we write
P
+ p(K + 1)
2p p+4
\₂ 1- p
> 1,
p(K + 1) + 2q
which allows us to complete the proof of Lemma A.27.
Next, we argue that studying L*, which is formed by taking into account the weighted self-loops, gives us an understanding that is not too far from that of C; which is formed by setting P.v = 0 for all E V.
Lemma A.28. Let P be the diagonal matrix where P Plu, v] = Pen- Lel L. be the normalized Laplacian of the graph formed by A P.. Then, we have
6K
| - Cap opp n 2
33

---

Proof of Lemma A.28. Recall L = D*= - A². Let D be defined analogously to Ca Observe that
we have
L' = (D') 1 L' (D") ) 1/2
S = (D L' (D (Di))-12 -1/2
From this, we see that writing down the wtt entry of the difference gives
(A - [r) [" w|
Vdd Pev (d' [w] Paww)
d 10 d w
This resolves to different forms based on whether = w. When = w, evaluating the formula gives
(Ch - [u, [1,
d' [2] Pov
d' Dve
Pve
d' [v] Pvo
d'lu]
d' [u]
When * w, we apply Lemma A.25 and get
1
( (v, = Pew
Vid - (dt
Pww)
v d [u]
1
4K
S Kp
np/2 -p np/22
ni 2n
Using this analysis and applying Lemma A.24 gives
|| - L 1' S max vVV
Pev
max Pros
dt
uF
(dtlo) Pou) (d' [w] Pww)
v [t [oj
2K
+ max Pew V
(d+ (0) Pov) [w]
Pwo
(dl
2K
4K
6K
7
T1 2
1 2"
completing the proof of Lemma A.28.
This gives Lemma A.29, which means can use uz suitable proxy for sign (ua(Ch))
Lemma A.29. There exists constant C(a,, K) depending on a and K such that we have
C(a, K)
(uz(Ch)) u 1l.o
n
This implies that for all n sufficiently large, we have sign (u2(C,)) = sign (uz).
Proof of Lemma A.29. By Lemma A.27, Weyl's inequality, and Lemma A.28, we know that for all sufficiently large,
A1 As \a()))) (2) x3) + (Aī -s((a))))
p² + 4pq
CA.28 2 (i K).
p + 3) + 4pg + 2q²
n
Combining this with Lemma A.28 again, the Davis-Kahan inequality tells us that
|| uzll S || -1l12 S C2(a, K)
n and then using the fact that | 1//n (arising from Lemma A.27) completes the proof of Lemma A.29,
We are now ready to prove the inconsistency of normalized spectral bisection on the nested block examples.
34

---

Proof of Theorem 3. Let G be graph drawn from the nested block example. We choose and such that p 2 logn/n and p/q
2 2 where is some constant and such that p and q both satisfy the conditions of Theorem 1. Let K 2 3x. Observe that the true communities are 7. and R. We will show that bisection based on 22 I L (corresponding to the eigenvector associated with the second smallest eigenvalue of L) will attain large misclassification on our calculation in Lemma A.27, we expect that u2 will output a bisection that places L1 and L2 into separate clusters. On the other hand, by Theorem I, for all large enough, the unnormalized spectral bisection algorithm will be strongly consistent.
rate. In particular, based
First, observe that it is enough to prove the inconsistency result just for the symmetric normalized Laplacian. Indeed, observe that if u2 is an eigenvector of I L D-1/2AD-11/ then we have D D-D---AD (A)2u)/
AzD-1/2uu =
which shows that D D-1/2u, must be the eigenvector of the random- waalk normalized Laplacian I D A corresponding to eigenvalue Ag. Since D is positive diagonal matrix, it does not change the signs of ug and therefore the output of the normalized spectral bisection algorithm is the same.
Our general approach to prove the inconsistency is to use the Davis-Kahan Theorem, a bound on ||C- lop and bound on the gap A/2 A3. Let dunin be the minimum degree of the graph given by adjacency matrix A and let dinin be the minimum weighted degree of the graph given by the adjacency matrix A First, using [DLS21, Theorem 3. 3.1J, we have with probability 1 - n for some constant 2 and constants ((r) and C' (the latter of which does not depend on r)) for all sufficiently large.
||c - Ghllop I C(r) (n (a Pij) 5/2
min (dmin: diaaa }
C(r) (n Kp)
min nn(p +333 4) C. /vpppp log
/)/3
C1 (((7)))k3/<pp)3)) Ci(r,a)55/2
(np)*
Vap
Next, we invoke Lemma A.28 to write
de(Cir) du (A₂ - )1) (Ag >s) + (A2(Cr)) -x))
p K + 3) + 4pg
C2(r.a) CA.28 2 Cy(a,)),
p2(K + 3) + 4p4 + 2q²
Vap
n
where the last line denotes positive constant depending on g and K (this constant will always be positive for sufficiently large n. as we showed that >₁ X/ > Lemma A.27). Putting everything together, we get by the
theorem that some signing of u2 satisfies
C2(r) S Ca(r,a, K) U22 - u2( S min (lA2(C Asl 1 X2( S K)
[ 2 llop
/mp Now, consider the subset of coordinates of u2 belonging L1. Suppose m of these coordinates do not agree in sign with uzz To maximize m, each of these coordinates in u2 should be 0, so using this reasoning and applying Lemma A.29 means the total E2 error can be bounded (using Lemma A.28)
as
2
1
CA.28
I u2 u2(h111 Ca(r, K)² K²² npp
1/2
This means the number of coordinates m on which u2 and un disagree on is at most n (r,r,,, K)²
2np
and therefore the misclassificattin rate of u2 with respect to the true labeling induced by L and R must be least
n- C-Cs K2)
1
ar,
2np
4
2mp
Since p 2 loggn// n/n, this completes the proof of Theorem 3.
35

---

p= 0.5
p=
1.0
1.0
Intra-cluster edge probability
0.4
Intra-clan cluster edge probability
0.4
0.8
0.8
0.6
0.6
0.2
0.4
0.4
0.1
0.2
0.1
0.2
0.0
0.0
0.0
0.1
0.2
0.3
0.4
0.0
0.1
0.2
0.3
0.4
Inter-cluster edge probability
Inter-cluster edge probability
Figure 2: Agreement with the planted bisection of the bipartition obtained from unnormalized spec- tral bisection, for graphs generated from a distribution in NSSBM(n, p, P, q) for fixed values of n, p and varying values of p q. The left plot uses curves plot the function pthr(4) (see (14)), and the dashed red curves plot the function Pinfo (4)
1/2, the right plot uses = 1. The solid
(see (15)).
B Additional experiments
In this section, we show more numerical trials that complement those discussed in Section 4.
B.1 Varying edge probabilities in NSSBM
In Section 4, investigated the behavior of an NSSBM model by fixing the values of p, q and varying the largest edge probability p. Here, we take an alternative approach, and instead fix p and vary the values of p and g.
Setup. Let us fix n = 2000, p E (1/2,1). For varying p: g in the range [1/n, 9/20) such that p q. sample t = independent draws G' from the same benchmark distribution D p.p.a used in Section 4. For each of them, we compute the agreement of the bipartition obtained by unnormalized spectral bisection with respect to the planted bisection. For each (p, g), plot the average agreement across the independent draws. The results are shown Fig. where in the left and right plot these plots, where p S artificially set to O.
the experiments with p 1/2 and
respectively. The lower diagonal of
Theoretical framing. According to Theorem 1, fixing the value of p E (1/2,1), 1}, we obtain that unnormalized spectral bisection achieves exact recovery provided that for E [1/m, 9/20] one has p 2 (thr(g) where
v log
VPlog
(g)
(14)
obtained by rearranging the precondition of Theorem ignoring the constants, and disregarding the fact that a should be O(1). The solid red curve Fig. plots (q) as a function of q. For comparison, the coormation-thhoreet threshold for SSBM [ABH16] demands that 2 (info where
=(V2N/
log
Pinfo (q)
(15)
The dashed red curve in Fig. 2 plots (q) as a function q.
Empirical evidence. From Fig. 2, one can see that our experiments reflect the behavior predicted by Theorem quite closely, although empirically we achieve 100% agreement slightly above Pehr (4) (i.e. the solid red curve). However, this is likely due to the constant factors from Theorem that we ignored, and also = 2000 plausibly too small to show asymptotic behaviors. Nevertheless, we do achieve 100% agreement consistently soon as we surpass the information-theoreet threshold Pinfo Pinfo(q): in the regime of our experiment, appears that the unnormalized Laplacian is robust all the way to the optimal threshold for exact recovery in the SSBM.
36

---

0-cut
Sweep bisection
Agreement with planted bisection
Agreement with planted bisection
1.0
0.9
0.8
Cymm
0.8
Esym
Cr
Cn
0.7
0.7
A
A
0.6
0.6
200
400 600
800
1000
200
400
600
800
1000
Size planted clique
Size planted clique
Figure 3: Agreement with the planted bisection of the bipartition obtained from several matrices associated with an input graph generated from distribution D E DCM(n, d q) for fixed values of n, g and varying the size of the planted clique S. In the left plot, the bipartition is the O-cut of the second eigenvector, as in Algorithm 1. In the right plot, the bipartition is the sweep cut of the first n/2 vertices in the second eigenvector.
B.2 Varying the size of a planted clique in a DCM
In some sense, the experiments from Section 4 and Appendix B.1 can be thought of as experiments for the deterministic clusters model too. This is because each realization of the internal edges gives rise to a different DCM distribution (see Section 2). We complement our previous discussion by illustrating the behavior of certain families of DCM distributions that conceptually different than those considered in Section 4.
Let n be divisible by 4 and let (PI, P--2 be partitioning of V = [n] Benchmark distribution.
into two equally-sized subsets. Fix p E [0. 1]. For some set C P1 such that (1,...,|S)) |S]} (for
simplicity), let G2 (P2, E2 ER(m/2, p) be graph drawn from the Erdös-Rényi distribution with sampling rate p. and let G (Pi, Fi) ERPC(n/2, p, ) be also a graph drawn from the Erdös- Erdös-Rény Rényi distribution with sampling rate where additionally plant a clique on the vertices S. Fixing G1, G2. for q E [0.1] we consider the distribution DC1. over graphs G = (V, E) where G[P:] G1, G[P2] G2, and every edge (u, v) E Pi P2 is sampled independently with probability One can see that D is in fact in the set DCM(n, din, q) for some din-
Setup. Let us fix n = 2000, = 9/V q ====1 1/V For varying values of |.|] in the range [|P11/10, [P sample G₁ E.P,EE ERPC(n/2, p. S) and G2 = (P2, E2) ER(n/2. p). and then draw = 10 independent samples G from Do, For each sample G, we run spectral bisection (i.c. Algorithm 1) with matrices L, Lsym: Los A. Then, we compute the agreement of the bipartition hence obtained with respect to the planted bisection, and average out across the t independent draws. The results are shown in the left plot of Fig. 3. Again, another natural way get a bipartition V from the eigenvector is a sweep cut, and the average agreements that this results in shown in the right plot of Fig. 3.
Ignoring the constants, Theorem guarantees that exact re- covery is achieved by unnormalized spectral bisection as long as din 2 ng + vn and (L - A2 2 vn + ng + yng lngllogn. + log where L is the expected Laplacian of DG For each clique size that
Theoretical framing.
consider, Fig. shows the minimum in-cluster degree of the graphs G1,G. G2 that we draw (in the left plot), and the spectral gap Ar (L (L). The red hori- zontal lines in the left and right plot respectively correspond to the value of ngg + v and yn + nq + /ng log n + log n on the y-axis, indicating the lower bound on dn and (L (L) demanded by Theorem 2.
Empirical evidence: consistency. From Fig. 4, one can see that all the distributions DGI,Ca that we use roughly meet the requirement of Theorem 2. Indeed, in the left plot of Fig. one sees that unnormalized spectral bisection consistently achieves exact recovery for all clique sizes. On the contrary, the bipartition obtained by running spectral bisection with the adjacency matrix A
37

---

160
135
As(L) -A(L
130
120
125
120
100
200
400
1000
200
400
600
800
1000
Size of planted clique
Size planted clique
Figure 4: The minimum in-cluster degree din and the spectral gap > X2 2 of distributions DC,,Ca DCM(n, din with fixed values of n, q and varying the size of the planted clique S. The red horizontal line on the left corresponds to the value nq + n,, the red horizontal line on the right corresponds to the value /n + nq /ng log log n.
misclassifies a fraction of the vertices for certain sizes of the planted clique. Nevertheless, the sweep cut obtained from all the matrices recovers the planted bisection exactly.
Let us fix the value J.s] 800 for the size of the planted clique, for which we see in Fig. 3 that the adjacency matrix fails recover the planted bisection. We generate a graph from a distribution DC.,G2 with clique size |S] = 800, and plot how the vertices are embedded in the real line by the second eigenvector of all the matrices consider. The result is shown in Fig. 5, where the three horizomtal dashed lines, from top to bottom, respectively correspond to the value of 1/VTi, O, -1/ /n on the y-axis. Graphically, one can see that the embedding in the unnormalized Laplacian is indeed the one that moves the least away from the values =1/vm, and fact the vertices (1.... 800} C P1 where we plant the clique concentrate even more around 1/ /n. This is phenomenon related to the one illustrated by Fig. 1. Finally, one can see from the embedding that splitting vertices around does result misclassifying a fraction of the vertices for the adjacency matrix. However, taking sweep cut that splits the vertices into two equally sized parts recovers the planted bisection for all matrices. This reflects the results shown in Fig. 3.
Empirical evidence: example embedding.
38

---

Unnormalized Laplacian
Sym. normalized Laplacian Csym
0.02
0.02
0.00
0.00
-0.04
-0.04
500
1000
1500
2000
500
1000 Vertices
1500
2000
Vertices
R.W. normalized Laplacian Cyw
Adjacency A
0.04
0.04
0.00
0.00
P2
P2
-0.02
-0.02
500
1000
1500
2000
500
1000
1500
2000
Vertices
Vertices
Figure 5: Embedding of the vertices given by the second eigenvector u2 of several matrices sociated with graph sampled from a distribution DGI,G2 E DCM(n, din, q). with the size of the planted clique set to |S| 2/5 n. Horizontal dashed lines, from top to bottom, correspond to 1/ /n, 0, 1 Vn respectively.
39

---

C 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: Please see Theorem 1, Theorem 2, and Theorem 3 for formal theoretical results. Please see Section and Appendix B for numerical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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. A 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.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Please see Theorem 1, Theorem 2, and Theorem 3 for formal theoretical results that include all assumptions and a corresponding discussion. Please see Section 4.1 for set of open questions that do not address in this work. Please see Section 4 and Appendix B for a numerical evaluation of our theoretical results, where we test our theory beyond the statements of our thcoretical results.
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 separate "Limitations" section 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 au- thors should reflect how these assumptions might be violated 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 a few datasets or with few runs. 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 ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-ter system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
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 ad- dress 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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
40

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Please see the proofs of Theorem 1 (Appendix A.7.1), Theorem (Ap- pendix A.7.2), and Theorem
3 (Appendix A.8), along with all lemmas referenced therein in the appendices. Please also see Section 3 for proof sketch of all the main results.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be elearly stated or referenced in the statement of any theo- rems.
The proofs can either appear the main paper or supplemental material, but 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 comple- mented by formal proofs provided appendix or 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 conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please see Section 4 and Appendix B for details, We have also attached our code.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible 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 a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
also be provided via
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution 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) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
41

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome 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 in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We have uploaded our experimental code with our submission.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
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 submission guidelines (https: /niips.coo wwtpccccpppcceeccccceccccceeeece http:/uudee///eeeee / ssionPolicy) 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 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 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, hyper- parameters, how they chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Please see Section and Appendix B.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [No]
Justification: It would be computationally expensive do so, especially for large graph sizes n. Decreasing n is not feasible because for small values of n, the asymptotic conver- gence of the algorithms is not evident.
Guidelines:
42

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence 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 a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors 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 out of range (e.g. negative eтror 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
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please the top of Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 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 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https : http///eeerip.eeeee httpppalicc/chcccciieeeeeeee
Answer: [Yes]
Justification: We attest that the research conducted through the course of this work adheres to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS 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 to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
43

---

This is theoretical paper on the robustness of a common unsupervised learn- ing algorithm.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a 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 technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (c.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
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (c.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This is theoretical paper on the robustness of a common unsupervised learn- ing algorithm.
Guidelines:
The answer NA means that the paper poses 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 re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make 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: [Yes]
Justification: Please see the top of Section 4.
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 dataset.
44

---

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 a particular source (e.g., website), the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the pack- age should be provided. For popular datasets, paperswi thcode com /dtaasess has curated licenses for some datasets. Their licensing guide can help determine the cense of 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.
If this information is not available online, the authors encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Question:
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create 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 pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: NA
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 contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to NeurlPS Code Ethics, workers involved in data collection, cura- tion, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: NA
Guidelines:
45

---

The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere 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.
46


Reviews:
[{"review_id": "dDDwHNApTB", "reviewer": "Reviewer_eQb7", "summary": "Spectral clustering has been a popular unsupervised method among mathematical statisticians and theoretical ML researchers. The first analysis of spectral clustering using perturbation analysis (Ng et al., 2001) appeared more than 20 years ago, which, of course, has a lot of limitations: Sparsity is not accounted for, and the number of clusters does not grow as the number of vertices increases.  The two major results that take care of these aspects are (Rohe et al., 2011) and (Lei and Rinaldo, 2015), which establish weak consistency of spectral clustering. On the other hand, there is a lot of literature on the strong consistency and in this context, authors introduces the problem very well. This paper is aimed at studying robustness of spectral algorithms a particular types of model mispecifications, using semirandom adverseries.  This paper provides several results on under what kind of semirandom models spectral clustering exactly recover groundtruth bi-clusters.", "questions": "(1) This paper doesnot deal with weak consistency results. Can you just comment on performing this kind of analysis to weak consistency case where one allow number of clusters to grow.  \n\n(2) One of the most important factor in studying spectral clustering under blockmodels models is sparsity. I could not find any comment about this in the paper.\n\n(3) Why is the bi-partitioning constraint? Is it because, when we consider top K eigenvectors, one need to perform K-means which can introduce further problems? \n\n(4) The Cheeger's inquality based description of hard instances for normalized case is nice but not difficult to perceive. Considering that we have higher-order cheeger inequalities, how do we extend this analysis to multi-partition case? Just looking for a comment if authors happens to know about these results.", "limitations": "Yes.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The problem is introduced very well, and even though there are a lot of technical details, one can easily go through all the results. While the present problem setting and results are based on the previous results in the literature, the contributions are respectable and provide more insights into the robustness of spectral clustering. Particularly, Theorem 3 is very interesting, which along with Theorem 1 and 2, shows that the unnormalized case is more robust to monotone adversarial changes.", "weaknesses": "(1) One of the biggest problem with keeping the number of clusters constant and then providing results for \"n\" large is that in most practical situations number of clusters grow with n. In that sense weak consistency, results that are available in the literature are much more appealing. \n\n(2) Limited to bi-partitioning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful feedback and questions! We address each concern here.\n\n> One of the biggest problems with keeping the number of clusters constant and then providing results for \"n\" large is that in most practical situations, the number of clusters grows with n. In that sense of weak consistency, results that are available in the literature are much more appealing.\n\nAs you point out, this may constitute a gap between practical scenarios and the theoretical guarantees that are proven within the SBM community. To our knowledge, most of the literature that gives provable guarantees for this problem consists of results where $k$ is independent of $n$ [Abbe17, page 114].\n\n> This paper does not deal with weak consistency results. Can you just comment on performing this kind of analysis to the weak consistency case where one allows the number of clusters to grow.\n\nAs highlighted by the survey of [Abbe17], spectral methods actually do not succeed up to the KS threshold, and such thresholds in fact cannot be achieved under a monotone adversary [MPW16]. While there are spectral partitioning algorithms based on higher-order Cheeger inequalities (e.g. [LOT11]), these work with the _normalized_ Laplacian and apply to a different generative model from the one we study. By virtue of our Theorem 3 (and our answer to your last question), these algorithms seem unlikely to be robust to the kinds of perturbations we study in this work. It would be interesting to see whether spectral methods can achieve the threshold obtained by [MPW16] under a monotone adversary.\n\n> One of the most important factors in studying spectral clustering under blockmodels models is sparsity. I could not find any comment about this in the paper.\n\nThe literature on block models often works in one of two regimes, the \"sparse\" regime where $p, q$ are $C/n$ for some constant $C$, and the \"high degree\" regime, where $p \\gg (\\log n)/n$. Our work falls into the latter setting, similar to many of the prior strong-consistency results. \n\n> Why is the bi-partitioning constraint? Is it because, when we consider top K eigenvectors, one needs to perform K-means which can introduce further problems?\n\nYes, if we consider more eigenvectors, simply considering the sign does not suffice for obtaining a partition. For example, the works on higher-order Cheeger inequalities need more careful partitioning algorithms to obtain guarantees [LOT11]. Also, to our knowledge, it is not known whether spectral methods achieve the information-theoretic bound for exact recovery in the case of $k > 2$, even for standard generalizations of the SBM to $k > 2$ communities.\n\nSecondly, analyzing the k=2 setting is already quite non-trivial, e.g., proving that spectral algorithms achieve strong consistency for two communities was a longstanding open problem until relatively recently [AFWZ19]. While it is true that many papers in property-testing [CKKMP18] do consider the general setting of $k$, in the setting of SBMs, designing _any_ algorithm for recovery for $k>2$ often requires much more sophisticated algorithmic machinery: like the recent result of [MRW24], STOC’24 (for general $k$), generalizing the result of [DDNS21], FOCS’21 (for $k = 2$) for the robust community recovery regime. Such results are less appealing in practice than those concerning spectral algorithms, which are commonly used.\n\n> The Cheeger's inequality based description of hard instances for the normalized case is nice but not difficult to perceive. Considering that we have higher-order cheeger inequalities, how do we extend this analysis to the multi-partition case? Just looking for a comment if authors happen to know about these results.\n\nThe Cheeger-based intuition of the hard instance for $k=2$ carries over to larger $k$: if the edges added by the adversary create a new, different, $k$-way sparsest cut, the embedding in the bottom $k$ eigenvectors of the normalized Laplacian should reflect (up to $poly(k)$ and square root losses) this new $k$-way sparsest cut as opposed to the planted one.\n\n[LOT11] Multi-way spectral partitioning and higher-order Cheeger inequalities (https://arxiv.org/abs/1111.1055)\n\n[MPW16] How Robust are Reconstruction Thresholds for Community Detection? (https://arxiv.org/abs/1511.01473)\n\n[Abbe17] Community Detection and Stochastic Block Models (https://arxiv.org/abs/1703.10146)\n\n[CKKMP18] Testing Graph Clusterability: Algorithms and Lower Bounds (https://arxiv.org/abs/1808.04807)\n\n[AFWZ19] Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank (https://arxiv.org/abs/1709.09565)\n\n[DDNS21] Robust recovery for stochastic block models (https://arxiv.org/abs/2111.08568)\n\n[MRW24] Robust recovery for stochastic block models, simplified and generalized (https://arxiv.org/abs/2402.13921)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BymePd1frO", "reviewer": "Reviewer_q18A", "summary": "This paper considers several semirandom variants of the SBM, and investigates whether spectral algorithms achieve exact recovery. The authors give guarantees for the performance of spectral clustering from the unnormalized Laplacian in both a nonhomogenous model, and a model in which the adversary has control over intra-community edges. Suprisingly, the normalized Laplacian is shown to perform worse than the unnormalized Laplacian in the inhomogeneous model.", "questions": "Could you please give an indication of which parts of your analysis could be tightened to yield sharp constants?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "As far as I know, this is the first work that provides guarantees for spectral algorithms in semirandom settings.  While the analysis is an adaptation of the work of Abbe et al on entrywise eigenvector analysis, it requires some new ideas. In particular, the models studied are not low-rank. It is very interesting that the unnormalized Laplacian does better than the normalized Laplacian!", "weaknesses": "Sharp constants are not given.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the supportive review! \n> Could you please give an indication of which parts of your analysis could be tightened to yield sharp constants?\n\nIn the current analysis, the Lemmas B.5 and B.6 have constants that we have not optimized, for the sake of clarity in exposition. While it is possible to improve constants slightly by a more tedious analysis, it is an open problem whether they can be improved all the way to the information-theoretic threshold. This question is also conceptually interesting: for certain semirandom models and recovery regimes, the recovery threshold can shift [MPW16], whereas in other cases it does not. We will add this discussion to the final version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qxoSgu018Y", "reviewer": "Reviewer_e2Qn", "summary": "The authors initially investigate the two-community spectral clustering algorithms applied to the 'Nonhomogeneous Symmetric Stochastic Block Model' (NSSBM). This model is characterized as a more encompassing semi-random framework, permitting a more lenient variation in the selection of in-cluster edge probabilities for each node pair, in comparison to the conventional '(Symmetric) Stochastic Block Model' (SBM). The authors subsequently apply the results derived from the NSSBM model to a more adversarial deterministic model, incorporating necessary adjustments. Finally, numerical simulation results are presented to support the theoretical insights from their study.", "questions": "Is it possible to extend the analysis to the model with variant choices of out-cluster probability for each pair of nodes such that $q_{v, w}\\in [\\bar{q},q]$. It seems trivial at least at the population level but I am not sure how the new change will affect the perturbation analysis.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The idea makes sense and the problem is of interest to the community. The authors provide the theoretical guarantee of the strong consistency of the spectral method for NSSBM which has a potential high rank(\\omega(n)) adjacent matrix whereas the counterpart is rank(2) for the traditional SBM model in the population level. Lemma $B.14$ ensures $\\mathbold u^\\star_2$ is always the second eigenvector of the Laplacian matrix even for the rank(\\omega(n)) case(NSSBM).", "weaknesses": "(1) The NSSBM model that the authors proposed is not that realistic as variants or perturbations may happen not only in in-cluster edges but also out-cluster edges in practice. Adding the edge only inside the clusters or promoting the in-cluster edge probability will only increase the signal-noise ratio (SNR) for the SBM model(Abbe 2018). \n\n(2) A comparison of the conditions of strong consistency for NSSBM with the existing model should help understand the paper better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful feedback! We address each concern here.\n\n> Adding the edge only inside the clusters or promoting the in-cluster edge probability will only increase the signal-noise ratio (SNR) for the SBM model(Abbe 2018).\n\nThis is typically the case for semi-random corruptions-- the SNR only improves compared to the uncorrupted (or purely stochastic) model. This means that the recovery problem is intuitively \"easier\", and it indeed is easier in an information theoretical sense. But as it turns out, algorithms for the stochastic case can fail. A classic example here is the semi-random planted clique problem, where a simple spectral algorithm can find cliques of size $\\sim \\sqrt{n}$ in the purely stochastic case, but it is known that the adjacency matrix-based spectral method fails under a monotone adversary and it is not known whether other spectral methods succeed to this threshold under the monotone adversary (see, e.g., pages 2-3 of https://timroughgarden.org/w17/l/l11.pdf).\n\nThus in our setting, it is not clear at all if the simple spectral algorithm (which has a reputation for being \"brittle\") should achieve perfect recovery when we add edges within clusters (in fact, by our Theorem 3, the _normalized_ spectral clustering algorithm provably fails in such a model). So while it would be nicer to be able to show recovery under more general corruptions, even the simpler setting we considered requires several new ideas. \n\n>A comparison of the conditions of strong consistency for NSSBM with the existing model should help understand the paper better.\n\nA comparison of these conditions can be found in lines 191-195 of the submission and in equations (14) and (15) in Appendix F (where we show additional empirical results): when $p,q = \\Theta(\\log n / n)$, the threshold we obtain is within a constant of that of the SSBM. We can emphasize this more in the final version.\n\n> Is it possible to extend the analysis to the model with variant choices of out-cluster probability for each pair of nodes such that $q_{v,w} \\in [\\overline{q},q]$? It seems trivial at least at the population level but I am not sure how the new change will affect the perturbation analysis.\n\nThis is a very interesting question, and it is posed as an open problem in Appendix A. In our current analysis, we crucially use the fact that the ideal second eigenvector can be easily characterized --- i.e., it is $u_2^{\\star} = [-1_{n/2} \\oplus 1_{n/2}]/\\sqrt{n}$. Further, this means that the Laplacian corresponding the internal edge additions remains orthogonal to $u_2^{\\star}$. But if we allow changing the out-cluster probabilities, then even at a population level, $u_2^{\\star}$ need not have a simple structural form, which causes the current techniques to fail. We will add more of this discussion to the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tLiuHFRKFZ", "reviewer": "Reviewer_hmYB", "summary": "The paper studies spectral algorithms for recovery in the stochastic block model (SBM).  Specifically, they consider a nonhomogeneous SBM where there are two communities $P_1, P_2$ and edges inside the communities occur (independently) with probability between $p$ and $\\bar{p}$ while edges between the communities appear with probability $q$.  This is a generalization of the standard SBM where the edges inside communities occur with probability exactly $p$.  The goal is to take a graph generated from the nonhomogeneous SBM (but without the community labels) and recover the communities $P_1, P_2$.   The nonhomogeneous modification seems to only strengthen the \"signal\" about the communities but is actually a useful test case for the robustness of various recovery algorithms for SBM -- in fact many well-known algorithms for SBM may break in the nonhomogeneous case.  The nonhomogeneous model is a special case of the more general semi-random model where edges may be arbitrarily added within communities and edges connecting different communities may be arbitrarily removed.  The sharp characterization of when exact recovery of the communities is possible was shown in [ABH16].  Semidefinite programming algorithms achieve the sharp threshold and succeed in recovery even in the more general semi-random model [FK01].  The goal of this paper is understanding spectral algorithms for recovery, which may be more efficient than semidefinite programming algorithms.\n\nThe main results of the paper are that under a certain gap condition on $p,\\bar{p},q$ that resembles the characterization in [ABH16] but is worse by some constant factor, spectral bisection based on the unnormalized Laplacian solves the recovery problem whereas using the spectrum of the normalized Laplacian provably fails.  The authors also prove a similar result in a modified setting called the deterministic cluster model.  The authors also run numerical simulations to support their results.", "questions": ".", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Spectral clustering algorithms are important for a variety of applications and understanding their robustness through the lens of semi-random models could potentially help bridge theory and practice\n\nThe paper has a neat conceptual takeaway about using the unnormalized Laplacian as opposed to the normalized Laplacian", "weaknesses": "The concrete theoretical results are somewhat weak.  The authors require an upper bound on the maximum edge probability that is comparable to $p,q$ -- this type of assumption isn't necessary for other algorithms such as SDPs.  They also don't achieve the sharp information-theoretic threshold of [ABH16] that other algorithms do. \n\n\n\nThe experiments are run on purely synthetic data but it would be more compelling if there were experiments on real graphs.  It is not clear that the nonhomogeneous SBM model proposed in the paper is a reasonable model for graphs that appear in practice because of this upper bound on the maximum edge probability and also the fact that no perturbations are allowed for the edges between different communities.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful feedback! We address each concern here.\n\n> The authors require an upper bound on the maximum edge probability that is comparable to $p, q$  -- this type of assumption isn't necessary for other algorithms such as SDPs.\n\nWhen the degrees are sufficiently high (i.e., $p, q$ are around $n^{-1/2}$), we do prove that even with arbitrary edge additions within clusters, unnormalized spectral clustering achieves perfect recovery (please see the DCM – Model 2, lines 202-211 on page 5 and the corresponding Theorem 2). This model actually allows more power than adding in-cluster edges to an SBM. Indeed, the adversary can be adaptive, meaning they can draw arbitrary internal edges _after seeing_ the randomized crossing edges. As far as we are aware, such an adversary was not studied even for SDPs or other (more complex) polynomial time algorithms. \n\nHowever, the stronger model above requires high degree (around $\\sqrt{n}$) to guarantee recovery, and it is an open question if we can push this result to the case of $p, q \\sim (\\log n)/n$ (see the discussion in Appendix A). A promising general direction here is to develop a better understanding of entrywise eigenvector perturbations for high-rank signal matrices. To our knowledge, our analysis is the first to give such a guarantee, but it will be interesting to do this for larger perturbations.\n\n> They also don't achieve the sharp information-theoretic threshold of [ABH16] that other algorithms do.\n\nOur bounds are within constants of the information-theoretic threshold, but yes, we do not know if it is possible to match it. Please refer to the response to reviewer e2Qn.\n\n> It is not clear that the nonhomogeneous SBM model proposed in the paper is a reasonable model for graphs that appear in practice because of this upper bound on the maximum edge probability and also the fact that no perturbations are allowed for the edges between different communities.\n\nNote that even the \"vanilla\" SBM has been a useful model in practice, by way of developing algorithms, and our model is a strict generalization. Our results provide evidence that unnormalized spectral clustering is a useful algorithm even with a significant amount of perturbation (though our proofs come with the limitation of the upper bound on max edge probability or a high-degree requirement). At a high level, the reason to study semirandom models is to understand if a given algorithm has overfit to some statistical properties about its input that should be morally irrelevant; in this sense, we believe that even with the restrictions, our results show a good level of robustness for spectral clustering. (We also refer to the discussion in lines 65-72 of the introduction, and our response to reviewer e2Qn.)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for their positive comments and their support of our paper. We are excited to hear the feedback and have responded to questions/provided some clarifications in comments directly responding to each review.

Meta-review: The reviewers generally agreed that the manuscript gives important and interesting insights into the performance of spectral algorithms for exact recovery in semi-random stochastic block models. They also gave a number of suggestions to improve the manuscript. Please address the reviewers' comments/questions carefully when you prepare the camera-ready version.
Decision: Accept (poster)