Asymptotic Mutual Information for the Two-Groups Stochastic Block Model

1 Introduction and main results

• The stochastic block model assigns vertices to groups and makes edge probabilities depend on endpoint labels, supporting community and latent-attribute inference from one graph realization.The paper focuses on the symmetric two-group model, with within-group probability p_n and across-group probability q_n.Source: §1 · pp. 1–2

1.1 Main result: Asymptotic per-vertex mutual information

• The paper gives an explicit single-letter characterization of asymptotic per-vertex mutual information, equivalently conditional entropy, under suitable parameter conditions.The characterization uses an effective Gaussian scalar channel and the signal-to-noise parameter λ_n = n(p_n − q_n)^2/[4p_n(1 − p_n)].Source: §1 · pp. 1–2, §1.1 · pp. 2–3

1 Introduction and main results

• The conditional entropy per vertex can range from 0 to log 2, and when λ_n is of order one it has a strictly positive limit while the incorrectly labeled fraction has a nontrivial limit.The strong-signal regime can instead yield vanishing per-vertex conditional entropy under exact reconstruction results.Source: §1 · p. 2

1.1 Main result: Asymptotic per-vertex mutual information

• The main theorem assumes λ_n converges and n p_n(1 − p_n) diverges, so the stated asymptotic result requires average degree to diverge, even arbitrarily slowly.The proof still gives an explicit error bound for large but bounded average degree, up to an offset vanishing with that degree.Source: §1.1 · p. 3
• The limiting MMSE equals random guessing for λ ≤ 1 but is strictly better than random guessing for λ > 1, establishing λ = 1 as an estimation phase transition.The same threshold also applies to overlap and vector mean square error.Source: §1.1 · p. 4

1.2 Outline of the paper

• The proof reduces the stochastic block model to a Gaussian observation model, characterizes its mutual information using AMP and an area theorem, and transfers the result back with explicit approximation bounds.The Gaussian model uses a rank-one signal corrupted by additive Gaussian noise, and the per-dimension mutual information is universal across the two noise models.Source: §1.1 · p. 5, §1.2 · p. 5

1.3 Notations

• The paper’s notation identifies graphs with adjacency matrices, uses natural logarithms and nats, and defines high-probability events as those whose probability tends to one.The paper also outlines related-work, estimation, proof, and technical-appendix sections.Source: §1.2 · p. 5, §1.3 · pp. 5–6

• Earlier work established sharp thresholds for exact recovery, including √α−√β ≥2 when pn = α log(n)/n and qn = β log(n)/n.Source: §2 · p. 6
• For sparse two-group models, detection is solvable if and only if (a −b)^2 > 2(a + b) when pn = a/n and qn = b/n.Source: §2 · p. 6
• The paper bridges detection and exact recovery by characterizing the minimum estimation error when it is nonzero but better than random guessing for λ > 1.Source: §2 · p. 6
• Prior information-theoretic work established normalized mutual-information limits in disassortative regimes, but left the assortative limit open and did not identify its value.Source: §2 · p. 6
• The paper's techniques reduce SBM mutual information to a Gaussian model using Lindeberg interpolation, then establish tightness through algorithmic bounds and an area theorem.Source: §2 · p. 7
• The authors expect the results to extend to multiple-community, censored, labeled, and other block models, while universality is established here across Gaussian and binary-output channels.Source: §2 · p. 7

3.2 Evaluation of the asymptotic formula

• For λ ≤ 1, the effective SNR is γ∗(λ) = 0 and the asymptotic mutual information equals the elementary upper bound λ/4.The fixed-point solution is trivial at and below the critical point.Source: §3.2 · p. 9
• The variational value Ψ(γ∗(λ), λ) is strictly below λ/4, with Ψ(γ∗(λ), λ) approaching log 2 as γ tends to infinity.Equation (8) has at most one strictly positive solution, and such a solution exists only when λ > 1.Source: §3.2 · p. 9
• The asymptotic mutual information is characterized variationally as Ψ(γ∗(λ), λ) = minγ∈[0,∞) Ψ(γ, λ).The minimizer satisfies the fixed-point equation, with γ∗ selected as the largest non-negative solution.Source: §3.2 · p. 10
• The fixed-point equation can be solved numerically by initializing γ0 = λ and iterating γt+1 = λG(γt), the procedure used for Figure 2.Figure 1 interprets γ∗(λ) as the intersection of G(γ) = 1 − mmse(γ) with γ/λ.Source: Figure 1 · p. 8, §3.2 · pp. 9–10

