mlsanityData to 7 Oct 2026

Scalable Graph Neural Networks via Bidirectional Propagation

arXiv 2010.15421 ↗First posted 29 Oct 2020cs.LGcited by 87

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks (GNN) is an emerging field for learning on non-Euclidean data. Recently, there has been increased interest in designing GNN that scales to large graphs. Most existing methods use "graph sampling" or "layer-wise sampling" techniques to reduce training time. However, these methods still suffer from degrading performance and scalability problems when applying to graphs with billions of edges. This paper presents GBP, a scalable GNN that utilizes a localized bidirectional propagation process from both the feature vectors and the training/testing nodes. Theoretical analysis shows that GBP is the first method that achieves sub-linear time complexity for both the precomputation and the training phases. An extensive empirical study demonstrates that GBP achieves state-of-the-art performance with significantly less training/testing time. Most notably, GBP can deliver superior performance on a graph with over 60 million nodes and 1.8 billion edges in less than half an hour on a single machine. The codes of GBP can be found at https://github.com/chennnM/GBP .

Key facts. Cited by 87 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 13; 2022: 24; 2023: 16; 2024: 21; 2025: 9; 2026: 4.

87 papers.

Sort:

By area:

  1. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  2. 2022NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphscited by 137
  3. 2022Data Augmentation for Deep Graph Learning: A Surveycited by 132
  4. 2021GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddingscited by 90
  5. 2022Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisitedcited by 87
  6. 2022Graph Attention Multi-Layer Perceptroncited by 82
  7. 2021Scaling Up Graph Neural Networks Via Graph Coarseningcited by 80
  8. 2021Graph-based Semi-supervised Learning: A Comprehensive Reviewcited by 79
  9. 2022A Survey on Graph Representation Learning Methodscited by 66
  10. 2021On the Unreasonable Effectiveness of Feature propagation in Learning on Graphs with Missing Node Featurescited by 62
  11. 2022A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphscited by 49
  12. 2021Node Dependent Local Smoothing for Scalable Graph Learningcited by 45
38 more
  1. 2022BNS-GCN: Efficient Full-Graph Training of Graph Convolutional Networks with Partition-Parallelism and Random Boundary Node Samplingcited by 43
  2. 2022Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPscited by 42
  3. 2022PaSca: a Graph Neural Architecture Search System under the Scalable Paradigmcited by 37
  4. 2023Graph Neural Networks with Learnable and Optimal Polynomial Basescited by 36
  5. 2023The expressive power of pooling in Graph Neural Networkscited by 35
  6. 2023VQGraph: Rethinking Graph Representation Space for Bridging GNNs and MLPscited by 34
  7. 2022GraphFM: Improving Large-Scale GNN Training via Feature Momentumcited by 31
  8. 2021Grain: Improving Data Efficiency of Graph Neural Networks via Diversified Influence Maximizationcited by 28
  9. 2022Model Degradation Hinders Deep Graph Neural Networkscited by 26
  10. 2022GRAND+: Scalable Graph Random Neural Networkscited by 25
  11. 2021Evaluating Deep Graph Neural Networkscited by 19
  12. 2022SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimizationcited by 19
  13. 2021Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networkscited by 18
  14. 2022Test-Time Training for Graph Neural Networkscited by 17
  15. 2022Instant Graph Neural Networks for Dynamic Graphscited by 16
  16. 2023Dynamic Causal Explanation Based Diffusion-Variational Graph Neural Network for Spatio-temporal Forecastingcited by 16
  17. 2024Rethinking Node-wise Propagation for Large-scale Graph Learningcited by 16
  18. 2024OpenFGL: A Comprehensive Benchmark for Federated Graph Learningcited by 16
  19. 2023Boosting Multitask Learning on Graphs through Higher-Order Task Affinitiescited by 15
  20. 2023Decoupled Graph Neural Networks for Large Dynamic Graphscited by 14
  21. 2024Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barriercited by 13
  22. 2023Federated Learning over Coupled Graphscited by 12
  23. 2022NAFS: A Simple yet Tough-to-beat Baseline for Graph Representation Learningcited by 11
  24. 2022On the Probability of Necessity and Sufficiency of Explaining Graph Neural Networks: A Lower Bound Optimization Approachcited by 11
  25. 2024LightDiC: A Simple yet Effective Approach for Large-scale Digraph Representation Learningcited by 11
  26. 2023SIGMA: An Efficient Heterophilous Graph Neural Network with Fast Global Aggregationcited by 10
  27. 2021RPT: Toward Transferable Model on Heterogeneous Researcher Data via Pre-Trainingcited by 9
  28. 2023Accelerating Scalable Graph Neural Network Inference with Node-Adaptive Propagationcited by 8
  29. 2024Two Trades is not Baffled: Condensing Graph via Crafting Rational Gradient Matchingcited by 8
  30. 2024Redesigning graph filter-based GNNs to relax the homophily assumptioncited by 8
  31. 2022Efficient Graph Neural Network Inference at Large Scalecited by 7
  32. 2024A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectivenesscited by 6
  33. 2022Alternately Optimized Graph Neural Networkscited by 4
  34. 2023You Only Transfer What You Share: Intersection-Induced Graph Transfer Learning for Link Predictioncited by 4
  35. 2023Tokenized Graph Transformer with Neighborhood Augmentation for Node Classification in Large Graphscited by 4
  36. 2024Generating Robust Counterfactual Witnesses for Graph Neural Networkscited by 4
  37. 2024Graph Neural Networks on Quantum Computerscited by 4
  38. 2024Towards Scalable and Deep Graph Neural Networks via Noise Maskingcited by 4

50 most cited of 87 All 87 (JSON)