Community detection in sparse networks via Grothendieck's inequality

Introduction

In this paper we present a simple and general method to prove consistency of various semidefinite optimization problems on random graphs.

A motivating example of $A$ is the adjacency matrix of a random graph; the Boolean vector $x$ can represent a partition of vertices of the graph into two classes. Such Boolean problems can be encountered in the context of community detection in networks which we will discuss shortly. For now, let us keep working with the general class of problems (1.1).

Since $\bar{A}$ is unknown, one might hope to estimate the solution $\bar{x}$ of (1.1) by solving the random instance of this problem, that is

The integer quadratic problem (1.2) is NP-hard for general (non-random) matrices $A$. Semidefinite relaxations of many problems of this type have been proposed; see and the references therein. Such relaxations are known to have constant relative accuracy. For example, a semidefinite relaxation in computes, for any given positive semidefinite matrix $A$, a vector $x_{0}\in\{-1,1\}^{n}$ such that $x_{0}^{\mathsf{T}}Ax_{0}\geq 0.56\,\max_{x\in\{-1,1\}^{n}}x^{\mathsf{T}}Ax$.

In this paper we demonstrate how semidefinite relaxations of (1.2) can recover a solution of (1.1) with any given relative accuracy. Like several previously known methods, our approach is based on Grothendieck’s inequality. We refer the reader to the surveys for many reformulations and applications of this inequality in mathematics, computer science, optimization and other fields. In contrast to the previous methods, we are going to apply Grothendieck’s inequality for the (random) error $A-\bar{A}$ rather that the original matrix $A$, and this will be responsible for the arbitrary accuracy.

We will describe the general method in Section 2. It is simple and flexible, and it can be used for showing consistency of a variety of semidefinite programs, which may or may not be related to Boolean problems like (1.1). But before describing the method, we would like to pause and give some concrete examples of results it yields for community detection.

For simplicity, we will first focus on the classical stochastic block model, which is a random network whose nodes are split into two equal-sized clusters. In Section 1.3 we will extend our discussion for broader models of networks almost without extra effort.

2. Community detection: the classical stochastic block model

It is now customary to model networks as inhomogeneous random graphs , which generalize the classical Erdös-Rényi model $G(n,p)$. A benchmark example is the stochastic block model . In this section we focus on the basic model with two communities of equal sizes; in Section 1.3 we will consider a more general situation.

We define a random graph on vertices $\{1,\ldots,n\}$ as follows. Partition the set of vertices into two communities $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ of size $n/2$ each. For each pair of distinct vertices, we draw an edge independently with probability $p$ if both vertices belong to the same community, and $q$ (with $q\leq p$) if they belong to different communities. For convenience we include the loops, so each vertex has an edge connecting it to itself with probability $1$. This defines a distribution on random graphs which is denoted $G(n,p,q)$ and called the (classical) stochastic block model. When $p=q$, we recover the classical Erdös-Rényi model of random graphs $G(n,p)$.

The community detection problem asks to recover the communities $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ by observing one instance of a random graph drawn from $G(n,p,q)$. As we will discuss in detail in Section 1.4, an array of algorithms is known to succeed for this problem for relatively dense graphs, those whose expected average degree (which is of order $pn$) is $\Omega(\log n)$, while less is known for totally sparse graphs – those with bounded average degrees, i.e. with $pn=O(1)$. Our paper focuses on this sparse regime.

Recovery of the communities $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ is equivalent to estimating the community membership vector, which we can define as

We will estimate $\bar{x}$ using the following semidefinite optimization problem:

For the value of $\lambda$ we choose the average degree of the graph (with loops removed), which is

where $a_{ij}\in\{0,1\}$ denote the entries of the adjacency matrix $A$.

Let $\varepsilon\in(0,1)$ and $n\geq 10^{4}\varepsilon^{-2}$. Let $A$ be the adjacency matrix of the random graph drawn from the stochastic block model $G(n,p,q)$ with $\max\{p(1-p),q(1-q)\}\geq\frac{20}{n}$. Assume that $p=\frac{a}{n}>q=\frac{b}{n}$, and

Let $\widehat{Z}$ be a solution of the semidefinite program (1.4). Then, with probability at least $1-e^{3}5^{-n}$, we have

Here and in the rest of this paper, $\|\cdot\|_{2}$ denotes the Frobenius norm of matrices and the Euclidean norm of vectors.

Once we have estimated the rank-one matrix $\bar{x}\bar{x}^{\mathsf{T}}$ using Theorem 1.1, we can also estimate the community membership vector $\bar{x}$ itself in a standard way, namely by computing the leading eigenvector.

