Global and Local Information in Clustering Labeled Block Models

Introduction

The stochastic block model is one of the most popular models for networks with clusters. The model has been extensively studied in statistics , computer science (where it is called the planted partition problem) and theoretical statistical physics .

The simplest block model has $k$ clusters of equal size, and is generated as follows. Starting with $n$ nodes, each node $v$ is randomly assigned a label $\sigma_{v}$ from the set $\{1,\ldots,k\}$. For each pair of nodes, $(u,v)$, if their labels are identical an edge is added between them with probability $p$, otherwise an edge is added with probability $q$. Often the case when $p>q$ is considered, and the question of interest is understanding how large $p-q$ must be for correct clusters recovery to be possible. In the recovery problem the input consists of the unlabeled graph and the desired output is a partition of the graph.

Real world networks are typically sparse. Thus, an interesting setting in the block model is when $p$ and $q$ are in $O(1/n)$. Here, it is more convenient to parametrize the problem by setting $p=a/n$ and $q=b/n$, where $a,b$ are constants. In the sparse setting, exact recovery is impossible as the resulting graph will have isolated nodes. Moreover, it is easy to see that even nodes with constant degree cannot be classified accurately given all other nodes in the graph. Thus the goal is to find a partition that has non-trivial correlation with the original clusters (up to permutation of cluster labels). This has sometimes been referred to as the cluster detection problem (see e.g. ); throughout the paper we refer to it as the cluster recovery problem (though note that the goal is not to recover every cluster with probability 1).

General results of Coja-Oghlan imply that it is possible to identify a partition that is correlated with the true hidden partition when $(a-b)^{2}\geq Ck^{4}(a+(k-1)b)$. A beautiful physics paper by Decelle et al. conjectured that the recovery problem is feasible for the case of two clusters when $(a-b)^{2}>2(a+b)$ and impossible when $(a-b)^{2}<2(a+b)$. The non-reconstructability in the case where $(a-b)^{2}<2(a+b)$ was proved by Mossel, Neeman and Sly , and more recently the same authors and Massoulié independently showed that recovery is possible when $(a-b)^{2}>2(a+b)$.

The aforementioned results along with previous results for denser block models provide a detailed picture of recovery in the stochastic block model. However, the model they consider is idealized and does not capture many aspects of real network problems. One such aspect is that in many realistic settings, node label information is available for some of the nodes. For example, in social networks, the group label of some individuals (nodes) is known. In metabolic networks, the function of some of the nodes may be known. Indeed, there has been much recent work in the machine learning and applied networks communities on combining node and network information (see for example ). There are several ways in which node and edge information can be incorporated; in real applications nodes and edges contain rich information which is noisy, but correlated with the node’s “true” label and with the “similarity” of pairs of nodes.

In this paper, we study a simple model which incorporates both node and edge information which we call the labeled stochastic block model. This model has been considered previously in the physics literature . In addition to having the unlabeled graph as an input, a small random fraction of the nodes’ labels are also provided as input to the clustering algorithm.

2 The big effect of a small number of node labels

It is easy to see that even a vanishing fraction of node labels can play a major role in the cluster recovery problem. For example, consider the denser case where the clusters $C_{1},\ldots,C_{k}$ can be identified accurately . Here, it is impossible to distinguish between a clustering $C_{1},\ldots,C_{k}$ where the nodes in cluster $C_{i}$ have label $i$ and the same clustering where the nodes in cluster $i$ have label $\pi(i)$ for any permutation $\pi$ of the labels. However, note that for any $p>0$, given a $p$-fraction of the node labels, it is possible to identify the permutation $\pi$ correctly with high probability. It is natural to ask if the same result holds in the sparse case, and it is not hard to see that a similar statement can be made (see Proposition 1).

The above observation shows that even a small amount of node information can overcome the problems of symmetry in the stochastic block model. Another problem of symmetry present in the unlabeled model is that there is no local algorithm that can identify clusters better than random guessing. Informally, a local algorithm determines the label of a node based solely on an $o(\log n)$ neighborhood of that node, including possibly uniform independent random variables attached to each node of the graph (see A.2 for a formal definition and for examples). The proof that a local algorithm cannot detect better than random guessing in this case is folklore, and we include it here for completeness. This limitation in detection may be compared to the problem of finding independent sets, where local algorithms can have non-trivial power (while still being less powerful than global algorithms) . It is therefore natural to ask:

Does a vanishing fraction of labeled nodes allow local algorithms to detect clusters? If so, when?

