Information propagation dynamics in Deep Graph Networks

Alessio Gravina

cs.LGOct 14, 2024

Information propagation dynamics in Deep Graph Networks

Authors: Alessio Gravina

Organizations: University of Pisa Department of Computer Science

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1 : (a) A directed graph. (b) An undirected graph. (c) The neighborhood of node $u$ . At the bottom, the adjacency matrix of the corresponding graph. The neighborhood of the node $u$ is depicted with a dotted line.

Panel of Figure 2 — Figure 2 : Instances of various graph families: (a) path graph, (b) ring graph, (c) crossed-ring graph, (d) grid graph, (e) Erdős–Rényi Graph with probability $p=0.2$ , and (f) Barabasi-Albert Graph with $k=2$ . Each graph consists of 10 nodes.

Figure 3 : A Discrete-Time Dynamic Graph defined over five timestamps and a set of five interacting entities.

Figure 4 : The evolution of a Continuous-Time Dynamic Graph through the stream of events until the timestamp

t_{3}

Figure 5 : Motion of a pendulum.

Figure 6 : Simulation of a simple pendulum, with unitary rod length ( $l=1$ ) and initial angular velocity of 2 rad/s, over a timespan of three seconds ( $t\in[0,3]$ ) with different initial angular displacement, i.e., $0$ , $\pi/6$ , and $\pi/3$ .

Figure 7 : Symplecticity (i.e., area preservation) of a linear mapping.

Panel of Figure 8 — Figure 8 : The stability regions, colored in green, of (a) various explicit Runge-Kutta methods and (b) the backward Euler method.

Figure 9 : The numerical integration for the equation $\exp(x^{2}/2)$ leveraging forward Euler method with step size 0.5 (i.e., F-E, $\epsilon=0.5$ ) and second order Runge-Kutta with step size 0.5 (i.e., RK2, $\epsilon=0.5$ ).

Method	Local error	Global error
Forward Euler	$\mathcal{O}(\epsilon^{2})$	$\mathcal{O}(\epsilon)$
Backward Euler	$\mathcal{O}(\epsilon^{2})$	$\mathcal{O}(\epsilon)$
Runge-Kutta 2 nd order	$\mathcal{O}(\epsilon^{3})$	$\mathcal{O}(\epsilon^{2})$
Runge-Kutta 3 rd order	$\mathcal{O}(\epsilon^{4})$	$\mathcal{O}(\epsilon^{3})$
Runge-Kutta 4 th order	$\mathcal{O}(\epsilon^{5})$	$\mathcal{O}(\epsilon^{4})$
Runge-Kutta 5 th order	$\mathcal{O}(\epsilon^{6})$	$\mathcal{O}(\epsilon^{5})$

Table 1 : The local truncation error and global truncation error of various discretization schemes.

Figure 10 : Motion of a simple harmonic oscillator.

Panel of Figure 11 — Figure 11 : Simulation of a simple harmonic oscillator with unit mass (m=1) and spring constant $k=1$ over a timespan of 50 seconds ( $t\in[0,50]$ ), comparing (a) the position and (b) the energy conservation over time using the Forward Euler and Symplectic Euler methods.

Figure 12 : At the top the continuous neural DE hidden state, in the middle the time-discrete hidden state of neural networks (e.g., ResNet), and at the bottom the real state evolution.

Figure 13 : Visual representation of a DGN wih

??

layers. Given the input graph, the

(\ell+1)

GCL computes the new representation of a node

u

as a transformation of

u

and its neighbors representations at the previous layer,

\ell

Figure 14 : A Deep Graph Network with 2 layers,

\ell

, showcasing recurrent and feed-forward architectures. In the recurrent architecture (at the top) a single shared layer is iteratively unfolded for 2 steps, as indicated by the recurrent connection. At the bottom, the feed-forward architecture leverages two Graph Convolutional layers to process the input graph.

Panel of Figure 15 — Figure 15 : Taxonomy employed to structure our survey of DGN models for static graphs. Graph rewiring is not displayed in the figure since it is a preprocessing technique for enhancing the power of the downstream DGN.

Panel of Figure 16 — Figure 16 : Comparison of original graph topology (left) and preprocessed graph after applying graph rewiring (right), illustrating densification of edges to facilitate information flow within the graph.

Panel of Figure 17 — Figure 17 : Taxonomy employed to structure our survey of DGN models for dynamic graphs.

	Montevideo		Metr-LA
Model	MAE	MSE	MAE	MSE
A3TGCN	0.3962 ±0.0021	1.0416 ±0.0047	0.3401 ±0.0008	0.3893 ±0.0039
DRCNN	0.3499 ±0.0006	1.0686 ±0.0012	0.1218 ±0.0013	0.0960 ±0.0017
GCRN-GRU	0.3481 ±0.0008	1.0534 ±0.0062	0.1219 ±0.0007	0.0973 ±0.0009
GCRN-LSTM	0.3486 ±0.0026	1.0451 ±0.0099	0.1235 ±0.0009	0.0985 ±0.0004
TGCN	0.4024 ±0.0022	1.0678 ±0.0049	0.3422 ±0.0046	0.3891 ±0.0058

Table 2 : Mean test scores of the spatio-temporal models and std averaged over 5 random weight initializations. MAE is the optimized metric. The lower, the better.

Model	Montevideo	Metr-LA	PeMSBay	Traffic
A3TGCN	1.59 ±0.05	95.12 ±0.53	167.05 ±1.96	18.81 ±1.04
DCRNN	3.15 ±0.1	291.44 ±0.76	366.34 ±2.73	112.49 ±11.52
GCRN-GRU	4.89 ±0.1	216.99 ±3.77	289.38 ±3.38	32.44 ±1.03
GCRN-LSTM	6.92 ±0.13	313.27 ±4.09	534.65 ±5.85	46.08 ±1.6
TGCN	1.64 ±0.07	95.08 ±1.43	165.19 ±2.69	17.96 ±0.52

Table 3 : Average time to execute a forward pass on the whole dataset (measured in seconds) and std of the best configuration of each model in each task in the spatio-temporal setting, averaged over 5 repetitions. The evaluation was carried out on an Intel(R) Xeon(R) Gold 6240R CPU @ 2.40GHz.

Node-level tasks
	Twitter tennis		Elliptic
Model	MAE	MSE	AUC	F1	B-Acc
DynGESN	0.1944 ±0.0056	0.3708 ±0.0411	51.12 ±1.30	79.2 ±19.62	50.56 ±1.10
EvolveGCN-H	0.1735 ±0.0007	0.2858 ±0.0074	48.43 ±2.71	92.54 ±8.39	49.52 ±1.55
EvolveGCN-O	0.1749 ±0.0007	0.3020 ±0.0111	45.11 ±1.68	90.80 ±12.67	49.23 ±1.03
GCLSTM	0.1686 ±0.0015	0.2588 ±0.0049	45.77 ±1.60	70.84 ±30.01	48.20 ±1.80

