# GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings

arXiv: https://arxiv.org/abs/2106.05609 · HTML: https://mlsanity.com/paper/2106.05609/

## Key facts

- Cited by 90 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 63 references that are in the map.
- First posted on arXiv 10 Jun 2021.

## Builds on (most cited first, 30 of 42)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space](https://mlsanity.com/paper/1706.02413/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Dynamic Graph CNN for Learning on Point Clouds](https://mlsanity.com/paper/1801.07829/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks](https://mlsanity.com/paper/2007.02901/) (2020)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)

## Built on by (most cited first, 30 of 90)

- [SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations](https://mlsanity.com/paper/2306.10759/) (2023)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Ordered Subgraph Aggregation Networks](https://mlsanity.com/paper/2206.11168/) (2022)
- [A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking](https://mlsanity.com/paper/2210.07494/) (2022)
- [PyG 2.0: Scalable Learning on Real World Graphs](https://mlsanity.com/paper/2507.16991/) (2025)
- [BNS-GCN: Efficient Full-Graph Training of Graph Convolutional Networks with Partition-Parallelism and Random Boundary Node Sampling](https://mlsanity.com/paper/2203.10983/) (2022)
- [Linkless Link Prediction via Relational Distillation](https://mlsanity.com/paper/2210.05801/) (2022)
- [VQGraph: Rethinking Graph Representation Space for Bridging GNNs and MLPs](https://mlsanity.com/paper/2308.02117/) (2023)
- [GraphFM: Improving Large-Scale GNN Training via Feature Momentum](https://mlsanity.com/paper/2206.07161/) (2022)
- [MLPInit: Embarrassingly Simple GNN Training Acceleration with MLP Initialization](https://mlsanity.com/paper/2210.00102/) (2022)
- [LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence](https://mlsanity.com/paper/2302.00924/) (2023)
- [SSSNET: Semi-Supervised Signed Network Clustering](https://mlsanity.com/paper/2110.06623/) (2021)
- [Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networks](https://mlsanity.com/paper/2107.10234/) (2021)
- [SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization](https://mlsanity.com/paper/2207.09179/) (2022)
- [Layer-Neighbor Sampling -- Defusing Neighborhood Explosion in GNNs](https://mlsanity.com/paper/2210.13339/) (2022)
- [Anomaly Detection in Dynamic Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2406.00134/) (2024)
- [Compressing Deep Graph Neural Networks via Adversarial Knowledge Distillation](https://mlsanity.com/paper/2205.11678/) (2022)
- [A Survey on Graph Neural Network Acceleration: Algorithms, Systems, and Customized Hardware](https://mlsanity.com/paper/2306.14052/) (2023)
- [Bag-of-Words vs. Graph vs. Sequence in Text Classification: Questioning the Necessity of Text-Graphs and the Surprising Strength of a Wide MLP](https://mlsanity.com/paper/2109.03777/) (2021)
- [SMORE: Knowledge Graph Completion and Multi-hop Reasoning in Massive Knowledge Graphs](https://mlsanity.com/paper/2110.14890/) (2021)
- [Hierarchical Transformer for Scalable Graph Learning](https://mlsanity.com/paper/2305.02866/) (2023)
- [LazyGNN: Large-Scale Graph Neural Networks via Lazy Propagation](https://mlsanity.com/paper/2302.01503/) (2023)
- [SelfCF: A Simple Framework for Self-supervised Collaborative Filtering](https://mlsanity.com/paper/2107.03019/) (2021)
- [Influence-Based Mini-Batching for Graph Neural Networks](https://mlsanity.com/paper/2212.09083/) (2022)
- [The Evolution of Distributed Systems for Graph Neural Networks and their Origin in Graph Processing and Deep Learning: A Survey](https://mlsanity.com/paper/2305.13854/) (2023)
- [Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity](https://mlsanity.com/paper/2406.15575/) (2024)
- [Implicit vs Unfolded Graph Neural Networks](https://mlsanity.com/paper/2111.06592/) (2021)
- [Graph Neural Networks for Tabular Data Learning: A Survey with Taxonomy and Directions](https://mlsanity.com/paper/2401.02143/) (2024)

## Abstract (arXiv)

We present GNNAutoScale (GAS), a framework for scaling arbitrary message-passing GNNs to large graphs. GAS prunes entire sub-trees of the computation graph by utilizing historical embeddings from prior training iterations, leading to constant GPU memory consumption in respect to input node size without dropping any data. While existing solutions weaken the expressive power of message passing due to sub-sampling of edges or non-trainable propagations, our approach is provably able to maintain the expressive power of the original GNN. We achieve this by providing approximation error bounds of historical embeddings and show how to tighten them in practice. Empirically, we show that the practical realization of our framework, PyGAS, an easy-to-use extension for PyTorch Geometric, is both fast and memory-efficient, learns expressive node representations, closely resembles the performance of their non-scaling counterparts, and reaches state-of-the-art performance on large-scale graphs.