An even a more direct question relates to the statistical power of revealing some of the node labels. While it is clear that revealing a large fraction of the node labels allows non-trivial recovery, it is far from clear what the effect is when this fraction is vanishingly small. On the one hand, we might expect by continuity that revealing a vanishing fraction of the node labels will be identical in the limit to revealing no labels. On the other hand, we might imagine how a small fraction of the node labels could be used as seeds for recovery algorithms. We thus ask:

Does revealing a vanishing fraction of the node labels change the detectability threshold? Does it change the fraction of correctly labeled nodes?

The latter question was considered in recent work in statistical physics .

3 Our results

To set the stage for our contributions, we begin with some observations regarding the utility of local information. The proofs of these propositions are straightforward (see Appendix A), but they are useful for establishing context of how information about (a small fraction of) node labels may help. The first is that even a vanishingly small proportion of node labels aids in breaking the symmetry and assigning labels to the cluster assignments.

Given a clustering algorithm which outputs clusters correlated with the true clustering, a small fraction of revealed node labels is sufficient to output a labeling which is correlated with the true labeling.

In the absence of any node information, it is an easy folklore result that any local algorithm cannot recover clusters. However, we show that in the case of two clusters, when a small fraction of node labels are revealed, a local algorithm is able to recover the clusters optimally. This latter result is a direct corollary of a robust reconstruction result on trees of .

In the unlabeled stochastic block model, no local algorithm can find a clustering correlated with the true clustering.

In an instance of the labeled stochastic block model, when $k=2$, if $(a-b)^{2}>C(a+b)$ for some large constant $C$, then there is a local algorithm which given a vanishing fraction of labeled nodes, reconstruct the label of all nodes with the same accuracy as the optimal (non-local) algorithm for the unlabeled problem.

We also observe that results on census reconstruction imply that above the Kesten-Stigum bound a vanishingly small fraction of revealed nodes suffices for the cluster recovery problem.

For any fixed $k$, above the robust reconstruction threshold (i.e. when $(a-b)^{2}>k(a+(k-1)b)$), when the fraction of revealed node labels is vanishingly small, the cluster recovery problem is solvable by a local algorithm.

The proof follows more or less directly from previous results, but we include it in Appendix A.4 for completeness.

In this context, one might expect that labels could allow clustering in the labeled model in regimes which cannot be effectively clustered in the unlabeled model. The case of two clusters is the case we understand the best. Here, utilizing results for the reconstruction problem on trees and of , we answer Question 2 in the negative (Theorem 2) and at the same time answer Question 1 positively (Propositions 3 and 4). The complete picture for the case of two clusters is presented in Figure 1(a).

For any fixed $k>2$, the picture is much more complicated. In this case, we observe that below the tree reconstruction threshold (this corresponds to $\theta^{*}$ in Figure 1(b)), a vanishing fraction of node labels do not assist in the cluster recovery problem (see Theorem 2).

For any fixed $k$, below the associated tree reconstruction threshold (to be defined later), when the fraction of revealed node labels is vanishingly small, the cluster recovery problem is not solvable. In particular, when $k=2$, the threshold is the Kesten-Stigum bound of $(a-b)^{2}<2(a+b)$; for $k\geq 2$, if $a-b<k$ then recovery is impossible.

Our main interest is in the case when the number of clusters is very large. Here, we consider the setting when the fraction of revealed nodes $p\to 0$, and simultaneously the number of clusters $k=k(p)\rightarrow\infty$. In this setting, we show that revealing node labels has a dramatic effect on the threshold for cluster recovery. We show that a local algorithm successfully solves the cluster recovery problem even below the conjectured algorithmic threshold in the unlabeled case, $(a-b)^{2}=k(a+(k-1)b)$. As the number of clusters $k\to\infty$, our algorithm works all the way down to the tree reconstruction threshold of $(a-b)/k>1$. Moreover, it is impossible to recover (locally or globally) with a vanishing fraction of labeled nodes if $(a-b)/k<1$. Both results follow from the corresponding results on trees.

For every $\delta>0$, there exists $\epsilon=\epsilon(\delta)>0$ such that for every $p>0$, if $k=k(p)$ is large enough as a function of $p$ and $a-b>(1+\delta)k$, then the label of a random node can be recovered with probability at least $\tfrac{1}{k}+\epsilon$.

Note that $\epsilon$ depends on $\delta$ but is independent of $p$.

Recent work in statistical physics argues that for every fixed number of clusters $k$, a vanishing fraction of labels does not provide any advantage in the detection probability over having no labels at all. We note that in our results, the order of limits is exchanged as the number of clusters $k$ needed for our results to hold, depends on the fraction of nodes revealed. Thus, there is no contradiction between the results (see also ). Figure 1(c) provides a detailed picture of the case in which the number of clusters is very large (in the setting of Theorem 1).

