Environment-Aware Dynamic Graph Learning for Out-of-Distribution Generalization
Authors: Haonan Yuan
Qingyun Sun
Xingcheng Fu
Ziwei Zhang
Cheng Ji
Hao Peng
Jianxin Li
Venue: NeurIPS 2023 poster (2023)
Keywords: dynamic graph learning
out-of-distribution generalization
invariant learning
link prediction
TL;DR: We propose a novel Environment-Aware dynamic Graph LEarning (EAGLE) framework for OOD generalization by modeling complex spatio-temporal environments and further exploiting time-invariant patterns.

Abstract: Dynamic graph neural networks (DGNNs) are increasingly pervasive in exploiting spatio-temporal patterns on dynamic graphs. However, existing works fail to generalize under distribution shifts, which are common in real-world scenarios. As the generation of dynamic graphs is heavily influenced by latent environments, investigating their impacts on the out-of-distribution (OOD) generalization is critical. However, it remains unexplored with the following two major challenges: **(1)** How to properly model and infer the complex environments on dynamic graphs with distribution shifts? **(2)** How to discover invariant patterns given inferred spatio-temporal environments? To solve these challenges, we propose a novel **E**nvironment-**A**ware dynamic **G**raph **LE**arning (**EAGLE**) framework for OOD generalization by modeling complex coupled environments and exploiting spatio-temporal invariant patterns. Specifically, we first design the environment-aware EA-DGNN to model environments by multi-channel environments disentangling. Then, we propose an environment instantiation mechanism for environment diversification with inferred distributions. Finally, we discriminate spatio-temporal invariant patterns for out-of-distribution prediction by the invariant pattern recognition mechanism and perform fine-grained causal interventions node-wisely with a mixture of instantiated environment samples. Experiments on real-world and synthetic dynamic graph datasets demonstrate the superiority of our method against state-of-the-art baselines under distribution shifts. To the best of our knowledge, we are the first to study OOD generalization on dynamic graphs from the environment learning perspective.

Environment-Aware Dynamic Graph Learning for Out-of-Distribution Generalization
Haonan Yuan 1., Qingyun Sun 12; Xingcheng Fu?, Ziwei Zhang", Cheng !2
Hao Peng', Jianxin Li
Beijing Advanced Innovation Center for Big Data and Brain Computing, Beihang University School of Computer Science and Engineering, Beihang University
Key Lab of Education Blockchain and Intelligent Technology. Guangxi Normal University *Department of Computer Science and Technology, Tsinghua University sruaghn,sunqy, sunqy, penghao, 1i jijx)abuaa. edu. fuxcêgxmu.c edu. cn, zwzhang@tsinghuu. edu. cn
fyuanhn,
Abstract
Dynamic graph neural networks (DGNNs) are increasingly pervasive in exploiting spatio-temporal patterns on dynamic graphs. However, existing works fail to generalize under distribution shifts, which are common in real-world scenarios. As the generation of dynamic graphs is heavily influenced by latent environments, investigating their impacts critical. However, it remains unexplored with the following two major challenges: (I) How properly model and infer the complex environments on dynamic graphs with distribution shifts? (2) How to discover invariant patterns given inferred spatio-temporil environments? To solve these challenges, we propose a novel Environment-A ware dynamic Graph LEarning (EAGLE) framework for OOD generalization by modeling complex coupled environments and exploiting spatio- temporal invariant patterns. Specifically, we first design the environment-awar EA- DGNN to model environments by multi-channel environments disentangling. Then, propose environment instantiation mechanism for environment diversification with inferred distributions. Finally, we discriminate spatio-temporal invariant patterns for out-of-distribution prediction by the invariant pattern recognition mechanism and perform fine- fine-grained causal interventions node-wisely with a mixture of instantiated environment samples. Experiments synthetic dynamic graph datasets demonstrate the superiority of our method against state-of-te the-hte-r art baselines under distribution shifts. To the best of our knowledge, we are the first to study OOD generalization on dynamic graphs from the environment learning perspective.
the -attt--distritttion (OOD) generalization is
real-world and
1 Introduction
Dynamic graphs ubiquitous in the real world, like social networks 6 25
financial transaction
networks (61 93], traffic networks [47 (97 (96), etc., where the graph topology evolves as time passes. Due to their complexity in both spatial and temporal correlation patterns, wide-ranging applications such as relation prediction [39] (68. anomaly detection [10] 699, etc. are rather challenging. With ex- cellent expressive power, dynamic graph neural networks (DGNNs) achieve outstanding performance in dynamic graph representation learning by combining the merits of graph neural network (GNN) based models and sequential based models.
Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

to (Tain))
ts (Train)
to iTstti
e
S
C
G
Y
Causal P art (invariant)
$
Spurious P (variant)
Obssevvttio
Ground-truth
Prediction
Environments
Observations
Latent Factors
(a) A toy example of distribution shifts on dynamic graphs.
(b)
The SCM model on dynamic graphs.
Figure I: (a) shows the "user-item" interactions with heavy distribution shifts when the underlying environments change (e.g., seasons). A model could mistakenly predict that users would purchase an Iced Americano instead of a Hot Latte it fails to capture spatio-temporal invariant patterns among spurious correlations. (b) analyzes the underlying cause of distribution shifts on dynamic graphs is broadly convinced [64, 67] that the spurious correlations of C' (coffee) ++ S (cold drink) within and between graph snapshots lead to poor OOD generalization under distribution shifts, which need be filtered out via carefully investigating the impact of latent e. (Detailed discussions in Appendix F.I
Despite the popularity, most existing works are based on the widely accepted I.I.D. hypothesis, i.e. the training and testing data both follow the independent and identical distribution, which fails to generalize well (77 under the out-of-distribun
(OOD) shifts dynamic scenarios. Figure [[a] illustrates a toy example demonstrating the OOD shifts on a dynamic graph. The failure lies in: (1) the exploited predictive patterns have changed for in-the-wild extrapolations, causing spurious correlations to be captured (94] and even strengthened with spatio-temporal convolutions. (2) perform- ing causal intervention and inference without considering the impact of environments, introducing external bias of label shifting 191). These can be explained by SCM model
[64 65, 66) in Figure [(b)
As the generation of dynamic graphs is influenced by complicated interactions of multiple varying latent environment factors [86] [7]] 8 24] 3 79 78 53), like heterogeneous neighbor relations,
multi-community affiliations, etc., investigating the roles environments play in OOD generalization is of paramount importance. To tackle the issues above, we study the problem of generalized representation learning under OOD shifts on dynamic graphs in an environment view by carefully exploiting spatio-temporal invariant patterns. However, this problem is highly challenging in:
How to understand and model the way latent environments behave on dynamic graphs over time?
How to infer the distribution of underlying environments with the observed instances?
How to recognize the spatio-temporal invariant patterns over changing surrounding environments?
To address these challenges, we propose a novel Environment-Awe dynamic Graph LEarning (EAgle) framework for OOD generalization, which handles OOD generalization problem by exploit- ing spatio-temporal invariant patterns, thus filtering out spurious correlations via causal interventions over time. Our EAGLE solves the aforementioned challenges and achieves the OOD generalization tar- get as follows. Firstly, to shed light on environments, we design the environment-aware EA-DGNN model environments by multi-channel environments disentangling. It can be considered as learning the disentangled representations under multiple spatio-temporal correlated environments, which makes it possible infer environment distributions and exploit invariant patterns. Then, we propose an environment instantiation mechanism for environment diversification with inferred environment distributions by applying the multi-labe variational inference. This endows our EAGLE with higher generalizing power of potential environments. Lastly, we propose a novel invariant pattern recogni- tion mechanism for diitr--distribttion prediction that satisfies the Invariance Property and Sufficient Condition with theoretical guarantees. We then perform fine- inn-ggrined causal interventions with mixture of observed and generated environment instances to minimize the empirical and invariant risks. We optimize the whole framework by training with the adapted min-max strategy, encouraging EAGLE to generalize to diverse environments while learning on the spatio-temporal invariant patterns. Contributions of this paper are summarized follows:

---

e
e
paradigm endows EAGLE with ① Modeling
Inferring
Discriminating
4 Generalizing
p P 1.T Ye
Environment Instantatiin Mechanism
(e)
x(k 1,03
Go (elo,y) >
e
Ru (x)y,e)
2(K-2,1)
Time Encoding
sample
da (z)
Link Predictor
PV
variant
I
P!
=
@1
e2
invariant
0
Invariant Pattern
@ Spatio-temporal
EA-DGNN
Recognition Mechanism
Causal Intervention Mechanism
Figure 2: The framework of EAGLE, Our proposed method jointly optimizes the following modules: (1) For given dynamic graph generated under latent environments, the EA-DGNN first models environment by multi-channel environments disentangling. (2) The environment instantiation mech- anism then infers the latent environments, followed by environment diversification with inferred distributions. (3) The invariant pattern recognition mechanism discriminates the spatio-temporal invariant patterns for OOD prediction. (4) Finally, EAGLE generalizes diverse environments by performing fine-grained causal interventions node-wisely with a mixture of environment instances. The Environment "Modeling- Inferrinn---r------ D higher generalizing power for future potential environments.
We propose a novel framework named EAGLE for OOD generalization by exploiting spatio- temporal invariant patterns with respect to environments. To the best of our knowledge, this the first trial to explore the impact of environments on dynamic graphs under OOD shifts.
We design the Environment endow EAGLE with higher extrapolation power for future potential environments. EAGLE can carefully model and infer underlying environments, thus recognizing the spatio-temporal invariant patterns and performing fine-grained causal intervention node-wisely with mixture of observed and generated environment instances, which generalize well to diverse OOD environments.
paradigm to
Extensive experiments on both real-world and synthetic datasets demonstrate the superiority of our method against state-of-the-as baselines for the future link prediction task.
2 Problem Formulation
In this section, formulate the OOD generalization problem dynamic graphs. Random variables are denoted as bold symbols while their realizations are denoted as italic letters. Notation with its description can be found in Appendix
Dynamic Graph Learning. Denote dynamic graph as set of discrete graphs snapshots DG (G)7 where 7' is the time length [94] 571, G = (Vr E*) is the graph snapshot at time t, D is the node set and Eº is the edge set. Let A E {0, 1] J be the adjacency matrix and X' E Xxd be the matrix of node features, where N = | denotes the number of nodes and denotes the dimensionality. As the most challenging task on dynamic graphs, future link prediction task aims to train a predictor fe
- (0, 1 N X that predicts the existence of edges at time T + given historical graphs g gl:T. Concretely, fo w o is compound of DGNN w(-) for learning node representations and a link predictor 9(-) for predicting links, i.e., Z w(1 1:T)) and ý g TT))

---

