# MSPipe: Efficient Temporal GNN Training via Staleness-Aware Pipeline

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 61 references that are in the map.
- First posted on arXiv 23 Feb 2024.

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

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Spatial Temporal Graph Convolutional Networks for Skeleton-Based Action Recognition](https://mlsanity.com/paper/1801.07455/) (2018)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Inductive Representation Learning on Temporal Graphs](https://mlsanity.com/paper/2002.07962/) (2020)
- [Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks](https://mlsanity.com/paper/1908.01207/) (2019)
- [Do We Really Need Complicated Model Architectures For Temporal Networks?](https://mlsanity.com/paper/2302.11636/) (2023)
- [Foundations and modelling of dynamic networks using Dynamic Graph Neural Networks: A survey](https://mlsanity.com/paper/2005.07496/) (2020)
- [Towards Better Evaluation for Dynamic Link Prediction](https://mlsanity.com/paper/2207.10128/) (2022)
- [APAN: Asynchronous Propagation Attention Network for Real-time Temporal Graph Embedding](https://mlsanity.com/paper/2011.11545/) (2020)
- [Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks](https://mlsanity.com/paper/2006.13866/) (2020)
- [PipeGCN: Efficient Full-Graph Training of Graph Convolutional Networks with Pipelined Feature Communication](https://mlsanity.com/paper/2203.10428/) (2022)
- [Accelerating Training and Inference of Graph Neural Networks with Fast Sampling and Pipelining](https://mlsanity.com/paper/2110.08450/) (2021)
- [Toward Understanding the Impact of Staleness in Distributed Machine Learning](https://mlsanity.com/paper/1810.03264/) (2018)
- [Pipe-SGD: A Decentralized Pipelined SGD Framework for Distributed Deep Net Training](https://mlsanity.com/paper/1811.03619/) (2018)
- [TIGER: Temporal Interaction Graph Embedding with Restarts](https://mlsanity.com/paper/2302.06057/) (2023)
- [Gap Aware Mitigation of Gradient Staleness](https://mlsanity.com/paper/1909.10802/) (2019)
- [GNNFlow: A Distributed Framework for Continuous Temporal GNN Learning on Dynamic Graphs](https://mlsanity.com/paper/2311.17410/) (2023)

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

- [Laminar: A Scalable Asynchronous RL Post-Training Framework](https://mlsanity.com/paper/2510.12633/) (2025)
- [Temporal-Aware Evaluation and Learning for Temporal Graph Neural Networks](https://mlsanity.com/paper/2412.07273/) (2024)
- [A Survey on Temporal Interaction Graph Representation Learning: Progress, Challenges, and Opportunities](https://mlsanity.com/paper/2505.04461/) (2025)
- [On the Topology Awareness and Generalization Performance of Graph Neural Networks](https://mlsanity.com/paper/2403.04482/) (2024)
- [On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks](https://mlsanity.com/paper/2508.14338/) (2025)
- [Graph2Video: Leveraging Video Models to Model Dynamic Graph Evolution](https://mlsanity.com/paper/2603.13360/) (2026)
- [Decoupled and Divergence-Conditioned Prompt for Multi-domain Dynamic Graph Foundation Models](https://mlsanity.com/paper/2605.13540/) (2026)
- [Influence Maximization in Temporal Social Networks with a Cold-Start Problem: A Supervised Approach](https://mlsanity.com/paper/2504.11245/) (2025)
- [MQ-GNN: A Multi-Queue Pipelined Architecture for Scalable and Efficient GNN Training](https://mlsanity.com/paper/2601.04707/) (2026)
- [FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism](https://mlsanity.com/paper/2606.22180/) (2026)
- [Directly Optimizing Mean Demographic Parity for Nonlinear Regression](https://mlsanity.com/paper/2607.05098/) (2026)
- [Structuring Relations Among Learning Paradigms via Protocol--Objective--Resource Reductions](https://mlsanity.com/paper/2609.32766/) (2026)

## Abstract (arXiv)

Memory-based Temporal Graph Neural Networks (MTGNNs) are a class of temporal graph neural networks that utilize a node memory module to capture and retain long-term temporal dependencies, leading to superior performance compared to memory-less counterparts. However, the iterative reading and updating process of the memory module in MTGNNs to obtain up-to-date information needs to follow the temporal dependencies. This introduces significant overhead and limits training throughput. Existing optimizations for static GNNs are not directly applicable to MTGNNs due to differences in training paradigm, model architecture, and the absence of a memory module. Moreover, they do not effectively address the challenges posed by temporal dependencies, making them ineffective for MTGNN training. In this paper, we propose MSPipe, a general and efficient framework for MTGNNs that maximizes training throughput while maintaining model accuracy. Our design addresses the unique challenges associated with fetching and updating node memory states in MTGNNs by integrating staleness into the memory module. However, simply introducing a predefined staleness bound in the memory module to break temporal dependencies may lead to suboptimal performance and lack of generalizability across different models and datasets. To solve this, we introduce an online pipeline scheduling algorithm in MSPipe that strategically breaks temporal dependencies with minimal staleness and delays memory fetching to obtain fresher memory states. Moreover, we design a staleness mitigation mechanism to enhance training convergence and model accuracy. We provide convergence analysis and prove that MSPipe maintains the same convergence rate as vanilla sample-based GNN training. Experimental results show that MSPipe achieves up to 2.45x speed-up without sacrificing accuracy, making it a promising solution for efficient MTGNN training.