Mixed membership stochastic blockmodels

Edoardo M Airoldi; David M Blei; Stephen E Fienberg; Eric P Xing

Source-linked AI summary

Mixed membership stochastic blockmodels

Edoardo M Airoldi, David M Blei, Stephen E Fienberg, Eric P Xing

arXiv:0705.4485v1May 30, 2007stat.MEcs.LGmath.STphysics.soc-phstat.ML

TL;DR

Relational data require models that address limitations of existing mixed membership approaches. This paper introduces mixed membership stochastic blockmodels and develops variational inference, with applications identifying tightly interacting protein complexes and their functional-category relationships.

Problem
Existing mixed membership models are not appropriate for relational data because they assume that [passage incomplete].
Method
The paper introduces mixed membership stochastic blockmodels, latent-variable models for relational data, and develops a fast variational inference approach.
Results
The MMSB identifies protein complexes whose member proteins are tightly interacting and whose complexes correlate with functional categories.
Takeaways & Limitations
The results support using mixed membership stochastic blockmodels to identify relational structure in protein interaction data.
Takeaways & Limitations
The model does not readily generate hubs, meaning nodes connected with a large number of [connections].

Abstract

from arXiv · show

Observations consisting of measurements on relationships for pairs of objects arise in many settings, such as protein interaction and gene regulatory networks, collections of author-recipient email, and social networks. Analyzing such data with probabilisic models can be delicate because the simple exchangeability assumptions underlying many boilerplate models no longer hold. In this paper, we describe a latent variable model of such data called the mixed membership stochastic blockmodel. This model extends blockmodels for relational data to ones which capture mixed membership latent relational structure, thus providing an object-specific low-dimensional representation. We develop a general variational inference algorithm for fast approximate posterior inference. We explore applications to social and protein interaction networks.

1 Introduction

Relational data violate classical independence assumptions, motivating models that represent interdependent objects and multiple latent roles. The paper develops mixed membership stochastic blockmodels and variational inference, then applies them to social and protein interaction networks.

Motivation: Relational observations are interdependent, so standard clustering methods assuming conditional independence given cluster assignments are not directly applicable.The paper frames relational analysis as requiring special-purpose statistical machinery.
Motivation: Latent stochastic blockmodels represent dyadic data but restrict each object to one cluster or latent role.Relationships are governed by the corresponding pair of clusters.
Contribution: The paper relaxes the single-latent-role assumption and develops mixed membership models for relational data.The approach is intended to describe interactions between objects playing multiple roles.
Mixed membership: Mixed membership models associate each object with multiple clusters through a membership probability-like vector, capturing different aspects or latent roles.This formalism is natural for relational data because multiple roles can influence an object’s relationships.
Contribution: The authors develop a fast variational inference algorithm and demonstrate the method on large-scale protein interaction and social networks.Applications include a student friendship network and a protein interaction network used for dimensionality reduction and functional information.
Results: Mixed membership and latent block structure can be reliably recovered from relational data, while applications reveal structure in friendship and protein interaction networks.The protein application examines whether the model can inform subsequent analyses through substantive protein-function information.

2 The mixed membership stochastic blockmodel

The mixed membership stochastic blockmodel represents each object with a distribution over latent groups and models pairwise relations through context-dependent group roles. It supports directed, sparse, and multiple-network relational data while enabling posterior inference and low-dimensional object representations.

Model specification: MMSB represents binary relational observations as a directed graph, while its interaction matrix B can parameterize broader observation distributions.The paper notes applications to probabilistic protein-interaction measurements as well as manually curated binary interactions.
Model specification: MMSB assigns each node a mixed membership vector, allowing simultaneous affiliation with multiple latent groups at different strengths.Group-to-group interaction probabilities are encoded in a Bernoulli matrix B, whose entries specify link probabilities between groups.
Model specification: For each directed interaction, the model draws separate group indicators for the node initiating the interaction and the node being approached.This context-dependent membership permits asymmetric networks; equality can be imposed for symmetric interactions.
Model extensions: The model can generate multiple networks among the same actors from shared latent vectors, including paired positive and negative sociometric relations.Examples include esteem and disesteem, liking and disliking, and positive and negative influence or praise.
Inference: Variational inference approximates the otherwise intractable marginal likelihood for parameter estimation and posterior inference over memberships and pairwise roles.The posterior membership vectors provide a low-dimensional representation of the underlying objects.
Modeling sparsity: A sparsity parameter ρ calibrates how much non-interactions contribute, modeling whether absent edges reflect general interaction rarity rather than group incompatibility.This addresses settings where many node pairs lack edges and non-interactions may otherwise influence membership and interaction estimates equally.