The widely adopted Empirical Risk Minimization (ERM) 82 learns the optimal fā as follows:
min Yo) | (So (G YT)].
OOD Generalization with Environments. The predictor fā learned in Eq. ① may not generalize well to the testing set when there exist distribution shifts, i.e., Prest G Y" + Ptrain (G Y A broadly accepted assumption is that the distribution shifts on graphs are caused by multiple latent environments e
86 7
g
24 3), which influence the generation of graph data, i.e. p(G Y
e) p G 1:7
e p Y
G I:T e). Denoting E as the support of environments across T time slices,
the optimization objective of OOD generalization can be reformulated as:
min max (OgGTTTYT))p)GTTTTT
| (Jo (G YY) le).
0 e
where the min-max strategy minimizes ERM under the worst possible environment. However, directly optimizing Eq. (2) is infeasible as the environment e cannot be observed in the data. In addition, the
training environments may not cover all the potential environments in practice, ie.., Etrain C Etest-
3 Method
In this section, we introduce EAGLE, an Environment-A ware dynamic Graph LEarning framework, to solve the OOD) generalization problem. The overall architecture of EAGLE is shown in Figure 2 following the Environment "Modeling-Interring Inferring-Diseriminnt Seneerinnnnting-Geeeaaaaiaa paradigm.
3.1 Environments Modeling with Environment-aware DGNN
To optimize the objectives of OOD generalization, first need to infer the environments of dynamic graphs. In practice, the formation of real-world dynamic graphs typically follows a complex process under the impact of underlying environments [56] 51. For example, the relationships in social networks are usually multi-attribute (e.g., colleagues, classmates, etc.) and are changing over time (e.g.. past classmates, current colleagues). Consequently, the patterns of message passing and aggregation in both spatial and temporal dimensions should be diversified in different environments, while the existing holistic approaches [94 52) fail distinguish them. To model spatio-tempone environments, we propose an Environment-A ware Dynamic Graph Neural Network (EA-DGNN) to exploit environment patterns by multi-channn environments disentangling.
Environment-aware Convolution Layer (EAConv). We perform convolutions following the "spatial first, temporal second" paradigm as most DGNNS do (54) We consider that the occurrence of links is decided by K underlying environments e, {eR by the features and structures of local neighbors. To obtain representations under multiple underlying environments, EAConv firstly projects the node features x into K subspaces corresponding to different environments. Specifically, the environment-aware representation of node v with respect to the k-th environment eş at time t is calculated as:
K k= of the central node v, which can be revealed
Z = (Wi & (x", @ RTE(!)) + bb),
(3)
where We E Rdd and by E Idd are learnable parameters, RTE(-) is the relative time encoding function, d' is the dimension of 2 (()) is the activation function (e.g., the Sigmoid function), and @ is the element-wiss addition.
To reflect the varying importance of environment patterns under K embedding spaces, we perform multi-channel convolutions with spatio-temporal aggregation reweighting for each e₁.- Let A ( be the weight of edge (u, v) under e at time t. The spatial convolutions of one EAConv layer are formulated as (note that we omit the layer superscript for brevity):
E z +
Σ (EN'(v)
A A(u.)) 2i
exp((2
)
T (2(xk)
A (u.n),
(5)
Σ exp((z)) )

---

where (e) is the neighbors of node e at time t and 2 denotes the updated node embedding. We then concatenate K embeddings from different environments as the final node representation 2, | 2 E Rxxd where ||- means concatenation. After that, we conduct temporal convolutions holistically here for graph snapshots at time and before:
2. ERRx
where - 12,,211 ... -
Note that, the temporal convolutions can be easily extended other sequential convolution models or compounded with any attention/reeiighhngg mechanisms.
EA-DGNN Architecture. The overall architecture of EA-DGNN is similar to general GNNs by stacking L layers of EAConv. In global view, we exploit the patterns of environments by reweighting the multi-attribute link features with K channels. In the view of individual node, multiple attributes in the link with neighbors can be disentangled to different attention when carrying out convolutions on both spatial and temporal dimensions. We further model the environment-aware representations by combining node representations each time snapshot z U (2) Rxxx(xx'),
3.2 Environments Inferring with Environment Instantiation Mechanism
To infer enviromments with the environmental patterns, we propose an environment instantiation mechanism with multi-label variational inference, which can generate environment instances given multi-labels of time / and environment index k:
Environment Instantiation Mechanism is a type of data augmentation to help OOD generalization. We regard the learned node embeddings z as environment samples drawn from the ground-truth distribution of latent environment e. Particularly, we optimize a multi-label Environment-avee Conditional Variational AutoEncoder (ECVAE) to infer the distribution of e ~ q z,y) across
T. We have the following proposition. Proof for Proposition Can be found in Appendix C.T
Proposition 1. Given observed environment samples from the dynamic graph Gl:T denoted as
K (z , [((M|XXT)xx def
z=
U-U k=vk=ltz
Sob
with their corresponding one-hot multi-labels y, the environment variable e is drawn from the prior distribution (e. y) across T time slices, and z is generated from the distribution Pw (z y, e). Maximizing the conditional log-likelihood log (z y) leads to optimal ECVAE by minimizing:
[x|
1
LECVAE (L(ga(e z, y,
y)]
log Pw (z y, e!))
(8)
where KL[-II-] is the Kullback-Leibbe (KL) divergence 37. |z| is the number of observed environ- ment samples, (1) is the i-th sampling by the reparameterization trick.
Sampling and Generating. Proposition demonstrates the training objectives of the proposed ECVAE. We realize ECVAE using fully connected layers, including environment recognition network qo (e z. y) as the encoder, a conditional prior network (w y) as observed environment instantiations, and an environment sample generation network P= y, e) as the decoder. By explicitly sampling latent c; from (c), we can instantiate environments by generating samples z from the the inferred distribution Pw y;, e;) with any given one-hot multi-label mixed up with the environment index k; and time index f.- We denote the generated samples as Sges which can greatly expand the diversity of the observed environments Sob in Eq.
3.3 Environments Discriminating with Invariant Pattern Recognition
Inspired by the Independent Causal Mechanism (ICM) assumption 664 65 67 next propose to
leam the spatio-temporal invariant patterns utilizing our inferred and instantiated environments.
Invariant Pattern Recognition Mechanism. To encourage the model to rely on the invariant correlation that can generalize under distribution shifts, we propose an invariant pattern recognition mechanism to exploit spatio-temporal invariant patterns. We make the following assumption.
5

---

Assumption 1 (Invariant and Sufficient). Given the dynamic graph Gl:T, each node is associated with K surrounding environments. There exist spatio-temporal invariant patterns that can lead to generalized out-of-distributis prediction across all time slices. The function (*))) can recognize the spatio-temporal invariant patterns Py and variant patterns Py node-wisely, satisfying:
(a) Invariance Property: Ve E E, (Z):T) } Po, s.t. p(Y Pe e) p(Y"' P));
(b) Sufficient Condition: Y g (Z) + +e, ie., Y IL P P. where Z denotes representa- tions under Pd over time, s() is the link predictor, is an independent noise.
Assumption I indicates that the modeled environment -wvironment-aware aware representations of nodes under P contain portion of apatio-tempora invariant causal features that contribute to generalized OOD prediction over time. Invariance Property guarantees for any environment e, function (.) can always recognize the invariant patterns Pe with the observation of Z and Sufficient Condition ensures the information contained in Z) is adequate for the link predictor to make correct predictions.
Next, we show that I (-) in Proposition can be instantiated with the following proposition.
Proposition 2 (A Solution for (-)). Denote z = | 2 x where z',a = UT= = Let Vzr(z E E represents the variance of K environment-awann representations. The Boolean function (I()) a solution for 1-))) with the following state update equation:
1(i v 1,j Var(z,)) )i I)), j 2 Var(z.)) 1] T(i 1,5),
((i.j)
otherwise
[(t,j) indicates whether it is feasible to select from the first elements in Var(z,") so that their sum j. Traversing,) j in reverse order from EΣ Var(z")) until satisfying ((K,)) is True, reach:
8 = Σ Var(z 2j,
(10)
(v) = {(ex Var(z,)) [k] <
8,
K Σ Var(z,) 2
PV (p))=
(11)
where 6, is the optimal spatio-temporal invariance threshold of node e.
Proposition 2 solves a dynamic programming problem to obtain the optimal (+), whose target is to find a partition dividing all patterns into variant/invariat set with the maximum difference between the variance means that reveals the current invariance status, providing an ideal optimizing start point. The proof can be found in Appendix C.2
With the theoretical support of Assumption I and Proposition 2 can recognize the spatio-temporal invariant/variant patterns P! = U.ev (v) and Pe = =U>e PV (v) with respect to the underlying
environments for each node over a period of time by applying II()).
3.4 Environments Generalizing with Causal Intervention
Generalization Optimization Objective. Eq. (2) clarifies the training objective of OOD generaliza- tion. However, directly optimizing Eq. (2) is not impracticable. Based on the inferred and generated environments in Section 3.2 and -patio-temporal invariant patterns learned in Section 3.3 further modify Eq. (2 to improve the model's ' OOD generalization ability by applying the intervention mechanism node-wisely with causal inference. Specifically, we have the following objectives:
min Crask + aLrisk.
(12)
Lrask = (eegg((e).(giir))")) x (g(Z)))) yr)"), [e (fo (G Y doo =))]]
(13)
Lrisk Varses (Be
(14)
where (e) is the environment distribution in Section 3.2 do(-) is the do-calculus that intervenes the variant patterns, S Sob USg is the observed and generated environment instances for interventions, and a is hyperparameter. We show the optimality of Eq. (12) with the following propositions:
Proposition 3 (Achievable Assumption). Minimizing Eq. 12 can encourage the model to satisfy the Invariance Property and Sufficient Condition in Assumption

---

Propasition 4 (Equivalent Optimization). Optimizing Eq. 12 is equivalent to minimizing the upper bound of the OOD generalization error Eq. (2).
Proposition avoids over-strong assumptions of the Sufficient Condition and Invariance Property. Proposition guarantees the OOD generalization error bound of the learned model within our expectation, which can also be explained in the perspective of the SCM model on dynamic graphs (Figure T(b) that, optimizing Eq. (12) eliminates the negative impacts brought by spatio-temporal spurious correlations between labels and variant patterns, while strengthening the invariant causal correlations under diverse latent environments. Proof's for Proposition 3 and Proposition 4 can be respectively.
found in Appendix C.3 and C.4
Spatio-temporal Causal Intervention Mechanism. As directly intervening the variant patterns node-wisely is time-consuming and intractable, we propose to approximately perform iie-grained spatio-temporal interventions with Sob USe by sampling and replacing variant patterns. For environment-avant representations 2 = [22, 2i,2," ... Ke of node at time I, we can obtain (((v) and P (v) by applying I((). As PV (v) represents environment indices related to variant patterns, we randomly sample instances as the intervention set 8, and perform node-wise replacing:
e.t [P' (w)] == Su, S. = {s 8 E Sab U
(15)
Note that, for each intervention operation, we randomly perform each replacement with different s. Further considering ECVAE loss in Eq. (8), the overall loss of EAGLE is defined as:
C
Leask
+ a
Crisk
LEOVAE
(16)
Eq.
13
Eq.
Eq. K
where 3 is another hyperparameter. We conduct hyperparameter sensitivity analysis in Appendix D.4 The training process of EAGLE summarized in Appendix B
Experiments
Datasets. We three real-world datasets evaluate EAGI 1 on the challenging link prediction task.
COLLAB [81 an academic collaboration dataset with papers published in 16 years; Yelp (75) contains customer reviews on business for 24 months; ACT 45 describes students actions
MOOC platform within 30 days. Statistics of the three datasets are concluded in T.Il
Baselines. We compare EAGLE with representative GNNs and OOD generalization methods.
Static GNNs: GAE [42 and VGAE 442 are GCN 41 based autoencoders on static graphs.
Dynamic GNNs: GCRN 76 adopts GCNs to obtain node embeddings. followed by a GRU [3 to capture temporal relations; EvolveGCN (62) applies an LSTM [3 or GRU to evolve the parameters of GCNs; DySAT
7 models self-attentions in both structural and temporal domains.
OOD Generalization Methods: IRM 3 learns invariant predictor minimize invariant risk; V-REx 44 extends IRM by reweighting the risk; GroupDRO 74) reduces the risk gap across training distributions; DIDA (44 exploits invariant patterns dynamic graphs.
4.1 Evaluation of Performance on Future Link Prediction Task
4.1.1 Distribution Shifts on Link Attributes
Settings. Each dataset owns multi-attribute relations. filter out one certain attribute links as the shifted variables under the future OOD environments in validation and training sets chronologically. This is more practical and challenging in information about the filtered links until testing stages. Note that, all attribute features have been removed after the above operations before feeding to EAGLE. Detailed settings are in Appendix [D.
scenarios as the model cannot get access to any
w/o OOD and w/ OOD) denote testing without and with Results. Results are shown in Table I
distribution shifts. The performance all baselines drops dramatically on each dataset when there exist distribution shifts. Static GNN baselines fail in both settings they cannot model dynamics.
'Code available at httpss /eettp::/gitaan tttpt////t/tttttt//eeee com/ htt.a//bccoom//iggnttttttt/aaaaa on Po PoTch 68 and MindSpore 33

---

Though dynamic GNNs are designed to capture spatio- temporal features. they even underperform static GNNs in several settings, mainly because the predictive patterns they exploited are variant with spurious correlations. Conventional OOD generalization baselines have limited improvements as they rely on the environment labels to generalize, which are inaccessible on dynamic graphs. As the most related work, DIDA (94) achieves further progress by learning invariant patterns. However, it is limited by the lack of in-depth analysis into the environments, causing the label shift phenomenon [9]] that damages its generalization ability. With the critical investigation of latent environments and theoretical guarantees, our EAGLE consistently outperforms the baselines and achieves the best performance in all w/ OOD settings and two w/o OOD settings. Especially even on the most challenging COLLAB, where the time span is extremely long (1990 to 2006) and its link attributes difference is huge.
Table 1: AUC score (% standard deviation) of future link prediction task on real-world datasets with OOD shifts of link attributes. The best results are shown in bold and the runner-ups are underlined.
Dataset
COLLAB
Yelp
ACT
Model
w/o OOD
w/OOD
w/o OOD
w/ 00D
w/ OOD
w/OOD
GAB [42
77.15=0.50
74.04=0.75
70.67=1.11
64,45+5 02
72.31=0.53
60.27=0.4 41
86.47:0.04
74.95&1.25
76.54+0.50
65.33+1
18.4870.47
66..9
GCRN 16
82.78:0.55
69.72:0.45
68 18.59:1.05
54.6817.5 7.59
76.28:0.51
1..3
EvolveGCN 62
86.62=0.95
76.15=0.91
78.21=0.03
53.82+2.06 220
74.55+0.33
63.17=1.05
DySAT
88.77=0.23
76.59+0.20
87.5770.57
66.09+1 .42
78.52+0.40
66.55+1.21
IRM
87.9622.900
75.42.0.87
10.79
$6.02:16.08
80.02+0.57
19.19
V-REx 44
88.31=0.32
76.2420.77
79 02.0442..1 16
66.41+1.87
83. 11
1.09
GroupDRO 74
88. 88.7620.12 12
76.33::0.29
79.
66.97+0.61
85. 19:0.53
74.35# 1.62
DIDA 94
91.97=0.05
81,87+0.40
78. 22:0200
75.92+0.90
89 84+084
78, 78.64+0.97 97
EAGLE
92.45=0.21
84.4120.87
78.9720.31
77.2620.74
92.37=0.53
82.70=0.72
4.1.2 Distribution Shifts of Node Features
Setting. We further introduce settings of node feature shifts on COLLAB. We respectively sample p(t)]E++ positive links and (1 p(t))]E*+1 negative links, which are then factorized into shifted features X" R while preserving structural property. The sampling probability p(t) p a cts, where X" with higher p(t) will have stronger spurious correlations with future underlying environments. We set p be 0.4, 0.6 and 0.8 for training and 0.1 for testing. In this way, training data are relatively higher spuriously correlated than the testing data. We omit results on static GNNs as they cannot support dynamic node features. Detailed settings are in Appendix D.3
Results. Results are reported in Table We can observe a similar trend as Table | i.e. our method better handles distribution shifts of node features on dynamic graphs than the baselines. Though some baselines can report reasonably high performance on the training set, their performance drops drastically in the testing stage. In comparison, our method reports considerably smaller gaps. In particular, our EAGLE surpasses the best-performed baseline by approximately 3%/5% of AUC in the testing set under different shifting levels. Interestingly. severer distribution shifts will lead to more significant performance degradation where the spurious correlations are strengthened, our method gains better task performance with higher shifting degree. This demonstrates EAGLE is more capable of eliminating spatio-temporal spurious correlations in severer OOD) environments.
4.2 Investigation on Invariant Pattern Recognition Mechanism
Settings. We generate synthetic datasets by manipulating environments to investigate the effect of the invariant pattern recognition mechanism. We set K = 5 and let de represent the proportion of the environments in which the invariant patterns are learned, where higher oe means more reliable invariant patterns. Node features are drawn from multivariate normal distributions, and features under the invariant patterns related C will be perturbed slightly and vice versa. We construct graph structures and filter out links built under a certain e₁ the same in Section 4.1.1 We compare EAGLE with the most related and strongest baseline DIDA 94. Detailed settings are in Appendix D.3
Results. Results are shown in Figure 3 TxCC denotes the prediction accuracy of the invariant patterns by I(()). We observe that, as ae increases, the performance of EAGLE shows a significant increase from 54.26% to 65. 590% while narrowing the gap between w/o OOD and w/ OOD scenarios.
8

---

Table 2: AUC score (% = standard deviation) of future link prediction task on real-world datasets with OOD shifts of node features. The best results are shown in bold and the runner-ups are underlined.
Dataset
COLLAB (p
0.4)
COLLAB (p
0.6)
COLLAB (ø 0.8)
Model
Train
Test
Train
Test
Train
Test
GCRN
6001.14
72.57=0.72
74.71=0.17
72.29+0.47
75.69=0.07
67.26=0.22
BvolveGCN 62
78.82&1.40
69.00s0.53
79.47&1.68
62.70+1.14
81.07a4.10
60.13a0.89
DySAT
75
84.71=0.80
70.24
89. 89.77=0.32
64.01#0.19
94,02+1.29
62.1920.39
IRM
85.20=0.07
40=0.09
89 08:0.22
63,97+0.37
95.02:0.09
22.66=0.33
V-REx
44
84.77=0.84
70.44+1.08
89.81+0121
63,99+0.21
94.06+1.30
+0.21+0
GROuDDRO 74
84.7840.85
70.30+1.25
89 9010..1
64.0510.21
94.0811.33
62.13
DIDA
p4
87.92=0.92
$5.20+0.84
91.22=0.59
82.89+0.23
92.7242.16
72.59+3.31
EAGLE
92.97=0.88
88.32+0.61
94.52+0.42
87,29+0.71
94.11+1.03
82.30a0.75
Though DIDA 14] also shows upward trend, its growth rate is more gradual. This indicates that, as DIDA 94 is incapable of modeling the environments, is difficult to perceive changes in the underlying environments caused by different de- thus cannot achieve satisfying generalization performance. comparison, our EAGLE can exploit more reliable invariant patterns, thus performing high-quality invariant learning and efficient causal interventions, and achieving better generalization ability. In addition, we also observe a positive correlation between Acc and the AUC, indicating the improvements is attributed the accurate recognition of the invariant patterns by I(-). Additional results are in Appendix D.7
Ablation Study
In this section, we conduct ablation studies to analyze the effectiveness of three main mechanisms:
EAGLE (w/o EI). We remove the Environment Instantiation mechanism in Section 3.2 and carrying out causal interventions in Eq. (13) with only observed environment samples.
EAGLE (w/o IPR). We remove the Invariant Pattern Recognition mechanism in Section 3.3 and determining the spatio-temporal invariant patterns P! by randomly generating ó, for each node.
EAGLE (w/o Interv). We remove the spatio-temporal causal Intervention mechanism in Section 3.4 and directly optimize the model by Eq. (16) without the second Crisk term.
Results. Results are demonstrated in Figure 4 Overall, EAGLE consistently outperforms the other three variants on datasets. The ablation studies provide insights into the effectiveness of the proposed mechanisms and demonstrate their importance in achieving better performance for OOD generalization on dynamic graphs.
90
90
ACC (56) (for bur graph)
B/7 IACC
75
AUC (%) (for (ffor line graph)
80
85
70
70
AUC (%)
80-
65
75
60
50
70
-55
COLLAB
Yelp
ACT
COLLAB (p 0.6)
DIDA (weo OOD)
EAGLE (w/o OOD) EAGLE (w/ 00D)
2022
EAGLE
EAGLE (w/ (PR)
0OD)
EAGLE (wo El)
EAGLE (w/ Inters)
Figure 3: Effects of invariant pattern recognition.
Figure 4: Results of ablation study.
4.4 Visualization
We visualize snapshots in COLLAB using NetworkX 227 as shown in Figure where colors reflect latent environments, numbers denote edge weights, solid lines implicate spatio-temporal invariant patterns dependencies, and dashed lines implicate variant patterns dependencies. EAGLE F. can gradually exploit the optimal invariant patterns and strengthen reliance, making generalized predictions.

---

0.29
0,12
OO X
0.31
Overview (COLLAB)
Snapshot (t =
Snapshot (t 4)
Snapshot (1
Figure 5:
Visualization of snapshots in COLLAB.
5 Related Work
Dynamic Graph Learning. Extensive researches 70
351 address the challenges of dynamic graph learning. Dynamic graph neural networks (DGNNs) are intrinsically utilized to model both spatial and temporal patterns 88
38
90,
85
&O 21 by combining vanilla GNNs and sequential-baser models [58] 31 28 However, most existing works fail to generalize under distribution shifts. DIDA (94] is the sole prior work that tackles distribution shifts on dynamic graphs, but it neglects model the complex environments, which is crucial in identifying invariant patterns.
76
84
73
62
75
Dittr--Dittiibttion Generalization. Most machine learning methods are built on the L.I.D hypoth- esis, which can hardly be satisfied in real-world scenarios [77 [1 B]
(OOD)
generalization has been extensively studied in both academia and industry areas 77 92 30 and
we mainly focus on graphs. Most works concentrate on static graphs for node-level or graph-level
tasks [98 18
49
86
52
12 87 supporting by invariant learning method [4 46
95 with disen-
tangled learning 5
5
and causal inference theories 65
66 64]. However, there lack of further
research on dynamic graphs with more complicated shift patterns caused by spatio-temporal varying latent environments, which is our main concern.
Invariant Learning. Invariant learning aims exploit the fewer variant patterns that lead to informative and discriminative representations for stable prediction [14 46 95
Supporting by disentangled learning theories and causal learning theories, invariant learning tackles the OOD generalization problem from more theoretical perspective, revealing promising power. Disentangle- based methods [5] (55) learn representations by separating semantic factors of variations in data, making it easier to distinguish invariant factors and establish reliable correlations. Causal- based methods 222 3 72
60 utilize Structural Causal Model (SCM) 64 to filter out spurious correlations by intervention or counterfactual with do-calculus [65 (66) and strengthen the invariant causal patterns. However, the invariant learning method of node-level tasks on dynamic graphs is underexplored, mainly due to its complexity in analyzing both spatial and temporal invariant patterns.
6 Conclusion
In this paper, we propose a novel framework EAGLE for out-of-distribution (OOD) generalization on dynamic graphs by modeling complex dynamic environments for the first time and further exploiting spatio-temporal invariant patterns. EAGLE first models environment by an environment-awaa DGNN, and then diversifies the observed environment samples with the environment instantiation mechanism, and finally learns OOD generalized spatio-temporal invariant patterns by the invariant pattern recog- nition mechanism and performs fine-grained causal interventions node-wisely, Experiment results on both real-world and synthetic datasets demonstrate that EAGLE greatly outperforms existing methods under distribution shifts. One limitation is that we mainly consider the node-level tasks, and leave extending our method to the graph-level OOD generalization for future explorations.
Acknowledgements
The corresponding author is Qingyun Sun. The authors of this paper are supported by the National Natural Science Foundation of China through grants No.62225202, No. 62302023, and No.62206 49, We owe sincere thanks to all authors for their valuable efforts and contributions. We also acknowledge the support of MindSpore, CANN (Compute Architecture for Neural Networks) and Ascend Al Processor used for this research.
10

---

References
[1] Abien Fred Agarap. Deep learning using rectified linear units (ReLU). arXiv preprint arXiv: 1803.08375
2018.
[2] Kartik Ahuja, Karthikeyan Shanmugam, Kush R. Varshney, and Amit Dhurandhar. Invariant risk mini- mization games. In Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 145- PMLR, 2020.
[3] Martín Arjovsky. Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv: 0e0./99770.999 02893, 2019.
[4] Gowtham Atluri, Anuj Karpatne, and Vipin Kumar. Spatio-temporal data mining: A survey of problems and methods. ACM Computing Surveys, 51(4):1-41, 2018.
[5] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 3588)1798-18888 2013.
[6] Tanya Y Berger-Wool Wolf and Jared Saia. A framework for analysis of dynamic social networks. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 523 528, 2006.
[7] Andrew P Bradley. The use of the area under the ROC curve in the evaluation of machine learning algorithms. Pattern Recognition, 30(7):1 145-11559 1997.
[8] Peter Bühlmann. Invariance, causality and robustness. arXiv preprint arXiv:1812.08233, 2018.
[9] Remi Cadene, Corentin Dancette, Matthieu Cord, Devi Parikh, et al. Rubi: Reducing unimodal biases for visual question answering. Advances in Neural Information Processing Systems, 32, 2019.
[10] Lei Cai, Zhengzhang Chen, Chen Luo, Jiaping Gui, Jingchao Ni, Ding Li, and Haifeng Chen. Structural temporal graph neural networks for anomaly detection dynamic graphs. In Proceedings of the 30th ACM International Conference on Information and Knowledge Management, pages 3747-3756, 2021.
[11] Shiyu Chang, Yang Zhang, Mo Yu, and Tommi S. Jaakkola. Invariant rationalization. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1448-145, PMLR, 2020.
[12] Yongqiang Chen, Yonggang Zhang. Yatao Bian, Han Yang, MA Kaili, Binghui Xie, Tongliang Liu, Bo Han, and James Cheng. Learning causally invariant representations for ofitt--distributiin generalization on graphs. Advances in Neural Information Processing Systems, 35:22131-22144 2022.
[13] Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçchre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, pages 1724-1734. ACI., 2014.
[14] Elliot Creager, Jörn-Henris Jacobsen, and Richard S. Zemel. Environment inference for invariant lcarning. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings Machine Learning Research, pages 2189 2200. PMLR, 2021.
[15] Dengxin Dai and Luc Van Gool. Dark model adaptation: Semantic image segmentation from daytime to nighttime. In International Conference on Intelligent Transportation Systems, pages 3819-3824. IEEE, 2018
[16] Pieter-Tjerk De Boer, Dirk P Kroese, Shie Mannor, and Reuven Y Rubinstein. tutorial on the cross- entropy method. Annals of Operations Research, 134:19-67, 2005.
[17] Mucong Ding, Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Micah Goldblum, David Wipf,, Furong Huang, and Tom Goldstein. closer look at distribution shifts and out-of-distribution generalization on graphs. NewrlPS 2021 Workshop on Distribution Shifts: Connecting Methods and Applications, 2021.
[18] Shaohua Fan, Xiao Wang, Chuan Shi, Peng Cui, and Bai Wang. Generalizing graph neural networks on duitt--diitriuution graphs. arXiv preprint arXiv:2111.10657, 2021.
[19] Marco Federici, Ryota Tomioka. and Patrick Forré. An information- theoretic approach to distribution shifts. Advances in Neural Information Processing Systems, 34:17628- 17611-176711,, 2021.
[20] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint 1903.0::90000223 2019.

---

[21] Xingcheng Fu, Yuecen Wei, Qingyun Sun, Haonan Yuan, Jia Wu, Hao Peng, and Jianxin Li. Hyperbolic geometric graph representation learning for hierarchy-imbalare node classification. In Proceedings of the ACM Web Conference, pages 460-468, 2023.
[22] Christophitt Gagnon-Audet, Kartik Ahuja, Mohammad- Darvishi- Bayyii,,,Baaaai,,,,, Guillaume Dumas, and Irina Rish. WOODS: Benchmarks for out-of-distributiin generalization time series tasks, arXiv preprint arXiv:2233.09978 2022.
[23] Walter R Gilks, Sylvia Richardson, and David Spiegelhalter. Markov chain Monte Carlo in practice. CRC press, 1995.
[24] Mingming Gong, Kun Zhang, Tongliang I. Liu, Dacheng Tao, Clark Glymour, and Bernhard Schölkopf. Domain adaptation with conditional transferable components. In Proceedings of the 33nd International Conference Machine Learning, volume 48 of JMLR Workshop and Conference Proceedings, pages 2839-2848. JMg.. 2016.
[25] Derek Greene, Donal Doyle, and Padraig Cunningham. Tracking the evolution communities in dynamic social networks. In 2010 International Conference on Advances in Social Networks Analysis and Mining, pages 176-183. IEEE, 2010.
[26] Shurui Gui, Xiner Li, Limei Wang, and Shuiwang Ji. GOOD: A graph out-of outoo--distribution benchmark. Advancey in Neural Information Processing Systems, 35:2059 2073, 2022.
[27] Aric Hagberg, Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National (TA..T. Los Alamos, NM (United States), 2008.
[28] Ehsan Hajiramezanali, Arman Hasanzadeh, Krishna Narayanan, Nick Duffield, Mingyuan Zhou, and Xiaoning Qian. Variational graph recurrent neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[29] John A Hartigan and Manchek Wong. Algorithm as 136; A K-means clustering algorithm. Journal of the Royal Statistical Society. Series C (Applied Statistics), 28(1): 1979.
[30] Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, et al. The many faces of robustness: A critical analysis of distr--iiittibution generalization. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8340-8349,, 2021.
[31] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 175 1997.
[32] Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogenenus graph transformer. In Proceedings of the Web Conference, pages 2704-2710, 2020.
[33] Huawei. Mindspore.
cn/ 2020.
[34] Johan Ludwig William Valdemar Jensen. les fonctions convexes et les inégalités entre les valeurs moyennes. Acta Mathematica, 30(1):175-193, 1906.
[35] Cheng Ji. Tao Zhao, Qingyun Sun, Xingcheng Fu, and Jianxin Li. Higher-order memory guided temporal random walk for dynamic heterogeneous network embedding. Pattern Recognition, page 109766, 2023.
[36] Yuanfeng Ji, Lu Zhang, Jiaxiang Wu, Bingzhe Wu, Long-Kai Huang, Tingyang Xu, Yu Rong. Lanqing Li, Jie Ren, Ding Xue, et al. DrugOOD: Out-of-distribution (OOD) dataset curator and benchmark for ai-aided drug discovery-a focus on affinity prediction problems with noise annotations. arXiv preprint arXiv:2201.0900 2022.
[37] James M Joyce. Kullback-leibler divergence. In International Encyclopediaa of Statistical Science, pages 720-722 Springer, 2011.
[38] Amol Kapoor, Xue Ben, Luyang Liu, Bryan Perozzi, Matt Barnes, Martin Blais, and Shawn O' O'Banion. Examining covid- 19 forecasting using spatio-temporal graph neural networks. arXiv preprint urXiv:2007.03113, 2020.
[39] Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: A survey. The Journal of Machine Learning Research, 21(1):2648 -2200 2020.
12

---

[40] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, 2015.
[41] Thomas N Kipf and Max Welling. Semi Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609,029900 2016.
[42] Thomas N Kipf and Max Welling. Variational graph auto-cneoders, arXiv preprint 10100006 2016.
[43] Alexander Kraskov, Harald Stögbauer, and Peter Grassberger. Estimating mutual information. Physical Review E, 69(6):066138, 2004.
[44] David Krueger, Ethan Caballero, Morn-Herrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Rémi Le Priol, and Aaron C. Courville. Out-of-distributie generalization via risk extrapolation (rex). In Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5815-5826. PMLR, 2021.
[45] Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1269-1278. ACM, 2019.
[46] Bo Li, Yezhen Wang, Shanghang Zhang, Dongsheng Li, Kurt Keutzer, Trevor Darrell, and Han Zhao. Learning invariant representations and risks for semi-supervised domain adaptation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 104-1113, 2021.
[47] Fuxian Li. Jie Feng, Huan Yan, Guangyin Jin, Fan Yang, Funing Sun. Depeng Jin, and Yong Li. Dynamic graph convolutional recurrent network for traffic prediction: Benchmark and solution. ACM Transactions on Knowledge Discovery from Data, 17(1):1-21, 2023.
[48] Haoyang Li, Xin Wang, Ziwei Zhang, Zehuan Yuan, Hang Li, and Wenwu Zhu. Disentangled contrastive learning on graphs. Advances in Neural Information Processing Systems, 34:21872-21888 2021.
[49] Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu Zhu. OOD-GNN: Out-of-distribution generalized graph neural network. IEEE Transactions on Knowledge and Data Engineering, 2022.
[50] Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu Zhu. Out-of-distrbbtton generalization on graphs: A survey. arXiv preprint arXiv:2202.0799: 2022.
[51] Haoyang Li, Ziwei Zhang, Xin Wang, and Wenwu Zhu. Disentangled graph contrastive learning with independence promotion. IEEE Transactions Knowledge and Data Engineering, 2022.
[52] Haoyang Li. Ziwei Zhang, Xin Wang, and Wenwu Zhu. Learning invariant graph representations for dutto--ditti generalization. In Advances in Neural Information Processing Systems, 2022.
[53] Jianxin Li, Qingyun Sun, Hao Peng, Beining Yang. Jia Wu, and S Yu Phillp. Adaptive subgraph neural network with reinforeed critical structure mining. IEEE Transactions on Pottern Analysis and Machine Intelligence, 2023.
[54] Jianxin Li, Shuai Zhang, Hui Xiong, and Haoyi Zhou. Autost: Towards the universal modeling of spatio-temporal sequences. In Advances in Neural Information Processing Systems, volume 35, pages 20498-20510, 2022.
[55] Francesco Locatello, Stefan Bauer, Mario Lucic, Gunnar Rätsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem. Challenging common assumptions in the unsupervised learning of disentangled representations. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4114-4124. PMIR, 2019.
[56] Jianxin Ma, Peng Cui, Kun Kuang, Xin Wang. and Wenwu Zhu. Disentangled graph convolutional networks. Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4212-4221 PMLR, 2019.
[57] Franco Manessi, Alessandro Rozza, and Mario Manzo. Dynamic graph convolutional networks. Patter Recognition, 97:107000, 2020.
[58] Larry R Medsker and LC Jain. Recurrent neural networks. Design and Applications, 5:64-67, 6644667,55 2001.
[59] Tomás Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. In 1st International Conference Learning Representations, 2013.
13

---

[60] Jovana Mitrovic, Brian McWilliams, Jacob C. Walker, Lars Holger Buesing, and Charles Blundell. Representation learning via invariant causal mechanisms, In 9th International Conference Learning Representations. OpenReview.net, 2021.
[61] Diego C. Nascimento, Bruno A Pimentel, Renata MCR Souza, Lilia Costa, Sandro Gonçalves, and Francisco Louzada. Dynamic graph in symbolic data framework: An account of the causal relation using covid- 19 reports and some reflections on the financial world. Chaus, Solitons Fractals, 153:1 14400. 2021.
[62] Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao B. Schardl, and Charles E. Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. The Thirty-Fourhh AAAI Conference on Artificial Intelligence, pages 5363-5370. AAAI Press, 2020.
[63] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 32, 2019.
[64] Pearl and Judea. Causal inference in statistics: An overview. Statistics Surveys, 1-96-146, 2009.
[65] Judea Pearl. Causal inference. Causality: Objectives and Assessment, pages 39-58, 2010.
[66] Judea Pearl and Dana Mackenzie. The Book of Why: the New Science of Cause and Ffffett. Basic books, 2018.
[67] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. The MIT Press, 2017.
[68] Anton V Proskurnikov and Roberto Tempo A tutorial modeling and analysis of dynamic social networks. part i. Annual Reviews in Control, 43:65 79, 2017.
[69] Stephen Ranshous, Shitian Shen. Danai Koutra, Steve Harenberg. Christos Faloutsos. and Nagiza F Sama- tova. Anomaly detection in dynamic networks: survey. Wiley Interdisciplinary Reviews: Computational Statistics, 7(3):233-247, 2015.
[70] John F Roddick and Myra Spiliopoulou. A bibliography of temporal, spatial and spatio-temporal data mining rescarch. ACM SIGKDD Explorations Newsletter, 1(1):34-38, 1999.
[71] Matco Mojas-Carulla, Berhhard Schölkopf, Richard Turner, and Jonas Peters. Invariant models for causal transfer learning. The Journal of Machine Learning Research, 1909):300-1132,, 2018.
[72] Elan Rosenfeld, Pradeep Kumar Ravikumar, and Andrej Risteski. The risks of invariant risk minimization. In 9th International Conference on Learning Representations. OpenReview.net, 2021.
[73] Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca. Davide Eynard, Federico Monti, and Michael Bron- stein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint 2ttv:22006106633 2020.
[74] Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint 19XXv::911.087750 2019.
[75] Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural representation learning on dynamic graphs via self-attention networks. In Proceedings of the 13th International Conference on Web Search and Aata Mining, pages 519-527, 2020.
[76] Youngjoo Sco, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence mod- eling with graph convolutional recurrent networks. In Neural Information Processing: 25th International Conference, ICONIP 2018, Siem Reap, Cambodia, December 13-16, 2018, Proceedings, Part I 25, pages 362-373. Springer, 2018
(77] Zheyan Shen, Jiashuo Liu, Yue Hc, Xingxuan Zhang, Renzhe Xu, Han Yu, and Peng Cui. Towards out-o--distribution generalization: A survey, arXiv preprint arXiv:2108. 13624, 2021.
[78] Qingyun Sun, Jianxin Li, Hao Peng. Jia Wu, Xingcheng Fu, Cheng Ji, and Philip S. Yu. Graph structure learning with variational information bottleneck. In -hirtt-Sixth AAAI Conference on Artificial Intelligence, pages
AAAI Press, 2022.
[79] Qingyun Sun, Jianxin Li, Hao Peng. Jia Wu, Yuanxing Ning, Philip S Yu, and Lifang He. SUGAR: Subgraph neural network with reinforcement pooling and self-supervised mutual information mechanism. In Proceedings of the ACM Web Conference, pages 2081-2091, 2021.
14

---

[80] Qingyun Sun, Jianxin Li, Haonan Yuan, Xingcheng Fu, Hao Peng. Cheng Ji. Qian Li, and Philip S Yu. Position-aware structure learning for graph topology-imbalance by relieving under-reaching and over- squashing. In Proceedings of the 31 ACM International Conference on Information and Knowledge Management, pages 14577187, 2022.
[81] Jie Tang. Sen Wu, Jimeng Sun, and Hang Su. Cross-domain collaboration recommendation. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1285-1293, 2012.
[82] Vladimir N Vapnik. An overview of statistical learning theory. IEEE transactions on neural networks. 10(5):988-99) 999, 1999.
[83] Xin Wang, Hong Chen, Yuwei Zhou, Jianxin Ma, and Wenwu Zhu. Disentangled representation learning for recommendation. IEEE Trans. Pattern Anal. Mach. Intell., 45(1):408 424, 2023.
[84] Yanbang Wang, Yen- Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learn- ing in temporal networks via causal anonymous walks. In 9th International Conference on Learning Representations. OpenReview.net, 2021.
[85] Yanbang Wang. Pan Li, Chongyang Bai, and Jure Leskovec. Tedic: Neural modeling of behavioral patterns in dynamic social interaction networks. In Proceedings of the ACM Web Conference, pages 693-705, 1021.
[86] Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invari- ance perspective. In The Tenth International Conference on Learning Representations. OpenReview.net, 2022.
[87] Yingxin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant ratio- nales for graph neural networks. In The Tenth International Conference on Learning Representations. OpenReview.net, 2022.
[88] Menglin Yang. Min Zhou, Marcus Kalander, Zengfeng Huang, and Irwin King. Discrete- time temporal network embedding via implicit hierarchical learning in hyperbolic space. In The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1975-1985, ACM, 2021.
[89] Yiding Yang. Zunlei Feng, Mingli Song, and Xinchao Wang. Factorizable graph convolutional networks. Advances in Neural Information Processing Systems, 33:20286 20296, 2020.
[90] Jiaxuan You, Yichen Wang, Aditya Pal, Pong Eksombatchai, Chuck Rosenberg, and Jure Leskovec. Hierarchical temporal convolutional networks for dynamic recommender systems. In Proceedings of the ACM Web Conference, pages 2236-2246. ACM, 2019.
[91] Junchi Yu. Jian Liang, and Ran He. Mind the label shift of augmentation- graph OOD generalization. In IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 11620-11630. IEEE, 2023.
[92] Lingxiao Yuan, Harold S Park, and Emma Lejeune. Towards out of distribution generalization for problems in mechanics. Computer Methods in Applied Mechanics and Engineering, 400:115569, 2022.
[93] Shilei Zhang, Toyotaro Suzumura, and Li Zhang. Dyngraphtrans: Dynamic graph embedding via modified universal transformer networks for financial transaction data. In 2021 IEEE International Conference on Smart Data Services, pages 184-191. IEEE, 2021.
[94] Zeyang Zhang. Xin Wang, Ziwei Zhang, Haoyang Li, Zhou Qin, and Wenwu Zhu. Dynamic graph neural networks under spatio-temporal distribution shift. In Advances in Neural Information Processing Systems, 2022.
[95] Han Zhao, Remi Tachet des Combes, Kun Zhang, and Geoffrey J. Gordon. On learning invariant representations for domain adaptation. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 7523-7532. PMLR, 2019.
[96] Zhengyang Zhou, Yang Wang, Xike Xie, Lianliang Chea, and Hengchang Liu. RiskOracle: A minute-level citywide traffic accident forecasting framework. In The Thirty-Fourlh AAAI Conference on Artificial Intelligence, pages 1265. AAAI Press, 2020.
[97] Zhengyang Zhou, Yang Wang. Xike Xie, Lianliang Chen, and Chaochao Zhu. Foresee urban sparse traffic accidents: A spatiotemporal multi-granulann perspective. IEEE Transactions on Knowledge and Data Engineering, 34(8):3786-379, 2020.
[98] Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi. rhift- GNNs: Overcoming the limitations of localized graph training data, Advances in Neural Information Processing Systems, 34:27965- 27977, 2021.
15

---

A Notations
Notations
Descriptions
DG (9)
Dynamic graph (a set of T' discrete graph snapshots)
g (V,8)
Graph with the node set V and edge set
G (VI (E)
Graph snapshot at time
X A'
Node features matrix and adjacency matrix graph at time t Node features and edge weights of (u, v) under ex Graph trajectory, labels and their corresponding random variables Latent environments and their support
x At (..)).c
g Y G Y
e, Cj E
Node representations under eg, time and overall time slices Observed environment sample with its label
2, y
Dimension for x and z respectively Number underlying environments (number of convolution channel) Model, encoder, and the link predictor The loss function
K f(-), w(-),. .(-) E(-)
96. Pur ((,,I()
The prior distribution and variational distribution of environments Invariant pattern recognition function and its implementation
P.. PVV (U),), PV (v)
Summary of spatio-temport invariant/variant patterns for each node Summary node representations, and their variants under P and PV Observed and generated environments sample libraries Intervention samples from Sob U Uge and their summary for node do-caculus for causal interventions Task loss, the invariance loss and the ECVAE loss Hyperparameters for loss trade-off
it 2 Z
Sob. Sge
8, St do(-)
Leasks Celsks LEOVAE ar 3
Algorithm and Complexity Analysis
Algorithm 1: Overall training process of EAGLE.
Input: Dynamic graph DG ((g)T 1) with labels Y of link occurrence; Number of training epochs E; Number of intervention times S; Hyperparameters a and B. Output: Optimized model fø: Predicted label y of link occurrence at time T
Initialize parameters randomly;
for i 1,2, F do
// Environments Modeling and Inferring
Obtain representations for each node at each time with the support of e, as 2 + Eq. (6
Establish the observed environment samples library Sob + Eq. (7):
Infer the distribution (c) with LECVAB +- Eq. ( and generate samples library Sgei
// Environments Extrapolating Learn the invariance threshold 8, +- Eq. 110 by function I(.) 4 Eq.
9);
Recognize the invariant/variant patterns for each node, as P! (v). PV (v) + Eq.
Calculate task loss depending the invariant patterns, Leask Eq. 13
// Environments Generalizing
for j = 1, 2, ... ,5 do
Sample items from Sab U Sgo and perform intervention for each node, as Eq. 15)p
11
Calculate intervention loss, as Lrisk +- Eq. [4]:
12
end
// Optimize
13
Calculate the overall loss, as C +- Eq. (16): Update model parameters by minimizing L.
14
15 end
The overall training process of our EAGLE is shown in Algorithm
16

---

Computational Complexity Analysis. We analyze the computational complexity of each part in EAGLE as follows. Denote [V] and [8] the total number of nodes and edges each graph snapshot.
In Section 3.1] operations of the EAConv layer in EA-DGNN can be parallelized across all nodes, which is highly efficient. Thus, the computation complexity of EA-DGNN is:
0 1
R V
Σ n d + (ddl)))))
(B.1)
where d(()) denotes the dimension of the 1-th layer. As L is a small number, and d is a constant, the Eq. B.I can be rewritten as O([E)d + [V]d)), where d is the universal notation of all d
In Section 3.2 the computation complexity of the ECVAE is a compound of the encoder and decoder, with the same computation complexity as ((z)['d)) where |z| the number of the observed environment samples, L' is the number of layers in the encoder and decoder. Also, as L' is small number, we omit it for brevity. Thus, the computation complexity of ECVAE is ([z]d).
In Section 3.3 we recognize the invariant/varian patterns for all nodes by the function I(-) in parallel, with the computation complexity OK log [V]).
In Section 3.4, we perform sampling and replacing as an implementation of causal interventions. Denote [ p the number of edges to predict and [S] the size of the intervention set, which is usually set as a small constant. The spatio-temporal causal intervention mechanism owns a computation complexity compounding of sampling and replacing as O([8 + ((EE,)(S)d) in training, and no extra computation complexity in the inference stage.
Therefore, the overall computation complexity of EAGLE is:
O(E)d + (V]d) + ((z]d) - OKK log MI) + O(IS)d) + ((E))())d)
(B.2)
In summary, EAGLE has linear computation complexity with respect to the number of nodes and edges, which is on par with DIDA (94] and other existing dynamic GNNs. We believe that the computational complexity bottleneck of EAGLE lies in the spatio-temporal causal intervention mechanism. We further analyze the intervention efficiency in Appendix [D.5
Space Complexity Analysis. We analyze the space complexity of each part in EAGLE as follows. Denote | and | as the number of nodes and edges, respectively, K as the number of environments, T as the number of time slices, L the number of layers in EA-DGNN, L' as the number of layers in ECVAE, as the dimension of input node features, d' = K'd as the hidden dimension EACony layers in EA-DGNN, d" the hidden dimension of the encoder and decoder networks layer of ECVAE, Evey Var(z,)) as the variance of environment-avve aware representations.
Here we provide rough analysis of EAGLE'S space complexity. Note that, as the space complexity analysis of deep learning models complicated, we omit some less important terms, such as intermediate activations, elc.
storing the dynamic graph: O(KT(M))+ (E)))
storing the node input features: ((V)KTd).
the EAConv layer: (
the encoder and decoder networks of ECVAE: ((T'd))
storing generated environment samples (the number set to be the same with the observed ones):
O(IV KTd").
storing the states for function I(.,:): O(K Evev Var(z")).
Then the overall space complexity of EAGLE can be roughly calculated as:
о(Kт(M) + (E)) O(V)KTd)) O(Ld?) + O(L'd") + O(V) + OOK Σ
Var(z
VEV
(B.3)
However, it is hard to intuitively draw conclusions about memory requirements from the space complexity analysis. Based on our experiments experience, EAGLE can be trained and tested under the hardware configurations (including memory requirements) listed Appendix E.3 which is on par with the related works" requirements.
17

---

C Proofs
C.1 Proof of Proposition
Proposition 1. Given observed environment samples from the dynamic graph g²: denoted as
K T z = -UUEE (2),)) ((M)KKXT) vEVA=1t=l
def
Sob
(C.1)
with their corresponding one-hot multi-labels y, the environment variable e is drawn from the prior distribution (e. y) across 7 time slices, and z is generated from the distribution p= y, e). Maximizing the conditional log-likelihood log (z [z y) leads to optimal ECVAE by minimizing:
|
LECVAE = KL(ga(e 2, y,y [e|y)
y)]
log Pw (z y, e
(C.2)
where KLL-II-] is the Kullback-Leibler (KL) divergence 37
|z] is the number of observed environ-
ment samples, (1) is the i-th sampling by the reparameterization trick.
Proof. The distribution distance between (o(c KL-divergence:
y. and (c y, can be calculated by the
g
z, z,y)
(T (el (ly))l 2,y)] = ao(e 2. log
dØ
Pe (e
y)
To 2, y. Pm
y (y) dø
9o(e 12.)) log
(,,
/ go(el 2. log y, dø +
g0(e 2, log y) dø
logp_(1ly)
/ 900cc y. (og - 901c 2. z, do
logg (z 1y)+ + / cole 2, log pu y, e) y) dØ
(o z.
logn (x1y) y) + flole ( z, log y)] logg (z yy Eyslelz.y)| log (o z, y, logp (e, |y]]
(C.3)
Thus the conditional log-likelihood log y) can be rewritten as: log (2 y) = [L z, y)y)lp y) + (el log go z. + log Pw (c. z y)]
(C.4)
Since this KL-divergence is non-negative, we then provide an Evidence Lower Bound (ELBO) for log (y z):
(2 y) 2 [ - log (e z,y) + lo z yy)
= =E Eysle/ - log (e y,y) + (w y)] + (oggu [y,e]] (C.5)
= (T z.y) y)] + E ( (z y, e)].
We can maximize (z y) by maximizing the ELBO, or minimizing:
LECVAE ELBOO = (g z. y.y)lp y)] (eky c)..
(C.6)
While the second term in LECVAE the maximum likelihood estimation, which is infeasible to calculate directly under the expectation of the latent enviromment variable e ~ Po z,y) across T time slices. Inspired by Markov Chain Monte Carlo (MCMC) sampling [23). it can be estimated as:
[x]
LECVAE KL[gs(e| | y2 Iy)l
log pa (z e()).
(C.7)
18

---

In implementations, we assume (e(e y) and (e y) follow the multivariate normal distribution Mpp o) parameterized by l and o, so that the KL-divergence can be easily calculated. In order to optimize the ECVAE by back- pnok-propagation, we utilize a reparameterization trick: e(*) f (z. y, where e NN I). Here (.)r))))) is some vector-valued functions parameterized by d.
C.2 Proof of Proposition 2
Proposition 2 (A Solution for I+)).. Denote 2.¹² = 1 /2,,c where <',, = U "
Let Var (2 E R represents the variance of K environment-awe representations. The Boolean function I(-) a solution for (-) with the following state update equation:
T(i 1,5) v T(i 1,j - (2r 1)), j 1 Var(2,)) - 1] I[i - 1,j),
((i,))
(C.8)
otherwise
I(t, () indicates whether it is feasible to select from the first i elements in Var(z"") so that their sum Traversing j in reverse order from Σ Var(22))/2 until satisfying [[(Kj) is True, we reach:
8, = Σ Var(z.)) 2j,
(C.9)
= -(ox
1
8, }
(v) =
Var(z")) -
K Var(z,))
PV (c)
(C.10)
2 S
where 6, is the optimal spatio-temporal invariance threshold of node e.
Proof. In order to prove the boolean function II() is solution for I-()) in Assumption [ the problem T(.) solves should satisfies: (a) Optimal substructure; (b) Non-aftereffect property; (c) Overlapping sub-problems.
Next, we prove the above three conditions are valid.
(a) Optimal substructure. It said that the problem has the optimal substructure property when the optimal solution of the problem covers the optimal solutions of its subproblems. Now we prove the optimal solution of determining the spatio-temporal invariant patterns P (v) for node is constructed from the optimal solutions of the sub- -eob-problems with the bottom-up approach by using the optimal substructure property of the problem.
As T(i, j) indicates whether it is feasible to select some elements from the first i elements in Var(z.) so that their sum is Σ Var(z5 (z!') means the sum of elements in Var(z))) ), the target of the problem to find & that denotes the optimal threshold for invariance of node v. We reduce this problem by dividing Var(z!') into two subsets Var(z"") and Var(z,) >v, where d, represents the value when the difference between the sum of two subsets is the smallest, i.e.,
8y = min Var(z.)) -
-2)) where I(K,j)) == True.
(C.11)
Let j) and Iv (i represent whether it is feasible to select some elements from the first i elements Var(z)'), I and Var(z))) respectively, so that their sum is j. Suppose the sum of Var(z"") and Var (zz)), y are ((Vr((z)))) and ((ar ), we have:
Σ(Var(z)))) + [(Var(z))))) = Σ Var(z))).
(C.12)
Then, the target of the original problem is transformed into finding an optimal solution for and j. satisfying:
[r((i)]) True, Iv(K - (.Va(r(22)))) - = True,
(C.13)
S.l. min Σ ((Var(2,)) - -- (Vaa((2)))
Σ (Var(2)))) (1) -)))
(C.14)
According to the definition of T(i,j), we can draw a conclusion the T (i, and (i, j) both are the subproblems of the original problem, which similarly target at figuring out whether it is feasible to select some elements from the first i clements that satisfy their sum is j. So, function (i,jj) and
19

---

[i,j) is the same with (( in Eq. (C.8) Assuming that when the difference in the subsets is maximized, (i) and (i.j) return Jr and jv, respectively, that satisfy:
1 (i, = True,
(C.15)
lIv[ i,jv) True.
We have:
[t. True, [(Var(z)))) j1 = ō1, [[Var(2)))) )v) - jv = =v, Tv(K - ((Var(2))))) - ji) == True.
(C.
As Ty (i, and ly (K-K, -i, -, ((Var(2()))) jr) are both the optimal solutions, reach:
16, - dvl = Σ E(Var(2?")) jr - Σ(Var(z;)v) -iv) s 8,.
(C.17)
The optimal substructure property is proven.
(b) Non-aftereffect property. This property implies that once the state of a certain stage is determined by T(.), it is not affected by future decision-making. In other words, the subsequent process will not affect the previous state, but only be related to the current state. Eq.
(C.8) implies that, when
j 2 Var(z;)) 1]. the state is decided by previous state 1(i - j. or 1(í - 1, accordingly, when j < Var(z"") state transition processes are based on historical states and executed in a one-way transition mode, meeting the requirements of the non-aftereffect property. Generally speaking, the -on-aftereffect property is a relaxation condition, that is, as long as the properties of the optimal substructure property are satisfied, the -f-eftfefffect property will be basically satisfied.
(2r(z"") 1]): 1]. the state is solely decided by previous state 1(i L,j). All
(c) Overlapping sub-problems. T(-) solve the problem from top to bottom in a recursive way, each sub-problem is not always new problem, but a large number of repeated sub-problems, that is, when different decision sequences reach a certain stage, they will generate duplicate problems. When figuring out I(-), we consider two situations:
Not select the i-th element Var(z)"), Le., I(i,j) I(i-),
Select the i-th element Var(z))) ie.. [(i.j) = T(i 1,, - Var(z [i 1]).
As we can observe, we need the solution of the sub-problem 1, and T(i - 1, ( 1)) when figuring out j), which are already calculated by 1, So we can prove that the problem I(-) solved has overlapping sub-probil hobbproblems.
We then have proven the function I(.) a solution for the function (+) in Assumption from which we can obtain the optimal apatio-tempont invariance threshold 8, of node v. Then the spatio-temporal invariant/variant patterns for node can be exploited by Eq. (C.10). and their unions constitute the overall P! and P!!. We conclude the proof for Proposition
C.3 Proof of Proposition
Proposition 3 (Achievable Assumption). Minimizing Eq. 12 can encourage the model to satisfy
the Invariance Property and Sufficient Condition in Assumption 1
Proof. We first propose the following lemma to rewrite the Sufficient Condition and the Invariance Property in Assumption T Jsing the information theory (3).
Lemma (Mutual Information Equivalence). The Invariance Property and Sufficient Condition in Assumption can be equivalently represented with the Mutual Information I (:::):
(a) Invariance Property:
p(YT PL. e) p(T P!) I(YT;e) P!) O:
(b) Sufficient Condition: YT ll L. p! + I(YT: P!) is maximized.
Proof. We prove Lemma by respectively proving the above two conditions are valid.
20

