Source-linked AI summary
A state-space mixed membership blockmodel for dynamic network tomography
Eric P. Xing, Wenjie Fu, Le Song
TL;DR
The paper tackles inference of latent semantics in social and biological networks whose interactions and roles change over time. It combines mixed-membership stochastic blockmodels with state-space dynamics, and reports dynamic role patterns across monk, Enron, and Drosophila networks.
Problem
Existing network inference techniques often assume each actor has one unique, invariant role, whereas dynamic networks can involve changing, context-specific roles and systematic rewiring.
Method
The paper proposes a Bayesian state-space mixed-membership blockmodel with time-evolving role vectors and role-compatibility functions, learned using approximate inference.
Results
Applied to Sampson’s monks, Enron email, and Drosophila gene networks, the model reveals patterns of actors’ dynamic roles and changing biological themes.
Takeaways & Limitations
The model provides an expressive framework for tomographic analysis of evolving networks in which actors can fractionally carry multiple roles that change over time.
Takeaways & Limitations
The algorithm scales quadratically with network nodes and is aimed at meso-level networks with thousands, rather than mega-level networks with millions, of nodes.
Abstract
from arXiv · showhide
In a dynamic social or biological environment, the interactions between the actors can undergo large and systematic changes. In this paper we propose a model-based approach to analyze what we will refer to as the dynamic tomography of such time-evolving networks. Our approach offers an intuitive but powerful tool to infer the semantic underpinnings of each actor, such as its social roles or biological functions, underlying the observed network topologies. Our model builds on earlier work on a mixed membership stochastic blockmodel for static networks, and the state-space model for tracking object trajectory. It overcomes a major limitation of many current network inference techniques, which assume that each actor plays a unique and invariant role that accounts for all its interactions with other actors; instead, our method models the role of each actor as a time-evolving mixed membership vector that allows actors to behave differently over time and carry out different roles/functions when interacting with different peers, which is closer to reality. We present an efficient algorithm for approximate inference and learning using our model; and we applied our model to analyze a social network between monks (i.e., the Sampson's network), a dynamic email communication network between the Enron employees, and a rewiring gene interaction network of fruit fly collected during its full life cycle. In all cases, our model reveals interesting patterns of the dynamic roles of the actors.
1. Introduction.
The paper addresses inference for time-evolving networks whose latent roles and interaction mechanisms can change across time and context. It proposes a Bayesian dynamic mixed-membership model, approximate inference algorithm, and applications to social, email, and gene networks.
- Network tomography seeks latent social roles, biological functions, and other semantic underpinnings from observed network structure.
- Dynamic biological and social networks can undergo systematic temporal rewiring rather than behaving as independent samples from one fixed distribution.
- The proposed Bayesian approach represents each actor with a time-evolving mixed-membership vector supporting context-specific roles in heterogeneous networks.
- The model combines a modified mixed membership stochastic blockmodel with a state-space model to embed actors in a latent tomographic space.
- A variational EM algorithm supports approximate learning, and the model is demonstrated on Sampson’s monks, Enron email, and Drosophila gene networks.
2. Related work.
The related work connects descriptive and generative network models with mixed-membership representations and state-space methods for evolving latent structures.
- Earlier network models include ERGMs, stochastic blockmodels, and latent space models for describing structure and actor positions.
- The mixed membership stochastic blockmodel allows each node to belong to multiple blocks and has been applied to role identification and functional prediction.
- State-space models have been used to extract evolving topical themes and author embeddings, motivating their use for functional changes in network entities.
3. Modeling dynamic network tomography.
The dynamic model represents actors’ changing role mixtures and role compatibilities through a logistic-normal mixed-membership blockmodel embedded in a state-space framework. Its generative process produces time-indexed network links from latent role interactions and supports tracking functional changes and function themes.
- Model assumptions: The model assumes a fixed vertex set whose links may change across time, with each vertex represented by a time-varying mixed-membership vector.
- Static mixed membership model: Each link draws one latent role for each endpoint and then uses the corresponding role-pair compatibility coefficient to generate a Bernoulli interaction.
- Static mixed membership model: Actors can instantiate different roles with different neighbors, while the compatibility matrix encodes affinities among role pairs and can express richer block patterns.
- Dynamic model: The dynamic model infers trajectories of role vectors while allowing both role-weight priors and role-compatibility functions to evolve over time.
- Dynamic model: The state-space construction tracks functional changes in network entities and detects the emergence and termination of function themes.
- Graphical model: Figure 1 depicts the graphical model for the dynamic logistic-normal mixed-membership stochastic blockmodel, including a logistic-normal MMSB component.
4. Variational inference.
The paper develops variational inference and learning procedures for the logistic-normal MMSB and its dynamic extension, combining approximate latent-variable inference with state-space smoothing. The coupled updates iterate to convergence, while multiple random restarts are used to seek a near-global optimum.
- Variational approximation: Exact posterior inference and direct EM estimation are infeasible because marginalization is over a super-exponential latent state space and logistic-normal integration lacks a closed form.The method therefore uses variational and Laplace approximations.
- Variational approximation: The GMF scheme approximates the joint posterior with factored marginals for role variables and interaction indicators, while optimizing the coupled marginals through iterative updates.The factorization separates role-vector variables from dyad-level role indicators, and each marginal update depends on the others.
- Variational approximation: Interaction indicators use a multinomial marginal with K × K outcomes, whereas role-vector marginals require further approximation because the normalization constant makes them nonintegrable in closed form.A Laplace approximation converts the role-vector marginal into a reparameterized multivariate normal distribution.
- Parameter estimation: Parameter learning uses an EM-style procedure: posterior latent-variable expectations are computed in the E-step, and parameters are re-estimated by approximate log-likelihood maximization in the M-step.Under the logistic-normal MMSB, variational EM supplies the required likelihood approximation.
- Dynamic extension: For dMMSB, time-evolving means are estimated with a state-space model using mixed-membership estimates as emissions, followed by Kalman filtering and Rauch–Tung–Striebel smoothing.The posterior mean of the time-varying state replaces the static mean in the MMSB inference equations.
- Convergence: The variational algorithm is a fixed-point iteration that converges to a local optimum, so multiple random restarts are used to obtain a near-global optimum.Inference stops when the relative change in log-likelihood is less than 10^-6 in absolute value, and the best-likelihood result is selected.
5. Experiments.
Experiments show that LNMMSB recovers latent roles and compatibility structures in synthetic networks, while dMMSB improves estimation by integrating temporal information. Applications to monk and Enron networks reveal interpretable role mixtures and temporal changes associated with organizational restructuring.
- Synthetic networks: Synthetic experiments show that mixed membership vectors are well recovered when actors have dominant roles and same-role connections.
- Synthetic networks: With off-diagonal role compatibility, LNMMSB still accurately estimates both the compatibility matrix and actors’ mixed membership vectors.
- Synthetic networks: In the hardest synthetic setting, fewer than 10 percent of actors have more than 20 percent role-vector errors, while group structure remains clear.
- Model comparisons: LNMMSB and Dirichlet MMSB have comparable goodness of fit, with LNMMSB slightly better, while their inferred membership accuracy is practically similar.
- Model comparisons: dMMSB has lower mixed-membership estimation error than static MMSB in most cases and about 10 percent lower error on average.The authors attribute this improvement to integrating information across the temporal domain.
- Sampson’s monk network: In the Sampson network, three roles align with Young Turks, Loyal Opposition plus Waverers, and Outcasts plus a Waverer; three roles are favored by BIC.
- Sampson’s monk network: Dynamic monk memberships changed most between times 1 and 2, then fluctuated less; later purification indicated increasing group isolation before conflict.
- Enron email network: Enron roles distinguish inactivity, same-role cliques, receiver and sender-receiver functions, and executives or managers occupying multiple active roles.
6. Discussion.
The dMMSB provides detailed, temporally varying tomographical information by modeling actors with dependent, fractional, and time-varying roles. Its logistic normal prior supports these features, while the method remains targeted at meso-level networks and has several stated limitations.
- The dMMSB reveals detailed tomographical information about every actor and relation in dynamic social or biological networks.
- Actors can have dependent internal role structures, fractional assignments to multiple roles, and temporally varying mixed memberships.Together, these features provide greater expressive power for modeling rich temporal phenomena.
- The model captures related biological interaction themes across development, including wing and muscle development, and supports understanding of biological processes.The paper motivates this capability by noting that these themes are tightly related and change during an organism’s developmental cycle.
- The logistic normal prior encodes dependencies between roles and couples mixed membership vectors to a state-space model for tracking role evolution.Because it is nonconjugate to the multinomial distribution, the method uses an efficient Laplace variational inference algorithm.
- The algorithm scales quadratically with network nodes and roles and linearly with time steps, handling networks of approximately 10^3 nodes within a day.The implementation targets meso-level networks with thousands of nodes rather than mega-networks with millions.
- The current model does not explicitly represent hubs or cliques, and its state-space component smooths only the mixed-membership prior rather than the vector directly.
A.1. Taylor approximation.
This appendix section approximates the logistic-normal normalization term with a second-order Taylor expansion, retaining linear and quadratic terms for tractable inference.
- The approximation replaces C(γ_i) with a second-order Taylor expansion around a point ˆγ.The derivation temporarily drops the actor subscript for simplicity.
- The Taylor expansion retains only linear and quadratic terms, yielding the stated approximation to equation (12).
- The resulting q_z expression is a 1×K row vector, while S = −(N − 1)H is a symmetric K × K matrix.The passage identifies g as a K × 1 first-derivative vector and H as a K × K second-derivative matrix.
A.2. Learning on logistic-normal MMSB.
The logistic-normal MMSB learning derivation rewrites the log-likelihood and uses Jensen’s inequality to obtain a tractable optimization problem with an approximate estimator for B.
- The log-likelihood is expressed as a function of B for the logistic-normal MMSB.
- Jensen’s inequality produces an analytical lower bound whose stationary point gives an approximate maximum-likelihood estimator of B.
- The approximation makes learning tractable by replacing direct log-likelihood optimization with optimization of the derived bound.
A.3. Learning on dMMSB.
The dMMSB learning derivation uses an approximation to the log-likelihood and updates B by maximizing the resulting upper bound.
- The dMMSB derivation again approximates the log-likelihood to obtain a more tractable objective.
- Learning therefore combines an approximated likelihood with bound maximization for parameter updating.
- The update equation for B is obtained by maximizing the upper bound of the log-likelihood.