How Robust are Reconstruction Thresholds for Community Detection?

Introduction

The stochastic block model is one of the oldest and most ubiquitous models for studying clustering and community detection. It was first introduced by Holland et al. [holland] more than thirty years ago and since then it has received considerable attention within statistics, computer science, statistical physics and information theory. The model defines a procedure to generate a random graph: first, each of the $n$ nodes is independently assigned to one of $r$ communities, where $p_{i}$ is the probability of being assigned to community $i$. Next, edges are sampled independently based on the community assignments: if nodes $u$ and $v$ belong to communities $i$ and $j$ respectively, the edge $(u,v)$ occurs with probability $Q_{ij}$ independent of all other edges, where $Q$ is an $r\times r$ symmetric matrix. The goal is to recover the community structure — either exactly or approximately — from the graph.

Since its introduction, the stochastic block model has served as a testbed for the diverse range of algorithms that have been developed for clustering and community detection, including combinatorial methods [bui], spectral methods [mcsherry], MCMC [jerrum], semidefinite programs [boppana] and belief propagation [MNSbelief]. Recently, the stochastic block model has been thrust back into the spotlight, the goal being to establish tight thresholds for when community detection is possible, and to find algorithms that achieve them. Towards this end, Decelle et al. [decelle] made some fascinating conjectures (which have since been resolved) in the case of two equal-sized communities with constant average degree, that we describe next.

Throughout this paper, we will focus on the two-community case and use $a/n$ and $b/n$ to denote the within-community and between-community connection probabilities respectively. We will be interested in the sparse setting where $a,b=\Theta(1)$. Moreover we set $p_{1}=p_{2}=1/2$, so that the two communities are roughly equal-sized, and we assume $a>b$ (although we discuss the case $a<b$ in Appendix D). We will use $G(n,a/n,b/n)$ to denote the corresponding random graph model. The setting of parameters above is particularly well-motivated in practice, where a wide variety of networks have been observed [leskovec] to have average degree that is bounded by a small constant. It is important to point out that when the average degree is constant, it is impossible to recover the community structure exactly in the stochastic block model because a constant fraction of nodes will be isolated. Instead, our goal is to recover a partition of the nodes into two communities that has non-trivial agreement (better than random guessing) with the true communities as $n\rightarrow\infty$, and we refer to this as partial recovery.

[decelle] If $(a-b)^{2}>2(a+b)$ then partial recovery in $G(n,a/n,b/n)$ is possible, and if $(a-b)^{2}<2(a+b)$ then partial recovery is information-theoretically impossible.

This conjecture was based on deep but non-rigorous ideas originating from statistical physics, and was first derived heuristically as a stability criterion for belief propagation. This threshold also bears a close connection to known thresholds in the broadcast tree model, which is another setting in which to study partial recovery. We formally define the broadcast tree model in Section 2.1, but it is a stochastic process described by two parameters $a$ and $b$. Kesten and Stigum [kesten-stigum] showed that partial recovery is possible if $(a-b)^{2}>2(a+b)$, and much later Evans et al. [evans] showed that it is impossible if $(a-b)^{2}\leq 2(a+b)$. The connection between the two models is that in the stochastic block model, the local neighborhood of a node resembles the broadcast tree model, and this was another compelling motivation for the conjecture.

In an exciting sequence of developments, Mossel, Neeman and Sly [mns] proved a lower bound that even distinguishing $G(n,a/n,b/n)$ from an Erdős–Rényi graph $G(n,(a+b)/2n)$ is information-theoretically impossible if $(a-b)^{2}\leq 2(a+b)$, by a careful coupling to the broadcast tree model. Subsequently Mossel, Neeman and Sly [mns2] and Massoulié [massoulie] independently gave matching algorithms that achieve partial recovery up to this threshold, thus resolving the conjecture! Mossel, Neeman and Sly [MNSbelief] later showed that for some constant $C>0$, if $(a-b)^{2}>C(a+b)$ then belief propagation works and moreover the agreement of the clustering it finds is the best possible.

In fact, many other sorts of threshold phenomena have been found in different parameter regimes. Abbe, Bandeira and Hall [abh] studied exact recovery in the logarithmic degree setting $G(n,a\log n/n,b\log n/n)$ and showed that it is efficiently possible to recover the two communities exactly if $(\sqrt{a}-\sqrt{b})^{2}>2$ and information-theoretically impossible if $(\sqrt{a}-\sqrt{b})^{2}<2$. Abbe and Sandon [as] gave a precise characterization of when exact recovery is possible in the general stochastic block model for more than two communities with arbitrary relative sizes and arbitrary connection probabilities.

2 Semirandom Models

This abundance of sharp thresholds begs a natural question: how robust are these reconstruction thresholds? It is clear that if one substantially changes the distributional model, the thresholds themselves are likely to change. However there is a subtler issue. The algorithms that achieve these thresholds may in principle be over-fitting to a particular distributional model. Random graphs are well-known [alon-spencer] to have rigid properties, such as sharp laws for the distribution of subgraph counts and a predictable distribution of eigenvalues. Real-world graphs do not have such properties.

In a remarkable paper, Blum and Spencer [bs] introduced the semirandom model as an intermediary between average-case and worst-case analysis, to address such issues. The details of the model vary depending on the particular optimization problem, and since we will focus on clustering we will be most interested in the variant used by Feige and Kilian [fk].

Semirandom Model for Community Detection: [fk] • Sample a ‘precursor’ graph ${G_{\text{pre}}}$ from $G(n,a/n,b/n)$. • A monotone ‘adversary’ observes ${G_{\text{pre}}}$ along with the hidden community structure, and can delete any number of edges crossing between the two communities, and add any number of edges with each community. • Output the resulting graph $G$.

The adversary above is called ‘monotone’ because it is restricted to making changes that seem to be helpful. It can only strengthen ties within each community, and break ties between them.This is the reason we require $a>b$. If we had $b>a$ we could define the adversary in the opposite way (which we analyze in Appendix D). The key is that a monotone adversary can break the sorts of rigid structures that arise in random graphs, such as predictable degree distributions and subgraph counts. An algorithm that works in a semirandom model can no longer rely on these properties. Instead of a graph containing only random edges, all we are assured of is that it contains some random edges.

In this paper, we use semirandom models as our notion of ‘robustness.’ Many forms of robustness exist in the literature – for example, the independent work [mmv-robust] gives algorithms that are robust to $o(n)$ non-monotone changes in addition to monotone changes. With most robustness models, any algorithm will break down after enough errors, and one can compare algorithms based on how many errors they can tolerate. In contrast, semirandom models distinguish between algorithms qualitatively: as we will see, entire classes of algorithms continue to work under any number of monotone changes, while others do not.

Feige and Kilian [fk] showed that semidefinite programs for exact recovery in the stochastic block model continue to work in the semirandom model — in fact they succeed up to the threshold for the random model [hwx]. Since then, there have been many further developments including algorithms that work in semirandom models for planted clique [fkr], unique games [kmm], various graph partitioning problems [mmv], correlation clustering [msc, mmv15] and the general planted partition modelIn the general planted partition model, we have $Q_{ii}=a/n$ for all $i$ and $Q_{ij}=b/n$ for all $i\neq j$, with $a>b$, but the number of communities and their relative sizes are arbitrary constants. [pw] (and in some cases for even more powerful adversaries). A common theme is that if you have a semidefinite program that works in some stochastic setting, then it often extends almost automatically to the semirandom setting. So are there semidefinite programs that achieve the same sharp partial recovery results as Mossel, Neeman and Sly [mns2] and Massoulié [massoulie], and that extend to the semirandom model too? Or is there a genuine gap between what is achievable in the random vs. the semirandom setting?

3 Our Results

Recall that in the semirandom block model, a monotone adversary observes a sample from the stochastic block model and is then allowed to add edges within each community and delete edges that cross between communities. We will design a particularly simple adversary to prevent an algorithm from utilizing the paths of length two that go from a ‘$+$’ node to a ‘$-$’ node and back to a ‘$+$’ node, where the middle node has degree two. Our adversary will delete any such path it finds (with some additional technical conditions to locally coordinate these modifications), and our main result is that, surprisingly, this simple modification strictly changes the partial recovery threshold. We will state our bounds in terms of the average degree $k=\frac{a+b}{2}$ and ‘noise’ $\varepsilon=\frac{b}{a+b}\in[0,\frac{1}{2})$, in which case the threshold $(a-b)^{2}>2(a+b)$ becomes $k(1-2\varepsilon)^{2}>1$. Note that this threshold requires $k>1$. Then:

For any $k>1$, there exists $0<\varepsilon<\frac{1}{2}$ so that $k(1-2\varepsilon)^{2}>1$ and hence partial recovery in the stochastic block model $G(n,a/n,b/n)$ is possible, and yet there is a monotone adversary so that partial recovery in the semirandom model is information-theoretically impossible.

A common tool in the algorithms of Mossel, Neeman and Sly [mns2] and of Massoulié [massoulie] is the use of non-backtracking walks and spectral bounds for their transition matrices. Our adversary explicitly deletes a significant number of these walks. This simple modification not only defeats these particular algorithms, but we can show that no algorithm can achieve partial recovery up to the threshold $k(1-2\varepsilon)^{2}>1$. To the best of our knowledge, this is the first explicit separation between what is possible in the random model vs. the semirandom model, for any problem with a monotone adversary.

We show a complementary result, that no monotone adversary can make the problem too much harder. Various semidefinite programs have been designed for partial recovery. These algorithms work in the constant-degree regime, but are not known to work all the way down to the information-theoretic threshold. In particular, we follow Guédon and Vershynin [GV] and show that their analysis (with a simple modification) works as is for the semirandom model. This shows that semidefinite programs not only give rise to algorithms that work for the semirandom model in the exact recovery setting, but also for partial recovery too under some fairly general conditions.

Let $k=\frac{a+b}{2}$ and $\varepsilon=\frac{b}{a+b}<\frac{1}{2}$. There is a constant $C>1$ so that if $a>20$ and $k(1-2\varepsilon)^{2}>C$ then partial recovery is possible in the semirandom block model. Moreover it can be solved in polynomial time.

Our robustness proof only applies to a particular form of SDP analysis. Given a different proof that the SDP succeeds in the random model for a larger range of parameters $k,\varepsilon$ than above, there would be no guarantee that the SDP also succeeds in the semirandom model for that range of parameters. Hence we cannot formally conclude that it is impossible for the SDP to reach the information-theoretic threshold in the random model, though our results are suggestive in this direction.

We remark that each possible monotone adversary yields a new distribution on planted community detection problems. Hence, we can think of the algorithm in the theorem above as one that performs almost as well as information-theoretically possible across an entire family of distributions, simultaneously. This is a major advantage to algorithms based on semidefinite programming, and points to an interesting new direction in statistics. Can we move beyond average-case analysis? Can we find robust, semirandom analogues to some of the classical, average-case thresholds in statistics? The above two theorems establish upper and lower bounds for this semirandom threshold, that show that it is genuinely different from the average-case threshold. The usual notion of a threshold makes sense when we have exact knowledge of the process generating the instances we wish to solve. But when we lack this knowledge, semirandom models offer an avenue for exploration that can lead to new algorithmic and statistical questions.

Along the way to proving our main theorem, we show a random vs. semirandom separation for the broadcast tree model too. We define this model in Section 2.1. In short, it is a stochastic process in which each node is given one of two labels and gives birth to $\operatorname{Pois}(a/2)$ nodes of the same label and $\operatorname{Pois}(b/2)$ nodes of the different label, with the goal being to guess the label of the root given the labels of the leaves. There are many ways we could define a monotone adversary, and we focus on a particularly weak one that is only allowed to cut edges between nodes with different labels. We call this the cutting adversary, and we prove:

For any $k>1$, there exists $0<\varepsilon<\frac{1}{2}$ so that $k(1-2\varepsilon)^{2}>1$ and hence partial recovery in the broadcast tree model is possible, and yet there is a monotone cutting adversary for which partial recovery in the semirandom broadcast tree model is information-theoretically impossible.

Furthermore we analyze the recursive majority algorithm and show that it is robust to an even more powerful class of monotone adversaries, which are allowed to entirely control the subtree at a node whose label is different than its parent. We call this a strong adversary, and we prove:

If $\frac{k}{\log k}(1-2\varepsilon)^{2}>1+o(1)$ and $\varepsilon<\frac{1}{2}$ then partial recovery in the broadcast tree model is possible, even with respect to a strong monotone adversary, where ‘$o(1)$’ is taken as $k\to\infty$.

These results highlight another well-studied model where the introduction of a monotone adversary strictly changes what is possible. Nevertheless there is an algorithm that succeeds across the entire range of distributions that arise from the action of a monotone adversary, simultaneously. Interestingly, our robustness results can also be seen as a justification for why practitioners use recursive majority at all. It has been known for some time that recursive majority does not achieve the Kesten–Stigum bound [mossel-recursive] — the threshold for reconstruction in the broadcast tree model — although taking the majority vote of the leaves does. The advantage of recursive majority is that it is robust to very powerful adversaries while majority is not, and this only becomes clear when studying these algorithms through semirandom models!

Models and Adversaries

Here we formally define the models we will be interested in, as well as the notion of partial recovery. Recall that $G(n,a/n,b/n)$ denotes the stochastic block model on two communities with $p_{1}=p_{2}=1/2$ so that the communities are roughly equal sized. We will encode community membership as a label $\sigma_{v}\in\{+1,-1\}$ on each node $v$. We will also refer to this as a spin, following the convention in statistical physics. This numeric representation has the advantage that we can ‘add’ spins in order to take the majority vote, and ‘multiply’ them to compute the relative spin between a pair of nodes. We will be interested in the sparse regime $a,b=\Theta(1)$ where the graph has constant average degree, and we will assume $a>b$.

Next, we formally define partial recovery in the stochastic block model. Throughout this paper will will be interested in how our algorithms perform as $n$ (number of nodes) goes to $\infty$. We say that an event holds a.a.s. (asymptotically almost surely) if it holds with probability $1-o(1)$ as $n\to\infty$. Similarly, we say that an event happens for a.a.e. (asymptotically almost every) $x$ if it holds with probability $1-o(1)$ over a random choice of $x$.

We say that an assignment of $\{+1,-1\}$ spins to the nodes achieves $\eta$-partial recovery if at least $\eta n$ of these spins match the true spins, or at least $\eta n$ match after a global flip of all the spins. Moreover, an algorithm that outputs a vector of spins $\widehat{\sigma}\in\{+1,-1\}^{n}$ (indexed by nodes) is said to achieve partial recovery and there exists $\eta>\frac{1}{2}$ such that $\widehat{\sigma}$ achieves $\eta$-partial recovery a.a.s. in the limit $n\to\infty$.

Next, we define the broadcast tree model (which we introduced informally earlier). The broadcast tree model is a stochastic process that starts with a single root node $\rho$ at level whose spin $\sigma_{\rho}\in\{+1,-1\}$ is chosen uniformly at random. Each node in turn gives birth to $\operatorname{Pois}(a/2)$ same-spin children and $\operatorname{Pois}(b/2)$ opposite-spin children, where $\operatorname{Pois}(c)$ is the Poisson distribution with expectation $c$. This process continues until level $R$ at which point it stops, and the nodes at level $R$ are called the leaves. (The nodes on level $\leq R-1$ that by chance do not give birth to any children are not considered leaves, even though they are leaves in the graph-theoretic sense.) An algorithm observes the spins at the leaf nodes and the topology of the tree, and the goal is to recover the root spin:

An algorithm that outputs a spin $\widehat{\sigma}_{\rho}$ is said to achieve partial recovery on the tree if there exists $\eta>\frac{1}{2}$ such that $\widehat{\sigma}_{\rho}=\sigma_{\rho}$ with probability at least $\eta$, as $R\to\infty$.

The reparameterization in terms of $(k,\varepsilon)$ becomes particularly convenient here: each node gives birth to $\operatorname{Pois}(k)$ children, so $k=\frac{a+b}{2}$ is the average branching factor. Moreover, each child has probability $\varepsilon=\frac{b}{a+b}$ of having spin opposite to that of its parent.