---

(a) Invariance Property. According to the definition of the Mutual Information, we can easily get the following equation:
37 Thus we have proved the equivalence in IYY":e :e P!) - KL |pl (Y
e, Pc) 11 p [P))] O,
(C.18)
where KL is the Kullback-Leible (KL) divergence Invariance Property.
(b) Sufficient Condition. We demonstrate sufficiency and necessity through the following two steps. First, we prove that for Y Pdd and e satisfying Y (Z) ) +e would also satisfy Pdd arg max P! Pd). We perform proving by contradiction. Suppose P + arg maxp! I(Y"; ; and there exists Pdd = arg maxp! where P * Pdd We can always find a mapping function M so that Ped M(P'' o x) where ı is a random variable. Then we reach:
T("": P! (YY::.P
(; I [(g(Z)))) = I(Y"; Pd). (C.19)
which leads to contradiction.
Next, we prove that for Y", Pd and satisfying P = arg maxp! ,(Y";P')) would also satisfy Y g (Z] te. We also perform proving by contradiction. Suppose that Y * (() +
and Y (Z):") where P!' + P'. We then have the following inequality:
(Z) : ); P!) & ((g(Z)))
(C.20)
from which we can obtain that P!d = arg maxp! 1(YT; Pb), leading to a contradiction.
Now, we prove Proposition 3 in the following two perspectives.
First, we prove that minimizing the expectation term (Craak) in Eq. (1) can enforce the model to satisfy the Sufficient Condition in Assumption [ (note that we omit the subscript P! in z for brevity in the rest of this subsection if there are no special declarations).
From the SCM model in Figure ((b) we can analyze that max,/z=r//=)) I(YT; Z Z!: is equivalent to (G I(YT; G Z ZTT),
filter out the spurious correlations that contain in the dependencies between Y and G1 Treating (Z G1:2)) as the variational distribution, we
have the following upper bound:
1(YT; G 1:T Z I.:T)
KL I(Y
G e) | Z!:T, e)]
KL |p(TT
G ,e) || (YY" z )
KL [p(Y*)
Z 1: ,e) ll (|y" z [T]
(C.21)
KL [p(Y
G .e) g( zz:r]
min ((Y?)
KI. [pY G
.e) g (Y= 22.
In addition, we have:
KL p G I: g ]
log p(Y? = Y G1:T GI:T .e)
8(YTT YT Z ZI:T)
Y = YT G1:T G1:T e)
< ( (T
log
EziT g G::T
(q( Y = YT ZITT
(C.22)
The inequality in Eg.
C.22
is derived from Jensen's Inequality 34] and 186) while the EA-DGNN is a Dirac delta distribution (f-distribution). Then we reach:
w(-) ensures (Z
min o (
KL I
G 1:TT ee
Z qY
(C.23)
min E (e
(ttp://...........r..aa.."xrrx." [e (g(2) ))²)
21

---

We thus have proven that, minimizing the expectation term (Ctack) in Eq. (12 is to minimize the upper
bound of I(Y"; G Z ZTT) (maximize the lower bound of maxy(z) GLT) I(Y"; Z!T"), which
leads to maximizing (TT::')) This helps enforce the model to satisfy the Sufficient Condition.
Then, we prove that minimizing the variance term (Cris)) in Eq. 12 can enforce the model to satisfy
the Invariance Property Assumption |
We have:
I(Y"; e z ZTT = KL |p(YT T 1: .e) PYY" 2
Z)
KL [p(Y- z .e) Ee [p Y z .e)]]
KKL [g(2"( Z Ecg( Y Z ZzT
-KL [g(YT Z P(Y z .c]
(C.24)
KL [E. [p(Y" ZZ .c]] E. [q 1 []'"]]
KL [a(Y " Eeg((
(Y" [
min
KL ( (YY Z E [2.7)]
(
In addition, we have:
KL [Y z (Y" Y z=rr
log q(YT Y" (Z.T)
(C.25)
= EgEigr, y )up(G (2))) ur T G
Eeg(Y Y = YT 21:1)
Derived from Jensen's Inequality, the upper bound for KL [Q(YT) (Z:iT) Eng( Y
KL |g I ( EYg(YT ]z:T]] < Ee lle (fo (gl.1) y2) E [e (fe
(C.26)
Finally, we reach:
min KL [ ) Eog(Y ) <(Y
min Varses (Eargo()) (T) (o) aa) (fo (T Y do = =))]}
(C.27)
We thus have proven that, minimizing the variance term (Crisk) in Eq. 12 is to minimize the upper bound of I(Y";e Z!T)), which leads to minimizing !(Y :e P!). This helps enforee the model to satisfy the Invariance Property.
We conclude the proof for Proposition 3
C.4 Proof of Proposition
Proposition 4 (Equivalent Optimization). Optimizing Eq. 12) is equivalent minimizing the upper bound of the OOD generalization error in Eq. (2).
Proof. As defined in (2) the generation of dynamic graph data (gI.T, YT) is drawn from the distribution p( 1 Y e), while the difference of e during training and testing causes the out-of-distribution shifts. Let q( Y G1:2) be the inferred variational distribution of the ground- truth distribution p( pY G e), then the OOD generalization error can be measured by the diveiveree of the two distributions:
KL [p(Y")
G 1:7
.e) "
G [
log PYYT_ YT GL:T = gbT ,e) q( (Y YT GLT = g
=GiTTe)]
(C.28)
E.E yT)
we apply an information -nformation-theoreticc approach to our scenarios. First, we propose the following lemma in order to rewrite the OOD generalization error.
Inspired by 19 86
22

---

Lemma 2 (OOD Generalization Upper Bound). The OOD generalization error is upper bounded by:
KL. [p(Y"] G .e) q(( G & KL [p(Y" / .e) || q( z'"), (C.29)
where ( (Y?)) Z can be seen as the inferred variational distribution of the edge predictor.
Proof. We prove Lemma by continue investigating on Eq. (C.28)
KL [p(Y" G G e) q
G
log P Y G = GI:T, ,e)
= (T)
Y = YT GLT = GI:T)
p yr GIT G1:TT ,e)
log
E EzziT ~2(T (2 GI 1 Y =Y Z
log (Y = G = Gl.T .))
?(YT y (!:T)
= =
[p("
G I.T e)
q(Y z(:T)
(upper bound for OOD generalization error)
(C.30)
Again, the inequality in Eq. (C.22) is derived from Jensen's 's Inequality, while the EA-DGNN w(:)
ensures (Z 1:7 G (T) is Dirac delta distribution (6-distribution).
Based on Lemma we can adapt the Eq. 122 as:
min (Z Gu:T) ( T .Z.T)
KT. [P(Y"
11:T e)
(Y
z z1:T]] + T(Y": :el Z
(C.31)
Thus, based on Lemma 2 we validate that minimizing Eq.
12 is equivalent to minimizing the upper
bound of the OOD generalization error Eq.
( i.e.
mjn Crask + aCrisk
min
KL Ip(Y"
Q e) q(Y [
2 G L 2777
I(Y : Z
KL |
G 1:T
.e) || yY [T]
min
KL
| Y
G.T
Y
G G (T(YT) ;e z is non-negative)
(C.32)
We conclude the proof for Proposition
D Experiment Details and Additional Results
D.1 Datasets Details
We use three real-world datasets to evaluate FAGLE on the challenging future link prediction task.
COLLAB 88 is academic collaboration dataset with papers that were published during 1990- 2006 (16 graph snapshots). Nodes and edges represent authors and co-authorship. respectively. Based the co-authored publication, there five attributes in edges, including "Data Mining", "Database", "Medical Informatics". "Theory" and "Visualization" We pick "Data Mining" as the shifted attribute. We apply word2vec (59) extract 32-dimensional node features from paper abstracts. We use 10/1/5 chronological graph snapshots for training, validation, and testing, respectively. The dataset includes 23,035 nodes and 151,790 links in total.
Yelp 75 contains customer reviews business. Nodes and edges represent customer/business and review behaviors, respectively. Considering categories of business, there are five attributes in edges, including "Pizza", "American (New) Food", "Coffee & Tea", "Sushi Bars" and "Fast Food" from January 2019 December 2020 (24 graph snapshots). We pick "Pizza" as the shifted attribute. We apply word2vec [59] to extract 32-dimensional node features from reviews. We use 15/1/8 chronological graph snapshots for training, validation, and testing, respectively. The dataset includes 13,095 nodes and 65,375 links in total.
httpp:///ww httpp:://www.ammee..cmm www.er.maieeec...m. http://www...ee..coolaaaaaaaaaaa
https::/www http://wwwwyl..l..oo..p......p welp.commdattset
23

---

describes student actions on MOOC platform within a month (30 graph snapshots). Nodes represent students or largets of actions, edges represent actions. Considering the attributes of different actions, we apply K-Means 29 to cluster the action features into five categories and randomly select a certain category (the 5th cluster) of edges as the shifted attribute. We assign the features of actions to each student or target and expand the original 4-dimensional features to 32 dimensions by a linear function. We use 20/2/8 chronological graph snapshots for training, validation, and testing, respectively. The dataset includes 20,408 nodes and 202,339 links in total.
45
Statistics of the three datasets are concluded in Table D.1 These three datasets have different time spans and temporal granularity (16 years, 24 months, and 30 days), covering most real- world scenarios. The most challenging dataset for the future link prediction task is the COLLAB. In addition having the longest time span and the coarsest temporal granularity, also has the largest difference in the properties of its links.
Table D.I: Statistics of the real-world datasets.
Graph Snapshots
Temporal Granularity
Shifted Attribute
Dataset
# Nodes
Links
In-distribution Attributes
Database, Medical Informaties,
COLLAB
23,035
151,790
16
year
Theory, Visualization
Data Mining
American (New) Food, Fast Food Sushi Bars, Coffee & Tea Attributes 1-4
Yelp
13,095
65,375
24
month
Pizza
ACT
20,408
202,339
30
day
Attribute 5
We visualize the distribution shifts in the three real-world dataset with respect to the average neighbor degree (Figure D.I) and the number of interactions (Figure D.2) in training and testing sets. We observe that, there exists a huge difference in terms of the values, trends, etc., between the training and the testing set, which demonstrates the distribution shifts are heavy. Interestingly, COLLAB has less testing data than its training data, which is common in real-world scenarios, such as not all the co-authorship was established from the beginning. In addition, we notice drastic drop in Yelp after January 2019 when the COVID-19 outbreak. The sudden change in predictive patterns increases the difficulty of the task. A similar abnormal steep upward trend can also be witnessed in ACT after Day 20, which may be caused by an unknown out-of-distribun event.
Negatee Dlgive
4.0
16-
3-5-
5.0
2.5-
1990 1992
1996.
1996. ro8k. 2000 2002 2004
19.1 1994 182
199.0 220.1 2264 2260 20 mn
17 19 27 29
Time (yer))
Time (ncedh
Time (ay))
(a) COLLAB
(b) Yelp
(c) ACT
Figure D.I: Visualizations of the average neighbor degree in each graph snapshot.
D.2 Baseline Details
We compare EAGLE with representative GNNs and OOD generalization methods.
Static GNNs: GAE 42 is a representative static GNN as the GCN [1 based graph autoencoder;
VGAE 42 further introduces variational variables into GAE, possessing better generative ability,
Dynamic GNNs: GCRN 76 is a representative dynamic GNN following "spatial first, temporal second" convolution mechanism, which firstly adopts GCNs to obtain node embeddings and then a GRU 13 to capture temporal relations; EvolveGCN
62 applies an LSTM (31) or GRU
https: https://enap.stanfoon www.sssttooo..oo. http:p/ppssaaaaoo...ccd/ataaaaaa

---

12002
17590-
6002
Nutter dileeesctionss
Namber of imumatiors
Number Tesrmations
10000
5000-
19000
6000
5002
7500-
2000
4002
5000
2000
4002
2530
1000
2003
1993
1992
1998 2000 2002
15.1
195A
19.77
19.00 20.1 22.44 120.7 20.10 Time (mooth)
15
Thme
-
-b- Thiit
Tast
Tee Toan
-
Train
Test
(a) COLLAB
(b) Yelp
(c) ACT
Figure D.2: Visualizations of the number of interactions in each graph snapshot.
flexibly evolve the parameters of GCNs instead of modeling the dynamics after deriving node embeddings; DySAT 75 models dynamic graph through self-attentions in both structural neighborhoods and temporal dynamics.
OOD generalization methods: IRM minimizes the empirical risk to learn an optimal
invariant predictor under potential environments; V-REx 44 extends the IRM by reweighting the empirical risk to emphasize more on training samples with larger errors; GroupDRO 774 reduces the empirical risk gap across training distributions enhance the robustness when encountering heavy OOD shifts; DIDA (94] tackles OOD generalization problem on dynamic graphs for the
first time by discovering and utilizing invariant patterns. It is worth noting that, DIDA [94 most relative work as our main baseline for comparison.
is the
D.3 Experiment Setting Details
Detailed Settings for Section 4.1.1. Each of the three real-world datasets can be split into several partial dynamic graphs based their link properties, which demonstrates the multi-attribute relations under the impact of their surrounding environments. We filter out one certain attribute links as the variables under the future shifted environment as the OOD data, and the left links are further divided into training. validation, and testing sets chronologically. The shifted attribute links will only be accessible during the OOD testing stage, which is more practical and challenging in real-world scenarios as the model cannot capture any information about the filtered links during training and validation. Note that, all attribute-related features have been removed after the above operations before feeding to EAGLE. Take the COLLAB dataset for example. There are five attribute links in COLLAB as summarized in Table D.I We filter out all the links with the attribute "Data Mining", and split the rest of the links into training. validation, and testing sets by positive and negative edge sampling. Then we add the "Data Mining" links into testing sets make the distribution shifts. Finally, we remove all link attribute information to avoid data leakage.
Detailed Settings for Section 4.1.2 Denote original node features and structures as X Nxd and A' E {0, N For each time I, we uniformly sample p(t)| positive links and (1 (+)) negative links, which are then factorized into shifted features X" E Nxd while preserving structural property. Original node features and synthesized node features are concatenated as [X' X as the input. In details, X obtained by training the embeddings with reconstruction loss fXX"X"TT A A++1), where E(.) refers to the cross-entropy loss function [6]. In this way, we find that the link predictor can achieve satisfying results by using X" to predict the links in A 441 which demonstrates that the generated node features have strong correlations with the future underlying environments. The sampling probability p(t)= 5 cos(t), where X with higher p(t) will have stronger spurious correlations with future underlying environments. Note that, we apply the clip(-) function to limit the probability to between 0 and 1. We set f to be 0.4, 0.6, and 0.8 for training and 0.1 for testing; set o = 0.05 in training and a = 0 in testing.
Detailed Settings for Section[.22 We set the number of nodes N = 2,000 with 10 graph snapshots, where 6/2/2 chronological snapshots are used for training, validation, and testing, respectively. We set K = 5 and let de represent the proportion of the environments in which the invariant patterns are learned, where higher de means more reliable invariant patterns. Node features with respect to different environments are drawn from five multivariate normal distributions N (up, og). Features
25

---

with respect to the invariant patterns will be perturbed slightly, while features with respect to the variant patterns will be perturbed significantly. Here we perturb features by adding Gaussian noise with different degrees. We then construct graph structures based on node feature similarity. Links generated by the node-pair representations under the eş are filtered out during the training and validation stages, which is similar to the setting of Section 4.1.1 and they only appear in the testing stage following the proportion constraint g. Higher : means more heavier distribution shifts. LACC denotes the prediction accuracy of the invariant patterns by II()). As the environments e {e do not satisfy the permutation invariance property, thus the predicted invariant patterns with respect to is hard to evaluate. May wish to set the lAC reports the highest results shift the orders of environments in e to satisfy the predicted invariant patterns better.
D.4 Hyperparameter Sensitivity Analysis
We analyze the sensitivity of the hyperparameters and B, which act as the trade-off for loss in Eq. (16). The hyperparameter
chosen from (10-3, 10 1001 100, 10'), and 3 chosen from {10 10- 10 10-3 10-23. 3. We conduct analysis on three real woal-world datasets and report results in Figure D.3 and Figure D.4 Results demonstrate that the task performance experiences significant decline in most datasets when the values of a and 3 are too large or too small. We can draw conclusion that acts as a balance factor between exploiting the spatio-tempore invariant patterns for out-of-distribution prediction and generalizing to diverse latent environments with respect to variant patterns. plays role in balancing the trade-off between modeling the environment and inferring the environment distribution as bi-level optimization. conclusion, different combinations of hyperparameters lead to varying task performance, and we follow the tradition of reporting the best task performance with standard deviations.
82
76
80-
75
(DEDA]
PM
AUC C5
AUC Di
78
(DEDA)
04
EAGLE
EAGLE
EAGLE
72
10
10-2
10-1
1d'
10
10-2
L6-1
10'
72
10-1
10
10-
1If
11
(a) COLLAB
(b) Yelp
(c) ACT
Figure D.3: Sensitivity analysis of the hyperparameter a on three real-world datasets. The solid line shows the average AUC (%) in the testing stage and the light blue area represents standard deviations. The dashed line represents the average AUC (%) of the best-performed baseline.
34
76
(TYTTA)
92
37
40
ALC 74
(DDAA)
MLC
784
96
76
70
74-
Best Perocceed Baselie
Bex Perfumel Baseite
Bes Porfoned Baodite
72
70
(a) COLLAB
(b) Yelp
(c) ACT
Figure D.4: Sensitivity analysis of the hyperparameter 3 on three real-world datasets. The solid line shows the average AUC (%) in the testing stage and the light blue area represents standard deviations. The dashed line represents the average AUC (%) of the best-performed baseline.
26

---

D.5 Intervention Efficiency Analysis
From the results of complexity analysis Appendix B we believe the computational complexity bottleneck of EAGLE lies in the spatio-temporal causal intervention mechanism. In this case, we analyze the intervention efficiency in the following two aspects.
Intervention Ratio. We perform node-wisely causal interventions as in Eq. (5).. However, executing interventions for all nodes in each epoch is time-consuming. Thus, we propose randomly selecting nodes and performing interventions according to certain ratio. Let the intervention ratio represent the ratio the number intervened nodes to the total number of nodes |V. Figure D.5 shows the changes in task performance (AUC %) and the training time as the intervention ratio increases. We observe the AUC increases, proving that the spatio-temporal causal intervention mechanism is more effective in solving the OOD generalization problem with more intervened nodes. In addition, notice a jump the growth rate of AUC on three datasets at the ratio 0.6, which indicates most suitable intervention ratio while maintaining an acceptable training time cost.
Mixing Ratio. The intervention set Sy is sampled from Sob Sge While Sob has been already prepared after we model the environments in Section 3.1 the Sge requires instantly generating, which may be burden on the intervention efficiency. Let the maxing ratio represent the ratio of the number of observed environment samples to the number of generated environment samples. Figure D.6 shows the changes in task performance (AUC %) and the training time as the mixing ratio increases. Different from the trend in Figure D.5 AUC reached the maximum value at different ratios on the three datasets, and when different datasets have varying preferences for mixing ratio settings. In addition, we observe the variation training time not significant, verifying that although Soh needs to be generated instantly, its time cost is acceptable still, and we should pay more attention the optimal mixing ratio.
ratio is too large or small, the model performs poorly, indicating that
100
77.5-
77.5
ALC
72.5
0.1
04
03 05
10
01
04
05
07
08
61
02
06
0.5
95
08
18
(5)
Kale
--- ANC (N))
Time X0
A00.60
Time 69
-B-
AlI
Tineell
(a) COLLAB
(b) Yclp
(c) ACT
Figure D.5: Intervention efficiency analysis on the intervention ratio. The vertical dashed line
indicates the most suitable intervention ratio while maintaining an acceptable training time cost.
AUC
744
0.1
(a) COLLAB
(b) Yelp
(c) ACT
Intervention efficiency analysis on the mixing ratio. The vertical dashed line indicates the ratio when AUC reaches the maximum value.
Figure D.6:
D.6 Additional Analysis of Section 4.1
We visualize Table and Table in Section 4.1 to provide additional analysis. We have concluded in 4.T the baselines own a strong fitting ability but weak generalization ability between the distribution shifts settings. In addition to visualizing the task performance (AUC %), Figure D.7
27

---

annotates the decrease of AUC under each baseline method, where the horizontal dashed line represents the AUC decrease of our EAGLE. The smaller the decrease, the stronger the control ability under the impact of out-of- oult----ditriitttionn shifts. We can observe that on the vast majority of datasets, our method can improve task performance in both w/o OOD and w/ 00D scenarios while minimizing AUC decrease. Our control over AUC decrease exceeds the baseline except for GAE and GCRN in the vast majority of cases. For the above two baseline methods, although they have better control ability over AUC decrease than our method, the premise is that their task performance is inherently poor. In addition, our method achieves the most excellent task performance on the ACT dataset, which explain the unsatisfying but acceptable AUC decrease control. In summary, in addition to evaluating the advantages of our EAGLE in terms of task performance and generalization ability, which is the most topic-relative and common, our EAGLE also maintains the ability to reduce the impact of OOD on task performance.
100
AUC Decoes (N) the paal
Ald Durreeaa oa the
30
ALCINe (Ge
AUC
045
aywkr
BAGKS
Comyy 20L
wil 0000
wr
000
Ni 000
177a 1e' 000
-
AUC Deavar
000000
000
AUCDsmm
COLLAB
(b) Yelp
(c) ACT
100
180
100
AUC (eseinnrraaan
ADC (eaeeeeee
99
-0-
22
8
DishwdWW
DNM
DRM
D0DH
Excle
ZIDH
EARLS
Trei
AlCDicm
AIC Demaa
(d) COLLAB (5- = 0.4)
(e) COLLAB (p (f= 0.6)
( COLLAB (p = 0.8)
Figure D.7: Additional analysis of the performance on future link prediction.
D.7 Additional Results of Section 4.2
Section 4.2 reports the results when q 0.8. Here we report the additional results when q = 0.4 and 0.6 in Figure D.8 as we report in Section
[.8] All detailed results are summarized in Table D.2 A similar trend can be observed
2 that as de increases, the performance of EAGLE shows a significant increase while narrowing the gap between w/o OOD and w/ OOD scenarios. Although DIDA 194) also shows an upward trend, its growth rate is much more gradual, which indicates that DIDA [94] is difficult perceive changes in the underlying environments caused by different d it is incapable of modeling the environments, thus cannot achieve satisfying generalization performance. In addition, we also notice positive correlation between LACo and the AUC, which verifies the improvements are attributed to the proper recognition of the invariant pattems by I[()) In conclusion, our EAGLE can exploit more reliable invariant patterns, thus performing high-quale invariant learning and efficient causal interventions, and achieving better generalization ability.
E Implementation Details
E.1 Training and Evaluation
Training Settings. The number of training epochs for optimizing our proposed method and all baselines is set to 1000. We adopt the early stopping strategy, i.e., stop training if the performance
28

---

90
222a Ixce
-75
Lane
3
A00 (for box grrppt)
graph))
ACC graph)
80-
80
70
70-
70-
AUC (%0 line
65
60
60
60
60
55
40
40
0.2
0.4
0.2
0.4
0.6
0.8
de
DIDA (wi OOD)
EAGLE (wel OOD)
DIDA O0D)
EAGLE (wol OOD)
DIDA (w/0
EAGLE (w0)
DIDA (w/ 0019
EAGLE (w/ ODD)
(a) q 0.4
(b) g 0.6
Figure D.8: Additional results the effects of invariant pattern recognition.
Table D.2: AUC score (% + standard deviation) of future link prediction task synthetic datasets. w/o OOD and w/ OOD denote testing without and with distribution shifts. LAce is reported in the accuracy score). The best results shown in bold and the runner-ups are underlined.
Shift Degree
9 0.4
q == 0.6
9 = 0.8
Go
Model
w/o OOD
w/ OOD
LACO
w/ OOD
LACC
w/ OOD
IACC
DIDA [94]
63.2940.35
54.62 $4.62=0.92
53.33+1 ..01
52.87+1. 1.28
0.2
EAGLE
67. 07.1000.23
59.91=1.18
69.28=1.59
$4.71#1.29
63.36t11.4
14.26*t1.31
59.79*1.37
DIDA 94
64.31 56.36=0.98 9.8
56,04#1.1
55.89+1.24
0.4
EAGLE
70.32+0.27 63.97=0.82
12.04
61,08 1.02
69.95=1.30
58,40+1.12
63.88
DIDA 94 EAGLE
65.27=0.41 59.37=0.87
58.79+0.97
57.35
0.6
71.77+0.38
66.01
80.31
63.26 664
73.6241.41
63.1140.78
69.30 1.50
DIDA 94
66 06.55:+0.39
60.07=0.89
59.82+ .05
59.20+1.03
0.8
EAGLE
74.33+0.29
68.41
83.95=1.66
66. 15#0.99
77.08=1.73
65.82+0.81
12.59#1.46
DIDA 94
66.93 16.9340.18
62.55=0.85
61. 61.05=0.93
60.33+1.17
EAGLE
75.58+0.40
70.12:0.91
85.83#1.54
69.8320.93
79.5621.65
68.0920.97
1..1
the validation set does not improve for 50 epochs. For our EAGLE, the hyperparameter is 10 10'), and B is chosen from {10-6, 10-5, 10 10 (0-3,,10-,,100 10- The intervention ratio and the mixing ratio are carefully tuned for each dataset. For other parameters, adopt the Adam optimizer (40] with an appropriate learning rate and weight decay for each dataset and adopt the grid search for the best performance using the validation split. All parameters are randomly initiated, which especially important for W in Eq. (3) that ensures the difference in each environment embedding space. The K channels will still remain orthogonal during training as we conduct discrete environment disentangling iteratively. This helps the recognition of invariant/variant patterns mainly because we guarantee there is no overlap between environments.
chosen from (10-3, 10-2 10-1
Evaluation. According respective experiment settings, randomly split the dynamic datasets into training, validation, and testing chronological sets. We sample negative links from nodes that do not have links, and the negative links for validation and testing sets are kept the same for all baseline methods and ours. We set the number of positive links to the same as the negative links. We use the Area under the ROC Curve (AUC) 7 as the evaluation metric. As we focus on the future link prediction task, we use the inner product of a pair of learned node representations to predict the occurrence of links, i.e., we implement the link predictor g(.) as the inner product of hidden embeddings, which is commonly applied in classic future link prediction tasks. The biased training technique adopted following (9]. We use the cross-entropy loss as the loss function f(.). The activation function is LeakyReLU [ We randomly run all the experiments five times, and report the average results with standard deviations.
E.2 Baseline Implementation Details
We provide the baseline methods implementations with respective licenses follows.
29

---

GAE 42
httper/gfttbbb.oo///oaaaa///g/gg with MIT License.
VGAE 42
http://ggthh..ccmmbbeaaaaaa/a/ga with MIT License.
GCRN 76
htte:///tthabbccco//o/nnn/ggpggp with MIT License.
EvolveGCN 62
https//gtttubbooo///////o/olllud A License.
IRM bttp://ggtta.coooo///aass//s/sgp license unspecified.
DySAT 75
with
CC License.
V-REx http:///gthuu.ooocccooaaaa/////a with license unspeci-
fied.
GroupDRO 74 https:/gghubb.ooo//baaaa//gggggp with MIT License.
DIDA 94
/ www.thu...om//ooooci hwtp:///owodeergg221///01/// with license unspecified.
https: github.......
The parameters of baseline methods the suggested value in their papers carefully tuned for fairness.
E.3 Configurations
We conduct the experiments with:
Operating System: Ubuntu 20.04 LTS.
CPU: Intel(R) Xeon(R) Platinum 8358 CPU@2.60GHH with ITB DDR4 of Memory.
GPU: NVIDIA Tesla A100 SMX4 with 40GB of Memory.
Software: CUDA 10.1, Python 3.8.12, Py PyTcch [63] 1.9.1, Py PyTorch Geometric (20 2.0.1.
F
Further Discussions
F1
Further Analysis on SCM Model
We provide further analysis of the intrinsic cause of the out-of-distribution shifts. From the causal- based theories (64 65, 66], we formulate the generation process of static graphs and dynamic graphs with the Structural Causal Model (SCM) (64] in Figure[F.]] where the arrow between variables denotes
causal dependencies. It is widely accepted in the OOD generalization works [2 3 [22
87
[1] 2 60]
that the correlations between labels and certain parts of the latent features are invariant across data distributions in training and testing, while the other parts of the features are variant. The invariant part also called the causal part (C) and the variant part also called the spurious part (S).
Qualitative Analysis. In the SCM model on static graphs, C- G - S demonstrates that the invariant part and variant part jointly decide the generation of the graphs, while C - denotes the label is solely determined by the causal part. However, there exists the spurious correlation Cs -S certain distributions that would lead to backdoor causal path and the label are correlated statistically. As the variant part changes in the testing distributions caused by different environments e, the predictive patterns built on the spurious correlations expired. For the same reason, similar spurious correlation C' 55t exists snapshot, which opens the backdoor causal path S C Y Especially, as we have captured the temporal dynamics between each graph snapshot, the variant part in the previous time slice may also establish spurious correlations with the invariant part at present time, i.e., 1 -St, leading to 8t-1 - Ctc - Y which is unique phenomenon in the dynamic scenarios. Hence, propose to get rid of the spurious correlations within and between graph snapshots by investigating the latent environment variable encouraging the model to rely on the spatio-temporal invariant patterns to make predictions, and thus handle the distribution shifts.
C Y so that the variant part
dynamic graphs within a single graph
F Further Analysis of Assumption 1. The causal inference theories 64 the spurious correlations by blocking the backdoor path with do-calculus, which would remove causal dependencies on the intervened variables. Particularly, we intervene in the variant parts on all graph snapshots, i.e., do(S*). and thus the spurious correlations within and between graph snapshots can be filtered out. This encourages the two conditions in Assumption I to be satisfied: the Invariance
65 66
propose to get rid of
30

---

Property will be satisfied if the spurious correlations St X-S" are removed and the label will solely decided by the invariant part C Y which also satisfies the Sufficient Condition. In this case, we can minimize the variance of the empirical risks under diverse potential environments, while encouraging the model to make predictions of the spatio-temporal invariant patterns.
Further Explanations of the Toy Example. From the above analysis, we can further explain the toy example in Figure ((a). The prediction model has captured the spurious correlations between "coffee" and the "cold drink", which caused the false prediction of buying an Iced Americano in the winter. By applying our environment-ve ware EAGLE, the prediction model can perceive the environments of seasons through the neighbors around the central node, i.e., perceiving the winter season by learning the observed interactions between the user and the thick clothing. Thus encouraging the model rely on the exploited spatio-tempon invariant patterns, i.e., "the user buys coffee", to make the correct prediction on the Hot. Latte by considering underlying environments.
SCM on S Static Graphs
SCM on Dynamic Graphs
e
g
G
C'
G'
Y
Y
Causal P Part (invariant)
Surrious Part (variant)
e E Environments
O
Observations
Latent F Factors
Figure F.1: The SCM model on static graphs and dynamic graphs.
F.2 Further Understanding of Environments
Environments dynamic graphs are latent factors, where there are accessible ground-truth environment labels the real world, leading to the lack of explainability. In order to improve the explainability of the environment, and patterns the EA-DGNN learns, we have provided some real- world examples to make explanations (Section 3.Ip. The key insight lies that, the formation of real- world dynamic graphs typically follows a complex process under the impact of latent environments, causing the relationships to be multi-attribute. To model diverse spatio-temporal environments, the ego-graphs of each node need to be disentangled and processed in different embedding spaces.
Easy-to-Understann Understand Example: the Social Networks. The relationships between the central node and its neighbor nodes, which may be classmates, colleagues, etc., are formed under the influence of different surrounding environments. For example, the relationship between classmates is formed in the "school" environment, which is compound of "classmates", "teachers". "staff" etc., and the relationship between colleagues is formed in the "working" environment, etc. Multiple relationships are compounded into single edge and change over time. In order to model such multiple environments, we propose multi-channel environments disentangling to represent different semantic relationships in K embedding spaces. For example, the 1-st embedding represents the "classmate" relationship, and the 2-nd embedding space represents the "colleague" relationship, etc. Thus, EA-DGNN realizes the perception of multiple surrounding environments and encodes spatio-temporal environment information into node representations.
F.3 Further Understanding of the Multi-Label
Understanding. We do not require ground -oound truth environment labels in our EAGLE. The environments on dynamic graphs are latent factors, where there are no accessible ground-truth environment labels that have practical meanings in the real world. This is also why conventional OOD generalization baselines on images, text, efc. have poor performance (Section 4.1) in graphs as they must rely on ground-truth environment labels to generalize. In our work, the multi-label in Section 3.2 is mixed up with time index and environment index ht indicating which environment index under which time index belongs. It can be seen inferred label of environments.
31

---

Example. If there exist K environments and T graph snapshots, we first initialize zero matrix of the shape K T. Then we mark the value in position (k, to be and reshape the matrix into the 1-dimension vector y, indicating the multi-label of z for the k-th environment at time L.
Role. The multi-labels are used with to infer environments by ECVAE, where the multi-label is concatenated with its corresponding z to realize conditional variational inference. We can then instantiate environments by generating samples from the inferred distribution with a given one-hot multi-label. This can be regarded as the data augmentation of the environment samples under the guidance of the inferred prior distribution ( z, y). which helps improve the generalization ability.
E,4 Further Understanding of Proposition 2
Targets and Principles. Proposition 2 provides a solution to obtain the optimal (-) in Assumption ! with theoretical proof in Appendix C.2 In fact, Proposition solves dynamic programming problem
by optimizing the state transition equation [(i Given Var(z,') E IR as the representation variance of node in each environment across times, the target is to find partition dividing all
environment patterns into invariant and variant types, so as to maximize the difference between the variance means.
Conceptual Example. If Var(z"') of node v [0.1, 0.2, 0.3, 0.4, 0.9), then the optimal partition is [0.1. 0.2, 0.3. 0,4] and [0.9] (with larger mean difference) rather than [0.1, 0.2, 0.3] and [0.4, 0.9]. An optimal partition can always be found for each node, which greatly helps the patterns discrimination and fine- fine-grained causal interventions, improving the generalization ability, and is one of our main advantages compared with DIDA (94).
Proposition 2 intuitively illustrates feasible implementation for the optimal (-),,, providing an ideal optimizing start point. Note that, Proposition 2 itself cannot fully guarantee the global accuracy of identifying the I (-), but should optimize along with the Crisk loss (Eq. [14). which provides theoretical ensure.
F5 Further Discussions Compared with DIDA
The difference between our EAGLEand DIDA 94 and EAGLE'S main advantages are:
Modeling Environments. EAGLE is the first to explicitly model latent environments on dynamic graphs by variational inference. DIDA 194) neglects to model complex environments, which weakens its ability to identify invariant patterns.
Representation Learning. EAGLE learns node embeddings by K K-channel environments disen- tangling and spatio-temporal convolutions, which helps better understand DIDA (94) learns with single channel convolutions with an attention mechanism.
relations.
Invariant Learning. EAGLE discriminates spatio-temppral invariant patterns by the theoretically supported (-) for each node individually, leading to better removal of spurious correlations. DIDA 94 divides invarian//variant parts heuristicly with a minus operation for all nodes.
Causal Intervention. EAGLE performs fine-grained causal interventions with both observed and generated environment samples, better minimizing the variance of extrapolation risks, and generalizing to unseen distributions better. DIDA (44 intervenes goarse-grainedly with only observed samples.
F.6 Further Related Work
Dynamic Graph Learning. Extensive research (70, 4 address the challenges of learning on dynamic graphs, which consist of multiple graph snapshots at different times. Dynamic graph neural networks (DGNNs) are widely adopted learn dynamic graphs by intrinsically modeling both spatial and temporal patterns, which can be divided into two main categories: spatial-fire first methods and temporal- first methods. The spatial-first methods [88 28 (66 first adopt vanilla GNNs to model spatial patterns for each graph snapshot, followed by sequential-basee to capture temporal relations. In comparison, temporal-first DGNNS advance with temporal encoding mechanisms [32] and then conduct convolutions of messagg-ppsssngg and aggregating on each single graph with GNNs. Dynamic graph learning has been widely utilized for prediction tasks like disease transmission prediction [38), dynamic recommender system (90).
models like RNNs
[58 or LSTMs [3]],
model dynamics in
32

---

social relation prediction |5], etc. However, most existing works fail to generalize under distribution shifts. DIDA 94 is the sole prior work that addresses distribution shifts on dynamic graphs with an intervention mechanism. But DIDA [94] neglects to model the complex environments on dynamic graphs, which is crucial tackling distribution shifts. We also experimentally validate the advantage of our method compared with DIDA (94).
Generalization. Most machine learning methods are built on the L.I., hy- pothesis, i.e., training and testing data follow the independent and identical distribution, which can hardly be satisfied in real-world scenarios 777, as the generation and collection process of data are affected by many latent factors [] The non-I.I.D. distribution results in a significant decline of model performance, highlighting the urgency investigate generalized learning meth- ods for out-of --ittiibbttiittionnn (OOD) shifts, especially for high-stake downstream applications, like autonomous driving [5], financial system [62, etc. OOD generalization has been extensively studied in both academia and industry covering various areas 77 92 30 and we mainly focus on OOD
generalization on graphs [50] Most graph-targeted works concentrate on node-level or graph-level
12 877, targeting at solving the problems of graph OOD generalization for drugs, molecules, etc,, which is identified as one key challenge in AI for science (A14Science). Another main category of works elaborates systematic benchmarks for graph OOD generalization evaluation [26] 17 36.. However, there lack of further research on dynamic graphs with more complicated shift patterns caused by opatio-temporal varying latent environments, which is our main concern.
tasks static graphs 198 I8
49
86
52
Invariant Learning. Deep learning models tend to capture predictive correlations behind observed samples, while the learned patterns are not always consistent with in-the-wild extrapolation. Invariant learning aims to exploit the less variant patterns that lead to informative and discriminative represen- tations for stable prediction [14 46 95). Supporting by disentangled learning theories and causal learning theories, invariant learning tackles the OOD generalization problem from more theoretical perspective, revealing a promising power. Disentangle-base
methods [5 learn representations
by separating semantic factors of variations in data, making it easier distinguish invariant factors and establish reliable correlations. Causal- bassd methods [22 3 72
60) utilize Structural Causal Model (SCM) [64] to filter out spurious correlations by intervention or counterfactual with do-calculus [65] 66 and strengthen the invariant causal patterns. However, the invariant learning method of node-level tasks dynamic graphs is underexplored, mainly due to its complexity in analyzing both spatial and temporal invariant patterns.
Disentangled Representation Learning. Disentangled Representation Learning (DRL) is paradigm that inspires a model with the capability to discriminate and disentangle latent factors intrinsic to the observable data. The fundamental objective of DRL is to separate latent factors of variation into distinct variables endowed with semantic significance. This helps to improve the generalization capacity, explainability, and robustness, etc. in wide range of scenarios. Following [83] categorize existing DRL works into traditional statistical approaches, VAE-based approaches, GAN- based approaches, hierarchical approaches, and other methods. Specifically, applying DRL to graphs results in benefits and advantages in graph tasks. DisenGCN (56), FactorGCN 89) DGCL [48),
etc. decompose the input graph into segments for disentangled representations, which inspire work on environment disentangling.
33


Reviews:
[{"review_id": "qD7gbSs42u", "reviewer": "Reviewer_oZr8", "summary": "This paper proposes a novel framework called EAGLE for out-of-distribution generalization on dynamic graphs. EAGLE models the complex environments that influence the generation of dynamic graphs and exploits the spatio-temporal invariant patterns that can generalize under distribution shifts. EAGLE consists of four mechanisms: environment-aware dynamic graph neural network, environment instantiation, invariant pattern recognition, and causal intervention. EAGLE achieves superior performance on future link prediction tasks on both real-world and synthetic datasets compared to existing methods. The paper also provides theoretical analysis and empirical studies to support the effectiveness of EAGLE.", "questions": "1. What does the one-hot multi-label y introduced in line 142 represent? Does it means what index of the environment which the observed z belongs to, or does it also include the index of the time step?\n2. Could the author provide a more detailed explanation of the visualization experiment mentioned in Section 4.4?\n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The illustration in Figure 2 is clear and aids in understanding the proposed method.\n2. Theoretical analysis and proofs are provided as necessary.\n3. Overall, the proposed solution for OOD Dynamic link prediction seems reasonable. The idea of generating spatio-temporal environments is novel.\n", "weaknesses": "1. The generated environment patterns lack explainability. These patterns are produced through disentangling, making it difficult to explicitly understand their specific meaning in reality.\n2. The author should include further discussion on how the proposed method can contribute to link prediction in a new environment, as exemplified in Figure 1. If the model successfully distinguishes environment-invariant patterns in previous graphs, how will it capture new patterns in a different environment to improve prediction?\n3. The writing style is not reader-friendly for those unfamiliar with the task and techniques. It would be beneficial to provide more intuitive explanations to enhance understanding.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the detailed comments and insightful questions. Responses are as follows.\n\n**Q1:** The generated environment patterns lack explainability. \n\n**A1:** Thank you for your question.\n\n- **[Understand latent environments]** Environments are **latent factors**, where the ground-truth labels are **inaccessible**. We provide real-world examples (lines 101-106) as illustrations. **The key insight is,** the formation of dynamic graphs typically follows a complex process under the impact of environments, causing the relationships to be multi-attribute. To effectively model diverse spatio-temporal environments, the ego-graphs of each node are disentangled and processed in **different embedding spaces**.\n- **[An example: the social networks]** The relations between a central node and its neighbors, e.g., “classmates”, “colleagues”, etc., are formed in different surrounding environments, e.g., classmates relations are formed in “school” environment, consisting of “classmates”, “teachers”, “staff”, etc., and colleagues relations are formed in “working” environment.  We propose **multi-channel environments disentangling mechanism** to discriminate different semantics in $K$ embedding spaces, e.g., the 1-st embedding space means the “classmate” relations, the 2-nd embedding space means the “colleague” relations, etc. Thus, EA-DGNN can percept and encode environment features into node representations.\n\nWe will add further explanation in the revised version.\n\n---\n\n**Q2:** Further discussion on how the proposed method can contribute to link prediction in a new environment in Figure 1. How will the model capture new patterns in a different environment?\n\n**A2:** Thank you for your question. \n\n- **[Further discussions]** We have provided further explanations in Appendix F.1. It indicates that the existing model has captured the spurious correlations between the semantics of “coffee” and “cold drink”, which caused the **false** prediction of “Iced Americano”. EA-DGNN can learn multiple environment patterns, such as  “coffee”, “cold drinks”, “iced dessert”, “summer dressing”, etc. Section 3.3 identifies the **spatio-temporal invariant pattern** to be “coffee”. Section 3.4 encourages the model to learn solely with the “coffee” pattern while minimizing the environment extrapolation risks to enhance the generalizing ability in a new environment.\n- **[During testing]** Our trained model will directly give a higher possibility score for a Hot Latte than an Iced Americano in testing. This is because the model has fully learned the invariant and sufficient information for correct prediction during training, and the risk in the unknown test environment is reduced. Besides, the model can perceive the testing environment's (winter) semantics through message passing and aggregation of its neighbor nodes, which leads to the final prediction.\n\nWe will add further explanations in the revision.\n\n---\n\n**Q3:** The writing style is not reader-friendly. Beneficial to provide more intuitive explanations.\n\n**A3:** Thank you for your suggestion. We will add more related works and further intuitive explanations to improve readability, especially to the techniques and theories. In addition, we will try to simplify the notations and add clearer clarifications to enhance understanding.\n\n---\n\n**Q4:** What does the one-hot multi-label $\\mathbf{y}$ introduced in line 142 represent? Does it mean what index of the environment which the observed $\\mathbf{z}$ belongs to, or does it also include the index of the time step?\n\n**A4:** Thank you for your questions. \n\n- **[Meaning]** $\\mathbf{y}$ is mixed up with time index $t$ and environment index $k$, indicating which environment index under which time index $\\mathbf{z}$ belongs. It can be seen as our inferred label of environments.\n- **[Example]** If there exist $K$ environments and $T$ graph snapshots, we first initialize a zero matrix of the shape $K \\times T$. Then we mark the value in position $(k,t)$ to be 1 and reshape the matrix into the 1-dimension vector $\\mathbf{y}$, indicating the multi-label of $\\mathbf{z}$ for the $k$-th environment at time $t$.\n- **[Role]** $\\mathbf{z}$ is **concatenated** with its corresponding $\\mathbf{y}$ to realize conditional variational inference for the distribution of latent environments by ECVAE. We can then instantiate environments by generating samples from the inferred distribution with any given $\\mathbf{y}$. This can be regarded as **the data augmentation** under the guidance of the inferred prior distributions, which helps improve the generalization ability.\n\nWe will add more explanations in the revision.\n\n---\n\n**Q5:** Provide a more detailed explanation of the visualization experiment.\n\n**A5:** Thank you for your question. \n\n- **[Settings]** We visualized snapshots in the dataset COLLAB using NetworkX in Figure 5. As EAGLE concentrates on solving **node-level** downstream tasks, we carried out visualization analysis from the perspective of a single node $v$ (red color).\n- **[Process]** EA-DGNN first models the environment-aware node representation for node $v$ (represented by “🟪🟦🟩🟧🟨”), then Section 3.3 identifies spatio-temporal variant patterns (represented by “⛝”). To encourage the model to rely on sufficient and invariant information to make predictions and minimize the environment extrapolation risks, Section 3.4 randomly replaces the “⛝” parts with observed or generated environment samples (represented by “🔄”).\n- **[Analysis]** Thus, the model focuses more on the neighbor nodes in the **more invariant environments patterns** (purple and blue parts “🟪🟦”), increasing the edge weights (can be seen as spatio-temporal attention), while ignoring the links with the **more variant environments patterns** (represented by “🟩🟧🟨”).\n\nIn conclusion, EAGLE can effectively learn invariant patterns, making generalized predictions. We will add more detailed explanations of the visualization experiment in the revision."}, {"review_id": "sEiglZey7R", "reviewer": "Reviewer_iWRC", "summary": "In this paper, the authors propose a novel framework EAGLE, Environment-Aware dynamic Graph LEarning, which tackles the OOD generalization problem by modeling complex dynamic environments and exploiting spatial-temporal invariant patterns. Following the Environment “Modeling-Inferring-Discriminating-Generalizing” paradigm, EAGLE consists of three modules. Firstly, an Environment-Aware Deep Graph Neural Network (EA-DGNN) is designed to model environments by learning disentangled representations under multi-channel environments. EAGLE then diversifies the observed environments' samples with the environment instantiation mechanism, which infers environment distributions by applying the multi-label variational inference. Finally, EAGLE discriminates spatio-temporal invariant patterns for out-of-distribution prediction by the invariant pattern recognition mechanism and performs fine-grained causal interventions node-wisely with a mixture of observed and generated environment samples. Extensive experiments on real-world datasets demonstrate that EAGLE outperforms baseline methods on dynamic graph OOD tasks.", "questions": "1. Please see the first two questions in Weaknesses.\n2. Compared to DIDA, what is the advantage of EAGLE for modeling the complex dynamic environment? It would be great if the authors could provide some examples for explanation.\n3. When the training data is homogeneous (i.e., only contains few environments), how does EAGLE generalize to unseen test environments with OOD shifts?\n4. How to select an appropriate number of generated instances for Invariant Pattern Recognition to exploit spatio-temporal invariant patterns?\n5. The authors discussed EAGLE's computational complexity in the appendix. What is EAGLE's space complexity?", "limitations": "The authors did not address the limitations of their work.  The reviewer thinks that the authors should make the description of the problem setting, the definitions of spatio-temporal invariant patterns, and variant patterns more clear. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The OOD generalization problem on dynamic graphs is important, especially when considering changes in latent environments. EAGLE is the first model to tackle this problem by modeling the impact of environments on dynamic graphs under distribution shifts.\n2. The proposed Environment “Modeling-Inferring-Discriminating-Generalizing” paradigm is technically sound and easy to understand, and using the proposed Environment Instantiation Mechanism to generate instances for inferring environment is novel.\n3. The experiments are extensive (real-world datasets under distribution shifts on link attributes and node features, ablation studies on proposed mechanisms), and the results are considerably better than existing methods.", "weaknesses": "1. The requirement of the environment information is not specified. Especially, whether EAGLE requires the environment label to be known or not. The reviewer thinks one of the main contributions of EAGLE should be inferring environments from samples, but there are not any detailed explanations, and it seems that the number of environments is pre-determined in the experimental setting. The reviewer wonders if the authors could discuss the requirement of environment labels in detail and how to select the proper number of environments if the environment label is unknown.\n2. Proposition 2 is difficult to understand and lacks details about how to obtain the optimal $\\mathbb{I}^*(\\cdot)$. It would be great if the authors could provide further explanation and a concrete example to help readers better understand the proposition.\n3. The related work part should also add literature related to disentangled representation learning and further discuss the difference between EAGLE and DIDA [61] in detail.\n\nMinor issues:\ntypo: line 145, multi-lables -> multi-labels", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the detailed comments. Responses are as follows.\n\n**Q1.1:** Whether EAGLE requires the environment label?\n\n**A1.1:** Thanks for your question. EAGLE doesn’t require the ground-truth environment labels, which are also **inaccessible** in the real dynamic graphs. We propose a multi-label $\\mathbf{y}$, which is mixed up with time and environment index. It can be seen as our inferred environment labels.\n\n---\n\n**Q1.2:** How to select the proper number of environments?\n\n**A1.2:** Thanks for your question. We adopt a **warm-up mechanism** to determine $K$. We evaluate the performance of the first 10 epochs on the validation set to find the most suitable $K$, and fix it for the rest of training. Following your suggestion, we add the parameter sensitivity experiment for $K$ on COLLAB, which shows the impact of $K$ on model performance. We will add this in the revision.  \n\n| $K$ | 2 | 4 | **6** | 8 | 10 |\n| --- | --- | --- | --- | --- | --- |\n| AUC (w/o OOD) | 80.33±1.29 | 81.17±1.04 | **84.41±0.87** | 83.65±0.79 | 81.94±1.03 |\n\n---\n\n**Q2:** Further explanation and example to understand Proposition 2.\n\n**A2:** Thank you for your suggestion. \n\n- **[Explanation]** Proposition 2 solves a **dynamic programming problem** to obtain the optimal $\\mathbb{I}^\\star(\\cdot)$ with proofs in Appendix C.2. The **target** is to find a partition dividing all patterns into variant/invariant set with the **maximum** difference between the variance means.\n- **[Example]** Suppose $\\mathrm{Var}(\\mathbf{z}_v^{\\mathbf{e}\\prime})$ is [0.1, 0.2, 0.3, 0.4, 0.9], then the optimal partition is [0.1, 0.2, 0.3, 0,4] and [0.9] (with a larger mean difference) rather than [0.1, 0.2, 0.3] and [0.4, 0.9]. An optimal partition **can always be found** for each node, which greatly improves the generalization, and is **one of our main advantages** compared with DIDA [1].\n\nWe will provide further explanations in the revision.\n\n---\n\n**Q3:** More related work to disentangled representation learning.\n\n**A3:** Thank you for your valuable suggestions. Disentangled Representation Learning (DRL) is closely related to our work. Most existing graph OOD works fail to learn separate semantics of latent and complex environments, and DRL inspires us to perform environment disentangling, which greatly helps to improve the generalization capability. We will update this in the revision to enhance the understanding of environments.\n\n---\n\n**Q4:** Further discuss the difference and between EAGLE and DIDA [1]. What are EAGLE’s advantages?\n\n**A4:** Thanks for your constructive suggestion. The difference and advantages are:\n\n- **[Modeling environments]** EAGLE is the **first** to explicitly model latent environments on dynamic graphs by variational inference. DIDA [1] neglects to model environments, which weakens its ability in identifying invariant patterns.\n- **[Representation learning]** EAGLE learns node embeddings by $K$-channel environments disentangling and spatio-temporal convolutions, which helps better understand multi-attribute relations. DIDA [1] learns with single channel convolutions with attention.\n- **[Invariant learning]** EAGLE discriminate spatio-temporal invariant patterns by **the theoretically supported $\\mathbb{I}^\\star(\\cdot)$** for each node individually, leading to better removal of spurious correlations. DIDA [1] divides invariant/variant parts simply and heuristically with a minus operation for all nodes.\n- **[Causal intervention]** EAGLE perform fine-grained causal interventions with **both** observed and generated environment samples, better minimizing the variance of extrapolation risks, generalizing to unseen distributions better. DIDA [1] intervenes coarse-grainedly with only observed samples.\n\nWe will add the comparison in the revision.\n\n---\n\n**Q5:** How does EAGLE generalize to unseen test environments with OOD shifts when training data is homogeneous?\n\n**A5:** Thank you for your question. EAGLE is agnostic about the intrinsic properties of data (density, heterophily, etc.).  Further, following OOD literature, we assume there are $K$ latent environments, where $K$ can be determined by **the warm-up mechanism**. We leave the study of how to dynamically and adaptively determine $K$ for different datasets as our future works.\n\n---\n\n**Q6:** How to select an appropriate number of generated instances for Invariant Pattern Recognition?\n\n**A6:** Thank you for your question. In Appendix D.5, we provide analysis and appropriate mixing ratio settings. As the number of the observed instances is fixed ($n_{ob}=|\\mathcal{V}| \\times K \\times T$), the number of generated instances can be calculated by multiplying the preferred ratio with $n_{ob}$.\n\n---\n\n**Q7:** What is EAGLE's space complexity?\n\n**A7:** Thank you for your question. The overall space complexity of EAGLE is $\\mathcal{O}(KT(|\\mathcal{V}|+|\\mathcal{E}|)) + \\mathcal{O}(|\\mathcal{V}|KTd) + \\mathcal{O}(Ld^2) + \\mathcal{O}(Ld)+ \\mathcal{O}(K\\sum_{v\\in\\mathcal{V}} \\mathrm{Var}(\\mathbf{z}_v^{\\mathbf{e}\\prime}))$, where the meaning of notations can be found in Appendix A and B. As $K$, $T$, $d$ and $L$ are small numbers, EAGLE has a linear space complexity with respect to $|\\mathcal{V}|$ and $|\\mathcal{E}|$. Our experiments also show that the empirical memory cost of EAGLE is on par with the related works. We will add the detailed space complexity in the revision.\n\n---\n\n**Q8.1:** No limitations statements.\n\n**A8.1:** Thanks for your suggestions. We would like to clarify that we have briefly discussed the limitations of our work being restricted only to node-level tasks **in Section 6, lines 322-323.**  We will extend limitation discussions in the revision.\n\n---\n\n**Q8.2:** Make the descriptions more clear.\n\n**A8.2:** Thank you for your suggestion. We will make further improvements with clearer notations and easy-to-understand explanations in the revision.\n\n---\n\n[1] Dynamic graph neural networks under spatio-temporal distribution shift. NeurIPS, 2022."}, {"review_id": "CdE3ia96YD", "reviewer": "Reviewer_YPMZ", "summary": "This paper proposes a novel framework called EAGLE to address the challenge of out-of-distribution generalization in dynamic graphs. The authors investigate the impact of latent environments on dynamic graphs and develop methods to model and infer these environments. They propose techniques to recognize spatio-temporal invariant patterns and perform fine-grained causal interventions. The rationality and correctness of EAGLE are guaranteed by rigorous reasoning and mathematical proof. Experimental results demonstrate the superiority of their method in handling distribution shifts in dynamic graph datasets.", "questions": "(1) Are there other OOD types besides the links and node features? How to demonstrate that the proposed model improves generalization performance on the other OOD types?\n(2) It is better to explain the details of the baselines and datasets, like the differences with the proposed model, the statistical information of the datasets, etc. in the main contents.\n", "limitations": "Y", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) First attempt to explicitly model the environment on dynamic graphs. Through the innovative Environment “Modeling-Inferring-Discriminating-Generalizing” paradigm, the influence of open environment on OOD generalization on dynamic graphs is explored, and the generalization ability of the model in this scenario is improved.\n(2) Well-organized derivation and mathematical proofs. Based on causality theories, the proposed method is proven to satisfy the invariance assumptions and propositions, directing the optimization that achieves OOD generalization for in-the-wild extrapolations by fine-grained causal interventions. \n(3) Reasonable experiment settings and sufficient results. Appropriate baseline methods are compared under multiple OOD environment settings. The results of the main experiment and several auxiliary experiments demonstrate the effectiveness and superiority of the proposed method.\n(4) This method can be easily extended to other sequential models to perform temporal convolutions, or compounded with any attention/reweighting mechanisms in environment modeling. This paper is well-organized and easy to follow. The background problems and method design are clearly explained.\n", "weaknesses": "(1) Variable symbols are kind of complicated, and their expressions are not very clear, which brings difficulties in understanding theoretical proofs.\n(2) Computational complexity and sufficient analysis are not discussed in the main contents.\n(3) The distribution shifts in the experiment datasets are manually designed. I wonder if there exist naturally formed dynamic graph OOD datasets that measure on their OOD degree, and conduct experiments based on those datasets.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the detailed comments and insightful questions. We make responses to the reviewer’s comments as follows.\n\n**Q1:** Variable symbols are kind of complicated, and their expressions are not very clear, which brings difficulties in understanding theoretical proofs.\n\n**A1:** Thanks for your kind suggestion. In order to enhance readability and reduce the difficulty of understanding symbols, we will improve complex symbols and notations by increasing the descriptions and omitting unnecessary superscripts and subscripts. Especially in the theoretical proofs, we will add easy-to-follow understandings and examples in the revision to improve the reader experience.\n\n---\n\n**Q2:** Computational complexity and sufficient analysis are not discussed in the main contents.\n\n**A2:** Thanks for your suggestion. \n\n- **[Computational complexity]** We include the computational complexity and its analysis in Appendix B. The computational complexity of EAGLE is $\\mathcal{O} \\left ( |\\mathcal{E}| \\sum_{l=0}^{L} d^{(l)}+ \\mathcal{V} \\left ( \\sum_{l=1}^{L} d^{(l-1)}d^{(l)} + (d^{(L)})^2 \\right ) \\right )$ (Eq. (B.1)), indicating EAGLE has **a linear computation complexity** with respect to the number of nodes and edges, which is **on par with** existing dynamic GNNs and OOD methods on dynamic graphs.\n- **[Space complexity]** Denote $|\\mathcal{V}|$ and $|\\mathcal{E}|$ as the number of nodes and edges, respectively, $K$ as the number of environments, $T$ as the number of time slices, $L$ as the number of layers in EA-DGNN, $L^\\prime$ as the number of layers in ECVAE, $d_0$ as the dimension of input node features, $d=K d^\\prime$ as the hidden dimension of EAConv layers in EA-DGNN, $d^\\prime$ as the hidden dimension of the encoder and decoder networks layer of ECVAE, $\\sum_{v \\in \\mathcal{V}} \\mathrm{Var}(\\mathbf{z}_v^{\\mathbf{e}\\prime})$ as the variance of $K$ environment-aware representations.\n    - the dynamic graph: $\\mathcal{O}(K T(|\\mathcal{V}|+|\\mathcal{E}|))$\n    - the node input features: $\\mathcal{O}(|\\mathcal{V}|  K  T  d_0)$\n    - the EAConv layer: $\\mathcal{O}(L  d^2)$\n    - ECVAE: $\\mathcal{O}(L^\\prime  d^\\prime)$\n    - storing generated environment samples: $\\mathcal{O}(|\\mathcal{V}| K  T  d^\\prime)$\n    - storing the states for function $\\mathbb{I}(\\cdot, \\cdot)$: $\\mathcal{O}(K  \\sum_{v \\in \\mathcal{V}} \\mathrm{Var}(\\mathbf{z}_v^{\\mathbf{e}\\prime}))$.\n    - The **overall** space complexity of EAGLE can be roughly calculated as $\\mathcal{O}(K T(|\\mathcal{V}|+|\\mathcal{E}|)) + \\mathcal{O}(|\\mathcal{V}|  K  T  d) + \\mathcal{O}(L  d^2) + \\mathcal{O}(L d) + \\mathcal{O}(K  \\sum_{v \\in \\mathcal{V}} \\mathrm{Var}(\\mathbf{z}_v^{\\mathbf{e}\\prime}))$ (note that, we omit differences in superscript and subscript of $L$’s and $d$’s for brevity)\n\nAs $K$, $T$, $d$ and $L$ are small numbers, EAGLE has a linear space complexity with respect to $|\\mathcal{V}|$ and $|\\mathcal{E}|$. Our experiments show that the empirical memory cost of EAGLE **is on par with the related works.** We will add these analyses in the main contents in the revised version.\n\n---\n\n**Q3:** If there exist naturally formed dynamic graph OOD datasets that measure on their OOD degree, and conduct experiments based on those datasets.\n\n**A3:** Thanks for your question. To the best of our knowledge, there is no existing dynamic graph OOD datasets that measure their OOD degree. \n\n- **[Why no naturally formed OOD datasets]** Out-of-distribution shifts naturally exist in dynamic graphs as the formation of real-world dynamic graphs typically follows a complex process under the impact of underlying environments. However, though these shifts vary in degree, they are **difficult to quantify**. We leave the problem of measuring the OOD degree between training and testing distributions as future work.\n- **[Our datasets are more challenging]** In our experiments, we manipulate the datasets following DIDA [1]. Actually, the manually designed distribution shifts in our work are **more practical and challenging** in real-world scenarios as the model **cannot get access to any information** about the filtered links until the testing stages. Our model still has satisfactory performance under such harsh OOD distribution shifts than all baselines, which further demonstrates EAGLE's excellent out-of-distribution generalization ability.\n\n---\n\n**Q4:** Are there other OOD types besides the links and node features? How to demonstrate that the proposed model improves generalization performance on the other OOD types?\n\n**A4:** Thanks for your question. Though there exist other OOD types on the graph level, such as the graph size, scaffold, base motifs, etc., none of them has a time dimension (not dynamic) and has no real-world scenarios in terms of the dynamic settings, leaving them **only suitable for static graphs**. As our work focuses on the OOD generalization problem on dynamic graphs for **node-level tasks**, the most related OOD types on the node level are the **links and node features**. So we conduct extensive experiments to demonstrate the generalization ability of our model in node-level OOD shift settings. \n\n---\n\n**Q5:** Explain the details of the baselines and datasets in the main contents.\n\n**A5:** Thank you for your suggestions. \n\n- **[Baselines]** We provide a short introduction in the main contents (Section 4, lines 220 to 227) and provide the full details of the baseline and the analysis of the differences with our proposed model in Appendix D.2, and the implementation details of the baseline are introduced in Appendix E.2.\n- **[Datasets]** We give a simplified explanation and the OOD settings in the main contents (Section 4, lines 216 to 219), and implement the full details of the baselines in Appendix D.1, including statistical information, the OOD manipulations, their visualizations, etc.\n\nWe will add more details of baselines and datasets in the main contents in the revision, to enhance a better understanding of experiments."}, {"review_id": "JrtPj1Qp7O", "reviewer": "Reviewer_aDm2", "summary": "This paper proposes EAGLE to improve OOD generalization in DGNNs. It focuses on modeling and inferring complex environments on dynamic graphs with distribution shifts and identifying invariant patterns within inferred spatio-temporal environments. The EAGLE incorporates an environment-aware model, an environment instantiation mechanism for diversification, and an invariant pattern recognition mechanism for OOD prediction. The authors claim that EAGLE outperforms current methods on various dynamic graph datasets, marking the first approach to OOD generalization on dynamic graphs from an environment learning perspective. ", "questions": "plz refer to Weaknesses.", "limitations": "plz refer to Weaknesses.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The problem to be solved in this article is significant.\n2. The authors conducted sufficient experiments to verify their claim.\n", "weaknesses": "1. The paper lacks a clear definition of 'environment', particularly in the context of multiple graphs. As the environment seems to correlate with time (T), the authors should elucidate whether the environment changes with T. Given the evident correlation between time and environmental changes - as seen in the authors' own example of transitioning from school to a company (past classmates --> current colleagues) - this should be addressed in the discussion.\n\n2. It is not apparent whether the different environment K is determined by the dataset or is a hyperparameter. The paper should elucidate the relationship between the environment number K and the graph data T.\n\n3. Assumption 1, which emulates a significant amount of existing work [1-4], seems to have a miswritten part (b) where the noise term should be placed outside the brackets.\n\n4. The article uses notations that are confusing, making it difficult to read. For instance, it is unclear why the same symbol, z, is used to represent the result set obtained by the set operation in line 134. The meanings of symbols e and s should be clarified.\n\n5. The author should provide more explanation about Proposition 1 and Proposition 2, rather than simply stating the theories and placing the proofs in the appendix. A brief explanation of what these theorems illustrate would be beneficial.\n\n6. Several remarks and statements in the article are wrong. For example:\n\n- The absolute statement, \"Existing works fail to generalize under distribution shifts ...\" overlooks recent works [4] addressing distribution shifts.\n- The sentence on lines 140-141, \"We regard the learned node embeddings as environment samples drawn from the ground-truth distribution of latent environment\", is ambiguous and warrants clarification. How can we learn \"ground-truth\" distribution?\n\nIn summary, the main issue with this paper is its lack of clarity, manifested in confusing mathematical symbols, unclear theorem and formula meanings, and an ill-defined problem statement.\n\n[1] Handling Distribution Shifts on Graphs: An Invariance Perspective, ICLR 2022\n\n[2] Learning Invariant Graph Representations for Out-of-Distribution Generalization, NeurIPS 2022\n\n[3] Learning Substructure Invariance for Out-of-Distribution Molecular Representations, NeurIPS 2022\n\n[4] Dynamic Graph Neural Networks Under Spatio-Temporal Distribution Shift, NeurIPS 2022\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the detailed comments. Responses are as follows.\n\n**Q1.1:** The definition of “environment”.\n\n**A1.1:** Thanks for your comment. We would clarify that we have explained “environment” from the perspective of **latent factor** (lines 88-94), **real-world explanations** (lines 100-104, Figure 1(a)), and **formal definition** (line 111). In short, environments are latent factors, where the ground-truth labels are inaccessible. The impact of environments causes relationships on dynamic graphs to be multi-attribute. To model diverse spatio-temporal environments, the ego-graphs of each node are disentangled and processed in $K$ embedding spaces.\n\n---\n\n**Q1.2:** Whether environment changes with T. Give evident correlations.\n\n**A1.2:** Thanks for your question. Environment is **time-dependent** (past classmate, current colleague). Note, time-independent is a special case, e.g., regions near the equator are always summer, shown in Figure 1(a). EAGEL doesn’t require explicit correlations between time and environment. Instead, EAGLE infers distributions of latent environments with multi-label $\\mathbf{y}$, mixing with time index $t$ and environment index $k$. We will add further clarifications in the revision.\n\n---\n\n**Q2:** How $K$ is determined? What’s the relationship between $K$ and graph?\n\n**A2:** Thanks for your question. We adopt a **warm-up mechanism** to determine $K$. We evaluate the performance of the first 10 epochs on the validation set to find the most suitable $K$, and fix it for the rest of training. We also add a parameter sensitivity experiment on COLLAB, which shows the impact of $K$ on model performance. We will add this in the revision and leave the study of how to adaptively determine $K$ for each node as future work.\n\n| $K$ | 2 | 4 | **6** | 8 | 10 |\n| --- | --- | --- | --- | --- | --- |\n| AUC (w/o OOD) | 80.33±1.29 | 81.17±1.04 | **84.41±0.87** | 83.65±0.79 | 81.94±1.03 |\n\n---\n\n**Q3.1:** Assumption 1 emulates a significant amount of existing works [1-4].\n\n**A3.1:** Thanks for your comment. Assumption 1 is **a universally acknowledged and widely accepted assumption** in OOD works based on the Independent Causal Mechanism and Invariant Learning theory [1-4]. **However**, most related works don’t state that they can be optimized to satisfy this assumption. Proposition 3 in our work proves Assumption 1 can be satisfied by optimizing EAGLE (Appendix C.3).\n\n---\n\n**Q3.2:** Assumption 1 seems to have a miswritten part (b).\n\n**A3.2:** Thanks for your careful and professional review. We revisit relevant literature and confirm it was a **typo**, i.e., $\\epsilon$ should be placed outside the brackets. We have re-checked that the typo will not affect Assumption 1 or the related propositions and proofs. We will correct this in the revision. \n\n---\n\n**Q4.1:** Notations are confusing and difficult to read. Why $\\mathbf{z}$ is used to represent results of set operation?\n\n**A4.1:** Thanks for your questions. We use $\\mathbf{z}$ to denote “embeddings”. $\\mathbf{z}$ with different super/subscripts introduces extra meaning. Explanations for all $\\mathbf{z}$ are listed in Appendix A. To avoid confusion, we will update $\\mathbf{z}$ in line 134 to $\\mathbf{Z}$ in the revision. We will further clarify the notations.\n\n---\n\n**Q4.2:** The meanings of $\\mathbf{e}$ and $s$.\n\n**A4.2:** Thank you for your question. \n\n- $\\mathbf{e}$ means multiple latent environments (lines 88-89). We explicitly define $\\mathbf{e}_v$ = {$\\mathbf{e}_k$}$_1^K$ in line 111, which means the multiple latent environment of node $v$ is a compound of $K$ surrounding environments.\n- $s$ is the element in $\\mathcal{S} _{ob} \\cup \\mathcal{S} _{ge}$ (Eq. (15)), i.e., the instances sampled from the observed and generated environment samples.\n\nDetailed explanations for $\\mathbf{e}$ and $s$ are listed in Appendix A. \n\n---\n\n**Q5:** More explanation about Proposition 1 and Proposition 2.\n\n**A5:** Thank you for your suggestions. \n\n- **[Proposition 1]** introduces loss function $\\mathcal{L}_{\\mathrm{ECVAE}}$ (Eq. (8)) to train ECVAE. ECVAE is realized by fully connected layers with the optimization goal in Eq. (C.6). To make it tractable, we apply MCMC sampling and reparameterization tricks, and reach the final optimization goal for ECVAE as Eq. (8).\n- **[Proposition 2]** solves a dynamic programming problem to obtain $\\mathbb{I}^\\star(\\cdot)$ with proofs in Appendix C.2. The target is to find a partition dividing all patterns into (in)variant set with the max difference between the variance means. Suppose $\\mathrm{Var}(\\mathbf{z}_v^{\\mathbf{e}\\prime})$ is [0.1, 0.2, 0.3, 0.4, 0.9], then the optimal partition is [0.1, 0.2, 0.3, 0,4] and [0.9] (with a larger mean difference) rather than [0.1, 0.2, 0.3] and [0.4, 0.9]. An optimal partition can always be found for each node, which contributes to the generalization.\n\nWe will provide further explanations in the revision.\n\n---\n\n**Q6:** The absolute statement, “Existing works fail to generalize under distribution shifts ...” overlooks recent work DIDA addressing distribution shifts.\n\n**A6:** Thanks for your comment. We clarify that our original sentence is “**most** existing works fail to generalize under distribution shifts. **DIDA [84] is the sole prior work** that tackles ......” (lines 303-305). We also express the exactly same meaning in lines 427-431 (Appendix F.2). We respectfully think our sentence clearly states the related works and is not an absolute statement.\n\n---\n\n**Q7:** Sentence on lines 140-141 is ambiguous. How can we learn “ground-truth” distribution?\n\n**A7:** Thanks for your question. We clarify that this sentence does not imply EAGLE could learn the ground-truth distribution. By “**regard**” the node embeddings obtained by EA-DGNN as environment samples drawn from the ground-truth distribution, we can **infer** the ground-truth distribution with the observed samples by ECVAE. We will further clarify our paper to avoid potential misunderstandings."}]

Author rebuttal:

Meta-review: This paper proposes a novel environment-aware dynamic graph learning framework for out-of-distribution generalization. In particular, the proposed framework models complex coupled environments and exploits spatial-temporal invariant patterns. Reviewers agreed that this paper studies an important problem, the proposed framework is novel, and extensive experiments are convincing. Meanwhile, reviewers raised some concerns regarding the concepts of environments, discussions of related work, and paper writing. The authors' rebuttal has successfully addressed most of the concerns. Also, the authors are strongly encouraged to incorporates the suggestions from reviewers to their final version.
Decision: Accept (poster)