Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery

Introduction

Community detection is an important problem in statistics, theoretical computer science and image processing. A widely studied theoretical model in this area is the stochastic block model. In the simplest case, there are two blocks $V_{1},V_{2}$ each of size of $n$; one considers a random graph generated from the following distribution: an edge between vertices belonging to the same block appears with probability $\frac{a}{n}$ and an edge between vertices across different blocks appear with probability $\frac{b}{n}$, where $a>b>0$. Given an instance of this graph, we would like to identify the two blocks as correctly as possible. Our paper will deal with the general case of $k\geq 2$ blocks, but for the sake of simplicity, let us first focus on $k=2$.

For $k=2$, the problem can be seen as a variant of the well known hidden bipartition problem, which has been studied by many researchers in theoretical computer science, starting with the work of [BCLS87]; (see [DF89] [Bop87] [JS93] [McS01] and the references therein for further developments). In these earlier papers, $a$ and $b$ are large (at least $\log n$) and the goal is to recover both blocks completely. It is known that one can efficiently obtain a complete recovery if $\frac{(a-b)^{2}}{a+b}\geq C\frac{\log n}{n}$ and $a,b\geq C\log n$ for some sufficiently large constant $C$ (see, for instance [Vu14]).

In the stochastic block model problem, the graph is sparse with $a$ and $b$ being constants. Classical results from random graph theory tell us that in this range the graph contains, with high probability, a linear portion of isolated vertices [Bol01]. Apparently, there is no way to tell these vertices apart and so a complete recovery is out of question. The goal here is to recover a large portion of each block, namely finding a partition $V_{1}^{\prime}\cup V_{2}^{\prime}$ of $V=V_{1}\cup V_{2}$ such that $V_{i}$ and $V_{i}^{\prime}$ are close to each other. For quantitative purposes, let us introduce a definition

A collection of subsets $V_{1}^{\prime},V_{2}^{\prime}$ of $V_{1}\cup V_{2}$ is $\gamma$-correct if $|V_{i}\cap V_{i}^{\prime}|\geq(1-\gamma)n$.

For any constant $\gamma>0$ there are constants $d_{0},C>0$ such that if $a,b>d_{0}$ and $\frac{(a-b)^{2}}{a+b}>C\log(a+b)$, one can find a $\gamma$-correct partition using a polynomial time algorithm.

Coja-Oglan proved Theorem 1.2 as part of a more general problem, and his algorithm was rather involved. Furthermore, the result is not yet sharp and it has been conjectured that the $\log$ term is removable We would like to thank E. Abbe for communicating this conjecture.. Even when the log term is removed, an important question is to find out the optimal relation between the accuracy $\gamma$ and the ratio $\frac{(a-b)^{2}}{a+b}$. This is the main goal of this paper.

There are constants $C_{0}$ and $C_{1}$ such that the following holds. For any constants $a>b>C_{0}$ and $\gamma>0$ satisfying

we can find a $\gamma$-correct partition with probability $1-o(1)$ using a simple spectral algorithm.

The constants $C_{0},C_{1}$ can be computed explicitly via a careful, but rather tedious, book keeping. We try not to optimize these constants to simplify the presentation. The proof of Theorem 1.3 yields the following corollary

There are constants $C_{0}$ and $\epsilon$ such that the following holds. For any constants $a>b>C_{0}$ and $\epsilon>\gamma>0$ satisfying

we can find a $\gamma$-correct partition with probability $1-o(1)$ using a simple spectral algorithm.

In parallel to our study, [ZZ] , proving a minimax rate result that suggested that there is a constant $c>0$

then one cannot recover a $\gamma$-correct partition (in expectation), regardless the algorithm.

In order to prove Theorem 1.3, we design a fast and robust algorithm which obtains a $\gamma$-correct partition under the condition $\frac{(a-b)^{2}}{a+b}\geq C\log\frac{1}{\gamma}$. Our algorithm guarantees $\gamma$-correctness with high probability.

We can refine the algorithm to handle the (more difficult) general case of having $k$ blocks, for any fixed number $k$. Suppose now there are $k$ blocks $V_{1},...,V_{k}$ with $|V_{i}|=\frac{n}{k}$ with edge probabilities $\frac{a}{n}$ between vertices within the same block and $\frac{b}{n}$ between vertices in different blocks. As before, a collection of subsets $V_{1}^{\prime},V_{2}^{\prime},..,V_{k}^{\prime}$ of $V_{1}\cup V_{2}\cup...\cup V_{k}$ is $\gamma$-correct if $|V_{i}\cap V_{i}^{\prime}|\geq(1-\gamma)\frac{n}{k}$.

There exists constants $C_{1},C_{2}$, such that if $k$ is any constant as $n\to\infty$ and if

$(a-b)^{2}\geq C_{2}k^{2}a\log\frac{1}{\gamma}$,

then we can find a $\gamma$-correct partition with probability at least $1-o(1)$ using a simple spectral algorithm.

We believe that this result is sharp, up to the values of $C_{1}$ and $C_{2}$; in particular, the requirement $\frac{(a-b)^{2}}{a}=\Omega(k^{2})$ is optimal.

Our method also works (without significant changes) in the case the blocks are not equal, but have comparable sizes (say $cn\geq|V_{i}|\geq n$ for some constant $c\geq 1$). In this case, the constants $C_{1},C_{2}$ above will also depend on $c$. While the emphasis of this paper is on the case $a,b$ are constants, we would like to point out that this assumption is not required in our theorems, so our algorithms work on denser graphs as well.

