Source-linked AI summary
Overlapping stochastic block models with application to the French political blogosphere
Pierre Latouche, Etienne Birmelé, Christophe Ambroise
TL;DR
Existing network-clustering methods often impose disjoint memberships even though vertices may belong to multiple groups, motivating a more flexible network model. The paper proposes the Overlapping Stochastic Block Model, develops variational approximate inference, and reports identifiability and efficiency comparisons using simulated and real networks.
Problem
Many graph-clustering methods partition vertices into disjoint clusters, although real-world objects can belong to multiple groups; MMSB does not let all memberships of an endpoint influence an edge.
Method
The Overlapping Stochastic Block Model assigns each vertex a latent binary membership vector and uses global and local variational techniques in an EM-like parameter-inference procedure.
Results
The model is identifiable within classes of equivalence and is reported efficient for detecting overlapping clusters in simulated data and two real networks.
Takeaways & Limitations
The model provides a network-specific approach for retrieving overlapping clusters while allowing varied topological structures through unrestricted connection-characterizing parameters.
Takeaways & Limitations
The experiments set the number of classes Q using prior network information, leaving automatic estimation of Q from topology as future work.
Abstract
from arXiv · showhide
Complex systems in nature and in society are often represented as networks, describing the rich set of interactions between objects of interest. Many deterministic and probabilistic clustering methods have been developed to analyze such structures. Given a network, almost all of them partition the vertices into disjoint clusters, according to their connection profile. However, recent studies have shown that these techniques were too restrictive and that most of the existing networks contained overlapping clusters. To tackle this issue, we present in this paper the Overlapping Stochastic Block Model. Our approach allows the vertices to belong to multiple clusters, and, to some extent, generalizes the well-known Stochastic Block Model [Nowicki and Snijders (2001)]. We show that the model is generically identifiable within classes of equivalence and we propose an approximate inference procedure, based on global and local variational techniques. Using toy data sets as well as the French Political Blogosphere network and the transcriptional network of Saccharomyces cerevisiae, we compare our work with other approaches.
1. Introduction.
Networks model interactions across scientific and social domains, but common clustering methods often force vertices into disjoint groups. The paper motivates and introduces an overlapping stochastic block model that supports multiple memberships while retaining network-specific edge dependencies.
- Networks represent interactions between objects in biological, metabolic, and social-science applications.
- Many clustering methods seek structures such as communities or disassortative mixing, but modularity-based methods can identify incorrect community structures.
- Existing graph clustering techniques commonly partition vertices into disjoint clusters, despite real-world objects such as proteins and actors belonging to multiple groups.
- MMSB permits overlapping memberships across relations, but each edge probability uses only one membership draw for each endpoint.
- The proposed model uses (Q + 1)^2 + Q parameters, assigns each vertex a latent binary membership vector, and makes edge probabilities depend on endpoint components.
- The paper establishes identifiability within equivalence classes, develops an EM-like variational inference procedure, and compares the model on simulated and real networks.
2. The stochastic block model.
The stochastic block model represents a directed binary network with latent vertex classes and class-specific connection probabilities. Its latent assignments are independent before conditioning, and the edges are conditionally independent given those assignments.
- The SBM represents a directed binary network with an adjacency matrix X and excludes self-loops.
- Each vertex receives a latent one-hot class label drawn from a multinomial distribution governed by class proportions α.
- Edges are drawn from Bernoulli distributions whose probabilities are specified by the Q × Q connectivity matrix Π.
- The latent vertex labels are independent and, conditional on them, all network edges are independent.
3. The overlapping stochastic block model.
The Overlapping Stochastic Block Model represents each vertex with multiple latent class memberships and models directed-edge probabilities from these memberships, sender/receiver effects, and sparsity.
- Each vertex has a latent vector of Q independent Boolean variables, allowing membership in multiple classes.
- Vertices with all latent membership indicators equal to zero provide a natural representation for outliers.
- Edge probabilities combine interactions between vertex memberships with class-dependent sender and receiver effects.The interaction term uses W, while U and V encode sender and receiver tendencies.
- Conditioned on the latent structure, all directed edges without self-loops are assumed independent.
- The model includes a scalar bias W* to represent sparsity arising either from generally rare interactions or from class-specific connectivity.
4. Identifiability.
The identifiability analysis characterizes when different OSBM parameters generate the same graph distribution, accounting for class reorderings and coordinate inversions. Generically, the model is identifiable up to the resulting equivalence relation.
- 4.1. Correspondence with (nonoverlapping) stochastic block models: OSBM parameters map naturally to an SBM with 2^Q classes because each Boolean membership vector encodes one SBM class.
- 4.2. Permutations and inversions: Permuting the Q OSBM classes and transforming α and f_W accordingly leaves the generative random graph model unchanged.
- 4.2. Permutations and inversions: Inverting selected membership coordinates is also an equivalent reparameterization because zeros and ones can exchange which vertices define a cluster.
- 4.3. Identifiability: Two parameters in the same equivalence class induce the same graph measure, and each class contains an ordered representative.
- 4.3. Identifiability: When the α_i values are distinct and strictly below 1/2, that ordered representative is unique.
- 4.3. Identifiability: The main theorem states that OSBM is generically identifiable up to the equivalence relation generated by these transformations.
5. Statistical inference.
Inference maximizes a tractable variational lower bound because the exact OSBM likelihood and network posterior are intractable. The resulting variational EM procedure alternates updates of latent memberships and model parameters.
- The exact likelihood marginalization involves 2^NQ terms and quickly becomes intractable.
- The network posterior cannot be factorized, so the method restricts optimization to a tractable variational family.
- Each τ_iq variational parameter represents the posterior probability that node i belongs to class q.
- Because the logistic sigmoid is nonlinear, a second approximation using ξ_ij is required to compute the lower bound.
- The variational EM algorithm alternates updates of posterior probabilities τ_i and parameters α and f_W while maximizing the approximated lower bound.
- The algorithm costs O(N^2Q^4), compared with O(N^2Q^2) for cited nonoverlapping SBM methods.
6. Experiments.
Experiments compare OSBM with CFinder, SBM, and MMSB on simulated, political-blog, and yeast transcription networks. OSBM accurately recovers overlapping structure and remains effective on heterogeneous and complex topologies.
- Experimental design: The experiments compare OSBM with CFinder, SBM, and MMSB across simulated and real networks.The real networks are the French political blogosphere and Saccharomyces cerevisiae transcriptional regulatory network.
- Simulations: Using 100 simulated community-structure networks, OSBM achieved a median L2 distance of 0, versus 22 for CFinder and 27.5 for MMSB.CFinder and MMSB estimated clusters accurately overall but showed slight bias, while SBM could not retrieve overlapping clusters.
- Simulations: On networks combining community structures and stars, OSBM had median L2 distance 43, compared with 354.5 for CFinder.OSBM remained more stable as CFinder degraded, while MMSB also deteriorated but remained better than SBM.
- French political blogosphere: In the French political blogosphere, OSBM found homogeneous party-related clusters and nine overlaps, including links among UMP, UDF, PS, liberal, and analyst blogs.The observed overlaps were consistent with known relational ties among parties and political analysts.
- French political blogosphere: MMSB produced similar blog clusters and recovered five of OSBM’s eight overlaps, whereas SBM assigned multi-party analyst blogs to single clusters.Because SBM permits only one cluster per vertex, it misses overlapping relational information.
- Saccharomyces cerevisiae transcription network: In the yeast transcriptional network, OSBM recovered biologically meaningful clusters and overlapping co-regulated operons, while CFinder performed poorly on the sparse network.MMSB and SBM recovered the six clusters, but MMSB uncovered no overlaps.
7. Conclusion.
The paper introduces OSBM for retrieving overlapping network clusters, combines variational inference with an EM-like optimization, and reports identifiability and empirical efficiency. The authors note that automatic selection of the number of classes remains an important future need.
- OSBM retrieves overlapping clusters in networks while allowing varied topological structures through unconstrained connection-probability parameters.The model uses latent binary membership vectors and allows each vertex to belong to several components.
- Global and local variational techniques produce a tractable lower bound of the observed log-likelihood for an EM-like parameter optimization procedure.
- The model is identifiable within classes of equivalence and is reported efficient relative to other methods on simulated and real networks.
- The experiments set the number of classes Q using prior network information rather than estimating it automatically from topology.
- The authors identify automatic model selection for the number of classes as a crucial direction for future work.
SUPPLEMENTARY MATERIAL
The supplement explains how global and local variational techniques yield a tractable lower bound and presents the inference procedure’s optimization equations.
- The supplement describes the variational construction of a tractable lower bound for the observed log-likelihood.
- It introduces the optimization equations used by the inference procedure.