Stochastic block model

Overview

A stochastic block model (SBM) explains an observed graph by hidden group labels. Each node has one group, and each pair of nodes is linked with a probability that depends only on the two groups 1903.00114 §2. Fitting the model means inferring the group memberships and the block matrix of group-pair probabilities at once, without any labels given in advance 1903.00114 §1.

The review treats every variant as a change to one of a few parts: the graph type (binary, valued, signed), whether node degrees are corrected for, hard or soft membership, the inference method, how the number of groups is chosen, and whether time or text is added 1903.00114 §3–§11. The review covers the variants under Variants except the last two. The contextual SBM comes from a graph neural network paper, which uses it to generate benchmark graphs rather than to model data 2006.07988 §5. A second GNN paper defines a signed, directed variant and uses it the same way 2209.00546 §4.2. The review runs no experiments; the GNN papers' results measure node classifiers and node clusterers, not fits of the SBM.

Variants

Bernoulli SBM

The base model. Dyads are independent Bernoulli draws given the groups, with success probability Z_pᵀ C Z_q, where C is the symmetric block matrix for undirected graphs 1903.00114 §2 eq. 2. Nodes in one group are stochastically equivalent: they have the same edge distribution toward any third node. This does not mean that nodes in a group link more to each other 1903.00114 §2.1. Card: A Review of Stochastic Block Models and Extensions for Graph Clustering.

Degree-corrected SBM (DC-SBM)

Multiplies the expected edge count by a per-node parameter φ_p, with φ summing to one within each group 1903.00114 §3.3 eq. 7. It is aimed at graphs where degrees vary a lot inside a group. The review gives the maximum likelihood estimates: φ_p is node p's degree divided by its group's total degree, and C_ij is the number of edges between groups i and j 1903.00114 §3.3. On the karate club network the DC-SBM recovers the two known factions, and the plain SBM does not 1903.00114 §8.1. See Contradictions for the likelihood-ratio result on the same network.

Poisson and valued SBMs

For weighted or count-valued edges. The Poisson SBM has expected edge count Z_pᵀ C Z_q 1903.00114 §3.3 eq. 6. The review says it is asymptotically equivalent to the Bernoulli model for large sparse graphs, with no convergence rate given 1903.00114 §3.3. A collapsed Poisson variant integrates out C under Gamma priors 1903.00114 §3.3 eq. 9. Valued graphs have other forms too: signed directed edges with values in {−1, 0, 1}, a tournament form for win, loss and tie, and a geometric or unbounded-rate exponential link 1903.00114 §3.2. Zeros are ambiguous in valued data: they may mean no edge, a zero-weight edge, or missing data 1903.00114 §3.3.

Microcanonical and nonparametric SBM

Puts an exponential prior on each C_ij with rate N_iN_j/λ. Integrating out C leaves a likelihood that depends on the memberships only through the edge counts E and dyad counts N 1903.00114 §3.4 eq. 11. Integrating out λ as well leaves a model with no free parameters, which the review calls nonparametric because it also models K 1903.00114 §3.4 eq. 12. The same construction applied to the DC-SBM gives a microcanonical DC-SBM 1903.00114 §3.4.

Mixed-membership SBM (MMSBM)

Soft clustering: each node has a membership vector θ_p, and each dyad draws its own latent group indicators from the two endpoints' vectors 1903.00114 §4.1 eq. 15. Inference targets the membership vectors, not the pairwise indicators 1903.00114 §4.1. The review cites the authors of the variational method as claiming a cost of O(nK+2K), against O(n²) for MCMC 1903.00114 §6.2. The review does not measure this.

Overlapping SBM

Each node picks a non-empty subset of the K groups, giving 2^K − 1 choices per node 1903.00114 §4.2. The review reports that overlapping nodes in real networks usually belong to two or three groups and make up less than 30% of nodes, and that the model overfits more easily than the non-overlapping one 1903.00114 §4.2.

Longitudinal (dynamic) SBM

Lets memberships or block parameters change over time. The review lists state-space models of membership or block parameters, Markov chains over memberships, autoregressive continuous-time chains on dyads, and Poisson processes on interaction events 1903.00114 §9. When C varies over time, identifiability and label switching become issues 1903.00114 §9. The review also cites a detectability threshold below which no efficient algorithm beats chance 1903.00114 §9.

