Organizations: School of Cyberspace, Hangzhou Dianzi University, China · State Key Laboratory of AI Safety, Beijing · School of Computer Science, Wuhan University, China · College of Intelligence and Computing, Tianjin University, China
Although dynamic graph neural networks (DyGNNs) have demonstrated promising capabilities, most existing methods ignore out-of-distribution (OOD) shifts that commonly exist in dynamic graphs. Dynamic graph OOD generalization is non-trivial due to the following challenges: 1) Identifying invariant and variant patterns amid complex graph evolution, 2) Capturing the intrinsic evolution rationale from these patterns, and 3) Ensuring model generalization across diverse OOD shifts despite limited data distribution observations. Although several attempts have been made to tackle these challenges, none has successfully addressed all three simultaneously, and they face various limitations in complex OOD scenarios. To solve these issues, we propose a Dynamic graph Causal Invariant Learning (DyCIL) model for OOD generalization via exploiting invariant spatio-temporal patterns from a causal view. Specifically, we first develop a dynamic causal subgraph generator to identify causal dynamic subgraphs explicitly. Next, we design a causal-aware spatio-temporal attention module to extract the intrinsic evolution rationale behind invariant patterns. Finally, we further introduce an adaptive environment generator to capture the underlying dynamics of distributional shifts. Extensive experiments on both real-world and synthetic dynamic graph datasets demonstrate the superiority of our model over state-of-the-art baselines in handling OOD shifts.
Figures & tables
Figure 1: Structural causal model for the generating process of the dynamic graph, where grey and white variables represent observed variables and unobserved, respectively.
Figure 2: The framework of DyCIL.
Dataset
# Nodes
# Edges
# Snapshots
# Features
# Classes
Train/Val/Test
Temporal Granularity
Distribution Shift
Collab
23,035
151,790
16
32
-
10/1/5
year
Cross-Domain Transfers
ACT
20,408
202,339
30
32
-
20/2/8
day
Cross-Domain Transfers
Synthetic-Collab
23,035
151,790
16
64
-
10/1/5
-
Feature Evolution
Temporal-Motif
5,000
298,709
30
8
3
24/3/3
-
Motif Structure Transfers
Aminer
43,141
851,527
17
128
20
11/3/3
year
Temporal Evolution
Table 1: The summary of the dataset statistics.
Dataset
Collab
ACT
Synthetic-Collab
Method Type
Model
w/o OOD
w/ OOD
w/o OOD
w/ OOD
pˉ=0.4
pˉ=0.6
pˉ=0.8
DyGNNs
GCRN
82.78±0.54
69.72±0.45
76.28±0.51
64.35±1.24
72.57±0.72
72.29±0.47
67.26±0.22
EvolveGCN
86.62±0.95
76.15±0.91
74.55±0.33
63.17±1.05
69.00±0.53
62.70±1.14
60.13±0.89
DySAT
88.77±0.23
76.59±0.20
78.52±0.40
66.55±1.21
70.24±1.26
64.01±0.19
62.19±0.39
OOD
IRM
87.96±0.90
75.42±0.87
80.02±0.57
69.19±1.35
69.40±0.09
63.97±0.37
62.66±0.33
VREx
88.31±0.32
76.24±0.77
83.11±0.29
70.15±1.09
70.44±1.08
63.99±0.21
62.21±0.40
Table 2: AUC score (%) of link prediction. The best are bolded and the second best are underlined.
Dataset
Temporal-Motif
Aminer
Method Type
Model
T-M28
T-M29
T-M30
Aminer15
Aminer16
Aminer17
DyGNNs
GCRN
51.93±1.68
51.55±1.26
51.31±1.28
47.96±1.12
51.33±0.62
42.93±0.71
EvolveGCN
45.63±0.33
45.50±0.28
45.29±0.42
44.14±1.12
46.28±1.84
37.71±1.84
DySAT
48.44±0.56
48.20±0.45
47.99±0.45
48.41±0.81
49.76±0.96
42.39±0.62
OOD
IRM
50.17±0.71
50.01±0.52
49.84±0.67
48.44±0.13
50.18±0.73
42.40±0.27
VREx
51.32±0.77
52.64±0.63
50.79±0.46
48.70±0.73
49.24±0.27
42.59±0.37
Table 3: ACC score (%) of node classification. The best are bolded and the second best are underlined.
Figure 3: The ablation experiment results.
Figure 4: A case study on Temporal-Motif dataset.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Symbol
Description
G1:T
A dynamic graph with T snapshots
Gt
The snapshot at timestamp t
Vt,Et
The nodes and edges of the snapshot Gt
Yt , Ytu
Labels of Gt and the label of node u in Gt
Xt,At
The feature matrix and adjacency matrix of Gt
G1:Tc
The causal dynamic subgraph of G1:T
Appendix
Table 4: Major notations in this paper
Figure 5: Illustration of the six motif structures in Temporal-Motif, where the ’house’ motif is the causal subgraph, and the others are variant subgraphs.
Figure 6: The ablation experiment results.
Figure 7: Parameter sensitivity analysis on causal ratio r .
Figure 8: Parameter sensitivity analysis on trade-off weight λ .
Figure 9: The training time cost per epoch of DyCIL and other three dynamic graphs OOD methods on Collab and ACT datasets
Department of Computer Science, Purdue University, West Lafayette, USA · Department of Computer Science and Engineering, The Ohio State University, Columbus Ohio, USA · Department of Industrial and Systems Engineering, The Ohio State University, Columbus Ohio, USA
School of Computer Science and Engineering, Nanjing University of Science and Technology, China · School of Computing and Information Systems, Singapore Management University, Singapore · Faculty of Data Science, City University of Macau, Macau, China +3