PaperlayerView exact revision on arXiv

Source-linked AI summary

A Review of Stochastic Block Models and Extensions for Graph Clustering

Clement Lee, Darren J Wilkinson

arXiv:1903.00114v2stat.MLcs.LG

TL;DR

In real-data applications, group memberships and the block matrix are unobserved, while longitudinal and textual information may also need incorporation into stochastic block models. The paper systematically reviews recent block-modelling approaches and extensions, finding that newer SBMs are usually collapsed and can enable the number of groups K to be selected or estimated. Its scope focuses on more recent work, and the usefulness of the degree-corrected SBM should not be overstated.

  • Problem

    In real-data applications, neither group memberships nor the block matrix is observed, and longitudinal or textual information may need incorporation into SBMs.

  • Method

    The paper systematically investigates block-modelling approaches and extensions to present the landscape of the literature.

  • Results

    Newer SBMs are usually collapsed, with algorithms enabling K to be selected or estimated, although an SBM has a maximum detectable K.

  • Takeaways & Limitations

    The systematic, cross-sectional review presents a concise landscape of recent block-modelling literature for comparing approaches and extensions.

  • Takeaways & Limitations

    The article focuses on more recent works, and the usefulness of the degree-corrected SBM should not be seen as universal.

Abstract

from arXiv · show

There have been rapid developments in model-based clustering of graphs, also known as block modelling, over the last ten years or so. We review different approaches and extensions proposed for different aspects in this area, such as the type of the graph, the clustering approach, the inference approach, and whether the number of groups is selected or estimated. We also review models that combine block modelling with topic modelling and/or longitudinal modelling, regarding how these models deal with multiple types of data. How different approaches cope with various issues will be summarised and compared, to facilitate the demand of practitioners for a concise overview of the current status of these areas of literature.

1 Introduction

This review surveys stochastic block models and their extensions for graph clustering, comparing how they address graph types, clustering, inference, model selection, and unknown group counts, including models combining networks with textual or temporal data.

  • Scope and motivation: SBMs model-based cluster graphs by assigning nodes to groups and relating edge probabilities to group memberships.The review presents SBMs as a framework for discovering latent network structure and clustering nodes.
  • Scope and motivation: Fitting an SBM to real data requires simultaneous inference of unobserved group memberships and the block matrix.Neither component is observed in typical applications.
  • Scope and motivation: The review organizes core challenges around realistic model structure, scalable inference, goodness-of-fit diagnostics, and selecting or estimating K.It discusses BIC, marginal likelihood, and whether K should be inferred within the model or chosen through model selection.
  • Review coverage: It compares developments across graph type, clustering approach, inference approach, and the treatment of the number of groups.The stated aim is to provide a concise overview of how different models handle these issues.
  • Multiple data types: The review also covers SBM extensions incorporating topic and longitudinal modelling when networks occur alongside textual or temporal information.Examples include email and citation data with network, text, and time components.
  • Scope boundary: Because topic and longitudinal modelling are large fields themselves, the article focuses on recent or relatively straightforward SBM extensions to them.The authors frame these interdisciplinary works as directions toward models handling multiple information types simultaneously.

2 Stochastic block models

A basic SBM represents a graph through an adjacency matrix, latent node memberships, and a block matrix of conditional edge probabilities. Conditional independence yields Bernoulli edge likelihoods and binomial block-edge counts, while stochastic equivalence motivates the model's grouping assumption.

  • Graph representation: A graph is represented by an adjacency matrix Y whose entries encode edges, with symmetry for undirected graphs and no self-edges assumed here.Directed graphs need not have symmetric adjacency matrices.
  • Block probabilities: The block matrix C assigns each pair of groups an edge probability, symmetric for undirected graphs but not necessarily for directed graphs.Its entries need not sum to one across rows or columns.
  • Likelihood: Given memberships, dyads are conditionally independent and each adjacency entry follows a Bernoulli distribution determined by the corresponding block probability.The Bernoulli SBM likelihood can be written over node pairs or, after reindexing, over group pairs.
  • Likelihood: The number of edges between any two blocks is binomial with mean equal to the block probability times the number of available dyads.The available dyads are NiNj/2 for undirected between-group pairs and NiNj for directed pairs.
  • Stochastic equivalence: Stochastic equivalence means nodes in the same group have equal, independent connection probabilities toward another node, without requiring stronger within-group connectivity.Community-detection settings may additionally favor larger diagonal entries in C.
  • Prior modelling: When memberships and block probabilities are unknown, the model requires assumptions about independent prior memberships and their multinomial probabilities.A Dirichlet distribution for θ with a Gamma prior on its parameter is also described.