In the setting of Theorem 1.1, let $\widehat{x}$ denote an eigenvector of $\widehat{Z}$ corresponding to the largest eigenvalue, and with $\|\widehat{x}\|_{2}=\sqrt{n}$. Then

In particular, the signs of the coefficients of $\widehat{x}$ correctly estimate the partition of the vertices into the two communities, up to at most $\varepsilon n$ misclassified vertices.

As we will discuss in Section 1.4.2 in more detail, there are previously known algorithms for recovery of two communities under conditions similar to (1.6). These include a spectral clustering algorithm based on truncating the high degree vertices (whose analysis can be derived from ), combinatorial algorithms of based on path counting, and an algorithm based on belief propagation, which minimizes the fraction of misclassified vertices.

An array of simple semidefinite programs like (1.4) and (1.9) has been proposed in networks community. Such programs have been analyzed for relatively dense graphs; see for a review. It has been unknown if they could succeed for totally sparse graphs, where the expected degree is of constant order. Theorem 1.1 provides a positive answer to this question. Moreover, the method of this paper is flexible enough to analyze many semidefinite programs, and it can be applied for more general models of sparse networks than any previous results.

To illustrate this point, we will now choose a different semidefinite program and show that it succeeds for a large class of stochastic models of networks. Moreover, in Section 7 we will see that a minor modification of the semidefinite program (1.4) also works well for multiple communities of equal sizes.

3. Community detection: general stochastic block models

Let us describe a model of networks where one can have multiple communities of arbitrary sizes, arbitrarily many outliers, and unequal edge probabilities.

To define such general stochastic block model, we assume that the set of vertices $\{1,\ldots,n\}$ is partitioned into communities $\mathcal{C}_{1},\ldots,\mathcal{C}_{K}$ of arbitrary sizes. We do not restrict the sizes of the communities, so in particular this model can automatically handle outliers, the vertices that form communities of size $1$. For each pair of distinct vertices $(i,j)$, we draw an edge between $i$ and $j$ independently and with certain fixed probability $p_{ij}$. For convenience we include the loops like in the classical stochastic block model, so $p_{ii}=1$. To promote more edges within than across the communities, we assume that there exist numbers $p>q$ (thresholds) such that

The community structure of such a network is captured by the cluster matrix matrix $\bar{Z}\in\{0,1\}^{n\times n}$ defined as

We will estimate $\bar{Z}$ using the following semidefinite optimization program:

Here as usual $Z\succeq 0$ means that $Z$ is positive semidefinite, and $Z\geq 0$ means that all entries of $Z$ are non-negative. We choose the value of $\lambda$ to be the number of elements in the cluster matrix, that is

If all communities have the same size $s$, then $\lambda=Ks^{2}=ns$.

Let $\varepsilon\in(0,1)$. Let $A$ be the adjacency matrix of the random graph drawn from the general stochastic block model described above. Denote by $\bar{p}$ the expected variance of the edges, that is $\bar{p}=\frac{2}{n(n-1)}\sum_{i<j}p_{ij}(1-p_{ij})$. Assume that $p=\frac{a}{n}>q=\frac{b}{n}$, $\bar{p}=\frac{g}{n}$, $g\geq 9$ and

Let $\widehat{Z}$ be a solution of the semidefinite program (1.10). Then, with probability at least $1-e^{3}5^{-n}$, we have

The power of Theorem 1.3 does not depend on the community structure, i.e. on the number and sizes of the communities. This seemingly surprising observation can be explained by the fact that small communities, those with sizes $o(n)$, can get absorbed in the error term in (1.13), so they will not be recovered.

Our choice of the parameter $\lambda$ in (1.11) assumes that we know the sizes of the communities. What if they are not known? From the proof of Theorem 1.3 it will be clear what happens when $\lambda>0$ is chosen arbitrarily. Assume that we choose $\lambda$ so that $\lambda\leq\lambda_{0}:=\sum_{k}|\mathcal{C}_{k}|^{2}$. Then instead of estimating the full cluster graph (described in Remark 1.6), the solution $\widehat{Z}$ will only estimate a certain subgraph of the cluster graph, which may miss at most $\lambda_{0}-\lambda$ edges. On the other hand, if we choose $\lambda$ so that $\lambda\geq\lambda_{0}$, then the solution $\widehat{Z}$ will estimate a certain supergraph of the cluster graph, which may have at most $\lambda-\lambda_{0}$ extra edges. In either case, such solution could be meaningful in practice.