Open Problems

In the case of two clusters, we conjecture that whenever any fraction of node labels are revealed, there is a local algorithm that recovers the clusters optimally. This would follow from a related conjecture regarding information flow on trees stated below. We report some simulations suggesting the veracity of the conjecture in Appendix B.

Let $T$ be an infinite tree with root $\rho$. The tree is labeled from the set $\{\pm 1\}$ as follows. First, the root is assigned a label from $\{\pm 1\}$ at random. Along each edge the label is propagated with probability $1-\eta$ and flipped with probability $\eta$. Let $(T,\tau)$ denote the resulting labeled tree. Add each node independently to a set $R$ with probability $p$. Finally for any $r$, let $\partial T_{r}$ denote the set of leaves at depth $r$. Then, for any value of $p>0$ and $\eta<1/2$,

In addition to Conjecture 1, several interesting questions remain, particularly in the regime where $k$ is large. When $k$ is large, is it possible to use global and local information together to obtain better recovery guarantees? Which algorithmic tools might allow one to use global and local information simultaneously?

Another open problem relates to different types noise models. The assumption in the current paper is that each label is revealed accurately with a vanishing probability. But one may consider other types of noise. In particular, we may assume for example that for each node independently we are given the correct label with small probability $\delta$ and otherwise a uniformly chosen label. Is it true that the same results hold for this noise model as for the noise model considered here? For most of the results presented here, it is easy to see that the answer is yes. However, for one of our main results, Theorem 1, the proof does not extend to the latter noise model. It is an interesting open problem to determine the effect of the noisy information in this setup.

A short abstract describing these results will appear in proceedings of RANDOM 2014.

E.M. thanks Cris Moore, Joe Neeman, Allan Sly and Lenka Zdeborová for many interesting discussions related to the block model. We would like to thank the authors of for discussion of their work at its early stages. The authors would like to thank the Simons Institute for the Theory of Computing where much of the work reported here was carried out. The authors would also like to thank anonymous referees for their helpful comments.

Model

The stochastic block model is a generative model for modular random networks, defined by the following set of parameters: the number of clusters $k$, the expected fraction of nodes in each cluster $i$, $\langle f_{i}\rangle_{i=1}^{k}$ , and a $k\times k$ symmetric affinity matrix $P_{i,j}$ indicating the edge probability between nodes of type $i$ and $j$. A random network $G$ on $n$ nodes is generated as follows:

First, each node $v$ is assigned a label $\sigma_{v}\in\{1,\ldots,k\}$, s.t. $\Pr[\sigma_{v}=i]=f_{i}$.

For every pair of nodes $u,v$, an edge is added between them with probability $P_{\sigma_{u},\sigma_{v}}$, independently for each pair.

In this work, we are mainly interested in the sparse case, i.e., when the average degree of the graph is constant. We focus on the setting where edge probabilities only depend on whether the labels of the endpoint are same or different. Thus, $P_{ii}=a/n$ for $1\leq i\leq k$ and $P_{ij}=b/n$ for $i\neq j$, for constants $a>b$.This is the so-called assortative model. Also, we focus on the case where $f_{i}=1/k$ for each $i$, i.e., each cluster is roughly of the same size. The model is denoted by ${\mathcal{G}}(n,k,a,b)$, and $(G,\sigma)\sim{\mathcal{G}}(n,k,a,b)$ denotes an instance of a graph generated according to the model, where $\sigma$ are the cluster labels of the nodes.

Labeled Block Model: The labeled block model has an additional parameter $p$, which is the probability with which the true cluster label of any given node is revealed. Thus, if $(G,\sigma)\sim{\mathcal{G}}(n,k,a,b)$ is an instance of the block model, $R\subseteq[n]$ is chosen by placing each node of $G$ in $R$ independently with probability $p$. We denote this by $(G,\sigma,R)\sim{\mathcal{G}}(n,k,a,b,p)$. The clustering algorithm has access to the edges of $G$ and the cluster labels $\sigma_{R}$ of nodes in $R$, i.e., $(G,R,\sigma_{R})$.

We also introduce the following notation for convenience. For any two nodes $u,v\in G$, let $d(u,v)$ denote the distance between $u$ and $v$. We let $G_{r}(v)=\{u\in G~{}|~{}d(u,v)\leq r\}$ denote the neighborhood of radius $r$ around $v$; at times we will use $G_{r}$ when $v$ is clear from context. Let $\partial G_{r}(v)=\{u\in G~{}|~{}d(u,v)=r\}$ denote the boundary of $G_{r}(v)$.

