Abstract
Graph Neural Networks (GNNs) face a significant challenge in scaling to large graphs due to the "neighbor explosion" problem, where the number of nodes required for computation grows exponentially with network depth. This paper introduces Blocking-based Neighbor Sampling (BNS), a novel strategy that stochastically "blocks" a fraction of neighbors from further expansion during recursive sampling. By combining this with a reweighted graph convolution to maintain unbiasedness, BNS significantly reduces computational overhead. Experiments on massive datasets like OGBN-Papers100M demonstrate that BNS achieves a 2x to 5x speedup over state-of-the-art methods while maintaining or improving accuracy.
The Challenge: Neighbor Explosion
The core challenge in scaling GNNs is the iterative dependency of nodes. To calculate the representation of a node at layer $L$, one requires the representations of its neighbors at layer $L-1$. These neighbors, in turn, require their own neighbors at layer $L-2$. If a node has an average degree of $s$, the number of nodes involved in a single update grows at a rate of $O(s^L)$. On a graph with 100 million nodes, even a 5-layer GNN can quickly exhaust GPU memory. Existing solutions like node-wise sampling still suffer from high time costs, while subgraph sampling can lead to sparse connection issues that degrade structural information.
Methodology: Blocking and Reweighting
To address this, BNS adopts a two-pronged approach: Blocking and Reweighting.
1. The Blocking Mechanism
Instead of allowing every sampled neighbor to trigger a new round of sampling for the next layer, BNS implements a "stop-and-stay" policy. For each node, it samples $s_n$ neighbors and then randomly "blocks" a fraction $\delta$ of them.
- Blocked nodes (black nodes in the figure) contribute their current features to the central node but do not expand further into deeper layers.
- Non-blocked nodes (red nodes) continue the expansion process as usual.
This effectively reduces the branching factor from $s_n$ to $\tilde{s}_n = s_n \times (1 - \delta)$, curbing the exponential growth of the computation graph.
2. Reweighted Graph Convolution
Because blocked nodes provide less information (as they do not aggregate from deeper layers), a naive calculation would lead to biased results. The authors introduce a reweighted policy to adjust the contribution of blocked vs. non-blocked neighbors. They mathematically prove that with the appropriate weights $\rho$, BNS provides an unbiased estimation of the original graph convolution operation, ensuring the model optimizes the intended objective.
Experimental Evaluation
The researchers evaluated BNS on three major benchmarks from the Open Graph Benchmark (OGB):
- ogbn-proteins: A small-scale graph (~132k nodes) representing biological interactions.
- ogbn-products: A large-scale graph (~2.4M nodes) of Amazon product co-purchases.
- ogbn-papers100M: A massive-scale graph (~111M nodes) of citation networks, one of the largest publicly available GNN benchmarks.
Key Results and Insights
BNS demonstrates superior efficiency and scalability across various graph sizes:
- Significant Speedup: On
ogbn-products, BNS was roughly 4x to 5x faster than GraphSAINT and standard Node Sampling (NS) while reaching the same 80% accuracy threshold. - Massive Scale Performance: On the 111-million-node
ogbn-papers100Mdataset, BNS achieved the highest accuracy (63.88%) in the shortest time ($1.2 \times 10^4$ seconds), outperforming standard node-wise sampling by a significant margin. - Preserving Density: Unlike standard sampling that simply picks fewer neighbors, BNS allows a node to "see" many neighbors but only "follows" a few deeper. This preserves local density while saving global computation.
Conclusion
BNS offers a mathematically grounded and computationally efficient solution to the neighbor explosion problem. By pruning the computation tree through blocking while maintaining unbiasedness through reweighting, it enables the training of deep GNNs on massive graphs with significantly reduced time and memory overhead. Future work may explore adaptive blocking rates and the application of BNS to attention-based architectures like GAT.
Summary updated