3.3 Consequences for estimation

• At λ = 1, the matrix MMSE undergoes a phase transition, and Figure 2 shows the predicted estimation error decreasing rapidly toward zero for λ > 1.The same critical point extends to vector MMSE and overlap.Source: §3.3 · pp. 10, 12
• For λ ≤ 1, vector-MMSE and overlap estimation cannot asymptotically outperform having no information, whereas for λ > 1 they can do better even as n →∞.These conclusions hold under λn → λ and npn(1−pn) → ∞, and labels remain identifiable only up to an overall flip.Source: §3.3 · pp. 10–12

4.1 Gaussian model

• The proof compares the SBM with a Gaussian observation model whose mutual information agrees with the SBM to leading order under λn → λ and npn(1 − pn) → ∞.The Gaussian model matches the first two moments of the original model, and Proposition 4.1 establishes the mutual-information approximation.Source: §4.1 · p. 13
• Additional binary-erasure observations break the X versus −X symmetry, after which continuity as ε → 0 recovers the original model.The graph has the same conditional distribution given X or −X, so its sign cannot be recovered without the auxiliary observations.Source: §4.1 · p. 13, §4.3 · p. 16

4.3 Proof of Theorem 1.1 and Theorem 4.3

• Continuity in ε and the Gaussian-to-SBM comparison together prove the asymptotic mutual-information theorem for the stochastic block model.The Gaussian limit is first established at ε > 0, then extended to ε = 0 and transferred using Proposition 4.1.Source: §4.1 · p. 14, §4.3 · p. 16

4.2 Approximate Message Passing (AMP)

• AMP produces estimators whose large-dimensional iterates admit a Gaussian scalar-channel characterization governed by one-dimensional state evolution.The algorithm includes a memory term, unlike ordinary power iteration, enabling an explicit distributional characterization of the iterates.Source: §4.2 · pp. 14–15
• The Bayes-optimal AMP estimates upper-bound the minimum estimation error, and an area theorem shows that this gap vanishes with sufficiently many iterations.This connects AMP state evolution to the asymptotic minimum mean-square estimation error.Source: §4.2 · pp. 15–16

5 Proof of Proposition 4.1

• The SBM mutual information can be expressed through a Hamiltonian and its associated log-partition function.A lemma shows that computing the relevant log-partition function for an approximating Hamiltonian suffices for computing I(X; G).Source: §5 · pp. 17–18
• A Hamiltonian expansion approximates the SBM expression under the condition that λn → λ and npn(1 − pn) → ∞.The approximation uses Taylor expansion and controls the resulting error terms.Source: §5 · pp. 18–19
• A Lindeberg replacement bounds the change in the log-partition function when the transformed SBM variables are replaced by Gaussian variables.The derivative estimates and replacement theorem yield the Gaussian approximation required for Proposition 4.1.Source: §5 · pp. 19–21
• Combining the SBM and Gaussian mutual-information formulas with the replacement guarantee proves Proposition 4.1.The proposition follows by combining Lemmas 5.1 and 5.3 with Lemma 5.5.Source: §5 · p. 21

6.1 Auxiliary lemmas

• For every ε > 0, the fixed-point equation has a unique non-negative solution γ∗(λ, ε), differentiable in λ, and AMP’s recursion converges to it.These properties provide the regularity needed for the subsequent mutual-information calculation.Source: §6.1 · pp. 22–23
• The variational expression has controlled endpoint behavior: as λ → 0 it tends to ε log 2, while the large-λ limit uses γ∗(λ, ε) = λ + O(1).These limits anchor the integration argument for the mutual-information formula.Source: §6.1 · pp. 22–23
• The limiting AMP mean-square error is characterized by the fixed-point recursion and its associated scalar estimation problem.The proof uses state evolution to identify the asymptotic error of the AMP estimates.Source: §6.1 · p. 23

6.2 Proof of Proposition 4.2

• These steps establish Proposition 4.2 for the Gaussian model and supply the mutual-information limit used in the main theorem.The proof combines the auxiliary lemmas with the conditional I-MMSE calculation.Source: §6.2 · pp. 24–25
• The conditional I-MMSE identity relates the derivative of mutual information to the limiting estimation error, and AMP optimality turns the resulting bound into equality.Monotonicity and continuity extend the conclusion from almost every λ to every λ.Source: §6.2 · pp. 24–25

7.1 A general differentiation formula