It may be convenient to view the cluster matrix $\bar{Z}$ as the adjacency matrix of the cluster graph, in which all vertices within each community are connected and there are no connections across the communities. This way, the semidefinite program (1.10) takes a sparse graph as an input, and it returns an estimate of the cluster graph as an output. The effect of the program is thus to “densify” the network inside the communities and “sparsify” it across the communities.

There is nothing special about the semidefinite programs (1.4) and (1.10). For example, one can tighten the constraints and instead of $\operatorname*{diag}(Z)\preceq{\textbf{I}}_{n}$ require that $\operatorname*{diag}(Z)={\textbf{I}}_{n}$ in both programs. Similarly, instead of placing in (1.10) the constraint on the sum of all entries of $Z$, one can place constraints on the sums of each row. In a similar fashion, one should be able to analyze other semidefinite relaxations, both new and those proposed in the previous literature on community detection, see .

For one more illustration for the method described here, we refer the reader to Section 7 of the extended version of this paper . There we consider a minor modification of the semidefinite program (1.4), and we show that it succeeds in presence of multiple communities of equal sizes (the so-called balanced planted partition model). The sufficient condition for that is $(a-b)^{2}\geq 50^{2}\varepsilon^{-2}(a+b(K-1))$ where $K$ is the number of communities, $s$ the size of the communities and $p=a/s$, $q=b/s$.

4. Related work

Community detection in stochastic block models is a fundamental problem that has been extensively studied in theoretical computer science and statistics. A plethora or algorithmic approaches have been proposed, in particular those based on combinatorial techniques , spectral clustering , likelihood maximization , variational methods , Markov chain Monte Carlo , belief propagation , and convex optimization including semidefinite programming .

Most known rigorous results on community detection are proved for relatively dense networks whose expected degrees go to infinity with $n$. If the degrees grow no slower than $\log n$, it may be possible to recover the community structure perfectly, without any misclassified vertices. A variety of community detection methods are known to succeed in this regime, including those based on spectral clustering, likelihood maximization and convex optimization mentioned above; see e.g. and the references therein.

The semidefinite programs (1.4) and (1.10) are similar to those proposed in the recent literature, most notably in . The semidefinite relaxations discussed in can perfectly recover the community structure if $(a-b)^{2}\geq C(a\log n+b)$ for a sufficiently large constant $C$; see for a review of these results.

4.2. Totally sparse networks: bounded average degrees

The problem becomes more difficult for sparser networks, whose expected average degrees grow to infinity arbitrarily slowly or even remain bounded in $n$. Although studying such networks is well motivated from the practical perspective , little has been known on the theoretical level.

If the degrees grow slower than $\log n$, it is impossible to correctly classify all vertices, since with high probability a positive fraction of the vertices will be isolated. Still, the fraction of isolated vertices tends to zero with $n$, so we can hope to correctly classify a majority of the vertices in this regime.

The spectral method developed by J. Kahn and E. Szemeredi for random regular graphs can be adapted for Erdös-Rényi random graphs and, more generally, for the stochastic block model $G(n,\frac{a}{n},\frac{b}{n})$. If one truncates the graph by removing all vertices with too large degrees (say, larger than $10(a+b)$), then the argument of can be adapted to conclude that with some positive probability, the truncated adjacency matrix concentrates near its expectation in the spectral norm. The communities can then be approximately recovered using the spectral clustering, which is based on the signs of the coefficients of the second eigenvector. Working out the details, one finds that a sufficient condition for this method to succeed is similar to (1.6), that is

where $C_{\varepsilon}$ depends only on the desired accuracy $\varepsilon$ or recovery. However, for real networks it is usually impractical to remove high degree vertices and the probabilistic estimate from is not sharp.

A. Coja-Oghlan proposed a different, complicated adaptive spectral algorithm that can approximately recover communities under the condition $(a-b)^{2}\geq C_{\varepsilon}(a+b)\log(a+b)$. Recently, L. Massoulié and E. Mossel, J. Neeman and A. Sly came up with combinatorial algorithms based on path counting, which can approximately recover communities under the condition (1.14). These results are stated in the asymptotic regime for $n\to\infty$ and without explicit dependence of $C_{\varepsilon}$ on the desired accuracy $\varepsilon$. Furthermore, E. Mossel, J. Neeman and A. Sly developed an algorithm based on belief propagation , which minimizes the fraction of misclassified vertices.