SBM with topic models

Adds text. In the textual-edge case the text sits on the edges, and the stochastic topic block model (STBM) gives each pair of groups its own topic mixture 1903.00114 §11.1.1. In the textual-node case the text sits on the nodes, as with linked documents 1903.00114 §11.1.2. The topic-modelling concept covers the topic-model side. Entries for each model are in tab. 4 of the review.

Nested SBM

A hierarchy: an SBM is fitted to the groups of the level below. In a synthetic example of 64 cliques of 10 nodes, a flat microcanonical SBM settled on 32 groups, while the nested model recovered the hierarchy 1903.00114 §7.2.1. On the political blogs network under the DC-SBM, the lowest level has 20 groups inside two main factions 1903.00114 §8.1.

Contextual SBM (cSBM) for benchmarks

An SBM whose nodes also carry features, used to build synthetic node classification graphs. The GNN paper uses two equal classes, n = 5000 nodes, f = 2000 features, ξ = n/f = 2.5 and margin ε = 3.25 2006.07988 app. A.5. Homophily is set by one knob φ: φ = (2/π)·arctan(λ√ξ/μ), with λ² + μ²/ξ = 1 + ε 2006.07988 §5 app. A.5. The paper sweeps φ from −1 to 1 in its tables tab. 5 tab. 6. Average degree is not stated in the paper 2006.07988 app. A.5. The paper also uses real heterophilic benchmarks, so the synthetic graphs are a control, not a replacement 2006.07988 §5. Card: Adaptive Universal Generalized PageRank Graph Neural Network.

Signed directed SBM (SDSBM) for benchmarks

An SBM whose edges carry a sign and a direction. The generator takes a meta-graph F of C blocks, an edge rate p, a node count n, a block-size ratio ρ and a sign-flip noise level η. Each directed edge from block k to block l is drawn with probability p·|F_kl| and gets weight +1 or −1 from the sign of F_kl. Then every edge's sign is flipped with probability η 2209.00546 §4.2. The paper uses two meta-graphs, with three and four blocks, and a directional noise level γ between 0 and 0.5 2209.00546 §4.2. It says the model generalises the signed SBM and the directed SBM of earlier work when the meta-graph is chosen suitably 2209.00546 §4.2. Node clustering with MSGNN on these graphs is reported as ARI in figures, not tables. The paper says MSGNN beats SigMaNet on every synthetic set and is competitive with SSSNET, and that a nonzero charge q usually helps on SDSBM 2209.00546 §4.4.1. Card: MSGNN.

Inference

• Monte Carlo. Plain Gibbs samplers update every parameter and latent variable in turn. The review also names Hamiltonian Monte Carlo, applied to a transformed C, and stochastic-gradient MCMC, which uses mini-batches of nodes and gains scalability from graph sparsity 1903.00114 §6.1.
• Collapsed samplers. A collapsed sampler picks one of four moves at random each iteration: a single-node Gibbs move, a reassignment of two random groups, or a move that adds or removes a group 1903.00114 §6.1.1.
• Variational EM. Maximises a lower bound on the marginal log-likelihood with a factorised distribution over the latent variables; the E step tightens the bound and the M step updates the parameters 1903.00114 §6.2 eq. 23 eq. 24.
• Greedy. Moves one node at a time, keeps the best objective seen, restarts from it, and stops when no move raises the objective 1903.00114 §6.3.
• Belief propagation. Used by Decelle et al. for a binary directed model 1903.00114 tab. 1.

Choosing K

• Fit and score. Fit several K and compare them with a criterion. The review lists the approximate ICL eq. 25 for directed graphs, the exact ICL under conjugate priors, a variational bound used as marginal likelihood, penalised likelihoods, held-out perplexity and an elbow plot of k-means distances 1903.00114 §7.1. It says BIC is intractable here, because the observed-data likelihood it needs is not available 1903.00114 §7.1.
• Let the model decide. A Dirichlet process or hierarchical Dirichlet process over memberships, or an Indian buffet process for latent features, generates K 1903.00114 §7.2. Birth, death, split and merge moves change K during MCMC 1903.00114 §7.2.

When to use which

The review's own comparison tables classify each model by graph type, directedness, inference, clustering and number of groups; they are classifications, not measured results 1903.00114 tab. 1 tab. 2 tab. 3 tab. 4.