Let us now discuss some recent works, which we just learned after posting the first version of this paper on arxiv. Mossel informed us about a recent result in [MNS13b] which is similar to Theorem 1.3 (see [MNS13b, Theorem 5.3]). They give a polynomial time algorithm and prove that there exists a constant $C$ such that if $(a-b)^{2}>C(a+b)$ and $a,b$ are fixed as $n\to\infty$, then the algorithm recovers an optimal fraction of the vertices. The algorithm in [MNS13b] is very different from ours, and uses non-back tracking walks. This algorithm doest not yet handle the case of more than 2 blocks, and its analysis looks very delicate. Next, Guedon sent us [GV14], in which the authors also proved a result similar to Theorem 1.3, under a stronger assumption $(a-b)^{2}\geq C\frac{1}{\gamma^{2}}(a+b)$ (see Theorem 1.1 and Corollary 1.2 of [GV14]). Their approach relies on an entirely different (semi-definite program) algorithm, which, in turn, was based on Grothendick’s inequality. This approach seems to extend to the general $k>2$ case; however, the formulation of the result in this case, using matrix approximation, is somewhat different from ours (see [GV14, Theorem 1.3]). Two more closely related papers have been brought to our attention by the reviewers. In [LMX13], authors have worked out the spectral part of the result in this paper.

It is remarkable to see so many progresses, using different approaches, on the same problem in such a short span of time. This suggests that the problem is indeed important and rich, and it will be really pedagogical to study the performance of the existing algorithms in practice. We are going to discuss the performance of our algorithm in Sections 3 and 4.

We next present an application of our method to the Censor Block Model studied by Abbe et. al. in [ABBS14]. As before, let $V$ be the union of two blocks $V_{1},V_{2}$, each of size $n$. Let $G=(V,E)$ be a random graph with edge probability $p$ with incidence matrix $B_{G}$ and $\boldsymbol{\mathit{x}}=(x_{1},...,x_{2n})$ be the indicator vector of $V_{2}$. Let $\boldsymbol{\mathit{z}}$ be a random noise vector whose coordinates $z_{e_{i}}$ are i.i.d $\text{Bernoulli}(\epsilon)$ (taking value $1$ with probability $\epsilon$ and $0$ otherwise), where $e_{i}$ are the edges of $G$.

where $\oplus$ is the addition in mod $2$, one would like identify the blocks. In [ABBS14], the authors proved that exact recovery ($\gamma=0$) is possible if and only if $\frac{np}{\log n}\geq\frac{2}{(1-2\epsilon)^{2}}+o(\frac{1}{(1-2\epsilon)^{2}})$ in the limit $\epsilon\to 1/2$. Further, they gave a semidefinite programming based algorithm which succeeds up to twice the threshold. They posed the question of partial recovery ($\gamma>0$) for sparse graphs. Addressing this question, we show

For any given constants $\gamma,1/2>\epsilon>0$, there exists constant $C_{1},C_{2}$ such that if $np\geq\frac{C_{1}}{(1-2\epsilon)^{2}}$ and $p\geq\frac{C_{2}}{n}$, then we can find a $\gamma$-correct partition with probability $1-o(1)$, using a simple spectral algorithm.

Let us conclude this section by mentioning a related, interesting, problem, where the purpose is just to do better than a random guess (in our terminology, to find a partition which is $(1/2+\epsilon)$-correct). It was conjectured in [DKMZ11] that this is possible if and only if $(a-b)^{2}>(a+b)$. This conjecture has been settled recently by Mossel et. al. [MNS12] [MNS13a] and Massoulie [Mas13] . Another closely related problem which has been studied in [ABH14] [MNS14] is about when one can recover at least $1-o(1)$ fraction of the vertices.

The rest of the paper is organized as follows. In section 2, we describe our algorithm for Theorem 2.1 and an overview of the proof. The full proof comes in sections 3. In section 4, we show how to modify the algorithm to handle the $k$ block case and prove theorem 1.5. Finally, in section 5, we prove theorem 1.6.

Two communitites

We first consider the case $k=2$. Our algorithm will have two steps. First we use a spectral algorithm to recover a partition where the dependence between $\gamma$ and $\frac{(a-b)^{2}}{a+b}$ is sub-optimal.

and eigenvector $\boldsymbol{\mathit{u}}_{2}$ corresponding to the eigenvalue $a-b$ has coordinates

Notice that the second eigenvector of $\bar{A}_{0}$ identifies the partition. We would like to use the second eigenvector of $A_{0}$ to approximately identify the partition. Since $A_{0}=\bar{A}_{0}+E_{0},$ perturbation theory tells us that we get a good approximation if $\left\|E_{0}\right\|$ is sufficiently small. However, with probability $1-o(1)$, the norm of ${E_{0}}$ is rather large (even larger than the norm of the main term). In order to handle this problem, we modify ${E_{0}}$ using the auxiliary deletion, at the cost of losing a few large degree vertices.

Let $\bar{A},A,E$ be the matrices obtained from $\bar{A}_{0},A_{0},E_{0}$ after the deletion, respectively. Let $\Delta\mathrel{\mathop{\kern 0.0pt=}\limits^{\text{d{}ef}}}\bar{A}-\bar{A}_{0}$; we have

The key observation is that $\left\|E\right\|$ is significantly smaller than $\left\|E_{0}\right\|$. In the next section we will show that $\left\|E\right\|=\mathcal{O}(\sqrt{d})$, with probability $1-o(1)$, while $\left\|E_{0}\right\|$ is $\Theta(\sqrt{\frac{\log n}{\log\log n}})$, with probability $1-o(1)$. Furthermore, we could show that $\left\|\Delta\right\|$ is only $\mathcal{O}(1)$ with probability $1-o(1)$. Therefore, if the second eigenvalue gap for the matrix $A_{0}$ is greater than $C\sqrt{d}$, for some large enough constant $C$, then Davis-Kahan $\sin\Theta$ theorem would allow us to bound the angle between the second eigenvector of $\bar{A}_{0}$ and $A$ by an arbitrarily small constant. This will, in turn, enable us to recover a large portion of the blocks, proving the following statement

