A Review of Stochastic Block Models and Extensions for Graph Clustering

In plain words

Many datasets are networks: people linked to people, papers linked to papers. A stochastic block model is a simple way to explain such a network. It assumes that each node secretly belongs to one of a few groups, and that the chance of two nodes being linked depends only on which groups they belong to. Nodes in the same group look alike from the outside, so fitting the model to the links reveals the groups.

This review surveys the many variants of that idea. Some allow weighted or directed links, some let a node belong to several groups, and some let the number of groups be learned rather than fixed. It also covers how these models are fitted, how people choose the number of groups, and how to combine them with time information or with the text attached to links and nodes. Its main use is the side-by-side comparison of which variant handles which problem.

TL;DR

A review of stochastic block models (SBMs) for clustering graphs. It sorts variants by graph type, degree correction, hard versus soft membership, inference method, and how the number of groups is chosen, and it extends the same view to longitudinal and topic-model combinations §1 §13. It runs no experiments of its own; four comparison tables classify the reviewed models tab. 1 tab. 2 tab. 3 tab. 4. Use it as a map of the literature, then check the source papers for numbers.

Problem

Given an observed graph but no group labels, fitting an SBM means inferring two things at once: the group memberships and the block matrix of group-pair edge probabilities §1. The review frames the open questions as: how to structure the model for real networks §1; how to infer the parameters efficiently and at scale §1; how to compare fits with criteria such as BIC or marginal likelihood §1; and whether the number of groups K should be a model parameter or picked by a criterion §1. Extra information on the nodes, edges or time adds further questions §1.

Cost is a recurring concern. Under hard clustering the latent variables scale with the n nodes; under soft clustering with pairwise latent variables they scale with n² §6. The review quotes a variational cost of O(nK+2K) against O(n²) for MCMC in the mixed-membership setting, as argued by the authors of the cited work §6.2.

Method

Base model: Bernoulli SBM §2

• Graph G = (N, E) with n nodes and an n×n adjacency matrix Y. Undirected graphs have symmetric Y; directed graphs need not. Self-edges are assumed absent in most of the models reviewed §2.
• Each node p has a K-vector Z_p with exactly one entry equal to 1, the node's group §2.
• The K×K block matrix C holds the edge probability between groups. For undirected graphs C is symmetric. Rows and columns need not sum to 1 §2.
• Given Z and C, dyads are independent Bernoulli variables with success probability Z_pᵀ C Z_q §2 eq. 2.
• Group memberships follow a multinomial with probabilities θ; the review writes the prior as a product over group sizes N_i §2 eq. 4.
• Stochastic equivalence: nodes in the same group have the same edge distribution toward any third node. It does not by itself imply that nodes in a group link more to each other §2.1 §2.1.1.

Generative process, as stated in §2 (undirected, no self-edges):

# Sample an undirected Bernoulli SBM  [§2] [eq. 2] [eq. 4]
# Input:  theta (K,) group probabilities summing to 1
#         C (K, K) symmetric block matrix with entries in [0, 1]
#         n number of nodes
# Output: memberships (n,) with values 0..K-1; adjacency Y (n, n)

def sample_sbm(n, theta, C):
    # Draw each node's hidden group from the multinomial  [§2] [eq. 4]
    memberships = draw_categorical(theta, size=n)
    adjacency = zeros(n, n)
    # Each dyad is an independent Bernoulli draw given the groups  [§2]
    for p in range(n):
        for q in range(p + 1, n):
            # The edge rate is the block entry for the two groups  [§2]
            rate = C[memberships[p], memberships[q]]
            adjacency[p, q] = draw_bernoulli(rate)
            adjacency[q, p] = adjacency[p, q]
    return memberships, adjacency

Likelihood for the undirected case §2 eq. 2:

\pi(\mathbf{Y}\mid\mathbf{Z},\mathbf{C}) = \prod_{p<q}\left(\mathbf{Z}_p^\top\mathbf{C}\mathbf{Z}_q\right)^{Y_{pq}}\left(1-\mathbf{Z}_p^\top\mathbf{C}\mathbf{Z}_q\right)^{1-Y_{pq}} \quad [\text{eq. 2}]

The same likelihood, regrouped by group pairs, is \prod_{i\le j} C_{ij}^{E_{ij}}(1-C_{ij})^{N_{ij}-E_{ij}} eq. 3, where E_ij counts edges between groups i and j and N_ij counts the dyads available to them. See Pitfalls for the value of N_ij.