It is known that taking the majority vote of the leaves is optimal in theory, in the sense that it achieves partial recovery for $k(1-2\varepsilon)^{2}>1$ [kesten-stigum] and that for $k(1-2\varepsilon)^{2}\leq 1$, partial recovery is information-theoretically impossible [evans]. This is called the Kesten–Stigum bound, and it can also be interpreted as a condition on the second-largest eigenvalue of an appropriately defined transition matrix. There are many other natural variants of the broadcast tree model, that are more general instances of multi-type branching processes. However, even for simple extensions, the precise information-theoretic threshold is still unknown. In the Potts model, where nodes are labeled with one of $q$ labels, Sly [sly-potts] showed that the Kesten–Stigum bound is not tight, as predicted by Mézard and Montanari [mezard-montanari-reconstruction]. And for an asymmetric extension of the binary model above, Borgs et al. [borgs-asymmetric] showed that the Kesten–Stigum bound is tight for some settings of the parameters. In our setting, this historical context presents a substantial complication because if we apply a monotone adversary to a broadcast tree model and it results in a complex propagation rule, there may not be good tools to prove that partial recovery is impossible.

2 Discussion

There is a close connection between the stochastic block model and the broadcast tree model, since the local neighborhood of any vertex in the graph is locally tree-like. Hence, if our goal is to prove a random vs. semirandom gap for community detection, a natural starting point is to establish such a gap for the broadcast tree model. It turns out that there is more than one natural way to define a monotone adversary for the broadcast tree model, but it will not be too difficult to establish lower bounds for either of them. The more difficult task is in finding an adversary that can plausibly be coupled to a corresponding adversary in the stochastic block model, and this will require us to put many sorts of constraints on the type of adversary that we should use to obtain a separation for the broadcast tree model.

In the broadcast tree model, we will work with two notions of a monotone adversary. One is weak and will be used to show our separation results:

Cutting Semirandom Model for Broadcast Tree: • Sample a ‘precursor’ broadcast tree ${T_{\text{pre}}}$ from the broadcast tree model. • The monotone cutting ‘adversary’ can delete any number of edges between nodes of different labels, thus removing subtrees. • Output the resulting tree $T$. (The removed subtrees are not revealed.)

Our other adversary is stronger, and we will establish upper bounds against this adversary (with the recursive majority algorithm) to give a strong recoverability guarantee:

Strong Semirandom Model for Broadcast Tree: • Sample a ‘precursor’ broadcast tree ${T_{\text{pre}}}$ from the broadcast tree model. • Whenever a child has the opposite label from its parent, the strong monotone ‘adversary’ can replace the entire subtree, starting from the child, with a different subtree (topology and labels) of its choice. • Output the resulting tree $T$.

An upper bound against this latter model amounts to a recovery guarantee without any assumptions as to what happens after a ‘mutation’ of labels — for example, a genetic mutation might affect reproductive fitness and change the birth rule for the topology. Other variants of monotone adversaries could also be justified.

It is helpful to first see how adversaries in these models might break existing algorithms. Recall that in the broadcast tree model, taking the majority vote of the leaves yields an algorithm that works up to the Kesten–Stigum bound, and this is optimal since reconstruction is impossible beyond this. In the language of $k$ and $\varepsilon$, each node gives birth to $\operatorname{Pois}(k(1-\varepsilon))$ nodes of the same label and $\operatorname{Pois}(k\varepsilon)$ nodes of the opposite label. Hence in a depth $R$ tree we expect $k^{R}$ leaves, but the total bias of the spins can be recursively computed as $k^{R}(1-2\varepsilon)^{R}$. The fact that majority works can be proven by applying the second moment method and comparing the bias to its variance.

However, an overwhelming number of the leaves are on some path that has a flip in the label at some point: we only expect $k^{R}(1-\varepsilon)^{R}$ nodes with all-root-spin ancestry, a vanishing proportion as $R\to\infty$. The strong monotone adversary has control over all the rest, and can easily break the majority vote. Even the monotone cutting adversary can control the majority vote, by cutting leaves whose spin matches the root but whose parents have the opposite label. This happens for a constant fraction of the leaf nodes, and this change overwhelms the majority vote. So majority vote fails against the semirandom model, for all nontrivial $k$ and $\varepsilon$.

This is an instructive example, but we emphasize that breaking one algorithm does not yield a lower bound. For example, if the algorithm knew what the adversary were doing, it could potentially infer information about where the adversary has cut edges based on the degree profile, and could use this to guess the label of the root.

The Problem of Orientation

Many first attempts at a separation in the broadcast tree model (which work!) rely on knowing the label of the root. However, such adversaries present a major difficulty in coupling them to a corresponding adversary in the graph. Each graph gives rise to many overlapping broadcast trees (the local neighborhood of each vertex) and a graph adversary needs to simultaneously make all of these tree reconstruction problems harder. This means a graph adversary cannot focus on trying to hide the spin of a specific tree root; rather, it should act in a local, orientation-free way that inhibits the propagation of information in all directions.

A promising approach is to look for nodes $v$ whose neighbors in ${G_{\text{pre}}}$ all have the opposite label, and cut all of these edges. Such nodes serve only to further inter-connect each community, and cutting their edges would seem to make community detection strictly harder. In the corresponding broadcast tree model, these nodes $v$ represent flips in the label that are entirely corrected back, and deleting them penalizes any sort of over-reliance on distributional flukes in how errors propagate. For example, majority reconstruction in the tree fully relies on predictable tail events whereby nodes with label different from the root may lead to subtrees voting in the correct direction nonetheless.

The Problem of Dependence

Now, however, a different sort of problem arises: if we were to naively apply the adversary described above to a broadcast tree, this would introduce complicated distance-$2$ dependencies in the distribution of observed spins, as certain diameter-$2$ spin patterns are banned in the observed tree (as they would have been cut). In particular, the resulting distribution is no longer a Markov random field. This is not inherently a problem, in that we could still hope to prove stronger lower bounds for such models beyond the Kesten–Stigum bound. However, the difficulty is that even for quite simple models on a tree (e.g. the Potts model [sly-potts], asymmetric binary channels [borgs-asymmetric]) the threshold is not known, and the lower bound techniques that establish the Kesten–Stigum bound seem to break down.

An alternative is to specifically look for degree-$2$ nodes $v$ whose neighbors in ${G_{\text{pre}}}$ have the opposite label, and cut both incident edges. Although there are still issues about making this a Markov random field, we can alleviate them by adding a $3$-clique potential on each degree-$2$ node and its two neighbors. Then after we marginalize out the label of the degree-$2$ node, the $3$-clique potential becomes a $2$-clique potential, and we return to a Markov random field over a tree! In other words, if we ignore the spin on a degree-2 node and treat its two incident edges like a single edge, we return to a well-behaved spin propagation rule.

3 Our Adversary

We are now ready to describe the adversary that we will use to prove Theorems 1.2 and 1.4. We only need two additional adjustments beyond the discussion above. Instead of making every possible degree-$2$ cutting move as described earlier, we will only cut with probability $\delta$. We will tune $\delta$ to ensure that the monotone changes we make do not overshoot and accidentally reveal more information about the underlying communities by cutting in too predictable a fashion. Finally, our adversary adds local restrictions to where and how it cuts, to ensure that the changes it makes do not overlap or interfere with each other (e.g. chains of degree-$2$ nodes). These details will not be especially relevant until Section 5, where they simplify the combinatorics of guessing the original precursor graph from the observed graph.

Let $(a,b,n)$ be given. Write $k=\frac{a+b}{2}$ and $\varepsilon=\frac{b}{a+b}$. We sample a ‘precursor’ graph ${G_{\text{pre}}}\sim G(n,a/n,b/n)$, and apply the following adversary:

Adversary: • If at least $3$ neighbors of a vertex $v$ have degree not equal to $2$, mark $v$ good. • If a degree-$2$ vertex has both of its neighbors marked good, mark it tagged. • For each tagged node $v$ whose two neighbors $w_{1}$, $w_{2}$ both have opposite label to $v$: with probability $\delta$, delete both edges $(v,w_{1})$ and $(v,w_{2})$ (otherwise keep both edges) where \delta\triangleq\begin{cases}1&\text{if\varepsilon\leq\frac{1}{3}},\\ \frac{(1-2\varepsilon)^{2}}{\varepsilon^{2}}&\text{if\varepsilon\geq\frac{1}{3}.}\end{cases} (1)