There are constants $C_{0}$ and $C_{1}$ such that the following holds. For any constants $a>b>C_{0}$ and $\gamma>0$ satisfying $\frac{(a-b)^{2}}{a+b}\geq C_{1}\frac{1}{\gamma^{2}}$, then with probability $1-o(1)$, Spectral Partition outputs a $\gamma$-correct partition.

The parameter $d:=a+b$ can be estimated very efficiently from the adjacency matrix $A$. We take this as input for a simpler exposition.

Step 2 is a further correction that gives us the optimal (logarithmic) dependence between $\gamma$ and $\frac{(a-b)^{2}}{a+b}$. The idea here is to use the degree sequence to correct the mislabeled vertices. Consider a mislabeled vertex $u\in V_{1}^{\prime}\cap V_{2}$. As $u\in V_{2}$, we expect $u$ to have $b$ neighbors in $V_{1}$ and $a$ neighbors in $V_{2}$. Assume that Spectral Partition output $V_{1}^{\prime},V_{2}^{\prime}$ where $|V_{1}\backslash V_{i}^{\prime}|\leq 0.1n$, we expect $u$ to have at most $0.9b+0.1a$ neighbors in $V_{1}^{\prime}$ and at least $0.1b+0.9a$ neighbors in $V_{2}^{\prime}$. As

$0.1b+0.9a>\frac{a+b}{2}>0.9b+0.1a,$ we can correctly reclassify $u$ by thresholding. There are, however, few problems with this argument. First, everything is in expectation. This turns out to be a minor problem; we can use a large deviation result to show that a majority of mislabeled vertices can be detected this way. As a matter of fact, the desired logarithmic dependence is achieved at this step, thanks to the exponential probability bound in the large deviation result.

The more serious problem is the lack of independence. Once Spectral Partition has run, the neighbors of $u$ are no longer random. We can avoid this problem using a splitting trick as given in Partition. We sample randomly half of the edges of the input graph and used the graph formed by them in Spectral Partition. After receiving the first partition, we use the other (random) half of the edges for correction. This doesn’t make the two steps completely independent, but we can still prove the stated result.

The sub-routine Correction is as follows:

Figure 4 is the density plot of the matrix before and after clustering according to the algorithm described above. We can prove

Given a $0.1$-correct partition $V_{1}^{\prime},V_{2}^{\prime}$ and a Blue graph on $V_{1}^{\prime}\cup V_{2}^{\prime}$ as input to the subroutine Correction given in figure 3, we get a $\gamma$-correct partition with $\gamma=2\exp(-0.072\frac{(a-b)^{2}}{a+b}).$

First step: Proof of Theorem 2.1

We now turn to the details of the proof. Using the notation in the previous section, we let $W$ be the two dimensional eigenspace corresponding to the top two eigenvalues of ${\mathit{A}}$ and $\bar{W}$ be the corresponding space of $\bar{A}$. For any two vector subspaces $W_{1},W_{2}$ of same dimension, we use the usual convention $\sin\angle(W_{1},W_{2}):=\left\|P_{W_{1}}-P_{W_{2}}\right\|$, where $P_{W_{i}}$ is the orthogonal projection onto $W_{i}$. The proof has two main steps:

Bounding the angle: We show that $\sin\angle(W,\bar{W})$ is small, under the conditions of the theorem.

Recovering the partition: If $\sin\angle(W,\bar{W})$ is small, we find an approximate partition which can then improved to find an optimal one.

For the first part, recall that ${\mathit{A}}=\bar{{\mathit{A}}}_{0}+\Delta+E$. We first prove that $\left\|\Delta\right\|$ and $\left\|E\right\|$ are small with probability $1-o(1)$. Bounding $\left\|\Delta\right\|$ is easy as it will be sufficient to bound the number of vertices of high degrees. We need the following

There exist a constant $d_{0}$ such that if $d:=a+b\geq d_{0}$, then with probability $1-\exp\left(-\Omega(a^{-2}n)\right)$ not more than $a^{-3}n$ vertices have degree $\geq 20d$.

Note that the proof of the above lemma and other missing proofs in this subsection appear in appendix A.1. If there are at most $a^{-3}n$ vertices with degree $\geq 20d$, then by definition, $\Delta$ has at most $2a^{-3}n^{2}$ non-zero entries, and the magnitude of each entry is bounded by $\frac{a}{n}$. Therefore, its Hilbert-Schmidt norm is bounded by $\left\|\Delta\right\|_{HS}\leq\sqrt{2}a^{-1/2}$.

For $d_{0}$ sufficiently large, with probability $1-\exp(-\Omega(a^{-3}n))$, $\left\|\Delta\right\|\leq 1$.

Now we address the harder task of bounding $\|E\|$. Here is the key lemma

Suppose $M$ is random symmetric matrix with zero on the diagonal whose entries above the diagonal are independent with the following distribution

Let $\sigma$ be a quantity such that $p_{ij}\leq\sigma^{2}$ and $M_{1}$ be the matrix obtained from $M$ by zeroing out all the rows and columns having more than $20\sigma^{2}n$ positive entries. Then with probability $1-o(1)$, $\left\|M_{1}\right\|\leq C\sigma\sqrt{n}$ for some constant $C>0$.

There exist constants $C_{0},C$ such that if $a>b\geq C_{0}$, and $E$ is obtained as described before, then we have,

