Information-theoretic thresholds for community detection in sparse networks

Introduction

The Stochastic Block Model (SBM) is a random graph ensemble with planted community structure, where the probability of a connection between each pair of vertices is a function only of the groups or communities to which they belong. It was originally invented in sociology [HLL83]; it was reinvented in physics and mathematics under the name “inhomogeneous random graph” [Söd02, BJR07], and in computer science as the planted partition problem (e.g. [McS01]).

Given the current interest in network science, the block model and its variants have become popular parametric models for the detection of community structure. An interesting set of questions arise when we ask to what extent the communities, i.e., the labels describing the vertices’ group memberships, can be recovered from the graph it generates. In the case where the average degree grows as $\log n$, if the structure is sufficiently strong then the underlying communities can be recovered [BC09], and the threshold at which this becomes possible has recently been determined [ABH16, AS15b, ABKK15]. Above this threshold, efficient algorithms exist that recover the communities exactly, labeling every vertex correctly with high probability; below this threshold, exact recovery is information-theoretically impossible.

In the sparse case where the average degree is $O(1)$, finding the communities is more difficult, since we effectively have only a constant amount of information about each vertex. In this regime, our goal is to label the vertices better than chance, i.e., to find a partition with nonzero correlation or mutual information with the ground truth. This is sometimes called the detection problem to distinguish it from exact recovery. A set of phase transitions for this problem was conjectured in the statistical physics literature based on tools from spin glass theory. Some of these conjectures have been made rigorous, while others remain as tantalizing open problems.

It is convenient to parametrize the strength of the community structure as

As we will see below, this is the second eigenvalue of a transition matrix describing how labels are “transmitted” between neighboring vertices. It lies in the range

The conjecture of [DKMZ11b, DKMZ11a] is that efficient algorithms exist if and only if we are above the threshold

This is known in information theory as the Kesten-Stigum threshold [KS66b, KS66a], and in physics as the Almeida-Thouless line [dAT78].

Above the Kesten-Stigum threshold, [DKMZ11b, DKMZ11a] claimed that community detection is computationally easy, and moreover that belief propagation—also known in statistical physics as the cavity method—is asymptotically optimal in that it maximizes the fraction of vertices labeled correctly (up to a permutation of the groups). For $k=2$, this was proved in [MNS14], and very recently, a type of belief propagation was shown to perform better than chance for all $k$ [AS15a]. In addition, a spectral clustering algorithm based on the non-backtracking operator was conjectured to succeed all the way down to the Kesten-Stigum threshold [KMM+13], and this was proved in [BLM15].

What happens below the Kesten-Stigum threshold is more complicated. The authors of [DKMZ11b, DKMZ11a] conjectured that for sufficiently small $k$, community detection is information-theoretically impossible when $d<1/\lambda^{2}$. This was proved in the case $k=2$ by [MNS12], who established two separate results. First, they showed that the ensemble of graphs produced by the stochastic block model becomes contiguous with that produced by Erdős-Rényi graphs of the same average degree, making it impossible even to tell whether or not communities exist with high probability. Secondly, by relating community detection to the robust reconstruction problem on trees [JM04], they showed that for most pairs of vertices the probability, given the graph, that they are in the same group asymptotically approaches $1/2$. Thus it is impossible, even if we could magically compute the true posterior probability distribution, to label the vertices better than chance.

More generally, planted ensembles where some combinatorial structure is built into the graph, and un-planted ensembles such as Erdős-Rényi graphs where these structures occur by chance, become distinguishable at a phase transition called condensation [KMRT+07]. Below this point, the two ensembles are contiguous; above it, the Gibbs distribution in the planted model is dominated by a cluster of states surrounding the planted state. For instance, in random constraint satisfaction problems, the uniform distribution on solutions becomes dominated by those near the planted one; in our setting, the posterior distribution of partitions becomes dominated by those close to the ground truth (although, in the sparse case, with a Hamming distance that is still linear in $n$). Thus the condensation threshold is also the threshold for information-theoretic community detection. Below it, even optimal Bayesian inference will do no better than chance, while above it, typical partitions chosen from the posterior will be fairly accurate (though finding these typical partitions might take exponential time).