Condition (1.14) has the optimal form. Indeed, it was shown in that the lower bound (1.14) is required for any algorithm to be able to recover communities with at most $\varepsilon n$ misclassified vertices, where $C_{\varepsilon}\to\infty$ as $\varepsilon\to 0$. A conjecture of A. Decelle, F. Krzakala, C. Moore and L. Zdeborova proved recently by E. Mossel, J. Neeman and A. Sly and Massouile states that one can find a partition correlated with the true community partition (i.e. with the fraction of misclassified vertices bounded away from $50\%$ as $n\to\infty$) if $(a-b)^{2}\geq C(a+b)$ with some constant $C>2$. Moreover, this result achieves information-theoretic limit: no algorithm can succeed if $C\leq 2$.

It remains an open question whether semidefinite programing can achieve similar information-theoretic limits. Theorem 1.1 does not achieve them; addressing this problem will require to tighten the absolute constant and the dependence on $\varepsilon$ in (1.6).

4.3. The new results in historical perspective

A variety of simple semidefinite programs like (1.4) and (1.9) have been proposed in the network literature. Such programs have been analyzed only for dense networks where the degrees grow as $\Omega(\log n)$ in which case perfect community detection is possible. The present paper shows that the same semidefinite programs succeed for totally sparse networks as well, producing a small number of misclassified vertices; moreover the sufficient condition (1.14) is optimal up to an absolute constant.

Furthermore, the method of the present paper generalizes smoothly for a broad classes of sparse networks. We saw in Section 1.3 that semidefinite programming succeeds for networks with variable edge probabilities $p_{ij}$; community detection in such networks seems to be out of reach for known spectral methods.

We also saw how networks with multiple communities be handled with semidefinite approach. This has been studied in the statistical literature before; the semidefinite relaxations proposed in were designed for multiple communities and outliers. However, previous theoretical results for multiple communities were only available for dense regime where the degrees grow as $\Omega(\log n)$, in which case perfect community detection is possible.

4.4. Follow up work

After this paper had been submitted, several new results appeared on community detection in stochastic block models. We will mention here only results that apply for totally sparse networks. The initial discovery of mentioned in Section 1.4.2 was followed by the work . Semidefinite programs on random graphs were further analyzed in using higher-rank Grothendieck inequalities and insights from mathematical physics. Stochastic block models with labeled edges were addressed in using truncated spectral clustering (with high degree vertices removed, based on ) and semidefinite programming (whose analysis is based on the method of the present paper). A two-stage algorithm based on truncated spectral clustering and swapping vertices (like e.g. in ) was analyzed in ; the swapping stage leads to the sufficient condition (1.14) with with an optimal dependence on the accuracy, $C_{\varepsilon}\sim\log(1/\varepsilon)$. A different combinatorial method was proposed and analyzed in ; regularized spectral clustering was shown to succeed in ; and a computationally feasible likelihood-based algorithm that minimizes the risk for misclassification proportion was found in . Some of the mentioned work can be used for networks with multiple communities, see .

5. Plan of the paper

We discuss the method in general terms in Section 2. We explain how Grothendieck’s inequality can be used to show tightness of various semidefinite programs on random graphs. Section 3 is devoted to Grothendieck’s inequality and its implications for semidefinite programming. In Section 4 we prove a simple concentration inequality for random matrices in the cut norm. In Section 5 we specialize to the community detection problem for the classical stochastic block model, and we prove Theorem 1.1 and Corollary 1.2 there. In Section 6 we consider the general classical stochastic block model, and we prove Theorem 1.3 there.

Acknowledgement

This work was carried out while the first author was a Gerhing Visiting Professor at the University of Michigan. He thanks this institution for hospitality. The second author is grateful to Alexander Barvinok for drawing his attention to Y. Nesterov’s work on combinatorial optimization and to Grothendieck’s inequality in this context. We also thank Elchanan Mossel for useful discussions, and the anonymous referees whose suggestions helped to improve the presentation.

Semidefinite optimization on random graphs: the method in a nutshell

In this section we explain the general method of this paper, which can be applied to a variety of optimization problems. To be specific, let us return to the problem we described in Section 1.1, which is to estimate the solution $\bar{x}$ of the optimization problem (1.1) from a single observation of the random matrix $A$. We suggested there to approximate $\bar{x}$ by the solution of the (random) program (1.2), which we can rewrite as follows:

Note that if we maximized $\langle A,xx^{\mathsf{T}}\rangle$ over the Euclidean ball $B(0,\sqrt{n})$, then the problem would be simple – the solution $x$ would be the eigenvector corresponding to the eigenvalue of $A$ of largest magnitude. This simpler problem underlies the most basic algorithm for community detection called spectral clustering, where the communities are recovered based on the signs of an eigenvector of the adjacency matrix (going back to , see ). The optimization problem (2.1) is harder and more subtle; the replacement of the Euclidean ball by the cube introduces a strong restriction on the coordinates of $x$. This restruction rules out localized solutions $x$ where most of the mass of $x$ is concentrated on a small fraction of coordinates. Since eigenvectors of sparse matrices tend to be localized (see ), basic spectral clustering is often unsuccessful for sparse networks.