Cluster Recovery: The cluster recovery problem is the problem of recovering the cluster label of nodes in the stochastic block model or labeled stochastic block model with better-than-random probability. Note that correct recovery of all nodes is not the aim, nor is it possible due to the sparsity of the graph. This problem has also been called the cluster detection problem and the cluster reconstruction problem; for consistency we will use the term recovery throughout the paper when referring to graphs, and use reconstruction when referring to broadcast processes on trees.

2 Information Flow on Trees

We use some results regarding information flow on trees. For a detailed survey on this topic, the reader is referred to .

Broadcast Process: Let $T$ be an infinite rooted tree with root $\rho$. Each node in the tree is assigned a label from some finite alphabet $\Sigma=\{1,\ldots,k\}$. The root is labeled by choosing a label $\tau_{\rho}\in\Sigma$ uniformly at random. For any edge $(u,v)$, with $d(u,\rho)<d(v,\rho)$, $\tau_{v}$ is conditionally independent given $\tau_{u}$, and is chosen as follows: $\tau_{v}=\tau_{u}$ with probability $1-(k-1)\eta$, and $\tau_{v}\in\Sigma\setminus\{\tau_{u}\}$ randomly otherwise, where $\eta<1/k$ is the broadcast parameter. We denote this process by ${\mathcal{T}}(T,k,\eta)$ and an instance generated according to this process by $(T,\tau)\sim{\mathcal{T}}(T,k,\eta)$. As in the block model, we can consider the process when the label of each node is revealed with probability $p$, i.e., $R\subseteq T$ is obtained by adding each $v\in T$ to $R$ independently with probability $p$. We denote this process by $(T,\tau,R)\sim{\mathcal{T}}(T,k,\eta,p)$. The reconstruction problem is to identify the label of the root, $\rho$ given the labeled nodes up to some depth $r$. Thus, the algorithm has access to $(T_{r},R_{r},\tau_{R_{r}})$, where $R_{r}$ denotes $T_{r}\cap R$.

Percolation Process: Let $T$ be an infinite rooted tree with root $\rho$. For percolation parameter $\lambda$, each edge $e\in T$ is deleted independently with probability $\lambda$. Let $C(\rho)$ denote the component of $T$ containing the root after percolation.

Recovery in the many clusters regime

We show that when the number of clusters is very large, even a very small fraction of revealed node labels allow for cluster recovery, and even in some regimes below the conjectured algorithmic threshold in the standard model. More formally, if $p$ is the probability that the label of a node is revealed, and if the number of clusters is at least $k^{*}=k(p)$, then even as $p\rightarrow 0$, the algorithm performs better than random assignment. The algorithm (Algorithm 1) is simple and local—it considers a neighborhood around each node and uses the revealed node information in the neighborhood to make its prediction.

Let $b>1$ be fixed, let $a=b+(1+\delta)k$ for some $\delta>0$, let $p>0$ be fixed. Then, there exists an $\epsilon=\epsilon(b,\delta)$ and $k^{*}=k^{*}(b,\delta,p)$, such that for every $k\geq k^{*}$, if $(G,R,\sigma_{R})\sim{\mathcal{G}}(n,k,a,b,p)$, Algorithm 1 labels any random node of $G$ correctly with probability at least $\epsilon$. In particular, there exists settings where $(a-b)^{2}<k(a+(k-1)b)$ and recovery is still possible.

Let $r<r(n)=\frac{1}{10\log(2(a+(k-1)b))}\log(n)$. There exists a coupling between $(G,\sigma)$ and $(T,\tau)$ such that $(G_{r},\sigma_{G_{r}})=(T_{r},\tau_{T_{r}})$ a.a.s.

We now prove Theorem 1 through a sequence of lemmas.

Let $T$ be a Galton-Watson tree with offspring distribution $\operatorname{Poisson}(d)$ for $d=\tfrac{a+(k-1)b}{k}$, and let $\eta=\tfrac{b}{a+(k-1)b}$ be the parameter of the $k$-label broadcast process on $T$ (so that $(T,\tau,R)\sim{\mathcal{T}}(T,k,\eta,p)$). Consider the coupling between $(G,\sigma,R)$ and $(T,\tau,R)$ as per Lemma 1.

Next, we relate the broadcast process on $T$ to a percolation process on $T$. Suppose the root is labeled according to some $\tau_{\rho}\in\Sigma=\{1,\ldots,k\}$. Then, across any edge the probability that the label remains unchanged is $1-(k-1)\eta$. Thus, if we look at a percolation process with $\lambda=1-(k-1)\eta$, then the connected component $C(\rho)$ corresponds to a tree in which every node has the same label as the root.

where the first inequality follows from independence and from the fact that $\Pr[\operatorname{Binomial}(q,p)\geq B]$ is increasing in $q$, and the second inequality is an application of Equation 1.

