Dynamic Graph Neural Networks Under Spatio-Temporal Distribution Shift
Authors: Zeyang Zhang
Xin Wang
Ziwei Zhang
Haoyang Li
Zhou Qin
Wenwu Zhu
Venue: NeurIPS 2022 Accept (2022)

Abstract: Dynamic graph neural networks (DyGNNs) have demonstrated powerful predictive abilities by exploiting graph structural and temporal dynamics. However, the existing DyGNNs fail to handle distribution shifts, which naturally exist in dynamic graphs, mainly because the patterns exploited by DyGNNs may be variant with respect to labels under distribution shifts. In this paper, we propose to handle spatio-temporal distribution shifts in dynamic graphs by discovering and utilizing {\it invariant patterns}, i.e., structures and features whose predictive abilities are stable across distribution shifts, which faces two key challenges: 1) How to discover the complex variant and invariant spatio-temporal patterns in dynamic graphs, which involve both time-varying graph structures and node features. 2) How to handle spatio-temporal distribution shifts with the discovered variant and invariant patterns. To tackle these challenges, we propose the Disentangled Intervention-based Dynamic graph Attention networks (DIDA). Our proposed method can effectively handle spatio-temporal distribution shifts in dynamic graphs by discovering and fully utilizing invariant spatio-temporal patterns. Specifically, we first propose a disentangled spatio-temporal attention network to capture the variant and invariant patterns.  Then, we design a spatio-temporal intervention mechanism to create multiple interventional distributions by sampling and reassembling variant patterns across neighborhoods and time stamps to eliminate the spurious impacts of variant patterns.  Lastly, we propose an invariance regularization term to minimize the variance of predictions in intervened distributions so that our model can make predictions based on invariant patterns with stable predictive abilities and therefore handle distribution shifts. Experiments on three real-world datasets and one synthetic dataset demonstrate the superiority of our method over state-of-the-art baselines under distribution shifts. Our work is the first study of spatio-temporal distribution shifts in dynamic graphs, to the best of our knowledge.

