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_cc_2024_Conference
Published: 2024-05-15 18:36:02

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.

Main paper: 
 introduction: 
 Graph partitioning or clustering is a fundamental unsupervised learning primitive. In a graph partitioning 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 to capture this situation have been proposed and studied in the literature. Perhaps the most popular of these is the Symmetric Stochastic Block Model (SSBM) [HLL83] .Following the notation of previous works [AFWZ20 ; DLS21] , in this paper we describe an SSBM with specifications n, P 1 , P 2 , p, q, where n is an even positive integer, P 1 and P 2 are a partitioning 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 P 1 and P 2 consist of vertices 1, . . . , n/2 and n/2 + 1, . . . , n, respectively. Hence, with a mild abuse of notation, we write an SSBM with parameters n, p, q only and write it as SSBM(n, p, q). Now, let SSBM(n, p, q) be a distribution over random undirected graphs G = (V, E) where each edge (v, w) ∈ P 1 × P 1 and (v, w) ∈ P 2 × P 2 (which we refer to as "internal edges") appears independently with probability p, and each edge (v, w) ∈ P 1 × P 2 (which we refer to 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.In such scenarios, our general algorithmic goal is to efficiently identify P 1 and P 2 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 {P 1 , P 2 } for all n sufficiently large. Other approximate notions of recovery (such as almost exact, partial, and weak recovery) are also well-studied but are beyond the scope of this work.Although the SSBM(n, p, q) distribution over graphs is a useful starting point for algorithm design and has led to a deep theory about when recovery is possible and of what nature [Abb18] , it 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-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 semirandom models. At a high level, a semirandom model for a statistical problem interpolates between an average-case input (for example produced by a model such as the SSBM) and a worst-case input, in a way that still allows for a 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 p vw ≥ p, where the p vw may be chosen adversarially for each internal edge). Researchers have studied similar semirandom models for graph bisection [FK01; MMV12; MPW16; 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-world data generation process. Rather, they are a 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 modifications [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; MPW16; Moi21]. However, in practice, it may be undesirable 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, a 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 L G and the normalized Laplacian L G (we will formally define and intuit these notions in the sequel) [Von07] . This is because structural properties of both L G and L G imply that the second smallest eigenvalue of each, denoted as λ 2 (L G ) and λ 2 (L G ), serves as a continuous proxy for connectivity, and the corresponding eigenvector, u 2 (L G ) and u 2 (L G ), 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) := L G or Matrix(G) := L G . Following this discussion, we arrive at the question we study in this paper.Algorithm 1 SpectralBisection: given G = (V, E), outputs a bipartition of V 1: procedure SpectralBisection(G) ▷ G = (V, E) is the input graph 2:M ← Matrix(G) ▷ M ∈ R V ×V is a matrix with real eigenvalues 3:((λ i , u i )) n i=1 ← eigenvalue-eigenvector pairs of M with λ 1 ≤ • • • ≤ λ n ▷ n = |V | 4: S ← {v ∈ V : u 2 [v] < 0} 5:return {S, V \ S} Question 1. Under which semirandom models do the Laplacian-based spectral algorithms, using the second eigenvector of L G or L G , exactly recover the ground-truth communities P 1 and P 2 ?Main contributions.Our results show a surprising difference in the robustness of spectral bisection when considering the normalized versus the unnormalized Laplacian. We summarize our results below:• Consider a nonhomogeneous symmetric stochastic block model with parameters q < p < p, where every internal edge appears independently with probability p uv ∈ [p, p] and every crossing edge appears independently with probability q. We show that under an appropriate spectral gap condition, the spectral algorithm with the unnormalized Laplacian exactly recovers the communities P 1 and P 2 . Moreover, this holds even if an adversary plants ≪ np internal edges per vertex prior to the edge sampling phase.• Consider a stronger semirandom model where the subgraphs on the two communities P 1 and P 2 are adversarially chosen and the crossing edges are 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 P 1 and P 2 .• We show that there is a family of instances from a nonhomogeneous symmetric stochastic block model in which the spectral algorithm achieves exact recovery with the unnormalized Laplacian, but incurs a 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 on 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.1 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. In Appendix A.8, we prove our inconsistency result for the normalized Laplacian. In Appendix B, we give additional numerical trials and discussion.] and G[P 2 ] with minimum degree d in ;2. Nature samples every edge (v, w) ∈ P 1 × P 2 to be in E independently with probability q.3. The adversary arbitrarily adds edges (v, w) ∈ P 1 × P 1 and (v, w) ∈ P 2 × P 2 to E after observing the edges sampled by nature.We call a distribution D of graphs generated according to the above process a deterministic clusters model (DCM). We call the set of all such D the family of deterministic clusters models with parameters d in and q, written as DCM(n, d in , q).The DCM graph generation process is heavily motivated by the one studied by Makarychev, Makarychev, and Vijayaraghavan [MMV12] . This model is much more flexible than the SSBM and NSSBM settings in that the graphs the adversary draws on P 1 and P 2 are allowed to look very far from random graphs. This means the DCM is a 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 q be a probability and d in be an integer, and let D ∈ DCM(n, d in , q). For G ∼ D, let L denote the expectation of L after step (2) but before step (3) in Model 2. There exists constants C 1 , C 2 , C 3 > 0 such that for all n sufficiently large, ifd in ≥ C 1 • nq 2 + √ n and λ 3 ( L) -λ 2 ( L) ≥ √ n + C 2 nq + C 3 nq log n + log n ,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 in Theorem 2 are somewhat arbitrary. They are chosen to make our proofs cleaner and can likely be optimized.As a basic application of Theorem 2, note that in the SSBM, if p = ω(1/ √ n) and q = 1/ √ n, 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 P 1 and P 2 be two d-regular spectral expanders with d = ω( √ n) and let q ≤ 1/ √ n. On top of both of these two graph classes, one can further allow arbitrary edge insertions inside P 1 and P 2 while still being guaranteed exact recovery from unnormalized spectral bisection. 