Say that a mutation occurs if the color changes along any edge. We note that in order for the event ${\mathcal{E}}$ to occur, two mutations must occur in the subtrees corresponding to different children of $\rho$, since $\rho$ must be the first common ancestor. By the Markov property of the broadcast process, it follows that the two mutations must be independent. Hence, it suffices to bound the probability of two independent mutations to the same color.

Before proving Theorem 1, we prove the corresponding version for Galton-Watson trees.

First, we check that $\lambda=1-k\eta=\tfrac{1+\delta}{d}$. Thus, $\lambda d=1+\delta>1$.

Finally, we can appeal to Proposition 5 to complete the proof of Theorem 1.

By Lemma 1, for $(G,R,\sigma)\sim{\mathcal{G}}(n,k,a,b,p)$, if $(T,R,\tau)\sim{\mathcal{T}}(T,k,\eta,p)$ where $T$ is a Galton-Watson tree with offspring distribution $\operatorname{Poisson}(d)$ where $d=\frac{a+(k-1)b}{k}$ and $\eta=\frac{b}{a+(k-1)b}$, then we can couple $G_{r}(v)$ with $T_{r}$. Note that $\lambda=1-k\eta$ is equal to $(1+\delta)/d$, and thus Proposition 5 implies the desired result immediately. ∎

Upper bounds below the threshold

In this section, we consider the setting where there are a fixed number of clusters and the fraction of revealed node labels is vanishingly small. We show that below a certain threshold that arises from the reconstruction problem on trees, in the limit as $p\rightarrow 0$, cluster recovery is not possible. We first note that a threshold exists for the tree problem.

Let $T$ be a Galton-Watson tree with average degree $d>1$. Let $(T,\tau)\sim{\mathcal{T}}(T,k,\eta)$ be the labels obtained by the broadcast process with parameter $\eta$. There there exists a predicate, $\pi_{k}(d,\eta)$, monotonically decreasing in $\eta$ and monotonically increasing in $d$, such that if $\pi_{k}(d,\eta)$ is false, then for each $i\in[k]$,

For the case of $k=2$, the exact form of $\pi_{2}$ is known, $\pi_{2}(d,\eta)=\mathds{1}[d(1-2\eta)^{2}>1]$, which follows from . In , the exact threshold is given for $k=3$, and bounds on the thresholds are given for $k\geq 5$. For $k\geq 4$, the exact form $\pi_{k}$ is not known, but it holds that if $(1-k\eta)d<1$, $\pi_{k}(d,\eta)$ is false. (This was proved for the case of regular trees in ; the proof for Galton-Watson trees is essentially identical). For all $k$, a reconstructability threshold in $\eta,d$ provably exists in the limit as $n\to\infty$; the proof of Proposition 6 relies on the monotonicity of $\pi_{k}$ in $\eta$ and $d$, and the existence of points where reconstruction is feasible and also points where it is impossible.

The threshold from Proposition 6 can be translated to an equivalent threshold $\theta_{k}(a,b)$ in the stochastic block model. We show that even in the labeled stochastic block model (where each node’s label is revealed with probability $p$), if $p$ is small and $\theta_{k}$ is false then it is impossible to recover node labels with better accuracy than random guessing. Specifically, we study the setting where $k$ is fixed, $\theta_{k}$ is false, and $p\to 0$. We first prove this for the general $k$-cluster case, then give an alternative proof for the case of two clusters (which results in a more explicit dependence on $p$).

Fix $v\in[n]$, and let $(G,R,\sigma)\sim{\mathcal{G}}(n,k,a,b,p)$, for $a+(k-1)b>k$. Then if the predicate $\theta_{k}(a,b)=\pi_{k}(\tfrac{a+(k-1)b}{k},\tfrac{b}{a+(k-1)b})$ is not satisfied, then for all $i\in\Sigma=[k]$,

The above result says that as the amount of revealed node information goes to zero, recovering a clustering that is correlated with the true clustering is not possible if $\theta_{k}$ is false. The proof of Theorem 2 requires some results from the literature which we now state.

We also use a result of which states that conditioned on $\sigma_{\partial G_{r}}$, information from further nodes is not helpful in clustering.

Fix $v\in[n]$, and let $(G,R,\sigma)\sim{\mathcal{G}}(n,k,a,b,p)$, with $a+(k-1)b>k$. For $r\leq\frac{1}{10\log(2(a+(k-1)b))}\log n$, let $C=\{u\in G~{}|~{}d(u,v)>r\}$, $B=\partial G_{r}$, and $A=\{u\in G~{}|~{}d(u,v)\leq r\}$. Then