Dynamic Graph Neural Networks Under Spatio-Temporal Distribution Shift
Zeyang Zhang'; Xin Wang Ziwei Zhang', Haoyang Li', Zhou Qin', Wenwu Zhu
'Tsinghua University, AAliabaa Group
go-zzangg00mails.tsiiieee wwwplhsa.tiinnnneeeee ediph en, (xin_vang, zwzhang)(tsinghha. edu en,
lihy18@mails.
twwggghaa twingaua..nneeee edu. en, ginzhou. wwwzhoooalllaaaaaiinnaa wta.aaaa.a..i..iiaaaaaaaaaaaaaaa
wwzhultainghua.en wwwpeeinnnuaauuuuu...m.oe edu.cn
Abstract
Dynamic graph neural networks (DyGNNs) have demonstrated powerful predictive abilities by exploiting graph structural and temporal dynamics. However, the ex- isting DyGNNs fail to handle distribution shifts, which naturally exist in dynamic graphs, mainly because the patterns exploited by DyGNNs may be variant with respect to labels under distribution shifts. In this paper, we propose to handle spatio-temporal distribution shifts in dynamic graphs by discovering and utilizing invariant patterns, i.c., structures and features whose predictive abilities are stable across distribution shifts, which faces key challenges: 1) How to discover the complex variant and invariant spatio-temporal patterns in dynamic graphs, which involve both tin-varying graph structures and node features. 2) How to handle opapool distribution shifts with the discovered variant and invariant pat- terns. To tackle these challenges, we propose the Disentangled Intervention based Dynamic graph Attention networks (DIDA). Our proposed method can effectively handle spatio-temporal distribution shifts in dynamic graphs by discovering and fully utilizing invariant spatio-temporal patterns. Specifically, we first propose a disentangled spatio-temport attention network to capture the variant and invariant patterns. Then, design spatio-temporal intervention mechanism create multiple interventional distributions by sampling and reassembling variant patterns across neighborhoods and time stamps to eliminate the spurious impacts of variant patterns. Lastly, we propose an invariance regularization term to minimize the variance of predictions in intervened distributions that model make predictions based on invariant patterns with stable predictive abilities and there- fore handle distribution shifts. Experiments synthetic dataset demonstrate the superiority of our method over state-of-the-art baselines under distribution shifts. Our work is the first study of spatio-temporal distribution shifts in dynamic graphs, to the best of our knowledge.
three real-world datasets and
Introduction
Dynamic graphs widely exist in real-world applications, including financial networks 2 social networks 3 4. traffic networks 5 6) etc. Distinct from static graphs, dynamic graphs can represent temporal structure and feature patterns, which more complex yet common in reality. Dynamic graph neural networks (DyGNNs) have been proposed to tackle highly complex structural and temporal information over dynamic graphs, and have achieved remarkable progress in many predictive tasks
'This work was done during author's internship at Alibaba Group Corresponding authors
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Nevertheless, the existing DyGNNs fail to handle exist in dynamic graphs for various reasons such as survivorship bias (9. selection bias [T] [.]. trending [12], etc. For example, in financial networks, external factors like period or market would affect the correlations between the payment flows and transaction illegitimacy [3]. Trends or commu- nities also affect interaction patterns in coauthor networks [14] and recommendation networks [I5]. If DyGNNs highly rely on spatio-temporal patterns which are variant under distribution shifts, they will inevitably fail to generalize well to the unseen test distributions.
distribution shifts, which naturally
To address this issue, in this paper, we study the problem of handling shifts in dynamic graphs through discovering and utilizing invariant patterns, i.e., structures and features whose predictive abilities are stable across distribution shifts, which remain unexplored in the literature. However, this problem is highly non-trivial with the following challenges:
distribution
How to discover the complex variant and invariant which include both graph structures and node features varying through time?
patterns in dynamic graphs,
How to handle spatio-temporal distribution shifts in principled manner with discovered variant and invariant patterns?
To tackle these challenges, we propose a novel DyGNN named Disentangled Intervention-baat Dynamic Graph Attention Networks (DIDA Our proposed method handles distribution shifts well by discovering and utilizing invariant spatio-temporal patterns with stable predictive abilities. Specifically, we first propose a disentangled spatio-temporal attention network to capture the variant and invariant patterns in dynamic graphs, which enables each node to attend to all its historic neighbors through a disentangled attention pessage-passing mechanism. Then, inspired by causal inference literatures [66 we propose a
intervention mechanism to create multiple intervened distributions by sampling and reassembling variant patterns across neighborhoods and time, such that spurious impacts of variant patterns can be climinated. To tackle the challenges that i) variant patterns are highly entangled across nodes and ii) directly generating and mixing up subsets of structures and features to do intervention is computationally expensive, we approximate the intervention process with summarized patterns obtained by the disentangled spatio-temporal attention network instead of original structures and features. Lastly, we propose an invariance regularization term minimize prediction variance in multiple intervened distributions. In this way, our model can capture and utilize invariant patterns with stable predictive abilities to make predictions under distribution shifts. Extensive experiments demonstrate the superiority of our proposed method over state-of-the-as baselines under distribution shifts. The contributions of our work are summarized as follows:
one synthetic dataset and three real-world datasets
We propose Disentangled Intervention- based Dynamic Graph Attention Networks (DIDA), which can handle spatio-tempone distribution shifts in dynamic graphs. This is the first study of spatio-temporal distribution shifts in dynamic graphs, to the best of our knowledge.
We propose a disentangled spatio-temporal attention network to capture variant and invariant graph patterns. We further design ppatio-temporda intervention mechanism to create multiple intervened distributions and an invariance regularization term based on causal inference theory to enable the model to focus invariant patterns under distribution shifts.
Experiments three real-world datasets and one synthetic dataset demonstrate the superiority of our method over state-of-the-an baselines.
2 Problem Formulation
In this section, we formulate the problem of spatio-temporal distribution shift in dynamic graphs.
Dynamic Graph. Consider graph G with the node set V and the edge set E. A dynamic graph can be defined as G (( where T is the number of time stamps, g = (V*, EE) is the graph slice at time stamp f, V = U V", ع = U gt_ For simplicity, a graph slice is also denoted as g'= = (X', A²), which includes node features and adjacency matrix at time f. We use G to denote random variable of g
Our codes are publicly available http:///ghuubbbco//wwwneegg/////

---

Spatio-Temporal Intervention Mechanism
Original Distribution
Intervened Distribution
Disentangled Dynamic Graph Attention Networks
Invariance Loss
Spatial- temporal
Invariant Pattern
Temporal
Spatial
a1
a3
a3
bz
a3
Lm
Lm
Lm
a3
t=1
t=2
t=3
Varlant
do = Var,(Lmldo((p= s))
Pattern
(L + do)
Figure I: The framework our proposed method DIDA. (Bottom left) For given dynamic graph with multiple timestamps, the disentangled dynamic graph attention networks first obtain summariza- tions of high-order invariant and variant patterns by disentangled spatio-temporal message passing. (Top) Then the spatio-temporal intervention mechanism creates multiple intervened distributions by sampling and reassembling variant patterns across space and time for each node. (Bottom right) Last, invariance loss is calculated by using samples from intervened distributions to optimize the model so that it can focus on invariant patterns to make predictions.
Prediction tasks. For dynamic graphs, the prediction task can be summarized as using past graphs to make predictions, i... p( PYY'G', G ..... G')==(Y''' l where label Y can be node properties or occurrence of links between nodes at time t + 1. In this paper, we mainly focus node-level tasks,
which are commonly adopted in dynamic graph literatures 7 K. Following [8 19 we factorize the distribution of graph trajectory into ego-graph trajectories, i.e. p(Y² G II p(y" G.!.). ego-graph induced from node u at time defined as g (X At) where A the adjacency matrix including all edges in node v's L-hop neighbors time t, i.e. A and X includes the features of nodes in A' The optimization objective to learn an optimal predictor with empirical risk minimization
min Biy Bett
(l:t)) (y' wt
where So is a learnable dynamic graph neural networks, We use G y' f to denote the random variable of the ego-graph trajectory and its label, and G. .y" refer to the respective instances.
Spatio-temporal distribution shift. However, the optimal predictor trained with the training distribution may not generalize well to the distribution when there exists distribution shift problem. In the literature of dynamic graph, researchers are devoted to capture laws of network dynamics which stable in systems
20
21 22
23 24 Following them, we assume the conditional Y"
distribution is the same Ptr (Y" G Y
G 1s ), and only consider the covariate shift problem
where Ptr (1:t) Pte
Besides temporal distribution shift which naturally exists time- and structural distribution shift in non-suclidean data 22 18 30)
varying data 25
26
27
there exists much more complex spatio-temporal distribution shift in dynamic graphs. example, the distribution of ego-graph trajectories may vary across periods communities.

---

3 Method
In this section, we propose Disentangled Intervention-base Dynamic Graph Attention Networks (DIDA) to handle spatio-temporal distribution shift in dynamic graphs. First, propose disentan- gled dynamic graph attention network to extract invariant and variant spatio-temporal patterns. Then we propose spatio-temporal intervention mechanism to create multiple intervened data distributions. Finally, we optimize the model with invariance loss to make predictions relying on invariant patterns.
3.1 Handling
Distribution Shift
Spatio-Tempore Pattern. In recent decades of development of dynamic graphs, some scholars endeavor to conclude insightful patterns of network dynamics to reflect how real-world networks evolve through time [3 32
For example. the laws of triadic closure describe that two nodes with common neighbors (patterns) tend to have future interactions in social networks [35] 36 23
33 34]
Besides structural information, node attributes are also an important part of the patterns, e.g., social interactions can be also affected by gender and age [77. Instead of manually concluding patterns, we aim at learning the patterns using DyGNNs so that the more complex spatio-temporal patterns
with mixed features and structures can be mined in dynamic graphs. Therefore, we define the spatio-temporal pattern used for node-level prediction as a subset ego-graph trajectory
('(v) = (G.
(2)
where m.) selects structures and attributes from the ego-graph trajectory. In 23 the pattern can be explained as open triad with similar neighborhood, and the model tend to make link predictions to close the triad with Kt, = fo Pt (u). P' (')) based on the laws of triadic closure [38]. DyGNNs aim at exploiting predictive apatio-temports power of some patterns may vary across periods or communities due to spatio-tempore distribution shift. Inspired by the causal theory [16 17), make the following assumption
patterns to boost prediction ability. However, the predictive
Assumption For given task, there exists a predictor f(-) , for samples (g):t ,yy) from any distribution, there exists an invariant pattern ((() and variant pattern Pt (v) such that y (()( + c and (u) PP i.e., y (P((v) PP))).
Assumption shows that invariant patterns (v) are sufficiently predictive for label y and can be exploited across periods and communities without adjusting the predictor, while the influence of variant patterns P Pi(U)) (v) on yt is shielded by the invariant patterns.
Training Objective. Our main idea is that to obtain better generalization ability, the model should rely on invariant patterns instead of variant patterns, as the former is sufficient for prediction while the predictivity of the latter could be variant under distribution shift. Along this, our objective can be transformed to
min Byy (Kv..g"")))p (y CCo, (P(())),))) 6,
(3)
s.t (e y 1 (o) (v).
where (.) make predictions based on the invariant patterns, dee (.) aims at finding the invariant patterns. Backed by causal theory [16
17], it can be transformed into
min (y (r (... C(fo (d,,, (C.: v'))+ 91
(4)
Varr (Brr" ott (y' (d C(fo, (0e, (G! )), y²))
where 'do' denotes do-calculas to intervene the original distribution 39 17 S denotes the inter- vention set and is a balancing hyperparameter. The idea can be informally described that as in Eq. 33, variant patterns PS have no influence on the label y' given the invariant patterns Pf then the prediction would not be varied if we intervene the variant patterns and keep invariant patterns untouched. More details about the connections between objective Eq. (3) and Eg. 4 can be found in Appendix.
Remark 1 Minimizing the variance term in Eq. 4 help the model to satisfy the constraint of y' 1 (v) (e) in Eq. 3 i.e. ply' P ()()) P (v)) p(y" (v))))

---

3.2 Disentangled Dynamic Graph Attention Networks
Dynamic Neighborhood. To simultaneously consider the spatio-temporal information, we define the dynamic neighborhood as (u) = {v: (u, E E which includes all nodes that have interactions with node u at time t.
Disentangled Spatio-temporal Graph Attention Layer. To capture spatio-temporal pattern for each node, we propose spatio-temporal graph attention to enable each node to attend to its dynamic neighborhood simultaneously. For a node u time stamp and its neighbors v E N (u), Vt' S t, we calculate the Query-Key-Van Value vectors as:
q = Wg (H,))) K. W& TE(t'), vf (
(5)
where h denotes the representation of node u at the time stamp I, q. k, v represents the query, key and value vector, respectively, and we omit the bias term for brevity. TE(t) denotes temporal encoding techniques to obtain embeddings of time t so that the time of link occurrence can be considered inherently [40 41). Then, we can calculate the attention scores among nodes in the
dynamic neighborhood to obtain the structural masks
my Softmax q K2
my = Softmax 9- 9-k" k2
(6)
Vd
where denotes feature dimension, my and my represent the masks of invariant and variant structural patterns. In this way, dynamic neighbors with higher attention scores in invariant pattems will have lower attention scores in variant ones, which means the invariant and variant patterns have negative correlation. To capture invariant featural pattern, adopt learnable featural mask m, Softmax (w,) (w)) to select features from the messages of dynamic neighbors. Then the messages of dynamic neighborhood can be summarized with respective masks,
z (u) Agg, V O my)
z (u) Aggv (my. (my.v)
where Agg(-) denotes aggregating and summarizing messages from dynamic neighborhood. To fur- ther disentangle the invariant and variant patterns, we design different aggregation functions Agg, (-) and (-) to summarize specific messages from masked dynamic neighborhood respectively. Then the pattern summarizations are added up as hidden embeddings to be fed into subsequent layers.
h 2) (u)
Overall Architecture. The overall architecture is stacking of spatio-temporal graph attention layers. Like classic graph peessage-passing networks, this enables each node to access high-order dynamic neighborhood indirectly, where zj (u) and z (u) at l-th layer can be a summarization of invariant and variant patterns in (-order dynamic neighborhood. In practice, the attention can be easily extended to multi-head attention
42
to stable the training process and model multi-faceted graph evolution 43
3.3 Spatio-Temporal Intervention Mechanism
Direct Intervention. One way of intervening variant pattern distribution as Eq. (4) is directly generating and altering the variant patterns. However, this is infeasible in practice due to the following reasons: First, since it has to intervene the dynamic neighborhood and features node- wisely, the computational complexity is unbearable. Second, generating variant patterns including time-varying structures and features another intractable problem.
Approximate Intervention. To tackle the problems mentioned above, we propose to approximate the patterns P with summarized patterns z' found in Sec. 3.2 As 2 and z (u) act summarizations of invariant and variant spatio-temporal patterns for node u at time f, we approximate the intervention process by sampling and replacing the variant pattern summarizations instead of altering original structures and features with generated ones. To do spatio-temporal intervention, we collect variant patterns of all nodes all time, from which we sample one variant pattern replace the variant patterns of other nodes across time. For example, we can use the variant pattern of node u at time to to replace the variant pattern node time t
2 (u), 2 (u) z 277
(9)
5

---

As the invariant pattern summarization is kept the same, the label should not be changed. Thanks the disentangled spatio-temporal graph attention. we get variant patterns across neighborhoods and time, which can act natural intervention samples inside data so that the complexity of the generation problem can also be avoided. By doing Eq. (9) multiple times, we can obtaín multiple intervened data distributions for the subsequent optimization.
3.4 Optimization with Invariance Loss
Based on the multiple intervened data distributions with different variant patterns, we next optimize the model to focus on invariant patterns to make predictions. Here, we introduce invariance loss to instantiate Eq. 44. Let ž and zy be the summarized invariant and variant patterns, we calculate the task loss by only using the invariant patterns
L {(f(z)..)
(10)
where f(-) is the predictor. The task loss let the model utilize the invariant patterns to make predictions. Then calculate the mixed loss
L. = [=)((v,,))))))
(11)
where another predictor g(-) makes predictions using both invariant patterns zy and variant patterns 2₁- The mixed loss measure the model's s prediction ability when variant patterns are also exposed to the model. Then the invariance loss is calculated by
da Var ( Cm [do = =s))
(12)
where 'do' denotes the intervention mechanism as mentioned in Section. 33 measures the variance of the model's prediction ability under multiple intervened distributions. The final training objective is
The invariance loss
min L + AL
(13)
where the task loss L is minimized to exploit invariant patterns while the invariance loss Lao helps the model discover invariant and variant patterns, and À is hyperparameter balance between two objectives. After training, we only adopt invariant patterns to make predictions in the inference stage. The overall algorithm summarized in Table T
Algorithm 1 Training pipeline for DIDA
Require: Training epochs L, number of intervention samples S, hyperparameter À for I 1..... . L do
2: Obtain ziy z for each node and time described in Section 3.2
3: Calculate task loss and mixed loss as Eq. (TO) and Eq. (1I
4: Sample S variant patterns from collections of ziy to construct intervention set S
5: for s do
6: Replace the nodes' variant pattern summarizations with Section 3.3
7: Calculate mixed loss as Eq. (T]
8: end for
9: Calculate invariance loss as Eq.
2
10: Update the model according Eq. 13
11:
end for
4
Experiments
In this section, we conduct extensive experiments to verify that our framework can handle spatio- temporal distribution shifts by discovering and utilizing invariant patterns. More Details of the settings and other results can be found in Appendix.
Baselines. We adopt several representative GNNs and Qut-of-Dissrrbbuttoo((OO1)) generalization methods as our baselines:
Statie GNNs: GAF representative static GNN with stacking of graph convolutions; VGAE 44 further introduces variational variables into GAE

---

Dynamic GNNs: GCRN 45 a representative dynamic GNN that first adopts a GCN 44 to
obtain node embeddings and then a GRU 446 model the dynamics; EvolveGCN [33 adopts
LSTM [7] or GRU [46] to flexibly evolve the GCN[44] parameters instead of directly learning
the temporal node embeddings; DySAT models dynamic graph using structural and temporal
self-attention.
48 aims at learning an invariant predictor which minimizes the empirical risks for all training domains; GroupDRO 4 reduces differences in risk across training domains to reduce the model's 's sensitivity to distributional shifts; V-REx (50) puts more weight on training domains with larger errors when minimizing empirical risk.
OOD generalization methods: IRM
4.1 Real- world Datasets
Settings. We use real-world dynamic graph datasets, including COLLAB, Yelp and Transaction. We adopt the challenging inductive future link prediction task, where the model exploits past graphs to make link prediction in the next time step. Each dataset can be split into several partial dynamic graphs based on its field information. For brevity, we use 'w/ DS and "w/o DS' to represent test data with and without distribution shift respectively. To measure models' performance under spatio- temporal distribution shift, we choose one field 'w/ DS' and the left others are further split into training, validation and test data ('w/o DS') chronologically. Note that the 'w/o DS' is a merged dynamic graph without field information and "w/ DS is unseen during training, which is more practical and challenging in real-world scenarios. More details on their spatio-temporal distribution shifts are provided in Appendix. Here we briefly introduce the real-world datasets as follows
is an academic collaboration dataset with papers that were published during 1990-2006. Node and edge represent author and coauthorship respectively. Based on the field of co-authored publication, each edge has the field information including "Data Mining". "Database" ", "Medical Informatics", "Theory" and "Visualization". The time granularity is year, including 16 time slices in total. We use "Data Mining" as 'w/ DS and the left as 'w/o DS'.
COLLAB [51
Yelp is a business review dataset, containing customer reviews on business. Node and edge represent customer/business and review behavior respectively. We consider interactions in five categories of business including "Pizza", " "American (New) Food", "Coffee & Tea ", "Sushi Bars" and "Fast Food" from January 2019 to December 2020. The time granularity is month, including 24 time slices in total. We use "Pizza" as 'w/ DS' and the left as 'w/ DS".
Transaction is secondary market transaction dataset, which records transaction behaviors of users from 10th April 2022 to 10th May 2022. Node and edge represent user and transaction respectively. The transactions have categories, including "Pants", "Outwears", "Shirts" and "Hoodies". The time granularity is day, including 30 time slices in total. We use "Pants" " as 'w/ DS' and the left 'wo DS'.
Results. Based on the results on real-world datasets in Table. we have the following observations:
Baselines fail dramatically under distribution shift: 1) Although DyGNN baselines perform well on test data without distribution shift, their performance drops greatly under distribution shift. In particular, the performance of DySAT, which is the best-performed DyGNN in 'w/o DS', drop by nearly 12%, 12% and 5% in 'w/ DS In Yelp and Transaction, GCRN and EGCN even underperform static GNNs, GAE and VGAE. This phenomenon shows that the existing DyGNNs may exploit variant patterns and thus fail to handle distribution shift. 2) Moreover, as generalization baselines are not specially designed consider spatio-temporal distribution shift in dynamic graphs, they only have limited improvements in Yelp and Transaction. In particular, they rely on ground-truth environment labels to achieve OOD generalization, which are unavailable for real dynamic graphs. The inferior performance indicates that they cannot generalize well without accurate environment labels, which verifies that lacking environmental labels is also key challenge for handling distribution shifts of dynamic graphs.
Our method can better handle distribution shift than the baselines, especially in stronger distribu- tion shift. DIDA improves significantly over all baselines in 'w/ DS' for all datasets. Note that
http::/www..miier.mmclllllllal
5 "hups://www.chh wwt.:o/.wwll...c/aaaaaa..e com/dataset "Collected from Alibaba.com
7

---

Table 1: ResUlt)AAUC)) of different methods on real-workd datasets. The best results are in bold and the second- best results are underlined. "w/o DS' and 'w/ DS' denote test data with and without distribution shift.
Model
COLLAB
Yelp
Transaction
Test Data
w/o DS
w/ DS
w/o DS
w/ DS
w/o DS
w/ DS
GAE
77.15
74.04
70.67
64.45+t:.02
71.90
73.44:10.1
VGAE
86.47=0.04
74.95
76.54
65.33++143
79.31 =0.37
75,66::0.3
GCRN
82.78=0.54
69.72:40.55
68.59
54.68+17.59
78.99
71.24
EGCN
86.62.10.95
76.151091
78.21 10.03
53.82.12.6
1.:22
66.49
DySAT
88.77.1.22
76.591..20
78.87 10.57
66.0911142
81.55 10.66
76.18
IRM
87.9610090
75.42.10.87
66.49
56.02.16.08
81.65
75.61
VREx
88.31
76,24
19.04
66,41
81.72
76,24
GroupDRO
88.76=0.12
76.33++029
79.38
66.97+061
81,50
75.92+10.7
DIDA
91.97
81.87
78.22+4040
75.92:10.90
83.08
77.61 1:0.59
Table 2: Results(AUC%) of different methods on synthetic dataset. The best results are in bold and the second-best results underlined. Larger p denotes higher distribution shift level.
Model Vp
0.4
0.6
0.8
Split
Train
Test
Train
Test
Train
Test
GCRN
69. 19.60+1.14
72.57
74.71
72.29:+047
75.6940007
67.26++0.22
EGCN
78.82+1AM 40
69. -.5.
19.47
62.70
81.07=4.10
60. 13
DySAT
84.71
70.24+
89.77
64.01
94.02++1.2 19
62. 194.99
IRM
85.20+0007
69.40=u009
89.48=0022
63.97=0.37
95.02++0.09
62.66::0.35
VREx
84.77+0.84
10.44+1.08
89.81
63.994002
94.06+11.30
62,21
GroupDRO 84.78
70.30+1.23
89.90=0.11
64.05
94.08+11.3
62, 03
DIDA
87.92+0.92
85.20+0084
91.222#059
82.89
92.72+2.16
72.59
Yelp has stronger temporal distribution shift since COVID-19 happens in the midway, strongly affecting consumers' behavior in business, while DIDA outperforms the most competitive baseline GroupDRO by 9% in 'w/ DS In comparison to similar field information in Yelp (all restaurants) and Transaction (all costumes), COLLAB has stronger spatial distribution shift since the fields are more different to each other, while DIDA outperforms the most competitive baseline DySAT by 5% in 'w/ DS'.
4.2 Synthetic Dataset
Settings. To evaluate the model's generalization ability under spatio-temporal distribution shift, following [18), we introduce manually designed shifts in dataset COLLAB with all fields merged. Denote original features and structures X E gg and A {0, 1JNNN, For each time uniformly sample E(+) positive links and (1 ((()) negative links in A 4+1 Then they are factorized into variant features X E N with property of structural preservation. Two portions of features concatenated as X X X:) as input node features for training and inference. The sampling probability p(t)= = clip(p + (cos(t), (t), 0, 1) refers to the intensity of shifts, where the variant features X constructed with higher p(t) will have stronger correlations with future link A 1+1 We set Prest = 0.1, Test 0, train = 0.05 and vary Ptrain in from 0.4 to 0.8 for evaluation. Since the correlations between X and label A vary through time and neighborhood, patterns include X are variant under distribution shifts. As static GNNs can not support time-varing features, we omit their results.
Results. Based on the results on synthetic dataset in Table.
2 we have the following observations:
Our method can better handle distribution shift than the baselines. Although the baselines achieve high performance when training, their performance drop drastically in the test stage, which
8

---

shows that the existing DyGNNs fail to handle distribution shifts. In terms of test results, DIDA consistently outperforms DyGNN baselines by a significantly large margin. particular, DIDA surpasses the best- rest-performed baseline by nearly 13%/10%/5% in test results for different shift levels. For the general OOD baselines, they reduce the variance in some cases while their improvements are not significant. Instead, DIDA is specially designed for dynamic graphs and can exploit the invariant spatio-temporal patterns to handle distribution shift.
Our method can exploit invariant patterns to consistently alleviate harmful effects of variant patterns under different distribution shift levels. As shift level increases, almost all baselines increase in train results and decline in test results. This phenomenon shows that as the relationship between variant patterns and labels goes stronger, the existing DyGNNs become more dependent on the variant patterns when training, causing their failure in test stage. Instead, the rise in train results and drop in test results of DIDA are significantly lower than basclines, which demonstrates that DIDA can exploit invariant patterns and alleviate the harmful effects of variant patterns under distribution shift.
4.3 Complexity Analysis
We analyze the computational complexity of DIDA as follows. Denote VV and |E] as the total number of nodes and edges in the graph, respectively, and d as the dimensionality of the hidden representation. The spatio-temporal aggregation has a time complexity of O(FE) d [V]d)). The disentangled component adds constant multiplier 2, which does not affect the time complexity of aggregation. Denote Epp as the number of edges to predict and |S| as the size of the intervention set. Our intervention mechanism has time complexity of O(EE [[]]d) in training, and does not put extra time complexity in inference. Therefore, the overall time complexity of DIDA is O(EEl + IV|2 + Ep SS Sld). Notice that [S] is a constant. In summary, DIDA has a linear time complexity with respect to the number of nodes and edges, which is on par with the existing dynamic GNNs.
and usually set as small
4.4 Ablation study
In this section, conduct ablation studies to verify the effectiveness of the proposed spatio-temporal intervention mechanism and disentangled graph attention in DIDA.
Spatio-temport intervention mechanism. We remove the intervention mechanism men- tioned in Sec 3.3 From Figure 2 we can see that without spatio-temporal intervention, the model's performance drop significantly especially in the synthetic dataset, which ver- ifies that our intervention mechanism helps the model to focus on invariant patterns to make predictions.
DIDA
DIDA
80
DIDA w/o I&D
AUC (%)
75
70
Disentangled graph attention. We further remove the disentangled attention mentioned in Sec From Figure we can see that dis- entangled attention is a critical component in the model design, especially in Yelp dataset. Moreover, without disentangled module, the model unable to obtain variant and invari- ant patterns for the subsequent intervention.
COLLAB
Yelp
Transaction Synthedic
Figure 2: Ablation studies on intervention mechanism and disentangled attention, where 'w/o I' denotes re- moving the spatio-temporal intervention mechanism in DIDA and 'w/o I&D' further removes disentangled attention.
5 Related Work
Dynamic Graph Neural Networks. To tackle the complex structural and temporal information in dynamic graphs, considerable research attention has been devoted to dynamic graph neural networks (DyGNNs) 7 g. A classic of DyGNNs first adopt a GNN to aggregate structural information
for graph at each time, followed by a sequence model like RNN [52] 53 45] or temporal self-attention 43 to process temporal information. Another classic of DyGNNs first introduce

---

time-encoding techniques to represent each temporal link as function of time, followed by spatial to process structural information. To obtain more fine-grained continous node embeddings in dynamic graphs, some work further leverages neural interaction processes [56] and ordinary differential equation [57]. DyGNNs have been widely applied in real-world applications, including dynamic anomaly detection [58] event forecasting [59], dynamic recommendation [60]. social character prediction [6]]. user modeling [62], temporal knowledge graph completion [63]. etc. In this paper, we consider DyGNNs under spatio-temporal distribution shift, which remains unexplored in dynamic graph neural networks literature.
module like GNN or memory module 20 55 40
Out-of- Sit--f--Ditributionn Generalization. Most existing machine learning methods assume that the testing and training data are independent and identically distributed, which is not guaranteed hold in many real-world scenarios [64]. In particular, there might be uncontrollable distribution shifts between training and testing data distribution, which may lead to sharp drop of model performance. (OOD) generalization problem has recently become
To solve this problem, central research topic in various areas
665
66
Recently, several works attempt to handle
distribution shift on graphs [67 22 most related to our works handle distribution shifts on time-series data [25] 26 12 27 28 74]. Current works consider either only structural distribution shift for static graphs or only temporal distribution shift for time-series data. However, apatio-temporal distribution shifts in dynamic graphs more complex yet remain unexplored. To the best of our knowledge, this is the first study of spatio-temporal distribution shifts in dynamic graphs.
18
68
71 72 73 Another classic of OOD methods
Disentangled Representation Learning. Disentangled representation learning aims to characterize the multiple latent explanatory factors behind the observed data, where the factors are represented
by different vectors 775 Besides its applications in computer vision 776 77 78
79 80 and
recommendation [8
85 86], several disentangled GNNs have proposed to generalize
disentangled representation learning in graph data recently. DisenGCN [87 and IPGDN [88 utilize the dynamic routing mechanism to disentangle latent factors for node representations. FactorGCN (89
decomposes the input graph into several interpretable factor graphs. DGCL 190] 91] aim to learn
disentangled graph-level representations with self-supervision. Some works factorize deep generative models based node, edge, static, dynamic factors [92] spatial, temporal, graph factors [93] to achieve interpretable dynamic graph generation.
Conclusion
In this paper, we propose Disentangled Intervention-basee Dynamic Graph Attention Networks (DIDA) to handle spatio-temporal distribution shift in dynamic graphs. First, we propose a disen- tangled dynamic graph attention network to capture invariant and variant spatio-temporal patterns. Then, based on the causal inference literature, we design a spatio-temporal intervention mechanism to create multiple intervened distributions and propose an invariance regularization term to help the model focus on invariant patterns under distribution shifts. Extensive experiments on three worldw datasets and one synthetic dataset demonstrate that our method can better handle spatio-temporal distribution shift than state-of-the-art baselines. One limitation is that in this paper we mainly consider dynamic graphs in scenarios of discrete snapshots, and we leave studying spatio-temports distribution shifts in continous dynamic graphs for further explorations.
Acknowledgements
This work was supported in part by the National Key Research and Development Program of China No. 2020AAA0106300 National Natural Science Foundation of China (No. 62250008, 62222209, 62102222, 62206149), China National Postdoctoral Program for Innovative Talents No. BX20220185 and China Postdoctoral Science Foundation No. 2022M71 1813. All opinions, findings, conclusions and recommendations in this paper are those of the authors and do not necessarily reflect the views of the funding agencies.
References
[1] Diego 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-
10

---

reports and some reflections on the financial world. Chaus, Solitons & Fractals, 153:1 153:110 1440, 2021.
[2] 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 (SMDS), pages 184-191. IEEE, 2021.
[3] Tanya Y Berger- 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.
[4] Derek Greene, Donal Doyle, and Padraig Cunningham. Tracking the evolution of communities in dynamic social networks. 2010 international conference on advances social networks analysis and mining, pages 176- 183.183.100 IEEE, 2010.
[5] Hao Peng. Bowen Du, Mingsheng Liu, Mingzhe Liu, Shumei Ji, Senzhang Wang. Xu Zhang. and Lifang He. Dynamic graph convolutional network for long-term traflic flow prediction with reinforcement learning. Information Sciences, 578:401-416, 2021.
[6] Hao Peng. Hongfei Wang, Bowen Du, Md Zakirul Alam Bhuiyan, Hongyuan Ma, Jianwei Liu, Lihong Wang. Zeyu Yang. Linfeng Du, Senzhang Wang, al. Spatial temporal incidence dynamic graph neural networks for traffic flow forecasting. Information Sciences, 521:277-229 290, 2020.
[7] Joakim Skarding, Bogdan Gabrys, and Katarzyna Musial, Foundations and modeling of dynamic networks using dynamic graph neural networks: A survey. IEEE Access, 9:7914::55 1979433779668, 2021.
[8] Yuecai Zhu, Fuyuan Lyu, Chengming Hu, Xi Chen, and Xue Liu. Learnable encoder-decoder architecture for dynamic graph: A survey, arXiv preprint arXiv:2203. 10480, 2022.
[9] Stephen Brown, William Goetzmann, Roger G Ibbotson, and Stephen Ross. Survivorship bias in performance studies. The Review of Financial Studies, 5(4))553-580) 1992.
[10] Richard A Berk. An introduction to sample selection bias in sociological data. American sociological review, pages 386-398, 1983.
[11] Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi. Shift-robust guns: Overcoming the limitations of localized graph training data. Advances in Neural Information Processing Systems, 34, 2021.
[12] Taesung Kim, Jinhee Kim, Yunwon Tae, Cheonbok Park. Jang-Ho Choi, and Jaegul Choo. Reversible instance normalization for accurate time-series forecasting against distribution shift, In International Conference on Learning Representations, 2021.
[13] Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao Schardl, and Charles Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5363- 5370. 2020.
[14] Tian Jin, Qiong Wu, Xuan Ou, and Jianjun Yu. Community detection and co-author recommendation in co-author networks. International Journal of Machine Learning and Cybernetics, 12(2):997-609 2021.
[15] Wenjie Wang, Xinyu Lin, Fuli Feng, Xiangnan He, Min Lin, and Tat-Seng Chua. Causal representation learning for out-of-distributiin recommendation. In Proceedings of the ACM Web Conference 2022, pages 3562-3571, 2022.
[16] Judea Pearl et Models, reasoning and inference. Cambridge, UK: CombriägeUniieersttypresss, 19:2, 2000.
[17] Madelyn Glymour, Judea Pearl, and Nicholas P Jewell. Causal inference in statistics: A primer. John Wiley & Sons, 2016.
[18] Qitian Wu, Hengrui Zhang, Junchi Yan. and David Wipf. Handling distribution shifts graphs: An invariance perspective. arXiv preprint arXiv:2202.02466. 2022.
[19] Kexin Huang and Marinka Zitmik. Graph meta learning via local subgraphs. Advances in Neural Information Processing Systems, 33:5862-5874, 2020.
[20] Yanbang Wang, Yen-Yo Yu Chang. Yunyu Liu. Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. arXiv preprint MrXiv22111009974 2021.
11

