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
Continuous-Time Dynamic Graphs (CTDGs) enable fine-grained modeling of evolving relational systems. However, most existing CTDG representation learning methods are tailored to in-distribution settings and exhibit limited robustness under out-of-distribution (OOD) shifts. Although recent causal approaches learn invariant representations via interventions, they are primarily designed for static or discrete-time graphs and become computationally prohibitive for CTDGs due to the combinatorial explosion of structural and temporal variations. To address these challenges, we propose CIR, a framework grounded in a novel structural causal model termed the ICCM. To avoid exhaustive interventions, we leverage the Normalized Weighted Geometric Mean (NWGM) to efficiently approximate interventional predictions. We further instantiate ICCM within a practical deep learning architecture that jointly captures invariant structural and temporal patterns through dedicated subgraph extractors, and maintains an environment memory bank to model distributional shifts across evolving contexts. Extensive experiments demonstrate that CIR consistently outperforms existing methods under diverse OOD scenarios.
Lanting Fang, Yulian Yang, Yawei Zhang +3
1Beijing Institue of Technology · Southeast University · Wuhan University
Out-of-distribution (OoD) generalization occurs when representation learning encounters a distribution shift. This occurs frequently in practice when training and testing data come from different environments. Covariate shift is a type of distribution shift that occurs only in the input data, while the concept distribution stays invariant. We propose RIA - Regularization for Invariance with Adversarial training, a new method for OoD generalization under convariate shift. Motivated by an analogy to Q-learning, it performs an adversarial exploration for counterfactual data environments. These new environments are induced by adversarial label invariant data augmentations that prevent a collapse to an in-distribution trained learner. It works with many existing OoD generalization methods for covariate shift that can be formulated as constrained optimization problems. We develop an alternating gradient descent-ascent algorithm to solve the problem in the context of causally generated graph data, and perform extensive experiments on OoD graph classification for various kinds of synthetic and natural distribution shifts. We demonstrate that our method can achieve high accuracy compared with OoD baselines.
Simon Zhang, Ryan P. DeMilt, Kun Jin +1
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
Activities in numerous evolving systems can be represented as dynamic graphs in snapshot form at different time intervals, i.e., discrete-time dynamic graphs (DTDGs). Existing methods show impressive advances in capturing historical temporal evolution patterns in DTDGs, but they focus on addressing an offline learning setting, where models are trained using historical snapshots once and then evaluated to all subsequent graph snapshots without further updating. This fails to capture 1) the nature of evolving complexities across graph snapshots and 2) the distribution shift in the testing graph snapshots. To address these problems, we propose PromptDyG, a novel framework that leverages unsupervised test-time Prompt adaptation for Dynamic Graph learning under a live-update online setting. The key insight is that an expressive dynamic graph prompt can be learned on a frozen backbone via minimization of feature-wise, label-free entropy to efficiently and continuously model the evolving patterns. We show theoretically that this unsupervised prompt adaptation can guarantee a larger similarity margin between positive and negative pairs, facilitating more accurate dynamic predictions. It is further confirmed by our extensive empirical results on six benchmark datasets that show consistent and significant improvements of PromptDyG over state-of-the-art baselines.
Guoguo Ai, Chaoxi Niu, Hui Yan +3
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