In , the lemmas above are stated for the case when $k=2$; however, the same proofs apply for any value of $k$. Armed with Lemmas 1, 4 and Proposition 6, we can now prove Theorem 2.

We begin by proving an analogous result for a broadcast process on a Galton-Watson tree. Let $T$ be a Galton-Watson tree with average degree $d=(a+(k-1)b)/k$. Let $(T,\tau,R)\sim{\mathcal{T}}(T,k,\eta,p)$, where $\eta=\frac{b}{a+(k-1)b}$. Fix some radius $r$ around $\rho$, and let $W_{1}=R\cap T_{r}$.

Using this, as $(p,r)\to(0,\infty)$, we have

Since $\theta_{k}(a,b)$ is false by assumption, $\pi_{k}(\eta,d)$ is false for the values of $\eta,d$ given above. Thus, we can apply Proposition 6 to see that,

If we wanted Theorem 2 to hold for $T$ rather than $G$ we would be done. By the Markov property of the broadcast process on $T$, the information from $\tau_{\partial T_{r}}$ isolates $\rho$ from the effects of information beyond $T_{r}$. However, because we are not in a tree, we must now take some extra care to apply this conclusion to $G$.

Now, we translate these results to the stochastic block model setting. We first apply the coupling in Lemma 1 to (2) and (3)—it is clear that the revealed nodes in $T$ can be coupled with the revealed nodes in $G$. Let $R_{1}=R\cap G_{r}(v)$ and let $B=\{u\in G~{}|~{}d(u,v)=r\}$. Then, we have the

All that now remains is to prove that global information does not help in the block model setting. To do this, we will look at the entropy of $\sigma_{v}$ conditioned on different sets of variables.

Using (4) it is clear that in the limit as $n\to\infty$ and $(p,r)\to(0,\infty)$, $H(\sigma_{v}~{}|~{}G,R,\sigma_{R_{1}},B)$ has the maximum possible value. By applying Lemma 4, we know that $H(\sigma_{v}~{}|~{}G,R,\sigma_{R_{1}},\sigma_{B})=(1+o(1))H(\sigma_{v}~{}|~{}G,R,\sigma_{R},\sigma_{C},\sigma_{B})$, and hence in the asymptotic limit the latter conditional entropy is also the maximum possible. Then, by monotonicity of conditional entropy,

Thus, we get that $\lim_{p\to 0}\lim_{n\to\infty}H(\sigma_{v}~{}|~{}G,R,\sigma_{R})$ is the maximum possible. This completes the proof of the theorem. ∎

In the special case of $k=2$ clusters, it is possible to prove the same result using a slightly different technique. Here, we get a more explicit convergence rate in terms of $p$. Note that the RHS in the statement of Theorem 3 cannot be smaller than $p$, since with probability $p$ the node of the label itself is revealed.

Fix $v\in[n]$, and let $(G,R,\sigma)\sim{\mathcal{G}}(n,2,a,b,p)$, for $a+b>2$. Then if $(a-b)^{2}<2(a+b)$, then

For this better dependence, we rely on a result of Evans et al. regarding predicting the label of the root, when the labels of some nodes in the tree are revealed.

Let $W$ be a finite set of nodes in the tree $T$. Let $(T,\tau)\sim{\mathcal{T}}(T,2,\eta)$ be a labeling of a tree obtained by the broadcast process as defined in Section 2.2 with alphabet $\Sigma=\{\pm 1\}$, and parameter $\eta$. Let $S$ be any set of nodes that separates the root from $W$. Then,

We consider the question of predicting the label $\tau_{\rho}$, given all the labels $\tau_{W}$. Note that when $\theta_{2}(a,b)$ is false, for the parameters above $(1-2\eta)^{2}d=(a-b)^{2}/(2(a+b))<1$. Then, using Proposition 7, we have the following:

Notice that since $(1-2\eta)^{2}d<1$, $((1-2\eta)^{2}d)^{r}\rightarrow 0$ as $r\rightarrow\infty$.

The rest of the proof proceeds analogously to the proof of Theorem 2 starting at (2) and applying the Cauchy-Schwarz inequality to (6). ∎

References

Appendix A When Little Information Helps

Here, we prove the simple observations described in Section 1 which illustrate the power and limitations of revealed labels in the stochastic block model.

Let $C:[n]\to[k]$ be the output of some clustering algorithm with the guarantee that there exists a permutation $\pi:[k]\to[k]$ such that

Then for $p\geq\tfrac{1}{n}\tfrac{512k}{\epsilon^{3}}\log\tfrac{4k}{\delta}$, if a $p$-fraction of node labels are revealed, we can find a function $g:[k]\to[k]$ such that

