Community Detection and Stochastic Block Models

Chapter 1 Introduction

The most basic task of community detection, or graph clustering, consists in partitioning the vertices of a graph into clusters that are more densely connected. From a more general point of view, community structures may also refer to groups of vertices that connect similarly to the rest of the graph without having necessarily a higher inner density, such as disassortative communities that have higher external connectivity. Note that the terminology of ‘community’ is sometimes used only for assortative clusters in the literature, but we adopt here the more general definition. Community detection may also be performed on graphs where edges have labels or intensities, and if these labels represent similarities among data points, the problem may be called data clustering. In this monograph, we will use the terms communities and clusters exchangeably. Further, one may also have access to interactions that go beyond pairs of vertices, such as in hypergraphs, and communities may not always be well separated due to overlaps. In the most general context, community detection refers to the problem of inferring similarity classes of vertices in a network by having access to measurements of local interactions.

Community detection and clustering are central problems in machine learning and data science. A large number of data sets can be represented as a network of interacting items, and one of the first features of interest in such networks is to understand which items are “alike,” as an end or as a preliminary step towards other learning tasks. Community detection is used in particular to understand sociological behavior [GZFA10, For10, NWS], protein to protein interactions [CY06, MPN+99], gene expressions [CSC+07, JTZ04], recommendation systems [LSY03, SC11, WXS+15], medical prognosis [SPT+01], DNA 3D folding [CAT15], image segmentation [SM97], natural language processing [BKN11], product-customer segmentation [CNM04], webpage sorting [KRRT99], and more.

The field of community detection has been expanding greatly since the 1980’s, with a remarkable diversity of models and algorithms developed in different communities such as machine learning, computer science, network science, social science and statistical physics. These rely on various benchmarks for finding clusters, in particular, cost functions based on cuts or modularities [GN02]. We refer to [New10, For10, GZFA10, NWS] for an overview of these developments.

Nonetheless, various fundamental questions remain unsettled, such as:

When are there really communities? Algorithms may output community structures, but are these meaningful or artefacts?

Can we always extract the communities when they are present; fully, partially?

What is a good benchmark to measure the performance of algorithms, and how good are the current algorithms?

The goal of this monograph is to describe recent developments aimed at answering these questions in the context of block models. Block models are a family of random graphs with planted clusters. The “mother model” is the stochastic block model (SBM), which has been widely employed as a canonical model for community detection. It is arguably the simplest model of a graph with communities (see definitions in the next section). Since the SBM is a generative model, it benefits from a ground truth for the communities, which allows us to consider the previous questions in a formal context. Like any model, it is not necessarily realistic, but it is insightful - judging for example from the powerful algorithms that have emerged from its study.

In a sense, the SBM plays a similar role to the discrete memoryless channel (DMC) in information theory. While the task of modelling external noise may be more amenable to simplifications than real data sets, the SBM captures some of the key bottleneck phenomena for community detection and admits many possible refinements that improve its fit to real data. Our focus here will be on the fundamental understanding of the “canonical SBM,” without diving too much into the refined extensions.

Further generalizations allow for labelled edges and continuous vertex labels, connecting to low-rank approximation models and graphons (using the latter terminology as adapted in the statistics literature). For example, a spiked Wigner model with observation $Y=XX^{T}+Z$, where $X$ is an unknown vector and $Z$ is Wigner, can be viewed as a labeled graph where edge $(i,j)$’s label is given by $Y_{ij}=X_{i}X_{j}+Z_{ij}$. If the $X_{i}$’s take discrete values, e.g., $\{1,-1\}$, this is closely related to the stochastic block model—see [DAM15] for a precise connection. Continuous labels can also model Euclidean connectivity kernels, an important setting for data clustering. In general, models where a collection of variables $\{X_{i}\}$ have to be recovered from noisy observations $\{Y_{ij}\}$ that are stochastic functions of $X_{i},X_{j}$, or more generally that depend on local interactions of some of the $X_{i}$’s, can be viewed as inverse problems on graphs or hypergraphs that bear similarities with the basic community detection problems discussed here. This concerns in particular topic modelling, ranking, synchronization problems and other unsupervised learning problems. We refer to Section 9 for further discussion on these. The specificity of the stochastic block model is that the input variables are discrete.

A first hint at the centrality of the SBM comes from the fact that the model appeared independently in numerous scientific communities. It appeared under the SBM terminology in the context of social networks in the machine learning and statistics literature [HLL83], while the model is typically called the planted partition model in theoretical computer science [BCLS87, DF89, Bop87], and the inhomogeneous random graph in the mathematics literature [BJR07]. The model takes also different interpretations, such as a planted spin-glass model [DKMZ11], a sparse-graph code [ABH16, AS15a] or a low-rank (spiked) random matrix model [McS01, Vu14, DAM15] among others.

In addition, the SBM has recently turned into more than a model for community detection. It provides a fertile ground for studying various central questions in machine learning, computer science and statistics: It is rich in phase transitions [DKMZ11, Mas14, MNS, ABH16, AS15a], allowing us to study the interplay between statistical and computational barriers [YC14, AS15d, BMNN16, AS17], as well as the discrepancies between probabilstic and adversarial models [MPW16], and it serves as a test bed for algorithms, such as SDPs [ABH16, WXH15, HWX15a, GV16, AL14, ABKK15, MS16, PW], spectral methods [Vu14, XLM14, Mas14, KMM+13, BLM15, YP14a], and belief propagation [DKMZ11, AS15c].

2 Fundamental limits: information and computation

This monograph focuses on the fundamental limits of community detection. The term ‘fundamental limit’ is used to emphasize the fact that we seek conditions for recovering the communities that are necessary and sufficient. In the information-theoretic sense, this means finding conditions under which a given task can or cannot be resolved irrespective of complexity or algorithmic considerations, whereas in the computational sense, this further constrains the algorithms to run in polynomial time in the number of vertices. As we shall see in this monograph, such fundamental limits are often expressed through phase transitions, which provide sharp transitions in the relevant regimes between phases where the given task can or cannot be resolved.

Fundamental limits have proved to be instrumental in the developments of algorithms. A prominent example is Shannon’s coding theorem [Sha48], which gives a sharp threshold for coding algorithms at the channel capacity, and which has led the development of coding algorithms for more than 60 years (e.g., LDPC, turbo or polar codes) at both the theoretical and practical level [RU01]. Similarly, the SAT threshold [ANP05] has driven the developments of a variety of satisfiability algorithms such as survey propagation [MPZ03].

In the area of clustering and community detection, where establishing rigorous benchmarks is a long standing challenge, the quest of fundamental limits and phase transitions is also impacting the development of algorithms. As discussed in this monograph, this has already lead to developments of algorithms such as sphere-comparisons, linearized belief propagation, nonbacktracking spectral methods. Fundamental limits also shed light on the limitations of the model versus those of the algorithms used; see Section 1.3. However, unlike in the data transmission context of Shannon, information-theoretic limits may not always be efficiently achievable in community detection, with information-computation gaps that may emerge as discussed in Section 8.

3 An example on real data

This monograph focuses on the fundamentals of community detection, but we want to give an application example here. We use the blogosphere data set from the 2004 US political elections [AG05] as an archetype example.

Consider the problem where one is interested in extracting features about a collection of items, in our case $n=1,222$ individuals writing about US politics, observing only some of their interactions. In our example, we have access to which blogs refers to which (via hyperlinks), but nothing else about the content of the blogs. The hope is to extract knowledge about the individual features from these simple interactions.

To proceed, build a graph of interaction among the $n$ individuals, connecting two individuals if one refers to the other, ignoring the direction of the hyperlink for simplicity. Assume next that the data set is generated from a stochastic block model; assuming two communities is an educated guess here, but one can also estimate the number of communities (e.g., as in [AS15d]). The type of algorithms developed in Sections 7.2 and 7.1 can then be run on this data set, and two assortative communities are obtained. In the paper [AG05], Adamic and Glance recorded which blogs are right or left leaning, so that we can check how much agreement the algorithms give with the true partition of the blogs. The results give about 95% agreement on the blogs’ political inclinations (which is roughly the state-of-the-art [New11, Jin15, GMZZ15]).

Despite the fact that the blog data set is particularly ‘well behaved’–there are two dominant clusters that are well balanced and well separated–the above approach can be applied to a broad collection of data sets to extract knowledge about the data from graphs of similarities or interactions. In some applications, the graph is obvious (such as in social networks with friendships), while in others, it is engineered from the data set based on metrics of similarity/interactions that need to be chosen properly (e.g, similarity of pixels in image segmentation). The goal is to apply such approaches to problems where the ground truth is unknown, such as to understand biological functionality of protein complexes; to find genetically related sub-populations; to make accurate recommendations; medical diagnosis; image classification; segmentation; page sorting; and more (see references in the introduction).

In such cases where the ground truth is not available, a key question is to understand how reliable the algorithms’ outputs may be. We now discuss how the results presented in this monograph add to this question. Following the definitions from Sections 7.2 and 7.1, the parameters estimated by fitting an SBM on this data set in the constant degree regime are

Following the definitions of Theorem 30 from Section 7.2, we can now compute the SNR for these parameters in the constant-degree regime, obtaining $\lambda_{2}^{2}/\lambda_{1}\approx 18$ which is much greater than 1. Thus, under an SBM model, the data is largely in a regime where communities can be detected, i.e., above the weak recovery threshold. Following the definitions of Theorem 25 from Section 7.1, we can also compute the CH-divergence for these parameters in the logarithmic-degree regime, obtaining $J(p,Q)\approx 2$ which is also greater than 1. Thus, under an SBM and with an asymptotic approximation, the data is in a regime where the graph communities can in fact be recovered entirely, i.e, above the exact recovery threshold. This does not answer whether the SBM is a good or a bad model, but it gives that under this model, the data appears to be in a strong ‘clusterable regime.’