Table 4 : Mean test scores and std of DGNs for general D-TDGs averaged over 5 random weight initializations on node-level tasks. For MAE and MSE scores, lower values corresponds to better performances, while for B-Acc, AUC and F1 the higher values are better. The optimized metric is colored .

Link-level tasks
	AS-773			Bitcoin $\alpha$
Model	AUC	F1	B-Acc	AUC	F1	B-Acc
DynGESN	95.34 ±0.04	79.83 ±5.27	82.80 ±3.40	97.68 ±0.12	69.98 ±1.57	76.79 ±0.93
EvolveGCN-H	59.52 ±17.53	39.85 ±34.24	53.72 ±16.79	51.35 ±2.88	29.55 ±30.58	50.69 ±1.69
EvolveGCN-O	58.90 ±17.80	29.99 ±37.10	56.99 ±13.97	51.42 ±2.84	31.74 ±29.98	51.42 ±2.84
GCLSTM	96.35 ±0.01	91.22 ±0.13	91.11 ±0.06	97.75 ±0.17	91.22 ±1.38	91.72 ±1.11

Table 5 : Mean test scores and std of DGNs for general D-TDGs averaged over 5 random weight initializations on link-level tasks. The higher, the better. The optimized metric is colored .

Model	Twitter tennis	Elliptic	AS-773	Bitcoin $\alpha$
DynGESN	0.04 ${}_{\pm 2\cdot 10^{-3}}$	0.03 ±0.01	0.53 ±0.13	0.15 ±0.01
EvolveGCN-H	0.38 ±0.01	21.14 ±0.07	3.73 ±0.18	2.33 ±0.03
EvolveGCN-O	0.11 ±0.02	19.5 ±0.25	2.35 ±0.29	1.07 ±0.03
GCLSTM	1.08 ±0.42	1.2 ±0.13	31.14 ±0.83	28.37 ±1.59
LRGCN	1.63 ±0.08	3.28 ±0.28	21.66 ±2.65	24.77 ±3.21

Table 6 : Average time to execute a forward pass on the whole dataset (measured in seconds) and std of the best configuration of each model in each task in the generic D-TDG, averaged over 5 repetitions. The evaluation was carried out on an Intel(R) Xeon(R) Gold 6240R CPU @ 2.40GHz.

	Wikipedia
Model	AUC	F1	Acc
EdgeBank	91.82	91.09	91.82
DyRep	89.72 ±0.59	79.02 ±0.91	80.46 ±0.63
JODIE	94.94 ±0.48	87.52 ±0.39	87.85 ±0.44
TGAT	95.54 ±0.22	88.11 ±0.45	88.58 ±0.31
TGN	97.07 ±0.15	90.49 ±0.24	90.66 ±0.22

Table 7 : Mean test scores and std of DGNs for C-TDGs averaged over 5 random weight initializations. The higher, the better. The models are trained to maximize the AUC score.

Model	Wikipedia	Reddit	LastFM
DyRep	13.95 ±1.05	99.11 ±9.04	143.15 ±12.72
JODIE	12.66 ±1.98	83.27 ±6.47	117.17 ±6.86
TGAT	36.84 ±2.09	303.70 ±7.80	167.65 ±13.33
TGN	28.35 ±2.14	114.73 ±14.77	178.15 ±7.87

Table 8 : Average time to execute a forward pass on the whole dataset (measured in seconds) and std of the best configuration of each model in each task in the C-TDG setting, averaged over 5 repetitions. The evaluation was carried out on an Intel(R) Xeon(R) Gold 6278C CPU @ 2.60GHz.

Figure 18 : A high level overview of our proposed framework, summarizing the involved concepts of ODE over a graph, its discretization as layers of a DGN, and the resulting node update of Antisymmetric DGN. At the top, it is illustrated the continuous processing of nodes’ states in the time span between

0

and

T>0

, as a Cauchy problem on graphs. The node-wise ODE

f_{\mathcal{G}}

determines the evolution of the states

{\bf x}_{u}(t)

, while the initial conditions

{\bf x}_{u}(0)

play the role of input information. In the middle, the discretized solution of the graph ODE is interpreted as a succession of DGN layers in a neural network architecture. The node state

{\bf x}_{u}^{\ell}

computed at layer

\ell

is updated iteratively by leveraging its neighborhood and self representations at the previous layer

\ell-1

. The bottom part sketches the computation performed by a layer in an Antisymmetric DGN (in Equation 79 ), resulting from the forward Euler discretization of a stable and non-dissipative ODE on graphs. The more the layers, the more long-range dependencies are included in the final nodes’ representations.

Model	Diameter	SSSP	Eccentricity
MPNNs
GCN	0.7424 ±0.0466	0.9499 ${}_{\pm 9.18\cdot 10^{-5}}$	0.8468 ±0.0028
GAT	0.8221 ±0.0752	0.6951 ±0.1499	0.7909 ±0.0222
GraphSAGE	0.8645 ±0.0401	0.2863 ±0.1843	0.7863 ±0.0207
GIN	0.6131 ±0.0990	-0.5408 ±0.4193	0.9504 ±0.0007
GCNII	0.5287 ±0.0570	-1.1329 ±0.0135	0.7640 ±0.0355

Table 9 : Mean test set

log_{10}(\mathrm{MSE})

and std averaged over 4 random weight initializations for each configuration. The subscript ws stands for weight sharing, while ldw for layer-dependent weights. The lower the better. First , second , and third best results for each task are color-coded.

Model	Diameter	SSSP	Eccentricity
MPNNs
GCN	32.45 ±2.54	17.44 ±3.85	11.78 ±2.43
GAT	20.20 ±5.18	26.41 ±8.34	17.28 ±1.92
GraphSAGE	13.12 ±2.99	13.12 ±2.99	8.20 ±0.75
GIN	6.63 ±0.28	21.16 ±2.33	14.22 ±3.17
GCNII	13.13 ±6.85	14.96 ±7.17	15.70 ±3.92

Table 10 : Average time per epoch (measured in seconds) and std, averaged over 4 random weight initializations. Each time is obtained by employing 20 layers and an embedding dimension equal to 30. The subscript ws stands for weight sharing, ldw for layer-dependent weights. The evaluation was carried out on an AMD EPYC 7543 CPU @ 2.80GHz. First , second , and third best results.

Panel of Figure 19 — Figure 19 : The test accuracy with respect to the number of layers on all the graph benchmark datasets. From the top left to the bottom, we show: PubMed, Coauthor CS, Coauthor Physics, Amazon Computers, and Amazon Photo. The accuracy is averaged over 5 random train/validation/test splits and 5 random weight initialization of the best configuration per split.

Panel of Figure 20 — Figure 20 : The test accuracy of A-DGN with respect to the number of layers on all the graph heterophilic datasets. From the top left to the bottom, we show: Chameleon, Squirrel, Actor, Cornell, Texas, and Wisconsin. The accuracy is averaged over 10 train/validation/test splits.