---

[21] Zhenyu Qiu, Wenbin Hu, Jia Wu, Weiwei Liu, Bo Du and Xiaohua Jia. Temporal network embedding with high-order nonlinear information. In Proceedings the AAAI Conference on Artificial Intelligence. volume 34, pages 5436-5443, 2020.
[22] Hong Huang, Zixuan Fang, Xiao Wang. Youshan Miao, and Hai Jin. Motif-preserving temporal network embedding. In IJCAI, pages 1237-1243, 2020.
[23] Lekui Zhou, Yang Yang, Xiang Ren, Fei Wu, and Yueting Zhuang. Dynamic network embedding by modeling triadic closure process. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
[24] Rakshit Trivedi, Mehrdad Farajtabar, Prasenject Biswal, and Hongyuan Zha. Dyrep: Learning representa- tions over dynamic graphs. In International conference on learning representations, 2019.
[25] Jean Sean-Christophe Gagnon-Auded Kartik Ahuja, Bahhammad-Javal Darvishi- Darvishi-Bayazi Guillaume Dumas, and Irina Rish. Woods: Benchmarks for out-of of-diitribttiin generalization in time series tasks. arXiv preprint arXiv:2203.089 099778 2022.
[26] Yuntao Du, Jindong Wang, Wenjie Feng, Sinno Pan, Tao Qin, Renjun Xu, and Chongjun Wang. Adarnm: Adaptive learning and forecasting of time series. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 402 411, 2021.
[27] Praveen Venkateswaran, Vinad Muthusamy, Vatche Isahagian, and Nalini Venkatasubramaniin. Environ- ment agnostic invariant risk minimization for classification of sequential datasets. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1615-1624, 2021.
[28] Wang Lu, Jindong Wang, Yiqiang Chen, and Xinwei Sun. Diversify to generalize: Learning generalized representations for time series classification. 2021.
[29] Ying-Xin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. arXiv preprint arXiv:2201.12877 2022.
[30] Mucong Ding, Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Micah Goldblum, David Wipf,, Furong Huang, and Tom Goldstein. A closer look at distribution shifts and out-of-distribution generalization on graphs. 2021.
[31] Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, and Jari Saramäki. Temporal motifs in time-dependent networks. Journal of Statistical Mechanics: Theory and Experiment, 201 (11):P1 1005, 2011.
[32] Austin R Benson, David F Gleich, and Jure Leskovee. Higher-order organization of complex networks. Science, (6366))) 2016.
[33] Ashwin Paranjape, Austin R Benson, and Jure Leskovec. Motifs in temporal networks. Proceedings of the tenth ACM international conference on web search and data mining, pages 601-610, 2017.
[34] Marinka Zitnik, Rok Sosič, Marcus W Feldman, and Jure Leskovec. Evolution of resilience in protein interactomes across the tree of life. Proceedings of the National Academy of Sciences. (16110):446-44433 2019.
[35] James Coleman. Foundations social theory. Harvard university press, 1994.
[36] Hong Huang, Jie Tang, Lu Liu, JarDer Luo, and Xiaoming Fu. Triadic closure pattern analysis and prediction in social networks. IEEE Transactions on Knowledge and Data Engineering. 27(12):334-3338, 2015.
[37] Lauri Kovanen, Kimmo Kaski, János Kertész, and Jari Saramäki. Temporal motifs reveal homophily, gender-specific patterns, and group talk in call sequences. Proceedings of the National Academy of Sciences, 110(45):18070 0000:088777-1755.5.. 18075, 2013.
[38] Georg Simmel. The sociology of georg simmel, volume 92892. Simon and Schuster, 1950.
[39] Jin Tian, Changsung Kang, and Judca Pearl. A characterization of interventional distributions in semi- Markovian causal models. eScholarship. University of California, 2006.
[40] Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive representation learning temporal graphs. arXiv preprint 27X1:22002.07662 2020.
12