We can now outline the proof of our main theorem. In order to show that partial recovery is impossible, it suffices to show that it is impossible to reconstruct the relative spin (same or different) of two random nodes $u$ and $v$, better than random guessing. Before applying the adversary, an $O(\log n)$-radius neighborhood $U$ around $u$ resembles the broadcast tree model rooted at $u$. After the adversary is applied to the graph, $U$ resembles a broadcast tree model with a corresponding cutting adversary applied. This resemblance will be made precise by the coupling argument of Section 3; there will be some complications in this, and our tree will not be uniformly the same depth but will have a serrated boundary.

We show in Section 4 that when the cutting adversary is applied to the tree, the tree reconstruction problem (guess the spin of $u$ from the spins on the boundary of $U$) becomes strictly harder: the average branching factor becomes lower due to sufficient cutting, while the new spin propagation rule resembles classical noisy propagation with at least as much noise (so long as we marginalize out the spins of tagged nodes). We then apply the proof technique of Evans et al. [evans] to complete the tree lower bound.

A natural open question is whether one can find the optimal monotone adversary. For instance, we have not even used the power to add edges within communities. Note however, that our current adversary is delicately constructed in order to make each step of the proof tractable. It is not too hard to propose alternative adversaries that seem stronger, but it is likely that one of the major steps in the proof (tree lower bound or no long-range correlations) will become prohibitively complicated. Recent predictions on the performance of SDP methods [jm-phase] could be suggestive of the true semirandom threshold.

Coupling of Graph and Tree Models

It is well-known that sparse, random graphs are locally tree-like with very few short cycles. This is the basis of Mossel–Neeman–Sly’s approach in coupling between a local neighborhood of the stochastic block model and the broadcast tree model [mns]. Hence, our first order of business will be to couple a typical neighborhood from our graph distribution (Distribution 2.3) to the following tree model, against which we can hope to show lower bounds.

Given the parameters $(a,b,R)$, generate a tree $T$ with spins $\sigma$ as follows:

Start with a root vertex $\rho$, with spin $\sigma_{\rho}$ chosen uniformly at random from $\pm 1$.

Until a uniform depth $R+3$ (where the root is considered depth 0), let each vertex $v$ give birth to $\operatorname{Pois}(a/2)$ children of the same spin and $\operatorname{Pois}(b/2)$ children of opposite spin.

Apply the graph adversary (from Distribution 2.3) to this tree; this involves assigning markings good and tagged, and cutting some tagged nodes. Keep only the connected component of the root.

Remove all nodes of depth greater than $R$ (the bottom $3$ levels).

Remove any tagged node at depth $R$ along with its siblings, exposing the parent as a leaf.

The reason we trim $3$ levels at the bottom is to ensure that the markings and cuttings in $T$ match those in $G$, since these depend on the radius-$3$ neighborhood of each node and edge, respectively. Removing tagged nodes at level $R$ will ensure that the more complicated spin interactions of tagged nodes and their neighbors do not span across the boundary of a tree neighborhood in the graph — we want to cleanly separate out a tree recovery problem. We use a slightly non-conventional definition of ‘leaves’:

When we refer to the leaves of a tree sampled from Distribution 3.1 we mean the nodes at depth $R$ plus any nodes at depth $R-1$ that are revealed during the last step. Nodes at depth $\leq R-1$ that happen to give birth to no children are not considered leaves; if the root is tagged and gets cut by the adversary so that the tree is a single node, this single node is not considered a leaf.

We can couple the above tree model to neighborhoods of the graph:

Let $(a,b,n)$ be given, and let $\rho_{G}$ be any vertex of the graph. Let

There exists a joint distribution $(G,\sigma_{G},T,\sigma_{T})$ such that the marginals on $(G,\sigma_{G})$ and $(T,\sigma_{T})$ match the graph and tree models, respectively, while with probability $1-o(1)$:

there exists an isomorphism (preserving edges, spins, and the markings good and tagged) between the tree $T$ and a vertex-subset $U$ of $G$,

the tree root corresponds to the vertex $\rho_{G}$ in the graph, and the leaves correspond to a vertex set $B$ that separates the interior $U\smallsetminus B$ from the rest of the graph $G\smallsetminus U$.

As proven in [mns], there exists a coupling between the precursor graph $({G_{\text{pre}}},\sigma_{G})$ and the precursor tree $({T_{\text{pre}}},\sigma_{T})$, such that ${T_{\text{pre}}}$ matches the radius $R+3$ neighborhood $U$ of $\rho_{G}$ in ${G_{\text{pre}}}$, which has size $O(n^{1/8})$; this fails with probability $o(1)$.

Next the adversary assigns vertex markings (good and tagged) to both models. The marking of each vertex is deterministic and only depends on the topology of the radius-$3$ neighborhood of the vertex. Thus the markings in ${G_{\text{pre}}}$ and ${T_{\text{pre}}}$ match up to radius $R$. Some tagged nodes are cuttable, i.e. both their neighbors have opposite spin; the cuttable nodes in ${G_{\text{pre}}}$ and ${T_{\text{pre}}}$ also match up to radius $R$. The adversary now cuts the edges incident to a random subset of cuttable vertices; we can trivially couple the random choices made on ${G_{\text{pre}}}$ with those on ${T_{\text{pre}}}$ up to radius $R$. We keep only the connected component of the root in $T$; likewise let us keep only the corresponding vertices in $U$, i.e. only those still connected to $\rho_{G}$ by a path in $U$.

After removing nodes of depth greater than $R$, we have removed the subset of $T$ for which the markings and the action of the adversary differ from those in $G$. Thus at this stage, the tree exactly matches the radius $R$ neighborhood of $\rho_{G}$ in $G$, along the isomorphism given by the coupling from [mns]. Any boundary vertex of this neighborhood must have distance exactly $R$ from $\rho_{G}$, thus its corresponding vertex in the tree has depth $R$ and is a leaf. Passing to the final step of removing tagged leaves in $T$ and their siblings, we remove their corresponding nodes from $U$; this does not change the boundary-to-leaves correspondence. ∎

Random vs. Semirandom Separation in the Tree Model

In this section we show that our tree distribution (Distribution 3.1) evidences a random vs. semirandom separation in the broadcast tree model. Recall that the goal is to recover the spin of the root from the spins on the leaves, given full knowledge of the tree topology and the node markings (good and tagged). Recall the non-conventional definition of ‘leaves’ (Definition 3.2).

Let $\Delta=\Delta(a,b,R)$ be the advantage over random guessing, defined such that $\frac{1+\Delta}{2}$ is the probability that the optimal estimator (maximum likelihood) succeeds at the above task. We will show that our tree model is asymptotically infeasible $(\Delta\to 0$ as $R\to\infty$) for a strictly larger range of parameters $(a,b)$ than that of the corresponding random model.

For every real number $k>1$, there exists $0<\varepsilon<\frac{1}{2}$ such that $k(1-2\varepsilon)^{2}>1$, yet for a tree sampled from Distribution 3.1 with parameters $a=2k(1-\varepsilon)$, $b=2k\varepsilon$ and depth $R$, we have $\Delta(a,b,R)\to 0$ as $R\to\infty$.

Recall that the condition $k(1-2\varepsilon)^{2}>1$ is the classical Kesten–Stigum bound, which is sufficient to beat random guessing in the random model [kesten-stigum]. Several decades later, this bound was found to be tight for the random model [evans]. There remain many open questions regarding the hardness of tree models, and some care was required in crafting an adversary for this problem that keeps the proof of this lower bound tractable.

Broadly, the Kesten–Stigum bound asserts that recoverability depends on the average branching factor (a contribution from the tree topology) and the amount of noise (a contribution from the spin propagation rule). The first step of our proof is to distinguish these in our distribution: we can first generate a tree topology from the appropriate marginal distribution, and then sample spins from the conditional distribution given this tree. We will show how to view this distribution on spins within the lower bound framework of [evans]. Moreover, the new spin propagation rule is at least as noisy as the original, while our cutting adversary has strictly decreased the average branching factor.