The proof follows easily from the following lemma, which is a simple application of the Chernoff-Hoeffding bound.

where $D_{j}$ is the probability of $j$ under $D$.

For any $j\in[k]$, let $\hat{D}_{j}$ be the fraction of of $j$ in $S$. By the Chernoff-Hoeffding bound, $\Pr[|D_{j}-\hat{D}_{j}|\geq\alpha]\leq 2\exp(-m\alpha^{2})$. By union bound, the probability that this happens for any $j\in[k]$ is at most $2k\exp(-m\alpha^{2})$. Thus, if we let $m\geq\frac{1}{\alpha^{2}}\log(\frac{4k}{\delta})$, this happens with probability at most $\delta/2$. Hence, we have $|D_{i}-\max_{j}D_{j}|\leq 2\alpha$ with probability at least $1-\delta/2$. Letting $\alpha=\frac{\epsilon}{8}$ completes the proof. ∎

Let $C:[n]\to[k]$ be a clustering with the assumed property, and let $C_{i}=\{v\in[n]~{}|~{}C(v)=i\}$. If $|C_{i}|\leq\tfrac{\epsilon n}{4k}$, we assign each node in $C_{i}$ a random label.

Since by the hypothesis of the proposition, the LHS of the above inequality is at least $\tfrac{1}{k}+\epsilon$, the assertion holds. ∎

A.2 Proof of Proposition 2

Now, we discuss the impact of revealed labels in the context of local algorithms. We use the definition of local algorithms as in . (The reader is referred to their paper and references therein for more background on local algorithms.)

Let $G$ be a graph with node set $V$, and for each $v\in V$, let $X_{v}\in$ uniformly at random. An $r$-local algorithm on $G$ is one in which the value of each node $v\in V$ is decided by a function $f_{v}(G_{r}(v),X_{r}(v))$, where $X_{r}(v)$ is the set of samples from $D$ associated with $G_{r}(v)$.

Here, we justify the intuitive statement that no $r$-local algorithm can accurately reconstruct clusters in the unlabeled stochastic block model for $r=o(\log n)$.

In the unlabeled stochastic block model, let $A$ be a local algorithm with node functions $\{f_{v}\}:G_{r}(v)\to\Sigma$, where here $G_{r}(v)$ denotes the structural information and random variables on the neighborhood of radius $r=o(\log n)$ around $v$. Then for all $\epsilon>0$,

where the maximum is taken over all possible permutations of the labels.

By the union bound over all $k!$ permutations it suffices to show that for each fixed permutation $\pi$:

Without loss of generality, we may assume that $\pi$ is the identity permutation. Let

Thus the proof reduces to showing that for a fixed $u\neq v$ (chosen before the graph is labeled and the edges are generated) it holds that

Now: $\Pr[f_{v}(G_{r}(v))=\sigma_{v}|f_{u}(G_{r}(u))=\sigma_{u}]$ is bounded by

since with high probability $u$ and $v$ are at distance $\Omega(\log n)$.

If there are $\gamma_{i}$ nodes with label $i$ in $G_{2r}(u)$, the distribution of $\sigma_{v}$ for a random $v$ with $d(u,v)>2r$ has total variation distance at most $\tfrac{2k}{n-|G_{2r}(u)|}\sum_{i\in[k]}\gamma_{i}$ from uniform; knowing $u$ was assigned $\sigma_{u}$ and $d(u,v)>2r$ only yields information about the distribution of values of $\gamma_{i}$, and has no other implications for $v$. Clearly, $\sum_{i\in[k]}\gamma_{i}=|G_{2r}(u)|$, and with high probability, $|G_{r2}(u)|=O(d^{2r}\log n)$ for $d=\tfrac{a+(k-1)b}{k}$. Thus, as $n\to\infty$, $\Pr[f_{v}(G_{r}(v))=\sigma_{v}~{}|~{}f_{u}(G_{r}(u))=\sigma_{u},d(u,v)>2r]=\frac{1}{k}$ completing the proof.

A.3 Proof of Proposition 3

It follows from the work of Evans et al. that ${\mathsf{T}}^{*}(d,\eta)>0$ if and only if $d(1-2\eta)^{2}>1$ .

then for any $\delta\in[0,1/2)$, whenever $d(1-2\eta)^{2}\geq C$ for a sufficiently large constant $C$, $\widetilde{{\mathsf{T}}}^{*}(d,\eta)={\mathsf{T}}^{*}(d,\eta)$.

Let $(G,R,\sigma_{R})\sim{\mathcal{G}}(n,2,a,b,p)$, with $a+b>2$. Then, there exists a large constant $C$, such that if $(a-b)^{2}>C(a+b)$, there is a local algorithm $A$ such that if $A(v)$ denotes the label output by the algorithm, for a random node $v$,