---

[41] 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 arXiv:2006.1663 10637. 2020.
[42] Ashish Vaswani, Noam Shazeer. Niki Parmar, Jakob Uszkoreit, Llion Jones. Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances neural information processing systems, 30, 2017.
[43] Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural representation learning on dynamic graphs via self- networks. In Proceedings of the 13th International Conference on Web Search and Data Mining, pages 519-527. 2020.
[44] Thomas N Kipf and Max Welling. Variational graph enoodencserss arXiv preprint arXiv:6611.07300 2016.
[45] Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. In International Conference on Neural Information Processing, pages 362 373. Springer, 2018.
[46] Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using ran encoder-decoder for statistical machine translation. In EMNLP, 2014.
[47] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):1735-1788 1997.
[48] Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez- Pazz Invariant risk minimization. arXiv preprint 1907:19007000993 2019.
[49] Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Percy Liang. Distributionally robust neural networks group shifts: On the importance of regularization for worst-case generalization. arXiv preprint arXiv:1911. 1.7331, 2019.
[50] David Krueger, Ethan Caballero, Joern-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. Out-of-distribution generalization via risk extrapolation (rex). In International Conference on Machine Learning, pages 5815-5826. PMLR, 2021.
[51] Jie Tang, Sen Wu, Jimeng Sun, and Hang Su. Cross-domain collaboration recommendation. In KDD'2012, 2012.
[52] Menglin Yang, Min Zhou, Marcus Kalander, Zengfeng Huang, and Irwin King. Discrete-time temporal network embedding via implicit hierarchical learning in hyperbolic space. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1975-1985, 2021.
[53] Li Sun, Zhongbao Zhang, Jiawei Zhang. Feiyang Wang, Hao Peng, Sen Su, and Philip S Yu. Hyperbolic variational graph neural network for modeling dynamic graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35. pages 4375 47735-433,222 2021.
[54] 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.
[55] Weilin Cong, Yanhong Wu, Yuandong Tian, Mengting Gu, Yinglong Xia, Mehrdad Mahdavi, and Chun- cheng Jason Chen. Dynamic graph representation learning via graph transformer networks. arXiv preprint arXiv:2111. 10447, 2021.
[56] Xiaofu Chang, Xuqin Liu, Jianfeng Wen, Shuang Li. Yanming Fang, Le Song, and Yuan Qi. Continuous- time dynamic graph learning via neural interaction processes. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 145 -54, 2020.
[57] Zijie Huang. Yizhou Sun, and Wei Wang. Coupled graph ode for learning interacting system dynamics. In KDD, pages 705-715, 2021.
[58] Lei Cai, Zhengzhang Chen, Chen Luo, Jiaping Gui, Jingchao Ni, Ding Li, and Haifeng Chen. Structural temporal graph neural networks for anomaly detection in dynamic graphs. In Proceedings of the 30th ACM international conference Information & Knowledge Management, pages 3747-3756, 2021.
[59] Songgaojun Deng, Huzefa Rangwala, and Yue Ning. Dynamic knowledge graph based multi-event forecasting. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1585-1595, 2020.
13

