Orca: Scalable Temporal Graph Neural Network Training with Theoretical Guarantees

• Published in: Proceedings of the ACM on Management of Data
• Main Authors: Li, Yiming, Shen, Yanyan, Chen, Lei, Yuan, Mingxuan
• Other Authors: Hong Kong ITC ITF, Hong Kong RGC AOE Project, Hong Kong RGC GRF Project, National Key Research and Development Program of China, Shanghai Municipal Science and Technology Major Project, National Science Foundation of China, Hong Kong RGC CRF Project, Guangdong Basic and Applied Basic Research Foundation, SJTU Global Strategic Partnership Fund, Hong Kong RGC Theme-based project, China NSFC, Microsoft Research Asia Collaborative Research Grant, HKUST-Webank joint research lab grant, HKUST Global Strategic Partnership Fund
• Format: Article in Journal/Newspaper
• Language: English
• Published: Association for Computing Machinery (ACM) 2023
• Subjects: Orca
• Online Access: http://dx.doi.org/10.1145/3588737; https://dl.acm.org/doi/pdf/10.1145/3588737

Representation learning over dynamic graphs is critical for many real-world applications such as social network services and recommender systems. Temporal graph neural networks (T-GNNs) are powerful representation learning methods and have achieved remarkable effectiveness on continuous-time dynamic graphs. However, T-GNNs still suffer from high time complexity, which increases linearly with the number of timestamps and grows exponentially with the model depth, causing them not scalable to large dynamic graphs. To address the limitations, we propose Orca, a novel framework that accelerates T-GNN training by non-trivially caching and reusing intermediate embeddings. We design an optimal cache replacement algorithm, named MRU, under a practical cache limit. MRU not only improves the efficiency of training T-GNNs by maximizing the number of cache hits but also reduces the approximation errors by avoiding keeping and reusing extremely stale embeddings. Meanwhile, we develop profound theoretical analyses of the approximation error introduced by our reuse schemes and offer rigorous convergence guarantees. Extensive experiments have validated that Orca can obtain two orders of magnitude speedup over the state-of-the-art baselines while achieving higher precision on large dynamic graphs.