Implementation sketch

Generative side: sample memberships from the group probabilities, then draw each dyad as a Bernoulli trial with the block entry for its two groups. This is the base model; variants change the draw.

# Sample an undirected Bernoulli SBM  [arxiv:1903.00114 §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 a multinomial  [arxiv:1903.00114 §2] [eq. 4]
    memberships = draw_categorical(theta, size=n)
    adjacency = zeros(n, n)
    # Each dyad is an independent Bernoulli draw given the groups  [arxiv:1903.00114 §2]
    for p in range(n):
        for q in range(p + 1, n):
            # The edge rate is the block entry for the two groups  [arxiv:1903.00114 §2]
            rate = C[memberships[p], memberships[q]]
            adjacency[p, q] = draw_bernoulli(rate)
            adjacency[q, p] = adjacency[p, q]
    return memberships, adjacency

Fitting side: for each candidate K, run a greedy label-switching search and keep the best objective. Then pick K by a criterion. The dyad count for two different groups is the product of their sizes; see the first pitfall under Contradictions.

# Greedy fit for a fixed K, then choose K by a criterion  [arxiv:1903.00114 §6.3] [§7.1]
# Input:  adjacency Y (n, n); candidate values ks; objective(labels, Y, K)
# Output: best labels and K

def fit_sbm(Y, ks):
    best = None
    for K in ks:
        # Start from an initial labelling into K groups  [arxiv:1903.00114 §6.3]
        labels = initial_labels(n_nodes(Y), K)
        # Move one node at a time; stop when no move raises the objective  [arxiv:1903.00114 §6.3]
        labels = greedy_label_switch(labels, Y, K, objective)
        # Score this K with a criterion such as ICL  [arxiv:1903.00114 §7.1]
        score = criterion(labels, Y, K)
        if best is None or score > best.score:
            best = Result(labels, K, score)
    return best

Contradictions

• Group counts in text versus table. The text says Tallberg used K = 2 and Karrer & Newman used K = 3 1903.00114 §7. Table 1 lists Tallberg as Fixed (3) and Karrer & Newman as Fixed (2) 1903.00114 tab. 1. Check the source before using either value.
• Karate club, degree correction. The DC-SBM recovers the two known factions and the plain SBM does not 1903.00114 §8.1. A likelihood-ratio test on the same network finds no clear evidence for degree correction, though degree heterogeneity prompted it 1903.00114 §8.1. The review reports both without resolving them.
• Karate club, selected K. Under the DC-SBM, the ICL selects K = 1; under the plain SBM it selects K = 4, with groups following degree levels 1903.00114 §8.1. Decelle et al. and Newman & Reinert both find K = 2 as the best fit 1903.00114 §8.1.
• Political blogs, selected K. A penalised likelihood selects K = 4, where one label group splits into three inferred groups. At another tuning value it selects K = 1, which the review says motivates a corrected BIC with a heavier penalty 1903.00114 §8.1.
• Latent feature models labelled hard. The review says a latent-feature node can have several 1s, unlike hard SBM membership 1903.00114 §5.1, yet Table 1 labels the two latent-feature models as Hard 1903.00114 tab. 1.
• Dyad count for different groups. The text gives N_ij = N_iN_j/2 for i ≠ j 1903.00114 §2 eq. 3. The review's example densities match dividing by N_iN_j instead: 37/(25·30) ≈ 0.049 for groups 1 and 2, and 36/(25·35) ≈ 0.041 for groups 1 and 3 1903.00114 §2. Dividing by N_iN_j/2 would give about 0.099 for groups 1 and 2. Implementations should follow the example.
• Results are not comparable across papers. Studies use different networks, sizes and criteria, so their outcomes differ for reasons beyond the model 1903.00114 §11.4 §12.1.

Papers

• A Review of Stochastic Block Models and Extensions for Graph Clustering: a survey of SBM variants, inference methods and ways to choose K, with four comparison tables and no experiments of its own.
• Adaptive Universal Generalized PageRank Graph Neural Network: uses a contextual SBM with a homophily knob to generate the synthetic graphs for its node-classification experiments.
• MSGNN: a signed, directed spectral GNN. It defines the signed directed SBM and uses it, with two older signed SBMs, for node-clustering tests.