# STAG: Enabling Low Latency and Low Staleness of GNN-based Services with Dynamic Graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 29 references that are in the map.
- First posted on arXiv 27 Sep 2023.

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

- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks](https://mlsanity.com/paper/1908.01207/) (2019)
- [Representation Learning for Dynamic Graphs: A Survey](https://mlsanity.com/paper/1905.11485/) (2019)
- [Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks](https://mlsanity.com/paper/1909.01315/) (2019)
- [AliGraph: A Comprehensive Graph Neural Network Platform](https://mlsanity.com/paper/1902.08730/) (2019)
- [Heterogeneous Graph Neural Networks for Malicious Account Detection](https://mlsanity.com/paper/2002.12307/) (2020)
- [Sequential Recommendation with Graph Neural Networks](https://mlsanity.com/paper/2106.14226/) (2021)
- [Alleviating the Inconsistency Problem of Applying Graph Neural Network to Fraud Detection](https://mlsanity.com/paper/2005.00625/) (2020)
- [Computing Graph Neural Networks: A Survey from Algorithms to Accelerators](https://mlsanity.com/paper/2010.00130/) (2020)
- [APAN: Asynchronous Propagation Attention Network for Real-time Temporal Graph Embedding](https://mlsanity.com/paper/2011.11545/) (2020)
- [GRIP: A Graph Neural Network Accelerator Architecture](https://mlsanity.com/paper/2007.13828/) (2020)
- [FeatGraph: A Flexible and Efficient Backend for Graph Neural Network Systems](https://mlsanity.com/paper/2008.11359/) (2020)
- [Architectural Implications of Graph Neural Networks](https://mlsanity.com/paper/2009.00804/) (2020)
- [Meta-Learning for Online Update of Recommender Systems](https://mlsanity.com/paper/2203.10354/) (2022)
- [Modelling graph dynamics in fraud detection with "Attention"](https://mlsanity.com/paper/2204.10614/) (2022)

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

- [Towards Training and Inference of Graph Neural Networks in Graph Databases](https://mlsanity.com/paper/2610.19142/) (2026)

## Abstract (arXiv)

Many emerging user-facing services adopt Graph Neural Networks (GNNs) to improve serving accuracy. When the graph used by a GNN model changes, representations (embedding) of nodes in the graph should be updated accordingly. However, the node representation update is too slow, resulting in either long response latency of user queries (the inference is performed after the update completes) or high staleness problem (the inference is performed based on stale data). Our in-depth analysis shows that the slow update is mainly due to neighbor explosion problem in graphs and duplicated computation. Based on such findings, we propose STAG, a GNN serving framework that enables low latency and low staleness of GNN-based services. It comprises a collaborative serving mechanism and an additivity-based incremental propagation strategy. With the collaborative serving mechanism, only part of node representations are updated during the update phase, and the final representations are calculated in the inference phase. It alleviates the neighbor explosion problem. The additivity-based incremental propagation strategy reuses intermediate data during the update phase, eliminating duplicated computation problem. Experimental results show that STAG accelerates the update phase by 1.3x~90.1x, and greatly reduces staleness time with a slight increase in response latency.