Now, let $\bar{\boldsymbol{\mathit{v}}_{1}},\bar{\boldsymbol{\mathit{v}}}_{2}$ be eigenvectors of $\bar{A}_{0}$ corresponding to the largest two eigenvalues $\lambda_{1}\geq\lambda_{2}$ $\boldsymbol{\mathit{v}}_{1},\boldsymbol{\mathit{v}}_{2}$ be eigenvectors of $A=\bar{A}_{0}+\Delta+E$ corresponding to the largest two eigenvalues. Further, $\bar{W}:=\text{Span}\{\bar{\boldsymbol{\mathit{v}}_{1}},\bar{\boldsymbol{\mathit{v}}}_{2}\}$ and $W:=\text{Span}\{\boldsymbol{\mathit{v}}_{1},\boldsymbol{\mathit{v}}_{2}\}$.

For any constant $c<1$, we can choose constants $C_{2}$ and $C_{3}$ such that such that if $a-b\geq C_{2}\sqrt{a+b}=C_{2}\sqrt{d}$ and $a\geq C_{3}$ then, $\sin(\angle\bar{W},W)\leq c<1$ with probability $1-o(1)$.

Proof of Lemma 3.5: Let $C_{3}$ be a constant such that if $a\geq C_{3}$, then theorem 3.2 holds giving us $\left\|\Delta\right\|\leq 1$. From lemma 3.4 we have that $\left\|E\right\|\leq C\sqrt{d}$. The lemma then follows from the Davis-Kahan [Dav63] [Bha97] bound for matrices $\bar{A}_{0}$ and $A$, which gives $\sin(\angle W,\bar{W})\leq\frac{\left\|E+\Delta\right\|}{\lambda_{2}}$. Therefore, the lemma follows by choosing $C_{1}$ big enough.

2 Recovery

Given a subspace $W$ satisfying $\sin(\angle\bar{W},W)\leq c<1/16$, we can recover a big portion of the vertices. We prove (in appendix A.2) that

Given a subspace $W$ satisfying $\sin(\angle\bar{W},W)\leq c<1/16$, we can recover a $8c/3$-correct partition.

Once we have an approximate partition, we can use the Blue edges to boost it in the Correction step. We prove (in appendix A.3)

Given a $0.1$ correct partition $V_{1}^{\prime},V_{2}^{\prime}$ as input to the Correction routine in figure 3, the algorithm outputs a $\gamma$ correction partition with $\gamma=2\exp(-0.072\frac{(a-b)^{2}}{a+b}).$

Multiple communities

Let us start with the algorithm, which (compared to the algorithm for the case of 2 blocks) has an additional step of random splitting. This additional step is needed in order to recover the partitions. We will start by computing an approximation of the space spanned by the first $k$ eigenvectors of the hidden matrix. However, when $k>2$, it is not obvious how to approximate the eigenvectors themselves. To handle this problem, we need a new argument that requires this extra step.

Since we use different set of edges for each step, we have independence across the steps.

2 Details

Step 1 is a spectral algorithm on a portion of the adjacency matrix $A_{0}$ as given in figure 6.

This will enable us to recover a large portion of the blocks $Z\cap V_{1},...,Z\cap V_{k}$. We will prove the following statement (appendix B.1)

There exists constants $C_{1},C_{2}$ such that for any fixed integer $k$ the following holds.

$\frac{(a-b)^{2}}{a}\geq C_{2}k^{2}\frac{1}{\gamma}$, and

then we can find a $\gamma$-correct partition $U_{1}^{\prime},...,U_{k}^{\prime}$ of $Z$ with high probability using a simple spectral algorithm.

Step 2 (figure 7) is a further correction that gives us the optimal (logarithmic) dependence between $\gamma$ and $\frac{(a-b)^{2}}{a+b}$. The idea here is to use the degree sequence to correct the mislabeled vertices in Z. Consider a mislabeled vertex $u\in Z\cap V_{1}$. As $u\in Z\cap V_{1}$, we expect $u$ to have $a/4$ Red neighbors in $Z\cap V_{1}$ and $b/4$ Red neighbors in $Z\cap V_{i}$ for all $i\neq 1$. Assume that Spectral Partition output $U_{1}^{\prime},...,U_{k}^{\prime}$ where $|U_{1}\backslash U_{1}^{\prime}|\leq.1n/2k$, we expect $u$ to have at most $0.9b/4k+0.1a/4k$ Red neighbors in $U_{i}^{\prime}$ and at least $0.1b/4k+0.9a/4k$ Red neighbors in $U_{1}^{\prime}$. As

we can correctly reclassify $u$ by thresholding. We can prove (appendix B.2)

Given a $0.1$ correction partition of $Z=(Z\cap V_{1})\cup...\cup(Z\cap V_{k})$ and the Red graph over $Z$, the sub-routine Correction given in figure 7 computes a $\gamma$ correct partition with $\gamma=2k\exp(-0.04\frac{(a-b)^{2}}{k(a+b)})$.

Step 3 is to use the clustering information of vertices in $Z$ to label the vertices in $Y$, and is similar to step 2. We prove (appendix B.3)

Given a $0.1$ correction partition of $Z=(Z\cap V_{1})\cup...\cup(Z\cap V_{k})$ and the Blue graph over $Y\cup Z$, the sub-routine Merge is given in (figure 8) computes a $\gamma$ correct partition with $\gamma=2k\exp(-0.0324\frac{(a-b)^{2}}{k(a+b)})$.

Combining lemmas $\ref{lem:correction_multi},\ref{lem:merge_multi}$, we get the stated result.

Censor Block Model

We first introduce some notations so as to write this problem in a way similar to the other problems in this paper. To simplify the analysis, we make the following assumptions. We assume that there are $|V|=2n$ vertices, with exactly $n$ of them labeled $1$, and the rest labeled $0$. As in [ABBS14], we assume that $G\in G_{2n,p}$ is a graph generated from the Erdos-Renyi model with edge probability $p$. Since any edge $(i,j)$ appears with probability $p$, and that $\boldsymbol{\mathit{z}}_{e}\sim\text{Bernoulli}(\epsilon)$, we have

For any $i,j\in V$, let us write $w_{ij}:=x_{i}\oplus x_{j}$, and $W:=(w_{ij})_{ij}$ the associated $2n\times 2n$ matrix.

We note that $\bar{y}_{i,j}:={\boldsymbol{E}}(y_{i,j})=p\epsilon+p(1-2\epsilon)w_{i,j}.$ Therefore, we can write $y_{i,j}=\bar{y}_{i,j}+\zeta_{i,j}$, where $\zeta_{i,j}s$ are mean zero random variables satisfying $\text{Var}(\zeta_{i,j})\leq p.$ First we note that we can recover the two communities from the eigenvectors of the $2n\times 2n$ matrix $\bar{Y}:=(\bar{y}_{i,j})=p\epsilon I+p(1-2\epsilon)W.$ $\bar{Y}$ is a rank $2$ matrix with eigenvalues $pn$ and $p(1-2\epsilon)n$, with the corresponding eigenvectors $\boldsymbol{\mathit{v}}_{1}=(1,1,....,1)$ and $\boldsymbol{\mathit{v}}_{2}=(1,...,1,-1,...,-1).$ if we can find $\boldsymbol{\mathit{v}}_{2}$, we can identify the two blocks. Let $Y=(y_{i,j})$ and $E=(\zeta_{i,j})$ be $2n\times 2n$ matrices. Algorithm 10 (which is essentially same as algorithm 2) which takes as input the adjacency matrix $Y$ and the edge probability $p$ achieves this when $np\geq\frac{C_{2}}{(1-2\epsilon)^{2}}.$ More detail appears in appendix C.

References

Appendix A Two communities

Proof of Lemma 3.1: One can prove Lemma 3.1 using a standard argument from random graph theory. Consider a set of vertices $X\subset V$ of size $|X|=cn$, where $c<1$ is a constant. We first bound the probability that all the vertices in this set have degree greater than $20d$.

Let us denote the set of edges on $X$ by $E(X)$ and the set of edges with exactly one end point in $X$ by $E(X,X^{c})$. If each degree in $X$ is at least $20d$, then a quick consideration reveals that either $|E(X)|\geq 2cnd$ or $|E(X,X^{c})|\geq 8cnd$. The expected number of edges $\mu_{E(X)}:={\boldsymbol{E}}(|E(X)|)$ satisfies

Let $\delta_{1}:=\frac{2}{c}\leq\frac{2cnd}{\mu_{E(X)}}$, then Chernoff bound (see [AS04] for example) gives

Similarly, the expected number of edges $\mu_{E(X,X^{c})}$ in $E(X,X^{c})$ satisfies

Let $\delta_{2}:=4\leq\frac{8cnd}{\mu_{E(X,X^{c})}}$, then by Chernoff bound

Now, if we substitute $c=a^{-3}$ in the above bounds, we get

subsets $X$ of size $|X|=cn$. Substituting $c=a^{-3}$ again, we get

Proof of Lemma 3.3: We start by proving a simpler result.

Let $M$ be random symmetric matrix of size $n$ with zero diagonal whose entries above the diagonal are independent with the following distribution

Let $\sigma^{2}\geq C_{1}\frac{\log n}{n}$ be a quantity such that $p_{ij}\leq\sigma^{2}$ for all $i,j$, where $C_{1}$ is a constant. Then with probability $1-o(1)$, $\left\|M\right\|\leq C_{2}\sigma\sqrt{n}$ for some constant $C_{2}>0$.

Let us address Lemma A.1. A weaker bound $C\sigma\sqrt{n\log n}$ follows easily from Alshwede-Winter type matrix concentration results (see [Tro12]). To prove the claimed bound, we need to be more careful and follow the $\epsilon$-net approach by Kahn and Szemeredi for random regular graphs in [FKS89] (see also [AK94, FO05]).

Consider a $\frac{1}{2}$-net $\mathcal{N}$ of the unit sphere $\mathcal{S}^{n}$. We can assume $|\mathcal{N}|\leq 5^{n}$. It suffices to prove that there exists a constant $C^{\prime}_{2}$ such that with probability $1-o(1)$, $|\boldsymbol{\mathit{x}}^{T}M\boldsymbol{\mathit{y}}|\leq C^{\prime}_{2}\sigma\sqrt{n}$ for all $\boldsymbol{\mathit{x}},\boldsymbol{\mathit{y}}\in\mathcal{N}$.

For two vectors $\boldsymbol{\mathit{x}},\boldsymbol{\mathit{y}}\in\mathcal{N}$, we follow an argument of Kahn and Szemerédi [FKS89] and call all pairs $(i,j)$ such that $|x_{i}y_{j}|\leq\frac{\sigma}{\sqrt{n}}$ light and all remaining pairs heavy and denote these two classes by $L$ and $H$ respectively. We have

We now show that with probability $1-o(1)$, the last two summands are small in absolute value.

First, let us consider the contribution of light couples. We rewrite $X:=\sum_{L}x_{i}M_{i,j}y_{j}$ as $\sum_{(i,j)\in L,i>j}M_{i,j}a_{i,j}$, where

By the definition light pairs, $|a_{i,j}|\leq 2\frac{\sigma}{\sqrt{n}}$. Also, since x and y are unit vectors, $\sum_{i,j}a_{i,j}^{2}\leq 4$. Therefore, by Bernstein’s bound (see page 36 in [BLM13] for e.g.)

