In traditional deep learning, mini-batching is straightforward. If you want to train a model on a dataset of images, a mini-batch of size 32 requires exactly 32 independent images. However, when training Graph Neural Networks (GNNs) on relational data, this independence assumption breaks down.
Because GNNs compute a node's representation by aggregating features from its neighbors, updating a single node at layer $L$ requires data from its neighbors at layer $L-1$. To compute the states of those neighbors, the model must fetch their neighbors at layer $L-2$, and so on. If a graph has an average node degree of $d$, the number of nodes required to compute a single target node's representation scales exponentially as $O(d^L)$.
This phenomenon is known as neighbor explosion (or neighborhood expansion). As highlighted by Jianfei Chen et al. in Stochastic Training of Graph Convolutional Networks with Variance Reduction, this recursive dependency makes full-batch training on large-scale graphs impossible due to hardware memory limits, while making naive mini-batching computationally prohibitive. In dense or small-world networks, a mini-batch of just a few dozen nodes can quickly expand to encompass nearly the entire graph.
To scale GNNs to massive datasets, researchers have developed three core paradigms to bypass or eliminate this exponential bottleneck: neighborhood sampling, subgraph isolation, and feature propagation decoupling.
Pruning the Tree: Node and Layer-Wise Sampling
The most intuitive way to stop an exponential explosion is to prune the expansion tree. Instead of aggregating information from all neighbors, what if we only look at a random subset?
Node-Wise Sampling and Variance Reduction
Early approaches restricted the expansion by sampling a fixed number of neighbors, $k$, per node. While this bounds the worst-case complexity to $O(k^L)$, the growth remains exponential with respect to network depth. Furthermore, discarding neighbors introduces significant stochastic variance into the message-passing step, which can destabilize training.
To resolve this, Jianfei Chen et al. proposed a control variate-based stochastic training algorithm. By maintaining historical activations of nodes, the control variates act as a memory buffer that approximates the missing neighborhood information. This reduces sampling variance to near zero, allowing models to train accurately with as few as $k=2$ neighbors per node, significantly flattening the expansion curve.
Layer-Wise Sampling
Rather than sampling neighbors independently for each node (which causes redundant evaluations when neighborhoods overlap), layer-wise sampling changes the geometry of the sample.
In FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling, Jie Chen et al. proposed sampling a fixed number of nodes per layer globally, rather than per node. By treating the vertices in each layer as independent samples from a probability distribution, the computational complexity drops from exponential ($O(k^L)$) to linear ($O(L \cdot k)$).
Node-Wise Sampling (Exponential) Layer-Wise Sampling (Linear)
[Target Node] [Target Node]
/ \ / \
[Node A] [Node B] [Layer L-1 Sampled Pool]
/ \ / \ / \
[...] [...] [...] [...] [Layer L-2 Sampled Pool]
To make this efficient, the authors used importance sampling, prioritizing nodes with higher degrees since they contribute more to the message-passing gradients. Wenbing Huang et al. advanced this concept in Adaptive Sampling Towards Fast Graph Representation Learning by introducing an adaptive, variance-reducing sampler that updates the sampling distributions layer-by-layer during training, ensuring that the most informative graph structures are preserved.
Bypassing the Tree: Subgraph Isolation
An alternative strategy is to avoid expanding neighborhoods altogether. Instead of starting with a batch of target nodes and reaching outward, subgraph-based training partitions the massive input graph into smaller, self-contained subgraphs.
As demonstrated by Hanqing Zeng et al. in Accurate, Efficient and Scalable Graph Embedding, training on these induced subgraphs completely eliminates neighbor explosion across layers. Because the GNN operations are restricted entirely within the boundaries of the sampled subgraph, the memory and computational footprint remains strictly bounded, regardless of how deep the network is.
The challenge shifts to ensuring that the sampled subgraphs retain the structural properties of the original graph. For instance, Jiyang Bai et al. developed Ripple Walk Training: A Subgraph-based training framework for Large and Deep Graph Neural Network, which uses a specialized exploration mechanism to balance randomness with local density. This ensures that long-range dependencies are not completely severed when the graph is broken into pieces.
Eliminating the Tree: Decoupling Propagation from Transformation
The most radical solution to neighbor explosion is to question a fundamental assumption of GNNs: Does message passing need to happen during the gradient descent loop?
In a standard GNN layer, feature propagation (averaging neighbor features) and feature transformation (multiplying by a weight matrix and applying an activation function) are tightly coupled. Because transformation happens at every layer, the model must maintain the entire multi-hop dependency tree in memory to compute backpropagation gradients.
Feature Propagation Decoupling
If the underlying graph structure is static, feature propagation is a deterministic linear operation. We can decouple propagation from transformation by executing all message-passing steps upfront as a preprocessing step.
Standard GNN Layer:
[Input] -> [Propagate & Transform] -> [Propagate & Transform] -> [Output]
Decoupled GNN (e.g., HopGNN / GAMLP):
[Input] -> [Precompute Multi-Hop Propagation] -> [Train Simple MLP] -> [Output]
In L2-GCN: Layer-Wise and Learned Efficient Training of Graph Convolutional Networks, Yuning You et al. showed that separating these operations allows the memory footprint to remain constant relative to graph size.
Taking this further, Jie Chen et al. introduced From Node Interaction to Hop Interaction: New Effective and Scalable Graph Learning Paradigm. Their architecture, HopGNN, precomputes multi-hop features for each node and shifts the learning mechanism to model the relationships between these hops within a single node.
Similarly, Wentao Zhang et al. proposed the Graph Attention Multi-Layer Perceptron (GAMLP), which applies attention mechanisms directly to these precomputed multi-scale features. Because the graph structure is fully absorbed during preprocessing, the actual training phase behaves exactly like a standard Multi-Layer Perceptron (MLP). Mini-batches can be sampled completely at random without fetching any neighbors, scaling effortlessly to billions of nodes.