Priors used later for inference §2.2 §6: each C_ij gets a Beta prior; θ gets a symmetric Dirichlet with concentration α; α gets a Gamma prior.

Graph-type extensions §3

• Binary graphs §3.1. Beyond the basic SBM, the review lists mixed-membership, latent-feature, and edge-partition models, plus a model for binary directed acyclic graphs in which no cycle is allowed §3.1. A multilayer variant aggregates layers either by OR (an edge exists in any layer) or by AND (an edge must exist in every layer); the review reports that the AND version predicted links better on the real networks studied §3.1.
• Valued graphs §3.2. A signed directed variant gives each dyad a value in {−1, 0, 1} with probabilities set by the block matrix and two auxiliary matrices D and E §3.2. A tournament variant uses the pairs (−1,1), (1,−1), (0,0) for loss, win and tie §3.2. A multi-edge model draws the two endpoints from node weights φ before drawing each edge §3.2. Two valued alternatives use a geometric distribution eq. 5 or a Poisson intensity exp(Z_pᵀ C Z_q) with unbounded C §3.2.
• Poisson and degree-corrected SBMs §3.3. The Poisson SBM eq. 6 has expected edge count Z_pᵀ C Z_q. The degree-corrected SBM (DC-SBM) multiplies this by per-node parameters φ_p, with the constraint that φ sums to one within each group eq. 7 §3.3. The review says the MLE of φ_p is the ratio of p's degree to the total degree of its group, and the MLE of C_ij is the total number of edges between groups i and j §3.3. The Poisson model is said to be asymptotically equivalent to the Bernoulli one for large sparse graphs §3.3. A collapsed Poisson SBM integrates out C under Gamma priors and gives a closed form in E and N eq. 9 §3.3. An exponential-family form eq. 10 covers both Bernoulli and Poisson, and a two-component mixture weighted by ψ handles the ambiguity of zeros in valued graphs §3.3.
• Microcanonical SBM §3.4. C_ij is given an exponential prior with rate N_iN_j/λ. Integrating out C gives a likelihood that depends on Z only through E and N eq. 11. Splitting it into a term for Y given E and a term for E gives a joint, microcanonical model with hard edge-count constraints §3.4. Marginalising λ gives a model with no free parameters, which the review calls nonparametric because it models K eq. 12 §3.4. The same route applied to the DC-SBM gives a microcanonical DC-SBM §3.4.
• Covariates and attributes §3.5. Group membership can depend on covariates through a random utility model with a Gaussian error §3.5. An ERGM-style model adds covariate terms to the edge probability eq. 13. A nonparametric weighted SBM models the graph and node attributes jointly, given the groups eq. 14. An attribute SBM draws attributes from a Gaussian mixture whose weights are the group probabilities θ §3.5.

Soft clustering §4

• Mixed-membership SBM (MMSBM) §4.1. Each node has a membership vector θ_p. For each dyad (p,q), latent group indicators Z_pq and Z_qp are drawn from θ_p and θ_q, and the edge depends on C between those two indicators eq. 15. Inference targets the membership vectors θ, not the pairwise indicators §4.1. A copula variant models correlation between Z_pq and Z_qp §4.1. A recommender variant treats ratings as weights on bipartite user-item edges §4.1.
• Overlapping SBM §4.2. Each node picks a non-empty subset of the K groups, giving 2^K − 1 choices per node. The review reports that in real networks overlapping nodes typically belong to two or three groups and make up less than 30% of nodes, and that the overlapping model is more prone to overfitting §4.2.

Related models §5