3 Type of graph and extensions of the SBM

The SBM has developed from binary block models into extensions for valued, directed, signed, temporal, multilayer, and otherwise structured graphs. The review also highlights alternative clustering formulations, degree correction, and models that accommodate multiple data types.

  • Lineage: SBMs originated from deterministic blockmodels that reorder adjacency matrices into homogeneous zero and one submatrices.The stochastic generalization was formalized by Holland et al. (1983), followed by models where unknown groups are inferred statistically.
  • Clustering and group number: Alternative clustering approaches allow mixed membership, latent features, edge partitions, and models that select or estimate the number of groups K.These approaches extend beyond assigning every node to one fixed group.
  • Longitudinal and multilayer graphs: Longitudinal SBMs model multiple graph layers over time, whereas multilayer models can infer layers whose edges have been aggregated into one observed graph.For two aggregated layers, one version uses an edge if either layer contains it, while another requires the edge in both layers.
  • Longitudinal and multilayer graphs: 59?
  • Poisson and degree-corrected SBMs: Degree-corrected SBMs address within-group degree variation that the original SBM ignores, while Poisson SBMs model edge counts and are asymptotically equivalent to Bernoulli SBMs for large sparse graphs.The degree-corrected model was reported to discover known factions in a karate club network, unlike the original model.

4 Clustering approach

The review contrasts hard clustering with soft and overlapping SBM extensions that represent nodes as belonging to multiple groups. These models differ in how memberships generate edges, how they handle dependence, and how complexity affects model selection.

  • Mixed membership and soft clustering: Soft-clustering SBMs allow a node to belong to multiple groups, unlike hard-clustering SBMs where each node belongs to one group.The review cautions that interactions involving multiply affiliated nodes require careful modelling.
  • Mixed membership and soft clustering: MMSBM represents each node with a non-negative membership vector whose weights sum to 1, with dyad-specific latent group indicators drawn from those memberships.Inference targets the mixed memberships Θ rather than only the pairwise latent variables Z.
  • Mixed membership and soft clustering: MMSBM extensions address scalable inference, longitudinal data, unknown group counts, intra-group dependence, and rating prediction in bipartite user–item networks.In the recommender-system extension, inferred memberships and the block matrix predict ratings for unobserved user–item combinations.
  • Overlapping SBMs: Overlapping SBMs use binary membership combinations, permitting any nonempty subset of groups rather than probability-weighted memberships.Their augmented-graph formulation can simplify modelling and inference, while multiply affiliated nodes have higher expected degree than nodes in either group alone.
  • Overlapping SBMs: Comparing MDL values, overlapping SBMs are more likely to overfit and are selected over non-overlapping SBMs only in a few cases.Real-world studies report that overlapping nodes typically belong to 2 or 3 groups and usually comprise less than 30% of nodes.
  • Overlapping SBMs: A bipartite overlapping model can infer actor memberships from event attendance without directly observing edges between actors.The data are represented as an actor–event bipartite network, with actors allowed to belong to one or more groups.

5 Related methods for graphs

The review covers latent feature, hypergraph, and latent space methods as alternatives or complements to SBMs. These approaches represent multiple node attributes, higher-order relations, or geometric positions, with reported performance differences among latent feature models.

  • Latent feature models: Latent feature models replace group memberships with unconstrained binary indicators for the presence or absence of K latent features.They allow multiple 1s in each node vector, whereas MMSBMs use non-binary non-negative weights summing to 1.
  • Latent feature models: The latent feature relational model uses a weight matrix W so Z_p^T WZ_q can take any real value before a function maps it to an edge probability.The latent feature formulation reduces to an SBM when each node is constrained to have exactly one feature.
  • Latent feature models: The EPM outperforms ILA, which outperforms LFRM, which outperforms MMSBM in the review’s comparison.The review notes that IMRM was not compared with these models and that no single comparison included all latent feature models.
  • Hypergraph models: Hypergraph models preserve higher-order relations by representing collaborations involving arbitrary subsets of nodes as hyperedges rather than only pairwise edges.Pairwise projection can lose information and may be unrealistic when a multi-author article does not imply separate pairwise collaborations.
  • Hypergraph models: Latent-class hypergraph models cluster hyperedges, while geometric models place nodes in Euclidean space and assign hyperedges to overlapping node regions.In the latent-class approach, node memberships are mixtures of the memberships of the hyperedges containing them.
  • Latent space models: Latent space models make edge probability depend on the distance between node positions and can incorporate dyadic covariates.The formulation supports symmetric undirected graphs, with a separate asymmetric term proposed for directed graphs.
  • Latent space models: A reviewed spectral approach fits a K-component model to spectral embeddings while estimating the embedding dimension d and group count K simultaneously.This simultaneous estimation is identified as the approach’s novelty.

5.4 Community detection

Community detection methods seek groupings with dense within-group and sparse between-group connections, but assortative assumptions and modularity optimization impose important constraints. The review discusses SBM-based, modularity-based, heuristic, and multiscale responses to these issues.

  • SBM-based community detection: Community detection targets high within-group and low between-group edge density, corresponding to assortative SBMs with high C_ii and low C_ij for i ≠ j.SBMs can also represent other network structures, so stochastic equivalence alone does not guarantee assortativeness.
  • SBM-based community detection: Degree correction can materially change detected communities: DC-SBM accounts for degree variation, whereas the original SBM grouped highly connected nodes together and separated the rest.In larger networks, the original SBM may place peripheral nodes in a low-density miscellaneous group instead of with their central neighbors.
  • SBM-based community detection: Assortative SBM variants constrain between-group probabilities and can tune assortativeness, but assortative structure is not sensible for bipartite networks.A higher tuning value h produces a more assortative partition and recovered the known karate-club factions in one application.
  • Modularity and heuristic methods: Modularity compares within-group edges with their expected number and can evaluate outputs from methods that do not optimize modularity directly.A modularity value above 0.3 was suggested as a practical indicator of significant community structure.
  • Modularity and heuristic methods: Modularity optimization suffers a resolution limit in large graphs, preventing detection of smaller groups and potentially requiring additional rounds of community detection.The review also notes sensitivity to initial configurations and differing results across runs or methods.
  • Responses and broader methods: Proposed responses include modularity density, multiscale agglomerative detection, and hierarchical SBM formulations.Modularity density is described as theoretically resolving the resolution-limit problem and empirically improving community-detection results.

6 Inference approach

The review covers Monte Carlo and variational inference for SBMs, emphasizing computational trade-offs between hard and soft clustering and scalable algorithmic variants.

  • Inference methods: Inference can use likelihood maximisation, EM, Monte Carlo, or variational methods, with the review focusing mainly on Bayesian inference.Bayesian inference requires priors for memberships and block probabilities before posterior inference.
  • Computational complexity: The reviewed literature favors hard clustering because its computational cost depends mainly on latent memberships, whose state space is smaller than in soft clustering.The review notes that K is usually much smaller than n, while soft clustering introduces more extensive latent-variable computation.
  • Computational complexity: Hard clustering has O(n) latent-variable updates, whereas soft clustering requires O(n^2) iterations and is less scalable.The quadratic cost makes a simple Gibbs sampler unsuitable for scalable soft clustering.
  • Monte Carlo methods: MCMC variants improve scalability through efficient moves, including edge-based updates and stochastic-gradient mini-batches.Some algorithms make complexity increase linearly with the number of edges, while others use only a small node mini-batch per iteration.
  • Variational methods: Variational methods optimize a tractable lower bound using factorized distributions and iterative E- and M-steps.The approximation seeks to reduce K-L divergence to the intractable posterior distribution.

7 Number of groups

The number of groups K may be fixed, selected by a goodness-of-fit criterion, or estimated within the model. The review emphasizes that these choices are intertwined with inference and can produce different structural conclusions.

  • Selecting K: When K is unknown, one strategy fits multiple candidate values and selects the best using a goodness-of-fit measure.Common criteria include BIC, marginal likelihood, ICL, held-out likelihood, and penalized likelihood.
  • Estimating K: A second strategy models K as a parameter and estimates it using transdimensional inference.This approach estimates the number of groups during inference rather than selecting it after separate fits.
  • Fixed K: Assuming K is given is often unrealistic in practice and complicates likelihood evaluation and membership inference when prior information is unavailable.Several reviewed applications fixed K using known labels, prior knowledge, or external practices.
  • Selection criteria: BIC and marginal-likelihood criteria face tractability problems, while BIC can misestimate K in some situations.Alternative criteria approximate likelihoods, integrate out parameters, or apply penalties to compare candidate group counts.
  • Model structure: Nested SBMs can overcome underfitting while discovering hierarchical structure, whereas some microcanonical fits may select 32 groups and still underfit.The review presents both hierarchical recovery and potentially excessive or inadequate group resolutions as outcomes of model selection.

