mlsanityData to 7 Oct 2026

BNS-GCN: Efficient Full-Graph Training of Graph Convolutional Networks with Partition-Parallelism and Random Boundary Node Sampling

arXiv 2203.10983 ↗First posted 21 Mar 2022cs.LG cs.AIcited by 43

Not on the map. Why?

Abstract (arXiv)

Graph Convolutional Networks (GCNs) have emerged as the state-of-the-art method for graph-based learning tasks. However, training GCNs at scale is still challenging, hindering both the exploration of more sophisticated GCN architectures and their applications to real-world large graphs. While it might be natural to consider graph partition and distributed training for tackling this challenge, this direction has only been slightly scratched the surface in the previous works due to the limitations of existing designs. In this work, we first analyze why distributed GCN training is ineffective and identify the underlying cause to be the excessive number of boundary nodes of each partitioned subgraph, which easily explodes the memory and communication costs for GCN training. Furthermore, we propose a simple yet effective method dubbed BNS-GCN that adopts random Boundary-Node-Sampling to enable efficient and scalable distributed GCN training. Experiments and ablation studies consistently validate the effectiveness of BNS-GCN, e.g., boosting the throughput by up to 16.2x and reducing the memory usage by up to 58%, while maintaining a full-graph accuracy. Furthermore, both theoretical and empirical analysis show that BNS-GCN enjoys a better convergence than existing sampling-based methods. We believe that our BNS-GCN has opened up a new paradigm for enabling GCN training at scale. The code is available at https://github.com/RICE-EIC/BNS-GCN.

Key facts. Cited by 43 papers in the map (data through 7 Oct 2026). Builds on 28 of its 49 references that are in the map. First posted on arXiv 21 Mar 2022.

Builds on

28 of 49 references.

References · 28

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2017Inductive Representation Learning on Large Graphscited by 6,284
  5. 2018How Powerful are Graph Neural Networks?cited by 4,355
  6. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  7. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  8. 2018Link Prediction Based on Graph Neural Networkscited by 829
  9. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 679
  10. 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
  11. 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 583
  12. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 540
16 more
  1. 2014One weird trick for parallelizing convolutional neural networkscited by 264
  2. 2019SGD: General Analysis and Improved Ratescited by 206
  3. 2018Adaptive Sampling Towards Fast Graph Representation Learningcited by 180
  4. 2019Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networkscited by 177
  5. 2019AliGraph: A Comprehensive Graph Neural Network Platformcited by 152
  6. 2020DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphscited by 139
  7. 2019PyTorch-BigGraph: A Large-scale Graph Embedding Systemcited by 118
  8. 2018PipeDream: Fast and Efficient Pipeline Parallel DNN Trainingcited by 116
  9. 2021GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddingscited by 90
  10. 2020Scalable Graph Neural Networks via Bidirectional Propagationcited by 87
  11. 2020Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networkscited by 54
  12. 2021Dorylus: Affordable, Scalable, and Accurate GNN Training with Distributed CPU Servers and Serverless Threadscited by 51
  13. 2020Reducing Communication in Graph Neural Network Trainingcited by 50
  14. 2022PipeGCN: Efficient Full-Graph Training of Graph Convolutional Networks with Pipelined Feature Communicationcited by 45
  15. 2018Pipe-SGD: A Decentralized Pipelined SGD Framework for Distributed Deep Net Trainingcited by 28
  16. 2013Recent Advances in Graph Partitioningcited by 24

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 5; 2023: 18; 2024: 8; 2025: 7; 2026: 5.

43 papers.

Sort:

  1. 2022Distributed Graph Neural Network Training: A Surveycited by 32
  2. 2022MLPInit: Embarrassingly Simple GNN Training Acceleration with MLP Initializationcited by 31
  3. 2022Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysiscited by 29
  4. 2023MaxK-GNN: Extremely Fast GPU Kernel Design for Accelerating Graph Neural Networks Trainingcited by 25
  5. 2023A Survey on Graph Neural Network Acceleration: Algorithms, Systems, and Customized Hardwarecited by 18
  6. 2023LazyGNN: Large-Scale Graph Neural Networks via Lazy Propagationcited by 16
  7. 2023Communication-Efficient Graph Neural Networks with Probabilistic Neighborhood Expansion Analysis and Cachingcited by 16
  8. 2022RSC: Accelerating Graph Neural Networks Training via Randomized Sparse Computationscited by 12
  9. 2022Neural Graph Databasescited by 11
  10. 2023Adaptive Message Quantization and Parallelization for Distributed Full-graph GNN Trainingcited by 10
  11. 2024Graph Neural Network Training Systems: A Performance Comparison of Full-Graph and Mini-Batchcited by 10
  12. 2023Learning Large Graph Property Prediction via Graph Segment Trainingcited by 9