We might hope that the solution $\widehat{Z}$ of this program would enable us to estimate the solution $\bar{x}$ of (1.1).

This condition can be arranged for in various applications. In particular, this is the case in the setting of Theorem 1.1; we show this in Lemma 5.1.

Second, one needs a uniform deviation inequality, which would guarantee with high probability that

This can often be proved by applying standard deviation inequalities for a fixed pair $(x,y)$, followed by a union bound over all such pairs. We prove such a deviation inequality in Section 4.

Now we make the crucial step, which is an application of Grothendieck’s inequality. A reformulation of this remarkable inequality, which we explain in Section 3, states that (2.5) automatically implies that

This will allow us to conclude that the solution $\widehat{Z}$ of (2.2) approximates the solution $\bar{Z}$ of (2.3). To see this, let us compare the value of the expected objective function $\langle\bar{A},Z\rangle$ at these two vectors. We have

This means that $\widehat{Z}$ almost maximizes the objective function $\langle\bar{A},Z\rangle$ in (2.3).

The final piece of information we require is that the expected objective function $\langle\bar{A},Z\rangle$ distinguishes points near its maximizer $\bar{Z}$. This would allow one to automatically conclude from (2.7) that the almost maximizer $\widehat{Z}$ is close to the true maximizer, i.e. that

Finally, we can recall from (2.4) that $\bar{Z}=\bar{x}\bar{x}^{\mathsf{T}}$. Together with (2.8), this yields that $\widehat{Z}$ is approximately a rank-one matrix, and its leading eigenvector $\widehat{x}$ satisfies

Thus we estimated the solution $\bar{x}$ of the problem (1.1) as desired.

For this method to work, it is not crucial that the semidefinite program be a relaxation of any vector optimization problem. Indeed, one can analyze semidefinite programs of the type (2.2) without any vector optimization problem (2.1) in the background. In such cases, the requirement (2.4) of tightness of relaxation can be dropped. The solution $\bar{Z}$ may itself be informative. An example of such situation is Theorem 1.3 where the community membership matrix $\bar{Z}$ is important by itself. However, $\bar{Z}$ can not be represented as $\bar{x}\bar{x}^{\mathsf{T}}$ for any $\bar{x}$, since $\bar{Z}$ is not a rank one matrix.

Grothendieck’s inequality and semidefinite programming

Grothendieck’s inequality is a remarkable result proved originally in the functional analytic context and reformulated in in the form we are going to describe below. This inequality had found applications in several areas . It has already been used to analyze semidefinite relaxations of hard combinatorial optimization problems , although previous relaxations lead to constant (rather than arbitrary) accuracy.

Consider an $n\times n$ matrix of real numbers $B=(b_{ij})$. Assume that

for all numbers $s_{i},t_{i}\in\{-1,1\}$. Then

for all vectors $X_{i},Y_{i}\in B_{2}^{n}$.

We note in passing that this norm is equivalent to the so-called cut norm, whose importance in algorithmic problems is well understood in theoretical computer science community, see e.g. .

Combining (3.2) with (3.4) and the identity (3.3), we obtain the following form of Grothendieck inequality for positive semidefinite matrices.

2. Semidefinite programming

To keep the discussion sufficiently general, let us consider the following class of optimization programs:

Imagine that there is a similar but simpler problem where $B$ is replaced by a certain reference matrix $R$, that is

The next lemma shows that $\widehat{Z}$ provides an almost optimal solution to the reference problem if the original and reference matrices $B$ and $R$ are close.

Now, to prove the lower bound in (3.7), we will first replace $R$ by $B$ using (3.8), then replace $\widehat{Z}$ by $Z_{R}$ using the fact that $\widehat{Z}$ is a maximizer for $\langle B,Z\rangle$, and finally replace back $B$ by $R$ using (3.8) again. This way we obtain

Deviation in the cut norm

To be able to effectively use Lemma 3.3, we will now show how to bound the cut norm of random matrices.

Then, with probability at least $1-e^{3}5^{-n}$, we have

We will shortly deduce Lemma 4.1 from Bernstein’s inequality followed by a union bound over $x,y\in\{-1,1\}^{n}$; arguments of this type are standard in the analysis of random graphs (see e.g. [13, Section 2.3]). But before we do this, let us pause to explain the conclusion of Lemma 4.1.