We first re-state our tree model in terms of topology generation followed by spin propagation. Instead of letting each node give birth to $\operatorname{Pois}(a/2)$ same-spin children and $\operatorname{Pois}(b/2)$ opposite-spin children, we can equivalently let each node $v$ give birth to $\operatorname{Pois}(k)$ children and then independently choose the spin of each child to be the same as $v$ with probability $1-\varepsilon$ and opposite to $v$ otherwise. (The equivalence of these steps is often known as ‘Poissonization’.) Here the correspondence between $(a,b)$ and $(k,\varepsilon)$ is as usual: $k=\frac{a+b}{2}$ and $\varepsilon=\frac{b}{a+b}$. This allows us to first sample the entire tree topology without spins. Then we can add markings (good and tagged), since these depend only on the topology. Next, we sample the spins as above, by generating an appropriate independent $\pm 1$ value $f_{e}$ on each edge, indicating whether or not a sign flip occurs across that edge. Finally, we cut edges according to the adversary’s rule.

Given the parameters $(a,b,R)$, generate a tree $T$ with spins $\sigma$ as follows:

Start with a root vertex $\rho$. Until a uniform depth $R+3$, let each vertex $v$ give birth to $\operatorname{Pois}(k)$ nodes.

Mark nodes as good and tagged according to the rules of the graph adversary.

For each edge $e$, generate an independent flip value $f_{e}$ which is $+1$ with probability $1-\varepsilon$ and $-1$ otherwise.

Choose the root spin $\sigma_{\rho}$ uniformly from $\pm 1$. Propagate spins down the tree, letting $\sigma_{v}=\sigma_{u}f_{e}$ where $e$ is the edge connecting $v$ to its parent $u$.

Cut edges according to the adversary’s rule, keeping only the connected component of the root.

Trim the bottom of the tree (according to the last two steps of Distribution 3.1).

It is clear that this tree distribution (Distribution 4.2) is identical to the original tree distribution (Distribution 3.1). Our next step will be to re-state this model in yet another equivalent way. The goal now is to sample the final tree topology (including which edges get cut) before sampling the spins. Consider a tagged node $v$, its parent $u$, and its single child $w$. Instead of writing the spin propagation as independent flips $f_{(u,v)}$ and $f_{(v,w)}$, we will write it as random variables $c_{v}$ and $f_{v}$. Here $c_{v}$ is equal to 1 if the adversary decides to cut $v$ (and 0 otherwise), and $f_{v}$ is equal to 1 if $\sigma_{u}=\sigma_{w}$ (and $-1$ otherwise). This means if $f_{(u,v)}=f_{(v,w)}=1$ then $c_{v}$ is 1 with probability $\delta$ (and 0 otherwise); and if we do not have $f_{(u,v)}=f_{(v,w)}=1$ then $c_{v}=0$. Hence $c_{v}=1$ with probability $\varepsilon^{2}\delta$. If $c_{v}=1$ then $f_{v}$ is irrelevant because the adversary will cut $v$ from the tree. Conditioned on $c_{v}=0$, $f_{v}$ takes the value $+1$ with probability $\frac{(1-\varepsilon)^{2}+\varepsilon^{2}(1-\delta)}{1-\varepsilon^{2}\delta}$ and $-1$ otherwise. This means that for a tagged (but not cut) node $v$, the joint distribution of $(\sigma_{u},\sigma_{w})$ obeys a propagation rule that is equivalent to putting noise $\varepsilon^{\prime}$ (instead of $\varepsilon$) on edges $(u,v)$ and $(v,w)$, where (using the definition of $\delta$)

One can verify that $\varepsilon<\varepsilon^{\prime}\leq\frac{1}{2}$ for all $\varepsilon\in(0,\frac{1}{2})$. For most tagged nodes in the tree, we are simply going to replace $\varepsilon$ by $\varepsilon^{\prime}$ on the incident edges, which gives the correct joint distribution of $(\sigma_{u},\sigma_{w})$ but not the correct joint distribution of $(\sigma_{u},\sigma_{v},\sigma_{w})$. This is acceptable because the distribution of leaf spins (given the root spin) is still correct; for this reason we have made sure that none of the leaves are tagged nodes. The only time when we actually care about the spin of a tagged node is in the case where the root $\rho$ is tagged. In this case, the root might be cut by the adversary, yielding a 1-node tree (with no revealed leaves). Otherwise, if the root is tagged but not cut, our spin propagation rule needs to sample the spins of the root’s two children (a tagged node that is not cut must have degree $2$) from the appropriate joint distribution over $\{\pm 1\}^{2}$; let $\mathcal{D}^{+}$ denote this distribution, conditioned on $\sigma_{\rho}=+1$. It will not be important to compute $\mathcal{D}^{+}$ explicitly (although it is straightforward to do so). We are now ready to state the next tree model. This model is equivalent to the previous ones in that the joint distribution of the root spin, topology, markings, and leaf spins is the same. The spins on the tagged nodes (other than the root) do not have the same distribution as before, but this is irrelevant to the question of recovering the root from the leaves.

Given the parameters $(a,b,R)$, generate a tree $T$ with spins $\sigma$ as follows:

Start with a root vertex $\rho$. Until a uniform depth $R+3$, let each vertex $v$ give birth to $\operatorname{Pois}(k)$ nodes.

Mark nodes as good and tagged according to the rules of the graph adversary.

Decide which nodes the adversary should cut: cut each tagged node independently with probability $\varepsilon^{2}\delta$.

Let $\varepsilon_{e}=\varepsilon^{\prime}$ for edges $e$ that are incident to a tagged node, and let $\varepsilon_{e}=\varepsilon$ for all other edges.

For each edge $e$, generate an independent flip value $f_{e}$ which is $+1$ with probability $1-\varepsilon_{e}$ and $-1$ otherwise.

Choose the root spin $\sigma_{\rho}$ uniformly from $\pm 1$. If the root is tagged but not isolated: let $u_{1},u_{2}$ be its children, draw $(d_{1},d_{2})\sim\mathcal{D}^{+}$, and let $\sigma_{u_{1}}=d_{1}\sigma_{\rho}$, $\sigma_{u_{2}}=d_{2}\sigma_{\rho}$. For all other nodes, propagate spins down the tree as usual, letting $\sigma_{v}=\sigma_{u}f_{e}$ where $e$ is the edge connecting $v$ to its parent $u$.

Trim the bottom of the tree (according to the last two steps of Distribution 3.1).

Our next step is to further modify this tree model in ways that only make it easier, in the sense that the advantage $\Delta(a,b,R)$ can only increase. First, we will address the issue of the complicated propagation rule $\mathcal{D}^{+}$ in the case that the root is tagged. Suppose the root is tagged (but not cut) and consider deterministically setting $\sigma_{u_{1}}=\sigma_{u_{2}}=\sigma_{\rho}$ where $u_{1},u_{2}$ are the root’s two children. From there, spin propagation continues as usual. We claim that this new model can only be easier than the original one. To see this, note that the new model can ‘simulate’ the original one: upon observing leaf spins drawn from the new model, drawn $(d_{1},d_{2})\sim\mathcal{D}^{+}$ and then, for each $i\in\{1,2\}$ and for each leaf $w$ descended from $u_{i}$, replace $\sigma_{w}$ by $d_{i}\sigma_{w}$. For convenience we will also replace the first level of the tree by deterministic zero-noise propagation in the case where the root is not tagged. We can similarly argue that the model only gets easier, since one can simulate the old model using the new model by sampling the noise on the first level.

Note that we now have a tree model such that once the topology is chosen, the spin-propagation rule is very simple: at each edge $e$, a sign flip occurs independently with some probability $\varepsilon_{e}\in\{\varepsilon,\varepsilon^{\prime},0\}$. Hardness results for such a tree model were studied by Evans et al., who established the following bound on the advantage $\Delta_{T}$ for a fixed tree topology $T$ ([evans] Theorem 1.3’):

Our goal is to show $\Delta\to 0$ (as $R\to\infty$), so it is sufficient to show $W\to 0$. Any leaf in our tree is at height $\geq R-1$. Furthermore we have $\varepsilon_{e}=0$ for edges incident to the root and $\varepsilon\leq\varepsilon_{e}\leq\frac{1}{2}$ elsewhere. Therefore, for any leaf $v$, we can bound $\Theta_{v}\leq(1-2\varepsilon)^{R-2}$. Note that we have not actually used the fact that $\varepsilon^{\prime}$ strictly exceeds $\varepsilon$; we will in fact be able to prove our result by leveraging only the decrease in branching factor and not the noise increase. Now we have

and so we need only to bound the expected number of leaves. For $i=0,\ldots,R$, let level $i$ denote the set of vertices at distance $i$ from the root (so the root is on level 0). Call levels $1,7,\ldots,6j+1,\ldots$ the base levels and call levels $4,10,\ldots,6j-2,\ldots$ the cutting levels. Imagine growing the tree using $\operatorname{Pois}(k)$ births as usual, and marking nodes as good and tagged as usual. Now allow the adversary to cut vertices as usual, except refuse to cut any tagged node that is not on a cutting level. Note that this can only result in more leaves, and so this new process will give an upper bound on the expected number of leaves in our actual model.

Hence this inequality suffices for impossibility of recovery.

However, $k^{\prime}$ depends on the topology of the final tree model, which depends on $k$, $\varepsilon$, and $\delta$, so this inequality is slightly more complicated than it looks. We write $k^{\prime}(k,\varepsilon)$ to make this dependence explicit; recall that $\delta$ is a (continuous) function of $\varepsilon$. We argued above that $k^{\prime}(k,\varepsilon)<k$ for all $0\leq\varepsilon\leq\frac{1}{2}$. In particular, at the critical value $\varepsilon_{\text{crit}}=\frac{1}{2}(1-\frac{1}{\sqrt{k}})$ for the random model, we have

But $k^{\prime}(k,\varepsilon)(1-2\varepsilon)^{2}$ is a continuous function of $\varepsilon$, so if we take $\varepsilon$ to be slightly less than $\varepsilon_{\text{crit}}$, we must still have $k^{\prime}(k,\varepsilon)(1-2\varepsilon)^{2}<1$, while $k(1-2\varepsilon)^{2}>1$, as desired. ∎

This completes the proof of Theorem 1.4 (semirandom vs. random separation on trees). In Appendix A, we explicitly compute a lower bound on the separation $k^{6}-k^{\prime}(k,\varepsilon)^{6}$.

No Long-Range Correlations

The lower bound of the previous section will form the core of a lower bound for the graph: we have already established that, for a large range of parameters, it is impossible to learn the spin of a node $u$ purely from the spins at the boundary $B$ of its tree-like local neighborhood. We will now see why this makes recovery in the graph impossible: there is almost nothing else to learn about $\sigma_{u}$ from beyond its local neighborhood once we know the spins on $B$.

Let a graph $G$ (including markings good and tagged) and spins $\sigma$ be drawn from Distribution 2.3. Let $A=A(G)$, $B=B(G)$, $C=C(G)$ be a vertex-partition of $G$ such that

$B$ separates $A$ from $C$ in $G$ (no edges between $A$ and $C$),

Here $\sigma_{A}$ denotes the spins on $A$ and $\sigma_{BC}$ denotes the spins on $B\cup C$.

To clarify, when we refer to good or tagged nodes in $G$ we are referring to the original markings that they were assigned in ${G_{\text{pre}}}$. For instance, if a tagged node is cut by the adversary, it is still considered tagged in $G$ even though it no longer has degree $2$. Recall that the markings (good and tagged) in $G$ are revealed to the reconstruction algorithm.

In Lemma 5.1, we do crucially use that $B$ does not contain tagged nodes: if a node in $B$ were tagged with spin $+1$, and we then revealed that its neighbor in $C$ has spin $-1$, this would strengthen our belief that the neighbor in $A$ has spin $+1$, as otherwise the tagged node would have some substantial probability of having been cut, which is observed not to be the case. So Lemma 5.1 would be false if we allowed tagged nodes in $B$.

The proof of Lemma 5.1 will require a thorough understanding of the distribution of spins given $G$, which we can only obtain by understanding the possible precursors of $G$ under the adversary. The reason for the good and tagged nodes in our adversary construction is to make these precursors well-behaved. We start with some simple observations. Let ${G_{\text{pre}}}$ be a graph that yields $G$ (with nonzero probability) by application of the adversary.

A good node has degree at least $3$ in $G$.

A good node has at least three non-degree-$2$ neighbors in ${G_{\text{pre}}}$ and the adversary will not remove these. ∎

The adversary does not create any new degree-$2$ nodes. In other words, if a node has degree $2$ in $G$ then it has degree $2$ in ${G_{\text{pre}}}$ (with the same two neighbors).

In order to create a degree-$2$ node $v$, the adversary must cut at least one edge incident to $v$. This can only happen if $v$ is either tagged or good. It cannot be tagged because it does not have degree $2$ in ${G_{\text{pre}}}$. But it also cannot be good or else it has degree at least 3 in $G$ (by Observation 5.2). ∎

The key property of the good/tagged construction is that the adversary cannot change whether or not a node has the following ‘goodness’ property.

Say that a node has the goodness property with respect to a graph if at least three of its neighbors do not have degree $2$.

The good nodes are precisely the nodes that have the goodness property with respect to $G$.

Note that this is not tautological because the good nodes are defined as the nodes that have the goodness property with respect to ${G_{\text{pre}}}$, not $G$.

We need to show that the goodness property is invariant under the adversary’s action. First we assume $v$ has goodness in ${G_{\text{pre}}}$ and show that it also has goodness in $G$. Since $v$ has the goodness property in ${G_{\text{pre}}}$, it has three neighbors $u_{1},u_{2},u_{3}$ in ${G_{\text{pre}}}$ that do not have degree $2$. Each $u_{i}$ remains connected to $v$ in $G$ since the adversary only cuts edges that are incident to a degree-$2$ node. Furthermore, each $u_{i}$ does not have degree $2$ in $G$ because degree-$2$ nodes cannot be created (Observation 5.3).

Now we show the converse: assume $v$ does not have goodness in ${G_{\text{pre}}}$ and show that it still does not have goodness in $G$. The only way that $v$ could obtain goodness is if at least one of its degree-$2$ neighbors $u$ becomes non-degree-$2$ (while remaining connected to $v$). But this is impossible because whenever the adversary cuts an edge incident to a degree-2 vertex $u$, it causes $u$ to become isolated in $G$. ∎

Next we state an easy fact about the structure of tagged nodes in $G$.

The tagged nodes in $G$ are precisely the degree-$2$ nodes with two good neighbors, plus some isolated nodes.

Every tagged node in ${G_{\text{pre}}}$ has degree-$2$ with two good neighbors. If the node is cut, it becomes isolated in $G$; otherwise it remains degree-$2$ with two good neighbors. Conversely, let $v$ be degree-$2$ in $G$ with two good neighbors; we will show $v$ is tagged. Since degree-$2$ nodes cannot be created (Observation 5.3), $v$ has degree-$2$ in ${G_{\text{pre}}}$ with the same two good neighbors, and is therefore tagged. ∎

Now we are ready to characterize the possible precursors ${G_{\text{pre}}}$ of a given $G$.

Suppose we have a graph $G$ (including node markings) and spins $\sigma$, drawn from Distribution 2.3. The probability that a graph ${G_{\text{pre}}}$ yields $G$ under the action of the adversary is zero unless ${G_{\text{pre}}}$ can be obtained from $G$ by connecting each isolated tagged node $v$ of $G$ to exactly two good nodes of opposite spin to $v$. In this case, if $G$ has $m=m(G)$ isolated tagged nodes and $w=w(\sigma,G)$ tagged nodes with two opposite-spin neighbors, then

where we define $0^{0}=1$ in the case $\delta=1,w=0$.

Recall that $\delta$ is the probability with which the adversary cuts each ${\tt tagged}$ node that has two opposite-spin neighbors.

First suppose ${G_{\text{pre}}}$ can yield $G$ via the adversary. We will show that ${G_{\text{pre}}}$ takes the desired form. The nodes cut by the adversary are precisely the isolated tagged nodes of $G$. Every such node was originally connected to two opposite-spin good nodes in ${G_{\text{pre}}}$. Therefore ${G_{\text{pre}}}$ can be obtained from $G$ by connecting each isolated tagged node to exactly two opposite-spin good nodes. Conversely, let ${G_{\text{pre}}}$ be obtained from $G$ by connecting each isolated tagged node to exactly two opposite-spin good nodes. The good nodes in $G$ are (by Lemma 5.5) precisely the nodes that have the goodness property in $G$. These are also precisely the nodes that have the goodness property in ${G_{\text{pre}}}$, since the process of connecting each isolated tagged node to two good nodes does not change goodness. Consider running the adversary on ${G_{\text{pre}}}$. The nodes that it marks good will be precisely the good nodes in $G$. Also, the nodes that it marks tagged will be precisely the tagged nodes in $G$; this is clear from Lemma 5.6. This means the adversary will output $G$ iff it chooses to cut the $m$ tagged nodes that are isolated in $G$ and chooses not to cut the $w$ tagged nodes that have two opposite-spin neighbors in $G$. This happens with probability $(1-\delta)^{w}\delta^{m}$. ∎

2 Proof of No Long-Range Correlations

We proceed as follows. In the ordinary stochastic block model, given an observed graph, the probability of any set of spins $\sigma$ factorizes as a product of pairwise interactions. In our model, by summing over all possible precursors ${G_{\text{pre}}}$ that could have lead to $G$ via the adversary, we find the same pairwise interactions together with a further global, combinatorial interaction. We show that the neighborhood $A$ is too small to make a significant impact on this global interaction, while the pairwise interactions between $A$ and $C$ are weak, so that the only factors relevant to $A$ are the pairwise interactions within $A\cup B$, which are independent of the spins in $C$.

where $\sim$ denotes adjacency in the graph $H$.

To leverage this description, let us sum over all possible precursors ${G_{\text{pre}}}$ of $G$ under the adversary. Let $L(\sigma,G)$ denote the set of possible precursors ${G_{\text{pre}}}$ of $G$, as described by Lemma 5.7: ${G_{\text{pre}}}$ is obtained from $G$ by connecting each of the $m$ isolated tagged nodes to exactly two good nodes of the opposite spin.

The proportionality constant hidden by ‘$\propto$’ depends on $G$ but not on $\sigma$. As ${G_{\text{pre}}}$ is obtained from $G$ by replacing $2m$ opposite-spin non-edges by opposite-spin edges, we have for every ${G_{\text{pre}}}\in L(\sigma,G)$,

Thus none of the terms depend on the precise choice of ${G_{\text{pre}}}$:

where we have dropped the constants that only depend on $G$ (and not $\sigma$).

Now we compute $|L(\sigma,G)|$. Suppose there are $m/2+\alpha$ isolated tagged nodes of positive spin and $m/2-\alpha$ of negative spin. Suppose there are $g/2+\beta$ good nodes of positive spin, and $g/2-\beta$ of negative spin. Then the number of possible ${G_{\text{pre}}}$ is

We can establish that this global $L$ factor only barely depends on the spins of $A$:

For a.a.e. $G,\sigma_{B},\sigma_{C}$, it holds for all $\sigma_{A}$, $\sigma_{A}^{\prime}$ that

The proof proceeds via concentration of measure and Taylor expansion, and is deferred to Appendix B.

Paraphrasing this lemma, a.a.s. over $(\sigma_{B},G)$, there exists a ‘good’ subset of a.a.e. $\sigma_{C}$ such that $|L(\sigma,G)|$ is independent of $\sigma_{A}$ up to a $1+o(1)$ factor. Let us also require of ‘good’ $\sigma_{C}$ that the census (sum of spins) is $O(\sqrt{n}\log n)$; as $C$ consists of all but $O(n^{1/8})$ nodes of $G$, it is equivalent to ask for the same concentration over all spins of $G$, and this occurs a.a.s. by Hoeffding. Let $\Omega$ be this set of ‘good’ $\sigma_{C}$ values. Since $\sigma_{C}\in\Omega$ a.a.s. we have for any set $D=D(G)$ (which will be taken as either $A$ or $A\cup B$ below),

We include a rigorous proof of this statement in Appendix C.

It will be useful to factor the product $\Phi$ of classical pairwise interactions into subsets of these interactions as

Here, for instance, $Q_{BC,C}$ denotes the product of $\phi(\sigma_{u},\sigma_{v},G)$ over unordered pairs $u,v$ consisting of one vertex from $B\cup C$ and one from $C$. The corresponding “no long-range correlations” proof in [mns] established that for ‘good’ values $\sigma_{C}\in\Omega$, $Q_{A,C}(\sigma_{AC},G)=(1+o(1))K(G)$ for a quantity $K(G)$ depending only on $|A|$ and $|C|$. Their proof of this fact holds verbatim in our setting: it only requires that $|A|=o(n)$ and that the number of $+1$ spins in the graph is distributed as $\operatorname{Binom}(n,\frac{1}{2})$.

Similarly, we can factor the $(1-\delta)^{w}$ term as

where, for instance, $w_{A}$ counts the number of tagged nodes in $A$ with two opposite-spin neighbors. This factorization holds as there are no $A$–$C$ edges and no tagged nodes in $B$. We can now absorb these terms into the $Q$ terms: define

and similarly $Q^{\prime}_{BC,C}$, and $\Phi^{\prime}=Q^{\prime}_{AB,AB}Q^{\prime}_{BC,C}Q_{A,C}$, so that for $\sigma_{C}\in\Omega$,

At this point we roughly adapt the proof of conditional independence from factorization in a Markov random field, following the corresponding proof in [mns]. We compute that for a.a.e. $(\sigma,G)$,

Random vs. Semirandom Separation in the Block Model

We can now assemble all of the pieces to prove our main result. We first prove that it is impossible to estimate the relative spin of any fixed pair of nodes, in a strictly larger parameter range than for the random model. The impossibility of partial recovery will then easily follow.

For all $k>1$, there exists $0<\varepsilon<\frac{1}{2}$ such that $k(1-2\varepsilon)^{2}>1$, yet given a graph $G$ (including markings good/tagged) from Distribution 2.3 with parameters $a=2k(1-\varepsilon)$, $b=2k\varepsilon$, we have that for any fixed vertices $u,v$,

By ‘fixed’ vertices $u,v$ we mean that the vertices are fixed before $\sigma$ and $G$ are chosen; so by symmetry it doesn’t matter which $u,v$ pair we fix.

Given $k$, choose $\varepsilon$ as in Proposition 4.1 (tree separation). With probability $1-o(1)$, the tree coupling of Proposition 3.3 centered at vertex $u$ succeeds. In this case, the neighborhood $U$ of $u$ coupled to the tree is of size $O(n^{1/8})$, and so with probability $1-o(1)$, $v$ lies outside this neighborhood. Let $B$ be the boundary vertices of $U$, i.e. those vertices in $U$ corresponding to the leaves of the tree. Let $A$ be the interior $U\smallsetminus B$, and let $C$ be the complement of $U$ in $G$.

With further probability $1-o(1)$, Lemma 5.1 (no long-range correlations) succeeds, and we have

But it follows from the coupling in Proposition 3.3 (which includes spins and markings) that

Since $R\to\infty$ as $n\to\infty$, non-reconstruction in the tree model (Proposition 4.1) implies that this latter variance converges to $1$: the variance of a $\{\pm 1\}$-valued random variable with expectation $o(1)$ is $1-o(1)$.

So we know that, with probability $1-o(1)$, a $1-o(1)$ proportion of $\sigma_{BC}$ contribute a value $1-o(1)$ to the expectation in (4). The remaining $o(1)$ proportion of $\sigma_{BC}$ contribute a value bounded in magnitude by $1$, as the variance of a $\{\pm 1\}$-valued variable must be. It follows that, a.a.s.,

and the only way that this is possible in the $\{\pm 1\}$-valued distribution $\sigma_{u}\mid\sigma_{v},G$ is if

