Scaling Graph Neural Networks via Partitioning and Sampling

This direction is split into other directions: subgraph-based training. Its last version stays readable and citable here.

Version 1 of 1371 papers467 conceptsfrozen 2026-10-04

Standard Graph Neural Networks (GNNs) suffer from a fundamental scalability crisis known as "neighbor explosion." Because GNNs compute a node's representation by aggregating information from its neighbors, and those neighbors in turn aggregate from their own neighbors, the computational graph grows exponentially with the number of layers. On massive datasets with billions of edges, a single update can end up requiring the entire graph to be loaded into memory—a feat impossible for modern GPUs.

To solve this, researchers have developed a suite of techniques to decouple the model's memory requirements from the total size of the graph. By intelligently sampling local neighborhoods and partitioning global structures, it is now possible to train GNNs on 100-billion-edge graphs using a single GPU.

The Neighbor Explosion Problem

In a review of the field, Maosong Sun and Ganqu Cui explain that the primary bottleneck in scaling GNNs is the recursive nature of neighborhood aggregation. In Graph Neural Networks: A Review of Methods and Applications, they note that as we move to multi-hop neighborhoods, the number of nodes involved grows so rapidly that standard matrix-based aggregation becomes computationally prohibitive.

The goal of scalable GNN research is to transform this $O(n^2)$ or high-degree polynomial complexity into something closer to linear time, allowing models to process data in manageable chunks without losing the critical relational context that makes GNNs useful.

Intelligent Sampling for Local Efficiency

The most direct way to stop neighbor explosion is to simply not look at every neighbor. Sampling techniques select a representative subset of the graph for each training step.

One sophisticated approach involves leverage scores. Seiyun Shin and Han Zhao demonstrate in Efficient Learning of Linear Graph Neural Networks via Node Subsampling that data-dependent sampling can reduce the memory footprint by over a thousand-fold. By using leverage scores to identify which nodes contribute most to the model's accuracy, they achieve a 40x speedup while maintaining theoretical guarantees.

In heterogeneous environments where nodes have different types, sampling becomes more complex. Zhaoning Yu and Hongyang Gao introduced a breadth-first search (BFS) sampling strategy in Molecular Representation Learning via Heterogeneous Motif Graph Neural Networks. Their method prioritizes essential molecule-to-motif connections while sub-sampling less critical interactions, allowing the model to capture high-order chemical relationships without exhausting hardware memory.

Graph Partitioning and the Halo Effect

While sampling handles local neighborhoods, partitioning addresses the global memory limit. The idea is to break a massive graph into smaller, disjoint subgraphs that can be processed independently.

A common tool for this is the METIS algorithm. In Learning to Cluster Faces via Hypergraph Convolution with Transformer on Large Graph, Dengdi Sun and Zhizhong Huang use METIS to divide k-nearest neighbor graphs into non-overlapping subgraphs. This prevents "out-of-memory" errors when clustering millions of faces.

However, partitioning creates a new problem: nodes at the boundary of a partition lose access to their neighbors in other partitions. To fix this, researchers use "halo" regions. Mohammad Amin Nabian describes this in X-MeshGraphNet: Scalable Multi-Scale Graph Neural Networks for Physics Simulation. By including a "halo" of boundary nodes from adjacent partitions, distributed training becomes mathematically equivalent to training on the full graph. This allows high-fidelity physics simulations to scale across multiple GPUs seamlessly.

Decoupling and Mini-Batching

To make GNNs as easy to train as standard neural networks, researchers are moving toward mini-batching and gradient decoupling.

In the realm of biology, the SemanticST framework applies mini-batch training to spatial transcriptomics, enabling the analysis of datasets with over 500,000 cells. By processing data in smaller batches, the model avoids the need to load the entire cellular landscape into memory at once.

A more radical approach is to decouple the neighbor encoding from the training process entirely. In Efficient Large Language Models Fine-Tuning On Graphs, Rui Xue and Xiaorui Liu introduce the LEADING framework. It uses a non-gradient pipeline for neighbor encoding and caches the results. This restricts heavy gradient calculations to target nodes only, reducing memory overhead to levels comparable with standard, graph-less text fine-tuning.

Reaching the 100-Billion Edge Frontier

The culmination of these techniques allows for extreme scaling. Feng He and Jie Tang recently demonstrated LPS-GNN, a system capable of deploying GNNs on graphs with 100 billion edges. By optimizing how partitions are loaded and sampled, they proved that industrial-scale graph learning—once the exclusive domain of massive distributed clusters—can now be achieved with significantly lower hardware requirements.

Similarly, the SANCUS system, developed by Jingshu Peng and Yingxia Shao, uses stale embedding caching and quantization to reduce communication overhead in decentralized training. As detailed in From Sancus to Sancusq, these optimizations allow for 3.0x faster throughput by avoiding up to 86% of the network traffic typically required to keep partitions synchronized.

Papers in this version

Showing 60 of 371 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scaling_graph_neural_networks_via_partit_b1c4b2a4,
  title = {Scaling Graph Neural Networks via Partitioning and Sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-graph-neural-networks-via-partitioning-and-sampling/rdr_b1c4b2a49b4641c19be1033de31fd7c7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_scaling_graph_neural_networks_via_partit_b1c4b2a4_v1,
  title = {Scaling Graph Neural Networks via Partitioning and Sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-graph-neural-networks-via-partitioning-and-sampling/rdr_b1c4b2a49b4641c19be1033de31fd7c7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}