Source-linked AI summary
Recovering asymmetric communities in the stochastic block model
Francesco Caltagirone, Marc Lelarge, Léo Miolane
TL;DR
The paper asks when graph structure can recover labels better than chance in sparse stochastic block models, focusing on unbalanced communities. It analyzes local belief propagation and tree reconstruction, finding recovery above the Kesten–Stigum bound with revealed labels and identifying a spinodal threshold in the large-degree limit.
Problem
The paper asks whether labels in a sparse stochastic block model can be recovered better than chance, focusing on the less-studied unbalanced setting.
Source: §I · p. 1Method
The paper studies local belief propagation and analyzes the associated labeled Poisson Galton–Watson tree reconstruction problem.
Source: §I · pp. 1–2Results
With a vanishing fraction of labels revealed, local belief propagation solves detection above Kesten–Stigum; at large degree, the spinodal threshold governs tree reconstruction.
Source: §I · pp. 1–2Takeaways & Limitations
In the large-degree limit, the spinodal curve corresponds to the solvability threshold for reconstruction on the associated tree.
Source: §I · p. 2
Abstract
from arXiv · showhide
We consider the sparse stochastic block model in the case where the degrees are uninformative. The case where the two communities have approximately the same size has been extensively studied and we concentrate here on the community detection problem in the case of unbalanced communities. In this setting, spectral algorithms based on the non-backtracking matrix are known to solve the community detection problem (i.e. do strictly better than a random guess) when the signal is sufficiently large namely above the so-called Kesten Stigum threshold. In this regime and when the average degree tends to infinity, we show that if the community of a vanishing fraction of the vertices is revealed, then a local algorithm (belief propagation) is optimal down to Kesten Stigum threshold and we quantify explicitly its performance. Below the Kesten Stigum threshold, we show that, in the large degree limit, there is a second threshold called the spinodal curve below which, the community detection problem is not solvable. The spinodal curve is equal to the Kesten Stigum threshold when the fraction of vertices in the smallest community is above $p^*=\frac{1}{2}-\frac{1}{2\sqrt{3}}$, so that the Kesten Stigum threshold is the threshold for solvability of the community detection in this case. However when the smallest community is smaller than $p^*$, the spinodal curve only provides a lower bound on the threshold for solvability. In the regime below the Kesten Stigum bound and above the spinodal curve, we also characterize the performance of best local algorithms as a function of the fraction of revealed vertices. Our proof relies on a careful analysis of the associated reconstruction problem on trees which might be of independent interest. In particular, we show that the spinodal curve corresponds to the reconstruction threshold on the tree.
I. INTRODUCTION
Under the equal-expected-degree condition, this paper studies community recovery in sparse two-community stochastic block models with unbalanced classes. It establishes local recovery with revealed labels above the Kesten–Stigum bound and characterizes a spinodal non-solvability region and its connection to tree reconstruction in the large-degree limit.
I. INTRODUCTION
- The problem is whether graph G permits label recovery better than a random guess, with vertices assigned labels independently and edges sampled according to label pairs.The model is defined using a symmetric connectivity matrix M and a class-1 label probability p.Source: §I · p. 1
- The paper focuses on equal expected degrees, where looking at a vertex's degree alone provides no non-trivial community information.The condition is pa + (1−p)b = pb + (1−p)c = 1.Source: §I · p. 1
- Earlier work established solvability above and non-solvability below the Kesten–Stigum threshold in the balanced case, while the unbalanced case was less understood.The introduction notes that prior bounds below the threshold were not expected to be tight.Source: §I · p. 1
- With a vanishing fraction of labels revealed, belief propagation as a local algorithm solves community detection above the Kesten–Stigum bound.The introduction contrasts this result with the non-backtracking spectral regime.Source: §I · p. 1
- For p>p*, community detection is not solvable below the Kesten–Stigum bound in the large-degree regime.Here dλ2^2 remains constant as d tends to infinity.Source: §I · p. 2
- For p<p*, the spinodal curve λsp(p) gives a non-solvability region below dλ2^2 = λsp(p), but is not expected to be tight.The introduction notes that solvable points also occur between the spinodal curve and the Kesten–Stigum bound.Source: §I · p. 2
- In the large-degree limit, the spinodal curve is the solvability threshold for reconstruction on the associated labeled Poisson Galton–Watson tree.The paper also considers reconstruction when labels at depth n are revealed independently with probability q.Source: §I · p. 2
II. COMMUNITY DETECTION IN THE STOCHASTIC BLOCK MODEL
This section sets up community detection in the sparse, degree-uninformative stochastic block model and defines solvability as recovery better than random guessing. It summarizes the paper’s phase picture: impossibility below the spinodal curve is proved, while the hard phase is conjectured.
II. COMMUNITY DETECTION IN THE STOCHASTIC BLOCK MODEL
- Community detection is solvable when an algorithm recovers communities more accurately than a random guess; differing class-conditional average degrees already make it solvable.The paper assumes equal asymptotic average degrees thereafter, so degrees alone provide no such information.Source: §II · pp. 2–3
- The asymptotic regime takes n to infinity at fixed average degree, then obtains quantitative results as the average degree tends to infinity with λ and p fixed.Here p is the proportion of nodes in community one, and λ is interpreted as a signal-to-noise ratio.Source: §II · p. 3
- For p ≥ p*, the spinodal curve equals the Kesten–Stigum threshold; below p*, the paper conjectures a gap between the spinodal curve and the solvability threshold.The spinodal curve’s stated fixed-point properties were verified numerically, and the dotted solvability-threshold curve is conjectured.Source: §II · p. 3, Figure 1 · p. 3
- For λ = 1, having three fixed points requires 1 − 6p(1 − p) < 0, equivalently p < p*, without specifying a closed-form value for p*.The authors report that they verified Conjecture 6 numerically.Source: §II · p. 3
- The paper proves reconstruction is impossible below the spinodal curve, while the hard phase above it and below the conjectured solvability curve remains conjectural.The easy phase follows from [6]; the dotted curve for λc(p) is conjectured.Source: Figure 1 · p. 3, §II · p. 4
III. RECONSTRUCTABILITY ABOVE THE KESTEN-STIGUM BOUND
Above the Kesten–Stigum bound, the section characterizes recovery using local algorithms with revealed labels. As the revealed fraction vanishes, their performance is at least that of the optimal algorithm without revealed labels and is given by an explicit expression.
III. RECONSTRUCTABILITY ABOVE THE KESTEN-STIGUM BOUND
- With a vanishing fraction of labels revealed (q → 0), the optimal algorithm’s probability of recovering a typical vertex’s true label is 2P(N(α/2, α) > 0) − 1, where α is the stable fixed point.In this limit, the best local algorithm performs at least as well as the optimal algorithm with no revealed labels.Source: §III · p. 4
- For λ > 1, local algorithms with any positive revealed-label fraction achieve the stated lower bound on recovery performance.A t-local test predicts each vertex using only its graph neighborhood out to distance t.Source: §III · p. 4
- With a vanishing fraction of labels revealed, local algorithms perform at least as well as the optimal algorithm with no revealed labels.The paper describes an explicit optimal local test in the proof.Source: §III · p. 4
IV. NON-RECONSTRUCTABILITY BELOW THE SPINODAL
Below the Kesten–Stigum bound, the section proves impossibility below the spinodal curve and bounds the solvability threshold. Between the spinodal and Kesten–Stigum thresholds for p < p*, local recovery is characterized when enough labels are revealed.
IV. NON-RECONSTRUCTABILITY BELOW THE SPINODAL
- For p ≥ p*, the spinodal curve equals the Kesten–Stigum threshold, so the solvability threshold is 1; for p < p*, its location above the spinodal curve is conjectured.The spinodal curve is a lower bound on the solvability threshold, and the Kesten–Stigum threshold is an upper bound.Source: §IV · p. 4
- Below the spinodal curve, the paper proves community detection is not solvable; above it, the solvability threshold is bounded above by 1.For p < p*, the authors conjecture that the solvability threshold lies strictly between the spinodal curve and 1.Source: §IV · p. 4
- For p < p* and λsp(p) < λ < 1, the section gives a lower bound on local recovery when the revealed-label fraction exceeds βp(1−p).The associated figure depicts the necessary revealed fraction and the recovery lower bound for p < p*; for p = 0.05, λsp(0.05) ≈ 0.58.Source: §IV · pp. 4–5, Figure 3 · p. 5
V. RECONSTRUCTION ON TREES
The section connects community detection to reconstruction on labeled Galton–Watson trees. In the large-degree limit, the spinodal curve is the tree-reconstruction threshold, with optimal success changing across it.
V. RECONSTRUCTION ON TREES
- The labeled stochastic block model converges locally to a labeled Poisson Galton–Watson tree whose root label has probability p and whose child labels follow the transition matrix.Source: §V · p. 5
- The setup distinguishes full-depth, random q-sampled, and census reconstruction; q=1 is full-depth, while sampled or census solvability implies full solvability.Source: §V · p. 5
- When λ > 1, the tree problem is census-solvable and q-solvable for every 0 < q ≤ 1; when λ < 1, it is not census-solvable.Source: §V · p. 6
- For λsp < λ < 1, optimal success is positive above the stated q cutoff and zero below it.Source: §V · p. 6
- In the large-degree limit, λsp is the tree-reconstruction threshold: optimal success is positive above it and zero below it.Above λsp, Popt = 2P(N(α/2, α) > 0) −1 > 0.Source: §V · p. 6
VI. CAVITY METHOD ON TREES
The section establishes cavity equations as a recursive method for computing marginals, then studies them in the large-degree regime with λ fixed.
VI. CAVITY METHOD ON TREES
- The approach rigorously establishes cavity equations, a recursive method for computing marginals related to work on finding one community.Source: §VI · p. 6
- The quantitative analysis studies the labeled branching process as d tends to infinity while λ remains fixed.Source: §VI · p. 6
- The section introduces ε = 1 − b as an auxiliary parameter in this asymptotic analysis.Source: §VI · p. 6
A. The cavity recursions
The cavity method represents information on the labeled tree through recursively updated messages. Child-message independence yields a distributional recursion that depends on the rooted subtree.
A. The cavity recursions
- The recursive message update incorporates the revealed boundary labels and vertex-label priors.Source: A. The cavity recursions · p. 6
- The message calculation is restricted to the rooted depth-r subtree; the tree structure outside that ball provides no information about vertex labels.Source: A. The cavity recursions · p. 6
- Conditioned on the root's children, their depth-r messages are independent and identically distributed with law P_{r−1}, yielding a distributional recursion.Source: A. The cavity recursions · p. 7
B. Gaussian limit
The section analyzes the message recursions as degree grows, using limit arguments to establish Gaussian behavior. These asymptotic results contribute to the proof of Proposition 17.
B. Gaussian limit
- As d grows, the message distributions converge toward Gaussian distributions, with Wasserstein convergence stated for the recursion limit.Source: B. Gaussian limit · pp. 7, 9
- The asymptotic proof applies a central limit argument to recursion terms, establishing Wasserstein convergence of a rescaled sum to a normal distribution.Source: B. Gaussian limit · pp. 7–9
- The Gaussian-limit corollary, together with Conjecture 6, yields Proposition 17.Source: B. Gaussian limit · p. 9
VII. PROOFS FOR THE STOCHASTIC BLOCK MODEL
The section transfers reconstruction results on a branching process to community detection in the stochastic block model. It characterizes local-test performance using local convergence and conditional-distribution convergence.
VII. PROOFS FOR THE STOCHASTIC BLOCK MODEL
- Revealed labels at the boundary of the radius-r ball define the local information used for estimating a uniformly chosen vertex.Each label is revealed independently with probability q; the boundary set contains revealed labels on the ball's boundary.Source: §VII · pp. 9–10
- Local convergence couples the stochastic block model and branching process so their conditional distributions converge.For i = 1, 2, the conditional laws of the local statistic converge as n tends to infinity.Source: §VII · pp. 9–10
- The local test's performance is characterized using the branching-process reconstruction results.The section applies those results to the stochastic block model.Source: §VII · pp. 9–10
A. Upper bound
The upper-bound argument uses a local test based on the rooted graph and boundary-label information. Its corollary gives a zero-success regime below the spinodal threshold and a limiting recursion value when λ > 1.
A. Upper bound
- When λ < λsp(p), µ∞ = 0 and the limiting optimal success probability is zero.The stated limit is lim_{d→∞} lim sup_{n→∞} Psucc(T opt) = 0.Source: A. Upper bound · p. 10
- When λ > 1, µ∞ = α, yielding the first bound of Proposition 7.The passage gives this as a corollary consequence but does not state the bound's value here.Source: A. Upper bound · p. 10
- The upper-bound test is local: it uses the rooted graph and extra information from labels on the radius-r boundary.The test estimates the label of a uniformly selected vertex.Source: A. Upper bound · p. 10
B. Lower bound
The lower-bound argument compares optimal estimation with a local test when a fraction of labels is revealed. The stated corollary yields positive limiting recursion value for λ > 1 and q > 0.
B. Lower bound
- The setting allows each vertex label to be revealed independently with probability q.The lower-bound argument considers estimation when a fraction q of labels is revealed.Source: B. Lower bound · p. 10
- For λ > 1 and q > 0, µ∞ = α > 0.The passage identifies this as the consequence of the corollary used for the lower-bound result.Source: B. Lower bound · p. 11
- A local test achieves the lower bound in (22), giving the stated lower-bound result for optimal estimation.The proof bounds optimal-test performance below by the performance of the local test.Source: B. Lower bound · p. 11