---

[60] Jiaxuan You, Yichen Wang, Aditya Pal, Pong Eksombatchai, Chuck Rosenburg, and Jure Leskovec. Hierarchical temporal convolutional networks for dynamic recommender systems. In The world wide web conference, pages 2236-2246, 2019.
[61] Yanbang Wang. Pan Li. Chongyang Bai, and Jure Leskovec. Tedic: Neural modeling of behavioral patterns in dynamic social interaction networks. In Proceedings of the Web Conference 202/, pages 693-705, 2021.
[62] Haoyang Li, Peng Cui, Chengxi Zang, Tianyang Zhang, Wenwu Zhu, and Yishi Lin. Fates of microscopic social ecosystems: Keep alive or dead? In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 668-676, 2019.
[63] Jiapeng Wu, Meng Cao, Jackie Chi Kit Cheung. and William L Hamilton. Temp: Temporal message passing for temporal knowledge graph completion. arXiv preprint arXiv:2010.03526, 2020.
[64] Zheyan Shen, Jiashuo Liu, Yue He, Xingxuan Zhang, Renzhe Xu, Han Yu, and Peng Cui. Towards out-of-distribution generalization: A survey. arXiv preprint arXiv:2108. 10088,3344,,.. 2021.
[65] Kaiyang Zhou, Ziwei Liu, Yu Qiao, Tao Xiang, and Chen Change Loy. Domain generalization: A survey. arXiv e-prints. pages arXiv-2103, 2021.
[66] Huaxiu Yao, Yu Wang. Sai Li, Linjun Zhang, Weixin Liang, James Zou, and Chelsea Finn. Improving out-of-distribution robustness via selective augmentation. Proceeding of the Thirty-ninth International Conference on Machine Learning, 2022.
[67] Haoyang Li, Xin Wang. Ziwei Zhang, and Wenwu Zhu. Out-of-distribution generalization on graphs: A survey. arXiv preprint urXiv:2202.07000 2022.
[68] Yongqiang Chen, Yonggang Zhang, Han Yang. Kaili Ma, Binghui Xie, Tongliang Liu, Bo Han, and James Cheng. Invariance principle meets out-of-distribution generalization on graphs. arXiv preprint a:Xiv:2202.05441, 2022.
[69] Yijian Qin. Xin Wang. Ziwei Zhang, Pengtao Xie, and Wenwu Zhu. Graph neural architecture search under distribution shifts. In International Conference on Machine Learning, pages 18083-18095. PMLR, 2022.
[70] Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu Zhu. Ood-gnn: disttriiittiiitoo generalized graph neural network. IEEE Transactions on Knowledge and Data Engineering, 2022.
[71] Zeyang Zhang, Ziwei Zhang, Xin Wang, and Wenwu Zhu, Learning to solve travelling salesman problem with hardness-adaptive curriculum. arXiv preprint XxXi:2204.03236, 2022.
[72] Shaohua Fan, Xiao Wang. Chuan Shi, Peng Cui, and Bai Wang. Generalizing graph neural networks on distriibbt graphs. arXiv preprint arXiv:2111. 10657, 2021.
[73] Haoyang Li, Ziwci Zhang, Xin Wang, and Wenwu Zhu. Learning invariant graph representations for out-of-distribution generalization. In Phirty--ixhh Conference on Neural Information Processing Systems, 2022.
[74] Huaxiu Yao, Caroline Choi, Yoonho Lee, Pang Wei Koh, and Chelsea Finn. Wild-time: benchmark of in-the-wild distribution shift over time. In Proceedings of the Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
[75] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. JEEE transactions on pattern analysis and machine intelligence, 35(8):1798 1798-117888888 2013.
[76] Jun-Ting Hsich, Binghin Liu, De-An Huang, Li F Fei-Fei, and Juan Carlos Niehles. learning to decompose and disentangle representations for video prediction. Advances in neural information processing systems. 31, 2018.
[77] Liqian Ma, Qianru Sun, Stamatios Georgoulis. Luc Van Gool, Bernt Schicle, and Mario Fritz. Disentangled person image generation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 99-108, 2018
[78] Xi Chen, Yan Duan, Rein Houthooft, John Schulman, Ilya Sutskever, and Pieter Abbeel. Infogan: Interpretable representation learning by information maximizing generative adversarial nets. Advances in neural information processing systems, 29, 2016.
[79] Emily L Denton et al. Unsupervised learning of disentangled representations from video. Advances in neural information processing systems, 30, 2017.
14

