STAG: Enabling Low Latency and Low Staleness of GNN-based Services with
  Dynamic Graphs
Jiawen Wang Quan Chen Deze Zeng Zhuo Song Chen Chen Minyi Guo
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.