8 Comparison

Across karate-club and political-blog networks, reviewed models generally recover broad factions, but their fine-grained partitions and preferred group counts often differ. The comparison also stresses that modelling, inference, clustering, and K selection are interconnected.

  • Overall comparison: The review cautions that matching known groups does not automatically establish model superiority, because SBM results are not unanimous.Different criteria and SBM variants can support conflicting structural interpretations of the same network.
  • Political-blog network: On political blogs, the DC-SBM agrees strongly with the ground truth, while the original SBM does not.The DC-SBM dominates the original SBM in the reported comparison, especially at smaller K.
  • Cross-cutting comparison: Model choices are interconnected: latent-feature and soft-clustering approaches enlarge latent state spaces and can require more efficient inference algorithms.The latent-feature state space grows from K^n to 2^Kn, increasing computational complexity.

9 SBM with longitudinal modelling

Longitudinal SBM extensions model changing group memberships, interaction rates, block structures, or edge processes across time. The review contrasts state-space, Dirichlet-process, Markov, continuous-time, likelihood-based, and MDL approaches, while noting identifiability and applicability constraints.

  • Dynamic model formulations: Dynamic SBMs represent evolving graphs through time-indexed memberships, block matrices, interaction intensities, or edge processes.Approaches include state-space models, recurrent Dirichlet processes, Markov chains, continuous-time Markov chains, and multilayer formulations.
  • Dynamic model formulations: Historical memberships influence current memberships in MTV and MTI models through Dirichlet-process parameters or time-invariant membership probabilities.Both models generate the current memberships from distributions linked to previous memberships, but differ in how temporal dependence is parameterized.
  • Identifiability and assumptions: Allowing memberships and the block matrix to vary simultaneously over time creates identifiability and label-switching issues, motivating a time-constant block matrix.This constraint is used in a valued dynamic SBM.
  • Multilayer models: MDL-based multilayer models either collapse edge counts across layers or generate layers independently while allowing nodes in only selected layers.The two versions are equivalent in special non-degree-corrected cases but generally differ for degree-corrected SBMs because only the second permits degree variability across layers.
  • Multilayer models: Temporal binning can approximate longitudinal structure when large-scale network structure remains stable within each bin, but these models specify no temporal dynamics explicitly.MDL can help choose the binning, model version, and degree-correction option.

10 Topic models

Topic models represent documents through mixtures of latent topics and topics through vocabulary distributions, paralleling soft clustering in graph models. The review covers inference choices and alternatives for fixing, selecting, or modeling the number of topics.

  • Topic-model structure: Topic models cluster documents into latent topics, each represented by a distribution over words.Documents commonly have non-binary weights across multiple topics rather than a single hard assignment.
  • Data representation: The document-word data are represented by word indicator vectors, document word sequences, and an m × n document-word frequency matrix.M_pk records the frequency of vocabulary word V_k in document p.
  • Topic-model structure: Latent Dirichlet allocation generates each word by sampling a document-specific topic assignment and then sampling the word from that topic’s vocabulary distribution.The topic assignment is one-hot for each word, while document-level topic membership is mixed.
  • Inference: Bayesian inference may integrate out topic and document parameters to obtain collapsed Gibbs samplers, whereas variational inference provides another common strategy.MCMC methods are especially useful when the number of topics is modeled rather than selected by a criterion.
  • Computational considerations: Topic-model computational complexity grows linearly rather than quadratically with the number of documents m.This comparison is stated for topic models relative to the reviewed SBM setting.
  • Choosing the number of topics: The number of topics K may be fixed, selected by perplexity or marginal log-likelihood, or modeled through nonparametric Bayesian processes.Dirichlet and hierarchical Dirichlet processes allow K to arise during sampling instead of being pre-specified.

11 SBM with topic modelling

