Source-linked AI summary
A Tractable Fully Bayesian Method for the Stochastic Block Model
Kohei Hayashi, Takuya Konishi, Tatsuro Kawamoto
TL;DR
Bayesian inference for the stochastic block model must address cluster assignments and the number of clusters, while partial Bayesian methods can overestimate model complexity and fully Bayesian model selection can be costly. The paper develops an FAB framework with sparse-graph and asymptotic-expansion refinements; the expansion improves the error rate, though F2AB lacks a consistency guarantee.
Problem
Bayesian SBM inference must recover cluster assignments and select the number of clusters, but partial Bayesian methods can overestimate model complexity and fully Bayesian model selection requires evaluating all candidate models.
Source: §1 · pp. 1–2Method
The FAB framework analyzes sparse-graph model singularities exactly, refines the asymptotic joint-marginal expansion, and derives a new BP rule for full Bayes.
Source: §1 · p. 2Results
The refined asymptotic expansion improves the error rate and yields interpretable regularization terms.
Source: §1 · p. 2Takeaways & Limitations
Empty bicluster contributions Pkl and QS impose an extra penalty on model redundancy, with the penalty depending on the prior choice.
Source: §3.1 · p. 5F2AB lacks a consistency guarantee because it uses BP and a lower bound, despite empirically selecting better models than other methods.
Source: §6 · p. 9
Abstract
from arXiv · showhide
The stochastic block model (SBM) is a generative model revealing macroscopic structures in graphs. Bayesian methods are used for (i) cluster assignment inference and (ii) model selection for the number of clusters. In this paper, we study the behavior of Bayesian inference in the SBM in the large sample limit. Combining variational approximation and Laplace's method, a consistent criterion of the fully marginalized log-likelihood is established. Based on that, we derive a tractable algorithm that solves tasks (i) and (ii) concurrently, obviating the need for an outer loop to check all model candidates. Our empirical and theoretical results demonstrate that our method is scalable in computation, accurate in approximation, and concise in model selection.
1. Introduction
The paper studies Bayesian inference for the fundamental stochastic block model, addressing cluster assignments and the selection of the number of clusters. It presents a fully Bayesian framework intended to make model selection tractable while establishing a consistent criterion, including for sparse graphs.
1. Introduction
- Full Bayes accounts for uncertainty in both cluster assignments and model parameters, whereas partial Bayes accounts only for assignment uncertainty.Full Bayes requires approximation of intractable integrals; partial Bayes is often favored for tractability, and BP retains assignment correlations unlike mean-field VB.Source: §1 · p. 1
- Sparse-graph analysis lacks an established consistent model-selection method, while partial Bayes overestimates model complexity and fully Bayesian selection can require evaluating up to Kmax candidates.The paper focuses on addressing these limitations for the fundamental SBM.Source: §1 · pp. 1–2
- FAB inference can eliminate unnecessary model components during inference, starting from Kmax and converging to a selected K no greater than Kmax.The paper notes that this regularization behavior is a feature of FAB methods for latent-variable models.Source: §1 · p. 2
- The paper introduces an FAB framework for the SBM with an approximation consistent for dense and sparse graphs, and closed-form EM-like alternating maximization.The framework automatically selects K during posterior inference, removing the outer loop over candidate values, and estimates all parameters without hyperparameters.Source: §1 · p. 2
- For sparse graphs, the original FAB approximation is invalid because of model singularity, which the paper analyzes explicitly.The paper also derives a more rigorous asymptotic expansion of the joint marginal likelihood, improving the error rate and yielding interpretable regularization terms, and derives a new BP rule for full Bayes.Source: §1 · p. 2
2. Background
The background defines the SBM and reviews EM, belief propagation, and inference in sparse graphs. It contrasts mean-field and BP approaches, then explains why sparse graphs make accurate posterior inference important and allow a lower-cost BP update.
2.1. SBM
- Each SBM node belongs to one of K clusters, and each edge is assigned to a bicluster whose connection probability is specified by the affinity matrix Π.The model also uses γ for cluster proportions and X for the adjacency matrix.Source: §2.1 · p. 2
2.2. EM Algorithm
- Variational marginalization makes inference over the exponentially many cluster assignments tractable in principle, and EM updates the assignment distribution and parameters in alternating steps.The M-step maximizes the expected complete-data log-likelihood with closed-form parameter updates.Source: §2.2 · pp. 2–3
2.3. BP
- Mean-field VB approximates the joint assignment posterior with a factorized distribution, while BP uses graph structure to compute marginal information and can retain assignment correlations.BP on the SBM does not converge to the exact posterior because the graph has many loops, though it can outperform mean-field approaches in many cases.Source: §2.3 · p. 3
2.4. Inference on a Sparse Graph
- In sparse graphs, πkl = Θ(1/N), so assignment uncertainty persists as N grows; sparse-graph BP replaces messages from unconnected nodes with an external field and has complexity O(MK^2).The stated complexity uses M edges and O(1) neighbors per node.Source: §2.4 · p. 3
3. Asymptotic Evaluation of Marginals
The section approximates the SBM’s fully marginalized likelihood using variational handling and asymptotic integration, while treating cases where Laplace’s conditions fail. It derives an interpretable complexity-penalized criterion and an approximation to the model-specific marginal likelihood.
3. Asymptotic Evaluation of Marginals
- The SBM is reparameterized in exponential-family form, with natural parameters for cluster proportions and edge probabilities linked to the original parameters.The two parameterizations represent the same probabilistic model.Source: §3 · pp. 3–4
3.1. Asymptotic Joint Marginal
- With assignments fixed, the joint marginal is more manageable; when clusters are nonempty, Laplace’s method approximates its integral around the unique likelihood peak.The full marginal is first rewritten using a variational form, but the joint marginal still contains parameter integrals.Source: §3.1 · p. 4
- Empty clusters make the Hessian singular, while a bicluster with no edges places the maximum at an endpoint, violating Laplace conditions in cases critical for sparse graphs.The method evaluates the violated cases exactly and combines them with Laplace’s method to obtain an asymptotic expansion.Source: §3.1 · p. 4
- Marginalizing over non-empty clusters and biclusters yields a BIC-like maximum-likelihood-plus-penalty term, while empty clusters and biclusters add prior-dependent penalties against redundancy.The ℓ_N term decreases on the order of ln N as the number of non-empty clusters grows; R1 and R2 add Hessian-based complexity terms.Source: §3.1 · p. 5
3.2. Asymptotic Marginal Likelihood
- F2IC(K) approximates ln p(X|K) with an O(1) error, and under A1 its error decreases as O(N^-1) when almost-empty clusters are rare under the marginal posterior.A1 concerns clusters with o(√N) nodes.Source: §3.2 · p. 5
4. Posterior Inference and Model Selection
The method makes fully Bayesian model selection tractable by constructing a lower bound for F2IC and using belief propagation for cluster inference. Its R1 and R2 penalties suppress different forms of redundant clusters, allowing inference to reduce the model without an outer candidate loop.
4.1. Lower Bound of F2IC
- F2AB uses a tractable lower bound to bypass challenges in parameter optimization, latent-assignment inference, and expectation computation; uniform priors make prior terms constant.The construction addresses challenges 2–4 with the lower bound and ignores the constant terms under the stated uniform-prior conditions.Source: §4.1 · p. 5
4.2. Inference of q(Z)
- FABBP approximates BP messages for sparse graphs at O(MK^2) cost, while F2AB alternates cluster-assignment inference with updates of the model parameters.The algorithm derives a new BP rule to tighten the lower bound through updates to q(Z).Source: §4.2 · p. 6
4.3. Penalization Effect of R1 and R2
- R1 reduces the message proportion of clusters with only a few nodes, while its penalty vanishes for clusters containing Ω(N) nodes.The R1 effect is illustrated in Figure 1.Source: §4.3 · p. 6, Figure 1 · p. 7
- R2 penalizes clusters with many low-proportion biclusters, making its redundancy assessment finer-grained than R1’s cluster-proportion penalty.The two cluster proportions for a bicluster appear together in the R2 penalty.Source: §4.3 · p. 7
- Because both penalties affect BP messages and remove redundant clusters during FABBP iterations, starting from a sufficiently large Kmax lets the algorithm determine K automatically.This removes the need to compute the F2IC lower bound separately for model selection.Source: §4.3 · p. 7
5. Related Work
Related work addresses Bayesian inference and criteria for choosing the number of SBM clusters. The paper positions F2IC as accurate and consistent for sparse graphs without A2, while contrasting it with methods that require additional conditions or candidate-by-candidate evaluation.
Model Selection
- ICL can be asymptotically equivalent to the marginal likelihood for dense graphs under A2, but its consistency does not hold for sparse graphs.For sparse graphs, the entropy term H(˜p) is O(N).Source: §5 · p. 7
- The VB lower-bound counterpart of ICL is non-asymptotic, but its mean-field approximation error is not asymptotically negligible and consistency does not hold.Source: §5 · p. 7
- FIC includes the R1 penalty but omits R2 by ignoring the Hessian term, weakening regularization and increasing approximation error relative to F2IC.The paper also notes that FIC does not handle empty (bi)clusters in Laplace’s method and lacks a BP inference formulation.Source: §5 · pp. 7–8
- Corrected ICL is asymptotically equivalent to the full marginal under A2, but still requires an outer loop over model candidates.Source: §5 · p. 8
- F2IC is reported as the most accurate criterion and the only one consistent for sparse graphs without special conditions such as A2.Table 1 compares accuracy and whether model selection is one pass.Source: §5 · p. 8, Table 1 · p. 8
6. Experiments
Experiments compare inference and model-selection methods on synthetic and real networks. F2AB performs strongly on both cluster recovery and prediction, with particularly parsimonious selections on most real datasets, although it lacks a theoretical consistency guarantee.
Synthetic Data
- On synthetic data with planted K = 4, FIC+BP and F2AB outperformed other methods, and F2AB’s cluster-count detection was more accurate and stable, especially for small N.The experiment used Kmax = 20 and reported means and standard deviations across 10 random seeds in Figure 2.Source: Figure 2 · p. 8, §6 · p. 8
Real Networks
- F2AB achieved the best prediction with the smallest K in most real datasets; versus FIC+BP, prediction was equivalent while K was 2–4 times smaller.The real-network results cover eight datasets; the comparison attributes the K difference to the objective function, specifically R2.Source: Table 3 · p. 9, §6 · p. 9
- The real-network evaluation masked 1% of edges for testing; cICL exceeded 48 hours on most datasets, while FIC+BP and F2AB significantly outperformed other methods in prediction on five datasets.The study used five random seeds for its real-network results.Source: §6 · p. 9, Table 3 · p. 9
Discussion
- F2AB lacks a consistency guarantee because it uses BP and a lower bound, despite empirically selecting better models than the other methods.The authors suggest sparse-graph message-loop behavior and initialization from a large Kmax as possible reasons for its empirical performance.Source: §6 · p. 9
A. Proof of Theorem 3
The proof evaluates the Hessian and marginalization terms needed for Theorem 3’s asymptotic expansion. It uses Laplace’s method where its conditions hold and exact integrals in specified boundary cases.
A. Proof of Theorem 3
- The Hessian of the negative maximum log-likelihood is block diagonal, with a diagonal Θ submatrix containing K(K + 1)/2 elements.The proof attributes the zero off-diagonal blocks to the lack of interaction between Θ and η in the log-likelihood.Source: A. Proof of Theorem 3 · p. 12
- For θkl marginalization, the proof uses Laplace’s method when the relevant cluster and bicluster counts are positive, but retains the exact integral at the endpoint case.When either cluster is empty, the likelihood contribution is one and the integral reduces to prior marginalization.Source: A. Proof of Theorem 3 · p. 13
- Combining the marginalization lemmas yields the asymptotic expansion of ln p(X, Z).Source: A. Proof of Theorem 3 · p. 14