• A general differentiation formula expresses how conditional entropy changes when one noisy observation channel varies while the others remain fixed.The proof uses two chain-rule decompositions and conditional independence to isolate the varying channel.Source: §7.1 · pp. 25–26
• The two-groups SBM fits this framework by taking uniform labels in {+1, −1}n and the graph adjacency matrix as the observations.Edges encode noisy observations of pairwise products XiXj.Source: §7.1 · p. 26

7.2 Application to the stochastic block model

• Applying the identity to the SBM yields a derivative relation involving the matrix minimum mean-square error of estimating the labels.The channel is reparameterized by θ through pn(θ) and qn(θ), with θ eventually set to λn.Source: §7.2 · pp. 27, 29
• The resulting bounds hold uniformly for θ in bounded intervals once n is sufficiently large.The threshold n0 depends on the chosen θmax.Source: §7.2 · pp. 27–28

7.3 Proof of Theorem 1.4

• The cited passage states that Lemma 7.2 and Theorem 1.1 yield a result for any 0 < λ1 < λ2, without specifying the resulting comparison.Source: §7.3 · p. 29

• vmmsen(λ) ≤ MMSEn(λ) follows from the conditional-mean estimator and the symmetry of (X, G).Source: §A.1 · p. 30
• The lower-bound argument assumes an optimal estimator exists, with an ε-optimal approximation available otherwise.Source: §A.1 · p. 30
• The minimizing scalar in the estimator comparison is α = ⟨X, bx(G)⟩/∥bx(G)∥2.Source: §A.1 · p. 30
• Comparing the resulting expressions in Eqs. (206) and (211) yields the desired lower bound in Eq. (41).Source: §A.1 · pp. 30–31

A.2 Proof of Lemma 3.6

• A normalized vector ξ(G) with ∥ξ(G)∥2 = √n is converted into a randomized sign estimator by independent coordinate-wise rounding.Source: §A.2 · p. 31
• The central limit theorem and dominated convergence complete the desired lower-bound argument for Lemma 3.6.Source: §A.2 · p. 31

B.1 Proof of Remark 5.4

• For Remark 5.4, Bernstein’s inequality applied to centered bounded quadratic-form terms gives the required concentration after setting t = Cn2pn.Source: §B.1 · p. 32

B.2 Proof of Lemma 6.1

• The identity mmse(γ, ε) = ε + (1 − ε)(1 − mmse(γ)) reduces the claim to a simpler case, while derivative signs follow from odd/even parity and nonpositive ψ′ for y, z ≥ 0.Source: §B.2 · pp. 32–33
• The proof uses E{X|√γX + Z} = tanh(γX + √γZ) and the identity sech(z)2 = 1 − tanh(z)2 to derive the required Gaussian-channel relations.Source: §B.2 · pp. 32–33
• Concavity of G′′(γ) follows by showing that both partial derivatives of H(x, y) are non-positive for x, y ≥ 0.Source: §B.2 · p. 33

• Conditioning on XXT leaves at most two possibilities for X, enabling the entropy comparison used in claim (147).Source: §B.3 · p. 34
• At λ = 0, independence of Y (0) and X gives I(X; X(ε), Y (0)) = I(X; X(ε)) = nε log 2.Source: §B.3 · p. 34
• For large λ, a principal-eigenvector estimator yields δ1(λ) = 2/λ, which controls the conditional entropy and proves the second claim.Source: §B.3 · p. 34
• The remaining entropy decomposition expands H(X, E|Y (λ), X(ε)) by the chain rule and bounds the success and failure events separately.Source: §B.3 · p. 34
• Dividing the resulting inequality by n and letting n →∞ completes the second claim.Source: §B.3 · p. 34

• The AMP iteration is reduced to the setting of, allowing almost-sure limits for pseudo-Lipschitz functions.Source: §B.4 · p. 35
• The state-evolution sequence is defined using the recursion for µt, while pseudo-Lipschitz functions and constants are specified for the induction.Source: §B.4 · p. 35
• The induction starts from trivial initial conditions s0 = x0 = 0, µ0 = 0, and ∆0 = 0, then propagates the claims through previous iterates.Source: §B.4 · pp. 35–36
• Lipschitz bounds and the induction hypothesis show that the error terms in the expansion of ∆t vanish asymptotically.Source: §B.4 · pp. 36–37
• Standard Wigner eigenvalue bounds and control the remaining terms, completing the induction claim for ∆t.Source: §B.4 · pp. 36–37