This deviation inequality is good when $a$ exceeds a sufficiently large absolute constant. Since that $a=pn$ is the expected average degree of the graph, it follows that we can handle graphs with bounded expected degrees.

The proof of Lemma 4.1 will be based on Bernstein’s inequality, which we quote here (see, for example, Theorem 1.2.6 in ).

Let us substitute $t=6\,(\bar{p}/n)^{1/2}$ here. Rearranging the terms and using that $N=\frac{n(n-1)}{2}$ and $\bar{p}>9/n$ (so that $t<2\bar{p}$), we conclude that the probability in (4.3) is bounded by $\exp(-3(n-1))$.

Summarizing, we have proved that for every ${x,y\in\{-1,1\}^{n}}$

Taking a union bound over all $2^{2n}$ pairs $(x,y)$, we conclude that

Stochastic block model: proof of Theorem 1.1

So far our discussion has been general, and the results could be applied to a variety of semidefinite programs on random graphs. In this section, we specialize to the community detection problem considered in Theorem 1.1. Thus we are going to analyze the optimization problem (1.4), where $A$ is the adjacency matrix of a random graph distributed according to the classical stochastic block model $G(n,p,q)$.

As we already noticed, this is a particular case of the class of problems (3.5) that we analyzed in Section 3.2. In our case,

with $\lambda$ defined in (1.5), and the feasible set is

In order to successfully apply Lemma 3.3, we will now choose a reference matrix $R$ so that it is close to (but also conveniently simpler than) the expectation of $B$. To do so, we can assume without loss of generality that $\mathcal{C}_{1}=\{1,\ldots,n/2\}$ and $\mathcal{C}_{2}=\{n/2+1,\ldots,n\}$. Then we define $R$ as a block matrix

where as usual $E_{n/2}$ denotes the $n/2\times n/2$ matrix whose all entries equal $1$.

Using the simple form of $R$, we can easily determine the form of the solution $Z_{R}$ of the reference problem (3.6).

2. Bounding the error

We are going to conclude from Lemma 4.1 and Lemma 3.3 that the maximizer of the actual objective function,

must be close to $Z_{R}$, the maximizer of the reference objective function.

Assume that $\bar{p}$ satisfies (4.1). Then, with probability at least $1-e^{3}5^{-n}$, we have

Finally, we use Lemma 3.3 to control the cross term in (5.4). To do this, notice that (5.1) and Lemma 5.1 imply that $R=\frac{p-q}{2}\cdot Z_{R}$. Then, by homogeneity, the conclusion of Lemma 3.3 implies that

To bound the norm of $R-B$, let us express this matrix as

and bound each of the three terms separately. According to Lemma 4.1 and Remark 4.4, we obtain that with probability larger than $1-e^{3}5^{-n}$,

Substituting these bounds into (5.7) and using triangle inequality along with the facts that $\|E_{n}\|_{\infty\to 1}=n^{2}$, $\|{\textbf{I}}_{n}\|_{\infty\to 1}=n$, we obtain

Since $\bar{p}\geq 9/n$, one can check that each of the last two terms is bounded by $\bar{p}^{1/2}n^{3/2}$. Thus we obtain $\|B-R\|_{\infty\to 1}\leq 8\bar{p}^{1/2}n^{3/2}$. Substituting into (5.6), we conclude that

The conclusion of the theorem will quickly follow from Lemma 5.2. Let us check the lemma’s assumption (4.1) on $\bar{p}$. A quick computation yields

where the last inequality follows from an assumption of Theorem 1.1. Thus the assumption (4.1) holds, and we can apply Lemma 5.2. It states that

with probability at least $1-e^{3}5^{-n}$. From (5.8), it is not difficult to see that $\bar{p}\leq\frac{p+q}{2}$. Substituting this into (5.9) and expressing $p=a/n$ and $q=b/n$, we conclude that

Rearranging the terms, we can see that this expression is bounded by $\varepsilon n^{2}$ if

But this inequality follows from the assumption (1.6).

The result follows from Davis-Kahan Theorem about the stability of the eigenvectors under matrix perturbations. The largest eigenvalue of $\bar{x}\bar{x}^{\mathsf{T}}$ is $n$ while all the others are 0, so the spectral gap equals $n$. Expressing $\widehat{Z}=(\widehat{Z}-\bar{x}\bar{x}^{\mathsf{T}})+\bar{x}\bar{x}^{\mathsf{T}}$ and using that $\|\widehat{Z}-\bar{x}\bar{x}^{\mathsf{T}}\|_{2}\leq\sqrt{\varepsilon}n$, we obtain from Davis-Kahan’s theorem (see for example Corollary 3 in ) that

