# Staleness-Alleviated Distributed GNN Training via Online Dynamic-Embedding Prediction

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 43 references that are in the map.
- First posted on arXiv 25 Aug 2023.

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

- [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)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [A Survey on Multi-Task Learning](https://mlsanity.com/paper/1707.08114/) (2017)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [AliGraph: A Comprehensive Graph Neural Network Platform](https://mlsanity.com/paper/1902.08730/) (2019)
- [DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs](https://mlsanity.com/paper/2010.05337/) (2020)
- [Discriminative Embeddings of Latent Variable Models for Structured Data](https://mlsanity.com/paper/1603.05629/) (2016)
- [GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings](https://mlsanity.com/paper/2106.05609/) (2021)
- [DistGNN: Scalable Distributed Training for Large-Scale Graph Neural Networks](https://mlsanity.com/paper/2104.06700/) (2021)
- [Dorylus: Affordable, Scalable, and Accurate GNN Training with Distributed CPU Servers and Serverless Threads](https://mlsanity.com/paper/2105.11118/) (2021)
- [Reducing Communication in Graph Neural Network Training](https://mlsanity.com/paper/2005.03300/) (2020)
- [PipeGCN: Efficient Full-Graph Training of Graph Convolutional Networks with Pipelined Feature Communication](https://mlsanity.com/paper/2203.10428/) (2022)
- [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)
- [GCN-GAN: A Non-linear Temporal Link Prediction Model for Weighted Dynamic Networks](https://mlsanity.com/paper/1901.09165/) (2019)
- [Decoupled Parallel Backpropagation with Convergence Guarantee](https://mlsanity.com/paper/1804.10574/) (2018)
- [Distributed Graph Neural Network Training: A Survey](https://mlsanity.com/paper/2211.00216/) (2022)
- [GraphFM: Improving Large-Scale GNN Training via Feature Momentum](https://mlsanity.com/paper/2206.07161/) (2022)
- [Deep Graph Representation Learning and Optimization for Influence Maximization](https://mlsanity.com/paper/2305.02200/) (2023)
- [Learn Locally, Correct Globally: A Distributed Algorithm for Training Graph Neural Networks](https://mlsanity.com/paper/2111.08202/) (2021)
- [Source Localization of Graph Diffusion via Variational Autoencoders for Graph Inverse Problems](https://mlsanity.com/paper/2206.12327/) (2022)
- [On the Acceleration of Deep Learning Model Parallelism with Staleness](https://mlsanity.com/paper/1909.02625/) (2019)
- [Distributed Training of Graph Convolutional Networks using Subgraph Approximation](https://mlsanity.com/paper/2012.04930/) (2020)

## Built on by (most cited first, 6 of 6)

- [Large Language Models for Spatial Trajectory Patterns Mining](https://mlsanity.com/paper/2310.04942/) (2023)
- [Beyond Text: A Deep Dive into Large Language Models' Ability on Understanding Graph Data](https://mlsanity.com/paper/2310.04944/) (2023)
- [MixGCN: Scalable GCN Training by Mixture of Parallelism and Mixture of Accelerators](https://mlsanity.com/paper/2501.01951/) (2025)
- [VISAGNN: Versatile Staleness-Aware Efficient Training on Large-Scale Graphs](https://mlsanity.com/paper/2511.12434/) (2025)
- [FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism](https://mlsanity.com/paper/2606.22180/) (2026)
- [SNI-GNN: SmartNIC-Assisted Full-Graph GNN Training with In-Network Embedding Prediction](https://mlsanity.com/paper/2608.06441/) (2026)

## Abstract (arXiv)

Despite the recent success of Graph Neural Networks (GNNs), it remains challenging to train GNNs on large-scale graphs due to neighbor explosions. As a remedy, distributed computing becomes a promising solution by leveraging abundant computing resources (e.g., GPU). However, the node dependency of graph data increases the difficulty of achieving high concurrency in distributed GNN training, which suffers from the massive communication overhead. To address it, Historical value approximation is deemed a promising class of distributed training techniques. It utilizes an offline memory to cache historical information (e.g., node embedding) as an affordable approximation of the exact value and achieves high concurrency. However, such benefits come at the cost of involving dated training information, leading to staleness, imprecision, and convergence issues. To overcome these challenges, this paper proposes SAT (Staleness-Alleviated Training), a novel and scalable distributed GNN training framework that reduces the embedding staleness adaptively. The key idea of SAT is to model the GNN's embedding evolution as a temporal graph and build a model upon it to predict future embedding, which effectively alleviates the staleness of the cached historical embedding. We propose an online algorithm to train the embedding predictor and the distributed GNN alternatively and further provide a convergence analysis. Empirically, we demonstrate that SAT can effectively reduce embedding staleness and thus achieve better performance and convergence speed on multiple large-scale graph datasets.