Note also that such a conclusion may not appear using a specific algorithm, e.g., one that is sensitive to the degree variations and that may split the vertices into high vs. low-degree vertices. This prompted for example the development of degree-corrected SBMs in [KN11], as the algorithm used in [KN11] for the blog data set with the fitting of an SBM failed for such reasons. However, how do we know whether the failure is due to the model or the algorithm? By establishing the fundamental limits on the SBM, we will find algorithms that are ‘maximally’ robust by succeeding in the most challenging regimes, i.e., down to the fundamental limits, which achieve in particular the positive accuracy for the blog data set described in Figure 1.2. We also refer to Section 5.3.2 for discussions on the robustness of algorithms to degree variations.

4 Historical overview of the recent developments

This section provides a brief historical overview of the recent developments discussed in this monograph. The resurgent interest in the SBM and its ‘modern study’ have been initiated in part due to the paper of Decelle, Krzakala, Moore and Zdeborová [DKMZ11], which conjecturedThe conjecture of the Kesten-Stigum threshold in [DKMZ11] was formulated with what we call in this note the max-detection criteria, asking for an algorithm to output a reconstruction of the communities that strictly improves on the trivial performance achieved by putting all the vertices in the largest community. This conjecture is formally incorrect for general SBMs, see [AS17] for a counter-example, as the notion of max-detection is too strong in some cases. The conjecture is believed to hold for symmetric SBMs, as re-stated in [MNS15], but it requires a different notion of detection to hold for general SBMs; see definitions from [AS17] discussed in Section 7.2. phase transition phenomena for the weak recovery (a.k.a. detection) problem at the Kesten-Stigum threshold and the information-computation gap at 4 symmetric communities in the symmetric case. These conjectures are backed in [DKMZ11] with insights from statistical physics, based on the cavity method (belief propagation), and provide a detailed picture of the weak recovery problem, both for the algorithmic and information-theoretic behavior. With such insights, a new research program started driven by the phase transition phenomena.

One of the first papers that obtained a non-trivial algorithmic result for the weak recovery problem is [CO10] from 2010, which appeared before the conjecture (and does not achieve the threshold by a logarithmic degree factor). The first paper that made progress on the conjecture is [MNS15] from 2012, which proved the impossibility part of the conjecture for two symmetric communities, introducing various key concepts in the analysis of block models. In 2013, [MNS13] also obtained a result on the partial recovery of the communities, expressing the optimal fraction of mislabelled vertices when the signal-to-noise ratio is large enough in terms of the broadcasting problem on trees [KS66, EKPS00].

The positive part of the conjecture for efficient algorithm and two communities was first proved in 2014 with [Mas14] and [MNS], using respectively a spectral method from the matrix of self-avoiding walks and weighted non-backtracking walks between vertices.

In 2014, [ABH14, ABH16] and [MNS14] found that the exact recovery problem for two symmetric communities has also a phase transition, in the logarithmic rather than constant degree regime, shown to be also efficiently achievable. This relates to a large body of work from the first decades of research on the SBM [BCLS87, DF89, Bop87, SN97, CK99, McS01, BC09, CWA12, Vu14, YC14], driven by the exact or almost exact recovery problems without sharp thresholds.

In 2015, the phase transition for exact recovery was obtained for the general SBM [AS15a, AS15d], and shown to be efficiently achievable irrespective of the number of communities. For the weak recovery problem, [BLM15] showed that the Kesten-Stigum threshold can be achieved with a spectral method based on the nonbacktracking (edge) operator in a fairly general setting (covering SBMs that are not necessarily symmetric), but felt short of settling the conjecture for more than two communities in the symmetric case due to technical reasons. The approach of [BLM15] is based on the ‘spectral redemption’ conjecture made in 2013 in [KMM+13], which introduced the use of the nonbacktracking operator as a linearization of belief propagation. This is one of the most elegant approaches to the weak recovery problem, except perhaps for the fact that the matrix is not symmetric (note that the first proof of [Mas14] does provide a solution with a symmetric matrix via the count of self-avoiding walks, albeit less direct to construct). The general conjecture for arbitrary many symmetric or asymmetric communities is settled later in 2015 with [AS15c, AS17], relying on a higher-order nonbacktracking matrix and a message passing implementation. It was further shown in [AS15c, AS17] that it is possible to cross information-theoretically the Kesten-Stigum threshold in the symmetric case at 4 communities, settling both positive parts of the conjectures from [DKMZ11]. Crossing at 5 rather than 4 communities is also obtained in [BM16, BMNN16], which further obtains the scaling of the information-theoretic threshold for a growing number of communities.

In 2016, a tight expression was obtained for partial recovery with two communities in the regime of finite SNR with diverging degrees in [DAM15] and [MX15] for a different distortion measure. This also gives the threshold for weak recovery in the regime where the SNR is finite while the degrees are diverging.

Other major lines of work on the SBM have been concerned with the performance of SDPs, with a precise picture obtained in [GV16, MS16, JMR16] for the weak recovery problem and in [ABH16, WXH15, AL14, Ban15, ABKK15, PW] for the (almost) exact recovery problem; as well as with spectral methods on classical operators [McS01, CO10, CRV15, XLM14, Vu14, YP14a, YP15]. A detailed picture has also been developed for the problem of a single planted community in [Mon15, HWX15c, HWX15b, CLM16]. Recently, attention has been paid to graphs that have a larger number of short loops [AMM+17, ABS17a, GMPS17, ABS17b]. There is a much broader list of works on the SBMs that is not covered in this monograph, especially before the ‘recent developments’ discussed above but also after. It is particularly challenging to track the vast literature on this subject as it is split between different communities of statistics, machine learning, mathematics, computer science, information theory, social sciences and statistical physics. This monograph mainly covers developments until 2016, with some references from 2017 There a few additional surveys available; community detection and statistical network models are discussed in [New10, For10, GZFA10], and C. Moore has a recent overview paper [Moo17] that focuses on the weak recovery problem with emphasis on the cavity method.

In the table below, we summarize the main thresholds proved for weak and exact recovery, covered in several chapters of this monograph:

5 Outline

In the next section, we formally define the SBM and various recovery requirements for community detection, namely exact, weak, and partial recovery. We then start with a quick overview of the key approaches for these recovery requirements in Section 3, introducing the key new concepts obtained in the recent developments. We then treat each of these three recovery requirements separately for the two community SBM in Sections 7.1, 7.2 and 6 respectively, discussing both fundamental limits and efficient algorithms. We give complete (and revised) proofs for exact recovery and partial proofs for weak and partial recovery. We then move to the results for the general SBM in Section 7. In Section 9 we discuss other block models, such as geometric block models, and in Section 10 we give concluding remarks and open problems.

6 Notations

We use the standard little-o and big-o notations. Recall that $a_{n}=\Omega(b_{n})$ means that $b_{n}=O(a_{n})$, and $a_{n}=\omega(b_{n})$ means that $b_{n}=o(a_{n})$. In particular, $a_{n}=o(1)$ means that $a_{n}$ is vanishing, $a_{n}=\Omega(1)$ means that $a_{n}$ is non-vanishing, and $a_{n}=\omega(1)$ means that $a_{n}$ is diverging. We use $a_{n}\lesssim b_{n}$ when $a_{n}=\Omega(b_{n})$; $a_{n}\ll b_{n}$ when $a_{n}=o(b_{n})$ (and $a_{n}\gg b_{n}$ when $b_{n}=o(a_{n})$); $a_{n}=\Theta(b_{n})$, or equivalently $a_{n}\asymp b_{n}$, when we simultaneously have $a_{n}=\Omega(b_{n})$ and $a_{n}=O(b_{n})$; $a_{n}\sim b_{n}$ when $a_{n}=b_{n}(1+o(1))$.

Chapter 2 The stochastic block model

The history of the SBM is long, and we omit a comprehensive treatment here. As mentioned earlier, the model appeared independently in multiple scientific communities: the term SBM, which seems to have dominated in the recent years, comes from the machine learning and statistics literature [HLL83], while the model is typically called the planted partition model in theoretical computer science [BCLS87, DF89, Bop87], and the inhomogeneous random graphs model in the mathematics literature [BJR07].

Thus the distribution of $(X,G)$ where $G=([n],E(G))$ is defined as follows; for $x\in[k]^{n}$ and $y\in\{0,1\}^{{n\choose 2}}$,

Except for Section 10, we assume that $p$ does not scale with $n$, whereas $W$ typically does. As a consequence, the number of communities does not scale with $n$ and the communities have linear size. Nonetheless, various results discussed in this monograph should extend (by inspection) to cases where $k$ is growing slowly enough.

Note that by the law of large numbers, almost surely,

Alternative definitions of the SBM require $X$ to be drawn uniformly at random with the constraint that $\frac{1}{n}|\{v\in[n]:X_{v}=i\}|=p_{i}+o(1)$, or $\frac{1}{n}|\{v\in[n]:X_{v}=i\}|=p_{i}$ for consistent values of $n$ and $p$ (e.g., $n/2$ being an integer for two symmetric communities). For the purpose of this paper, these definitions are essentially equivalent, and we may switch between the models to simplify some proofs.

Note also that if all entries of $W$ are the same, then the SBM collapses to the Erdős-Rényi random graph, and no meaningful reconstruction of the communities is possible.

2 The symmetric SBM

The SBM is called symmetric if $p$ is uniform and if $W$ takes the same value on the diagonal and the same value outside the diagonal.

3 Recovery requirements

The goal of community detection is to recover the labels $X$ by observing $G$, up to some level of accuracy. We next define the notions of agreement.

The agreement between two community vectors $x,y\in[k]^{n}$ is obtained by maximizing the common components between $x$ and any relabelling of $y$, i.e.,

Note that the relabelling permutation is used to handle symmetric communities such as in SSBM, as it is impossible to recover the actual labels in this case, but we may still hope to recover the partition. In fact, one can alternatively work with the community partition $\Omega=\Omega(X)$, defined earlier as the unordered collection of the $k$ disjoint unordered subsets $\Omega_{1},\dots,\Omega_{k}$ covering $[n]$ with $\Omega_{i}=\{u\in[n]:X_{u}=i\}$. It is however often convenient to work with vertex labels. Further, upon solving the problem of finding the partition, the problem of assigning the labels is often a much simpler task. It cannot be resolved if symmetry makes the community label non identifiable, such as for SSBM, and it is trivial otherwise by using the community sizes and clusters/cuts densities.

and $\|p\|_{2}^{2}=1/k$ in the case of $p$ uniform. Thus an agreement becomes interesting only when it is above this value.

One can alternatively define a notion of component-wise agreement. Define the overlap between two random variables $X,Y$ on $[k]$ as

and $O^{*}(X,Y)=\max_{\pi\in S_{k}}O(X,\pi(Y))$. In this case, for $X,\hat{X}$ i.i.d. under $p$, we have $O^{*}(X,\hat{X})=0$.

When discussing impossibility for weak recovery in the SSBM (Section 5.2.1), we also use an alternative definition for which the conditional mutual information between an arbitrary pair of vertices $u\neq v$ vanishes, i.e.,

as $n\to\infty$. Note that if this mutual information between two arbitrary vertices $u$ and $v$ is vanishing, i.e., the two vertex labels are asymptotically independent conditioned on the graph, then it is not possible to obtain a reconstruction of all vertices that solves weak recovery.

All recovery requirements in this note are going to be asymptotic, taking place with high probability as $n$ tends to infinity. We also assume in the following sections—except for Section 2.5—that the parameters of the SBM are known when designing the algorithms.

Different terminologies are sometimes used in the literature, with following equivalences:

almost exact recovery $\iff$ weak consistency

Sometimes ‘exact recovery’ is also called just ‘recovery’ and ‘almost exact recovery’ is called ‘strong recovery.’

As mentioned above, values of $\alpha$ that are too small may not be interesting or realizable. In the symmetric SBM with $k$ communities, an algorithm that ignores the graph and simply draws $\hat{X}$ i.i.d. under $p$ achieves an accuracy of $1/k$. Thus the problem becomes interesting when $\alpha>1/k$, leading to the following definition.

As shown in [AS17], the previous definition is not the right definition to capture the Kesten-Stigum threshold in the general case. In other words, the conjecture that max-detection is always possible above the Kesten-Stigum threshold is not accurate in general SBMs. Back to our example with communities of relative sizes $(0.8,0.2)$, an algorithm that could find a set containing $2/3$ of the vertices from the large community and $1/3$ of the vertices from the small community would not satisfy the above above weak recovery criteria, while the algorithm produces nontrivial amounts of evidence on what communities the vertices are in. To be more specific, consider a two community SBM where each vertex is in community 1 with probability $0.99$, each pair of vertices in community 1 have an edge between them with probability $2/n$, while vertices in community 2 never have edges. Regardless of what edges a vertex has it is more likely to be in community 1 than community 2, so weak recovery according to the above definition is not impossible, but one can still divide the vertices into those with degree 0 and those with positive degree to obtain a non-trivial detection—see [AS17] for a formal counter-example.

Using the normalized agreement fixes this issue. Weak recovery can then be defined as obtaining with high probability a weighted agreement of

and this applies to the general SBM. Another definition of weak recovery that seems easier to manipulate and that implies the previous one is as follows; note that this definition requires a single partition even for the general SBM.

where we recall that $\Omega_{i}=\{u\in[n]:X_{u}=i\}$.

In other words, an algorithm solves weak recovery if it divides the graph’s vertices into two sets such that vertices from two different communities have different probabilities of being assigned to one of the sets. With this definition, putting all vertices in one community does not detect, since $|\Omega_{i}\cap S|/|\Omega_{i}|=1$ for all $i\in[k]$. Further, in the symmetric SBM, this definition implies Definition 5 provided that we fix the output:

If an algorithm solves weak recovery in the sense of Definition 7 for a symmetric SBM, then it solves max-detection (or detection according to Decelle et al. [DKMZ11]), provided that we consider it as returning $k-2$ empty sets in addition to its actual output.

See [AS16] for the proof. The above extends to other weakly symmetric SBMs, i.e., those that have constant expected degrees, but not all.

Finally, note that our notion of weak recovery requires us to separate at least two communities $i,j\in[k]$. One may ask for a definition where two specific communities need to be separated:

There are at least two additional questions that are natural to ask about SBMs, both can be asked for efficient or information-theoretic algorithms:

Distinguishability (or testing): Consider an hypothesis test where a random graph $G$ is drawn with probability $1/2$ from an SBM model (with same expected degree in each community) and with probability $1/2$ from an Erdős-Rényi model with matching expected degree. Is is possible to decide with asymptotic probability $1-o(1)$ from which ensemble the graph is drawn? In particular, this is not possible if the total variation distance between the two ensembles is vanishing. This problem is sometimes called ‘detection’, which partly explains why we prefer to use ‘weak recovery’ in lieu of ‘detection’ for the reconstruction problem discussed earlier. Distinguishability is further discussed in Section 8.

The obvious implications are: exact recovery $\Rightarrow$ almost exact recovery $\Rightarrow$ partial recovery $\Rightarrow$ weak recovery $\Rightarrow$ distinguishability, and almost exact recovery $\Rightarrow$ learnability. Moreover, for symmetric SBMs with two symmetric communities: learnability $\Leftrightarrow$ weak recovery $\Leftrightarrow$ distinguishability, but these are broken for general SBMs; see Section 2.5.

4 SBM regimes and topology

Before discussing when the various recovery requirements can be solved or not in SBMs, it is important to recall a few topological properties of the SBM graph.

When all the entries of $W$ are the same and equal to $w$, the SBM collapses to the Erdős-Rényi model $G(n,w)$ where each edge is drawn independently with probability $w$. Let us recall a few basic results for this model derived mainly from [ER60]:

$G(n,c\log(n)/n)$ is connected with high probability if and only if $c>1$,

$G(n,c/n)$ has a giant component (i.e., a component of size linear in $n$) if and only if $c>1$.

For $a,b>0$, SSBM$(n,k,a\log n/n,b\log n/n)$ is connected with high probability if and only if $\frac{a+(k-1)b}{k}>1$ (if $a$ or $b$ is equal to 0, the graph is of course not connected).

SSBM$(n,k,a/n,b/n)$ has a giant component (i.e., a component of size linear in $n$) if and only if $d:=\frac{a+(k-1)b}{k}>1$,

and is not connected with high probability if $\min_{i\in[k]}\|(\operatorname{diag}(p)Q)_{i}\|_{1}<1$, where $(\operatorname{diag}(p)Q)_{i}$ is the $i$-th column of $\operatorname{diag}(p)Q$.

These results are important to us as they already point regimes where exact or weak recovery are not possible. Namely, if the SBM graph is not connected, exact recovery is not possible (since there is no hope to label disconnected components with higher chance than $1/2$), hence exact recovery can take place only if the SBM parameters are in the logarithmic degree regime. In other words, exact recovery in SSBM$(n,k,a\log n/n,b\log n/n)$ is not solvable if $\frac{a+(k-1)b}{k}<1$. This is however unlikely to provide a tight condition, i.e., exact recovery is not equivalent to connectivity, and the next section will precisely investigate how much more than $\frac{a+(k-1)b}{k}>1$ is needed to obtain exact recovery. Similarly, it is not hard to see that weak recovery is not solvable if the graph does not have a giant component, i.e., weak recovery is not solvable in SSBM$(n,k,a/n,b/n)$ if $\frac{a+(k-1)b}{k}<1$, and we will see in Section 7.2 how much more is needed to go from the giant component to weak recovery.

5 Learning the model

In this section we overview the results on estimating the SBM parameters by observing a realization of the graph. The estimation problem tends to be ‘easier’ than the recovery problems, although some problems remain for the general sparse SBM, see Section 2.5.2. We consider first the case where degrees are diverging, where estimation can be obtained as a side result of universal almost exact recovery, and the case of constant degrees, where estimation can be performed without being able to recover the clusters but only above the weak recovery threshold.

For diverging degrees, one can estimate the parameters by first solving almost exact recovery without knowing the parameters, and proceeding then to estimate the parameters by simply computing the clusters’ cuts and volumes. This requires solving a potentially harder problem, but it turns out to be achievable:

The algorithm used in this theorem (agnostic-sphere-comparison) is discussed in section 6.1 in the context of two communities and is based on comparing neighborhoods of vertices. Note that assumption that $\delta$ is given in this theorem can be removed when $\alpha=\omega(1)$, i.e., when the degrees diverge. We then obtain:

[AS15d] The number of communities $k$, the community prior $p$ and the connectivity matrix $Q$ can be consistently estimated in quasi-linear time in SBM$(n,p,\omega(1)Q/n)$.

Note that for symmetric SBMs, certain algorithms such as SDPs or spectral algorithms discussed in Section 3 can also be used to recover the communities without knowledge of the parameters, and thus to learn the parameters in the symmetric case. A different line of work has also studied the problem of estimating ‘graphons’ [CWA12, ACC13, OW14] via block models, assuming regularity conditions on the graphon, such as piecewise Lipschitz, to obtain estimation guarantees. In addition, [BCS15] considers private graphon estimation in the logarithmic degree regime, and obtains a non-efficient procedure to estimate ‘graphons’ in an appropriate version of the $L_{2}$ norm. More recently, [BCCG15] extends the type of results from [WO13] to a much more general family of ‘graphons’ and to sparser regimes (though still with diverging degrees) with efficient methods (based on degrees) and non-efficient methods (based on least square and least cut norm).

5.2 Constant degree regime

In the case of the constant degree regime, it is not possible to recover the clusters fully, and thus estimation has to be done differently. The first paper that shows how to estimate tightly the parameter in this regime is [MNS15], which is based on approximating cycle counts by nonbacktracking walks. An alternative method based on expectation-maximization using the Bethe free energy is also proposed in [DKMZ11] (without a rigorous analysis).

This theorem is extended in [AS15c] for the symmetric SBM with $k$ clusters, where $k$ is also estimated. The first step needed is the following estimate.

To see this lemma, note that there is a cycle on a given selection of $m$ vertices with probability

Since there are $\sim n^{m}/2m$ such selections, the first moment follows. The second moment follows from the fact that overlapping cycles do not contribute to the second moment. See [MNS15] for proof details for the 2-SSBM and [AS15c] for the general SBM.

However, for the general SBM, the problem is more delicate and one has to first stabilize the cycle count statistics to extract the eigenvalues of $PQ$, and use weak recovery methods to further peel down the parameters $p$ and $Q$. Deciding which parameters can or cannot be learned in the general SBM seems to be a non-trivial problem. This is also expected to come into play in the estimation of graphons [CWA12, ACC13, BCS15].

Chapter 3 Tackling the stochastic block model

In this section, we discuss how to tackle the problem of community detection for the various recovery requirements of Section 4. One feature of the SBM is that it can (and has) been viewed from many different angles. In particular, we will pursue here the algebraic and information-theoretic (or statistical) interpretations, viewing the SBM:

As a low-rank perturbation model: the adjacency matrix of the SBM has low rank in expectation; thus one may hope to characterize its behavior, e.g., its eigenvectors, as perturbations of its expected counterparts. For example, the expected adjacency matrix of a two-community SBM$(n,p,Q/n)$ has the form:

As a noisy channel: the SBM graph can be viewed as the output on a channel that takes the community memberships as inputs. In particular, this corresponds to a memoryless channel encoded with a sparse graph code as in Figure 3.1.

A natural starting point (e.g., from viewpoint 2) is to resolve the estimation of $X$ from the noisy observation $G$ by taking the Maximum A Posteriori estimator. Upon observing $G$, if one estimates the community partition $\Omega=\Omega(X)$ with $\hat{\Omega}(G)$, the probability of error is given by

In the two-community case, denoting by $N_{in}$ and $N_{out}$ the number of edges inside and across the clusters respectively,

i.e., a balanced partition with the least number of crossing edges.

Since MAP minimizes the probability of making an error for the reconstruction of the entire partition $\Omega$, it minimizes the error probability for exact recovery. Thus, if MAP fails in solving exact recovery, no other algorithm can succeed. In addition, MAP may not be optimal for weak recovery, since the most likely partition may not necessarily maximize the agreement. To see this, consider for example the uniform SSBM in a sparse regime with $a+b$ slightly above $2$. In this case, the graph has a giant component that contains less than half of the vertices, and there are various balanced partitions of the graph that have zero crossing edges (they separate the giant component from a collection of small disconnected components). Clearly, these are min-bisections, but they do not solve weak recovery. Nonetheless, weak recovery can still be solved in some of these cases:

Note that such an argument is harder to establish if one restricts the min-bisection to the giant component (though we still conjecture that MAP can fail at weak recovery with this restriction). We summarize the two points obtained so far:

Fact 1: If MAP does not solve exact recovery, then exact recovery is not solvable.

Fact 2: Weak recovery may still be solvable when MAP does not solve weak recovery.

2 Computing block MAP: spectral and SDP relaxations

Exactly resolving the maximization in (3.3) requires comparing exponentially many terms a priori, so the MAP estimator may not always reveal the computational threshold for exact recovery. In fact, in the worst-case model, min-bisection is NP-hard, and approximations leave a polylogarithmic integrality gap [KF06]. Various relaxations have been proposed for the MAP estimator. Here we review two of the main ideas.

Spectral relaxations. Consider again the symmetric SBM with strictly balanced communities. Recall that MAP maximizes

since this counts the number of edges inside the clusters minus the number of edges across the clusters, which is equivalent to the min-bisection problem (the total number of edges being fixed by the graph). The general idea behind spectral methods is to relax the integral constraint to an Euclidean constraint on real valued vectors. This leads to looking for a maximizer of

Without the constraint $x^{t}1^{n}=0$, the above maximization gives precisely the eigenvector corresponding to the largest eigenvalue of $A$. Note that $A1^{n}$ is the vector containing the degrees of each node in $g$, and when $g$ is an instance of the symmetric SBM, this concentrates to the same value for each vertex, and $1^{n}$ is close to an eigenvector of $A$. Since $A$ is real symmetric, this suggests that the constraint $x^{t}1^{n}=0$ leads the maximization (3.6) to focus on the eigenspace orthogonal to the first eigenvector, and thus to the eigenvector corresponding to the second largest eigenvalue. Thus it is reasonable to take the second largest eigenvector $\phi_{2}(A)$ of $A$ and round it to obtain an efficient relaxation of MAP:

We will discuss later on whether this is a good algorithm or not (in brief, it works well in the exact recovery regime but not in the weak recovery regime). Equivalently, one can write the MAP estimator as a minimizer of

since the above minimizes the size of the cut between two balanced clusters. From simple algebraic manipulations, this is equivalent to looking for minimizers of

where $L$ is the Laplacian of the graph, i.e.,

The challenge with such ‘basic’ spectral methods is that, as the graph becomes sparser, the fluctuations in the node degrees become more important, and this can disrupt the second largest eigenvector from concentrating on the communities (it may concentrate instead on large degree nodes). To analyze this, one may express the adjacency matrix as a perturbation of its expected value, i.e.,

When indexing the first $n/2$ rows and columns to be in the same community, the expected adjacency matrix takes the following block structure

hence defining $X:=xx^{t}$, we can write (3.13) as

A possible approach to handle the constraint $X1^{n}=0$ is to again use a centering of $A$. For example, one can replace the adjacency matrix $A$ by the matrix $B$ such that $B_{ij}=1$ if there is an edge between vertices $i$ and $j$, and $B_{ij}=-1$ otherwise. Using $-T$ for a large $T$ instead of $-1$ for non-edges would force the clusters to be balanced, and it turns out that $-1$ is already sufficient for our purpose. This gives another SDP:

We will further discuss the performance of SDPs in Section 4.3.2. In brief, they work well for exact recovery, and while they are suboptimal for weak recovery, they are not as senstive as vanilla spectral methods to degree variations. However, the complexity of SDPs is significantly higher than that of spectral methods. We will also discuss how other spectral methods can afford optimality in both the weak and exact recovery regimes while preserving a quasi-linear time complexity. Notice however that we are putting the cart before the horse by talking about weak recovery now: we viewed spectral and SDP methods as relaxations of the MAP estimator, which is only an optimal estimator for exact recovery. These relaxations may still work for weak recovery, but the connection is less clear. Let us thus move to what would be the objective of merit for weak recovery.

3 The bit MAP estimator

If block MAP is not optimal for weak recovery, what is the right objective? To answer this more easily in the symmetric SBM, we have to in some way break the symmetry again, as done in the previous section using the partition function $\Omega(X)$. This is slightly more technical for weak recovery. We use a different trick to avoid uninteresting technicalities, and consider a weakly symmetric SBM. I.e., consider a two-community SBM with a Bernoulli prior given by $(p_{1},p_{2})$, $p_{1}\neq p_{2}$, and connectivity $Q/n$ such that $PQ$ has two rows with the same sum. In other words, the expected degree of every vertex is the same (and weak recovery is non-trivial), but the model is slightly asymmetrical and one can determine the community labels from the partition. In this case, we can work with the agreement between the true labels and the algorithm reconstruction without use of the relabelling $\pi$, i.e.,

Consider now an algorithm that maximizes the expected agreement, i.e,

To solve weak recovery, one needs a non-trivial expected agreement, and to maximize the above, one has to maximize each term given by

4 Computing bit MAP: belief propagation

Set $v_{0}$ to be a specific vertex in $G$. Let $v_{1},...v_{m}$ be the vertices that are adjacent to $v_{0}$, and define the vectors $q_{1},...,q_{m}$ such that for each community $i$ and vertex $v_{j}$,

Assume for a momentThis is where the symmetry breaking based on large degree vertices discussed in the previous footnote is convenient, as it allows to make the statement. that, ignoring $v_{0}$, the probability distributions of $X_{v_{1}},X_{v_{2}},...,X_{v_{m}}$ are asymptotically independent, i.e., for all $x_{1},...,x_{m}$,

This is a reasonable assumption in the sparse SBM because the graph is locally tree-like, i.e., with probability $1-o(1)$, for every $i$ and $j$, every path between $v_{i}$ and $v_{j}$ in $G\backslash\{v_{0}\}$ has a length of $\Omega(\log n)$. So we would expect that knowing the community of $v_{i}$ would provide little evidence about the community of $v_{j}$. Then, with high probability,

One can now iterate this reasoning. In order to estimate $P[X_{v}=i|G=g]$, one needs $P[X_{v_{j}}=i^{\prime}|G\backslash\{v\}=g\backslash\{v\}]$ for all community labels $i^{\prime}$ and all $v_{j}$ adjacent to $v$. In order to compute those, one needs $P(X_{v^{\prime}}=i^{\prime}|G\backslash\{v,v_{j}\}=g\backslash\{v,v_{j}\})$ for all $v_{j}$ adjacent to $v$, $v^{\prime}$ adjacent to $v_{j}$, and every community label $i^{\prime}$. To apply the formula recursively with $t$ layers of recursion, one needs an estimate of $P(X_{v_{0}}=i^{\prime}|G\backslash\{v_{1},...,v_{t}\}=g\backslash\{v_{1},...,v_{t}\})$ for every path $v_{0},...,v_{t}$ in $G$. The number of these paths is exponential in $t$, and so this approach would be inefficient. However, again due to the tree-like nature of the sparse SBM, it may be reasonable to assume that

which should hold as long as there is no small cycle containing $v$, $v_{j}$, and $v^{\prime}$.

Therefore, using an initial estimate $(q_{v,v^{\prime}})_{i}$ of $P(X_{v^{\prime}}=i|G\backslash\{v\}=g\backslash\{v\})$ for each community $i$ and each adjacent $v$ and $v^{\prime}$, we can iteratively refine our beliefs using the following algorithm which is essentiallyOne should normally also factor in the non-edges, but we ignore these for now as their effect is negligible in BP, although we will factor them back in when discussing linearized BP. belief propagation (BP):

Belief Propagation Algorithm (t,q, p,Q, G):

Set $q^{(0)}=q$, where $q$ provides $(q_{v,v^{\prime}})_{i}\in$ for all $v,v^{\prime}\in[n]$, $i\in[k]$; the initial belief that vertex $v^{\prime}$ sends to vertex $v$ (one can set $q_{v^{\prime},v}=q_{v^{\prime\prime},v}$).