---

[80] Luan Tran, Xi Yin, and Xiaoming Liu. Disentangled representation learning gan for pose-invariant face recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1415-1424, 2017.
[81] Xin Wang, Hong Chen, Yuwei Zhou, Jianxin Ma, and Wenwu Zhu. Disentangled representation learning for recommendation. IEFF Transactions on Pattern Analysis and Machine Intelligence, 2022.
[82] Hong Chen, Yudong Chen, Xin Wang, Ruobing Xie, Rui Wang, Feng Xia, and Wenwu Zhu. Curriculum disentangled recommendation with noisy multi-fcedback. Advances in Neural Information Processing Systems, 34:26924 26936, 2021.
[83] Xin Wang, Hong Chen, and Wenwu Zhu. Multimodal disentangled representation for recommendation. In 2021 IEEE International Conference on Multimedia and Expo (ICME), pages 1-6. IEEE, 2021.
[84] Jianxin Ma, Chang Zhou, Hongxia Yang. Peng Cui, Xin Wang, and Wenwu Zhu. Disentangled self- supervision in sequential recommenders. In Proceedings of the 26th ACM SIGKDD International Confer- ence on Knowledge Discovery & Data Mining, pages 483-491, 2020.
[85] Jianxin Ma. Chang Zhou, Peng Cui, Hongxia Yang, and Wenwu Zhu. Learning disentangled representations for recommendation. Advances in neural information processing systems, 32, 2019.
[86] Haoyang Li, Xin Wang. Ziwei Zhang, Jianxin Ma, Peng Cui, and Wenwu Zhu. Intention-awars sequential recommendation with structured intent transition. IEEE Transactions on Knowledge and Data Engineering, 2021.
[87] Jianxin Ma, Peng Cui, Kun Kuang, Xin Wang, and Wenwu Zhu. Disentangled graph convolutional networks. In International conference on machine learning, pages 4212-4221. PMLR, 2019.
[88] Yanbei Liu, Xiao Wang, Shu Wu, and Zhitao Xiao. Independence promoted graph disentangled networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4916-4923, 2020.
[89] Yiding Yang, Zunlei Feng, Mingli Song, and Xinchao Wang. Factorizable graph convolutional networks. Advances in Neural Information Processing Systems, 33:20286 202996, 2020.
[90] Haoyang Li, Xin Wang, Ziwei Zhang, Zehuan Yuan, Hang Li, and Wenwu Zhu. Disentangled contrastive learning graphs. Advances in Neural Information Processing Systems, 34:21872-21884 2021.
[91] Haoyang Li, Ziwci Zhang, Xin Wang, and Wenwu Zhu. Disentangled graph contrastive learning with independence promotion. IEEE Transactions on Knowledge and Data Engineering, 2022.
[92] Wenbin Zhang, Liming Zhang, Dieter Pfoser, and Liang Zhao. Disentangled dynamic graph deep generation. In Proceedings of the 2021 SIAM International Conference on Duta Mining (SDM), pages 738-746. SIAM, 2021.
[93] Yuanqi Du, Xiaojie Guo, Hengning Cao, Yanfang Ye, and Liang Zhao. Disentangled spatiotemporal graph generative models. arXiv preprint 1:X1v:2203.00411, 2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all thcoretical results? [N/A]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)?
[Yes]
15