3 Parameter Estimation and Posterior Inference

The paper develops mean-field variational inference and empirical Bayes estimation for MMSB parameters, addressing intractable posterior computation. A nested update schedule improves convergence behavior and reduces per-cycle memory for large graphs.

Posterior inference and estimation: MMSB inference estimates node mixed-membership vectors, per-pair roles, Dirichlet parameters, and the Bernoulli rate matrix.The approach uses empirical Bayes for (α, B) and mean-field approximation for posterior inference.
Variational approximation: Mean-field variational inference provides a deterministic alternative to MCMC for approximating the posterior distribution.The method posits a fully factorized family whose free parameters are optimized to tighten a Jensen lower bound and minimize KL divergence to the true posterior.
Nested variational inference: The nested variational scheme changes the update schedule to preserve dependence among variational parameters and improve convergence in relational data.It keeps the per-pair parameters optimized conditional on other variational parameters, while the naïve algorithm often failed to converge or required many iterations.
Nested variational inference: NK + 2K scalars are allocated per variational cycle by the nested algorithm, compared with NK + 2N^2K for the naïve scheme.The nested method trades time for space and is intended to support large graphs.
Empirical behavior: The nested algorithm can be parallelized and leads to empirically observed faster convergence rates, with lower memory requirements than MCMC variants.The paper compares the naïve and nested variational schemes empirically and describes the nested approach as better than blocked and collapsed Gibbs samplers on memory and convergence rates.
Parameter estimation: Variational EM alternates between fitting q to approximate the posterior and maximizing the corresponding likelihood lower bound with respect to model parameters.The M-step uses expected sufficient statistics under the variational distribution; empirical Bayes guides inference toward hyperparameter regions supported by the data.

4 Experiments and Results

Simulations recover mixed memberships and latent block structure, while nested variational inference reaches higher likelihood efficiently. Social and protein-network applications show that MMSB summarizes relational structure and supports interpretation and prediction.

4.1 Simulations: Simulations recover both mixed membership vectors and latent block structure, while nested variational inference reaches a higher likelihood peak than the naïve implementation.The nested algorithm is reported as fast as the naïve implementation and more efficient in space.
4.2 Social Network Analysis: In the student friendship network, the model recovers a block structure interpretable in terms of grades, while few students display mixed membership.The analysis decouples observed friendship patterns into connectivity and membership-related variability and can produce node-specific predictions.
4.1 Simulations: As α increases, nodes belong to more clusters, making the reordered simulated interaction matrices’ block structure less evident.The estimated reordering nevertheless reveals the original blockmodel across the tested data settings.
4.3 Protein Interaction Network: In the protein network, inferred protein complexes tightly interact and correlate with four broad functional categories, supporting functional-annotation prediction.The inferred latent structure summarizes the interaction collection and captures biological signal at a scale higher than protein complexes.
4.3 Protein Interaction Network: Posterior mixed memberships and group-connectivity patterns provide a dimensionality-reduced summary of the MIPS collection with high precision.The authors report that the latent block structure helps rank interactions, while noting that lower-recall estimated networks can have more precise functional content.

5 Discussion

The discussion situates MMSB among relational-data models, emphasizing its representation of multiple roles, interpretable interaction-specific memberships, scalable inference, and known structural limitations.

Modeling context: MMSB relates to latent space models through the interaction probability π_p'Bπ_q, but uses Dirichlet latent vectors and a Bernoulli data distribution.Latent space models instead use Gaussian latent vectors and Gaussian interaction data with mean π_p'Iπ_q.
Inference and interpretation: The scalable variational inference algorithm is developed for analyzing large network structures, in contrast to MCMC-based posterior inference in latent space models.The algorithm is presented as a fast approximate approach for relational data.
Inference and interpretation: Retaining interaction-specific latent membership indicators preserves interpretable posterior quantities useful for prediction, denoising, and new measurements.In protein-interaction applications, these memberships encode individual proteins’ memberships to protein complexes.
Limitations and extensions: MMSB can generate diverse local and global connectivity patterns but does not readily generate hubs or networks with skewed degree distributions.This limitation constrains the structural network patterns the model represents.
Limitations and extensions: The authors identify semi-supervised membership priors as a setting where changes from prior to posterior membership may signal biological phenomena worth investigating.They also note nonparametric extensions using stochastic processes and hierarchical Dirichlet processes to support mixed membership with potentially nonfinite groups.

6 Conclusions

The paper introduces mixed membership stochastic blockmodels as latent-variable tools for relational data and develops a parallelizable variational algorithm for fast approximate inference on large graphs.