• Latent feature models §5.1. Each node has a binary vector with no sum constraint. Four link functions are listed: an independent-feature model eq. 16, a logistic link on a weight matrix W eq. 17, an edge-partition model with a Poisson-type link eq. 18, and an infinite latent-attribute model with subclusters per feature eq. 19. The review ranks them as its cited comparisons do: EPM above ILA, ILA above LFRM, and LFRM above MMSBM §5.1.
• Hypergraphs §5.2. Hyperedges are unordered node subsets, so coauthorship with three authors on one paper is one hyperedge, not three pairwise edges §5.2. One model clusters hyperedges with latent class analysis; another places nodes in Euclidean space and forms hyperedges from overlapping circles §5.2.
• Latent space models §5.3. Each node has a latent position; the edge probability is a logistic function of distance, plus covariate terms, and a directed variant adds an asymmetric projection term §5.3. A latent-space cluster model puts a Gaussian mixture on the positions §5.3. A spectral method embeds the graph and then fits a Gaussian mixture, estimating the embedding dimension and K together §5.3.
• Community detection §5.4. Assortative SBM: C_ij is set to a constant δ for i ≠ j, with δ smaller than the diagonal entries, so the model has K+1 parameters §5.4.1. A regularised DC-SBM sets φ_p = max(h·k_p, 1) with a fixed h in (0, 1), and h is varied rather than estimated §5.4.1. Non-probabilistic methods such as label propagation are also covered §5.4.2. Modularity eq. 20 scores a partition by its within-group edges minus the count expected from the node degrees §5.4.2. Modularity has a resolution limit that hides small groups in large graphs §5.4.3. Remedies named include modularity density and multi-scale agglomeration §5.4.3.

Inference §6

• Frequentist §6. Direct likelihood maximisation or EM is possible; the review cites its use for K = 2 §6.
• Bayesian §6. Beta priors on C_ij and a Dirichlet prior on θ give the joint posterior eq. 21 for hard clustering. The soft-clustering posterior eq. 22 has n² latent indicators §6.
• Monte Carlo §6.1. Plain Gibbs samplers update every parameter and latent variable (except α) in turn. HMC has been applied to a transformed C, and an SMC step with a label-switching move appears in a dynamic model. A stochastic-gradient MCMC uses mini-batches of nodes and gains scalability from graph sparsity §6.1.
• Collapsed samplers and efficient moves §6.1.1. One collapsed sampler picks one of four moves uniformly at random per iteration: a Gibbs move for one node, a reassignment of all nodes in two random groups, and two moves that add or remove groups. Another single-node move proposes a new group j for node p with probability proportional to E_ij, where i is the group of a random neighbour q §6.1.1. A merge move handles K §6.1.1.
• Variational EM §6.2. A lower bound on the marginal log-likelihood uses a factorised distribution Q over the latent variables eq. 23. The gap to the true log-likelihood is a KL divergence eq. 24. The E step tightens Q, and the M step updates the parameters. Stochastic optimisation and belief propagation are named as alternatives §6.2.
• Greedy §6.3. One label-switching algorithm moves nodes one at a time, keeps the best objective seen along the way, restarts from it, and stops when the objective no longer rises. Another greedy method maximises the ICL, and when no move raises it, the node stays put §6.3.
• Missingness and errors §6.4. Link prediction and network reconstruction use the same models to fill in or correct the observed graph §6.4.

Choosing K §7

• Criteria §7.1. Fit several K values and pick the best by a criterion. Options listed: the modularity-like profile likelihood with the MLE of C plugged in; BIC, which the review says is intractable here because it needs the observed-data likelihood; the approximate ICL eq. 25 for directed graphs; the exact ICL under conjugate priors; a variational lower bound used as the marginal likelihood; penalised likelihoods §7.1; held-out perplexity; and an elbow plot of k-means distances §7.1.
• Modelling K §7.2. Use a Dirichlet process or hierarchical Dirichlet process for the membership prior, or an Indian buffet process for latent features, so that K is generated by the process §7.2. Once C and θ are integrated out, the parameter count no longer depends on K, which makes MCMC moves that add or remove groups simpler §7.2. Birth/death and split/merge moves change K during MCMC §7.2.
• Nested SBM §7.2.1. A hierarchy of SBMs on the groups of the level below. In a synthetic example of 64 cliques of 10 nodes, a flat microcanonical SBM settled on 32 groups (underfitting); the nested model overcame this and found a hierarchical structure §7.2.1.

Longitudinal SBMs §9

Time-varying models include state-space evolution of membership or block parameters §9, Markov chains over group memberships §9, autoregressive continuous-time Markov chains on dyads §9, self-exciting Poisson processes on interaction events §9, and conditional Poisson processes with time-varying intensity §9. Identifiability and label switching are flagged when C varies over time §9. The review cites a detectability threshold below which no efficient algorithm beats chance §9.

Topic models §10