For each $0<t^{\prime}<t$, each $v\in G$, and each community $i$, set

For each $v\in G$ and each community $i$, set

This algorithm is efficient and terminates with a probability distribution for the community of each vertex given the graph, which seems to converge to the true distribution with enough iterations even with a random initialization. Showing this remains an open problem. Instead, we will discuss in Section 5.3.1 how one can linearize BP in order to obtain a version of BP that can be analyzed more easily. This linearization of BP will further lead to a new spectral method on an operator called the nonbacktracking operator (see Section 5.3.1), which connects us back to spectral methods without the issues mentioned previously for the adjacency matrix in the weak recovery regime (i.e., the sensitivity to degree variations).

Chapter 4 Exact recovery for two communities

Exact recovery for linear size communities has been one of the most studied problems for block models in its first decades. A partial list of papers is given by [BCLS87, DF89, Bop87, SN97, CK99, McS01, BC09, CWA12, Vu14, YC14]. In this line of work, the approach is mainly driven by the choice of the algorithms, and in particular for the model with two symmetric communities. The results are as followsSome of the conditions have been borrowed from attended talks and have not been double-checked.:

More recently, [Vu14] obtained a result for a spectral algorithm that works in the regime where the expected degrees are logarithmic, rather than poly-logarithmic as in [McS01, CWA12], extending results also obtained in [XLM14]. Note that exact recovery requires the node degrees to be at least logarithmic, as discussed in Section 2.4. Thus the results of [Vu14] are tight in the scaling, and the first to apply in such generality, but as for the other results in Table 1, these results do not reveal the phase transition. The fundamental limit for exact recovery was derived first for the case of symmetric SBMs with two communities:

At the threshold, one has to distinguish two cases: if $a,b>0$, then exact recovery is solvable (and efficiently so) if $|\sqrt{a}-\sqrt{b}|=\sqrt{2}$, as first shown in [MNS14]. If $a$ or $b$ are equal to 0, exact recovery is solvable (and efficiently so) if $\sqrt{b}>\sqrt{2}$ or $\sqrt{a}>\sqrt{2}$ respectively, and this corresponds to connectivity.

Note that $|\sqrt{a}-\sqrt{b}|>\sqrt{2}$ can be rewritten as $\frac{a+b}{2}>1+\sqrt{ab}$ and recall that $\frac{a+b}{2}>2$ is the connectivity requirement in SSBM. As expected, exact recovery requires connectivity, but connectivity is not sufficient. The extra term $\sqrt{ab}$ is the ‘over-sampling’ factor needed to go from connectivity to exact recovery, and the connectivity threshold can be recovered by considering the case where $b=0$. An information-theoretic interpretation of Theorem 3 is also discussed in Section 7.1.

Before discussing exact recovery in the SBM, we discuss a simpler problem which will turn out to be crucial to understanding exact recovery. Namely, exact recovery with a genie that reveals all the vertices labels except for a few. By ‘a few’ we really mean here one or two. If one works with the strictly balanced model for the community prior, then it is not interesting to reveal all vertices but a single one, as this one is forced to take the value of the community that does not have exactly $n/2$ vertices. In this case one should isolate two vertices. If one works with the Bernoulli model for the community prior, then one can isolate a single vertex and it is already non-trivial to decide for the labelling of that vertex given the others.

To further clean up the problem, assume for now that we have a single vertex (say vertex 0) that needs to be labelled, with $n/2$ vertices revealed in each community, i.e., assume that we have a model with two communities of size exactly $n/2$ and an extra vertex that can be in each community with probability $1/2$.

To minimize the probability of error for this vertex we need to use the MAP estimator that picks $u$ maximizing

Note that the above probability depends only on the number of edges that vertex has with each of the two communities; denoting by $N_{1}$ and $N_{2}$ these edge counts, we have

This gives an hypothesis test with two hypotheses corresponding to the two values that vertex can take, with equiprobable prior and distributions for the observable $N_{1}=N_{1}(G,X_{\sim 0})$ given by

The probability of error of the MAP test is then given byTies can be broken arbitrarily; assume that an error is declared in case of ties to simplify the expressions.

This is the probability that a vertex has more “friends” in the other community than its own. We have the following key estimate.

The next result, which we will prove in the next section, reveals why this hypothesis test is crucial.

In other words, when the probability of error of classifying a single vertex when all others are revealed scales sublinearly, one can classify all vertices correctly whp, and when it scales supperlinearly, one cannot classify all vertices correctly whp.

2 The information-theoretic threshold

In this section, we establish the information-theoretic threshold for exact recovery in the two-community symmetric SBM with the uniform prior. That is, we assume that the two communities have size exactly $n/2$, where $n$ is even, and are uniformly drawn with that constraint.

Recall that the MAP estimator for this model picks a min-bisection (see Section 3.1), i.e., a partition of the vertices in two balanced groups with the least number of crossing edges (breaking ties arbitrarily). We will thus investigate when this estimator succeeds/fails in recovering the planted partition. Recall also that we work in the regime where

where the logarithm is in natural base, $a$, $b$ are two positive constants.

First recall that the term ‘converse’ is commonly used in information theory to refer to the impossibility part of a result, i.e., when exact recovery cannot be solved in this case. Note next that exact recovery cannot be solved in a regime where the graph is disconnected with high probability, because two disconnected components cannot be correctly labelled with a probability tending to one. So this gives us already a simple condition:

Under this condition, the graph is disconnected with high probability [ER60]. ∎

As we will see, this condition is not tight and exact recovery requires more than connectivity:

We will now describe the main obstruction for exact recovery. First assume without loss of generality that the planted community is given by

be the SBM graph generated from this planted community assignment.

We define the set of bad pairs of vertices by

where $x_{0}[u\leftrightarrow v]$ denotes the vector obtained by swapping the values of coordinates $u$ and $v$ in $x_{0}$.

Exact recovery is not solvable if $\mathcal{B}(G)$ is non-empty with non-vanishing probability.

If there exists $(u,v)$ in $\mathcal{B}(G)$, we can swap the coordinates $u$ and $v$ in $x_{0}$ and increase the likelihood of the partition, thus obtaining a different partition than the planted one that is as likely as the planted one, and thus a probability of error of at least $1/2$. ∎

We now examine the condition $P_{G|X}(G|x_{0})\leq P_{G|X}(G|x_{0}[u\leftrightarrow v])$. This is a condition on the number of edges that vertex $u$ and $v$ have in each of the two communities. First note that an edge between vertex $u$ and $v$ stays in the cut if the two vertices are swapped. So the likelihood can only vary based on the number of edges that $u$ has in its community and in the other community ignoring $v$, and similarly for $v$.

For a vertex $u$, define $d_{+}(u)$ and $d_{-}(u)$ as the number of edges that $u$ has in its own and other community respectively. For vertices $u$ and $v$ in different communities, define $d_{-}(u\setminus v)$ as the number of edges that a vertex $u$ has in the other community ignoring vertex $v$.

We can now define the set of bad vertices (rather than bad pairs) in each community.

If $\mathcal{B}_{1}(G)$ is non-empty with probability $1/2+\Omega(1)$, then $\mathcal{B}(G)$ is non-empty with non-vanishing probability.

If $u\in C_{1}$ and $v\in C_{2}$ are such that $d_{+}(u)\leq d_{-}(u)-1$ and $d_{+}(v)\leq d_{-}(v)-1$, then $d_{+}(u)+d_{+}(v)\leq d_{-}(u)+d_{-}(v)-2$, and since $d_{-}(u)\leq d_{-}(u\setminus v)+1$, this implies $d_{+}(u)+d_{+}(v)\leq d_{-}(u\setminus v)+d_{-}(v\setminus u)$. Therefore

Using the union bound and the symmetry in the model, we have

If the events $\{u\notin\mathcal{B}_{1}(G)\}_{u\in C_{1}}$ were pairwise independent, then we would be done. The technical issue is that for two vertices $u$ and $v$, the events are not exactly independent since the vertices can share an edge. This does not however create significant dependencies. Let

and the last bound tends to 1 if the following three conditions hold

The first condition follows from the genie-aided hypothesis testIn this case, one of the two Binomial random variables has $n-1$ trails rather than $n$, with a trial replace by 1, which makes no difference in the result as mentioned in Remark 3. and reveals the bound in the theorem; the second condition amounts to say that $B_{1}$ and $B_{2}$ are asymptotically independent.

We now show the second condition. We have

2.2 Achievability

The next result shows that the previous bound is tight.

We will discuss the boundary case $|\sqrt{a}-\sqrt{b}|>\sqrt{2}$ later on (it is still possible to solve exact recovery in this case as long as both $a$ and $b$ are non-zero). To prove this theorem, one can proceed with different approaches:

Showing k-swaps are dominated by 1-swaps. The converse shows that below the threshold, there exists a bad pair of vertices in each community that can be swapped (and thus placed in the wrong community) while increasing the likelihood (i.e., reducing the cut). To show that the min-bisection gives the planted bisection, we need to show instead that there is no possibility to swap $k$ vertices from each community and reduce the cut for any $k\in\{1,\dots,n/4\}$ (we can use $n/4$ because the communities have size $n/2$). That is, above the threshold,

For $T_{1}\subseteq C_{1},T_{2}\subseteq C_{2}$ such that $|T_{1}|=|T_{2}|=k$, define

where $R:=\sum_{k=2}^{n/4}{n/4\choose k}{n/4\choose k}P_{e}(k)$. Note that $P_{e}(1)$ behaves like the error probability of the genie-aided test squared (we look at two vertices instead of one), and one can show that the product $n^{2}P_{e}(1)$ is vanishing above the threshold. So it remains to show that the reminder $R$ is also vanishing, and in fact, one can show that $R=O(n^{2}P_{e}(1))$, i.e., the first term (1-swaps) dominates the other terms (k-swaps). This approached is used in [ABH16].

