Mitigating Neighbor Explosion in Scalable Graph Neural Networks

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2328 papers356 conceptsfrozen 2026-10-04

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:

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.

Papers in this version

Showing 60 of 328 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 275 papers
  2. Version 1 · 2026-10-04 · 328 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_neighbor_explosion_633ec7bb,
  title = {neighbor explosion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/neighbor-explosion/rdr_633ec7bb8c744a989aa88e653e286423},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_mitigating_neighbor_explosion_in_scalabl_633ec7bb_v1,
  title = {Mitigating Neighbor Explosion in Scalable Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/mitigating-neighbor-explosion-in-scalable-graph-neural-networks/rdr_633ec7bb8c744a989aa88e653e286423/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}