Stochastic Block Model (SBM)

The defining characteristic of an SBM is that the probability of an edge between any two nodes depends solely on their block (community) assignments. This is formalized by a connectivity matrix, B, where B[r, s] specifies the probability of an edge between a node in block r and a node in block s. This creates a homogeneous connection pattern within and between blocks, abstracting away individual node identities.

• Intra-block edges: Probability B[r, r] controls connection density within community r.
• Inter-block edges: Probability B[r, s] (for r ≠ s) controls connection density between communities r and s.

The connectivity matrix B dictates the model's fundamental community pattern. In an assortative SBM, the diagonal entries of B (intra-block probabilities) are significantly larger than the off-diagonal entries (inter-block probabilities). This models networks where nodes preferentially connect to others within their same community, like social friendship circles.

Conversely, a disassortative SBM has larger off-diagonal probabilities, modeling networks where connections are more likely between different blocks, such as in bipartite networks (e.g., author-paper graphs) or certain economic buyer-seller networks.

The SBM defines a clear, step-by-step generative process for creating a random graph G=(V, E):

1. For each node i, assign it to a block z_i ∈ {1,...,K} according to a prior distribution (e.g., categorical).
2. For each pair of nodes (i, j), independently sample an edge A_{ij} = 1 with probability B[z_i, z_j], and A_{ij} = 0 otherwise.

This process enables both synthesis of graphs with controlled community structure and statistical inference. Given an observed graph, algorithms like variational inference or Markov Chain Monte Carlo (MCMC) can be used to infer the most likely block assignments z and the matrix B, a task known as community detection.

The SBM is a direct generalization of the classic Erdős–Rényi (ER) model. An ER graph G(n, p) is equivalent to an SBM with a single block (K=1), where the connectivity matrix B is simply the scalar p. This highlights the SBM's role as a more expressive, structured prior for random graphs. When K>1, the SBM introduces heterogeneity in connection probabilities that the homogeneous ER model cannot capture, making it a fundamental tool for modeling real-world networks with mesoscale structure.

The standard SBM has known limitations, leading to numerous extensions that increase its expressiveness:

• Degree-Corrected SBM (DC-SBM): Separates node degree (popularity) from community membership by introducing node-specific parameters, correcting the SBM's tendency to generate blocks with overly homogeneous degree distributions.
• Overlapping SBM: Allows nodes to belong to multiple blocks (communities) simultaneously via mixed memberships.
• Hierarchical SBM: Organizes blocks into a tree structure, modeling communities and sub-communities.

A core limitation is its exchangeability within blocks; it cannot model degree heterogeneity or transitivity (clustering) beyond what is specified by the block probabilities, which is why extensions like the DC-SBM are critical for fitting real-world data.

The SBM serves as a critical tool and benchmark in graph machine learning:

• Synthetic Graph Generation: It is the canonical model for generating benchmark datasets with ground-truth communities to test community detection and graph representation learning algorithms.
• Theoretical Analysis: Its well-defined probabilistic structure allows for rigorous analysis of algorithmic detectability limits (the community detection threshold) and the expressive power of models like Graph Neural Networks (GNNs).
• Anomaly Detection: Nodes or edges that significantly deviate from the connection patterns predicted by a fitted SBM can be flagged as anomalies.
• Foundational Prior: It acts as a foundational component in more complex generative graph models, such as certain Graph Variational Autoencoders (Graph VAEs), where the latent space may encode block-like structures.

An Exponential Random Graph Model (ERGM) is a statistical model that defines the probability of observing a given network as an exponential function of a set of sufficient network statistics. Unlike the SBM, which defines communities explicitly, ERGMs model the probability of the entire graph based on global features.