models and main results: 
 In this paper, we study unnormalized and normalized spectral clustering in several semirandom SSBMs. These models permit a 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 we assume that the vertices of an n-vertex graph coincide with the set {1, . . . , n}. With this in mind, we begin 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).A G ∈ R V ×V of G is the matrix with entries defined as A G [v, w] = {(v, w) ∈ E}. Definition 2.2 (Degree matrix). Let G = (V, E) be a graph. The degree matrix D G ∈ R V ×V of G is the diagonal matrix with entries defined as D G [v, v] = d G [v], where d G [v] is the degree of v. Definition 2.3 (Unnormalized Laplacian). Let G = (V, E) be a graph. The unnormalized Laplacian L G ∈ R V ×V of G is the matrix defined as L G := D G -A G = (v,w)∈E (e v -e w )(e v -e w ) ⊤, where e i denotes the i-th standard basis vector. Definition 2.4 (Normalized Laplacians). Let G = (V, E) be a graph. The symmetric normalized Laplacian L G,sym ∈ R V ×V and the random walk Laplacian L G,rw ∈ R V ×V of G are defined asL G,sym := I -D -1/2 G A G D -1/2 G , L G,rw := I -D -1 G A G .For all notions above, when the graph G is clear from context, we omit the subscript G. Furthermore, when we discuss normalized Laplacians, we intend its symmetric version L sym 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 a graph, and let its unnormalized and normalized Laplacians be L and L, respectively. We refer to the algorithm resulting from running Algorithm 1 on G with Matrix(G) := L G as unnormalized spectral bisection. We refer to the algorithm resulting from running Algorithm 1 on G with Matrix(G) = L G 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 or strong consistency, defined as follows.Definition 2.6. Let {P 1 , P 2 } be a partitioning of V = {1, . . . , n}, and let D := D({P 1 , P 2 }) be a 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 {P 1 , P 2 } with probability at least 1 -1/n over the randomness of G.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 = {1, . . . , n}, {P 1 , P 2 } be a partitioning of V into two equally-sized subsets, and q < p ≤ p be probabilities. Let D be any probability distribution over graphs G = (V, E) such that for every (v, w) ∈ P 1 × P 1 and (v, w) ∈ P 2 × P 2 , the edge (v, w) appears in E independently with some probability p vw ∈ [p, p], and for every (v, w) ∈ P 1 ×P 2 , the edge (v, w) appears in E independently with probability q. We call such D 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(n, p, p, q). To visualize Model 1, consider the expected adjacency matrix of some NSSBM distribution. We then have the relationsp • J n/2 q • J n/2 q • J n/2 p • J n/2 ≤ P P1 q • J n/2 q • J n/2 P P2 ≤ p • J n/2 q • J n/2 q • J n/2 p • J n/2 ,where the leftmost matrix denotes the expected adjacency matrix of SSBM(n, p, q), the rightmost matrix denotes the expected adjacency matrix of SSBM(n, p, q), J k denotes the k×k all-ones matrix, and P P1 and P P2 denote the edge probability matrices for edges internal to P 1 and P 2 , respectively.The above also shows that the rank of the expected adjacency matrix for SSBM(n, p, q) is 2. However, the rank for the expected adjacency matrix for some NSSBM distribution may be as large as Ω(n). Perhaps surprisingly, this will turn out to 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.The NSSBM family generalizes the symmetric stochastic block model described in the previous section -this is attained by setting p vw = p for all internal edges (v, w). However, it can also encode biases for certain graph properties. For instance, a distribution from the NSSBM family may encode the idea that certain subsets of P 1 are expected to be denser than P 1 as a whole.With this definition in hand, we are ready to formally state our first technical result in Theorem 1.Theorem 1. Let p, p, q be probabilities such that q < p ≤ p and such that α := p/(pq) is an arbitrary constant. Let D ∈ NSSBM(n, p, p, q). Let n ≥ N (α) where the function N (α) only depends on α. There exists a universal constant C > 0 such that ifn(p -q) ≥ C np log n + log n , (gap condition)then unnormalized spectral bisection is strongly consistent on D.We prove Theorem 1 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 a small number of the p vw to 1 (at most np/ log log n 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 an exact information-theoretic threshold above which exact recovery with high probability is possible and below which no algorithm can be strongly consistent. In particular, the threshold states that for any p and q satisfying √ p -√ q > 2 log n/n, exact recovery is possible, and when p and q do not satisfy this, exact recovery is information-theoretically impossible. Furthermore, Feige and Kilian [FK01] prove that the information-theoretic threshold does not change in a somewhat stronger semirandom model that includes the NSSBM family. Additionally, Deng, Ling, and Strohmer [DLS21] show that unnormalized spectral bisection is strongly consistent all the way to this threshold in the special case where the graph is drawn from SSBM(n, p, q). By contrast, our gap condition holds in the same critical degree regime as in the information-theoretic threshold (namely, p = Θ(log n/n)) but our constant is not optimal. We incur this constant loss because for the sake of presentation, we opt for a 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 in an SSBM setting [AFWZ20; DLS21].Given Theorem 1, it is natural to ask what happens if we allow the adversary full control over the structure of the graphs in P 1 and P 2 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.Model 2 (Deterministic clusters model). Let n be an even positive integer, V = {1, . . . , n}, {P 1 , P 2 } be a partitioning of V into two equally-sized subsets, q be a probability, and d in be an integer degree lower bound. Consider a graph G = (V, E) generated according to the following process.Notice that in Theorem 1 and Theorem 2, we only address the strong consistency of the unnormalized 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 is a subfamily of instances belonging to NSSBM(n, p, p, q) with p = 6p, q = p/2 on which unnormalized spectral bisection is strongly consistent (following from Theorem 1) but normalized spectral clustering is inconsistent in a rather strong sense. Thus, one cannot obtain results similar to Theorem 1 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 is strongly consistent whereas normalized spectral bisection (both symmetric and random-walk) incurs a misclassification rate of at least 24% with probability 1 -1/n.We prove Theorem 3 in Appendix A.8. Furthermore, we expect that it is straightforward to adapt the example in Theorem 3 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 nuanced 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 second eigenvector is more robust to monotone adversarial changes.Perhaps the most natural follow-up question inspired by our results is to determine whether the restriction that every internal edge probability p vw ≤ 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, we only study insertion-only monotone adversaries, as crossing edge deletions change the second eigenvector of the expected Laplacian. It would be illuminating to understand the robustness of Laplacian-based spectral algorithms against a monotone adversary that is 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 to why one may expect that unnormalized spectral bisection is robust against our monotone adversaries. Here and in the sequel, letu ⋆ 2 = [ n/2 ⊕ -n/2 ]/ √ n,where k denotes the all-1s vector in k dimensions and ⊕ denotes vector concatenation. Let L be the unnormalized Laplacian of the graph we want to partition, L ⋆ := E [L], E := L -L ⋆ , andλ ⋆ i := λ i (L ⋆ ) for 1 ≤ i ≤ n.For an edge (v, w), let e vw := e v -e w , so that e vw is an edge incidence vector corresponding to the edge (v, w). Let p vw be the probability that the edge (v, w) appears in G and observe that L ⋆ can be written asL ⋆ = (v,w)∈Einternal p vw • e vw e T vw + (v,w)∈Ecrossing q • e vw e T vw ,where E internal = (P 1 × P 1 ) ∪ (P 2 × P 2 ) and E crossing = P 1 × P 2 . We can verify that u ⋆ 2 is an eigenvector of L ⋆ -indeed, we do so in Lemma A.14. And, for now, assume that u ⋆ 2 does correspond to the second smallest eigenvalue of L ⋆ (in our NSSBM family, this is easily ensured by enforcing p > q). Moreover, for every internal edge (v, w) ∈ E internal , we have ⟨e vw , u ⋆ 2 ⟩ = 0. Hence, any changes in internal edges do not change the fact that u ⋆ 2 is an eigenvector of the perturbed matrix. Thus, if the sampled L is close enough to L ⋆ , then it is plausible that the second eigenvector of L, denoted as u 2 , is pretty close to u ⋆ 2 . In fact, the following conceptually stronger statement holds. If the subgraph formed by selecting just the crossing edges of G is regular, then u ⋆ 2 is an eigenvector of L. This follows from the fact that u ⋆ 2 is an eigenvector of the unnormalized Laplacian of any regular bipartite graph where both sides have size n/2 and the previous observation that every internal edge is orthogonal to u ⋆ 2 . To make this perturbation idea more formal, we recall the Davis-Kahan Theorem. Loosely, it statesthat ∥u 2 -u ⋆ 2 ∥ 2 ≲ ∥(L -L ⋆ )u ⋆ 2 ∥ 2 /(λ ⋆ 3 -λ ⋆2 ) (we give a more formal statement in Lemma A.15). Expanding the entrywise absolute value |(L -L ⋆ )u ⋆ 2 | reveals that its entries can be expressed as2 |d out [v] -E [d out [v]]| / √ n, where d out [v]denotes the number of edges incident to v crossing to the opposite community as v. This is unaffected by any increase in the number of edges incident to v that stay within the same community as v, denoted as d in [v] . Hence, regardless of how many internal edges we add before sampling or what substructures they encourage/create, if we haveλ ⋆ 2 ≪ λ ⋆ 3 , then we get ∥u 2 -u ⋆ 2 ∥ 2 ≤ o(1). This immediately implies that u 2 is a correct classifier on all but an o(1) fraction of the vertices.Entrywise analysis of u 2 and NSSBM strong consistency.In order to achieve strong consistency, we need that for all n sufficiently large, u 2 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 directly yield ∥u ⋆ 2 -u 2 ∥ 2 ≪ 1/ √ n. Instead, we carry out an entrywise analysis of u 2 . A general framework for doing so is given by Abbe, Fan, Wang, and Zhong [AFWZ20] and is adapted to the unnormalized and normalized Laplacians by Deng, Ling, and Strohmer [DLS21] .At a high level, we adapt the analysis of Deng, Ling, and Strohmer [DLS21] to our setting. We consider the intermediate estimator vector (Dλ 2 I)-1 Au ⋆ 2 . This is a natural choice because we can verify (Dλ 2 I) -1 Au 2 = u 2 . We will see that it is enough to show that this intermediate estimator correctly classifies all the vertices while satisfying |(D -λ 2 I) -1 A(u ⋆ 2 -u 2 )| ≤ | (D -λ 2 I)-1 Au ⋆ 2 | (again, the absolute value is taken entrywise). With this in mind, taking some entry indexed by v ∈ V and multiplying both sides by d[v]λ 2 (which we will show is positive with high probability), we see that it is enough to showEQUATIONwhere a v 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 v is a Bernoulli random vector and use Bernstein's inequality to argue about the sum of rescalings of these Bernoulli random variables. Unfortunately, we cannot do this since u 2 and a v are dependent. To resolve this, we use a leave-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 (v) , denoted as u(v)2 , is a very good proxy for u 2 and is independent from a v . 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 P 1 and P 2 . In particular, the nonhomogeneity we permit in the NSSBM family may make L ⋆ look very far from a spiked low-rank signal matrix. Furthermore, our entrywise analysis of eigenvectors under perturbations is one of the first that we are aware of that moves beyond analyzing low-rank signal matrices or spiked low-rank signal matrices.L 1 L 2 R L 1 Kp • n/4×n/4 p • n/4×n/4 q • n/2×n/2 L 2 p • n/4×n/4 Kp • n/4×n/4 R q • n/2×n/2 p • n/2×n/2Table 1 : A ⋆ for Theorem 3 is defined to have the above block structure.Extension to 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 Davis-Kahan theorem gives us control over ∥u2 -u ⋆ 2 ∥ 2 while ∥a v ∥ 2 = d[v].The advantage of this is that we get a worst-case upper bound on the left hand side of (1) -it holds no matter what edges orthogonal to u ⋆ 2 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 d in [v] (and increases faster than∥a v ∥ 2 = d[v]) allows us to complete the proof of Theorem 2.Finally, we describe the family of hard instances we use to prove Theorem 3. To motivate this family of instances, recall that by the graph version of Cheeger's inequality, the second eigenvalue of L and the corresponding eigenvector can be used to find a sparse cut in G. Thus, if we create sparse cuts inside P 1 that are sparser than the cut formed by separating P 1 and P 2 , then conceivably the normalized Laplacian'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 L 1 consist of indices 1, . . . , n/4, L 2 consist of indices n/4 + 1, . . . , n/2, and R consist of indices n/2 + 1, . . . , n. Consider the block structure induced by the matrixA ⋆ = E [A] shown in Table 1.Intuitively, as K gets larger, the cut separating L 1 from V \ L 1 becomes sparser. From Cheeger's inequality, this witnesses a small λ 2 (L) and therefore the corresponding u 2 (L) may return the cut L 1 , V \ L 1 . We formally prove that this is indeed what happens when K is a sufficiently large constant and then Theorem 3 follows. 
numerical trials: 
 We programmatically generate synthetic graphs that help illustrate our theoretical findings using the libraries NetworkX 3.3 (BSD 3-Clause license), SciPy 1.13.0 (BSD 3-Clause License), and NumPy 1.26.4 (modified BSD license) [HSS08; VGO + 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 a setting that allows relating Theorem 1 and Theorem 3, and defer more experiments that investigate both NSSBM and DCM graphs to Appendix B.To put Theorem 1 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.1 , P -2} be a partitioning of V = [n] into two equally-sized subsets. Let {L 1 , L 2 } be a bipartition of P 1 such that |L 1 | = |L 2 | = n/4 and call L = P 1 , R = P 2 for convenience as in the proof of Theorem 3. Then, for some p, p, q ∈ [0, 1] such that q ≤ p ≤ p, consider the distribution D p,p,q over graphs G = (V, E) obtained by sampling every edge (u, v) ∈ (L 1 × L 1 ) ∪ (L 2 × L 2 ) independently with probability p, every edge (u, v) ∈ (L 1 × L 2 ) ∪ (R × R)independently with probability p, and every edge (u, v) ∈ L × R independently with probability q. One can see that D p,p,q is in fact in the set NSSBM(n, p, p, q).Let us fix n = 2000, p = 24 log n/n, q = 8 log n/n. For varying values of p in the range [p, 1], we sample t = 10 independent draws G from D p,p,q . For each of them, we run spectral bisection (i.e. Algorithm 1) with matrices L, L sym , L rw , 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 cut. In a sweep cut, we sort the entries of u 2 and take the vertices corresponding to the smallest n/2 entries to 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 .Theoretical framing. As per Theorem 1, we expect unnormalized spectral bisection to achieve exact recovery (i.e. agreement equal to 1) whenever p ≤ p max , wherep max = (n(p -q) -log n) 2 n log n (2)is obtained by rearranging the precondition of Theorem 1, ignoring the constants and disregarding the fact that α should be O(1). On the contrary, the proof of Theorem 3 shows that normalized spectral bisection misclassifies a constant fraction of vertices provided that p/q ≥ 2 (which our choice of parameters satisfies) and p ≥ p thr , whereEQUATION)In Fig. 1 , the solid vertical line corresponds to the value of p thr on the x-axis, and the dashed vertical line corresponds to the value of p max on the x-axis. In particular, observe that in our setting p thr < p max , so there is an interval of values for p where we expect Theorem 1 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 p thr and p max . On the other hand, the agreement of the bipartition obtained from all other matrices (hence including normalized spectral bisection) drops below 70% well before the threshold p thr 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 -u 2 of the unnormalized Laplacian continues to achieve 100% agreement, while for all other matrices the corresponding u 2 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] to have increasing volume. As illustrated in Fig. 1 , this seems to correlate with a decrease in the "variance" of the second eigenvector u 2 of the unnormalized Laplacian with respect to the ideal second eigenvector u ⋆ 2 . More precisely, we compute the average distance squared of the embedding of a vertex in u 2 from its ideal embedding in u ⋆ 2 , i.e. the quantity minEQUATION)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 u ⋆ 2 . Empirical evidence: example embedding.Let us fix the value p = p thr , 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 p,p,q , 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/ √ n, 0, -1/ √ n on the y-axis.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 to what we study in this paper.As mentioned in the introduction, perhaps the most fundamental and well-studied model is the symmetric 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 can achieve the information theoretic 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 recovery for the SSBM all the way to the information-theoretic threshold.Since the introduction of SBMs [HLL83], numerous variants have been proposed. These variants are designed to better reflect realworld graph properties that are unlikely to appear in graphs sampled from the SSBM. For instance, real-life social networks are likely to contain triangles. To address this, Sankararaman and Baccelli Figure 1 : Top left, bottom left: Agreement with the planted bisection of the bipartition obtained from several matrices associated with an input graph generated from a distribution in NSSBM(n, p, p, q) for fixed values of n, p, q and varying values of p. In the top left plot, the bipartition is the 0-cut of the second eigenvector, as in Algorithm 1. In the bottom left plot, the bipartition is the sweep cut of the first n/2 vertices in the second eigenvector. The dashed vertical line corresponds to p max = p max (n, p, q) (see (2)), and the solid vertical line corresponds to p thr = p thr (n, p, q) (see (3)). Top middle, top right, bottom middle: Embedding of the vertices given by the second eigenvector u 2 of several matrices associated with a graph sampled from D p,p,q with p = p thr . Horizontal dashed lines, from top to bottom, correspond to 1/ √ n, 0, -1/ √ n respectively. Bottom right: Variance of the embedding in the second eigenvector u 2 of the unnormalized Laplacian with respect to the ideal eigenvector u ⋆ 2 (see (4)), for input graphs generated from a distribution in NSSBM(n, p, p, q) with fixed values of n, p, q and varying values of p.[SB17] introduced a spatial stochastic block model, sometimes known as the geometric stochastic block model (GSBM). Other variations were introduced in the works of [GPMS18; GMPS19] . Subsequent work studies the performance of spectral algorithms on certain Gaussian or Geometric Mixture block models [ABRS20; ABD21; LS24; GNW24].Studying community detection with a semirandom model approaches this modeling question differently. Rather than implicitly encouraging a particular structure within the clusters like the models just mentioned, a semirandom adversary (including the ones we study in this paper) can more directly test the robustness of the algorithm to specially designed substructures.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 accurately recover communities up to a certain threshold, even in the semi-random setting. Other problems, such as detecting a planted clique [Jer92; Ku95; BHKKMP19], have also been studied in the semi-random model of [FK01] . In the setting of planted clique, a 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; BGLMSY24]. Finally, [SL17] shows that a spectral heuristic due to Boppana [Bop87] is robust under a 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 1.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 in [MMV12] (although without allowing crossing edge deletions).Lemma A.3. Suppose the crossing edges are sampled identically and independently with probability q. Then, for some universal constant C > 0, with probability at least 1δ we have that∀v ∈ V, |d out [v] -E [d out [v]]| ≤ C nq log ( n /δ) + log ( n /δ) .Proof of Lemma A.3. Choose some v ∈ V . Consider the random variable d out [v] . Using Lemma A.2, we have that there is a constant C > 0 such that with probability at least 1δ/n one has|d out [v] -E [d out [v]]| ≤ C 4nq/2 log ( 2n /δ) + log ( 2n /δ) .Taking a union bound over all n vertices completes the proof of Lemma A.3.Note that Lemma A.3 above applies in both the settings of Theorem 1 and Theorem 2.Lemma A.4. Suppose the internal edges are sampled independently with probabilities p vw such that p ≤ p vw ≤ p. Then, for some universal constant C > 0, with probability ≥ 1δ we have that∀v ∈ V, |d in [v] -E [d in [v]]| ≤ C   w∈P (v)\{v} p vw (1 -p vw ) log ( n /δ) + log ( n /δ)   .Proof of Lemma A.4. As before, choose some v ∈ V and consider the random variable d in [v] . By Lemma A.2, we have that there is a constant C > 0 such that with probability at least 1δ/n one has|d in [v] -E [d in [v]]| ≤ C   4 w∈P (v)\{v} p vw (1 -p vw ) log ( 2n /δ) + log ( 2n /δ)   .Taking a union bound over all n vertices completes the proof of Lemma A.4.Combining the above two lemmas, we obtain a lower-bound ond in [v] -d out [v].In particular, the following lemma implies that in the setting of Theorem 1, we haved in [v] > d out [v].This will be required for applying Lemma A.23.Lemma A.5. There exists a universal constant C > 0 such that with probability ≥ 1δ, in the same settings as Lemma A.3 and Lemma A.4 and assuming the gap condition in Theorem 1, if p ≥ q, then for all v ∈ V we haved in [v] -d out [v] ≥ n(p -q) 2 -C np log ( n /δ) + log ( n /δ) .Proof of Lemma A.5. Let v ∈ V . First, we call Lemma A.3 with a failure probability of δ/(2n) to conclude thatd out [v] ≤ nq 2 + C A.3 nq 2 log 2n 2 /δ + log 2n 2 /δ .Next, we call Lemma A.4 with a failure probability of δ/(2n) to conclude thatd in [v] ≥ w∈P (v)\{v} p vw -C A.4   w∈P (v)\{v} p vw (1 -p vw ) log 2n 2 /δ + log 2n 2 /δ   ≥ w∈P (v)\{v} p vw -C A.4   w∈P (v)\{v} p vw log 2n 2 /δ + log 2n 2 /δ   ≥ np 2 -2C A.4 np 2 log n 2 /δ + log 2n 2 /δ .where the last line uses the fact that xc √ x is increasing in x whenever x ≥ c 2 /4 and c > 0. We subtract and conclude the proof of Lemma A.5 by a union bound.The following lemma will be useful for lower-bounding d[v]λ 2 in Theorem 1.Lemma A.6. Suppose every crossing edge appears independently with probability q. Then, with probability ≥ 1δ, for all v ∈ V we haveλ 2 ≤ 2d out [v] + C nq log ( n /δ) + log ( n /δ) .Proof of Lemma A.6. Observe that with probability at least 1δ,d out [w] -E [d out [v]] ≤ 2nq log( 2n /δ) + 2 log(2n/δ) for all w ∈ V by Lemma A.2. Then, for every v ∈ V we have2 n w∈P (v) d out [w] -d out [v] =   2 n w∈P (v) d out [w] -E [d out [v]]   + (E [d out [v]] -d out [v]) ≤ 2 n w∈P (v) d out [w] -E [d out [v]] + |E [d out [v]] -d out [v]| ≤ 2nq log ( 2n /δ) + 2nq log ( 2n /δ) + 4 log ( 2n /δ) ≤ 3 nq log ( n /δ) + 10 log ( n /δ) .Next, by the min-max principle, we haveλ 2 ≤ (w,w ′ )∈E (u ⋆ 2 [w] -u ⋆ 2 [w ′ ]) 2 = 4 n w∈P (v) d out [w].Combining everything, we getλ 2 ≤ 2   2 n w∈P (v) d out [w]   ≤ 2 d out [v] + 3 nq log ( n /δ) + 10 log ( n /δ) ,completing the proof of Lemma A.6.We can now lower-bound d[v]λ 2 . Note that the following lower bound implies that d[v] > λ 2 , as required by Lemma A.23.Lemma A.7. In the setting of Theorem 1, with probability ≥ 1δ, for all v ∈ V , we haved[v] -λ 2 > n(p -q)/4.Proof of Lemma A.7. Recall that the gap condition in Theorem 1 tells us that p and q are such that for a universal constant C,n(p -q) ≥ C np log ( n /δ) + log ( n /δ) ,We have for all n sufficiently large (specifically, n ≥ N (α, δ) for some N that is a function only of the constant α, and we take δ ≥ 1/n O(1) ) that with probability at least 1δ,d[v] -λ 2 = d in [v] -d out [v] + (2d out [v] -λ 2 ) ≥ d in [v] -d out [v] -C A.6 nq log ( n /δ) + log ( n /δ) ≥ n(p -q) 2 -(C A.5+C A.6 ) np log ( n /δ) + log ( n /δ) , so insisting n(p -q) 4 ≥ (C A.5+C A.6 ) np log ( n /δ) + log ( n /δ) + 1gives the condition required to complete the proof of Lemma A.7.The following technical lemma will be useful for upper-bounding ∥u 2 ∥ ∞ in Lemma A.22.Lemma A.8. In the setting of Theorem 1, there exists a universal constant C such that with probability ≥ 1δ, for all v ∈ V we havenp + log ( n /δ) d[v] -λ 2 ≤ 4α + C.Proof of Lemma A.8. By Lemma A.7, we have with probability ≥ 1δ that for all v ∈ V ,d[v] -λ 2 ≥ n(p -q) 4 .This givesnp + log ( n /δ) d[v] -λ 2 ≤ 4(np + log ( n /δ)) n(p -q) = 4p p -q + 4 log ( n /δ) n(p -q) ≤ 4α + C.This completes the proof of Lemma A.8.For the matrix concentration lemmas, we need a result due to Le, Levina, and Vershynin [LLV17] .We reproduce it below.Lemma A.9 ([LLV17, Theorem 2.1]). Consider a random graph from the model G(n, {p ij }). Let d = max ij np ij . For any r ≥ 1, the following holds with probability at least 1n -r for a universal constant C. Consider any subset consisting of 10n/d vertices, and reduce the weights of the edges incident to those vertices in an arbitrary way. Let d ′ be the maximal degree of the resulting graph. Then, the adjacency matrix A ′ of the new weighted graph satisfies∥A ′ -E [A]∥ op ≤ Cr 3/2 √ d + √ d ′ .Moreover, the same holds for d ′ being the maximal ℓ 2 norm of the rows of A ′ .Lemma A.10. Let L be a Laplacian sampled from the nonhomogeneous Erdős-Rényi model where each edge (i, j) is present independently with probability p ij . Then, there exists a universal constant C such that for all n sufficiently large, with probability ≥ 1δ for any δ ≥ n -10 ,∥L -E [L]∥ op ≤ C n max (i,j) : pij ̸ =1 p ij log ( n /δ) + log ( n /δ) .Proof of Lemma A.10. Without loss of generality, for all p ij that are 1, reset their probabilities to 0.To see that this is valid, let L ′ be a Laplacian sampled from this modified distribution and notice thatL ′ -E [L ′ ] = L -E [L].By Lemma A.9 and Lemma A.2, we have with probability≥ 1 -δ/2 that ∥A -E [A]∥ op ≤ 200C A.9 2n max ij p ij + C A.2 n max ij p ij log( 8n /δ) + log( 8n /δ) ≤ 400C A.9 C A.2 n max ij p ij + log( 8n /δ) ≤ 400C A.9 C A.2 n max ij p ij log( 8n /δ) + log( 8n /δ)and by Lemma A.3 and Lemma A.4, we have with probability1 -δ/2 that ∥D -E [D]∥ op ≤ max v∈V |d out [v] -E [d out [v]]| + max v∈V |d in [v] -E [d in [v]]| ≤ 2 max {C A.3 , C A.4 } n max ij p ij log ( 2n /δ) + log ( 2n /δ)Now, observe that with probability ≥ 1δ (following from a union bound),∥L -E [L]∥ op = ∥D -E [D] -(A -E [A])∥ op ≤ ∥D -E [D]∥ op + ∥A -E [A]∥ op ≤ 800C A.9 C A.2 max {C A.3 , C A.4 } n max ij p ij log ( 8n /δ) + log ( 8n /δ) ,completing the proof of Lemma A.10.By applying the above lemma, we can show that there is a gap between λ 3 and λ ⋆ 2 , which will allow us to apply Davis-Kahan style bounds. More concretely, Lemma A.11 and Lemma A.12, together with Lemma A.16, show that ∥u 2u ⋆ 2 ∥ 2 is small. This will be useful for proving that in the context for Theorem 1, the condition|⟨a v , u ⋆ 2 -u 2 ⟩| ≤ (d in [v] -d out [v])/ √ n in Lemma A.23 is satisfied.Lemma A.11. In the setting of Theorem 1, there exists a universal constant C such that the following holds.Let p and q be such that we haven(p -q) ≥ C np log ( n /δ) + log( n /δ) .Then, for any δ ≥ n -10 , with probability ≥ 1δ, we haveλ 3 -λ ⋆ 2 ≥ n(p -q)/4.Proof of Lemma A.11. By Weyl's inequality and Lemma A.10, we have with probability ≥ 1δ thatλ 3 -λ ⋆ 2 ≥ λ ⋆ 3 -λ ⋆ 2 -∥L -L ⋆ ∥ op ≥ n(p -q) 2 -C A.10 np log ( n /δ) + log( n /δ) .Let C ≥ 4C A.10 . Then,n(p -q) 4 ≥ C A.10 np log ( n /δ) + log( n /δ) .Subtracting completes the proof of Lemma A.11.Next, we bound ∥Eu ⋆ 2 ∥ 2 , which we will need in order to apply our Davis-Kahan 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 q. There exists a universal constant C such that for all n sufficiently large, with probability ≥ 1δ, we have∥Eu ⋆ 2 ∥ 2 ≤ C log ( 1 /δ) log n 3/2 √ nq + (nq log ( n /δ)) 1/4 + log ( n /δ) . Proof of Lemma A.12. Observe that |Eu ⋆ 2 | = 2 |d out -E [d out ]| / √ n. By Lemma A.3, for all v ∈ V , with probability ≥ 1 -δ/2, we have d out [v] ≤ nq/2 + C A.3 nq • log (2n/δ) + log ( 2n /δ) .So, if we let A out and A ⋆ out denote the adjacency matrices consisting only of the crossing edges and the expected value of that, respectively, then invoking Lemma A.9, with probability ≥ 1δ, we have∥Eu ⋆ 2 ∥ 2 = 2 ∥d out -E [d out ]∥ 2 √ n = 2 ∥(A out -A ⋆ out ) ∥ 2 √ n ≤ 2 ∥A out -A ⋆ out ∥ op ≤ 2C A.9 log ( 2 /δ) log n 3/2 nq 2 + C A.3 nq + nq log ( 2n /δ) + log ( 2n /δ) ,completing the proof of Lemma A.12.Finally, we apply Lemma A.9 in order to bound bound ∥a v -a ⋆ v ∥ 2 .Lemma A.13. In the setting of Theorem 1, with probability ≥ 1δ, we have∥a v -a ⋆ v ∥ 2 ≤ C log ( 1 /δ) log n 3/2 np + (np log ( n /δ)) 1/4 + log ( n /δ) .Proof of Lemma A.13. We use a similar proof to that of Lemma A.12. Indeed, invoke Lemma A.9 (observe that we can set p ij for the deterministic internal edges to 0 as they do not affect A -E [A]) and notice that∥a v -a ⋆ v ∥ 2 ≤ ∥A -A ⋆ ∥ op ≤ C A.9 log ( 2 /δ) log n 3/2 np + (np log ( 2n /δ)) 1/4 + log ( 2n /δ) ,where we used d ′ ≤ n(p + q)/2 + 2 max {C A.3 , C A.4 } np log ( 2n /δ) + log ( 2n /δ) from combining Lemma A.3 and Lemma A.4. This completes the proof of Lemma A.13.In this Appendix, we give our Euclidean norm eigenvector perturbation bounds.First, we verify that u ⋆ 2 is indeed the second eigenvector of L ⋆ .Lemma A.14. In the setting of Theorem 1, we haveL ⋆ u ⋆ 2 = λ 2 (L ⋆ )u ⋆ 2 = nqu ⋆ 2 , where L ⋆ = E [L].In the setting of Theorem 2, we haveL ⋆ u ⋆ 2 = λ 2 (L ⋆ )u ⋆ 2 = nqu ⋆ 2, where L ⋆ 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 u ⋆ 2 is an eigenvector of L ⋆ with eigenvalue nq:for any v ∈ P 2 (i.e. u ⋆ 2 [v] = -1/√ n without loss of generality), one has(L ⋆ u ⋆ 2 ) v = 1 √ n   -(d in [v] + nq/2) - w∈P1:{v,w}∈E (-1) + w∈P2 (-q)   = - nq √ n = nq • u ⋆ 2 [v] .By virtue of the above observations, it suffices to argue that nq < λ3 (L ⋆ ) ≤ • • • ≤ λ n (L ⋆ ).In the setting of Theorem 1, we claim λ ⋆ 3 ≥ n(p+q)> nq. This is because because p vw ≥ p, which implies that if we consider L ⋆ 1 to be the expected Laplacian for SSBM(n, p, q) and L ⋆ 2 to be the expected Laplacian for NSSBM(n, p, p, q), then L ⋆ 2 ⪰ L ⋆ 1 .. In the setting of Theorem 2, we have λ 3 ( L)λ 2 ( L) > nq, by the theorem assumption. Since L ⋆ is obtained from L by adding the adversarial edges, we have λ i (L ⋆ ) ≥ λ i ( L) for all i. In particular, we haveλ 3 (L ⋆ ) ≥ λ 3 ( L) = λ 2 ( L) + (λ 3 ( L) -λ 2 ( L)) > nq,where the last inequality is using the fact λ 2 ( L) ≥ 0. Therefore, nq must be the second eigenvalue of L ⋆ , completing the proof of Lemma A.14.Next, we prove a general Davis-Kahan style bound.Lemma A.15. Let L and L be two weighted Laplacian matrices. Let u 2 and u 2 be the second eigenvectors of L and L, respectively. Then,∥u 2 -u 2 ∥ 2 ≤ √ 2 • min    ( L -L)u 2 2 λ 3 ( L) -λ 2 (L) , ( L -L) u 2 2 λ 3 (L) -λ 2 ( L)   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 an eigenvalue decomposition and observe it from there. Without loss of generality, assume that ⟨ u 2 , u 2 ⟩ ≥ 0 (indeed, otherwise we can always negate u 2 if this is not the case). Notice that( L -L)u 2 2 2 = L -λ 2 (L)I u 2 2 2 = (λ 2 ( L) -λ 2 (L)) 2 ⟨ u 2 , u 2 ⟩ 2 + n i=3 λ i ( L) -λ 2 (L) 2 ⟨ u i , u 2 ⟩ 2 ≥ n i=3 λ 3 ( L) -λ 2 (L) 2 ⟨ u i , u 2 ⟩ 2 = λ 3 ( L) -λ 2 (L) 2 1 -⟨ u 2 , u 2 ⟩ 2 , which rearranges to ⟨ u 2 , u 2 ⟩ 2 ≥ 1 -   ( L -L)u 2 2 λ 3 ( L) -λ 2 (L)   2 . Now, if ( L -L)u 2 2 ≥ |λ 3 ( L) -λ 2 (L)|, then the condition ∥u 2 -u 2 ∥ 2 ≤ √ 2 • ( L-L)u2 2 λ3( L)-λ2(L) is trivially satisfied, since ∥u 2 -u 2 ∥ 2 ≤ 2 -2 ⟨ u 2 , u 2 ⟩ ≤ √ 2.Otherwise, taking the square roots of both sides, we obtain⟨ u 2 , u 2 ⟩ ≥ 1 -   ( L -L)u 2 2 λ 3 ( L) -λ 2 (L)   2 , which gives ∥ u 2 -u 2 ∥ 2 2 = 2 -2 ⟨ u 2 , u 2 ⟩ ≤ 2 -2 1 -   ( L -L)u 2 2 λ 3 ( L) -λ 2 (L)   2 ≤ 2 •   ( L -L)u 2 2 λ 3 ( L) -λ 2 (L)   2 .Taking the square root of both sides and repeating this argument by exchanging the roles of L and L yields the statement of Lemma A.15.This immediately implies the following upper-bound on ∥u 2 -u ⋆ 2 ∥ 2 . We will use it repeatedly, both in Theorem 1 and Theorem 2. Lemma A.16. We have∥u 2 -u ⋆ 2 ∥ 2 ≤ √ 2 • ∥Eu ⋆ 2 ∥ 2 |λ 3 -λ ⋆ 2 | .Proof. Lemma A.16 immediately follows from Lemma A.15 by letting L = L ⋆ .Combining with Lemma A.11 and Lemma A.12, we can now upper-bound ∥u 2 -u ⋆ 2 ∥ 2 in the setting of Theorem 1.Lemma A.17. In the setting of Theorem 1, there exists a universal constant C such that, for δ ≥ 3n -10 , with probability ≥ 1δ, we have∥u 2 -u ⋆ 2 ∥ 2 ≤ C log ( n /δ) .Proof of Lemma A.17. Using Lemma A.16, Lemma A.11 and Lemma A.12, we have∥u 2 -u ⋆ 2 ∥ 2 ≤ 400 √ 2C A.12 √ nq + (nq log ( n /δ)) 1/4 + log ( n /δ) n(p -q) .At this point, it is enough to show that there exists a universal constant C such that Cn(pq) ≥ 4 √ 2C A.12 nq log ( n /δ) + (nq) 1/4 (log ( n /δ)) 3/4 + log ( n /δ) .To see this, note that for any two nonnegative real numbers we have 2a ≤ 8 √ 2C A.12 np log ( n /δ) + log ( n /δ) ≤ n(p -q),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 ℓ 1 norm concentration for the rows of A and for the rows of L in the setting of Theorem 1. We will use this in Lemma A.19, where we will bound u(v) 2 -u 2 2 . Here u (v) 2denotes the second eigenvector of the leave-one-out Laplacian L (v) .Lemma A.18. In the setting of Theorem 1, there exists a universal constant C such that with probability ≥ 1δ, for all v ∈ V , we have∥a v -a ⋆ v ∥ 1 ≤ C np + np log ( n /δ) + log ( n /δ) ∥l v -E [l v ]∥ 1 ≤ C np + np log ( n /δ) + log ( n /δ) .Proof of Lemma A.18. It is easy to see that∥l v -E [l v ]∥ 1 = |d[v] -E [d[v]]| + ∥a v -a ⋆ v ∥ 1 .Let us consider the second term above. By Lemma A.4 and Lemma A.3, we have with probability≥ 1 -δ/2 that ∥a v -a ⋆ v ∥ 1 ≤ ∥a v ∥ 1 + ∥a ⋆ v ∥ 1 ≤ 2 np 2 + max {C A.3 , C A.4 } np log ( 4n /δ) + log ( 4n /δ) + np = 2np + 2 max {C A.3 , C A.4 } np log ( 2 /δ) + log ( 4n /δ) .Finally, by Lemma A.3 and Lemma A.4, we have with probability 1δ/2 that for all v ∈ V ,|d[v] -E [d[v]]| ≤ max v∈V |d out [v] -E [d out [v]]| + max v∈V |d in [v] -E [d in [v]]| ≤ 2 max {C A.3 , C A.4 } np log ( 4n /δ) + log ( 4n /δ)Adding everything up means that with probability ≥ 1δ, for all v ∈ V , we have∥l v -E [l v ]∥ 1 ≤ 2np + 4 max {C A.4 , C A.3 } np log ( 4n /δ) + log ( 4n /δ) ,which completes the proof of Lemma A.18.Having established Lemma A.18, we can now upper-bound u(v) 2 -u 2 2 .Lemma A.19. In the setting of Theorem 1, with probability ≥ 1δ, for all v ∈ V , we haveu (v) 2 -u 2 2 ≤ ∥u 2 ∥ ∞ • C p + p log ( n /δ) /n + log ( n /δ) /n p -qProof of Lemma A.19. Recall that the gap condition in Theorem 1 means that p and q are such that for a universal constant C, n(pq) ≥ C np log ( n /δ) + log ( n /δ) .To appeal to Lemma A.15, we need to understand the entries of the matrix L -L (v) . It is easy to see that this matrix only has nonzero entries on the diagonal and in the vth row and column. There, the vth row and column of L -L (v) are exactly equal to those of L -L ⋆ . Moreover, the w ̸ = vthdiagonal entry of L -L (v) is exactly {(v, w) ∈ E} -p vw .Hence, we haveL -L (v) u 2 2 = n w=1 L -L (v) w , u 2 2 1/2 =   ⟨(L -L ⋆ ) v , u 2 ⟩ 2 + w̸ =v ((a v [w] -p vw ) u 2 [w] -(a v [w] -p vw ) u 2 [v]) 2   1/2 ≤ |⟨(L -L ⋆ ) v , u 2 ⟩| +   w̸ =v ((a v [w] -p vw ) u 2 [w] -(a v [w] -p vw ) u 2 [v]) 2   1/2 ≤ (∥l v -E [l v ]∥ 1 + 2 ∥a v -a ⋆ v ∥ 2 ) • ∥u 2 ∥ ∞ ≤ (∥l v -E [l v ]∥ 1 + 2 ∥a v -a ⋆ v ∥ 1 ) • ∥u 2 ∥ ∞ ≤ ∥u 2 ∥ ∞ • 3C A.18 np + np log ( n /δ) + log ( n /δ) .Now, let C ≥ 8C A.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 ≥ 1δ that for all v ∈ V and for all n sufficiently large,λ (v) 3 -λ 2 ≥ λ (v) 3 -λ ⋆ 3 -(λ 2 -λ ⋆ 2 ) + (λ ⋆ 3 -λ ⋆ 2 ) ≥ -2 C A.10 np log ( n /δ) + log ( n /δ) + n(p -q) 2 ≥ n(p -q) 4 .Now, using Lemma A.15, we getu (v) 2 -u 2 2 ≤ L -L (v) u 2 2 |λ (v) 3 -λ 2 | ≤ ∥u 2 ∥ ∞ • 12C A.18 np + np log ( n /δ) + log ( n /δ) n(p -q) ≤ ∥u 2 ∥ ∞ • 12C A.18 p + p log ( n /δ) /n + log ( n /δ) /n p -q ,completing the proof of Lemma A.19.The main goal of this section is to establish an upper-bound on |⟨a v -a ⋆ v , u 2 -u ⋆ 2 ⟩| in the setting of Theorem 1. To this end, we will need the following concentration inequality from [AFWZ20] .Lemma A.20 (Lemma 7 from [AFWZ20] ). Let w ∈ R n and X i ∼ Ber(p i ). Let p ≥ p i for all i ∈ [n]. Let X ∈ R n be the vector formed by stacking the X i . Then,Pr   |⟨w, X -E [X]⟩| ≥ (2 + a)pn max 1, log √ n∥w∥ ∞ ∥w∥ 2 • ∥w∥ ∞   ≤ 2exp (-anp) .Lemma A.21. In the setting of Theorem 1, suppose a v is such that a v [w] ∼ Bernoulli(p vw ) and let p ≥ max w : pvw̸ =1 p vw . With probability ≥ 1δ for δ ≥ 1/n 2 , for all v ∈ V , we have|⟨a v -a ⋆ v , u 2 -u ⋆ 2 ⟩| ≤ C (np + log ( 1 /δ)) ∥u 2 ∥ ∞ log log n + 1 √ n log log n .Proof of Lemma A.21. Ideally, one would treat u 2 -u ⋆ 2 as fixed and then apply Bernstein's inequality to argue that the sum of centered Bernoulli random variables as written above concentrates well. Unfortunately, since u 2 depends on a v -a ⋆ v , we cannot express this inner product as the sum of independent random variables.To resolve this, we use the leave-one-out method. Let u (v) 2 be the second eigenvector of the leaveone-out Laplacian L (v) of A (v) , where A (v) is chosen to agree with A everywhere except for the vth row and vth column. The vth row and vth column of A (v) are replaced with those of A ⋆ . Now, a v does not depend on L (v) and therefore u (v) 2 . We therefore write|⟨a v -a ⋆ v , u 2 -u ⋆ 2 ⟩| ≤ a v -a ⋆ v , u 2 -u (v) 2 + a v -a ⋆ v , u (v) 2 -u ⋆ 2 ≤ ∥a v -a ⋆ v ∥ 2 • u (v) 2 -u 2 2 + a v -a ⋆ v , u (v) 2 -u ⋆ 2 ≤ ∥a v -a ⋆ v ∥ 2 • C A.19 p p -q ∥u 2 ∥ ∞ + a v -a ⋆ v , u (v) 2 -u ⋆ 2 .To bound the rightmost term of the RHS, we use Lemma 7 of [AFWZ20] , reproduced in Lemma A.20. In that, let w := u(v) 2 -u ⋆ 2 . Let a = 1 np log ( 2 /δ) so that 2 exp(-2anp) ≤ δ.Note that for the deterministic entries, we have a v -a ⋆ v = 1 -1 = 0, so in Lemma A.20, we can set X w ∼ Ber(0) for these entries. Now, by Lemma A.20, with probability ≥ 1δ, we haveu (v) 2 -u ⋆ 2 , a v -a ⋆ v ≤ 2np + log 2 δ max 1, log √ n∥w∥ ∞ ∥w∥ 2 • ∥w∥ ∞ . (5) Let us first bound ∥w∥ ∞ = u (v) 2 -u ⋆ 2 ∞. We writeEQUATION)In what follows, we omit the arguments α and δ in mentions of C A.19 . Next, using Lemma A.17, the triangle inequality, and δ ≥ 1/n 3 , we have∥w∥ 2 = u (v) 2 -u ⋆ 2 2 ≤ C A.19 ∥u 2 ∥ ∞ + 4C A.17 √ log n .We now have two cases based on the value of√ n • u (v) 2 -u ⋆ 2 ∞ u (v) 2 -u ⋆ 2 2.Case 1 -w is not too "flat." Let us first handle the case where√ n • u (v) 2 -u ⋆ 2 ∞ u (v) 2 -u ⋆ 2 2 ≥ log n.We plug this into (5) and getu (v) 2 -u ⋆ 2 , a v -a ⋆ v ≤ 2np + log 2 δ max 1, log √ n∥w∥ ∞ ∥w∥ 2 • ∥w∥ ∞ ≤ 4 • np + log ( 1 /δ) log log n C A.19 ∥u 2 ∥ ∞ + 1 √ n ,where the last inequality follows from (8).Case 2 -w is "flat." We now assume√ n • u (v) 2 -u ⋆ 2 ∞ u (v) 2 -u ⋆ 2 2 ≤ log n.We can easily check that the function x max (1, log x) is increasing, so its maximum will be attained at the largest value of x in the domain. Let x = √ n ∥w∥ ∞ / ∥w∥ 2 and write2np + log 2 δ max 1, log √ n∥w∥ ∞ ∥w∥ 2 • ∥w∥ ∞ = 2np + log 2 δ max 1, log √ n∥w∥ ∞ ∥w∥ 2 • √ n ∥w∥ ∞ ∥w∥ 2 • ∥w∥ 2 √ n ≤ 2np + log 2 δ log log n • log n n • ∥w∥ 2 ≤ 2np + log 2 δ log log n • log n n • C A.19 ∥u 2 ∥ ∞ + 1 log ( n /δ) = C A.19 2np + log 2 δ log log n • log n n ∥u 2 ∥ ∞ + 2np + log 2 δ √ n • log log n .All of this tells us thata v -a ⋆ v , u (v) 2 -u ⋆ 2 ≤ 4C A.19 • (np + log ( 1 /δ)) ∥u 2 ∥ ∞ log log n + 1 √ n log log n .It remains to handle the term∥a v -a ⋆ v ∥ 2 • ∥u 2 ∥ ∞ . Indeed, using Lemma A.13, we have with probability ≥ 1 -δ that ∥a v -a ⋆ v ∥ 2 • ∥u 2 ∥ ∞ ≤ C A.13 log ( 1 /δ) log n 3/2 np • ∥u 2 ∥ ∞ .Combining everything tells us that|⟨a v -a ⋆ v , u 2 -u ⋆ 2 ⟩| ≤ C A.13 log ( 1 /δ) log n 3/2 np • ∥u 2 ∥ ∞ + 4C A.19 • (np + log ( 1 /δ)) ∥u 2 ∥ ∞ log log n + 1 √ n log log n ≤ C (np + log ( 1 /δ)) ∥u 2 ∥ ∞ log log n + 1 √ n log log n .Taking a union bound over all v ∈ V concludes the proof of Lemma A.21.Finally, we establish an upper-bound on ∥u 2 ∥ ∞ . This will be used repeatedly in the proof of Theorem 1.Lemma A.22. In the same setting as Theorem 1, with probability ≥ 1-δ, we have for some constantC(α, δ) that ∥u 2 ∥ ∞ ≤ C(α, δ) √ n .Proof of Lemma A.22. First, observe that(D -A)u 2 = λ 2 u 2 ,which means that(D -λ 2 I) -1 Au 2 = u 2 .By Lemma A.7, with probability ≥ 1δ, for all v ∈ V we haved[v] -λ 2 ≥ n(p -q) 4 .Combining with Lemma A.6, we haved in [v] -d out [v] d in [v] -d out [v] + (2d out [v] -λ 2 ) = 1 - 2d out [v] -λ 2 d in [v] -d out [v] + (2d out [v] -λ 2 ) ≤ 1 + C A.6 nq log ( n /δ) + log ( n /δ) d in [v] -d out [v] + (2d out [v] -λ 2 ) ≤ 1 + 4C A.6 nq log ( n /δ) + log ( n /δ) n(p -q) ≤ C ′ ,for some constant C ′ > 0, 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 ≥ 1δ that for all v ∈ V ,|⟨a ⋆ v , u ⋆ 2 -u 2 ⟩| d[v] -λ 2 ≤ p √ n d[v] -λ 2 • C A.17 log ( n /δ) ≤ C A.8 (α) • C A.17n log ( n /δ) . Now, using Lemma A.8 (and using Lemma A.7 to ensure that d[v]λ 2 > 0 for all v ∈ V ), we have∥u 2 ∥ ∞ = (D -λ 2 I) -1 Au 2 ∞ = (D -λ 2 I) -1 Au 2 -(D -λ 2 I) -1 Au ⋆ 2 + (D -λ 2 I) -1 Au ⋆ 2 ∞ ≤ (D -λ 2 I) -1 Au ⋆ 2 ∞ + (D -λ 2 I) -1 A(u ⋆ 2 -u 2 ) ∞ = max 1≤v≤n |⟨a v , u ⋆ 2 ⟩| d[v] -λ 2 + max 1≤v≤n |⟨a v , u ⋆ 2 -u 2 ⟩| d[v] -λ 2 = 1 √ n max 1≤v≤n |d in [v] -d out [v]| d[v] -λ 2 + max 1≤v≤n |⟨a v , u ⋆ 2 -u 2 ⟩| d[v] -λ 2 ≤ C √ n + max 1≤v≤n |⟨a v -a ⋆ v , u ⋆ 2 -u 2 ⟩| d[v] -λ 2 + max 1≤v≤n |⟨a ⋆ v , u ⋆ 2 -u 2 ⟩| d[v] -λ 2 ≤ C √ n + C A.21 (np + log ( 1 /δ)) d[v] -λ 2 • 1 √ n log log n + ∥u 2 ∥ ∞ log log n + C A.8 (α) • C A.17 n log ( n /δ) ≤ C √ n + C A.21 • C A.8 (α) • 1 √ n log log n + ∥u 2 ∥ ∞ log log n + C A.8 (α) • C A.17n log ( n /δ) .Note that any n large enoughC A.21 • C A.8 (α) • ∥u 2 ∥ ∞ log log n ≤ ∥u 2 ∥ ∞ 2 .Thus, rearranging and solving for ∥u 2 ∥ ∞ yields∥u 2 ∥ ∞ ≤ 2 C √ n + C A.21 • C A.8 (α) • 1 √ n log log n + C A.8 (α) • C A.17 n log ( n /δ) ,completing the proof of Lemma A.22.In this section, we prove our main positive results Theorem 1 and Theorem 2. It will be helpful to recall the proof sketches given in Section 3 while reading this section.At a high level, the proof plan is as follows.1. We first establish a sufficient condition for a particular vertex to be classified correctly. We can think of this as simultaneously showing that the intermediate estimator (Dλ 2 I) -1 Au ⋆ 2 is strongly consistent and that the corresponding "noise" term(D -λ 2 I) -1 A(u ⋆ 2 -u 2) is a lower-order term in comparison to this. For a 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 |⟨a v , u ⋆ 2 -u 2 ⟩|. This is where we will have to use the leave-one-out method to decouple the dependence between a v and u 2 . The relevant lemmas for the leave-one-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.The main result of this subsection is Lemma A.23, which gives a general condition under which a particular vertex will be classified correctly. The proofs of Theorem 1 and Theorem 2 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 v ∈ V be some vertex. If d[w] -λ 2 > 0 for all w ∈ V , d in [v] > d out [v],and|⟨a v , u ⋆ 2 -u 2 ⟩| ≤ (d in [v] -d out [v])/ √ n, then sign (u 2 [v]) = sign (u ⋆ 2 [v]), i.e., u 2 correctly classifies vertex v.The goal of the rest of this section is to prove Lemma A.23.Our approach is to study the intermediate estimator(D -λ 2 I) -1 Au ⋆ 2 .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 u 2 in ℓ ∞ norm with high probability. Deng, Ling, and Strohmer [DLS21] used this intermediate estimator to prove the strong consistency of unnormalized spectral bisection for SBM(n, p, q) instances.Next, we show that this estimator is consistent and prove Lemma A.23.u 2 = (D -λ 2 I) -1 Au ⋆ 2 -(D -λ 2 I) -1 A (u ⋆ 2 -u 2 ) . Without loss of generality, suppose v ∈ P 1 . In particular, this means that u ⋆ 2 [v] = 1/ √ n.Our goal is to show that u 2 [v] > 0. And, as per the above, this means that it is enough to show that(D -λ 2 I) -1 Au ⋆ 2 [v] ≥ (D -λ 2 I) -1 A (u ⋆ 2 -u 2 ) [v],or equivalently, using the fact thatd[v] -λ 2 > 0, ⟨a v , u ⋆ 2 ⟩ ≥ ⟨a v , u ⋆ 2 -u 2 ⟩, where a v denotes the v-th row of A. To see that the above holds, use the fact that we know thatd in [v] -d out [v] > 0, which gives ⟨a v , u ⋆ 2 ⟩ = d in [v] -d out [v] √ n ≥ |⟨a v , u ⋆ 2 -u 2 ⟩| ≥ ⟨a v , u ⋆ 2 -u 2 ⟩ .This is exactly what we needed, and we conclude the proof of Lemma A.23.At this point, we are ready to prove our main results.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 ≤ p and such that α := p/(pq) is an arbitrary constant. Let D ∈ NSSBM(n, p, p, q). Let n ≥ N (α) where the function N (α) only depends on α. There exists a universal constant C > 0 such that ifEQUATIONthen unnormalized spectral bisection is strongly consistent on D.Proof of Theorem 1. As mentioned in Section 2, we actually prove a slightly stronger statementwe will allow the adversary to set at most np/ log log n of the p vw to 1 per vertex v (in other words, the adversary can commit to at most np/ log log n edges per vertex that are guaranteed to appear in the final graph).Our plan is to apply Lemma A.23. In order to do so, we start with that for all v, we haved in [v] > d out [v]. By Lemma A.5, with probability ≥ 1δ, we haved in [v] -d out [v] ≥ n(p -q) 2 -C A.5 np log ( n /δ) + log ( n /δ) > 0.Additionally, by Lemma A.7, we have for allv that d[v] > λ 2 .The final item we need is to show that for all v ∈ V , we have|⟨a v , u ⋆ 2 -u 2 ⟩| ≤ |⟨a v , u ⋆ 2 ⟩|. Observe that |⟨a v , u ⋆ 2 -u 2 ⟩| ≤ |⟨a ⋆ v , u ⋆ 2 -u 2 ⟩| + |⟨a v -a ⋆ v , u ⋆ 2 -u 2 ⟩| , where a ⋆ v denotes the v-th row of E [A].We handle the terms one at a time. First, note that by Lemma A.11, with probability ≥ 1δ, we haveλ 3 -λ ⋆ 2 ≥ n(p -q) 4 . Now, let E := L -E [L], and let a ⋆ v [rand] ∈ R V correspond to the vector that entrywise agrees with a ⋆ v wherever a ⋆ v is not 1 and is zero elsewhere. This corresponds to the edges incident to v that will be sampled randomly from the distribution over graphs. This means that for all n ≥ N (δ) and choosing δ ≥ 1/n 3 , we have|⟨a ⋆ v [rand], u ⋆ 2 -u 2 ⟩| ≤ ∥a ⋆ v [rand]∥ 2 • √ 2 ∥Eu ⋆ 2 ∥ 2 |λ 3 -λ ⋆ 2 | ( Lemma A.16) ≤ p √ n • 4 √ 2C A.12 √ nq + (nq log n) 1/4 + √ log n n(p -q)(Lemmas A.11 and A.12)≤ 100C A.12 np √ n log log n (gap in Theorem 1)To handle the oblivious insertions, let d det ∈ R V denote the degree vector that counts the number of deterministic edges inserted incident to v, for all v ∈ V . Under this notation, we have|⟨a ⋆ v -a ⋆ v [rand], u ⋆ 2 -u 2 ⟩| ≤ d det [v] • ∥u 2 -u ⋆ 2 ∥ ∞ ≤ np √ n log log n + np ∥u 2 ∥ ∞ log log n .where the last inequality follows from using∥u 2 -u ⋆ 2 ∥ ∞ ≤ ∥u 2 ∥ ∞ + ∥u ⋆ 2 ∥ ∞ . Combining yields |⟨a ⋆ v , u ⋆ 2 -u 2 ⟩| ≤ C ′ np √ n log log n + np ∥u 2 ∥ ∞ log log n ,for some constant C ′ > 0. Now, notice that for all n sufficiently large,|⟨a v -a ⋆ v , u ⋆ 2 -u 2 ⟩| ≤ C A.21 (np + log ( 1 /δ)) ∥u 2 ∥ ∞ log log n + 1 √ n log log n (Lemma A.21) ≤ C A.21 (np + log ( 1 /δ))   C A.22 (α,δ) √ n log log n + 1 √ n log log n   (Lemma A.22) ≤ C 1 (α, δ) • (np + log ( 1 /δ)) √ n log log n .Adding yields for n ≥ N (α, δ),|⟨a v , u ⋆ 2 -u 2 ⟩| ≤ |⟨a ⋆ v , u ⋆ 2 -u 2 ⟩| + |⟨a v -a ⋆ v , u ⋆ 2 -u 2 ⟩| ≤ C 2 (α, δ) • (np + log ( 1 /δ)) √ n log log n ≤ 1 √ n • n(p -q) 2 -C A.5 np log ( n /δ) + log ( n /δ) (gap condition) ≤ d in [v] -d out [v] √ n = |⟨a v , u ⋆ 2 ⟩| ,which means we satisfy the conditions required by Lemma A.23. Taking a union bound over all our (constantly many) probabilistic statements, setting δ = Θ(1/n), and rescaling completes the proof of Theorem 1.For convenience, we reproduce the statement of Theorem 2 here.Theorem 2. Let q be a probability and d in be an integer, and let D ∈ DCM(n, d in , q). For G ∼ D, let L denote the expectation of L after step (2) but before step (3) in Model 2. There exists constants C 1 , C 2 , C 3 > 0 such that for all n sufficiently large, ifd in ≥ C 1 • nq 2 + √ n and λ 3 ( L) -λ 2 ( L) ≥ √ n + C 2 nq + C 3 nq log n + log n ,then unnormalized spectral bisection is strongly consistent on D.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 (cross) denote the Laplacian matrix corresponding to the cross edges, so we can writeL ⋆ = L -L (cross) + E L (cross) . Although L ⋆ ̸ = E [L]due to the adaptive adversary, by Lemma A.14, we still haveL ⋆ u ⋆ 2 = λ ⋆ 2 u ⋆ 2 = nqu ⋆ 2 . Moreover, (L -L ⋆ )u ⋆ 2 is the vector whose entries are of the form 2(d out [v] -E [d out [v]])/ √ n.Thus, we will be able to apply Lemma A.16 and Lemma A.12 later on. Finally, observe thatλ i (L ⋆ ) ≥ λ i ( L) for all i ≥ 3 and λ 2 ( L) = λ 2 (L ⋆ ) = nq. Thus, one can use the spectral gap λ 3 ( L) -λ 2 ( L) to reason about λ ⋆ 3 -λ ⋆ 2 .Let δ ≥ 1/n 3 . We will apply Lemma A.23 to get strong consistency. First, let us verify that d[v] > λ 2 for all v. Applying Lemma A.10 to the matrix L (cross) gives∥L -L ⋆ ∥ op = L (cross) -E L (cross) op ≤ C A.10nq log ( n /δ) + log(n/δ) .Thus, using Weyl's inequality, for n > N (δ), we haved[v] -λ 2 ≥ d in [v] -λ ⋆ 2 -∥L -L ⋆ ∥ op ≥ C 1 nq 2 + C 1 √ n -nq -C A.10 nq log ( n /δ) + log(n/δ) > 0.Next, we verify thatd in [v] > d out [v]for all v. By Lemma A.3, with probability ≥ 1δ, for all v ∈ V , we haved out [v] - nq 2 ≤ C A.3 nq log ( n /δ) + log ( n /δ) .So for n > N (δ), we obtaind in [v] -d out [v] ≥ C 1 nq 2 + C 1 √ n - nq 2 -C A.3 nq log ( n /δ) + log ( n /δ) > 0.Here, in the last inequality we used the fact that nq log ( n /δ) ≤ max{nq, log(n/δ)} .Finally, we need to show that for all v ∈ V ,|⟨a v , u ⋆ 2 -u 2 ⟩| ≤ |⟨a v , u ⋆ 2 ⟩| = d in [v] -d out [v] √ n .By Cauchy-Schwarz, we have|⟨a v , u ⋆ 2 -u 2 ⟩| ≤ ∥a v ∥ 2 • ∥u ⋆ 2 -u 2 ∥ 2 = d in [v] + d out [v] • ∥u ⋆ 2 -u 2 ∥ 2 . Thus, it is enough to show that for all v ∈ V we get √ n ∥u ⋆ 2 -u 2 ∥ 2 ≤ d in [v] -d out [v] d in [v] + d out [v] .Observe that the RHS above is a decreasing function in d out [v] and an increasing function ind in [v].Now, by Lemma A.16 and Lemma A.12, we haveEQUATIONWe now do casework on the value of q.Case 1: q ≤ log ( n /δ) /n. Carrying on from (9) and applying Lemma A.10 (we can set p ij for the deterministic internal edges to 0 as they do not affect L -E [L]) along with Weyl's inequality, for all n ≥ N (δ) we have√ n ∥u ⋆ 2 -u 2 ∥ 2 ≤ 18C A.12 n log ( n /δ) |λ 3 -λ ⋆ 2 | ≤ 18C A.12 n log ( n /δ) √ n -3C A.10 log ( n /δ) ≤ C log ( n /δ) ≪ d in [v] -d out [v] d in [v] + d out [v] ,as required. Here the last inequality follows using the fact thatd in [v] ≥ C 1 nq 2 + √ n and d out [v] ≤ nq 2 + 2C A.3 log(n/δ).Case 2: log ( n /δ) /n ≤ q. Similar to the previous case, we getEQUATIONEQUATION)Additionally, we can use the conclusion of Lemma A.3 to write with probability ≥ 1δ for all v ∈ V and n ≥ N (δ) thatEQUATION)From this, it is clear that one can choose constants C 1 and C 2 such that (11) is at most (13). This means we may conclude the proof of Theorem 2.In this section, we design a family of problem instances on 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 is strongly consistent whereas normalized spectral bisection (both symmetric and random-walk) incurs a misclassification rate of at least 24% with probability 1 -1/n.We first state the family of instances on which we will prove our inconsistency results. Let n be a multiple of 4. Let L 1 consist of indices 1, . . . , n/4, L 2 consist of indices n/4 + 1, . . . , n/2, and R consist of indices n/2 + 1, . . . , n.As mentioned in Section 3, consider the following block structure determined by the A ⋆ written below, where q < p and K ≥ 3p/q.L 1 L 2 R L 1 Kp • n/4×n/4 p • n/4×n/4 q • n/2×n/2 L 2 p • n/4×n/4 Kp • n/4×n/4 R q • n/2×n/2 p • n/2×n/2Table 2: A ⋆ is defined to have the above block structure.We will draw our instances from the nonhomogeneous stochastic block model according to the probabilities prescribed above. Note that within the two clusters L := L 1 ∪ L 2 and R, each edge appears with probability at least p. Moreover, each edge in L × R appears with probability exactly q. However, there are also two subcommunities L 1 and L 2 that appear within L. Furthermore, observe that unnormalized spectral bisection is consistent on this family of examples with probability ≥ 1 -1/n by Theorem 1.First, we construct L ⋆ .Lemma A.24. Let L ⋆ be the normalized Laplacian constructed from A ⋆ and the corresponding D ⋆ . Then, I -L ⋆ has the following block structure.L 1 L 2 R L 1 Kp n 2 •(p• K+1 2 +q) • n/4×n/4 p n 2 •(p• K+1 2 +q) • n/4×n/4 q n 2 •(p• K+1 2 +q)• n 2 •(p+q) • n/2×n/2 L 2 p n 2 •(p• K+1 2 +q) • n/4×n/4 Kp n 2 •(p• K+1 2 +q) • n/4×n/4 R q n 2 •(p• K+1 2 +q)• n 2 •(p+q) • n/2×n/2 p n 2 •(p+q) • n/2×n/2Proof of Lemma A.24. It is easy to see that for any v ∈ L, we haved ⋆ [v] = n 2 • p • K+1 2 + q and for any v ∈ R, we have d ⋆ [v] = n 2 • (p + q).Lemma A.24 follows by noting that every element ofI -L ⋆ is of the form a ⋆ i [j]/ d ⋆ [i]d ⋆ [j].Next, we analyze the eigenvalues and eigenvectors of L ⋆ .We now address u ⋆ 3 . The first n/2 entries of (I -L ⋆ )u ⋆ 3 aren 4 • Kp n 2 • p • K+1 2 + q + n 4 • p n 2 • p • K+1 2 + q + n 2 •   q • -p(K+1)+2q 2(p+q) n 2 • p • K+1 2 + q • n 2 • (p + q)   = (K + 1)p (K + 1)p + 2q +   q • - 1 p+q √ p + q   = (K + 1)p (K + 1)p + 2q - q p + q = λ ⋆ 3 ,and the second n/2 entries of (I -L ⋆ )u ⋆ 3 aren 2 • q n 2 • p • K+1 2 + q • n 2 • (p + q) + n 2 • p n 2 • (p + q) • - p(K + 1) + 2q 2(p + q) = q p • K+1 2 + q (p + q) - p (p + q) • p(K + 1) + 2q 2(p + q) = - p(K + 1) + 2q 2(p + q) -2q p(K + 1) + 2q + p p + q = y -• λ ⋆ 3 .Finally, it remains to check that 1 > λ ⋆ 2 > λ ⋆ 3 > 0. The fact that λ ⋆ 2 < 1 easily follows from using p + q > 0. To prepare to bound λ ⋆ 2λ ⋆ 3 , we first use p ≥ q to establish p 2pq + 2q 2 = p(pq) + 2q 2 ≥ 2q 2 . This impliespq(K -1) + 2q 2 ≥ 3p 2 -pq + 2q 2 = 2p 2 + (p 2 -pq + 2q 2 ) ≥ 2p 2 + 2q 2 ,which rearranges to p 2 (K + 1) + pq(K + 3) + 2q 2 ≥ p 2 (K + 3) + 4pq + 2q 2 .Next, we writeλ ⋆ 2 -λ ⋆ 3 = (K -1)p 2 p • K+1 2 + q --1 + p 1 p + q + K + 1 p(K + 1) + 2q = 1 - p p + q - 2p p(K + 1) + 2q = 1 - p 2 (K + 1) + 2pq + 2p 2 + 2pq (p + q)(p(K + 1) + 2q) = 1 - p 2 (K + 3) + 4pq p 2 (K + 1) + pq(K + 3) + 2q 2 ≥ 1 - p 2 (K + 3) + 4pq p 2 (K + 3) + 4pq + 2q 2 > 0.Finally, to show λ ⋆ 3 > 0, we writeλ ⋆ 3 + 1 = p p + q + p(K + 1) p(K + 1) + 2q > 2p p + q > 1,which allows us to complete the proof of Lemma A.25.We are now ready to prove the inconsistency of normalized spectral bisection on the nested block examples.Proof of Theorem 3. Let G be a graph drawn from the nested block example. We choose p and q such that p ≳ log n/n and p/q = α ≥ 2 where α is some constant and such that p and q both satisfy the conditions of Theorem 1. Let K ≥ 3α. Observe that the true communities are L and R. We will show that bisection based on u 2 of I -L (corresponding to the eigenvector associated with the second smallest eigenvalue of L) will attain a large misclassification rate. In particular, based on our calculation in Lemma A.25, we expect that u 2 will output a bisection that places L 1 and L 2 into separate clusters. On the other hand, by Theorem 1, for all n large enough, the unnormalized spectral bisection algorithm will be strongly consistent.First, observe that it is enough to prove the inconsistency result just for the symmetric normalized Laplacian. Indeed, observe that if u 2 is an eigenvector of I -L = D -1/2 AD -1/2 , then we haveλ 2 D -1/2 u 2 = D -1 AD -1/2 u 2 = D -1 A(D -1/2 u 2 ),which shows that D -1/2 u 2 must be the eigenvector of the random-walk normalized Laplacian I -D -1 A corresponding to eigenvalue λ 2 . Since D is a positive diagonal matrix, it does not change the signs of u 2 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 ∥L -L ⋆ ∥ op , and a bound on the gap λ ⋆ 2λ 3 . Let d min be the minimum degree of the graph given by adjacency matrix A and let d ⋆ min be the minimum weighted degree of the graph given by the adjacency matrix A ⋆ . First, using [DLS21, Theorem 3.1], we have with probability 1n -r for some constant r ≥ 1 and constants C(r) and C (the latter of which does not depend on r), for all n sufficiently large,∥L -L ⋆ ∥ op ≤ C(r) n max (i,j) p ij 5/2 min {d min , d ⋆ min } 3 ≤ C(r) (n • Kp) 5/2 min n(p + q)/2, n(p + q)/2 -C n(p + q) log n 3 ≤ C 1 (r, α)K 5/2 (np) 5/2 (np) 3 = C 1 (r, α)K 5/2 √ np .Next, we haveλ ⋆ 2 -λ 3 = (λ ⋆ 2 -λ ⋆ 3 ) + (λ ⋆ 3 -λ 3 ) ≥ 1 - p 2 (K + 3) + 4pq p 2 (K + 3) + 4pq + 2q 2 - C 1 (r, α)K 5/2 √ np ≥ C g (α, K),where the last line denotes a positive constant depending on q and K (this constant will always be positive for sufficiently large n, as we showed that λ ⋆ 2λ ⋆ 3 > 0 in Lemma A.25). Putting everything together, we get by the Davis-Kahan theorem that some signing of u 2 satisfies∥u 2 -u ⋆ 2 ∥ 2 ≤ ∥L -L ⋆ ∥ op min {|λ ⋆ 2 -λ 3 | , 1 -λ ⋆ 2 } ≤ C 2 (r)K 5/2 C g (α, K) √ np ≤ C(r, α, K) √ np .Now, consider the subset of coordinates of u 2 belonging to L 1 . Suppose m of these coordinates do not agree in sign with u ⋆ 2 . To maximize m, each of these coordinates in u 2 should be 0, which means the total ℓ 2 error can be bounded as∥u 2 -u ⋆ 2 ∥ 2 2 = m 1 n /2 2 ≤ C(r, α, K) 2 np .This means the number of coordinates m on which u 2 and u ⋆ 2 disagree on is at most n• C(r, α, K) 2 2np ,and therefore the misclassification rate of u 2 with respect to the true labeling induced by L and R must be at leastn 4 -n•C(r,α,K) 2 2np n = 1 4 - C(r, α, K) 2 2np .Since p ≳ log n/n, this completes the proof of Theorem 3.Figure 2 : Agreement with the planted bisection of the bipartition obtained from unnormalized spectral 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 p = 1/2, the right plot uses p = 1. The solid red curves plot the function p thr (q) (see ( 14)), and the dashed red curves plot the function p info (q) (see ( 15)).In this section, we show more numerical trials that complement those discussed in Section 4.In Section 4, we 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 q.Setup.Let us fix n = 2000, p ∈ {1/2, 1}. For varying p, q in the range [1/n, 9/20] such that p > q, we sample t = 3 independent draws G from the same benchmark distribution D p,p,q used in Section 4. For each of them, we compute the agreement the bipartition obtained by unnormalized spectral bisection with respect to the planted bisection. For each (p, q), we plot the average agreement across the t independent draws. The results are shown in Fig. 2 , where in the left and right plot we ran the experiments with p = 1/2 and p = 1 respectively. The lower diagonal of these plots, where p ≤ q, is artificially set to 0. Theoretical framing. According to Theorem 1, fixing the value of p ∈ {1/2, 1}, we obtain that unnormalized spectral bisection achieves exact recovery provided that for q ∈ [1/n, 9/20] one has p ≥ p thr (q) wherep thr (q) = √ p log n √ n + q (14)is obtained by rearranging the precondition of Theorem 1, ignoring the constants, and disregarding the fact that α should be O(1). The solid red curve in Fig. 2 plots p thr (q) as a function of q. For comparison, the information-theoretic threshold for SSBM [ABH16] demands that p ≥ p info (q) whereEQUATION)The dashed red curve in Fig. 2 plots p info (q) as a function of q.Empirical evidence. From Fig. 2 , one can see that our experiments reflect the behavior predicted by Theorem 1 quite closely, although empirically we achieve 100% agreement slightly above p thr (q) (i.e. the solid red curve). However, this is likely due to the constant factors from Theorem 1 that we ignored, and also n = 2000 is plausibly too small to show asymptotic behaviors. Nevertheless, we do achieve 100% agreement consistently as soon as we surpass the information-theoretic threshold p info (q): in the regime of our experiment, it appears that the unnormalized Laplacian is robust all the way to the optimal threshold for exact recovery in the SSBM.Figure 3 : Agreement with the planted bisection of the bipartition obtained from several matrices associated with an input graph generated from a distribution D G1,G2 q ∈ DCM(n, d in , q) for fixed values of n, q and varying the size of the planted clique S. In the left plot, the bipartition is the 0-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.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 are conceptually different than those considered in Section 4.Benchmark distribution. Let n be divisible by 4 and let {P 1 , P -2} be a partitioning of V = [n] into two equally-sized subsets. Fix p ∈ [0, 1]. For some set S ⊆ P 1 such that S = {1, . . . , |S|} (for simplicity), let G 2 = (P 2 , E 2 ) ∼ ER(n/2, p) be a graph drawn from the Erdős-Rényi distribution with sampling rate p, and let G 1 = (P 1 , E 1 ) ∼ ERPC(n/2, p, S) be also a graph drawn from the Erdős-Rényi distribution with sampling rate p where we additionally plant a clique on the vertices S. Fixing G 1 , G 2 , for q ∈ [0, 1] we consider the distribution D G1,G2 q over graphs G = (V, E) where G[P 1 ] = G 1 , G[P 2 ] = G 2 , and every edge (u, v) ∈ P 1 × P 2 is sampled independently with probability q. One can see that D G1,G2 q is in fact in the set DCM(n, d in , q) for some d in .Let us fix n = 2000, p = 9/ √ n, q = 1/ √ n. For varying values of |S| in the range [|P 1 |/10, |P 1 |], we sample G 1 = (P 1 , E 1 ) ∼ ERPC(n/2, p, S) and G 2 = (P 2 , E 2 ) ∼ ER(n/2, p), and then draw t = 10 independent samples G from D G1,G2 q . For each sample G, we run spectral bisection (i.e. Algorithm 1) with matrices L, L sym , L rw , A. Then, we compute the agreement of the bipartition hence obtained with respect to the planted bisection, and average it out across the t independent draws. The results are shown in the left plot of Fig. 3 . Again, another natural way to get a bipartition of V from the eigenvector is a sweep cut, and the average agreements that this results in are shown in the right plot of Fig. 3 .Ignoring the constants, Theorem 2 guarantees that exact recovery is achieved by unnormalized spectral bisection as long asd in ≥ nq + √ n and λ 3 ( L) -λ 2 ( L) ≥ √ n + nq + √ nq log n + log n,where L is the expected Laplacian of D G1,G2 q . For each clique size that we consider, Fig. 4 shows the minimum in-cluster degree of the graphs G 1 , G 2 that we draw (in the left plot), and the spectral gap λ 3 ( L)λ 2 ( L). The red horizontal lines in the left and right plot respectively correspond to the value of nq + √ n and √ n + nq + √ nq log n + log n on the y-axis, indicating the lower bound on d in and λ 3 ( L)λ 2 ( L) demanded by Theorem 2.Empirical evidence: consistency.From Fig. 4 , one can see that all the distributions D G1,G2 q that we use roughly meet the requirement of Theorem 2. Indeed, in the left plot of Fig. 3 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 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.Empirical evidence: example embedding.Let us fix the value |S| = 800 for the size of the planted clique, for which we see in Fig. 3 that the adjacency matrix fails to recover the planted bisection. We generate a graph from a distribution D G1,G2 q with clique size |S| = 800, 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. 5 , where the three horizontal dashed lines, from top to bottom, respectively correspond to the value of 1/ √ n, 0, -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/ √ n, and in fact the vertices {1, . . . , 800} ⊆ P 1 where we plant the clique concentrate even more around 1/ √ n. This is a phenomenon related to the one illustrated by Fig. 1 . Finally, one can see from the embedding that splitting vertices around 0 does result in misclassifying a fraction of the vertices for the adjacency matrix. However, taking a 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 . (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
open access to data and code: 
 Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes]Justification: We have uploaded our experimental code with our submission.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: Please see Section 4 and Appendix B.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: It would be computationally expensive to do so, especially for large graph sizes n. Decreasing n is not feasible because for small values of n, the asymptotic convergence of the algorithms is not evident.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: Please see 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 or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is a theoretical paper on the robustness of a common unsupervised learning algorithm.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific 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 out 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 as 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 or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This is a theoretical paper on the robustness of a common unsupervised learning algorithm.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines 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 a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [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 or dataset.• 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 equivalent) 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 we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: (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. 

(2) Limited to bi-partitioning.
questions: 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.  

(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.

(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? 

(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: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: Sharp constants are not given.
questions: questions: Could you please give an indication of which parts of your analysis could be tightened to yield sharp constants?
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: (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). 

(2) A comparison of the conditions of strong consistency for NSSBM with the existing model should help understand the paper better.
questions: 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: limitations: N/A
paper_summary: paper_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.

The 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.
strength_weakness: strength_weakness: 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. 



The 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.
questions: questions: .
limitations: limitations: Yes

Comments: title: Thanks
Acknowledgement of rebuttal
comment: Thanks for pointing this out, we will add a pointer to this classic reference in the camera-ready version. However, note that the work only guarantees weak recovery and also assumes that $k$-means can be solved optimally, so the regime is different from ours.
Thanks for your replies. Regarding allowing the number of clusters to grow: Check 
"Spectral clustering and the high-dimensional stochastic blockmodel" by  Karl Rohe, Sourav Chatterjee, Bin Yu
Thanks for your reply. I happily maintain my current evaluation.
Thank you for the response and addressing my concerns/questions.  I still think it would be very interesting and potentially impactful to see how the proposed algorithms perform on real-world graphs!
Thank you for the clarifications!