Using graph-splitting. The technique of graph-splitting is developed in [ABH16, AS15a] to allow for multi-round methods, where solutions are successively refined. The idea is to split the graph $G$ into two new graphs $G_{1}$ and $G_{2}$ on the same vertex set, by throwing each edge independently from $G$ to $G_{1}$ with probability $\gamma$ and keeping the other edges in $G_{2}$. In a sparse enough regime, such as logarithmic degrees, one can further treat the two graphs as essentially independent SBMs on the same planted community. Taking $\gamma=\log\log(n)/\log(n)$, one obtains for $G_{1}$ an SBM with degrees that scale with $\log\log(n)$, and it is not too hard to show that almost exact recovery can be solved in such a diverging-degree regime. One can then use the almost exact clustering obtained on $G_{1}$ and refine it using the edges of $G_{2}$, using a genie-aided test for each vertex, where the genie is not an exact genie as in Section 4.1, but an almost-exact genie obtained from $G_{1}$. One then shows that the almost-exact nature of the genie does not change the outcome, and the same threshold emerges. This approach is discussed in more details in Section 7.1 when we consider exact recovery in the general SBM.

Using the spectral algorithm. While it is not necessary to use an efficient algorithm to establish the information-theoretic threshold, the spectral algorithm offers a nice algebraic intuition to the problem. This approach is discussed in detail in next section.

3 Achieving the threshold

In this section, we show that the vanilla spectral algorithm discussed in Section 3.2 achieves the exact recovery threshold. The proof is based on [AFWZ17]. Recall that the algorithm is a relaxation of the min-bisection, changing the integral constraint on the community labels to an Euclidean-norm constraint. This suggest that taking the second largest eigenvector of $A$, i.e., the eigenvector corresponding to the second largest eigenvalue of $A$, and rounding it, gives a plausible reconstruction. Techniques from random matrix theory are naturally relevant here, as used in various works such as [Vu07, NN12, OVW, Vu14, YP14b, PWBM16b] and references therein.

In words, $\bar{\phi}_{2}$ is a vector whose signs indicate the assignment of $X$. We will work with the “centered” adjacency matrixStrictly speaking, obtaining the centered adjacency matrix requires that $p+q$ is known. A better approach is to replace $p+q$ by an estimate, or use the second eigenvector of $A^{\prime}$ directly as analyzed in [AFWZ17]. which we denote by $A$ in this section (with an abuse of notation compared to previous sections) where we subtract the top expected eigenvector:

The slight advantage is that $A$ is now rank 1 in expectation:

We now want to show that the top eigenvector $\phi$ of $A$ has all its components aligned with $\bar{\phi}$ in terms of signs (up to a global flip). Define, for $i\in[n]$,

Note that the algorithm runs in polynomial time in $n$, at most $n^{3}$ counting loosely and less using the sparsity of $A$. Also note that we do not have to worry about the case where the resulting community is not balanced, as this enters the vanishing error probability. Another way to write the theorem is as follows:

In the regime $p=a\,\frac{\log n}{n}$, $q=b\,\frac{\log n}{n}$, $a\neq b$, $a,b>0$, $|\sqrt{a}-\sqrt{b}|\neq\sqrt{2}$,

i.e., the spectral and MAP estimators are equivalent whenever MAP succeeds at recovering the true $X$ (we use $x\equiv y$ in the above for $x\in\{y,y^{c}\}$ where $y^{c}$ flips the components of $y$, due to the usual symmetry).

This an interesting phenomenon that seems to take place for more than one problem in combinatorial statistics, see for example discussion in [AFWZ17].

We now proceed to prove Theorem 8. We will break the proof in several parts. A first important result due to [FO05] gives a bound on the norm of $A-\bar{A}$ (see [AFWZ17] for a proof):

[FO05] For any $a,b>0$, there exist $c_{1},c_{2}>0$ such that

This implies a first reassuring fact, i.e., the first eigenvalue $\lambda$ of $A$ is in fact asymptotic to $\bar{\lambda}$ in our regime. This follows from the Courant-Fisher Theorem:

This implies that $\lambda\sim\bar{\lambda}$ with high probability, since $\bar{\lambda}\asymp\log(n)$. However, this does not imply anything for the eigenvectors yet. A classical result to convert bounds on the norm $A-\bar{A}$ to eigenvector alignments is the Davis-Kahan Theorem. Below we present a user-friendly version based on the Lemma 3 in [AFWZ17].

Suppose that $\bar{H}=\sum_{j=1}^{n}\bar{\mu}_{j}\bar{u}_{j}\bar{u}_{j}^{t}$ and $H=\bar{H}+E$, where $\bar{\mu}_{1}\geq\cdots\geq\bar{\mu}_{n}$, $\|\bar{u}_{j}\|_{2}=1$ and $E$ is symmetric. Let $u_{j}$ be an eigenvector of $H$ corresponding to its $j$-th largest eigenvalue, and $\Delta=\min\{\bar{\mu}_{j-1}-\bar{\mu}_{j},\bar{\mu}_{j}-\bar{\mu}_{j+1}\}$, where we define $\bar{\mu}_{0}=+\infty$ and $\bar{\mu}_{n+1}=-\infty$. We have

In addition, if $\|E\|_{2}\leq\Delta$, then

where both $\lesssim$ only hide absolute constants.

While this gives a strong alignment, it does not give any result for exact recovery. One can use a graph-splitting step to leverage this result into an exact recovery result by using a cleaning phase on the eigenvector (see item 2 in Section 4.2.2). Interestingly, one can also proceed directly using a sharper spectral analysis, and show that the sign of the eigenvector $\phi$ directly recovers the communities. This was done in [AFWZ17] and is covered below.

A first attempt would be to show that $\phi$ and $\bar{\phi}$ are close enough in each component, i.e., that with high probability,

or $\|\phi-(-\bar{\phi})\|_{\infty}\stackrel{{\scriptstyle?}}{{<}}1/\sqrt{n}$ since we must allow for a global flip due to symmetry. This would imply that rounding the components of $\phi$ to their signs would produce with high probability the same signs as $\bar{\phi}$ (or $-\bar{\phi}$), which solves exact recovery.

Unfortunately the above inequality does not hold all the way down to the exact recovery threshold, which makes the problem more difficult. However, note that it is not necessary to have (4.73) in order to obtain the correct sign by rounding $\phi$: one can have a large gap for $|\phi_{i}-\bar{\phi}_{i}|$ which still produces the good sign as long as this gap in “on the right side,” i.e., $\phi_{i}$ can be much larger than $\bar{\phi}_{i}$ if $\bar{\phi}_{i}$ is positive and $\phi_{i}$ can be much smaller than $\bar{\phi}_{i}$ if $\bar{\phi}_{i}$ is negative (or the reverse statement for $-\bar{\phi}$). This is illustrated in Figure 4.1 and is shown below.

The main idea is to show that the components of $\phi$ are well-approximated by the components of $A\bar{\phi}/\bar{\lambda}$ (rather than $\bar{\phi}$), i.e.,

Let $a>b>0$. There exist constants $C$ and $c$ such that for sufficiently large $n$,

Note that $A\bar{\phi}$ is familiar to us: it contains exactly the random variable entering the error event for the genie-aided hypothesis test in (4.6), i.e.,

and each $A^{\prime}_{ij}$ is an independent Bernoulli variable whose success probability depends on whether $X_{i}=X_{j}$. We know from Lemma 4 has probability $n^{-1-\Omega(1)}$ to be negative (i.e., to move to “the other side”) above the exact recovery threshold. Since $A\bar{\phi}$ is normalized by $\bar{\lambda}$, we will use the stronger version of Lemma 4 mentioned in Remark 3. We now give the proof for Theorem 7, and then proceed to proving Theorem 10.

Note that Theorem 10 says that $\mathcal{E}_{2}$ takes place with high probability. Therefore if $\mathcal{E}_{1}$ takes place with high probability as well, the event

must take place with high probability, because entrywise (up to a global flip) $\phi$ is at distance $O(\frac{1}{\sqrt{n}\log\log n})$ from $A\bar{\phi}/\bar{\lambda}$, and $A\bar{\phi}/\bar{\lambda}$ is at distance $\Omega(\frac{1}{\sqrt{n}})$ from the origin, so the noise that takes $\bar{\phi}$ to $\phi$ cannot make $\phi$ across the origin and change sign since $|\bar{\phi_{i}}|=1/\sqrt{n}$ (though it could take $\phi$ far on the other side).

We now show that $\mathcal{E}_{1}$ takes place with high probability. We have

When $\sqrt{a}-\sqrt{b}>\sqrt{2}$, we can choose some $\varepsilon=\varepsilon(a,b)>0$ such that $(\sqrt{a}-\sqrt{b})^{2}/2-\varepsilon\log(a/b)/2>1$. Thus from (a strengthening of) the genie-aided error bound,

We now proceed with the proof of Theorem 10.

To simplify the notation, assume that $\phi$ is chosen such that $\phi^{t}\bar{\phi}\geq 0$, so that we can remove the sign variable $s$. We want to obtain a bound on

Recall that Weyl’s theorem gives $|\lambda-\bar{\lambda}|\leq\|A-\bar{A}\|_{2}$, and thus under the event $\mathcal{E}$, which takes place with high probability by Lemma 9, we must have $|\lambda-\bar{\lambda}|=O(\sqrt{\log(n)})$. Given that $\bar{\lambda}=\Theta(\log(n))$, we must have under $\mathcal{E}$

and a fortiori $\frac{|\bar{\lambda}-{\lambda}|}{\bar{\lambda}}=O(1/\sqrt{\log(n)})$. Therefore, under $\mathcal{E}$, we have that the first term in (4.89) is bounded as

Before worrying about estimating $\|\phi\|_{\infty}$, we move to the second term in (4.89). One difficulty in estimating $\|A(\phi-\bar{\phi})\|_{\infty}$ is that $A$ and $(\phi-\bar{\phi})$ are dependent since $\phi$ is an eigenvector of $A$. Thus, to bound the $m$-th component of $A(\phi-\bar{\phi})$, namely $A_{m}(\phi-\bar{\phi})$, where $A_{m}$ is the $m$-row of $A$, we cannot directly use a concentration result that applies to expressions of the kind $A_{m}w$ where $w$ is an independent test vector. To decouple the dependencies, we use a leave-one-out technique, as used for example in [BBEKY13], [JM], and [ZB17].

