Source-linked AI summary
Variational Bayesian Inference and Complexity Control for Stochastic Block Models
Pierre Latouche, Etienne Birmele, Christophe Ambroise
TL;DR
SBM lacks a satisfactory criterion for estimating the number of classes, while existing likelihood-based approaches are limited by intractability or asymptotic approximations. The paper introduces ILvb, a non-asymptotic marginal-likelihood criterion derived through variational Bayes EM, and reports improved class-number estimation over ICL in experiments.
Problem
SBM lacks sufficient model-based criteria for estimating the number of classes, with ICL relying on an asymptotic integrated complete-data likelihood approximation.
Method
The paper uses variational Bayes EM to approximate the full posterior and derive ILvb as a non-asymptotic approximation to the marginal likelihood.
Results
ILvb estimates the true number of classes more accurately than ICL in reported experiments, including 99 versus 77 correctly estimated networks when Q_true = 5.
Takeaways & Limitations
The Bayesian framework provides a density-focused criterion for estimating latent class numbers in SBM networks.
Takeaways & Limitations
The variational model-selection approximation assumes a KL divergence that cannot be computed analytically and whose closeness to zero is not established.
Abstract
from arXiv · showhide
It is now widely accepted that knowledge can be acquired from networks by clustering their vertices according to connection profiles. Many methods have been proposed and in this paper we concentrate on the Stochastic Block Model (SBM). The clustering of vertices and the estimation of SBM model parameters have been subject to previous work and numerous inference strategies such as variational Expectation Maximization (EM) and classification EM have been proposed. However, SBM still suffers from a lack of criteria to estimate the number of components in the mixture. To our knowledge, only one model based criterion, ICL, has been derived for SBM in the literature. It relies on an asymptotic approximation of the Integrated Complete-data Likelihood and recent studies have shown that it tends to be too conservative in the case of small networks. To tackle this issue, we propose a new criterion that we call ILvb, based on a non asymptotic approximation of the marginal likelihood. We describe how the criterion can be computed through a variational Bayes EM algorithm.
1 Introduction
SBM provides a framework for clustering network vertices by connection profiles, but estimating the number of classes remains difficult because standard observed-data likelihood criteria are intractable. The paper introduces ILvb, a non-asymptotic marginal-likelihood criterion computed through variational Bayes EM.
- Existing network models: SBM-related models cluster vertices according to community, disassortative, or mixed connection structures.These approaches cover assortative networks, bipartite structures, and models combining both patterns.
- Existing inference methods: SBM inference jointly estimates model parameters and vertex clusters, but latent-variable dependencies prevent direct use of standard EM.The conditional distribution of latent variables and parameters does not factorize given the observed network.
- Model selection gap: Estimating the number of SBM classes remains unresolved because BIC and AIC rely on an intractable observed-data likelihood, while ICL uses an asymptotic complete-data approximation.ICL is described as the only previously developed model-based criterion for SBM.
- Proposed criterion: ILvb selects SBM complexity using the marginal likelihood p(X), also called the integrated observed-data likelihood.The criterion is motivated by the marginal likelihood’s focus on density estimation.
- Proposed criterion: The paper computes ILvb through a variational Bayes EM algorithm using a non-asymptotic approximation of the marginal likelihood.The paper also introduces non-informative conjugate priors and evaluates ILvb on simulated and biological networks.
2 A Mixture Model for Graphs
The SBM assigns each vertex to one latent class and generates binary edges according to class-pair connection probabilities. Its Bayesian formulation places conjugate priors on class proportions and the connection matrix.
- Model and notations: SBM represents a network as an N × N binary matrix, focusing here on undirected relations so X is symmetric.Directed graphs and self-loops require modified product terms and treatment of diagonal edges.
- Model and notations: Each vertex receives a single latent class indicator drawn from a multinomial distribution.Z_iq = 1 indicates that vertex i belongs to class q.
- Model and notations: Conditional on the latent classes, edges are independent Bernoulli variables governed by the Q×Q connection-probability matrix π.The model therefore permits distinct probabilities for different pairs of latent classes.
- Model relationships: Unlike mixed-membership models, SBM assumes each vertex belongs to one class rather than having a distribution over classes.The affiliation model is a constrained SBM in which within-class and between-class probabilities are λ and ϵ.
- Bayesian formulation: The Bayesian SBM assigns a Dirichlet prior to class proportions and independent Beta priors to entries of π.These are specified as non-informative conjugate priors.
- Bayesian formulation: The model parameters become random variables whose distributions depend on fixed hyperparameters.The hyperparameters are omitted from later conditional-distribution notation for simplicity.
3 Estimation
Because SBM’s latent-variable posterior is intractable, the paper uses variational approximations to estimate clusters and parameters. Variational Bayes EM approximates the full posterior and supplies a lower bound later used for model selection.
- Variational estimation: The observed-data likelihood marginalizes over Q^N latent assignments, making direct computation quickly intractable.This motivates variational inference within the EM framework.
- Variational EM: Variational EM factorizes the latent assignment distribution and alternates parameter-fixed and assignment-fixed lower-bound maximization steps.The variational parameters τ_iq represent the probability that node i belongs to class q.
- Variational Bayes EM: Variational Bayes EM approximates the full posterior distribution of latent assignments and model parameters given the observed network.The factorized approximation covers q(Z), q(α), and q(π).
- Variational Bayes EM: The algorithm optimizes q(Z_i) in its variational Bayes E-step and q(α), q(π) in its variational Bayes M-step.The optimization equations and lower bound are provided in the appendix.
- Algorithm implementation: Initialization uses hierarchical clustering with Ward distance, followed by iterative updates until successive lower-bound values differ by less than a threshold.The experiments use eps = 1e-6; the reported computational cost is O(Q^2N^2).
4 Model selection
The paper selects the number of SBM classes by replacing the marginal log-likelihood with a variational Bayes approximation. After variational Bayes EM convergence, the resulting ILvb criterion is maximized across candidate class counts, without relying on an asymptotic approximation.
- Variational approximation: For each candidate Q, variational Bayes EM maximizes a lower bound that approximates the marginal log-likelihood when the KL divergence is small.The lower bound is optimized with respect to the variational distribution q(.).
- Variational approximation: The approximation is adopted as a tractable model-selection criterion despite the KL divergence being analytically unavailable and potentially dependent on model complexity.The paper explicitly notes that the small-divergence assumption cannot be verified in practice.
- ILvb criterion: After convergence, the lower bound yields the new SBM criterion ILvb, whose parameters include estimated class-membership probabilities τiq.The remaining quantities are defined as model parameters in the appendix.
- ILvb criterion: ILvb differs from Daudin et al.'s criterion because it does not use an asymptotic, BIC-like approximation.This makes ILvb a non-asymptotic alternative for SBM model selection.
- Model selection: In practice, variational Bayes EM is run for each considered Q, and Q* is selected by maximizing ILvb.The selected class count is therefore determined by comparing the criterion across candidate mixture sizes.
5 Experiments
Experiments compare VBMOD, ICL, and ILvb on simulated networks and the metabolic network of Escherichia coli. ILvb is more reliable than ICL for small graphs, while performance depends on network topology and the comparison method.
- Experimental design: The experiments assess ILvb against ICL and VBMOD using simulated networks and the metabolic network of Escherichia coli.The evaluation targets both synthetic structures and a real metabolic network.
- Affiliation networks: On affiliation networks with 100 small graphs per true class count, VBMOD outperforms ICL and ILvb; at QTrue = 5, accuracies are 100, 77, and 99, respectively.The networks contain N = 50 vertices, with λ = 0.9 and ϵ = 0.1.
- Networks with community structures and hubs: For networks containing community structures and hubs, VBMOD often misses the hub class, whereas ICL and ILvb behave more consistently.VBMOD always misses a class when QTrue = 3 or QTrue = 4, while ILvb remains more stable as the number of true classes increases.
- Networks with community structures and hubs: In small graphs, ILvb provides a more reliable class-count estimate than ICL for density estimation and outperforms VBMOD when classes are not communities.This conclusion is stated for the tested small-graph settings.
- The metabolic network of Escherichia coli: For the Escherichia coli network, ILvb selects QILvb = 22 classes versus QICL = 21, while the Bayesian and frequentist partitions show similar patterns.The network has 605 vertices and 1,782 edges; eight inferred classes are cliques and six have within-class connectivity above 0.5.
6 Conclusion
The paper develops a full Bayesian SBM framework with variational Bayes EM and introduces ILvb, a non-asymptotic criterion for estimating latent classes. Experiments show ILvb estimates data density and class number effectively across network structures.
- 6 Conclusion: The framework places SBM in a full Bayesian setting with non-informative conjugate priors and variational Bayes EM for approximating latent-variable and parameter posteriors.The posterior approximation is conditioned on the observed data.
- 6 Conclusion: ILvb is a non-asymptotic model-selection criterion that approximates the marginal likelihood.It is derived within the variational Bayesian framework.
- 6 Conclusion: ILvb focuses on estimating data density and provides a relevant estimate of the number of latent classes for networks generated using SBM.
- 6 Conclusion: The SBM retrieves interesting structures in varied networks, unlike algorithms that search only for community structures.
- 6 Conclusion: The metabolic-network visualization represents 605 vertices classified into QV B = 22 classes, with shaded dots marking edges.
A Approximation of q(Zi) the conditional distribution of the latent variables
The variational approximation for each latent-variable distribution is multinomial, parameterized by vertex-specific class responsibilities. A fixed-point iteration updates and normalizes these responsibilities until convergence.
- A Approximation of q(Zi) the conditional distribution of the latent variables: The optimal approximation q(Zi) is a multinomial distribution parameterized by responsibilities τi1 through τiQ.
- A Approximation of q(Zi) the conditional distribution of the latent variables: τiq represents the probability, or responsibility, that node i belongs to class q.
- A Approximation of q(Zi) the conditional distribution of the latent variables: A fixed-point algorithm updates each row of τ from τ old to τ new using the responsibility relation, followed by normalization.
- A Approximation of q(Zi) the conditional distribution of the latent variables: The algorithm repeatedly rebuilds τ from the normalized matrix and stops when the update difference falls below eps.The experiment section sets eps = 1e −6.
- A Approximation of q(Zi) the conditional distribution of the latent variables: The normalized variational update yields the multinomial distribution in equation (A.1).
B Optimization of q(α).
Variational optimization preserves the functional forms of the priors for both q(α) and q(π). The resulting normalized distributions are Dirichlet for q(α) and products of Beta distributions for q(π).
- B Optimization of q(α).: Optimizing the lower bound with respect to q(α) produces a distribution with the same functional form as the prior p(α).
- B Optimization of q(α).: After exponentiation and normalization, q(α) becomes a Dirichlet distribution.
- B Optimization of q(α).: The optimization of q(π) likewise conserves the functional form of the prior p(π).
- B Optimization of q(α).: After exponentiation and normalization, q(π) becomes a product of Beta distributions.
D Lower bound.
After the variational Bayes M-step, the lower bound simplifies substantially. It depends on the posterior responsibilities and the normalizing constants of the Dirichlet and Beta distributions.
- D Lower bound.: After the variational Bayes M-step, the lower bound depends on posterior probabilities τiq and distribution normalizing constants.
- D Lower bound.: The lower bound is expressed through expected log-likelihood, latent-class, and prior terms before simplification.
- D Lower bound.: Most terms vanish after the variational Bayes M-step.
- D Lower bound.: Only terms involving τiq and the Dirichlet and Beta normalizing constants remain.