Source-linked AI summary
Contextual Stochastic Block Models
Yash Deshpande, Andrea Montanari, Elchanan Mossel, Subhabrata Sen
TL;DR
The paper asks how to infer latent communities from a sparse graph and high-dimensional covariates that share the same structure. It develops a combined statistical model, rigorously analyzes its Gaussian limit, and studies belief propagation, finding threshold-level performance under the model while focusing on two approximately equal-sized clusters and fixed known parameters.
Problem
Inferring latent community labels from graph structure and high-dimensional covariates is difficult because combining their complementary information lacks a principled analysis.
Method
The paper introduces a model combining the stochastic block model with the spiked covariance model and analyzes belief propagation for inference.
Results
The analysis rigorously establishes the correct information-theoretic threshold in the Gaussian limit and empirically shows belief propagation achieves the conjectured threshold.
Takeaways & Limitations
The tight analysis shows that graph and covariate sources jointly contribute to latent-community inference, including in large-degree and Gaussian regimes.
Takeaways & Limitations
The main analysis focuses on two approximately equal-sized latent clusters and fixed, known model parameters.
Abstract
from arXiv · showhide
We provide the first information theoretic tight analysis for inference of latent community structure given a sparse graph along with high dimensional node covariates, correlated with the same latent communities. Our work bridges recent theoretical breakthroughs in the detection of latent community structure without nodes covariates and a large body of empirical work using diverse heuristics for combining node covariates with graphs for inference. The tightness of our analysis implies in particular, the information theoretical necessity of combining the different sources of information. Our analysis holds for networks of large degrees as well as for a Gaussian version of the model.
1 Introduction
The paper studies inference of shared latent communities from complementary graph and high-dimensional covariate data, establishing sharp information-theoretic thresholds and evaluating belief propagation.
- Motivation and model: Combining graph structure with node features is challenging because the two sources provide complementary information about latent communities.The political blogs example contrasts network links with bag-of-words representations of blog content.
- Motivation and model: The model combines stochastic block and spiked covariance models to represent graph and covariate observations sharing latent cluster structure.The graph and covariate sources are assumed conditionally independent given the node labels.
- Contributions: The paper establishes a sharp information-theoretic threshold for detecting latent structure using techniques from statistical physics.The threshold is presented as an information-theoretic characterization of detectability in the combined model.
- Contributions: In the Gaussian limit, novel Gaussian comparison inequalities rigorously establish the correct information-theoretic threshold.The analysis also shows convergence to Gaussian-limit predictions as graph density diverges.
- Contributions: The authors provide a simple iterative belief propagation algorithm for inference.The algorithm computes vertex messages iteratively and returns their signs as estimated labels.
- Contributions: Empirically, the algorithm achieves the conjectured information-theoretic threshold on data generated from the model.The paper numerically validates the threshold prediction and organizes the proof and algorithmic analyses separately.
2 Model and main results
The paper models two balanced latent communities observed through a graph and high-dimensional covariates, then derives sharp recovery thresholds for their combination. It establishes the threshold rigorously in Gaussian and large-degree settings and gives an efficiently computable spectral estimator above it.
- Model: The model combines a stochastic block model graph with a spiked covariance model sharing latent community labels.The graph and covariates are conditionally independent given labels and provide complementary information.
- Thresholds: Graph-only recovery is possible if and only if λ > 1, while covariate-only recovery is possible if and only if µ > √γ.These are the separate thresholds that the joint model interpolates between.
- Thresholds: The cavity prediction gives an analogous joint threshold that smoothly interpolates between the graph-only and covariate-only regimes.The prediction is represented by an estimator with overlap bounded away from zero under its stated condition.
- Main results: The main result rigorously confirms the cavity prediction in the limit of large graph degrees.The theorem provides a positive overlap margin ε(λ, µ) independent of d, with vanishing d-dependent error.
- Main results: The Gaussian model captures the large-degree behavior of the original graph model through a universality result.Theorem 4 is obtained from the Gaussian threshold result together with this universality theorem.
- Main results: For the Gaussian observation model, weak recovery is impossible when λ2 + µ2/γ < 1 and achievable when λ2 + µ2/γ > 1.Above the threshold, the estimator is proportional to the maximum eigenvector of M(ξ*) with ξ* minimizing λmax(M(ξ)).
3 Related work
Prior work combines graph structure and node information using many generative, heuristic, Bayesian, and semisupervised methods, but rigorous guarantees were incomplete or non-optimal. The paper positions its contribution as a sharp information-theoretic analysis of the combined setting.
- Existing approaches: Existing graph-clustering approaches with node attributes include generative models, heuristic model-free methods, Bayesian methods, and other surveyed techniques.These methods address clustering with graph and node information but span diverse modeling and algorithmic assumptions.
- Rigorous results: Some rigorous analyses impose unrealistic edge-label independence assumptions or establish only one side of a conjectured threshold.Other works analyze specific heuristics and provide consistency guarantees, but those guarantees are not optimal.
- Semisupervised setting: In the semisupervised sparse stochastic block model, correlated recovery is impossible from any vanishing proportion of labeled nodes.This contrasts with the paper’s claim that high-dimensional covariates shift the information-theoretic threshold.
4 Belief propagation: algorithm and cavity prediction
The paper derives a linear message-passing algorithm from belief propagation and analyzes its iterates through density evolution. The linearized recursion amplifies weak signal precisely above the joint threshold λ2 + µ2/γ > 1.
- Algorithm: The algorithm iteratively updates vertex and covariate messages and returns the signs of the final vertex messages as label estimates.It starts from an initialization and runs for a prescribed number of iterations.
- Algorithm: With µ = 0, the edge updates closely match nonbacktracking spectral power iteration, while λ = 0 yields power iteration for singular vectors of B.The two limiting cases recover graph-only and covariate-only spectral procedures.
- Algorithm: The method approximates belief propagation by linearizing around a zero-information fixed point and adding memory terms through approximate message passing.The behavior of the resulting iteration is tracked by density evolution in the high-dimensional limit.
- Density evolution: Density evolution maps the law of current message variables to the law of their next iterates and faithfully describes the algorithm’s message distributions.The recursion is defined by repeatedly applying the map DE.
- Threshold prediction: The linearized density-evolution map has spectral radius greater than one if and only if λ2 + µ2/γ > 1.Thus, a small initial correlation is exponentially amplified exactly above this condition.
- Threshold prediction: Random initialization has correlation of order 1/√n with the truth, which is amplified above the threshold to yield nontrivial reconstruction.Below the threshold, the correlation is expected to remain small and the algorithm does not yield a useful estimate.
5 Proof overview
The proof establishes the Gaussian weak-recovery threshold by combining impossibility below the threshold with an optimization and spectral construction above it. Gaussian comparison inequalities control the optimization, while universality transfers the result to large-degree graphs.
- Gaussian threshold: Theorem 6 is the key Gaussian-model result establishing a precise weak-recovery threshold.It analyzes the limit p,n → ∞ with fixed aspect ratio p/n → 1/γ.
- Impossibility: Below λ2 + µ2/γ = 1, a second-moment argument bounds the chi-squared distance and makes both testing and weak recovery impossible.The total-variation bound prevents any test from distinguishing the planted and null models with probability approaching one.
- Achievability: Above λ2 + µ2/γ = 1, an optimization problem yields soft label estimates equivalent to the efficiently computable spectral algorithm.The optimizer is positively correlated with the latent labels.
- Proof technique: Gaussian process comparison uses Sudakov-Fernique inequalities to derive matching asymptotic upper and lower bounds for the optimization value.The lower bound from the comparison process X2 is identified as novel and crucial to the main theorem.
- Numerical validation: The resulting phase transition is numerically validated through BP tests and overlap measurements in Figure 1.Below the theoretical curve, the null is accepted and estimated overlaps are negligible, in agreement with the theory.
6 Experiments
The experiments evaluate belief propagation for testing and weak recovery in the Gaussian model, finding close agreement with the theoretical phase transition.
- BP is evaluated through 100 Monte Carlo runs on graphs with n = 800, p = 1000, and d = 5.
- The algorithm runs for T = 50 iterations from random initialization and produces vertex and covariate iterates.
- Figure 1 reports null-rejection probabilities and BP overlaps with the community vectors across λ and µ.
- Below λ2 + µ2/γ = 1, the null is accepted and estimated vectors have negligible correlation with the truth.
- The empirical detection and overlap results are in excellent agreement with the theoretical curve.
A Proof of Theorem 6
The proof establishes the detection boundary by combining contiguity below the threshold with a test and weak-recovery construction above it. Its technical ingredients include likelihood-ratio second moments and Gaussian comparison inequalities.
- Contiguity is used to show that asymptotically error-free detection is impossible below the conjectured detection boundary.
- For λ2 + µ2/γ > 1, the maximizer of ⟨x, Ax⟩ + b∗⟨y, Bx⟩ achieves weak recovery of the community assignment vector.
- The likelihood-ratio second moment is bounded under the null using the expectation operator E0[·] and independent prior draws.
- The main technical contribution uses a novel Gaussian process comparison argument based on the Sudakov-Fernique comparison.
A.2 A Gaussian process comparison result
This section derives a tight high-dimensional characterization of the Gaussian optimization value by comparing Gaussian processes whose asymptotic upper and lower bounds coincide.
- The optimization problem is studied as p,n →∞ with constant aspect ratio n/p = γ.
- Two comparison processes provide upper and lower bounds whose asymptotic values coincide in the high-dimensional limit.
- The null-value characterization generalizes maximum eigenvalue and singular-value bounds for W and Z.
- For τ = 0, the optimization value recovers OPT = 2√ρ, while setting ρ = 0 and b = 1 recovers OPT = √τ(1 + γ−1/2).
A.4 Proof of Theorem 15: the lower bound
The lower-bound proof constructs aligned comparison-process optimizers and uses deformed GOE eigenvalue and eigenvector results to match the upper-bound asymptotics.
- The proof separates the cases G′(2λ + bµt∗, 4ρ + b2τ) = 0 and G′(2λ + bµt∗, 4ρ + b2τ) > 0.
- In the zero-derivative case, principal eigenvectors of Wx and Wy are used as the candidate optimizers.
- Standard GOE results provide the limiting value in the eigenvector construction.
- The lower bound is proved with the principal eigenvalue and eigenvector of a deformed GOE matrix.
- The comparison theorem controls the constructed vectors, and the remainder term vanishes before taking ε to zero.
B Proof of Lemma 8
The proof converts density-evolution recursions into a four-dimensional moment map and analyzes its Jacobian to determine when an eigenvalue exceeds one.
- Moment mapping: The distributional recursions yield a vector of moments and an induced mapping φDE: R4 → R4.The mapping is analyzed at the origin through its Jacobian.
- Jacobian analysis: The Jacobian of φDE at zero is reduced, up to identical row and column permutations, to an eigenvalue calculation.The proof characterizes eigenvalues through a polynomial condition.
- Root criterion: Checking the polynomial at z = 1 and z = −1 determines whether it has a root with magnitude greater than 1.The argument uses f(0) < 0 and evaluates the polynomial at the two boundary points.
C Proof of Theorem 4
The proof of Theorem 4 relates MMSE to estimators with nontrivial overlap, then establishes recovery above the threshold and impossibility below it.
- Estimator–MMSE link: Lemma 19 converts an estimator with normalized norm and MMSE bounded below one into an estimator with nontrivial overlap.The lemma applies to both the original observation model and the Gaussian observation model.
- Impossibility regime: When γ < 1, the proof uses Theorem 6 and the I-MMSE identity to show lim infn→∞ MMSE(v; A(θ), B) = 1.The argument considers θ ∈ [0, λ] under the condition θ2 + µ2/γ < 1.
- Impossibility regime: This MMSE limit implies that every estimator bv(AG; B) has vanishing overlap with v in probability.Thus weak recovery is impossible in the stated regime.
- Recovery regime: For γ > 1, the proof sets λ0 = (1 − µ2/γ)1/2 and applies bounds uniformly for θ1, θ2 ∈ [λ0, λ].The argument assumes µ2/γ < 1, with the complementary case delegated to Theorem 2.
- Recovery regime: Applying Theorem 5 and Lemma 19 yields an estimator bs(AG, B) with nontrivial overlap in probability.This establishes the positive-recovery direction of the theorem.
D Belief propagation: derivation
The derivation starts from the posterior and belief-propagation message updates, approximates message distributions analytically, and reduces the resulting algorithm from O(np) messages to a linear-size form.
- Belief propagation: Belief propagation is derived from the posterior distribution of u and v given graph and covariate observations A and B.Messages represent cavity marginals and are updated through distributional equations.
- Notation: The conventions identify i, j, k as graph nodes, q, r, s as covariates, and ∂i and ∂ic as neighbors and non-neighbors.The symbol ≃ denotes equality up to an omitted proportionality constant that may change between lines.
- Message approximation: An analytical ansatz reduces distribution-valued updates to real-valued updates using Gaussian approximations and Taylor expansions.The expansions assume uq and Bjq are O(1/√p), while later approximations ignore lower-order terms.
- Simplified updates: The resulting definitions give simplified update equations for node messages ηt+1 and covariate-related messages mt.The derivation computes these updates by substituting the analytical ansatz into the original belief-propagation equations.
- Message reduction: The updates for ηt and mt initially require O(np) messages, motivating a reduction to O(dn + p) messages.The reduced representation is linear in the size of the input graph observation.
- Graph-message reduction: Non-neighbor contributions are shown to be negligible through Taylor bounds, allowing graph-message updates to retain only neighbor-dependent terms.The argument uses bounds on f and its derivative and ignores O(1/n) corrections.
- Covariate-message reduction: A further ansatz and first-order Taylor expansion reduce covariate-to-node updates by discarding terms of order O(1/n).The resulting identifications are substituted back into the update equations.