Here $\hat{v}$ and $\bar{v}$ denote the unit-norm eigenvectors associated to the largest eigenvalues of $\widehat{Z}$ and $\bar{x}\bar{x}^{\mathsf{T}}$ respectively, and $\theta\in[0,\pi/2]$ is the angle between these two vectors. By definition, $\widehat{x}=\sqrt{n}\widehat{v}$ and $\bar{x}=\sqrt{n}\bar{v}$. This concludes the proof. ∎

General stochastic block model: proof of Theorem 1.3

In this section we focus on the community detection problem for the general stochastic block-model considered in Theorem 1.3. The semidefinite program (1.10) is a particular case of the class of problems (3.5) that we analyzed in Section 3.2. In our case, we set $B:=A$, choose the reference matrix to be

From the definition of the general stochastic block model we can recall that $\bar{A}=(p_{ij})$ has two types of entries. The entries larger than $p$ form the community blocks $\mathcal{C}_{k}\times\mathcal{C}_{k}$, $k=1,\ldots,K$. The number of such large entries is the same as the number of ones in the community membership matrix $\bar{Z}$, which in turn equals $\lambda$ by the choice we made in Theorem 1.3. All other entries of $\bar{A}$ are smaller than $q$. Thus the $\lambda$ largest entries of $\bar{A}$ form the community blocks $\mathcal{C}_{k}\times\mathcal{C}_{k}$, $k=1,\ldots,K$.

2. Bounding the error

We are going to conclude from Lemma 4.1 and Lemma 3.3 that the maximizer of the actual objective function,

must be close to $\bar{Z}$, the maximizer of the reference objective function. We will first show that the reference objective function $\langle\bar{A},Z\rangle$ distinguishes points near its maximizer $\bar{Z}$.

Substituting (6.5) and (6.6) into (6.4), we obtain the conclusion (6.3). ∎

Now we are ready to conclude that $\widehat{Z}\approx\bar{Z}$.

Assume that $\bar{p}$ satisfies (4.1). With probability at least $1-e^{3}5^{-n}$, we have

Using first Lemma 6.2, Lemma 3.3 (with $R=\bar{A}$ and $Z_{R}=\bar{Z}$ as before) and then Lemma 4.1, we obtain

with probability at least $1-e^{3}5^{-n}$. Lemma 6.3 is proved. ∎

The conclusion follows from Lemma 6.3. Indeed, substituting $p=a/n$, $q=b/n$ and $\bar{p}=g/n$ and rearranging the terms, we obtain

Since for any sequence $\sum|b_{i,j}|^{2}\leq\max|b_{i,j}|\sum|b_{i,j}|$, we get

As we noted in (6.1), all entries of $\widehat{Z}$ and $\bar{Z}$ belong to $$hence$\|\widehat{Z}-\bar{Z}\|_{\infty}\leq 1$. The bound for the Frobenius norm follows and Theorem 1.3 is proved. ∎

The balanced planted partition model.

In this section, we will show that a direct generalization of the semidefinite program (1.4) (instead a completely different program (1.10)) is capable of detecting multiple communities of equal sizes.

Assume that a graph on $n$ vertices $\{1,\ldots,n\}$ is partitioned in $K$ communities $\mathcal{C}_{1},\ldots,\mathcal{C}_{K}$ of equal sizes $s=n/K$. For each pair of distinct vertices, we draw an edge with probability $p$ if both vertices belong to the same community and with probability $q$ if not. This is known as the balanced partition model.

Let $A$ be the adjacency matrix of the random graph drawn according to the balanced partition model. The community structure of such a network is not only captured by the community membership matrix $\bar{Z}$ defined in (1.9) but also by the matrix $\bar{P}$ defined as

As we will see, $\bar{P}$ is an orthogonal projection with rank $K-1$. We are going to estimate $\bar{P}$ using the following semidefinite optimization problem:

For the value of $\lambda$, we choose the average degree of the graph as in (1.5), that is

This semidefinite program is a direct generalization of (1.4). Indeed, when there are two communities, that is $K=2$, the constraint $\min_{i,j}Z_{ij}\geq-1$ can be dropped since it follows from $\operatorname*{diag}(Z)\preceq{\textbf{I}}_{n}$ (3.4)).

Let $\varepsilon\in(0,1/2)$, $K,s,n$ be integers with $n\geq 10^{4}K/\varepsilon^{2}$ and $n=Ks$. Let $A=(a_{i,j})$ be the adjacency matrix of the random graph drawn from the balanced partition model described above, with $K$ communities of equal sizes $s$. Let $p=\frac{a}{s}>q=\frac{b}{s}$ be such that