---

(c) Did you report enror bars (e.g.. with respect to the random seed after running experiments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/relessnng new assets...
(a) your work existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did discuss whether and how consent was obtained from people whose data you re using/cu- rating? [Yes]
(e) Did discuss whether the data you using/curating contains personally identifiable informa- tion or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable?
[N/A]
(h) Did you descrihe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "XjgVTbz8wTY", "reviewer": "Reviewer_8AMq", "summary": "This paper introduces a method of dynamic graph neural networks with spatio and temporal intervention mechanism.", "questions": "in equation (6), why are the expressions for m_i and m_v identital? \n", "limitations": "I failed to find the accurate definition of 'ego-graph', 'distribution shifts', 'invariant and variance structural patterns' , etc. As a result, it is not easy to understand this paper correctly without reading several previous papers.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n(1) the empirical study shows considerable improvement on existing method.\n(2) Innovative using attention layers to capture spatio-temporal information.\n\nWeakness:\n(1) no strict proof or detailed illustration to show why spatio-temporal intervention works.\n(2) computational complexity is not discussed in the main contents.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PA0Y4Utyceh", "reviewer": "Reviewer_nS4E", "summary": "This paper studies the problem of spatio-temporal distribution shift in dynamic graphs.\nBy disentangling the patterns in dynamic graphs into invariant and variant ones, the invariant patterns are utilized for stable prediction and the impact of distribution shift can be reduced.\nAlthough the distribution shift has been widely studied in the literature on computer vision and natural language processing, the authors made early attempts in the dynamic graph.\nI am overall positive about this work.", "questions": "1. Can the proposed model generalized to the continuous dynamic graph?\n2. What is the variant and invariant pattern in dynamic graph? Is there any common understanding rather than the specific graph type?", "limitations": "The core definition of variant and invariant are not well explained, which limits the generalization and scalability of the proposed method.\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n[+] The distribution shift in the dynamic graph is critical and the authors made the early attempts on this topic, which should be encouraged in the community.\n\n[+] The proposed solution is technical sound, the disentanglement as well as the causal spatio-temporal intervention mechanism can satisfy the requirements.\n\n[+] The experiments are extensive and the results are encouraging.\n\nWeaknesses\n\n[-] The invariant pattern is assumed to be dependent on the time. From my opinion of view, the invariant pattern can be futher divided into the time dependent and time independent ones.\n\n[-] The distribution shift in the experimental datasets are manually conducted，it would be better to have some automatically designed mechanism. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Be13RQ55AvO", "reviewer": "Reviewer_vUM5", "summary": "This work studies the patio-temporal distribution shift issue of dynamic graph neural networks. To pursue the robustness of DyGNNs, the authors proposed a specific invariant learning method and conducted experiments on both real-world and synthetic datasets.", "questions": "1. The experiment results need more explanations. For instance, why IRM and GroupDRO achieve inferior performance under the \"w/ DS\" setting. Why the compared methods show different trends on the real-world and synthetic datasets, e.g., GCRN performs quite well on the synthetic datasets.\n2. As compared to [18], what is the advantage of the proposed method.\n", "limitations": "No.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strong points:\n1. This paper revels the impact of distribution drift in DyGNNs, which forms a new research problem.\n2. This paper presents a new method for training distributionally robust DyGNNs.\n3. Extensive experiments validate the effectiveness of the proposed method.\n\nWeak points:\n1. The experiment results need more explanations. For instance, why IRM and GroupDRO achieve inferior performance under the \"w/ DS\" setting. Why the compared methods show different trends on the real-world and synthetic datasets, e.g., GCRN performs quite well on the synthetic datasets.\n2. As compared to [18], what is the advantage of the proposed method.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7HprgfhVUhu", "reviewer": "Reviewer_zQjJ", "summary": "This paper investigates graph neural networks on dynamic graphs, especially under spatio-temporal distribution shifts. The authors recognize that distribution shift is an important factor for dynamic graph embedding, which is not well-handled by the existing approaches. To address this, the authors propose a novel model named DIDA, to handle spatio-temporal distribution shifts in dynamic graphs by discovering and fully utilizing invariant spatio-temporal patterns. Experiments on four datasets demonstrate the effectiveness of the proposed model.", "questions": "Please see the weaknesses.", "limitations": "None", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well-written and easy to follow.\n2. Dealing with the spatio-temporal information on dynamic graphs from the perspective of discovering and utilizing invariant patterns, I feel might be an effective direction.\n3. The experiments are sufficient to demonstrate the performance of the proposed model.\n\n\nWeaknesses:\n\n1. The related studies discussed in Related Work are not quite sufficient. I suggest the authors cite and discuss more.\n2. It is better to give the details for the baselines (e.g., the differences with the proposed model), as well as more details for the datasets (e.g., give a statistic table) in the main paper. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept