Graph Neural Networks (GNNs) are widely used for representation learning on graphs, but most methods assume static topologies, making them inefficient on evolving networks where edges change over time. Existing dynamic approaches either model graph evolution through temporal GNN architectures without focusing on efficient dynamic maintenance, or are restricted to linear propagation models based on Personalized PageRank. In this work, we study how to efficiently maintain node representations for non-linear GNN propagation under edge insertions and deletions. The propagation has no learned parameters, and only a classifier applied afterward is trained. For a broad class of standard activation functions, we develop a residual-based dynamic algorithm that selectively propagates local errors via push operations, maintaining an approximation to the evolving fixed point without full recomputation. We prove that our method achieves amortized O(1/ε) update time per graph change under a degree-normalized error guarantee. Our approach uses a potential-based analysis in a degree-scaled norm and, in contrast to prior work on the linear case, requires no randomness assumptions on either the update sequence or the input vector. For the linear special case, we additionally provide an exact dynamic algorithm via low-rank matrix inverse updates. Experiments on benchmark datasets show that incorporating non-linearity improves accuracy while preserving efficient update performance, yielding a scalable and theoretically grounded method for maintaining this propagation on dynamic graphs.
Figures & tables
Figure 1: Results on the dynamic arxiv dataset. Accuracy is similar for the linear and hard-tanh models. Since this is the smallest dynamic experiment, recomputation from scratch is still faster than the “single” strategy, which handles the harder online setting of propagating after each edge update. Batched updates are much faster than both.
Figure 2: Results on the dynamic products dataset. Accuracy peaks early and then slowly decreases across later snapshots. Unlike on arxiv , recomputation from scratch becomes much more expensive on this larger graph, while dynamic updates keep the propagation cost substantially lower.
Figure 3: Results on the dynamic SBM-500K dataset. The dynamic methods remain efficient even with both edge insertions and deletions. After the first snapshot, their per-snapshot cost stays low and stable while preserving the accuracy behavior of the linear and hard-tanh models.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Symbol
Meaning
n
Number of nodes.
A
Adjacency matrix of the current graph, with a self-loop at every node.
D
Diagonal degree matrix of the current graph.
d(i)
Degree of node i . Since every node has a self-loop, d(i)≥1 .
β∈[0,1]
Normalization parameter in W=D−βADβ−1 .
W
Normalized weight matrix.
Appendix
Table 2: Parameters used in the paper.
Dataset
Nodes ( n )
Edges
Feature dimension
Classes
Cornell
183
164
1,703
5
Texas
183
167
1,703
5
Wisconsin
251
231
1,703
5
Squirrel
5,201
159,248
2,089
5
Actor
7,600
14,992
932
5
Chameleon
2,277
23,370
2,325
5
Appendix
Table 3: Statistics for datasets used in Section 4.1 .
Hyperparameter
Values
α
{0.01,0.1,0.2,0.3,0.5,0.7}
β
{0.5,1.0}
cfeat
{1,3,5}
Classifier
{linear,MLP}
Learning rate
{10−3,10−2,10−1,0.5}
Weight decay
5×10−4
Appendix
Table 4: Hyperparameter search grid used for each activation–dataset pair.
Method
Cham. (filt.)
Squi. (filt.)
GCN
35.6 ± 0.8
34.8 ± 0.4
GAT
35.3 ± 0.8
34.9 ± 0.4
APPNP
36.1 ± 0.9
34.9 ± 0.4
ACM-GCN
38.9 ± 0.7
35.9 ± 0.5
GREAD
44.0 ± 1.0
41.0 ± 0.5
Linear
41.1 ± 1.1
40.4 ± 0.6
Appendix
Table 6: Test accuracy on the filtered Chameleon and Squirrel datasets of [ 20 ] . The best method is underlined .
Activation
Cham. (filt.)
Squi. (filt.)
Linear
0.01/0.5/1/M/0.1
0.01/0.5/1/M/0.1
Sh Tanh -0.5
0.7/0.5/3/M/0.001
0.5/0.5/1/M/0.01
Sh Tanh -1.2
0.5/0.5/5/M/0.01
0.7/0.5/1/M/0.001
Appendix
Table 7: Configuration of (α,β,cfeat,classifier,lr) selected by validation accuracy for each (activation, dataset) cell of Table 6 . “L” denotes the linear classifier and “M” denotes the MLP.
Figure 4: Total propagation time of varying ϵ values. The propagation time scales inversely with ϵ .
Figure 5: Total propagation time of varying α values. Our theoretical bounds show that the propagation time scales with 1/α2 .
Dynamic graphs are widely used to model time-evolving relational systems in real-world applications. Dynamic graph neural networks provide an effective framework for capturing both structural dependencies and temporal dynamics in such data. However, they typically intertwine temporal graph propagation with every optimization epoch and often maintain large trainable representations for each node-time pair. This design repeatedly recomputes largely unchanged historical structures, leading to substantial training and parameter overhead. To address this critical issue, we propose CacheDyG, a Cache-refine framework for efficient Dynamic Graph learning. Specifically, it decouples temporal propagation from routine parameter updates by constructing a time-ordered temporal dependency cache that stores graph-aware node-time representations in non-trainable buffers. During standard training epochs, CacheDyG reads from the cache and updates only a lightweight cache refiner, an adaptive residual gate, and the link predictor. Selective cache refresh further keeps cached representations aligned with the supervised objective while avoiding epoch-wise sparse propagation. Experiments on five dynamic graph benchmarks show that CacheDyG adopts substantially fewer trainable parameters and lower runtime to obtain more competitive predictive performance than baselines. These results demonstrate that cache-based decoupling provides an effective principle for scalable dynamic graph learning.
PinHeng Zong, Ye Yuan
College of Computer and Information Science, Southwest University, Chongqing, China
Dynamic graph neural networks (DGNNs) that operate on snapshot sequences typically fall into one of two categories. Temporal-first approaches build per-node temporal embeddings and only afterward perform spatial aggregation, whereas Spatial-first approaches invert this order, feeding the output of a graph convolution into a downstream temporal module. In either case, the rigid sequencing forces the second stage to consume an already-compressed summary produced by the first, ruling out joint reasoning over topology and evolution; effectively, the message-passing operator never gets to weight a neighbor's contribution by that neighbor's past trajectory. This paper introduces SiST-GNN (Simultaneous Spatial-Temporal GNN), which fuses the two signals inside a single message-passing operation rather than chaining them. At each snapshot, we maintain a recurrent hidden state per node that summarises its history, pairs it with the node's current feature vector, and treats the pair as two nodes joined by a cross-time edge; running a standard graph convolution on this temporally augmented graph yields the updated representation. We compare against fourteen link-prediction baselines under both the fixed-split and live-update evaluation regimes, and eleven baselines on node classification. Across the public benchmarks, SiST-GNN improves on the strongest prior method in link prediction by 1-18% in the fixed-split setting, and is the leading learned method on five of six datasets in the live-update setting, improving on the strongest prior method by 1-158% there. We additionally derive three dynamic node-classification tasks by discretizing the underlying continuous-time event streams; here SiST-GNN beats the leading discrete-time (DTDG) baseline by 7-23% and matches continuous-time (CTDG) methods that consume the raw events directly.
Shubhajit Roy, Anirban Dasgupta
Department of Computer Science and Engineering Indian Institute of Technology Gandhinagar
Graphs are a highly expressive abstraction for modeling entities and their relations, such as molecular structures, social networks, and traffic networks. Deep Graph Networks (DGNs) have emerged as a family of deep learning models that can effectively process and learn such structured information. However, learning effective information propagation patterns within DGNs remains a critical challenge that heavily influences the model capabilities, both in the static domain and in the temporal domain (where features and/or topology evolve). Given this challenge, this thesis investigates the dynamics of information propagation within DGNs for static and dynamic graphs, focusing on their design as dynamical systems. Throughout this work, we provide theoretical and empirical evidence to demonstrate the effectiveness of our proposed architectures in propagating and preserving long-term dependencies between nodes, and in learning complex spatio-temporal patterns from irregular and sparsely sampled dynamic graphs. In summary, this thesis provides a comprehensive exploration of the intersection between graphs, deep learning, and dynamical systems, offering insights and advancements for the field of graph representation learning and paving the way for more effective and versatile graph-based learning models.