• Core Mechanism: The probability of a graph G is given by P(G) ∝ exp(θ⋅s(G)), where s(G) is a vector of network statistics (e.g., number of edges, triangles, or k-stars) and θ are model parameters.
• Key Difference from SBM: ERGMs are typically descriptive models used for statistical inference on an observed network, asking "what features characterize this network?" SBMs are more often used as generative models for creating networks with a planted community structure.
• Application: Used in social network analysis to understand which structural features (reciprocity, transitivity) are over- or under-represented in an observed network.

A Graph Generative Adversarial Network (GraphGAN) is a deep learning framework that adapts the adversarial training paradigm of GANs to the generation of graph-structured data. It pits a generator against a discriminator in a minimax game.

• Generator: Creates synthetic graphs, often node-by-node or edge-by-edge.
• Discriminator: Evaluates whether a given graph (or subgraph) is real (from the training data) or fake (from the generator).
• Contrast with SBM: While SBMs are parametric, interpretable, and rely on explicit block assignments, GraphGANs are non-parametric, data-driven, and can capture more complex and subtle topological patterns without a pre-defined community model. They are part of the deep generative model family for graphs, alongside Graph VAEs and Diffusion Models.

A Graph Variational Autoencoder (Graph VAE) is a deep generative model that learns a low-dimensional, probabilistic latent representation of a graph and can generate new graphs by sampling from this latent space and decoding.

• Architecture: Consists of an encoder (often a GNN) that maps a graph to a distribution in latent space (mean and variance vectors), and a decoder that reconstructs a graph from a latent sample.
• Training Objective: Maximizes the Evidence Lower Bound (ELBO), which balances reconstruction fidelity with keeping the latent distribution close to a prior (e.g., a standard Gaussian).
• Relation to SBM: The latent space in a Graph VAE can be seen as a learned, continuous, and often more flexible alternative to the discrete block assignments in an SBM. It can generate graphs with properties beyond simple community structure.

The Degree-Corrected Stochastic Block Model (DC-SBM) is a crucial extension of the standard SBM that accounts for the heterogeneous degree distributions (i.e., variation in how many connections nodes have) commonly found in real-world networks.

• Problem with Standard SBM: The basic SBM assumes all nodes within the same block have the same expected degree, leading to unrealistic, homogeneously connected communities.
• Solution: The DC-SBM introduces a node-specific parameter (θ_i) that scales the connection probability. The probability of an edge between node i (in block r) and node j (in block s) becomes: P(A_{ij}=1) = θ_i θ_j B_{rs}.
• Impact: This model is far more effective at generating and fitting real-world networks like social or citation networks, where a few "hub" nodes have many connections while most nodes have few.

The Mixed Membership Stochastic Block Model (MMSB) generalizes the SBM by allowing each node to have mixed, or fractional, membership across multiple blocks (communities). This reflects the reality that entities often belong to several overlapping groups.

• Core Concept: Instead of a hard, single block assignment z_i, each node i has a probability vector π_i over K blocks. For each potential edge (i,j), a block assignment is drawn for both nodes from their respective membership vectors, and the connection is determined by the block-block matrix B for that pair of assignments.
• Use Case: Ideal for modeling social networks where a person belongs to a family, a workplace, and a hobby group simultaneously, and their interactions depend on which "role" they are acting in for a given connection.
• Contrast: Provides a richer, more flexible representation than the hard-clustering assumption of the classic SBM.

Graph Isomorphism is the problem of determining whether two graphs are structurally identical. The Weisfeiler-Lehman (WL) test is a classical, efficient heuristic for this problem, and its theory underpins the analysis of Graph Neural Networks.

• WL Test Procedure: An iterative algorithm that colors nodes based on the multiset of colors in their neighborhood, then hashes these colors into new colors. After several iterations, if the histograms of colors between two graphs differ, they are non-isomorphic.
• Connection to SBM & GNNs: The WL test's power to distinguish graphs sets an upper bound on the expressive power of message-passing GNNs. Since the SBM generates graphs based on coarse block structure, two different SBM parameterizations could generate graphs that are indistinguishable to a WL test of limited iterations, which has implications for the learnability and identifiability of SBMs using GNNs.