It will follow immediately from Proposition 6.1 that it is hard to find a partition that is correlated (better than random guessing) with the true one. For if it was possible to find such a partition then one could also guess the relative spins of $u$ and $v$. We now complete the proof of our main theorem, restating it slightly more precisely.

For any $k>1$, there exists $0<\varepsilon<\frac{1}{2}$ so that $k(1-2\varepsilon)^{2}>1$ and hence partial recovery in the stochastic block model $G(n,a/n,b/n)$ is possible, and yet against the monotone adversary given in Section 2, for any $\eta>\frac{1}{2}$, no estimator of the spins achieves $\eta$-partial recovery with probability greater than $o(1)$ as $n\to\infty$.

Let $\widehat{\sigma}$ be some assignment of spins to vertices that achieves $\eta$-partial recovery: $\widehat{\sigma}$ agrees with the true spins on at least $\eta n$ vertices, possibly after a global spin flip. Consider the relative spins $\widehat{\sigma}_{u}\widehat{\sigma}_{v}$, where $u$ and $v$ are distinct vertices; these match the true relative spins on at least

ordered pairs of distinct vertices. If we choose two distinct vertices at random, the chance of correctly estimating their relative spin from $\widehat{\sigma}$ is at least

Suppose for a contradiction that some estimator achieves $\eta$-partial recovery, for some $\eta>\frac{1}{2}$, with probability $p$ not converging to as $n\to\infty$. When $\eta$-partial recovery succeeds, the process above recovers the relative spin of two random vertices with probability at least $(1+o(1))(\eta^{2}+(1-\eta)^{2})$, and note $\eta^{2}+(1-\eta)^{2}>\frac{1}{2}$. When partial recovery does not succeed, the process still recovers the relative spin of two random vertices with probability at least $(1+o(1))\frac{1}{2}$, as can be seen by plugging in $\eta=\frac{1}{2}$ to (5). It follows that we can recover the relative spin of two random vertices with probability at least $(1+o(1))[p(\eta^{2}+(1-\eta)^{2})+(1-p)\frac{1}{2}]$ which remains bounded above $\frac{1}{2}$ as $n\to\infty$, contradicting Proposition 6.1. (Proposition 6.1 assumes the markings on $G$ are known, but clearly the problem is only harder when they are unknown, since an estimator can choose to ignore them.) ∎

Robustness of SDPs for Partial Recovery

We now turn to giving algorithms for partial recovery in the semirandom setting. In the existing literature on exact recovery, it has been observed that algorithms obtained through semidefinite programming extend almost automatically to semirandom models [fk, al, pw], and moreover many of these results match the information-theoretic thresholds for exact recovery. In contrast, semidefinite programs for partial recovery, such as those of Guédon and Vershynin [GV], come within a constant of the threshold but have been unable to close this gap.

In fact Guédon and Vershynin [GV] developed a general framework for using SDPs to solve problems on sparse graphs, including partial recovery for the stochastic block model. We define a notion of semirandom model for any problem in this framework, generalizing the semirandom model for community detection. We show that any analysis that follows their framework carries over automatically to this semirandom model. In particular, after minor modifications, the SDP analyzed in [GV] achieves partial recovery in the semirandom block model, up to within a constant factor of the classical threshold.

Semirandom vs. random gaps offer an explanation for why it seems hard to find semidefinite programs for partial recovery that reach the information-theoretic threshold: the analysis often extends equally well to the semirandom model, where we know the threshold is strictly harder!

Suppose we have $(B,R,Z_{R})$ such that the following three conditions hold for some value $\alpha$, some function $F(\beta)$, and some matrix norm $\|\cdot\|$:

$Z_{R}$ is a maximizer of the reference objective $\langle R,-\rangle$ over $\Omega$ (the reference SDP recovers the truth),

$\|B-R\|_{\infty\to 1}\leq\alpha$ (the observed objective is close to the reference one in cut norm),

if $Z\in\Omega$ and $\langle R,Z_{R}-Z\rangle\leq\beta$, then $\|Z_{R}-Z\|^{2}\leq F(\beta)$ (good solutions to the reference SDP are close to the ground truth).

Then $\|Z_{R}-\widehat{Z}\|^{2}\leq F(2K_{G}\alpha)$ where $\widehat{Z}$ is any maximizer of the empirical objective $\langle B,-\rangle$ over $\Omega$, and $K_{G}$ is the Grothendieck constant.

Here, the cut norm (or $\infty$-to-$1$ norm) of a matrix is defined as

The proof of Proposition 7.1 follows from Lemma 3.3 in [GV], and uses Grothendieck’s inequality.

The partial recovery results of [GV] proceed by verifying the three conditions of Proposition 7.1 for a particular choice of parameters:

Assume $a>20$. Let $B=A-\lambda J$ with $\lambda=\frac{a+b}{2n}$, $R=\frac{a-b}{2n}\sigma\sigma^{\top}$, and $Z_{R}=\sigma\sigma^{\top}$. Conditions (1–3) of Proposition 7.1 hold a.a.s. with $\alpha=O(n\sqrt{a+b}),F(\beta)=\beta\cdot O(n/(a-b))$, and $\|\cdot\|$ as the Frobenius norm $\|\cdot\|_{2}$.

Concretely, this means that we solve the following SDP:

Maximize $\langle A-\lambda J,Z\rangle$ subject to $Z\succeq 0$ and $\operatorname{diag}(Z)\leq I$, where $\lambda=\frac{a+b}{2n}$.

Note that the regularization constant $\lambda$ is necessary because if we simply take $B=A$ then condition 1 of Proposition 7.1 fails. In [GV] they estimate $\lambda$ from the empirical average degree, but their arguments also apply to the case where we deterministically take $\lambda=\frac{a+b}{2n}$. (This requires knowledge of the parameters $a,b$ but we will address this issue later.)

In [GV], condition 1 is shown in Lemma 5.1, and conditions 2 and 3 are implicit in the proof of Lemma 5.2. These require a technical condition: $\max\{a(1-a/n),b(1-b/n)\}\geq 20$, which for large $n$ simply amounts to $a>20$. By Propositions 7.1 and 7.2, we now attain the result $\|Z_{R}-\widehat{Z}\|_{2}^{2}\leq O(n^{2}\sqrt{a+b}/(a-b))$ a.a.s. It is also shown in [GV] how to translate this to a precise partial recovery result:

Let $Z_{R}=\sigma\sigma^{\top}$. For any $\frac{1}{2}<\eta\leq 1$, $\eta$-partial recovery succeeds a.a.s. in the stochastic block model, provided that $\|Z_{R}-\widehat{Z}\|_{2}^{2}\leq(1-\eta)n^{2}$, by taking the signs in the top eigenvector of $\widehat{Z}$.

There exists a constant $C$ such that $\eta$-partial recovery succeeds a.a.s. in the stochastic block model as $n\to\infty$ whenever $a>20$ and $(a-b)^{2}\geq C(1-\eta)^{-2}(a+b)$.

The constant $C$ is quite large: [GV] sets $C=10^{4}$, although no attempt is made to optimize this constant. Nevertheless this result is only off by a constant from the threshold, which is $(a-b)^{2}>2(a+b)$. Our random vs. semirandom separation becomes small as $k$ grows, so it remains plausible that semidefinite programs can achieve partial recovery when $k(1-2\varepsilon)^{2}>1+o(1)$ as $k\to\infty$. In fact, SDPs are known to distinguish random block model graphs from Erdős–Rényi graphs in such a range [ms], and it would be interesting to determine whether this carries through to partial recovery in the semirandom model.

2 SDPs and Semirandom Models

We now turn to a semirandom view of the general Guédon–Vershynin framework. In the semirandom block model, a monotone adversary is allowed to make changes aligned with the ground truth $Z_{R}$; more formally, it can add a matrix $S$ to the observed adjacency $A$, where $S$ is symmetric and has $1$’s in some same-spin entries where $A$ is , and $-1$’s in some opposite-spin entries where $A$ is $1$. It is easily verified that $Z_{R}$ maximizes $\langle S,-\rangle$ over $\Omega$: every matrix in $\Omega$ has entries in $$, and$Z_{R}$has$\pm 1$entries that match the sign pattern of$S$.