Set $t=10\sigma\sqrt{n}$ and use the union bound (combining with the fact that the net has at most $5^{n}$ vectors, we can conclude that with probability at least $1-\exp(-3n)$, $|\sum_{L}x_{i}M_{i,j}y_{j}|\leq 10\sigma$.

Next we handle the heavy pairs in $H$. Since $1\geq\sum_{H}x_{i}^{2}y_{j}^{2}$, the definition of heavy implies that $\sum_{H}|x_{i}y_{j}|\leq\frac{\sqrt{n}}{\sigma}$.

Note that $A$ defines a graph, say $G_{A}$, such that $A$ is its adjacency matrix. As $p_{ij}\leq\sigma^{2}$, we have $\sum_{H}p_{ij}|x_{i}y_{j}|\leq\sigma^{2}\frac{\sqrt{n}}{\sigma}=\sigma\sqrt{n}$. We use the following lemma to bound the first term.

Let $\widetilde{G}=(\widetilde{V},\widetilde{E})$ be any graph whose adjacency matrix is denoted by $\widetilde{A}$, and $\boldsymbol{\mathit{x}},\boldsymbol{\mathit{y}}$ be any two unit vectors. Let $\widetilde{d}$ be such that the maximum degree $\leq c_{1}\widetilde{d}$. Further, let $\widetilde{d}$ satisfy the property that for any two subsets of vertices $S,T\subset\widetilde{V}$ one of the following holds for some constants $c_{2}$ and $c_{3}$:

then $\sum_{H}x_{i}\widetilde{A}_{i,j}y_{j}\leq\max(16,8c_{1},32c_{2},32c_{3})\sqrt{\widetilde{d}}$. Here $H:=\{(i,j)||x_{i}y_{j}|\geq\sqrt{\widetilde{d}}/n$ }.

Let $\widetilde{d}:=\sigma^{2}n$. Then with probability $1-o(1)$, the maximum degree in the graph $G_{A}$ is $\leq 20\widetilde{d}$ and for any $S,T\subset V$ one of the conditions (1.1) or (1.2 ) holds.

The two lemmas above guarantee that with probability $1-o(1)$, $|\sum_{H}x_{i}A_{i,j}y_{j}|\leq C^{\prime}\sigma\sqrt{n}$ for some constant $C^{\prime}$.

Proof The bound on the maximum degree follows from the Chernoff bound. We have that

Consider a particular vertex $k$ and let $X=\sum_{i}A_{ik}$ be the random variable denoting the number of edges incident on it. We have that

For any $l\geq 4$, Chernoff bound (see [AS04]) implies that

Applying this with $l=20$, and taking a union bound over all the vertices, we can bound the maximum degree by $20\sigma^{2}n$. Now let $S,T\subset V$ be any two subsets. Let $X:=e(S,T)$ be the number of edges going between $S$ and $T$. We have ${\boldsymbol{E}}X\leq\sigma^{2}|S||T|$. If $|T|\geq\frac{n}{e}$, then since the maximum degree is $\leq 20\sigma^{2}n$, we have $e(S,T)\leq|S|20\sigma^{2}n\leq 20e\sigma^{2}|S||T|$, giving us 1.1 in this case. Therefore, we can assume $|T|\leq\frac{n}{e}$. By Chernoff bound, it follows that for any $l\geq 4$,

Let $l^{\prime}$ be the smallest number such that $l^{\prime}\ln(l^{\prime})\geq\frac{21|T|}{\sigma^{2}|S||T|}\log\left(\frac{n}{|T|}\right)$. As in [FO05], if we choose $l=\max(l^{\prime},4)$, we can bound the above probability by $\exp\left({-\frac{l\ln(l)\sigma^{2}|S||T|}{3}}\right){n\choose|S|}{n\choose|T|}\leq\frac{1}{n^{3}}$. Therefore, by the union bound we get that with probability $1-o(1)$ for all subsets $S,T$, and

This implies that one of the conditions 1.1 or 1.2 holds with probability $1-o(1)$.

Proof of Lemma 3.3: Now we are ready to prove Lemma 3.3 by modifying the previous proof. We again handle the light couples and the heavy couples separately, but need to make a modification to the argument for the light couples.

Since we zero out some rows and columns of $M$ to obtain $M_{1}$, we first bound the norm of the matrix $M_{0}$, obtained from $M$ by zeroing out a set $S$ of rows and the corresponding columns. Next, we take a union bound over all choices of $S$. For a fixed $S$, lemma A.1 implies that with probability at least $1-\exp(-3n)$, for all $\boldsymbol{\mathit{x}},\boldsymbol{\mathit{y}}\in\mathcal{N}_{1/2}$, $|\sum_{L}x_{i}(M_{0})_{ij}y_{j}|\leq 10\sigma\sqrt{n}$. Since there are at most $2^{n}=\exp\left(n\ln 2\right)$ choices for $S$, we can apply a union bound to show that with probability at least $1-\exp(-(3-\ln 2)n)$, $|\sum_{L}x_{i}(M_{1})_{ij}y_{j}|\leq 10\sigma\sqrt{n}$.

The proof for the heavy couples goes through without any modifications. We just have to verify that the conditions of lemma A.2 are met. Firstly, the adjacency matrix $A_{1}$ obtained from $M_{1}$ has bounded degree property by the definition of $M_{1}$. Now we note that only for the case of $|S|\leq|T|\geq\frac{n}{e}$ did we need that the maximum degree was bounded. So for any $|S|\leq|T|<\frac{n}{e}$, the discrepancy properties (1.1) or (1.2) holds for $A_{1}$, since zeroing out rows and columns can only decrease the edge count across sets of vertices. In the case $|T|\geq\frac{n}{e}$, like before we can show that (1.1) holds for $A_{1}$ since the degrees are bounded. $\blacksquare$

Now, to bound the norm of matrix $E$, we just appeal to 3.3. Suppose $a>b\geq C_{0}$, for a large enough constant $C_{0}$ to be determined later. Since $A=\bar{A}_{0}+\Delta+E$ and we have bounded $\Delta$, it remains to bound $\left\|E\right\|$. Note that

if $i,j$ belongs to the same community and

if $i,j$ belongs to different communities. Since $a>b$, for all $i,j$ we have that

A.2 Recovery

Now we focus on the second step in the proof, namely the recovery of the blocks once the angle condition is satisfied.

If $\sin(\angle\bar{W},W)\leq c\leq\frac{1}{4}$, then we can find a vector $\boldsymbol{\mathit{v}}\in W$ such that $\sin(\angle\boldsymbol{\mathit{v}},\bar{\boldsymbol{\mathit{v}}_{2}})\leq 2\sqrt{c}$.

Proof Let $P_{\bar{W}},P_{W}$ be the orthogonal projection operators on to the subspaces $\bar{W},W$ respectively. From the angle bound for the subspaces, we have that

The vector we want is obtained as follows. We first project $\bar{\boldsymbol{\mathit{v}}}_{1}$ on to $W$, and then find the unit vector orthogonal to the projection in $W$. We will now prove that the vector so obtained satisfies the bound stated in the lemma. Since $\bar{\boldsymbol{\mathit{v}}_{1}},\bar{\boldsymbol{\mathit{v}}}_{2}\in\bar{W}$, we have that $\left\|P_{W}\bar{\boldsymbol{\mathit{v}}_{i}}-\bar{\boldsymbol{\mathit{v}}}_{i}\right\|_{2}\leq c$ for $i=1,2$. Let us define $\boldsymbol{\mathit{u}}_{i}:=P_{W}\bar{\boldsymbol{\mathit{v}}_{i}}$ and $\textbf{x}_{i}:=\boldsymbol{\mathit{u}}_{i}-\bar{\boldsymbol{\mathit{v}}}_{i}$ (note that $\left\|\textbf{x}_{i}\right\|\leq c$) for $i=1,2$. We will now show that the vector $\boldsymbol{\mathit{v}}\in W$ perpendicular to $\boldsymbol{\mathit{u}}_{1}$ is close to $\bar{\boldsymbol{\mathit{v}}}_{2}$. Let $\boldsymbol{\mathit{u}}_{\perp}=\boldsymbol{\mathit{u}}_{2}-\frac{\boldsymbol{\mathit{u}}_{1}^{T}\boldsymbol{\mathit{u}}_{2}}{\left\|\boldsymbol{\mathit{u}}_{1}\right\|^{2}}\boldsymbol{\mathit{u}}_{1}$, it is then clear that $\left\|\boldsymbol{\mathit{u}}_{\perp}\right\|\leq 1$. Note that $|\boldsymbol{\mathit{u}}_{1}^{T}\boldsymbol{\mathit{u}}_{2}|=|\bar{\boldsymbol{\mathit{v}}}_{1}^{T}\textbf{x}_{2}+\bar{\boldsymbol{\mathit{v}}}_{2}^{T}\textbf{x}_{1}+\textbf{x}_{1}^{T}\textbf{x}_{2}|\leq 2c+c^{2}$. We have,

The last inequality holds when $c\leq\frac{1}{4}$. Therefore, it holds that for a unit vector $\boldsymbol{\mathit{v}}\perp\boldsymbol{\mathit{u}}_{1}$,

This gives $\sin(\angle\boldsymbol{\mathit{v}},\bar{\boldsymbol{\mathit{v}}}_{2})\leq\sqrt{1-(1-2c)^{2}}\leq 2\sqrt{c}$. $\blacksquare$

For any constant $c<1$, we can choose constants $C_{2}$ and $C_{3}$ in lemma 3.5 and find a vector $\boldsymbol{\mathit{v}}$ such that $\sin(\angle\bar{\boldsymbol{\mathit{v}}}_{2},\boldsymbol{\mathit{v}})\leq c<1$ with probability $1-o(1)$.

We now can conclude the proof of our theorem using the following deterministic fact.

If $\sin(\angle\bar{\boldsymbol{\mathit{v}}}_{2},\boldsymbol{\mathit{v}})<c\leq 0.5$, then we can identify at least a $(1-\frac{4}{{3}}c^{2})$ fraction of vertices from each block correctly.

Proof of Lemma A.6: Let us define two sets of vertices, $V^{\prime}_{1}=\{i|\boldsymbol{\mathit{v}}(i)>0\}$ and $V^{\prime}_{2}=\{i|\boldsymbol{\mathit{v}}(i)<0\}$. One of the sets will have less than or equal to $\frac{n}{2}$ vertices, let us assume without loss of generality that $|V^{\prime}_{1}|\leq\frac{n}{2}$. Writing $\boldsymbol{\mathit{v}}=c_{1}\bar{\boldsymbol{\mathit{v}}}_{2}+\textbf{err}$, for a vector err perpendicular to $\bar{\boldsymbol{\mathit{v}}}_{2}$ and $\left\|\textbf{err}\right\|<c$. We also have $c_{1}>\sqrt{1-c^{2}}$. Since $\left\|\textbf{err}\right\|<c$, not more than $\frac{c^{2}}{1-c^{2}}n$ coordinates of err can be bigger than $\frac{\sqrt{1-c^{2}}}{\sqrt{n}}<\frac{c_{1}}{\sqrt{n}}$. Since $\boldsymbol{\mathit{v}}=c_{1}\bar{\boldsymbol{\mathit{v}}}_{2}+\textbf{err}$ at least $1-\frac{c^{2}}{1-c^{2}}>1-\frac{4}{3}c^{2}$ (since $c\leq 0.5$) fraction of vertices with $\bar{\boldsymbol{\mathit{v}}}_{2}(i)=\frac{1}{\sqrt{n}}$ will have $\boldsymbol{\mathit{v}}(i)>0$. Therefore, we get that there are at least $(1-\frac{4}{3}c^{2})n$ vertices belonging to the first block. $\blacksquare$

A.3 Proof of lemma 2.3

We will use the following large deviation result (see page 36 in [BLM13] for e.g.) repeatedly

(Chernoff) If $X$ is a sum of $n$ iid indicator random variables with mean at most $\rho\leq 1/2$, then for any $t>0$

In the Red graph, the edge densities are $a/2n$ and $b/2n$, respectively. By Theorem 2.1, there is a constant $C$ such that if $\frac{(a-b)^{2}}{a+b}\geq C$ then by running Spectral Partition on the Red graph, we obtain, with probability $1-o(1)$ two sets $V_{1}^{\prime}$ and $V_{2}^{\prime}$, where

In the rest, we condition on this event, and the event that the maximum Red degree of a vertex is at most $\log^{2}n$, which occurs with probability $1-o(1)$.

Now we use the Blue edges. Consider $e=(u,v)$. If $e$ is not a red edge, and $u\in V_{i},v\in V_{3-i}$, then $e$ is a Blue edge with probability

Similarly, if $e$ is not a Red edge, and $u,v\in V_{i}$, then $e$ is a Blue edge with probability

Thus, for any $u\in V_{i}^{\prime}\cap V_{i}$, the number of its Blue neighbors in $V_{3-i}^{\prime}$ is at most

where $\xi_{i}^{u}$ are iid indicator variables with mean $\mu$ and $\zeta_{j}^{u}$ are iid indicator variables with mean $\tau$.

Similarly, for any $u\in V_{1}^{\prime}\cap V_{2}$, the number of its Blue neighbors in $V_{2}^{\prime}$ is at least

where $d(u)=\log^{2}n$ is the Red degree of $u$.

After the correction sub-routine, a vertex $u$ in the (corrected) set $V_{1}^{\prime}$ is misclassified if

$u\in V_{1}^{\prime}\cap V_{1}$ and $S_{u}\geq\frac{a+b}{4}$.

$u\in V_{1}^{\prime}\cap V_{2}$ and $S_{u}^{\prime}\leq\frac{a+b}{4}$

Let $\rho_{1},\rho_{2}$ be the probability of the above events. Then the number of misclassified vertices in the (corrected) set $V_{1}^{\prime}$ is at most

where $\Gamma_{k}$ are iid indicator random variables with mean $\rho_{1}$ and $\Lambda_{l}$ are iid indicator random variables with mean $\rho_{2}$.

The rest is a simple computation. First we use Chernoff bound to estimate $\rho_{1},\rho_{2}$. Consider

By (2.4), one can show that $2(0.9n\mu+.1n\tau)+0.19(a-b)=0.71b+0.29a+o(1)\leq\frac{a+b}{2}$. It follows that

By a similar argument, we obtain the same estimate for $\rho_{2}$ (the contribution of the term $d(u)\leq\log^{2}n$ is negligible). Thus, we can conclude that

Applying Chernoff’s with $t:=0.9n\exp(-0.072\frac{(a-b)^{2}}{a+b})$, we conclude that with probability $1-o(1)$

This implies that with probability $1-o(1)$,

By symmetry, the same conclusion holds for $|V_{2}^{\prime}\backslash V_{2}|$.

This shows that the output $V_{1}^{\prime},V_{2}^{\prime}$ form a $\gamma$-correct partition, with $\gamma$ satisfying

Proof of Corollary 1.4: Notice that in the analysis of Spectral Partition, we only require $\frac{(a-b)^{2}}{a+b}\geq C$ for a sufficiently large constant $C$ (so $\gamma$ does not appear in the bound). In the analysis of Correction, we require $\frac{(a-b)^{2}}{a+b}\geq 13.89\log\frac{2}{\gamma},$ as shown above. If $\gamma<\epsilon$ for a sufficiently small $\epsilon$, this assumption implies the first. Thus, Corollary holds with assumption $\frac{(a-b)^{2}}{a+b}\geq 13.89\log\frac{2}{\gamma}$.

The constant $13.89$ comes from the fact that the partition obtained from Spectral Partition is $.1$-correct. If one improves upon $.1$, one improves $13.89$. In particular, there is a constant $\delta$ such that if the first partition is $\delta$-correct, then one can improve $13.89$ to $8.1$ (or any constant larger than $8$–which is the limit of the method, for that matter).

Appendix B Multiple communities

We say the splitting is ‘perfect’ if we have $|Y_{1}\cap V_{i}|=\frac{n}{4k}=|Y_{2}\cap V_{i}|$ for $i=1,..,k.$ We will assume the splittings are perfect in the proofs for a simpler exposition. Though the splitting will almost always not be perfect, and there will just be a $o(1)$ error term that we have to carry throughout to be precise. The bounds we give will all be still be essentially the same.

To analyze this algorithm, we use the machinery developed so far combined with some ideas from [Vu14]. We consider the stochastic block model with $k$ blocks of size $n$, where $k$ is a fixed constant as $n$ grows. This is a graph $V=V_{1}\cup V_{2}\cup...\cup V_{k}$ where each $|V_{i}|=n/k$ and for $u\in V_{i},v\in V_{j}$:

where $\bar{A},\bar{A_{1}}$ are the expected matrices, and $\Delta$ is matrix containing the deleted rows and columns. Let $\bar{W}$ be the span of the $k$ left singular vectors of $\bar{A}_{1}$ We can bound $\left\|\Delta\right\|\leq 1$ by bounding the number of high degree vertices as we did before. $E$ is given by

if $u,v\in V_{i}\cap Y_{1}\text{ for some }i\in{1,..,k}$ and

$\text{ if }u\in V_{i}\cap Y_{1}\text{ and }v\in V_{j}\cap Y_{1}\text{ for }i\neq j.$ Since $\sigma^{2}:=\frac{a}{n}\geq\text{Var}(E_{u,v})$, corollary 3.3 applied to $\bar{A}_{1}-A$ gives the following result.