where $\delta_{A}$ is the indicator function on the event $A$. Therefore, $A^{(m)}$ is obtained from $A$ by zeroing out the $m$-th row and column. Let $\phi^{(m)}$ be the leading eigenvector of $A^{(m)}$. Again, $\phi^{(m)}$ is chosen such that $(\bar{\phi})^{t}\phi^{(m)}\geq 0$. Denoting the $m$th row vector as $A_{m}$, we can write

where we used the Cauchy-Schwarz Inequality in the first inequality, and $\|A\|_{2\to\infty}:=\max_{m\in[n]}\|A_{m}\|_{2}$ in the second inequality. The point of introducing $A^{(m)}$ is that for the second term in (4.96), we have that $A_{m}$ and $(\phi^{(m)}-\bar{\phi})$ are now independent. Thus this term can be tackled with concentration results. We now handle both terms in (4.96). Recall the definition of the event $\mathcal{E}$ in (4.90).

Claim 1: Under $\mathcal{E}$, $T_{1}=\|A\|_{2\to\infty}\|\phi-\phi^{(m)}\|_{2}=O(\sqrt{\log(n)}\|\phi\|_{\infty})$.

To prove this claim, assume that $\mathcal{E}$ takes place. To bound $\|u-\phi^{(m)}\|_{2}$, we will view $A^{(m)}$ as a perturbation of $A$ and apply the Davis-Kahan Theorem (Theorem 9).

By definition we have $(\bar{\phi})^{T}\phi\geq 0$ and $(\bar{\phi})^{T}\phi^{(m)}\geq 0$. Using Theorem 9, we have

When $n$ is large enough, we have that $\|\phi^{(m)}-\phi\|_{2}\leq 1$, which implies (4.97) since $\{\pm 1\}\ni s\mapsto\|s\phi^{(m)}-\phi\|_{2}=2-s\langle\phi^{(m)},\phi\rangle$ has its minima below 1 for $s=1$.

By Weyl’s inequality, $\max_{i}|\lambda_{i}(A)-\lambda_{i}(\bar{A})|\leq\|A-\bar{A}\|_{2}$. Recall that we are under $\mathcal{E}$, thus

Moreover from (4.100) we have that for $n$ large enough,

Therefore (4.105) satisfies the conditions for Theorem 9. Combined with (4.97), this yields

Note that $((A-A^{(m)})\phi)_{m}=A_{m}\phi=\lambda\phi_{m}$ and $((A-A^{(m)})\phi)_{i}=A_{im}\phi_{m}$ for $i\neq m$. By (4.91) and (4.99),

Using this with (4.107), we have that there exists $C_{1}>0$ such that

Finally, from (4.99) and (4.110), there exists $C_{2}>0$ such that

Claim 2: Under $\mathcal{E}$, $T_{2}=|A_{m}(\phi^{(m)}-\bar{\phi})|=O(\log(n)\|\phi\|_{\infty}/\log\log(n))$.

Had we applied Bernstein’s inequality directly, we would get a loose upper bound that contains the term $\log n\cdot\|\phi^{(m)}-\bar{\phi}\|_{\infty}$ without the denominator, which turns out to be critical for the analysis. In fact, as we show below, the denominator will give us an additional $\log\log n$ factor.

there exists a choice of $C_{3}>0$ in the definition of $\mathcal{E}^{(m)}_{0}$ such that

for some constant $C_{4}\geq 1$. Define $\gamma=C_{4}/\sqrt{\log n}$, which is smaller than 1 for large enough $n$, and define function $h(z)=[1\vee\log(1/z)]^{-1}$ where $z\in(0,1]$. It is easily checked that $h(z)$ is non-decreasing and $h(z)/z$ is non-increasing, so $h(z)\leq h(\gamma)\vee h(\gamma)z/\gamma$. Setting $z=\frac{\|\phi^{(m)}-\bar{\phi}\|_{2}}{\sqrt{n}\|\phi^{(m)}-\bar{\phi}\|_{\infty}}$, we can use this inequality to simplify the bound in (4.112) and obtain

Note that under $\mathcal{E}$, (4.110) leads to

where we use $\|\phi\|_{\infty}\geq 1/\sqrt{n}$. Hence, recalling that $\gamma=C_{4}/\sqrt{\log n}$, we have that under $\mathcal{E}\cap\mathcal{E}_{0}$ there exists $C_{5}>0$ such that

Let us use now plug the bounds from Claim 1 and 2 in (4.96), which gives under $\mathcal{E}\cap\mathcal{E}_{0}$,

Putting this back in (4.89) together with (4.92), we obtain under $\mathcal{E}\cap\mathcal{E}_{1}$,

We are now left to show that $\|\phi\|_{\infty}=O(1/\sqrt{n})$, which implies the theorem’s statement since $\mathcal{E}\cap\mathcal{E}_{0}$ takes place with probability $1-\Omega(n^{-2})$.

Claim 3: $\|\phi\|_{\infty}=O(1/\sqrt{n})$.

To prove this claim, note that from (4.119) and $\|\phi\|_{\infty}\leq\|\phi-A\bar{\phi}/\bar{\lambda}\|_{\infty}+\|A\bar{\phi}/\bar{\lambda}\|_{\infty}$, we have $\|\phi\|_{\infty}\lesssim\|A\bar{\phi}\|_{\infty}/\bar{\lambda}$. Hence it remains to show that $\|A\bar{\phi}\|_{\infty}\lesssim\frac{\log n}{\sqrt{n}}$. Observe that $|A_{m}\bar{\phi}|\leq\|\bar{\phi}\|_{\infty}\sum_{i=1}^{n}|A_{mi}|=\sum_{i=1}^{n}|A_{mi}|/\sqrt{n}$ and

where the last inequality holds for $n$ large enough. Moreover from (4.99),

Therefore, $\left\|A\bar{\phi}\right\|_{\infty}\lesssim\frac{\log n}{\sqrt{n}}$, which proves Claim 3 and the theorem. ∎

3.2 SDP algorithm

Recall that an SDP was derived in Section 3.2, lifting the variables to change the quadratic optimization into a linear optimization, and removing the rank-one constraint to obtain

or the version using the matrix $B$ such that $B_{ij}=1$ if there is an edge between vertices $i$ and $j$, and $B_{ij}=-1$ otherwise,

Since the dual minimization gives an upper-bound on the primal maximization, a solution is optimal if it makes the dual minimum match the primal maximum. The Ansatz here consists in taking $Y=2(D_{in}-D_{out})+I_{n}$ as a candidate for the diagonal matrix $Y$, which gives the primal maxima. It we thus have $Y\succeq B(g)$, this is a feasible solution for the dual, and we obtain a dual certificate. The following is shown in [ABH16] based on this reasoning.

Define the SBM Laplacian for $G$ drawn under the symmetric SBM with two communities by

where $D(G_{in})$ ($D(G_{out})$) are the degree matrices of the subgraphs of $G$ containing only the edges inside (respectively across) the clusters, and $A$ is the adjacency matrix of $G$.

The second requirement above is used for the uniqueness of the solution. This condition is verified all the way down to the exact recovery threshold. In [ABH16], it is shown that this condition holds in a regime that does not exactly match the threshold, off roughly by a factor of 2 for large degrees. This gap is closed in [WXH15, Ban15], which show that SDPs achieve the exact recovery threshold in the symmetric case. Results for unbalanced communities were also obtained in [PW], although it is still open to achieve the general CH threshold with SDPs. Many other works have studied SDPs for the stochastic block model, we refer to [AL14, ABH16, Ban15, ABKK15, WXH15, MS16, PW] for further references. In particular, [MS16] shows that SDPs can approach the threshold for weak recovery in the two-community SSBM arbitrarily close when the expected degrees diverge. Recently, [BRS16] also studied an Ising model with block structure, obtaining results for exact recovery and SDPs.

Chapter 5 Weak recovery for two communities

The focus on weak recovery, also called detection, was initiatedThe earlier work [RL08] also considers detection in the SBM. with [CO10, DKMZ11]. Note that weak recovery is typically investigated in SBMs where vertices have constant expected degree, as otherwise the problem can trivially be resolved by exploiting the degree variations.

The following conjecture was stated in [DKMZ11] based on deep but non-rigorous statistical physics arguments, and is responsible in part for the resurgent interest in the SBM:

It was proved in [Mas14, MNS] that the KS threshold can be achieved efficiently for $k=2$, and [MNS15] shows that it is impossible to detect below the KS threshold for $k=2$. Further, [DAM15] extends the results for $k=2$ to the case where $a$ and $b$ diverge while maintaining the SNR finite. So weak recovery is closed for $k=2$ in SSBM.

For several communities, it was also shown in [BLM15] that for SBMs with multiple communities that are balanced and that satisfy a certain asymmetry condition (i.e., the requirement that $\mu_{k}$ is a simple eigenvalue in Theorem 5 of [BLM15]), the KS threshold can be achieved efficiently. The achievability parts of previous conjecture for $k\geq 3$ are resolved in [AS15c, AS17]. We discuss these in Section 7.2.

Note that the terminology ‘KS threshold’ comes from the reconstruction problem on trees [KS66, EKPS00, MP03, MM06], referring to the first paper by Kesten-Stigum (KS). A transmitter broadcasts a uniform bit to some relays, which themselves forward the received bits to other relays, etc. The goal is to reconstruct the root bit from the leaf bits as the depth of the tree diverges. In particular, for two communities, [MNS15] makes a reduction between failing in the reconstruction problem in the tree setting and failing in weak recovery in the SBM. This is discussed in more details in next section. The fact that the reconstruction problem on tree also gives the positive behavior for efficient algorithms requires a more involved argument, as discussed in Section 5.3.

Achieving the KS threshold raises an interesting challenge for community detection algorithms, as standard clustering methods fail to achieve the threshold, as discussed in Section 5.3.1. This includes spectral methods based on the adjacency matrix or standard Laplacians, as well as SDPs. For standard spectral methods, a first issue is that the fluctuations in the node degrees produce high-degree nodes that disrupt the eigenvectors from concentrating on the clusters. A classical trick is to suppress such high-degree nodes, by either trimming or shifting the matrix entries [JY13, LLV15, CO10, Vu14, GV16, CRV15], throwing away some information, but this does not suffice to achieve the KS threshold [KK15]. SDPs are a natural alternative, but they also appear to stumble before the KS threshold [GV16, MS16, MPW16], focusing on the most likely rather than typical clusterings. As shown in [Mas14, MNS, BLM15, AS15c], approximate BP algorithms or spectral algorithms on more robust graph operators instead allow us to achieve the KS threshold.

As for exact recovery, we start with a simpler problem that will play a key role in understanding weak recovery. The idea is similar to that of the exact recovery warm up, except that we do not reveal only the direct neigbors of a vertex, but the neighbors at a small depth. In particular, at depth $(1/2-\varepsilon)\log(n)/\log((a+b)/2)$, the SBM neigborhood of a vertex can be coupled with a Galton-Watson tree, and so we will consider trees for the warm up. In contrast to exact recovery, we will not be interested in reconstructing the isolated vertex with probability tending to 1, but with probability greater than $1/2$. This is known in the literature as the reconstruction problem for broadcasting on trees. We refer to [MP03] for a survey on this topic.

The problem consists of broadcasting a bit from the root of a tree down to its leaves, and trying to guess back this bit from the leaf bits at large depth. First consider the case of a deterministic tree with fixed degree $c+1$, i.e., each vertex has exactly $c$ descendants (note that the root has degree $c$). Assume that on each branch of the tree the incoming bit is flipped with probability $\varepsilon\in$, and that each branch flips independently. Let $X^{(t)}$ be the bits received at depth $t$ in this tree, with $X^{(0)}$ being the root bit, assumed to be drawn uniformly at random in $\{0,1\}$.

Note that the above limits exist due to monotonicity arguments. The first result on this model is due to Kesten-Stigum:

In the tree model with constant degree $c$ and flip probability $\varepsilon$,

[KS66] weak recovery is solvable if $c(1-2\varepsilon)^{2}>1$,

[BRZ95, EKPS00] weak recovery is not solvableThe proof from [EKPS00] appeared first in 1996. if $c(1-2\varepsilon)^{2}\leq 1$.

In fact, one can show a seemingly stronger result where weak recovery fails in the sense that, when $c(1-2\varepsilon)^{2}\leq 1$,

Thus weak recovery in the tree model is solvable if and only if $c(1-2\varepsilon)^{2}>1$, which gives rise to the so-called Kesten-Stigum (KS) threshold in this tree context. Note that [MP03] further shows that the KS threshold is sharp for “census reconstruction,” i.e., deciding about the root-bit by taking majority on the leaf-bits, which is shown to still hold in models such as the multicolor Potts model where the KS threshold is no longer sharp for reconstruction.

To see this result, let us compute the moments of the number of 0-bits minus 1-bits at generation $t$. First, consider $\pm 1$ variables rather than bits, i.e., redefine $X_{i}^{(t)}\leftarrow(-1)^{X_{i}^{(t)}}$, and consider the difference variable:

Note that, if there are $x$ bits of value $1$ and $y$ bits of value $-1$ at generation $t$, then $\Delta^{(t+1)}$ would be the sum of $xc$ Radamacher$(1-\varepsilon)$ and $yc$ Radamacher$(\varepsilon)$ (all independent), and since the expectation of Radamacher$(1-\varepsilon)$ is $1-2\varepsilon$, we have

We now look at the second moment. A direct computation gives

Denote now by $\mu_{+}$ the distribution of $\Delta^{(t)}$ given that $X^{(0)}=1$, and by $\mu_{-}$ the distribution of $\Delta^{(t)}$ given that $X^{(0)}=-1$. We have by Cauchy-Schwarz,

Therefore, we have from previous expansions that the total variation distance between $\mu_{+}$ and $\mu_{-}$ is $\Omega(1)$, which implies that it is possible to distinguish between the hypotheses $X^{(0)}=1$ and $X^{(0)}=-1$ with a probability of error that is $1/2-\Omega(1)$.

Note that this subadditivity holds in greater generality for the first layer, i.e., if we have a Markov chain $Y_{1}-X-Y_{2}$, such as happens when a root variable $X$ is broadcast on two independent channels producing $Y_{1}$ and $Y_{2}$, then

However, going to depth 2 of the tree, there is no simple inequality as the above that shows the subadditivity, and in fact, the subadditivity is not true in general for binary non-symmetric noise or for non-binary labels. For binary labels and symmetric channels, it is shown in [EKPS00] that the distribution of labels on the tree can be obtained by degradation from a so-called “stringy tree”, where branches are “detached”, which implies the inequality.

Further, the channel between $X^{(0)}$ and a one leaf-bit such as $X_{1}^{(t)}$ corresponds to $t$ Bernoulli$(\varepsilon)$ random variables added, and the mutual information scales as $(1-2\varepsilon)^{2t}$,

and the information of the root-bit gets lost in the leaves.

The subadditivity property in (5.15) can also be established for the Chi-squared mutual information, i.e., using $I_{2}(X;Y)=D_{\chi_{2}}(p_{X,Y}\|p_{X}p_{Y})$ where $D_{\chi_{2}}$ is the Chi-squared $f$-divergence with $f(z)=(z-1)^{2}$. We describe here how this can be obtained with an induction on the tree depth, assuming the following two building blocks:

if $\,\,\,Y_{1}-X^{(0)}-Y_{2}$ (i.e., $Y_{1},Y_{2}$ are independent conditionally on $X^{(0)}$ and $X^{(0)}$ is Bernoulli$(1/2)$ as before) and

if $Y_{1}$ is a direct descendant of $X^{(0)}$ and $Y_{t}$ are descendants of $Y_{1}$ at depth $t$ (in the broadcasting on trees model). One then obtains the subadditivity by applying inequality (5.23) to the sub-trees pending at the root, and equality (5.24) to factor out the first edge on each sub-tree, reducing the depth by one and allowing for the induction hypothesis. Interestingly, while the inequality also holds for the mutual information, the equality does not hold for the mutual information, and can in fact go in the wrong direction. On the other hand, one has

and since the Chi-squared mutual information upper-bounds the classical mutual information for binary inputs, the same threshold of $c(1-2\varepsilon)^{2}=1$ is obtained with this argument.

We will soon turn to the connection between the reconstruction on trees problem and weak recovery in the SBM. It is easy to guess that the tree will not be a fixed degree tree for us, but the local neighborhood of a vertex in the SBM, which behaves like a Galton-Watson tree of Poisson offspring. We first state the above results for Galton-Watson trees.

Define as before $X^{(t)}$ as the variables at generation $t$ obtained from broadcasting the root-bit on a Galton-Watson tree $T^{(t)}$.

In [EKPS00], it is shown that the threshold $c(1-2\varepsilon)^{2}>0$ is necessary and sufficient for weak recovery for a large class of offspring distributions, where $c$ is the expectation of $\mu$. The case of $\mu$ being the Poisson$(c)$ distribution is of particular interest to us:

[EKPS00] In the broadcasting model with a Galton-Watson tree of Poisson$(c)$ offspring and flip probability $\varepsilon$, weak recovery is solvable if and only if

Another important extension is the ‘robust reconstruction’ problem [JM04], where the leaves are not revealed exactly but with the addition of independent noise. It was shown in [JM04] that for very noisy leaves, the KS threshold is also tight.

2 The information-theoretic threshold

We focus in particular on the information-theoretic converse. Interestingly, for the achievability part, there is not currently a simpler proof available in the literature than the proof that directly gives an efficient algorithm. Below we discuss some attempts, and in Section 5.3 we will the efficient achievability.

The following result is shown in [MNS15]:

Here we show the following equivalent result that also implies the impossibility of weak recovery:

Note that the role of vertex 1 and 2 is arbitrary above, it could be any fixed pair of vertices (not chosen based on the graph).

The connection between the warm-up problem and the SBM comes from the fact that if one picks a vertex $v$ in the SBM graph, its neighborhood at small enough depth behaves likes a Galton-Watson tree of offspring Poisson$(c)$, $c=((a+b)/2)$, and the labelling on the vertices behaves like the broadcasting process discussed above with a flip probability of $\varepsilon=b/(a+b)$. Note that the latter parameter is precisely the probability that two vertices have different labels given that there is an edge between them. More formally, if the depth is $t\leq(1/2-\delta)\log(n)/\log(a+b)/2)$ for some $\delta>0$, then the true distribution and the above have a vanishing total variation when $n$ diverges. This depth requirement can be understood from the fact that the expected number of leaves in that case is in expectation $n^{1/2-\delta}$, and by the birthday paradox, no collision will likely occur between two vertices’ neighborhoods if $\delta>0$ (hence no loops take place and the neighborhood is a tree with high probability).

The reduction extends to more than two communities (i.e., non-binary labels broadcasted on trees) and to asymmetrical communities, but the tightness of the KS bound is no longer present in these cases. For two asymmetrical communities, the result still extends if the communities are roughly symmetrical, using [BCMR06] and [MNS13, Mos17]. For more than three symmetric communities, new gap phenomena take place [AS17]; see Section 8.

We now proceed to proving Theorem 17. The first step is to formalize what is meant by the fact that the neighborhoods of the SBM look like a Galton-Watson tree. Let $G$

The second technical lemma that we need regards the negligible effect of non-edges outside from our local neighborhood of a vertex. The difficulty here is that these non-edges are negligible if the vertices labels are more or less balanced; for example, the effect of non-edges would not be negligible if the vertices had all the same labels.

The statement means that the probability that $(X,G)$ satisfies (5.29) tends to one as $n$ tends to infinity. Note that $R$ could actually be $c\log(n)/\log((a+b)/2)\rfloor$ for any $c<1/2$; we keep the same $R$ as in the previous lemma to reduce the number of parameters.