Panel of Figure 21 — Figure 21 : An illustration of the ability of Global and Local Non-Dissipativity (e) to propagate information to distant nodes, from the source (a) to the target (b). Other dynamics, such as diffusion (c) cannot achieve the desired behavior, while Local Non-Dissipativity (d) has only limited effect. A-DGN implements (d) and SWAN implements (e). The color yellow represents the signal at its maximum strength, while the color blue indicates the absence of signal. Intermediate signal strengths are depicted through a gradient of colors between yellow and blue.

Panel of Figure 22 — Figure 22 : The difference among non-dissipative and dissipative behaviors. With global (i.e., graph-wise) and local (i.e., node-wise) non-dissipative behavior (a), information is propagated between any pair of nodes with a viable path in the graph. Therefore, such a behavior increases the long-range effectiveness of the model, with propagation reaching distant nodes. A model exhibiting local non-dissipative behavior (b) enhances only the long-term memory capacity of individual nodes. A model demonstrating dissipative behavior (c) exhibits a convergence of node features toward non-informative values.

Name	$\Phi$	$\Psi$
Weight Antisymmetry Only
SWAN β=0	$(\hat{{\bf A}}+\hat{{\bf A}}^{\top})\mathbf{X}(\mathbf{V}-\mathbf{V}^{\top})$	–
Bounded Non-Dissipative
SWAN- ne	$\hat{{\bf A}}{\bf X}{\bf V}$	$(\tilde{{\bf A}}-\tilde{{\bf A}}^{\top})\mathbf{X}(\mathbf{Z}+\mathbf{Z}^{\top})$
SWAN- learn-ne	$\hat{{\bf A}}_{\bf F}\mathbf{X}\mathbf{V}$	$(\mathbf{\tilde{A}}_{\bf F}-\mathbf{\tilde{A}}_{\bf F}^{\top})\mathbf{X}(\mathbf{Z}+\mathbf{Z}^{\top})$
Global and Local Non-Dissipative

Table 13 : The grid of the evaluated SWAN versions. We consider

\hat{{\bf A}}

to be either the original adjacency matrix

{\bf A}

or the symmetric normalized adjacency matrix,

{\bf D}^{-1/2}{\bf A}{\bf D}^{-1/2}

, while

\tilde{{\bf A}}

is the random walk normalized adjacency matrix,

{\bf D}^{-1}{\bf A}

. The learned versions (- learn ) employ learnable

\hat{{\bf A}}

and

\tilde{{\bf A}}

as described in Section 12.2.2 , here referred as

\hat{{\bf A}}_{\bf F}

and

\tilde{{\bf A}}_{\bf F}

Panel of Figure 23 — Figure 23 : Information transfer on (a) Line, (b) Ring, and (c) Crossed-Ring graphs. While baseline approaches struggle to transfer the information accurately, non-dissipative methods like A-DGN and our SWAN achieve low errors.

Model	Diameter	SSSP	Eccentricity
MPNNs
GCN	0.7424 ±0.0466	0.9499 ${}_{\pm 9.18\cdot 10^{-5}}$	0.8468 ±0.0028
GAT	0.8221 ±0.0752	0.6951 ±0.1499	0.7909 ±0.0222
GraphSAGE	0.8645 ±0.0401	0.2863 ±0.1843	0.7863 ±0.0207
GIN	0.6131 ±0.0990	-0.5408 ±0.4193	0.9504 ±0.0007
GCNII	0.5287 ±0.0570	-1.1329 ±0.0135	0.7640 ±0.0355

Table 14 : Mean test set

log_{10}(\mathrm{MSE})

and std averaged over 4 random weight initializations on the Graph Property Prediction tasks. SWAN and DE-DGN baselins employ weight sharing . The lower, the better. First , third and fourth best results for each task are color-coded.

Model	Diameter	SSSP	Eccentricity
A-DGN	-0.5455 ±0.0328	-3.4020 ±0.1372	0.3046 ±0.1181
SWAN	-0.6381 ±0.0358	-3.9342 ±0.1993	-0.2706 ±0.0948
SWAN- learn	-0.5905 ±0.0372	-3.8258 ±0.0950	-0.2245 ±0.0840

Table 15 : Mean test set

log_{10}(\mathrm{MSE})

and std averaged over 4 random weight initializations on the Graph Property Prediction tasks. SWAN and A-DGN emply layer-dependent weights . The lower, the better. First and second best results for each task are color-coded.

Model	Peptides-	Peptides-	Pascal
	func	struct	voc-sp
	AP $\uparrow$	MAE $\downarrow$	F1 $\uparrow$
MPNNs
GCN	0.5930 ±0.0023	0.3496 ±0.0013	0.1268 ±0.0060
GINE	0.5498 ±0.0079	0.3547 ±0.0045	0.1265 ±0.0076
GCNII	0.5543 ±0.0078	0.3471 ±0.0010	0.1698 ±0.0080

Table 16 : Performance of various classical, multi-hop and static rewiring MPNN, graph Transformer benchmarks, DE-GNNs, and our SWAN across two LRGB tasks. Results are averaged over 3 weight initializations. The first , second , and third best results for each task are color-coded. Beseline results are reported from Gutteridge et al. (2023) .

Model	Diam.	SSSP	Ecc.	Peptides-	Peptides-
	Diam.	SSSP	Ecc.	func	struct
	$log_{10}$ (MSE) $\downarrow$	$log_{10}$ (MSE) $\downarrow$	$log_{10}$ (MSE) $\downarrow$	AP $\uparrow$	MAE $\downarrow$
Weight Antisymmetry Only
SWAN β=0	-0.3882 ±0.0610	-3.2061 ±0.0416	0.5573 ±0.0247	0.6195 ±0.0067	0.2703 ±0.0023
Bounded Non-Dissipative
SWAN- ne	-0.5497 ±0.0766	-3.1913 ±0.0762	0.3792 ±0.1514	0.6119 ±0.0037	0.2672 ±0.0012

Table 17 : Performance of different versions of SWAN on Graph Property Prediction and LRGB tasks. Results are averaged over 4 random weight initializations on the Graph Property Prediction, while over 3 on the LRGB. The first , second , and third best results for each task are color-coded.

Method	Training	Inference	MAE $\downarrow$
GCN	2.90	0.32	0.3496 ±0.0013
GraphGPS+LapPE	23.04	2.39	0.2500 ±0.0005
GraphCON	3.03	0.27	0.2778 ±0.0018
A-DGN	2.83	0.25	0.2874 ±0.0021
SWAN	2.88	0.24	0.2571 ±0.0018
SWAN- learn	2.93	0.26	0.2485 ±0.0009

Table 18 : Measured training and inference runtimes in seconds, and the obtain MAE of SWAN and other baselines on the Peptides-func dataset.

Figure 24 : A high-level overview of the proposed (port-)Hamiltonian Deep Graph Network. It summarizes how the initial node state

{\bf x}_{u}(0)

is propagated by means of energy preservation up until the terminal time

T