Combining (8) and (9) together with the result in , we have that whenever $d(1-2\eta)^{2}\geq C$, (7) is true.

Finally, the mapping from the result on trees to the block model follows from a coupling between local neighborhoods of nodes in the block model with the broadcast process on trees. For details see Lemma 1 and its application in the proof of Theorem 2.

This implies the proposition, as we can take $A$ to be the Belief Propagation algorithm (see e.g., ) with radius $r$, with nodes in $R$ initialized according to their labels and with nodes outside of $R$ initialized randomly. Note that belief propagation is known to converge on trees. ∎

A.4 Proof of Proposition 4

Let $(G,\sigma,R)\sim{\mathcal{G}}(n,k,a,b,p)$, with $a+(k-1)b>k$. Then, there exists a constant $\epsilon=\epsilon(a,b,k,p)$, such that if $(a-b)^{2}>k(a+(k-1)b)$, there is a local algorithm $A$ such that if $A(v)$ denotes the label output by the algorithm, for a random node $v$,

The result also holds for the noisy-label model.

We control the second moment by induction. Let

where $S_{j}$ and $S^{\prime}_{j}$ are the sums corresponding to two sibling sub-trees of $j$ levels each (so that the root labels of the trees of $S_{j}$ and $S^{\prime}_{j}$ are correlated). Similarly, let

We obtain a recurrence for the value of $A_{j}$ by considering the contribution from subtrees rooted at the root’s children (where we have applied the triangle inequality):

where $D$ is a random variable corresponding to the degree of the root. We can bound the initial values of the recurrence by:

Plugging this back to $A_{j}$ and using the fact that the variance and expected value of a Poisson variable are identical, we get that

Since $d\lambda^{2}>1$ the expression above is bounded by

for some absolute constant $C=C(d\lambda^{2})$. Thus if we look at the difference of means:

and the second moment is bounded above by

Appendix B Conjecture

In the case of two clusters, we conjecture that whenever any node label information is present, a local algorithm is already able to recover the clusters optimally. The algorithm is the following: Fix some radius $r$, for each $v\in G$, look at the neighborhood $G_{r}(v)$, let $R_{r}\subseteq G_{r}(v)$ denote the revealed nodes in the neighborhood. As long as $r\leq c\log(n)$ for a sufficiently small constant $c$, the neighborhood is a tree with high probability. Then $\Pr[\sigma_{v}=1~{}|~{}R_{r},\sigma_{R_{r}}]$ can be computed exactly by belief propagation. We conjecture that this is optimal. This would follow from a related conjecture regarding the broadcast process on trees and an application of Lemma 1.

Let $T$ be infinite tree with root $\rho$. Let $(T,\tau,R)\sim{\mathcal{T}}(T,2,\eta,p)$ (see Section 2). Then for any $p>0$ and $\eta<1/2$,

B.2 Simulation

To test this conjecture, we ran the Belief Propagation algorithm on $3$-regular trees of depth $10$, in which labels were assigned to nodes according to broadcast processes starting at the root. Let $L$ denote the set of leaves at level $10$. Each node in the interior was revealed independently with probability $p$, to get the set $R$. We considered $p\in\{0.01,0.05,0.10,0.20\}$. We also tried various settings of the broadcast parameter, $\eta$. We chose $\eta\in\{0.1,\eta_{c},0.3,0.4\}$, where $\eta_{c}=\frac{1}{2}\left(1-\frac{1}{\sqrt{3}}\right)$ is the threshold value for the setting considered.

The labeling process was always initiated with the root having label $1$. Thus, we were interested in the posterior probability of the root being labeled $1$ in various cases. We computed this posterior probability in three cases: (i) using only the labels at the leaves, denoted by $p_{L}$ (ii) using only the interior nodes, denoted $p_{R}$, and (iii) using both the leaves and the interior nodes, denoted by $p_{L,R}$.

In the first case, only global information is used—i.e., the set of labels at the boundary is the maximum possible information that can be inferred using the global properties of the graph. Thus, in some sense this is an upper bound on the utility of global information. In the second case, only local information in the form revealed nodes in the neighborhood is used. Finally, in the the third case, both local and global information is used.

Our conjecture suggests that as $r\to\infty$, $|p_{R,L}-p_{R}|\rightarrow 0$. Figure 2 shows our results. Each plot corresponds to a fixed value of $\eta$, and displays the average distance $|p_{R,L}-p_{R}|$ for different values of $p$. We ran the simulation multiple times for each setting of $p$ and $\eta$ and the standard deviation is marked on the plot.