We note that some previous results show that community detection is possible below the Kesten-Stigum threshold when the sizes of the groups are unequal [NN14, ZMN16]. In addition, even a vanishing amount of initial information can make community detection possible if the number of groups grows with the size of the network [KMS14].

2. Our contribution

We give rigorous upper and lower bounds on the information-theoretic threshold for community detection, or equivalently the condensation threshold, bounding the critical average degree as a function of $k$ and $\lambda$. First, we use a first-moment argument to show that if

then, with high probability, the only partitions that are as good as the planted one—that is, which have the expected number of edges within and between groups—have a nonzero correlation with the planted one. As a result, there is a simple exponential time algorithm for labeling the vertices better than chance: simply test all partitions, and output the first good one.

We then show that community detection is information-theoretically impossible if

Here we rely heavily on a recent preprint [NN14], who gave a beautiful generalization of the argument of [MNS12]. Using the small subgraph conditioning method, they showed that the block model and the Erdős-Rényi graph are contiguous whenever the second moment of the ratio between their probabilities—roughly speaking, the number of good partitions in an Erdős-Rényi graph—is appropriately bounded. They also show that this second moment bound implies non-detectability, in that the posterior distribution on any finite collection of vertices is asymptotically uniform. This reduces the proof of contiguity and non-detectability to a second moment argument, which in turn consists of maximizing a certain function of doubly stochastic matrices.

Happily, this latter problem was largely solved in [AN05], who used the second moment method to give nearly-tight lower bounds on the $k$-colorability threshold. Indeed, our bound (5) corresponds to their lower bound on $k$-colorability for $G(n,d^{\prime}/n)$ where $d^{\prime}=d\lambda^{2}(k-1)^{2}$. Intuitively, $d^{\prime}$ is the degree of a random graph in which the correlations between vertices in the $k$-colorability problem are as strong as those in the block model with average degree $d$ and eigenvalue $\lambda$.

In the limit $\mu=-1$, corresponding to graph coloring, this ratio is $1$, inheriting the tightness of previous upper and lower bounds on $k$-colorability. For other values of $\mu$, our bounds match up to a multiplicative constant. In particular, when $k$ is constant and $|\lambda|$ is small, they are about a factor of $2$ apart:

When $\lambda\geq 0$ is constant and $k$ is large, we have

so that in the limit of large $k$ detectability is possible below the Kesten-Stigum threshold whenever $\lambda<1/2$.

Our model, notation, and results

We have $n$ vertices $V=[n]$. In the usual version of the block model, we start by choosing a partition $\sigma:[n]\to[k]$ uniformly from the $k^{n}$ possibilities. We independently include each pair of vertices $(u,v)$ in the edge set $E$ with probability $c_{\sigma(u),\sigma(v)}/n$, where $c$ is a $k\times k$ matrix. As in much other work on community detection, we focus on the special case

We will often find it convenient to assume that the partition $\sigma$ is balanced, i.e., that $n$ is divisible by $k$ and that there are $|\sigma^{-1}(r)|=n/k$ vertices in each group $r$. Of course, this is true within an $o(n)$ error term with high probability.

Recalling that the expected average degree is

we will find it useful to define a doubly stochastic matrix,

We can think of $\gamma$ as a transition matrix in a Markov random field. All else equal, if $(u,v)\in E$ and $\sigma(u)=r$, then $\gamma_{rs}$ is the probability that $\sigma(v)=s$. Notice that

is $\gamma$’s second eigenvalue. We can think of $\lambda$ as the probability that information is transmitted from $u$ to $v$: with probability $\lambda$ we copy $u$’s group label to $v$, and with probability $1-\lambda$ we choose $v$’s group uniformly. The parameter $\lambda$ interpolates between the case $\lambda=1$ where all edges are within-group, to an Erdős-Rényi graph where $\lambda=0$ and edges are placed uniformly at random, to $\lambda<0$ where edges are more likely between groups than within them. This gives a useful reparametrization of the model in terms of $c$ and $\lambda$, where