(i.e., layer

L

{\bf x}_{u}(T)

. While the global system’s state

\mathbf{y}

evolves preserving energy, external forces (i.e., dampening

D(\mathbf{y})

and external control

F(\mathbf{y},t)

) can intervene to alter its conservative trajectory. The gray trajectories between the initial and final states represent the continuous evolution of the system. The discrete message passing step from layer

\ell

\ell+1

, which is shown in middle of the figure, is given by the coupling of coordinates

{\bf q}

and momenta

{\bf p}

in terms of neighborhood aggregation

\Phi_{\mathcal{G}}

and influence to adjacent neighbors

\Phi^{*}_{\mathcal{G}}

. Self-influence on both

{\bf q}

and

{\bf p}

from the previous step

\ell

are omitted for simplicity.

Panel of Figure 25 — Figure 25 : (a) Time evolution of the energy difference to the initial state $\mathbf{y}(0)=\mathbf{y}^{0}$ obtained from one forward pass of H-DGN with fixed random weights on the Carbon-60 graph with three different numbers of layers given by $T/\epsilon$ . The sensitivity $\|{\partial\mathbf{x}_{u}^{L}}/{\partial\mathbf{x}_{u}^{\ell}}\|$ of 15 different node states to their final embedding obtained by backpropagation on the Carbon-60 graph after (b) $T=10$ and $\epsilon=0.1$ (i.e., 100 layers) and (c) $T=300$ and $\epsilon=0.3$ (i.e., 1000 layers). The log scale’s horizontal line at $0$ indicates the theoretical lower bound.

Panel of Figure 26 — Figure 26 : Information transfer performance on (a) Line, (b) Ring, and (c) Crossed-Ring graphs. Overall, baseline approaches are not able to transfer the information accurately as distance increase, while non-dissipative methods like A-DGN, SWAN, and our H-DGN achieve low errors.

Model	Diameter	SSSP	Eccentricity
MPNNs
GCN	0.7424 ±0.0466	0.9499 ${}_{\pm 9.2\cdot 10^{-5}}$	0.8468 ±0.0028
GAT	0.8221 ±0.0752	0.6951 ±0.1499	0.7909 ±0.0222
GraphSAGE	0.8645 ±0.0401	0.2863 ±0.1843	0.7863 ±0.0207
GIN	0.6131 ±0.0990	-0.5408 ±0.4193	0.9504 ±0.0007
GCNII	0.5287 ±0.0570	-1.1329 ±0.0135	0.7640 ±0.0355

Table 19 : Mean test

log_{10}(\text{MSE})

and std average over 4 training seeds on the Graph Property Prediction. Our methods and DE-DGN baselines are implemented with weight sharing . The first , second , and third best scores are colored.

Model	Diameter	SSSP	Eccentricity
MPNNs
GCN	32.45 ±2.54	17.44 ±3.85	11.78 ±2.43
GAT	20.20 ±5.18	26.41 ±8.34	17.28 ±1.92
GraphSAGE	13.12 ±2.99	13.12 ±2.99	8.20 ±0.75
GIN	6.63 ±0.28	21.16 ±2.33	14.22 ±3.17
GCNII	13.13 ±6.85	14.96 ±7.17	15.70 ±3.92

Table 20 : Average time per epoch (measured in seconds) and std, averaged over 4 random weight initializations. Each time is obtained by employing 20 layers and an embedding dimension equal to 30. Our methods and DE-DGN baselines are implemented with weight sharing . The evaluation was carried out on an AMD EPYC 7543 CPU @ 2.80GHz. First , second , and third best results.

Model	Peptides-func	Peptides-struct
Model	AP $\uparrow$	MAE $\downarrow$
MPNNs
GCN	0.5930 ±0.0023	0.3496 ±0.0013
GINE	0.5498 ±0.0079	0.3547 ±0.0045
GCNII	0.5543 ±0.0078	0.3471 ±0.0010
GatedGCN	0.5864 ±0.0077	0.3420 ±0.0013

Table 21 : Results for Peptides-func and Peptides-struct averaged over 3 training seeds. Baseline results are taken from Dwivedi et al. (2022) and Gutteridge et al. (2023) . Re-evaluated methods employ the 3-layer MLP readout proposed in Tönshoff et al. (2023) . Our methods and DE-DGN baselines are implemented with weight sharing . Note that all MPNN-based methods include structural and positional encoding. The first , second , and third best scores are colored.

Figure 27 : The continuous processing of node $u$ ’s state in a discrete-time dynamic graph with irregularly-sampled snapshots over a set of 4 nodes and fixed edge set. At the top, the node-wise ODE function $f_{\theta}$ defines the evolution of the states ${\bf x}_{u}(t)$ . At the bottom, the discretized solution of the node-wise ODE, which corresponds to our framework TG-ODE. The node embedding ${\bf x}_{u}^{\ell}$ is computed iteratively over a discrete set of points by leveraging the temporal neighborhood and self-representation at the previous step.

Figure 28 : Average time per epoch (measured in seconds) and std computed using an Intel Xeon Gold 6240R CPU @ 2.40GHz. Each time is obtained using 5 neighbor hops (when possible) and embedding dimension equal to 64. The graph size is computed as

size=\#steps*\#edges

Figure 29 : Test

\mathrm{MAE}

scores and std of TG-ODE on PeMS04, averaged over 5 runs, for different sparsity levels.

Figure 30 : A high-level overview of the proposed framework illustrated for the

i

-th Cauchy sub-problem. On the left, we depict the propagation of the information of event

o_{i}

through the graph.

o_{i}

is an interaction event (

\mathcal{E}_{\oplus}

) between nodes

u

and

v

. The faded portion of the graph corresponds to historical information, while the rest is the incoming event. On the right, we illustrate the evolution of node states given the propagation of the incoming event. Specifically, the top right shows the evolution as an ODE,

f_{\theta}

, that computes the node representation for a node

k

\mathbf{h}_{k}(t)

. Such computation is subject to an initial condition

\mathbf{h}_{k}(t_{s})=\eta(\mathbf{h}_{k}^{i-1}(t_{e}),\mathbf{x}_{k}(i))

that includes the node representations computed in the previous sub-problem

\mathbf{h}_{k}^{i-1}(t_{e})

and the current node input state. In the bottom right, the discretized solution of the ODE is computed as iterative steps of the method over a discrete set of points in the time interval

[t_{s},t_{e}]

	Temporal Pascal VOC (sc=10)			Temporal Pascal VOC (sc=30)
no. GCLs	1	3	5	1	3	5
DGNs for C-TDGs
DyGFormer	8.45 ±0.13	$-$	$-$	8.07 ±0.27	$-$	$-$
DyRep	5.29 ±0.47	$-$	$-$	5.23 ±0.11	$-$	$-$
GraphMixer	6.60 ±0.11	$-$	$-$	5.88 ±0.08	$-$	$-$
JODIE	6.33 ±0.41	$-$	$-$	5.76 ±0.35	$-$	$-$

Table 26 : Results of the classification on the Temporal PascalVOC task, for increasing number of GCLs. The performance metric is the mean test set F1-score, averaged over 5 different random weights initializations for each model configuration.

	Wikipedia	Reddit	LastFM	MOOC
Baseline
EdgeBank ${}_{1\%\,tr\,set}$	71.03	71.92	77.59	61.29
EdgeBank ${}_{5\%\,tr\,set}$	81.65	85.07	86.75	63.93
EdgeBank ${}_{10\%\,tr\,set}$	85.26	89.07	89.87	65.18
EdgeBank ${}_{25\%\,tr\,set}$	88.31	92.92	92.74	67.49
EdgeBank ${}_{50\%\,tr\,set}$	90.29	94.82	94.06	69.63

Table 27 : Mean test set AUC and std in percent averaged over 5 random weight initializations. Each model have a maximum budget of learnable weights equal to

\sim

140k. The higher, the better. First , second , and third best results for each task are color-coded.

Sampler size	2	8	16	32	64	128
CTAN	82.64 ±0.93	86.21 ±0.58	86.16 ±0.55	86.27 ±0.55	86.32 ±0.81	87.82 ±0.42

Table 28 : Mean test set AUC and std on LastFM (in percent) for increasing size of sampled neighbors, averaged over three different weights initializations. The model has a budget of learnable weights equal to

\sim

350k. When nodes have large degrees as in LastFM, accessing larger neighborhoods with the neighbor sampler is fundamental to access and retain important information.

Model	N. params	tgbl-	tgbl-	tgbl-	tgbl-	Avg.
Model	N. params	wiki-v2	review-v2	coin-v2	comment	rank
Baseline
EdgeBank ∞	$-$	52.50	2.29	35.90	10.87	11
EdgeBank ${}_{\text{tw-ts}}$	$-$	63.25	2.94	57.36	12.44	8.25
EdgeBank ${}_{\text{re}}$	$-$	65.88	2.84	59.15	$-$	8.25
EdgeBank ${}_{\text{th}}$	$-$	52.81	1.97	43.36	$-$	11.33

Table 29 : Results of the Dynamic Link Property Prediction task on the TGB benchmark datasets ( Huang et al., 2023 ) . The table reports the average MRR on the test split of the datasets over the considered weight initializations. For CTAN, the average is taken over a maximum of five runs with different random seeds for different weight initializations. All baselines’ results are taken from Yu (2023) . The number of parameters is computed from the TGB Baselines repository ( Huang et al., 2023 ) by loading the best performing model across the model selection search. First , second , and third best results for each task are color-coded.

Figure 31 : Mean accuracy on the T-PathGraph task on the experiment of Section 24.1.1 , with distinction between the performance at different number of GCLs (whenever possible). With 3 and 5 GCLs we report in grey the results of DyGFormer, DyRep, GraphMixer, and JODIE, which are designed for 1-hop aggregation only. The plots show that not only CTAN can better retain information at low number of GCLs, but also that increasing the number of GCL enables solving the T-PathGraph task on longer graphs, where the task is harder because information needs to be propagated further away. The number of GCL allows CTAN to scale up the range of information propagation.

	Model	Wikipedia	Reddit	LastFM	MOOC
1 layer	DGNs for C-TDGs
	DyRep	27.07 ±0.32	161.43 ±0.96	216.88 ±2.83	53.32 ±0.56
	JODIE	20.62 ±0.24	131.71 ±0.85	176.61 ±3.02	43.92 ±0.68
	TGAT	11.56 ±0.14	67.83 ±0.64	139.79 ±20.78	33.92 ±0.50
	TGN	30.92 ±0.25	196.87 ±1.35	289.22 ±30.38	53.46 ±0.62
	Our

Table 30 : Mean time (in seconds) and std averaged over 10 epochs. Each model is run with an embedding dimension equal to 100 on an Intel(R) Xeon(R) Gold 6278C CPU @ 2.60GHz.

Figure 32 : Average time per epoch (measured in seconds) and std with respect to the embedding size computed on the Wikipedia dataset, averaged over 10 epochs. The experiments were carried out on an Intel(R) Xeon(R) Gold 6278C CPU @ 2.60GHz. On the left (a), each model has 1 DGN layer (when possible), while on the right (b) the models have 5 GCLs.

Appendix figures & tables33 assets

Supplementary material from the paper’s appendix.

Appendix

Name	#Nodes	#Edges	Seq. len.	Snapshot sizes (nodes/edges)	Granularity	Type	Link
Autonomous systems	7,716	13,895	733	103-6,474 / 243-13,233	daily	$\mathcal{D}$	http://snap.stanford.edu/data/as-733.html
Bitcoin- $\alpha$	3,783	24,186	24,186	$-$	seconds	$\mathcal{C}$	http://snap.stanford.edu/data/ soc-sign-bitcoin-alpha.html
Bitcoin-OTC	5,881	35,592	35,592	$-$	seconds	$\mathcal{C}$	http://snap.stanford.edu/data/ soc-sign-bitcoin-otc.html
CONTACT	274	2,712	28,244	$-$	$-$	$\mathcal{C}$	https://networkrepository.com/ia-contact.php
ENRON	151	2,227	50,572	$-$	unix timestamp	$\mathcal{C}$	https://networkrepository.com/ ia-enron-employees.php
Elliptic	203,769	234,355	49	1,552-12,856 / 1,168-9,164	49 steps	$\mathcal{D}$	https://www.kaggle.com/ellipticco/elliptic-data-set

Appendix

Table 31 : A selected list of datasets used in dynamic graphs representation learning field. The “

\mathcal{C}

” in the type column means C-TDG, “

\mathcal{D}

” corresponds to D-TDG, and “

\mathcal{ST}

” to spatio-temporal graph.

			Node		Edge
Name	Cit.	Type	Add	Del	Add	Del
A3TGCN	Bai et al. (2021)	$\mathcal{ST}$	✗	✗	✗	✗
ASTGCN	Guo et al. (2019)	$\mathcal{ST}$	✗	✗	✗	✗
CAW	Wang et al. (2021b)	$\mathcal{C}$	✓	✓	✓	✓
CTDNG	Nguyen et al. (2018)	$\mathcal{C}$	✓	✓	✓	✓
DCRNN	Li et al. (2018)	$\mathcal{ST}$	✗	✗	✗	✗

Appendix

Table 32 : An overview of the examined models and the specific changes in the graph structure that each model was designed to address, i.e., node additions/deletions and edge addition/deletions. The “

\mathcal{C}

” in the type column means C-TDG, “

\mathcal{D}

” corresponds to D-TDG, and “

\mathcal{ST}

” to spatio-temporal graph.

	Survey				Year of the last surveyed method	Datasets		Dyn. graph benchmark
Study	Static	$\mathcal{ST}$	$\mathcal{D}$	$\mathcal{C}$		static	dynamic	$\mathcal{ST}$	$\mathcal{D}$	$\mathcal{C}$
Hamilton et al. (2017b)	✓	✗	✗	✗	2017	✗	✗	✗	✗	✗
Bacciu et al. (2020a)	✓	✗	✗	✗	2020	✗	✗	✗	✗	✗
Wu et al. (2020)	✓	✓	✗	✗	2019	✓	✗	✗	✗	✗
Kazemi et al. (2020)	✓	✓	✓	✓	2020	✗	✓	✗	✗	✗
Jiang and Luo (2022)	✓	✓	✗	✗	2022	✗	✓ ( $\mathcal{ST}$ only)	✗	✗	✗

Appendix

Table 33 : Comparative analysis with previous benchmarking studies and surveys, assessing the provision of datasets and benchmarks and delineating the types of analyzed graphs. The “

\mathcal{C}

” in the columns means C-TDG, “

\mathcal{D}

” corresponds to D-TDG, and “

\mathcal{ST}

” to spatio-temporal graph.

Hyperparameter	Values
learning rate	$10^{-2}$ , $10^{-3}$ , $10^{-4}$
weight decay	$10^{-3}$ , $10^{-4}$
embedding dim	1, 2, 4, 8
$\sigma$	ReLU
Chebishev poly. filter size	1, 2, 3
normalization scheme for $\mathbf{L}$	$\mathbf{L}=\mathbf{D}-\mathbf{A}$ , $\mathbf{L}^{sym}=\mathbf{I}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$ , $\mathbf{L}^{rw}=\mathbf{I}-\mathbf{D}^{-1}\mathbf{A}$

Appendix

Table 34 : The grid of hyperparameters employed during model selection for the spatio-temporal tasks.

Hyperparameter	Values
learning rate	$10^{-2}$ , $10^{-3}$ , $10^{-4}$
weight decay	$10^{-3}$ , $10^{-4}$
embedding dim	8, 16, 32
$\sigma$	ReLU
Chebishev poly. filter size	1, 2, 3
normalization scheme for $\mathbf{L}$	$\mathbf{L}=\mathbf{D}-\mathbf{A}$ , $\mathbf{L}^{sym}=\mathbf{I}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$ , $\mathbf{L}^{rw}=\mathbf{I}-\mathbf{D}^{-1}\mathbf{A}$

Appendix

Table 35 : The grid of hyperparameters employed during model selection for the D-TDG tasks. The “

*

” value refer only to LRGCN model, while “

\diamond

” to DynGESN.

Hyperparameter	Values
learning rate	$10^{-3}$ , $10^{-4}$
weight decay	$10^{-4}$ , $10^{-5}$
n. DGN layers	1, 3
embedding dim	32, 64, 96
DGN dim	emb dim, emb dim / 2
$\sigma$	tanh

Appendix

Table 36 : The grid of hyperparameters employed during model selection for the C-TDG tasks.

		emb dim	lr	weight decay	filter size	norm.
Montevideo	A3TGCN	8	$10^{-2}$	$10^{-3}$	-	-
	DCRNN	8	$10^{-2}$	$10^{-3}$	1	-
	GCRN-GRU	8	$10^{-2}$	$10^{-3}$	3	${\bf L}$
	GCRN-LSTM	8	$10^{-2}$	$10^{-4}$	3	${\bf L}$
	TGCN	8	$10^{-2}$	$10^{-3}$	-	-
Metr-LA	A3TGCN	8	$10^{-3}$	$10^{-3}$	-	-

Appendix

Table 37 : The table of selected hyper-parameters for the spatio-temporal tasks.

		emb dim	lr	weight decay	n. bases	K	norm.	random weight init. value	$\gamma$
Twitter tennis	DynGESN	32	$10^{-2}$	$10^{-3}$	-	-	-	0.9	0.5
	EvolveGCN-H	8	$10^{-2}$	$10^{-3}$	-	-	${\bf L}$	-	-
	EvolveGCN-O	32	$10^{-3}$	$10^{-3}$	-	-	${\bf L}$	-	-
	GCLSTM	32	$10^{-2}$	$10^{-4}$	-	2	${\bf L}$	-	-
	LRGCN	32	$10^{-2}$	$10^{-4}$	None	-	-	-	-
Elliptic	DynGESN	8	$10^{-2}$	$10^{-4}$	-	-	-	0.1	0.9

Appendix

Table 38 : The table of selected hyper-parameters for the D-TDG tasks.

		emb dim	lr	weight decay	n. DGN layers	DGN dim
Wikipedia	DyRep	96	$10^{-3}$	$10^{-4}$	-	-
	JODIE	96	$10^{-4}$	$10^{-5}$	-	-
	TGAT	96	$10^{-3}$	$10^{-4}$	3	96
	TGN	96	$10^{-3}$	$10^{-5}$	3	48
Reddit	DyRep	96	$10^{-4}$	$10^{-4}$	-	-
	JODIE	96	$10^{-4}$	$10^{-5}$	-	-

Appendix

Table 39 : The table of selected hyper-parameters for the C-TDG tasks.

	Montevideo		MetrLA
	min	max	min	max
A3TGCN	ed: 0.009	lr: 0.015	wd: 0.099	ed: 0.127
DCRNN	ed: 0.016	lr: 0.025	wd: 0.019	ed: 0.034
GCRN-GRU	lr: 0.038	K: 0.043	wd: 0.057	K: 0.071
GCRN-LSTM	wd: 0.031	ed: 0.039	wd: 0.056	ed: 0.082
TGCN	ed: 0.013	lr: 0.018	wd: 0.099	ed: 0.120

Appendix

Table 40 : The min imum and max imum standard deviation of validation scores obtained by fixing individual hyperparameter values in spatio-temporal models. The hyperparameter names corresponding to these values are also provided for reference. “wd” means weight decay, “ed” embedding dimension, “lr” learning rate, and “fs” filter size.

	Twitter tennis		Elliptic
	min	max	min	max
DynGESN	lr: 0.004	$\sigma$ : 0.006	lr: 0.004	ed: 0.005
EvolveGCN-H	wd: 0.011	lr: 0.012	lr: 0.003	ed: 0.005
EvolveGCN-O	ed: 0.010	lr: 0.012	lr: 0.005	ed: 0.007
GCLSTM	lr: 0.012	ed: 0.016	wd: 0.004	ed: 0.005
LRGCN	nb: 0.008	ed: 0.01	wd: 0.005	nb: 0.005

Appendix

Table 41 : The min imum and max imum standard deviation of validation scores obtained by fixing individual hyperparameter values in D-TDGs models. The hyperparameter names corresponding to these values are also provided for reference. “wd” means weight decay, “ed” embedding dimension, “lr” learning rate, “ns” normalization scheme, and “nb” number of bases.

	Wikipedia		Reddit		LastFM
	min	max	min	max	min	max
DyRep	ed: 0.004	wd: 0.009	lr: 0.002	wd: 0.003	lr: 0.004	ed: 0.007
JODIE	lr: 0.023	ed: 0.027	wd: 0.007	ed: 0.007	wd: 0.004	ed: 0.006
TGAT	gl: 0.004	re: 0.023	ge: 0.002	re: 0.011	gl: 0.007	wd: 0.030
TGN	ed: 0.004	wd: 0.005	wd: 0.004	ge: 0.006	gl: 0.012	lr: 0.033

Appendix

Table 42 : The min imum and max imum standard deviation of validation scores obtained by fixing individual hyperparameter values in C-TDGs models. The hyperparameter names corresponding to these values are also provided for reference. “wd” means weight decay, “ed” embedding dimension, “lr” learning rate, “gl” number of DGN layers, “ge” DGN dimension, and “re” readout embedding dim.

Figure 33 : The relative change in the weights (

\bar{\mathbf{W}}

) across layers for A-DGN, SWAN, and SWAN- learn models, measured on the Diameter task of the Graph Property Prediction experiment. Here,

\bar{\mathbf{W}}

represents the norm of the weights of the entire graph convolutional layer, i.e.,

\bar{\mathbf{W}}_{\ell}=norm\left(concat({\bf W}_{\ell},{\bf V}_{\ell},{\bf Z}_{\ell})\right)

, with

{\bf V}_{\ell}

the weights of the aggregation function

\Phi

and

{\bf Z}_{\ell}

the weights of the antisymmetric aggregation function

\Psi

(when possible). The encoder and readout components’ weights are excluded.

	Nodes	Edges	Features	Classes	Density
GPP	25 - 35	22 - 553	2	—	0.0275 - 0.5
Texas	183	309	1703	5	9.3 $e^{-3}$
Cornell	183	295	1703	5	8.9 $e^{-3}$
Squirrel	5201	217073	2089	5	8.0 $e^{-3}$
Wisconsin	251	499	1703	5	8.0 $e^{-3}$
Chameleon	2277	36101	2325	5	7.0 $e^{-3}$

Appendix

Table 43 : Datasets statistics ordered by graph density.

Hyperparameter	Values
Hyperparameter	GraphProp	Bench	H-Bench
optimizer	Adam	AdamW	Adam
learning rate	0.003	$10^{-2}$ , $10^{-3}$ , $10^{-4}$	$10^{-1}$ , $10^{-2}$ , $10^{-4}$
weight decay	$10^{-6}$	0.1	$10^{-2}$
n. layers	1, 5, 10, 20	1, 2, 3, 5 ,10, 20, 30	8, 16, 32, 64
embedding dim	10, 20, 30	32, 64, 128	128, 256, 512, 1024

Appendix

Table 44 : The grid of hyperparameters employed during model selection for the graph property prediction tasks (GraphProp), graph benchmarks (Bench), and graph heterophilic benchmarks (H-Bench).

Panel of Figure 36 — Figure 36 : The relative change in Jacobian of GCN and our SWAN over layers, measured on the peptides-func data.

Panel of Figure 37 — Figure 37 : Line, ring, and crossed-ring graphs where the distance between source and target nodes is equal to 5. Nodes marked with “S” are source nodes, while the nodes with a “T” are target nodes.

Hyperparameters	Values
Hyperparameters	Transfer	GraphProp	LRGB
optimizer	Adam	Adam	AdamW
learning rate	0.001	0.003	0.001, 0.0005
weight decay	0	$10^{-6}$	0, 0.0001
n. layers	3, 5, 10, 50	1, 5, 10, 20	5, 8, 16, 32
embedding dim	64	10, 20, 30	64, 128

Appendix

Table 45 : The grid of hyperparameters employed during model selection for the graph transfer tasks ( Transfer ), graph property prediction tasks ( GraphProp ), and Long Range Graph Benchmark ( LRGB ). We observe that, in each graph transfer task, we use a number of layers that is equal to the distance between the source and target nodes.

Hyperparameters	Values
Hyperparameters	Transfer	GraphProp	LRGB
optimizer	Adam	Adam	AdamW
learning rate	0.001	0.003	0.001, 0.0005
weight decay	0	$10^{-6}$	0
embedding dim	64	10, 20, 30	195, 300
n. layers ( $L$ )	3, 5, 10, 50,	1, 5, 10, 20, 30	32, 64

Appendix

Table 46 : The grid of hyperparameters employed during model selection for the graph transfer tasks ( Transfer ), graph property prediction tasks ( GraphProp ), and Long Range Graph Benchmark ( LRGB ). We refer to Appendix 11.A for more details about dampening and external force implementations.

Panel of Figure 38 — Figure 38 : (a) A grid graph consisting of 70 nodes in which each node is characterized by an initial temperature. Darker colors correspond to colder temperatures, while brighter colors mean warmer temperatures. (b) The heat diffusion simulation is computed through 1000 steps forward Euler’s method leveraging $-\mathbf{L}\mathbf{X}(t)$ as diffusion.

	# Steps	# Nodes	# Edges	Timespan
MetrLA	34,272	207	1,515	1 st Mar. - 30 th Jun. 2012
Montevideo	739	675	690	1 st Oct. - 31 st Oct. 2020
PeMS03	26,208	358	442	1 st Sep. - 30 th Nov. 2018
PeMS04	16,992	307	209	1 st Jan. - 28 th Feb. 2018
PeMS07	28,225	883	790	1 st May - 31 st Aug. 2017
PeMS08	17,856	170	137	1 st Jul. - 31 st Aug. 2016

Appendix

Table 47 : Statistics of the original version of the datasets.

Hyperparameters	Values
	Heat	Bench
learning rate	$10^{-2}$ , $10^{-3}$ , $10^{-4}$
weight decay	$10^{-2}$ , $10^{-3}$
$\eta$	concat, sum, $\eta(\overline{\mathbf{x}},\hat{\mathbf{x}})=\overline{\mathbf{x}}$
activation fun.	tanh, relu, identity
embedding dim.	None, 8	64, 32

Appendix

Table 48 : The grid of hyperparameters employed during model selection for the heat diffusion tasks ( Heat ) and graph benchmark tasks ( Bench ). The

\epsilon

hyperparameter is only used by our method (i.e., TG-ODE), and embedding dim equal to None means that no encoder and readout are employed.

	# Nodes	# Edges	# Edge ft.	Split	Surprise Index
T-PathGraph	3,000-20,000	2,000-19,000	1	70/15/15	1.0
T-PascalVOC 10	2,671,704	2,660,352	14	70/15/15	1.0
T-PascalVOC 30	2,990,466	2,906,113	14	70/15/15	1.0
Wikipedia	9,227	157,474	172	70/15/15, Chron.	0.42
Reddit	11,000	672,447	172	70/15/15, Chron.	0.18
LastFM	2,000	1,293,103	2	70/15/15, Chron.	0.35

Appendix

Table 49 : Statistics of the datasets used in our experiments. We report the total number of nodes and edges in the dataset for the temporal path graph (i.e., T-PathGraph) and temporal Pascal VOC (i.e., T-PascalVOC). “Chron.” means that chronological order is preserved.

Figure 39 : The illustration of the sequence classification task on a temporal path graph consisting of 5 nodes. The first node (colored in orange) has an initial feature that can be either

1

-1

. All the other nodes and edges have a feature set to random value sampled uniformly in

[-1,1]

. At the end of the sequence, the representation computed for the last node (colored in red) is used to predict the original value of the first node. At each timestamp, the faded portion of the graph corresponds to historical information.

Figure 40 : Construction of the Temporal PascalVOC-SP dataset. The SLIC algorithm extracts patches from an image. We create the rag-boundary graph connecting neighboring patches based on spatial closeness. We construct a temporal graph by traversing from the topleftmost node with BFS. The goal of the task is to predict the class of the destination node at each visited edge - in the figure, either ’potted plant’ (red) or ’background’ (blue). For clarity in this visualization, the compactness of the SLIC algorithm is low.

Hyperparameters	Method	Values
		Seq	Pasc	Link
optimizer		Adam
learning rate		$3\cdot 10^{-4}$	$3\cdot 10^{-4}$	$10^{-4}$ , $10^{-5}$
weight decay		$10^{-7}$	$10^{-5}$	$10^{-6}$
n. GCLs		1, 3, 5
$\sigma$		tanh

Appendix

Table 50 : The grid of hyperparameters employed during model selection for the following three tasks: Sequence classification on temporal path graphs ( Seq ), Temporal Pascal-VOC ( Pasc ), and Link Prediction ( Link ). For Seq and Pasc , we conducted 10 runs and 5 runs with different random seeds for different weight initializations for each configuration , whereas for Link , we conducted 5 runs only for the configuration that resulted in the best performance in the initial run. For the three tasks, the models were configured to have a maximum number of learnable parameters of

\sim

20k ,

\sim

40k , and

\sim

140k , respectively. Training was conducted for 20 epochs , 200 epochs , and 1000 epochs , respectively. For Seq and Pasc , we employed a scheduler halving the learning rate with a patience of 5 epochs , 20 epochs , respectively, whereas for Link we used early stopping with a patience of 50 epochs . For all tasks, the neighbor sampler size was set to 5. The batch size was set to 128 , 256 , and 256 , respectively. We used the loss , F1-score , and AUC on the validation set to optimize for the hyperparameters. We used dropout only for GraphMixer and DyGFormer, where the values are loosely based on best-performing values in Yu (2023) .

Hyperparameters	Values
Hyperparameters	tgbl-wiki-v2	tgbl-review-v2	tgbl-coin-v2	tgbl-comment
optimizer	Adam
$\sigma$	tanh
$\gamma$	0.1	0.1, 0.01	0.1, 0.01	0.1
$\eta$	concat, $\eta=\text{tanh}(\textbf{h}^{i-1}(t_{e})\|\|\mathbf{x}(i))$
n. GCLs	1, 2, 3	1,2	1	1

Appendix

Table 51 : The grid of hyperparameters employed during model selection for CTAN on the Dynamic Link Property Prediction task on the three TGB benchmark datasets considered: tgbl-wiki-v2 , tgbl-review-v2 , tgbl-coin-v2 , tgbl-comment . For tgbl-wiki-v2 we conducted five runs with different random seeds for different weight initializations for each configuration, whereas for the other datasets we conducted three different runs. The rest of the training configuration is taken from the TGB codebase: batch size is 200, weight decay penalty was 0, the optimized metric is Mean Reciprocal Rank and is evaluated with the TGB evaluator.

Panel of Figure 41 — Figure 41 : Graphical model of an HMM, with its recurrent view (a) and its unfolded view (b).

Figure 42 : Graphical model of HMM4G at layer

\ell

for node

u

in the graph. Observed r.v.s (values estimated at layer

\ell-1

) are in blue and latent ones in white.

Figure 43 : Computation process for node

u

in two consecutive layers of our HMM4G. In layer

\ell

, Expectation Maximization is applied to infer the parameters of the posterior distribution of the variable

Q_{u}^{t}

for all nodes and time-steps in the graph sequence. This information is then used to compute

\bm{h}^{t}_{\mathcal{N}u}

in the subsequent layer

\ell+1

. Finally, the computed

\bm{h}^{t}{\mathcal{N}_{u}}

is used to transition to the new state.

	# Nodes	Seq. len.	Frequencey	Split
Chickenpox	20	522	Weekly	80/10/10
Pedalme	15	30	Weekly	80/10/10
Wikimath	1,068	731	Daily	80/10/10
Twitter tennis	1,000	120	Hourly	80/10/10

Appendix

Table 52 : Statistics of the datasets used in our experiments.

Hyperparameters	HMM4G	Readout
n. layers	1, 2, 3, 4, 5	1, 2, 3
C	5, 10	–
epochs	10, 20, 40	1000
optimizer	–	Adam
learning rate	–	$10^{-3}$ , $10^{-2}$
weight decay	–	0, 0.0005, 0.005

Appendix

Table 53 : The grid of hyperparameters employed during model selection for our experiments.

Model	Chickenpox	Tennis	Pedalme	Wikimath
Baseline
Mean baseline	1.117	0.482	1.484	0.843
Linear baseline	0.952	0.356	1.499	0.663
DGN for D-TDGs
DCRNN	1.097 ±0.006	0.478 ±0.004	1.454 ±0.050	0.679 ±0.007
GCRN-GRU	1.103 ±0.004	0.477 ±0.007	1.420 ±0.054	0.680 ±0.021

Appendix

Table 54 : Test MSE with standard deviation averaged over 10 final runs. First , second , and third best results for each task are color-coded. Baselines taken from Micheli and Tortorella (2022) .

Explore similar work

CacheDyG: Decoupling Temporal Propagation for Efficient Dynamic Graph Learning
Sep 22, 2026PinHeng Zong, Ye YuanTemporal Graph Neural Networks Graph Representation Learning
College of Computer and Information Science, Southwest University, Chongqing, China
SiST-GNN: Simultaneous Spatial-Temporal Message Passing for Dynamic Graph Representation Learning
May 25, 2026Shubhajit Roy, Anirban DasguptaTemporal Graph Neural Networks Gnn-Based Detectors
Department of Computer Science and Engineering Indian Institute of Technology Gandhinagar
Forget Less, Generalize More: Unifying Temporal and Structural Adaptation for Dynamic Graphs
May 28, 2026Qian Chang, Ciprian Doru Giurcaneanu, Runsong Jia +6Recurrent State Rapid Adaptation
University of Auckland, Auckland, New Zealand · University of Technology Sydney, Sydney, Australia · Central China Normal University, Wuhan, China

Sep 22, 2026, cs.LGJ/K move · Enter open · S save

CacheDyG: Decoupling Temporal Propagation for Efficient Dynamic Graph Learning

PinHeng Zong, Ye Yuan

College of Computer and Information Science, Southwest University, Chongqing, China

Temporal Graph Neural Networks Graph Representation Learning Temporal Dynamics Refinevla

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

CacheDyG: Decoupling Temporal Propagation for Efficient Dynamic Graph Learning

SiST-GNN: Simultaneous Spatial-Temporal Message Passing for Dynamic Graph Representation Learning

Forget Less, Generalize More: Unifying Temporal and Structural Adaptation for Dynamic Graphs