Contributions: The paper introduces mixed membership stochastic blockmodels, a latent-variable model class for relational data represented as unipartite graphs.The model is presented as an exploratory tool for scientific analyses.
Contributions: The nested variational inference algorithm is parallelizable and enables fast approximate inference on large graphs.The paper develops this approach because relational applications involve large structures and multiple analytical goals.
Model formulation: The model introduces latent variables to capture application-specific substantive elements, such as monks and factions in a monastery.Similar relational structures across social and biological networks motivate a general formulation.
Model formulation: The model assumes K population classes, node-specific mixed-membership vectors, and conditionally independent response edges given those memberships.It also permits M independent replications of relations measured on the same population of nodes.
Model formulation: MMSB specifications allow different data types through the choice of f and allow parametric or semiparametric priors on the number of clusters through Dα.The general formulation is stated across population, node, latent-variable, and sampling-scheme levels.

B Details of the Variational Approximation

The appendix extends the variational EM framework to replicated, arbitrary-valued, multivariate relational data and multiple blockmodels with minor derivational changes.

Extensions: The inference framework addresses M replicated paired measurements whose relations can take values in an arbitrary metric space according to f.This extends the setting beyond a single binary relational response.
Extensions: Multivariate J-dimensional relations and multiple blockmodels B1:J can be handled with minor modifications to the derivations.Each blockmodel corresponds to a distinct relational response.

B.1 Variational Expectation-Maximization

Variational EM replaces an intractable posterior with a parametric approximation, optimizing a lower likelihood bound by alternating updates of model parameters and variational distributions.

Variational EM: The variational EM procedure lower-bounds p(Y|Θ) using Jensen’s inequality and alternately maximizes the bound over Θ and q.The M step updates parameters, while the E step updates the distribution over latent variables.
Variational EM: Because the exact posterior is not computable for the admixture of latent blocks model, the method uses a direct parametric approximation q̃=qΔ(X).The approximation introduces variational parameters Δ and an approximate lower bound LΔ(q,Θ).
Variational EM: At each E-step iteration, the variational approximation is optimized by minimizing its Kullback-Leibler divergence using the data.The resulting parametric approximation is a proper posterior conditional on the current parameter estimates.

B.2 Lower Bound for the Likelihood

Mean-field theory replaces the intractable distribution with a fully factored approximation, yielding an approximate likelihood lower bound whose variational parameters can be estimated.

Mean-field theory approximates the distribution defined by Equation (1) with a fully factored distribution q.
The approximation produces a lower bound for the likelihood that is optimized with respect to ∆.
The factorized approximation introduces Dirichlet and multinomial factors, with parameters collected in ∆.
Single-variable expectations provide the quantities needed to work with this lower bound.

B.3 The Expected Value of the Log of a Dirichlet Random Vector

The expected log of the Dirichlet random vector is derived by expressing the Dirichlet as an exponential-family distribution and applying its standard expectation identities.

The likelihood lower bound requires evaluating expectations involving the Dirichlet distribution.
The Dirichlet is rewritten as an exponential-family distribution with natural parameters θk(⃗α) = (αk −1).
Its natural sufficient statistics are tk(⃗π) = log(πk).
The resulting expectations use ψ(x), the derivative of the log-gamma function.

B.4 Variational E Step

The variational E step optimizes the approximate likelihood bound over latent-variable distributions while holding the model parameters fixed, using coordinate-ascent updates.

The variational E step maximizes the approximate lower bound using exponential-family arguments and coordinate ascent.
The update calculations use natural sufficient statistics and functions of the other latent variables and observations.
The resulting variational-parameter updates apply across node pairs and group indices.
At iteration t, the model parameters Θ(t−1) remain fixed while the optimal approximate bound is found.

B.5 Variational M Step

The variational M step estimates model and hyper-parameters from expected sufficient statistics, while separately addressing the concentration parameter and sparsity parameter ρ.

The M step derives empirical Bayes estimates for Θ by maximizing the optimized approximate likelihood bound.
The approximate maximum-likelihood estimate of ⃗α has no closed-form solution, so Newton-Raphson is used with linear-time gradient and Hessian calculations.
The block parameter B is estimated by maximizing its corresponding part of the approximate bound for every group pair.
The sparsity parameter ρ controls the relative importance of interaction presence and absence in likelihood-based inference and estimation.
ρ can be estimated from the bound or fixed before analysis using an estimator that assigns non-interactions to the point mass.
The fixed-ρ recipe reduces computational burden during exploratory analyses, while attributing non-interaction information to latent sources outside B or ⃗π1:N.