31 more
  1. 2023Comprehensive Evaluation of GNN Training Systems: A Data Management Perspectivecited by 9
  2. 2023SUREL+: Moving from Walks to Sets for Scalable Subgraph-based Graph Representation Learningcited by 8
  3. 2024Federated Graph Condensation with Information Bottleneck Principlescited by 8
  4. 2023GSplit: Scaling Graph Neural Network Training on Large Graphs via Split-Parallelismcited by 6
  5. 2023Staleness-Alleviated Distributed GNN Training via Online Dynamic-Embedding Predictioncited by 6
  6. 2023Distributed Matrix-Based Sampling for Graph Neural Network Trainingcited by 6
  7. 2024DiskGNN: Bridging I/O Efficiency and Model Accuracy for Out-of-Core GNN Trainingcited by 5
  8. 2023FreshGNN: Reducing Memory Access via Stable Historical Embeddings for Graph Neural Network Trainingcited by 4
  9. 2023GNNPipe: Scaling Deep GNN Training with Pipelined Model Parallelismcited by 4
  10. 2025Scaling Laws of Graph Neural Networks for Atomistic Materials Modelingcited by 4
  11. 2023Boosting Distributed Full-graph GNN Training with Asynchronous One-bit Communicationcited by 3
  12. 2024FastGL: A GPU-Efficient Framework for Accelerating Sampling-Based GNN Training at Large Scalecited by 3
  13. 2024FedGraph: A Research Library and Benchmark for Federated Graph Learningcited by 3
  14. 2025Sparsity-Aware Communication for Distributed Graph Neural Network Trainingcited by 3
  15. 2023BatchGNN: Efficient CPU-Based Distributed GNN Training on Very Large Graphscited by 2
  16. 2023Communication-Free Distributed GNN Training with Vertex Cutcited by 2
  17. 2023GraNNDis: Efficient Unified Distributed Training Framework for Deep GNNs on Large Clusterscited by 2
  18. 2025Reforge: Low-Latency Distributed GNN Serving with Selective Embedding Recomputationcited by 2
  19. 2025LPS-GNN : Deploying Graph Neural Networks on Graphs with 100-Billion Edgescited by 2
  20. 2023Auto-Differentiation of Relational Computations for Very Large Scale Machine Learningcited by 1
  21. 2024LSM-GNN: Large-scale Storage-based Multi-GPU GNN Training by Optimizing Data Transfer Schemecited by 1
  22. 2024PromptGCN: Bridging Subgraph Gaps in Lightweight GCNscited by 1
  23. 2025Plexus: Taming Billion-edge Graphs with 3D Parallel Full-graph GNN Trainingcited by 1
  24. 2024FedGAT: A Privacy-Preserving Federated Approximation Algorithm for Graph Attention Networkscited by 0
  25. 2025MixGCN: Scalable GCN Training by Mixture of Parallelism and Mixture of Acceleratorscited by 0
  26. 2025Hierarchical graph sampling based minibatch learning with chain preservation and variance reductioncited by 0
  27. 2026Grappa: Gradient-Only Communication for Scalable Graph Neural Network Trainingcited by 0
  28. 2026Communication-free Sampling and 4D Hybrid Parallelism for Scalable Mini-batch GNN Trainingcited by 0
  29. 2026Scalable and Adaptive Parallel Training of Graph Transformer on Large Graphscited by 0
  30. 2026SNI-GNN: SmartNIC-Assisted Full-Graph GNN Training with In-Network Embedding Predictioncited by 0
  31. 2026Two-level domain-decomposition AdaGrad method for scalable training of graph neural networkscited by 0