# Instant Graph Neural Networks for Dynamic Graphs

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 45 references that are in the map.
- First posted on arXiv 3 Jun 2022.

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

- [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)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks](https://mlsanity.com/paper/1908.01207/) (2019)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [T-GCN: A Temporal Graph ConvolutionalNetwork for Traffic Prediction](https://mlsanity.com/paper/1811.05320/) (2018)
- [Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation](https://mlsanity.com/paper/1806.02473/) (2018)
- [Representation Learning for Dynamic Graphs: A Survey](https://mlsanity.com/paper/1905.11485/) (2019)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Interpreting and Unifying Graph Neural Networks with An Optimization Framework](https://mlsanity.com/paper/2101.11859/) (2021)
- [PyTorch Geometric Temporal: Spatiotemporal Signal Processing with Neural Machine Learning Models](https://mlsanity.com/paper/2104.07788/) (2021)
- [DynGEM: Deep Embedding Method for Dynamic Graphs](https://mlsanity.com/paper/1805.11273/) (2018)
- [dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning](https://mlsanity.com/paper/1809.02657/) (2018)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [Dynamic Graph Convolutional Networks](https://mlsanity.com/paper/1704.06199/) (2017)
- [Aspect-based Sentiment Classification with Aspect-specific Graph Convolutional Networks](https://mlsanity.com/paper/1909.03477/) (2019)
- [Attacking Graph-based Classification via Manipulating the Graph Structure](https://mlsanity.com/paper/1903.00553/) (2019)
- [Approximate Graph Propagation](https://mlsanity.com/paper/2106.03058/) (2021)
- [Approximate Personalized PageRank on Dynamic Graphs](https://mlsanity.com/paper/1603.07796/) (2016)

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

- [OpenGraph: Towards Open Graph Foundation Models](https://mlsanity.com/paper/2403.01121/) (2024)
- [Decoupled Graph Neural Networks for Large Dynamic Graphs](https://mlsanity.com/paper/2305.08273/) (2023)
- [Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier](https://mlsanity.com/paper/2408.09212/) (2024)
- [DistTGL: Distributed Memory-Based Temporal Graph Neural Network Training](https://mlsanity.com/paper/2307.07649/) (2023)
- [Repeat-Aware Neighbor Sampling for Dynamic Graph Learning](https://mlsanity.com/paper/2405.17473/) (2024)
- [Revisiting Dynamic Graph Clustering via Matrix Factorization](https://mlsanity.com/paper/2502.06117/) (2025)
- [H2CGL: Modeling Dynamics of Citation Network for Impact Prediction](https://mlsanity.com/paper/2305.01572/) (2023)
- [Breaking the Discretization Barrier of Continuous Physics Simulation Learning](https://mlsanity.com/paper/2509.17955/) (2025)
- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)
- [Accelerating Dynamic Network Embedding with Billions of Parameter Updates to Milliseconds](https://mlsanity.com/paper/2306.08967/) (2023)
- [Fast and Robust Contextual Node Representation Learning over Dynamic Graphs](https://mlsanity.com/paper/2411.07123/) (2024)
- [Node Role-Guided LLMs for Dynamic Graph Clustering](https://mlsanity.com/paper/2603.13799/) (2026)
- [Interaction Order Prediction for Temporal Graphs](https://mlsanity.com/paper/2302.02128/) (2023)
- [Lighter-X: An Efficient and Plug-and-play Strategy for Graph-based Recommendation through Decoupled Propagation](https://mlsanity.com/paper/2510.10105/) (2025)
- [Coden: Efficient Temporal Graph Neural Networks for Continuous Prediction](https://mlsanity.com/paper/2602.12613/) (2026)
- [Efficient Dynamic Algorithms for Graph Neural Networks with Non-Linear Propagation](https://mlsanity.com/paper/2609.32929/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have been widely used for modeling graph-structured data. With the development of numerous GNN variants, recent years have witnessed groundbreaking results in improving the scalability of GNNs to work on static graphs with millions of nodes. However, how to instantly represent continuous changes of large-scale dynamic graphs with GNNs is still an open problem. Existing dynamic GNNs focus on modeling the periodic evolution of graphs, often on a snapshot basis. Such methods suffer from two drawbacks: first, there is a substantial delay for the changes in the graph to be reflected in the graph representations, resulting in losses on the model's accuracy; second, repeatedly calculating the representation matrix on the entire graph in each snapshot is predominantly time-consuming and severely limits the scalability. In this paper, we propose Instant Graph Neural Network (InstantGNN), an incremental computation approach for the graph representation matrix of dynamic graphs. Set to work with dynamic graphs with the edge-arrival model, our method avoids time-consuming, repetitive computations and allows instant updates on the representation and instant predictions. Graphs with dynamic structures and dynamic attributes are both supported. The upper bounds of time complexity of those updates are also provided. Furthermore, our method provides an adaptive training strategy, which guides the model to retrain at moments when it can make the greatest performance gains. We conduct extensive experiments on several real-world and synthetic datasets. Empirical results demonstrate that our model achieves state-of-the-art accuracy while having orders-of-magnitude higher efficiency than existing methods.