SBM–topic-model hybrids combine relational structure with textual information, with model design shaped by whether text belongs to edges or nodes. Extensions can jointly cluster nodes, documents, and temporal occurrences.

  • Alternative graph representations: A nested SBM applied to suitable non-relational data can infer hierarchical groups and was found to outperform traditional LDA.This illustrates that text can sometimes be represented directly through graph structure rather than probabilistic matrix factorization.
  • Data configurations: The modeling approach depends largely on whether textual information is associated with graph edges or nodes.The available data structure determines which graph–text combination is appropriate.
  • Email-network models: Author–recipient and user-community models generate email text from latent topics linked to users, authors, recipients, or their communities.Their structures differ in whether membership probabilities are user-, author-recipient-, sender-group-, or topic-specific.
  • Edge-associated text: The stochastic topic block model combines SBM node groups and edge modeling with LDA-style topic generation for documents attached to edges.Group memberships influence both dyadic connections and, when an edge exists, the words in its document.
  • Longitudinal graph–text models: Corneli et al. extend the STBM with latent time clusters and nonhomogeneous Poisson document occurrences.The model simultaneously clusters nodes into groups, documents into topics, and occurrences into time clusters.
  • Document networks: For document networks, topic-link LDA makes edge probability depend on document similarity and author similarity.These similarities are represented by dot products of document and author topic-membership vectors.

12 Comparison

The review compares models combining block modelling with longitudinal and topic modelling on the Enron email network, using temporal, textual, and network information. These comparisons show that modelling choices affect inferred groups, topics, and temporal dynamics.

  • Longitudinal modelling: Dynamic MMSBM analyses found that employees with strong cross-group connections or important positions tended to maintain multiple active roles.Major changes in mixed memberships aligned with real-life events, including the bankruptcy filing.
  • Longitudinal modelling: Fixed K = 7 dynamic block modelling detected spikes in block interaction parameters at the CEO resignation event.The groups were fixed according to known employee roles.
  • Topic modelling: Topic-aware models found topically meaningful groups, but several studies did not compare inferred groups with employees’ actual company roles.This leaves topical coherence and correspondence with organizational roles as distinct evaluation dimensions.
  • Topic and temporal modelling: The dynamic STBM found different group interactions and discussion topics across time clusters, supporting incorporation of both temporal and textual information.Sachan et al.’s topic user community model also achieved maximum modularity greater than 0.3 at K = 10, with perplexity selecting around K = 10.

13 Discussion

The discussion presents SBMs as a broad, interconnected modelling spectrum and emphasizes systematic comparison across graph, clustering, inference, and group-number choices. It highlights collapsed and nested approaches, mixed evidence for degree correction on real networks, and extensions combining textual and temporal data.

  • Discussion: SBM aspects—including graph type, clustering, inference, and treatment of K—are interdependent rather than completely independent.The review therefore frames model selection as a coordinated design problem.
  • Future directions: The review systematically investigates models to make the literature landscape easier to compare across models and dimensions.Proposed directions include hierarchical models for textual nodes and frameworks representing graphs between words and documents and between documents.
  • Inference and K: Recent collapsed SBMs integrate out model parameters, enabling model-selection criteria or tractable posteriors with efficient MCMC algorithms.These developments allow K to be selected or estimated without trans-dimensional methods.
  • Recent developments: The nested microcanonical SBM combines MDL-related Bayesian equivalence, efficient MCMC, and hierarchy to model K and address potential SBM underfitting.The review identifies hypergraphs as a possible application direction for these methods.
  • Model extensions: DC-SBM is useful for degree heterogeneity, but its results on real-world networks are more mixed and should not be read as showing that the original SBM is inferior.The discussion attributes this distinction to the different underlying structures captured by the models.
  • Future directions: The review recommends realistic SBM extensions rather than aimless complexity increases and proposes unifying regularised and weighted SBM variants.It also outlines textual and temporal extensions involving mixed membership, hierarchical structure, joint group/topic/time modelling, and scalable inference.

Declarations

The article reports its data-sharing status, funding source, competing-interests declaration, and author contributions.

  • No datasets were generated or analysed during the current study, so data sharing is not applicable.
  • The authors declare that they have no competing interests.
  • The research was funded by the EPSRC DERC grant EP/M023001/1.
  • CL compiled the reviewed articles and wrote the manuscript, while both authors reviewed and approved the final manuscript.
Loading 1903.00114v2…