Assume also that $\max\left\{a(1-p),(K-1)b(1-q)\right\}\geq 10$. Let $\widehat{Z}$ be a solution of the semidefinite program (7.2) and $\widehat{P}$ be the orthogonal projection onto the span of the eigenvectors associated to the $2K-3$ largest eigenvalues. Then, with probability at least $1-e^{3}5^{-n}$, we have

In the case of two communities, that is $K=2$, Theorem 7.1 yields the same conclusion as Corollary 1.2.

It comes from the proof that if $\varepsilon\leq 1/\sqrt{K-1}$, then the same conclusion holds true with $\widehat{P}$ replaced by the orthogonal projection onto the span of the eigenvectors associated to the $K-1$ largest eigenvalues of $\widehat{Z}$, thus making $\bar{P}$ and $\widehat{P}$ of the same rank.

We build all the steps in one proof. Without loss of generality we assume that $\mathcal{C}_{i}=\{(i-1)s+1,\ldots,is\}$ for all for all $i=1,\ldots,K$. Then $\bar{P}$ is the block matrix that has the following form:

In other words, $\bar{P}$ has $K^{2}$ blocks of size $s\times s$. The diagonal blocks equal $\frac{K-1}{sK}E_{s}$, the off-diagonal blocks equal $-\frac{1}{sK}E_{s}$, where as usual $E_{s}$ denotes the $s\times s$ matrix whose all entries equal $1$. Since $E_{s}^{2}=sE_{s}$, it is easily seen that $\bar{P}^{2}=\bar{P}$, so $\bar{P}$ is an orthogonal projection of rank $K-1$. We define the reference matrix $R$ as follows:

Let us compute the expectated values of $\lambda$ and $A$. By definition (7.3) of $\lambda$, we have

then with probability larger than $1-e^{3}5^{-n}$,

The second step of the argument consists of determining the form of the maximizer

To bound the error, we establish as in Lemma 5.2 that the maximizer of the actual objective function,

if $\max\left\{p(1-p),(K-1)q(1-q)\right\}\geq 10\,K/n$. Moreover,

Recall that $a>1$ and $b<a$ are such that $p=a/s=aK/n$, $q=b/s=bK/n$. Together with (7.8), this yields

Observe also that $\|Z_{R}\|_{2}^{2}=\frac{n^{2}}{K-1}$. With (7.4), we have proved that

For a symmetric $n\times n$ matrix $M$, $\{\lambda_{1}(M),\ldots,\lambda_{n}(M)\}$ is the set of eigenvalues of $M$ arranged in decreasing order, that is $\lambda_{1}(M)\geq\ldots\geq\lambda_{n}(M)$. Recall that $Z_{R}=\frac{sK}{K-1}\bar{P}$ is a multiple of an orthogonal projection of rank $(K-1)$ hence

From Weyl’s inequalities, see for example Theorem III.2.1 in , we have

since $\widehat{Z}\succeq 0$ and $\lambda_{K}(Z_{R})=0$. Hence $\lambda_{1}(\widehat{Z}-Z_{R})\geq\ldots\geq\lambda_{K-1}(\widehat{Z}-Z_{R})\geq 0$ and we deduce from (7.9) that

By definition, $\widehat{P}$ is the orthogonal projection onto the span of the eigenvectors of $\widehat{Z}$ associated to the eigenvalues $\{\lambda_{1}(\widehat{Z}),\ldots,\lambda_{2K-3}(\widehat{Z})\}$ and $({\textbf{I}}_{n}-\widehat{P})$ is the orthogonal projection onto the span of the eigenvectors of $\widehat{Z}$ associated to the eigenvalues $\{\lambda_{2K-2}(\widehat{Z}),\ldots,\lambda_{n}(\widehat{Z})\}$. Let

From (7.10), the projection onto the span of the eigenvectors of $Z_{R}$ whose eigenvalues belong to $S_{1}$ equals $\bar{P}$, thanks to the observation (7.7). From (7.11), the projection onto the span of the eigenvectors of $\widehat{Z}$ whose eigenvalues belong to $S_{2}$ equal $({\textbf{I}}_{n}-\widehat{P})$. And the gap between $S_{1}$ and $S_{2}$ equals $(1-\sqrt{\varepsilon})\frac{sK}{K-1}$. We deduce from a well-known theorem due to Davis and Kahan , see for example Theorem VII.3.1 in , that

and the conclusion of Theorem 7.1 follows from (7.9). ∎

References