Latent Dirichlet allocation is the reference topic model. Documents have topic mixtures from a symmetric Dirichlet, topics are Dirichlet distributions over the vocabulary, and each word draws its own topic §10. Inference is mostly Bayesian: collapsed Gibbs, or variational methods §10.1. The number of topics is fixed, chosen by perplexity or marginal likelihood, or modelled with an HDP or IBP §10.2 §10.2.1. Dynamic topic models let topic distributions evolve with a state-space model, or let a Dirichlet process evolve over time §10.3.

SBM combined with topic models §11

• Textual edges §11.1.1. The text sits on the edges (for example, emails between employees). Models here include author-recipient topic models and group-based topic models; the stochastic topic block model (STBM) gives each pair of groups its own topic mixture §11.1.1.
• Textual nodes §11.1.2. The text sits on the nodes (for example, linked documents). Models include topic-link LDA, a relational topic model, and a hierarchical tree model that mixes word distributions along a path §11.1.2.
• Inference §11.2. Gibbs samplers appear for several models. The VEM algorithm is used for others, and the classification VEM variant alternates a variational step with a greedy update of the group labels §11.2.
• Clustering and K §11.3 §11.4. Nodes are often hard-clustered while documents are soft-clustered. The number of groups and topics is fixed, or set by perplexity, BIC-like, or ICL criteria §11.4.

Entries for each model are in tab. 4.

Discussion §13

The review argues that recent SBMs are mostly collapsed, so that criteria can be computed and MCMC can use tractable posteriors without trans-dimensional moves §13. It names the nested microcanonical SBM and the DC-SBM as recent developments with mixed empirical results, and suggests extending hierarchical and collapsed ideas to mixed-membership and hypergraph models §13.

Hyperparameters

Values as stated in the review. The review sets no values for most priors; it describes the models only.

Results

The review runs no experiments of its own. The results below are its summaries of other papers, on the datasets it names. Numbers in the original papers are author-reported.

Karate club (n = 34 members, M = 78 edges, two known factions after a split) §8.1 fig. 3:

• Two community detection methods (Girvan & Newman; Newman & Girvan) recover the two factions; Blondel et al. stop at four groups §8.1.
• The DC-SBM recovers the two known factions, and the original SBM does not §8.1.
• Under the DC-SBM, the ICL selects K = 1; under the original SBM, it selects K = 4, with groups following degree levels §8.1.
• A likelihood-ratio test finds no clear evidence for degree correction on this network, even though degree heterogeneity prompted it §8.1.
• Decelle et al. and Newman & Reinert both find K = 2 as the best fit §8.1.

Political blogs (directed; 1490 blogs in total, giant component of 1222 blogs with 19089 edges; labelled liberal or conservative) §8.1:

• With K forced to 2, the DC-SBM agrees with the labels more closely than the original SBM §8.1.
• A penalised likelihood selects K = 4, where one label group splits into three inferred groups. At one tuning value, the penalised likelihood selects K = 1, which motivates a corrected BIC with a heavier penalty §8.1.
• A nested SBM finds two main factions with 20 groups at the lowest level under the DC-SBM §8.1.

Enron email network (about 150 nodes in most studies; 184 in two) §12.1:

• Dynamic MMSBM: membership changes line up with company events in 2001 §12.1.1.
• Dynamic SBM with K = 7 groups: block-matrix elements spike at the CEO's resignation §12.1.1.
• Conditional Poisson SBM with K = 3: two groups peak at different times §12.1.1.
• Textual-edge models: one study finds 50 topics matching company issues; another uses 8 groups and 25 topics §12.1.2.
• STBM selects K = 10 groups and 5 topics, against K = 8 from an SBM alone §12.1.2.
• Dynamic STBM selects 6 groups, 9 topics and 4 time clusters, matching the period boundaries around the events §12.1.3.

Comparison tables, as classified by the review (not measured results):

Table 1: models for graphs without longitudinal or topic modelling tab. 1. Columns: article, graph type, directedness, SBM (yes/no), inference, clustering, number of groups. Keys in parentheses are the paper's citation keys.

Table 2: SBMs with longitudinal modelling tab. 2:

Table 3: topic models and related clustering models tab. 3:

Table 4: models combining block models and topic models tab. 4. The first clustering entry refers to topics; a second entry refers to groups.

Paper vs code

No official code. The paper names no repository, project page or code link. A GitHub repository search for "stochastic block models review" returned no relevant project. The paper is a review with no implementation of its own.

Pitfalls

