Graph Neural Networks (GNNs) have become the standard for modeling relational data, but they face a fundamental scalability bottleneck: the "neighbor explosion" problem. As identified in Graph Neural Networks: A Review of Methods and Applications, the recursive nature of message passing causes the number of nodes required for a single update to grow exponentially with the number of layers.
If each node has an average degree $d$, a $k$-layer GNN requires information from $O(d^k)$ neighbors. In dense or "small-world" graphs, a 3-layer model might need to touch nearly the entire graph to compute a single node's representation. This makes mini-batch training—the engine of modern deep learning—computationally prohibitive and memory-intensive. Researchers have developed three primary strategies to break this "memory wall": sampling, decoupling, and coarsening.
Sampling the Receptive Field
The most direct way to handle neighbor explosion is to avoid aggregating the full neighborhood. Early methods used node-wise sampling, but this still suffered from high variance. Jianfei Chen and colleagues addressed this in Stochastic Training of Graph Convolutional Networks by introducing a control variate-based approach. By using historical node activations to reduce sampling variance, they showed that a GCN could be trained using as few as two neighbors per node without losing accuracy.
Other researchers shifted the sampling unit from nodes to layers or subgraphs:
- Layer-wise Sampling: Wenbing Huang and Yu Rong proposed Adaptive Layer-wise Sampling in Adaptive Sampling Towards Fast Graph Representation Learning. Instead of sampling neighbors for each node independently, they sample a fixed number of nodes per layer, which bounds the computational cost regardless of the graph's density.
- Subgraph Sampling: Hanqing Zeng introduced GraphSAINT, which samples entire subgraphs for each mini-batch. This completely eliminates the need to fetch multi-hop neighbors during training, as the message passing is restricted to the sampled subgraph.
- Bandit-based Sampling: To make sampling more efficient over time, Qingru Zhang and David Wipf developed Thanos in A Biased Graph Neural Network Sampler with Near-Optimal Regret, which uses a bandit framework to learn the most informative nodes to sample.
Decoupling Aggregation from Transformation
A second approach involves changing the GNN architecture itself to remove the recursive dependency. In standard GNNs, feature transformation and neighborhood aggregation are interleaved. Emanuele Rossi and his team proposed SIGN: Scalable Inception Graph Neural Networks, which precomputes different "hops" of the graph (e.g., $A^1X, A^2X, \dots$) as a preprocessing step. This allows the model to use simple MLPs for training, making it as scalable as standard deep learning on non-graph data.
Similarly, Sunil Kumar Maurya introduced FSGNN in Improving Graph Neural Networks with Simple Architecture Design, which uses precomputed neighborhood features and a learnable selection mechanism. This "uncoupled" approach is also seen in SAS: A Simple, Accurate and Scalable Node Classification Algorithm by Ziyuan Wang, which reorders operations to ensure memory consumption remains constant even as the graph grows to millions of nodes.
Structural Regularization and Coarsening
Rather than sampling or decoupling, some researchers focus on reducing the graph's complexity before training begins. Chong Xi demonstrated in Scaling Up Graph Neural Networks Via Graph Coarsening that training a GNN on a significantly smaller, coarsened version of the graph can yield weights that generalize well to the original, massive graph. This "train small, predict big" strategy acts as a form of structural regularization, often improving accuracy while slashing memory requirements.
This multi-resolution intuition is further explored in SMGRL: A Scalable Multi-resolution Graph Representation Learning Framework by Reza Namazi, which applies a single GCN across a hierarchy of graph resolutions to capture both local and global dependencies without the depth-related tax of neighbor explosion.
Local and Bidirectional Propagation
Finally, new propagation algorithms aim for sub-linear time complexity. Ming Chen and Zhewei Wei introduced GBP in Scalable Graph Neural Networks via Bidirectional Propagation. By using a localized bidirectional algorithm, GBP can process graphs with billions of edges on a single machine in minutes. This shift toward "strict locality," also seen in the quantum operator modeling of SLEM by Zhanghao Zhouyin, ensures that the receptive field is strictly bounded, enabling massive parallelization and real-time inference on industrial-scale networks.