The community detection problem is to recover the planted partition $\sigma$ from the graph $G=(V,E)$. We define the degree to which an algorithm succeeds as follows. Given another partition $\tau$, we define the overlap matrix

Since $\sigma$ is balanced, this is the fraction of group $r$ (according to $\sigma$) that is in group $s$ (according to $\tau)$. If $\tau$ is balanced as well, then $\alpha$ is doubly stochastic. The overlap $\beta$ is then the fraction of vertices labeled correctly, maximized over all permutations $\pi$ of the groups,

For $k\geq 5$, community detection is information-theoretically possible below the Kesten-Stigum threshold $d=1/\lambda^{2}$ for $\lambda$ sufficiently negative. For $k\geq 11$, there exist positive values of $\lambda$ for which this holds as well.

The Upper Bound

Let $G$ be a graph generated by $G(n,d/n)$. We condition on the high-probability event that it has $m$ edges with $|m-\overline{m}|<n^{2/3}$ with

in which case $G$ is chosen from $G(n,m)$. Since $G$ is sparse, we can think of its $m$ edges as chosen uniformly with replacement from the $n^{2}$ possible ordered pairs. With probability $\Theta(1)$ the resulting graph is simple, with no self-loops or multiple edges, and hence uniform in $G(n,m)$. Thus any event that holds with high probability in the resulting model holds with high probability in $G(n,m)$ as well. Call this model $G^{\prime}(n,m)$.

For a given balanced partition $\sigma$, the probability in $G^{\prime}(n,m)$ that a given edge has its endpoints in the same group is $1/k$. Thus, up to subexponential terms resulting from summing over the $n^{2/3}$ possible values of the error terms, the probability that a given $\sigma$ is good is

Now, by the union bound, since there are at most $k^{n}$ balanced partitions, the probability that any good partitions exist is exponentially small whenever the function in (14) is less than $-\log k$. This tells us that the block model is distinguishable from an Erdős-Rényi graph whenever

2. All good partitions are accurate

where $h=-\beta\log\beta-(1-\beta)\log(1-\beta)$ is the entropy function. Therefore, an exponential-time algorithm exists that w.h.p. achieves overlap at least $\beta$.

In analogy with the model $G^{\prime}(n,m)$ defined above, we consider another version of the block model where the $m$ edges are chosen independently as follows. For each edge, we first choose an ordered pair of groups $r,s$ with probability proportional to $c_{rs}$, i.e., with probability $\gamma_{rs}/k$ where $\gamma=c/(kd)$ is the doubly stochastic matrix defined in (7). We then choose the endpoints $u$ and $v$ uniformly from $\sigma^{-1}(r)$ and $\sigma^{-1}(s)$ (with replacement if $r=s$). Call this model $G^{\prime}_{\text{SBM}}(n,m)$. In the sparse case $d=O(1/n)$, the resulting graph is simple with probability $\Theta(1)$, in which event it is generated by $G_{\text{SBM}}(n,m)$. Thus any event that holds with high probability in $G^{\prime}_{\text{SBM}}(n,m)$ holds with high probability in $G_{\text{SBM}}(n,m)$ as well.

Now fix a balanced partition $\tau$, and let $q$ denote the probability that an edge $(u,v)$ chosen in this way is within-group with respect to $\tau$. Recall that the overlap matrix $\alpha_{st}$ is the probability that $\tau(u)=t$ if $u$ is chosen uniformly from those with $\sigma(u)=s$. Up to $O(1/n)$ terms, the events that $\tau(u)=t$ and $\tau(v)=t$ are independent. Thus in the limit $n\to\infty$,

where $|\alpha|$ denotes the Frobenius norm,

Since $\alpha$ is doubly stochastic, Birkhoff’s theorem tells us it can be expressed as a convex combination of permutation matrices,

For fixed $\sigma$, the number of balanced partitions $\tau$ with overlap matrix $\alpha$ is the number of ways to partition each group $\sigma^{-1}(r)$ so that there are $\alpha_{rs}n/k$ vertices in $\sigma^{-1}(r)\cap\tau^{-1}(s)$:

where $H(\alpha)$ is the average entropy of the rows of $\alpha_{rs}/k$,

By the union bound, the probability that there are any good partitions with overlap matrix $\alpha$ is exponentially small whenever the sum of $H(\alpha)$ and the right-hand side of (3.2) is negative. For a fixed overlap $\beta$, maximized by the permutation $\pi$, the entropy $H(\alpha)$ is maximized when

Combining the bounds (3.2) and (19), and requiring that their sum is at least zero, completes the proof. ∎

3. Detection below the Kesten-Stigum bound

The Lower Bound

We apply the following theorem of Neeman and Netrapalli, translated into our notation.

In contrast, the probability of $G$ in the Erdős-Rényi model $G(n,d/n)$ is

We can rewrite this expression in a helpful way. For each pair of partitions $\sigma,\tau$, let us replace the product over vertices with a product over groups; let us assume that $\sigma$ and $\tau$ are both nearly balanced, so that $\alpha$ is doubly-stochastic. Since there are $\alpha_{rs}n/k$ vertices in $\sigma^{-1}(r)\cap\tau^{-1}(s)$, we have

where the factor of $1/2$ avoids double-counting of the unordered pairs $(u,v)$.

2. Maximizing ΦΦ\Phi

Achlioptas and Naor, in the process of proving a lower bound on the $k$-coloring threshold for Erdős-Rényi graphs, develop substantial machinery for optimizing $\Phi$-like functions over the Birkhoff polytope of doubly stochastic matrices [AN05]. Specifically, they relax the problem to maximizing over all row-stochastic matrices, and show that the maximizer is then a mixture of uniform rows and rows where all but one of the entries are identical. Although their bound is quite general, we quote here their results for the entropy. (Note that their definition of $H(\alpha)$ and ours differ by a factor of $k$.)

[AN05, Theorem 9] Let $\alpha$ be doubly stochastic with $|\alpha|^{2}=\rho$. Then

With this result in hand and using $f(1/k)=kh(1/k)=\log k$, we know that for all $\alpha$ with $|\alpha|^{2}=\rho$,

for $m\in[0,k(k-\rho)/(k-1)]$. Achlioptas and Naor determined the value of $d\lambda^{2}/2$ for which the right-hand side is less than or equal to zero for all $m$ in this interval and all $\rho\in[1,k]$.

[AN05, Proof of Theorem 7] When $\delta<(k-1)\log(k-1)$,

for all $m\in[0,k(k-\rho)/(k-1)]$ and all $\rho\in[1,k]$.

Our lower bound is an immediate corollary of this lemma. Substituting $\delta=d\lambda^{2}(k-1)^{2}/2$ and solving for $d$ gives

As we commented in §1, this corresponds to the lower bound on the $k$-colorability threshold of $G(n,d^{\prime}/n)$ where $d^{\prime}=2\delta=d\lambda^{2}(k-1)^{2}$, scaling the eigenvalue on each edge to $\lambda$ from its value $-1/(k-1)$ for $k$-cooring. This fits with the Kesten-Stigum threshold as well, since the amount of information (appropriately defined) transmitted along each edge is proportional to $\lambda^{2}$ [JM04].

Conclusions

Physically, we believe this occurs because there is a free energy barrier between a “paramagnetic” phase of partitions which are essentially random, and a “ferromagnetic” or “retrieval” phase which is correlated with the planted partition [DKMZ11b, DKMZ11a, ZM14]. Proving this seems within reach: rigorous results have been obtained in random constraint satisfaction problems [AC08, CE15] showing that solutions become clustered with $O(n)$ Hamming distance and $O(n)$ energy barriers between them, and that Markov chain Monte Carlo algorithms take exponential time to travel from one cluster to another. The goal here would be to show in a planted model that Monte Carlo takes exponential time to find the cluster corresponding to the planted solution.

Acknowledgments.

This work was supported by the ARO under contract W911NF-12-R-0012 and the John Templeton Foundation. We are grateful to Emmanuel Abbe, Afonso Bandeira, Amin Coja-Oghlan, Elchanan Mossel, and Joe Neeman for helpful discussions.

References