• Dyad count for undirected pairs of different groups. The text gives N_ij = N_iN_j/2 for i ≠ j §2 eq. 3. The review's own example contradicts this. Its densities match E_ij divided by N_iN_j with no factor of one half: 37/(25·30) = 0.049 for groups 1 and 2, 52/(30·35) = 0.050 for groups 2 and 3, and 36/(25·35) = 0.041 for groups 1 and 3 §2. Dividing by N_iN_j/2 would give about 0.099 for groups 1 and 2. Implement the count of unordered pairs with one node in each group, which is N_iN_j. Check it against the example densities. The within-group count N_i(N_i − 1)/2 is consistent with the example.
• Table and text disagree on the number of groups. The text says Tallberg used K = 2 and Karrer & Newman used K = 3 §7. Table 1 lists Tallberg as Fixed (3) and Karrer & Newman as Fixed (2) tab. 1. The review's own DC-SBM versus SBM comparison on a real network is at K = 2 §5.4.2. Check the source before taking either value.
• Yan (2016) criterion. Section 8.1 says the ICL selected K = 1 and K = 4 for that paper §8.1. Table 1 lists the criterion as BIC tab. 1, and Section 7.1 says the paper derived a more principled BIC §7.1. Treat the criterion as unresolved.
• Vu et al. (2013) groups. The text says K = 5 was used §7. Table 1 lists Fixed (5, 20) tab. 1. No text explains the 20.
• Latent feature models labelled hard. Section 5.1 says each latent-feature node may have several 1s, and that this is unlike hard SBM membership §5.1. Table 1 labels the two latent-feature models Hard tab. 1. Do not read "Hard" as a single group per node for these models.
• Modularity on valued graphs. The review defines M as the number of edges §2, but modularity eq. 20 uses 2M. For a valued graph, the total of the degrees equals twice the total edge weight, so use that total in the normalisation, not the edge count. This is an implementation choice the review does not spell out §5.4.2.
• Modularity threshold is a rule of thumb. The 0.3 cut-off is a heuristic from a cited paper §5.4.2. The review also uses it as evidence of significant structure for one Enron model §12.1.2. It is not a statistical test.
• Zeros in valued graphs. A zero may mean no edge, a zero-weight edge or missing data §3.3. The review's remedy is a two-component mixture with weight ψ §3.3. The review does not say how ψ is set.
• Cost of soft clustering. Soft clustering needs O(n²) latent variables against O(n) for hard clustering §6. The review says the stochastic-gradient MCMC gains its scalability from graph sparsity §6.1, so that advantage depends on sparse graphs.
• Label switching. When C or the memberships change over time, the model has identifiability and label-switching problems §9. The review cites a greedy label-switching move §6.3, and says a spectral model avoids label switching by design §6.1.1.
• Criteria can disagree. On the karate club, the factions appear under the DC-SBM and not under the original SBM, yet the likelihood-ratio test does not support the DC-SBM over the original §8.1. The ICL also selects different K for the two models. Report which criterion you used.
• Results are not comparable across papers. The review notes that studies use different networks, sizes and criteria, so their outcomes differ for reasons beyond the model itself §11.4 §12.1.
• Asymptotic equivalence of Poisson and Bernoulli. The equivalence argument for large sparse graphs §3.3 is asymptotic. The review gives no convergence rate.
• Approximate ICL. The approximation eq. 25 is stated for directed graphs §7.1. The review does not say whether it holds for undirected graphs.
• Unknown inference. Several rows of Table 1 say "Unknown" for inference (vmgs16, yan16, vv18, hqyz19) tab. 1. The review does not identify their algorithms.
• Mixed-membership cost. A VEM bound is cited as O(nK+2K), against O(n²) for MCMC. This is the cited authors' claim, not a measurement by the review §6.2.

Lineage

• Builds on (named in the review; no cards in this wiki): Breiger et al. 1975; White et al. 1976; Holland et al. 1983 for the stochastic blockmodel; Snijders & Nowicki 1997 and Nowicki & Snijders 2001 for a posteriori blocking §3.
• Related models named in the review (no cards in this wiki): Airoldi et al. 2008 (MMSBM); Miller et al. 2009 (latent feature); Zhou 2015 (edge partition); Palla et al. 2012 (infinite latent attribute); Hoff et al. 2002 (latent space) §4.1 §5.
• Superseded by: not stated. The review names open directions instead §13.