Improving Generalization of Dynamic Graph Learning via Environment Prompt
Authors: Kuo Yang
Zhengyang Zhou
Qihe Huang
Limin Li
Yuxuan Liang
Yang Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: Dynamic graph
spatio-temporal graph learning
out-of-distribution generalization
causal theory
prompt learning
subgraph learning.
Primary area: deep_learning_architectures
TL;DR: Our work aims to design a powerful  spatio-temporal OOD framework that can comprehensively achieve the inference and exploitation of unseen environments.

Abstract: Out-of-distribution (OOD) generalization issue is a well-known challenge within deep learning tasks. In dynamic graphs, the change of temporal environments is regarded as the main cause of data distribution shift. While numerous OOD studies focusing on environment factors have achieved remarkable performance, they still fail to systematically solve the two issue of environment inference and utilization. In this work, we propose a novel dynamic graph learning model named EpoD based on prompt learning and structural causal model to comprehensively enhance both environment inference and utilization. Inspired by the superior performance of prompt learning in understanding underlying semantic and causal associations, we first design a self-prompted  learning  mechanism to infer unseen environment factors. We then rethink the role of environment variable within spatio-temporal causal structure model, and introduce a novel causal pathway where dynamic subgraphs serve as mediating variables. The extracted dynamic subgraph can effectively capture the data distribution shift  by incorporating the inferred environment variables into the node-wise dependencies. Theoretical discussions and intuitive analysis support the generalizability and interpretability of EpoD. Extensive experiments on seven real-world datasets across domains showcase the superiority of EpoD against baselines, and toy example experiments further verify the powerful interpretability and rationality of our EpoD.

Improving Generalization of Dynamic Graph Learning via Environment Prompt
Kuo Yang!.?, Zhengyang Z. Qihe Huang! 1.2, Limin Li!e2, Yuxuan Liang", Yang Wang!.
University of Science and Technology of China (USTC), Hefei, China Suzhou Institute for Advanced Research, USTC, Suzhou, China
State Key Laboratory of Resources and Environmental Information System, Beijing, China The Hong Kong University of Science and Technology (Guangzhou). Guangzhou, China www..ued.c....nn.... edu.en, zzy0929@uste uuteeuusstttuuut.nnm [hqh, lilimin) J mail.ustc.edu.cn, yangkuo @ mail.ustc.
yuxliang @ @outlook.com, angyan @ @ustc.edu.cn
Abstract
cut-of-distribution (OOD) generalization issue is well-known challenge within deep learning tasks. In dynamic graphs. the change of temporal environments is regarded as the main cause of data distribution shift. While numerous OOD stud- ies focusing on environment factors have achieved remarkable performance, they still fail to systematically solve the two issue of environment inference and utiliza- tion. In this work, we propose novel dynamic graph learning model named EpoD based on prompt learning and structural causal model to comprehensively enhance both environment inference and utilization. Inspired by the superior performance of prompt learning in understanding underlying semantic and causal associations, we first design self- self- prompted learning mechanism infer unseen environment factors. We then rethink the role of environment variable within spatio-temporal causal structure model, and introduce novel causal pathway where dynamic sub- graphs serve as mediating variables. The extracted dynamic subgraph can effec- tively capture the data distribution shift by incorporating the inferred environment variables into the node- wise dependencies. Theoretical discussions and intuitive analysis support the generalizability and interpretability of EpoD. Extensive exper- iments seven real-world datasets across domains showcase the superiority of EpoD against baselines, and toy example experiments further verify powerful interpretability and rationality of our EpoD.
1 Introduction
Dynamic graph learning aims to capture the evolution patterns of individual feature and global topol- ogy in spatio-temporal graphs over time. It has extensive applications real-world scenarios, such as social relationship analysis [6i 61], traffic flow forecasting [G] 59. Telj and air quality prediction [16. 23]. The dynamic evolution is a prominent characteristic of spatio-temporal graphs [8), I16. [7), such as human interest and social development naturally undergo changes over time. This charac- teristic inevitably gives rise a issue of data distribution shifts. Given this issue, enabling models to get temporal out-of-dee out-of--dstrinee of-distribution (OOD) generalization ability poses major challenge in dynamic graph learning [BIL (55) 633].
Actually, recent studies have paid attention to tackling the issue of temporal OOD gemeralization [53, 58, [1]]. They demonstrate that unseen temporal environments contribute such distribution Yang Wang and Zhengyang Zhou are corresponding authors.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

shift. For example, potential urban-hosted events can lead to out- -it-off-ditribution traffic state, and un- recorded academic communication between individuals in citation networks may hide new patterns of cooperation. Therefore, the research line relying on environment inference present promising solution for addressing the temporal OOD issue. This paradigm focuses on inferring underlying en- vironment factors, and utilizing the extracted environment information to enhance the robustness of dynamic graph learning against environment shifts. Although some works have achieved impressive performance [63 58), there remain limitations in both environment inference and utilization.
The judgment of existing limitations stems from two crucial observations. Firstly, unseen environ- ments invariably encompass a wide range of factors, posing challenges in accurately determining their quantities and scales. However, existing methods often rely on a predefined scale environment codebook for inferring unseen environments [53] D8], which may infer unrealistic environment re- sults. Secondly, the shift of environments in dynamic graphs fundamentally reflects in the changes of structural associations [[8 655]. A real-world example is that the change of weather alters the future flow of the traffic network by changing human's trajectory. Nevertheless, existing methods often prioritize using the inferred environment as additional information augment raw features, overlooking capturing the evolving structural associations [[.3% 588 6J].. Therefore, the existing dy- namic graph OOD efforts face issues in both environment extraction and utilization, and the com- prehensive solution to address both problems is currently lacking.
To tackle these limitations,, we propose an Environment promppted Dynamic Graph Learning (EpoD) architecture. Firstly, we propose a novel self- prlmppetpted learning mechanism to infer underlying environment representation. Given the lacking of environment labels and explicit scaling of envi- ronments, our aim is guide the network generalizing environment factors from historical data in autonomous manner. The practices of language model inference on underlying semantics inspires us to utilize prompt learning to achieve this goal [IEL [T].. We propose a self-prompted learning mechanism for spatio-temporal data to infer environment variables from historical data. By design- ing learnable prompt tokens and an interactive prompt-answer squeezing mechanism, we enable the model to effectively infer the compact and informative environment representations. Secondly, we propose a novel Structural Causal Model (SCM) with dynamic subgraph as mediating variable to enhance the adaptability of the network to environment shifts. Different from some approaches that obtain the causal subgraph by partitioning the original graph [6]]]. we design a node-centered sub- graph extractor specifically tailored for spatio-temporal data. This design is derived from profound understanding of dynamic graph that the shift of environments within dynamic graphs invariably re- sult in the changes of these asymmetric correlations between nodes. Our node-centered dynamic subgraphs extractor can capture node-wise asymmetry, where each node has its unique subgraph based on its environment states. Lastly, we conduct comprehensive experiments generalizability of EpoD. On the one hand, we perform experiments over multiple cross-domain datasets and introduce more intricate long-series prediction task. On the other hand, we design an enviromment-shade toy dataset, named EnvST, to verify the generalization ability of EpoD. The results show that EpoD can precisely perceive environment factors, and the generated dynamic sub- graphs are equipped with both generalizability and interpretability. Our contributions are summa- rized as follows:
evaluate the
We systematically investigate the environment- efforts to tackle the temporal OOD issue, and observe the limitations of existing works in environment inference and utilization.
To address existing challenges, we propose novel ing (EpoD) architecture. Specifically, we introduce a self-prompted learning mechanism for spatio-temporal data to infer underlying environment variables without preset scale. For the ex- ploitation of inferred environment factors, we propose a structural causal model with dynamic subgraphs for mediating variables to capture the effect of environment variable shifts on the data distribution. Our work presents a pioneering practice jointly focusing and solving the issue of environment inference and utilization.
Dynamic Graph Learn-
We conduct experiments over multiple cross-domain datasets. including traffics and social net- works, to verify the effectiveness of our framework. And a toy dataset is designed to demonstrate the generalizability and interpretability of EpoD.

---

Prompts
STGNN Backbone
Cross Attention
Z Prompe answers
Node embeddings
ge
B
Input
KLOH
Quantify Asymmetry
8 = X ZEl
STGNN Backbone
S=
Asymmetrric Correlations
Output
Dynomic subgraphs
Figure I: The architecture of EpoD. Left panel: the prediction future evolution based on historical observations. Right panel: the extraction process of node-centered dynamic subgraph.
2 Background
Preliminaries. We denote (9') dynamic graph across T steps, where G (V","", (²) represents snapshot of the graph at step t. The tensor 2" E IR NxD indicates observed features of |V*| nodes step where denotes the feature dimension. A' {0. 1 is the adjacency matrix describing the connectivity of graph G². Given the historical data X = (T dynamic graph learning aims to predict the future evolution patterns Y = (g') I==++1 (g)) notes the number of predicted future time steps. Historical observations can divided into the accessible environment features Xx and observed labels with evolution patterns Yx. e.g., volumes traffic datasets, or links social networks.
where K de-
Problem Definition. There is consensus that unseen environment factor, E. considered as the primary reason for temporal OOD issue [5X, [33]. this work, we focus on capturing the invariant evolution pattern of dynamic graph to tackle the temporal OOD issue.
Spatio-Temporal Graph Forecasting for OOD issue. Our work aims systematically tackle the challenges existing environment-centened OOD approaches. Our specific practice in envi- ronment inference and utilization is significantly distinct from existing works and has substantial improvements. On the one hand, the self-prompted environment inference framework aims to guide the network adaptively infer environment variables from historical data by using well-designed prompt tokens. Different from existing efforts relying on predefined environment scale [533, 58), our methods advantageously eliminates human biases and ensures accurate extraction of the environ- ment from real historical data. On the other hand, we propose novel SCM with dynamic subgraph as mediating variable. Compared to simply attaching environment embeddings to existing represen- tations, our approach is more consistent with the understanding of dynamic graph data from a causal perspective. Furthermore, unlike some approaches that rely on partition strategies commonly used in static graph learning to extract subgraphs [6.]]] we propose node-centered dynamic subgraph extraction method that is better suited for spatio-temporal graph scenarios.
Prompt Learning. Prompt learning was initially introduced to address the challenge of data scarcity in language models [7), [12, []]. By utilizing well-designed prompts, the model can effectively cap- ture a broader space of data distributions and patterns during training, which better at adapting input samples from different distributions. For an extended period, the complexity of prompt design has been a hindrance preventing prompt learning from achieving broader applications. In contrast to language data, human beings lack the intuitive cognition of both image and graph data, making it challenging to design interpretable prompts templates. Recently, learnable prompts have also been proven have superior performance [29, 20]. Therefore, prompt learning is thriving in computer vision research and graph learning [22. B0, [9]] Recently, the efforts of using prompt learning to enhance spatio-temporal prediction is beginning to emerge, including [62]] and [60]]. The former focuses on multi-attribute forecasting: the latter aims to enhance model generalization abil- ity. However, there lacking systematical research on prompt learning addressing temporal OOD problems.
3

---

3 Methodology
In this section, we introduce novel Environment- proometttdddpdddddddee Dynamic Graph Learning architecture named EpoD. First, we propose self-prompted learning mechanism to realize the awareness of unseen environment factors. Second, we revisit the winding causal path from environment to graph evolution, and a spatio-temporal learning framework utilizing dynamic subgraph as mediating vari- ables is presented. Last, we provide theoretical analysis of EpoD from causal perspective interpret its excellent generalization ability.
3.1 Self-prompted learning for environment awareness
Existing methods typically infer environments by predefining the scale of the environment codebook, which introduces human bias and has the potential to cause performance degradation. To tackle this issue, we introduce an environment inference principle that extract underlying environment representations from historical observations without predefining scales. Inspired by the remarkable success of prompt learning in inferring underlying semanties and the multimodal generalization of large language models (LLMs) ESA 35, [9), we propose a self-prompted learning mechanism (SPL) to realize this environment inference principle.
Spatial-specified prompt design. Our SPI. focuses on guiding models to effectively extract envi- ronment variables from observed data by well-designed prompts. Therefore, the initial challenge we need to address is the design of prompt tokens. Within spatio-temporal graphs, it is common for dif- ferent nodes to exhibit diverse evolution patterns. Thus, the design of prompts should be specified on spatial aspect to reflect node-wise distinctive evolution state. Given a dynamic graph G, we assign a prompt token p; for each node, which is shared across temporal steps. However, the absence of prior knowledge about environment information hinders us from adopting the template-base -asud approach to initialize P,- Fortunately, learnable prompts have revealed satisfactory performances on capturing hidden mappings [B9 [DJ. Therefore, we initialize learnable prompt token p; e H for each i V. where d denotes the dimension of latent embedding space. The environment prompt tokens P for g is then denoted
P ( E Nxd
(1)
Since P is specified on the spatial perspective, the node across different temporal snapshots shares the same environment prompt. In the implementation. P is expanded as a new tensor IR NxTxxx by cloning 7 times.
Prompt-answer mechanism for environment squeezing. The next challenge address is how to effectively utilize the well-designed prompts to guide the model in extracting underlying envi- romment representations Zg E R Nxxd The premise of achieving this goal lies in profoundly understanding the relationships between the variables in dynamic graph. The ability of Structural Causal Model (SCM) to describe the relationship between variables offers a valuable framework for our analysis [26] 27). The SCM of dynamic graph includes the temporal environment information E. spatial context C, historical observation X, and future evolving signals Y. Actually, denotes historical observations, which is the combination of Xx and Yx defined in Sec. eL This causal model can be formalized as,
P(X. YJE, C) = IP E, C)P(XIE, C).
Therefore, we aim to squeeze environment variables E from the observable feature Xx and the observed labels with evolution patterns Yx, which is similar to solving cloze problems. To accom- plish this, we design an interactive squeezing mechanism (-).) to guide the model to squeeze out the underlying environment variables through the interaction of learnable prompts P and the ob- servable features Xx. Specifically, we first perform a spatio-temporal network backbone (.) to get nodes embedding = {zi,... D- E T xd by taking observable features Xx as in- puts. Then, ()(+)) decodes the learnable prompts P and encoded embedding Z to obtain prompt answers Zg. In implementation, ge(.) consists of three families of learnable parameters, i.c., WV E Txdx Three hidden state matrices are calculated by,
p2 = P zk ZWK, z ZWV.
(3)
The prompt answer Zæ is obtained by,
pa p7
Zg = softmax
)z + c,
(4)
Vd

---

where e ~ (O.I). Random noise is added to further enhance the robustness of inferred environ- ment representation. Then. the ground-truth Yx serves as the learning goal during this squeezing process. We design tractable objective to squeeze unseen environment representation ZE.,
min Lp = P P Xxx E) = ( P. (Z)) 0.0.P
Ellog P Fe,0 Yxx Zg)l,
(5)
where 3 E [0, 1] is preset hyperparameter, and its sensitivity analysis is provided in Appendix (A)
The first term captures the similarity between environment states Zg and node embedding Z.
The second term predicts the evolution rule Yx only using inferred unseen environments Zg.
The objective of Eq. 5 implies that our prompt answers not only reflect the evolution of dynamic graphs but also significantly differ from current available features.
Our design infers unseen environment factors into a continuous space, which remarkably distinctive from previous methods with predefined and discrete environment scale [63 588]. Our extracted Z can eliminate the bias stemming from inadequate prior knowledge of environment information.
Provable Squeezed Environment Answer. SPL enables the awareness of environment factors via employing environment prompt framework. However, there still indistinctness about the feasibil- ity of our design. From the perspective of information theory [2,, [S], the learning objective of SPI. can be restated as,
max 7 [ZZ;; Yx) (T Xx). d.8.P
We will replace Eq. with above Eq. G for later proof.
Theorem 3.1. If there exists a causal relationship between unseen environment pattern Zg and the label Yx, Zg is the optimal result of SPL objective.
Theorem I demonstrates the feasibility of SPI. and we can always extract additional environment factor if exist. Detailed proof is provided in Appendix O
3.2 Seaporlllemporal Learning with Dynamic Subgraph
With the well-learned environment answers, how to exploit such representations to achieve spatio-temporal prediction becomes a natural problem. Existing environment-centee proaches tend to directly treat the perceived en- vironment embedding Zg as the additional fea- ture. However, from the perspective of data generation, the influence of environments data distribution shifts is usually reflected in the changes of node-wise correlations. Current methods fail to capture the causal effects en- vironment variables in dynamic graphs. In this subsection, we introduce spatio-temporaa invariant learning approach using node-centered dy-
ap-
Y
(a)
(b)
(c)
Figure 2: SCMs of dynamic graph. (a) Tradi-
tional generation understanding of dynamic graph; (b) Indirect effect of environment factors; (c) Dy- namic subgraph as mediating variable.
namic subgraph as the mediating variable.
winding causal path in dynamic graph. model, and propose novel SCM with dynamic subgraph Xs as mediating variable as shown in Fig. ().. can be formalized by,
We revisit the role of E in the spatio-temporal causal
PPY, - C)P((EE,
P(Y(Xs)P(Xs/X
In contrast to the symmetric correlations between nodes in static graphs, the dependencies between nodes in dynamic graphs are often directional and asymmetric. For example, there is flow direction between nodes in traffic network and certain node pairs may have different influence or importance to each other in social network. As result, the shift of environments within dynamic graphs always leads to the changes of these asymmetric correlations between nodes. A typical example is that the change of weather conditions always leads to shift in the direction of traffic flow instead bring any new paths. Different from partition-based subgraph learning strategies investigated in static
5

---

graphs, we design node-centered dynamic subgraph extractor tailored for dynamic graphs, where each node has its unique subgraph based on its environment states. Such strategy not only captures the impact of environments on internode dependencies, but also facilitates to mine the invariant pattern of spatio-temporal evolution more interpretably.
Dynamic subgraph extraction for environment enhancement. We argue that the asymmetry of environment factor between nodes often leads clustering effects, such as the asymmetrical impor- lance between the prominent individuals and their followers brings stable connectivity. We leverage the relative entropy (Kullback-Leibler Divergence) to measure such asymmetry. Relative entropy a metric employed to quantify the disparity between two probability distributions, which exhibits notable feature of asymmetry, i.e. KL(PIQQ) * KL [P). (L(P)) [Q] quantifies the degree of match when using IP as the reference distribution and approximating it with Q, while (L quantifies the degree of match when using Q as the reference distribution and approximating it with P. Such property of relative entropy offers significant advantages in quantifying asymmetric envi- ronment distributions. This is because the asymmetric dependencies of environment distributions also considers the influence of one environment factor another as the reference basis. However, computing the KL divergence between every pair nodes KL(Z' B(s.:) (ZZ))))) is computationally intensive. To this end, we propose linear complexity quantification method using the mean distribu- tion of node-level environment distributions proxy. S(i,)) represents the dependence from i on j at time
S(a,)- (Z')
2 ((..)) x KL F(AA)) (Zg)
(8)
where z MEAN(Z'S (Z'z) denotes the mean distribution of node-level environment embedding.
This method utilizes D as an intermediary to measure the environment dependency from node to j. The larger of (a,)) indicates a greater gap of environment difference from node to J. which
reflects the strong dependence. The asymmetric correlation matrix S E NNN at time t can be calculated as,
s = =M*)T "MM').N'' N
(9)
M E I and No RIXN respectively calculated from the two terms in Eq. B.
M [KL
2 2 KL E(2.)) KL 2 Z :)),
)]
(10)
N' (KL(ZE 17 KL E(2,)) 233 ...., (L(ZZE(..)) IZ
(11)
((,.)) denotes potential nodes centered on node and KL(-II)) indicates the Kullback-Leibbe di- vergence. We can extract node-centered L-hop subgraph A' NNN based on this environment- enhanced correlation matrix St, S @ T((AA)*).
(12)
where @) denotes element-wise multiplication of matrices and is a hyperparameter. T. is set to 5 and its sensitivity is discussed in Appendix G.I. TT() is an indicator function that assigns value of to elements in the matrix that are greater than 0, and assigns a value ( to the rest. We can get a series of dynamic subgraphs that evolves over time À E IR 7x N Meanwhile, we combine the features of each node by concatenating environment answer Z'g to obtain enhanced Xe (x++d))
L CONCAT( Zzel).
(13)
The historical data enhanced by dynamic subgraph with environment representation is denoted as,
Xs ( = (V* Et "
(14)
Dynamic graph prediction with generalizability. Finally, fo encodes the dynamic subgraphs Xs via ppatio-temport network backbone to predict future dynamic evolution. We obtain the learning objective of EpoD,
min C = - Ellog (Y - log (Yx.XYxxx...) P)] ( 6.0.P.0
(15)
We provide the training process of EpoD Alg. II it worth noting that our EpoD systematically re- solves the limitations of environment inference and environment utilization faced by spatio-temporal invariant learning methods. The two aspects of the design are not independent, but rather tightly cou- pled. Moreover, our EpoD is pluggable that can be flexibly integrated with various backbones. In

---

Table 1: The performance of traffic prediction tasks (12 + 24) on four real-world datasets. The
best results are shown in bold and the second best results are underlined.
PEMS08
PEMS04
SD(2019-2020)
GBA(2019-2020)
Model
MAE
RMSE
MAE
RMSE
MAE
RMSE
MAE
RMSE
GWNET
19,0410.9
29.02=1.1
23.12:0.8
38.7511.3
30.22::2.1
43.65:22.9
31.2712.66
45.2912..3
AGCRN
17.30=0.2
27.44=0.6
21.1940.3
34.65=0.2
26.19:1.2
40.51=1.3
28.7411.
43.75#2.00
Z-GCNET's
19.24=0.3
28.40=0.2
22.55=0.55
36,27+0.7
28.21=1177
41.32+1.88
29.87=1.
43.11#2.2
DSTAGNN
17.56.1033
26.2911.2
21.22.10.7
36,65.10.2
2..34.1.4
41.31.1..66
30.111:.00
42.9912.7
STGNCDE
18.41110.
27.38.1.33
22.04.10.6
35.39110.
27.34.10.9
40.73.11.3
29.2111.5
43.03.1244
CaST
17.28+0.3
26.56=00.4
20.79+00.4
34.95+0.33
25.38+1.11
39.92+116
28.67+
42.23+199
EopD(ours)
16.92:10.2
25.66:10.6
21.1210.
34.02.10.3
23.581122
38.25:1.44
27.26:::.5
40.1411.88
the experiments of traffic flow and social relationship prediction, we select Adaptive Graph Convo- lutional Recurrent Network (AGCRN) [3] and Disentangled Dynamic Graph Attention Networks (DDGAN) [6]]] our STGNN backbone respectively.
Our approach does not require predictions of future unseen environments. Actually, we argue that the underlying unseen environment factors within historical observations harbors valuable informa- tion guide evolution. Therefore, our focus lies in perceiving historical environment factors and exploiting them appropriately to capture evolution-invariant pattern for prediction. The subsequent experimental diseussion can further validate such intuition.
3.3 Causal Interpretation of Dynamic Subgraphs
In this subsection, we provide a deeper understanding of EpoD in the causal theory perspective [28]]
The mediating effect in the dynamic graph. The efforts on how temporal environment factors and spatial contexts influence the evolution of dynamics graph has been extensively made. However, even though some studies claim disentanglement of spatial-temporal dependencies, it is acknowl- edged that true separation may not be fully achieved. Most of them inherently concentrated on exploring the interplay between spatial and temporal dynamics. In fact, some pioncering researches have revealed the temporal evolution mostly stem from the changes over spatial dependencies. To this end, we summarize such indirect influence as mediating effect within dynamic graph, as shown Fig, (b).. But according to the complete mediation effect theorem, this SCM eliminates the direct effect of temporal variable E on future opatio-temporal evolution Y. This requires to contemplate whether C can serve as a mediation variable. Given the lime-varying property of dynamic graph, the only spatial context cannot sufficiently interpret the graphs evolution. Therefore, mediating variable simultaneously encapsulating spatial dependencies and temporal dynamics required.
Dynamic subgraphs mediation variable. The dynamic spatial variations induced by environ- ment factors are essentially rooted in the changes of local dependencies. Thus, a novel SCM introduced, which employ dynamic subgraph Xs as the mediation variable as illustrated in Fig. E(c). Dynamic subgraphs exhibit both temporal and spatial characteristics, also serve as mediation variable from X to Y. This design offers us a chance to address distribution shift issue along the practices of causal adjustment [[8]. We can observe a back-door path between causal path and Y, i.c., X +- - Xs + Y. The backdoor adjustment pattern leveraging do-calculus dynamic subgraph Xs is,
P(Y x)) P
P(Y v/X Xs P(Xs ES).
(16)
In essence, EpoD be viewed employing backdoor adjustments estimate P(Y (X))) by discovering dynamic subgraphs, where the prompted environment representations support the subgraph discovery process. More discussion is provided in Appendix D
4 Experiments
4.1
Experiment Setup
We introduce datasets, basclines and experiment settings, and details are leaved in Appendix E
7

---

Datasets. We employ seven cross cross-domain real-world dynamic graph datasets to evaluate our EpoD. PEMS08 and PEMS04 [-4]]]] are classic medium-scale traffic network datasets from California with 5-minute intervals; SD and GBA [244] are newly proposed large-scale traffic network datasets. COL- LAB [M]] is an academic collahoration dataset comprising papers published in 16 years; Yelp [[%] is a business review dataset; ACT [TS] shows students' actions on MOOC platform over 30 days.
Baselines. We compare EpoD with two families of baselines, i.c., six traffic flow prediction models and six social link forecasting methods. Traffic flow prediction models; GWNET [[2]], AGCRN
[G]. Z-GCNETs[N], DSTAGNN [19). STGNCDE [ CaST [[3]] Social link forecasting models: DySAT]B3) IRM VREx GroupDRO DIDA[58], EAGLE [58]]
Experiment settings. In the experiments of traffic flow prediction, our task is to predict the next 24 steps based on historical 12 steps observations (12 - 24). Moreover, we choose traffic data from the SD and GBA datasets spanning from 2019 2020 in order to add the distribution shift scenarios arising from COVID-19, where the training set is composed of data from 2019, while the data from 2020 is divided into a validation set and test set. The task of social relationship analysis is to exploit past graphs to make link prediction in the next time step. In the training stage, we selectively mask shifted attribute link from COLLAB, Yelp and ACT to simulate the distribution shift scenario encountered in the real world [b]].
4.2 Performance Analysis on Real-world Datasets
Traffic flow prediction. We evaluate our Epol) with baselines based on Mean Abso- lute Error (MAE) and Root Mean Square Er- (RMSE), where lower values of them rep- resent better performance. Tab. II shows the results of EpoD on traffic flow data. We have two observations: 1) our EpoD outperforms all baselines on three datasets. The power- ful Long-sequence prediction ability of EpoD demonstrates that our design robust en- vironment perturbations and excels in captur- ing the evolution patterns of dynamic graph.
Table 2: AUC score (% of future link prediction
task on real-world social relationship datasets. The best results are shown in bold and the second best results are underlined.
Model
Collab
Yelp
ACT
DySAT
76.59+10.20
66.09::1.42
66.55 1,21
IRM
75.42:40.87
$6.02.11.008
1.35
VREx
76.24:10.77 66.4111.877
70.15 1.09
GroupDRO
76.33+:0229
66.97+0.61
74.35 .62
We also note that CaST [53] obtains subop- timal results on most datasets and even opti-
DIDA
81,87+00.0
75.92+
78.64:
EAGLE
84.4110.87
77.26.1074
82.70.10.72
mal results on PEMS04. This indicates that is effective to tackle the temporal distribu-
FopD(ours)
83.21+0.35
00.85
83.85+00522
tion shift issue by studying environment factors under the guidance of causal theory. 2) EpoD ex- hibits a more pronounced capability for prediction improvement on two large-scale traffic datasets. It indicates that EpoD is better suited for addressing the distribution shift issue caused by extremely intricate environment perturbations, which is the main challenge posed by large-scale traffic data. We also discuss the interpretability of dynamic subgraphs in Appendix <K!
Social link forecasting. Tab. 2 presents the performance of EpoD on social link prediction tasks. Our model outperforms all baselines on two datasets under distribution shifts. We also observe that EAGLE [58] achieves one best performance and other sub-optimal results, which is comparable to our method. It proves that the approaches of perceiving environments can tackle the distribution shifts issue in dynamic graph. Besides, our extracted continuous environment representations are more expressive than the environment factors with pre-defined scales.
4.3 Toy Dataset
We manually design a toy dataset EnvST with temporal distribution shift to explore the general- izability of EpoD. The feature of each node EnvST' encompasses three components, i.e., [x IB, zcl, where ZA and øB represent evolution-causal features but ZB is masked after the data is generated, xe indicates available evolution-spurious feature. To simulate the temporal distri- bution shift in the dynamic graph, the training and test dataset of ZA. In and ae are sampled from distributions with significant differences separately. The label of each node on the EnvST at t step is activated by updated feature of ~ (2)n( where a(.) is the sigmoid func-
8

---

tion. We conduct experiments from the following two aspects: 1) we investigate whether EpoD has the capability perceive masked environment feature zg. 2) we study whether EpoD can identify and remove the spurious correlation rC. More analysis can be found in Appendix
Powerful perception for unseen environment. Fig. Saa and 5ib] show the distribution differ- ence between masked feature and prompted environment feature Zg. where experiments are conducted on EnxST under the scenario of
sood
distribution shift. Fig. Bía) shows our prompted environment feature Z can cover more than half of the shifted features in the future steps. As shown in Fig. B(b] we observe that our prompted environment variables can effectively cover slight early signal and utilize it to tackle OOD issue.
(a) Sharp temporal distri-(b) (b) Temporal distribution bution shift.
shift with slight signals.
Figure 3: Analysis on the toy dataset.
Robust spurious information identification
ability. We then explore whether our EpoD can filter out the disturbance of zc. Specifically, we have the following experiment design. Consider ze is sampled from W(H, I), we set E [0, 10] and record the performance of EpoD under the influence of different spurious information as shown in Fig. M We can observe that the fluctuations in prediction performance consistently fall within the acceptable error bounds. Therefore, we can conclude that EpoD have the ability to identify spurious information Ic.
4.4 Ablation Study
We conduct ablation studies from the following two aspects.
Temporal shared learnable prompts. In spatio-temporal graphs, we can observe different nodes always reveal hetero- geneous evolution patterns. Thus, design temporal shared node-wise Icarnable prompts. In essence, this design is driven by both resource consumption and are still two potentially effective design approaches: a single learnable prompt shared globally (SingleP) and node-private learnable prompts (PrivateP). The former only initializes a globally shared prompt for the dynamic graph P Rd, the latter assigns learnable prompts to each node of each snapshot x xd To this end, we compare three design methods in terms of accuracy and efficiency. Fig. A shows the results of ablation, where the bars represent the time consuming and the lines depict accuracy. We have the following two observations. 1) From the aspects of accuracy, the design of EpoD and PrivateP have similar performance, and SingleP is significantly inferior to them. 2) From the aspects of efficiency, it is understandable that SingleP has the highest training efficiency and PrivateP is the least efficient. The efficiency of EpoD falls between them, yet it remains competitive with SingleP. Therefore, we can conclude that our design stands out as the optimal choice considering both efficiency and accuracy.
Rpob
PrivacoP
Time consuning (Hepsce)
12
scenarios. There
R
Figure 4: A comparison of learn- able prompts design approaches.
The necessity of dynamic subgraph de- sign. We aim investigate the importance of dynamic subgraphs and explore which sub- graph extraction strategy more suitable for dynamic graph learning. Specifically, we first construct two variants of EpoD, i.e., EpSD-NoSub and PortttaatiionSuu EpoD- NoSub is a variant of EpoD that does not utilize dynamic subgraphs for spatiotempo- ral prediction, which just uses the perceived environment only by incorporating features.
Table 3: Ablation results dynamic subgraph in EpoD. MAE performance on PEMSO8 and PEMS04, AUC(%) score Yelp.
Model
PEMS08
PEMS04
Yelp
EpoD-NoSub
17.45
21.93
76.34
EpoD-Pane Poo-taatitionSub
18.09
22.04
77.35
EopD()urs)
16.92
21.12
80.85

---

EpoD- PonDD-ariitionSub means an EpoD variant with Irrrition-basedd subgraph extraction strategy like static graph learning. We perform ablation experiments on PEMS08. PEMS04 and Yelp, as shown in Tab. B. First, we observe that the performance difference between Epol and EpoD-NoSub is substantial, with maximum gap exceeding 2. It means the utilization of dynamic subgraphs not only enhances interpretability but also is crucial for improving generalization performance. Second, we EpoD had a more pronounced effect than EpoD-PartitionSe In addition, more experiments show that EpoD is more stable than EpoD- PooD-PartitionSub
4.5 Efficiency Analysis
We analyze the efficiency of EpoD theoretically and practically. We utilize [V] and |F] to denote the num- ber of nodes and edges in the graph, to represent the dimension of implicit representation, and T to repre- sent the time step of historical observations. The time consumption mainly comprises three components: the spatio-temporal graph aggregation process, the prompt answer process, and the dynamic subgraphs sampling process. The time complexity of the centtiiltepoalll ag- gregation is (1E) Id))). The prompt answer
Table 4: Efficiency analysis of EpoD (s/epoch).
Dataset
DIDA
EAGLE
EpoD
COLLAB
11.21
12.05
11.84
Yelp
6,89
7.38
7.34
ACT
9.27
9.76
9.59
process primarily involves a cross cross-attention operation, with a time complexity of (OT-/VV) [VI.d). The dynamic subgraphs sampling module implements node-centered sampling, with time complexity of O |V]). Therefore, the time complexity of EpoD is O d [E] + T- (1 + d + d²) [V]). In conclusion EpoD exhibits linear time complexity concerning the number of nodes and edges, which is competitive with existing dynamic GNNs such as DIDA, EAGLE, and CaST.
We also conduct efficiency comparisons of EpoD, DIDA, and EAGLE in COLLAB, Yelp, and ACT datasets, measuring the time taken per epoch (s/epoch). All experiments are run on an NVIDIA A100-PCIE-400 Empirically, observe that the operational efficiency of our method is compet- itive with existing approaches.
5 Conclusion and Future Work
In this paper, propose novel dynamic graph learning framework Epol) tackle the temporal dis- tribution shift issue by exploiting prompt learning. Inspired by the powerful ability of prompt learn- ing in perceiving underlying semantic and causal associations, environment inference mechanism. This approach aims to extract underlying environment vari- ables that potentially influence temporal distribution shift. Subsequently, we propose a novel causal pathway that leverages dynamic subgraphs as mediating variables to effectively utilize the inferred environment embedding. Experiments on real-world datasets and toy examples show that our EpoD effectively improve the dynamic graph learning under temporal shifts, especially boosting the inter- pretability via dynamic subgraphs.
first introduce self-prompted
Limitations. One of the limitation of our work is its strong dependence on graph topology. Specif- ically, subgraph discovery strategy essentially is the node filtering based K-hop neighbors, which can be regarded as subtracting elements from the graph topology. However, the graph topol- ogy constructed by distance- based adjacency matrix always lacks adaptability to dynamic changes in the relationships between nodes [[53]. In the future, we aim to improve the extraction process of node-centered dynamic subgraphs. We intend form subgraphs from an empty topology by taking into account both the perceived environment embeddings and the initial distance information.
Acknovledgements
This paper is partially supported by the National Natural Science Foundation of China 122279179 No.62072427, No.62402414), Natural Science Foundation of Jiangsu Province (BK. 20244400), the Project of Stable Support for Youth Team Basic Research Field, CAS (No.YSBR-OW) YSBR-005), Academic Leaders Cultivation Program, USTC, and the grant from State Key Lab- oratory of Resources and Environmental Information System. We sincerely thank all reviewers for their insightful and constructive comments in improving this paper.
10

---

References
[1] Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk mini- mization, arXiv preprint arXiv:1907.0289) 2019.
[2] Robert B Ash. Information theory. Courier Corporation, 2012.
[3] Lei Bai, Lina Yao, Can Li, Xianzhi Wang, and Can Wang. Adaptive graph convolutional recurrent network for traffic forecasting. Advances in neural information processing systems, 33:17804-1788 2020.
[4] Shaojic Bai, J Zico Kolter, and Vladlen Koltun. An empirical evaluation of generic convolu- tional and recurrent networks for sequence modeling. arXiv preprint arXiv:1803.01271 2018.
[5] Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In International conference on machine learning, pages 531-540. PMLR, 2018
[6] 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 2006.
and data mining. pages
[7] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language mod- els are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[8] Yuzhou Chen, Ignacio Segovia, and Yulia Gel. Z-genets: Time zigzags at graph convolu- tional networks for time series forecasting. In International Conference on Machine Learning. pages 1684-1694. PMLR, 2021.
[9] Jeongwhan Choi, Hwangyong Choi, Jechyun Hwang, and Noseong Park. Graph neural con- trolled differential equations for traffic forecasting. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6367-6374, 2022.
[10] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[11] Chen Gao, Si Liu, Jinyu Chen, Luting Wang, Qi Wu, Bo Li, and Qi Tian. Room-object entity prompting and reasoning for embodied referring expression. IEEE Transactions Pattern Analysis and Machine Intelligence, 2023.
[12] Tianyu Gao, Adam Fisch, and Danqi Chen. Making pre-trained language models better few- shot leamerr. arXiv preprint 1522:30 2020.
[13] Shengnan Guo, Youfang Lin, Ning Feng, Chao Song, and Huaiyu Wan. Attention based spatial- temporal graph convolutional networks for traffic flow forecasting. In Proceedings the conference on artificial intelligence, volume 33, pages 922-929, 2019.
the AAAI
[14] Yutai Hou, Hongyuan Dong, Xinghao Wang, Bohan Li, and Wanxiang Che. Metaprompting: Learning to learn better prompts. arXiv preprint arXiv:2209. 1486, 2022.
[15] Qihe Huang, Lei Shen, Ruixin Zhang, Shouhong Ding, Binwu Wang, Zhengyang Zhou, and Yang Wang. Crossgnn: Confronting noisy multivariate time series via cross interaction refine- ment. In seirth- Conference on Neural Information Processing Systems, 2023.
[16] Jin, Y Liang, Fang, J Huang, Zhang and Y Zheng. Spatio-temporal graph neural networks for predictive learning in urban computing: A survey, arxiv 2023. arXiv preprint arXiv:2303.14483
[17] 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). International Conference on Machine Learning, pages 5815-5826. PMLR, 2021.
11

---

[18] Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1269-1278, 2019.
[19] Shiyong Lan, Yitong Ma, Weikang Huang. Wenwu Wang, Hongyu Yang, and Pyang Li. Dstagnn: Dynamic spatial-temporal aware graph neural network for traffic flow forecasting. In International conference on machine learning, pages 1 11906-11917 PMLR, 2022.
[20] Brian Lester, Rami AI-Rfou, and Noah Constant. The power of scale for parameter-efficient prompt tuning, arXiv preprint arXiv:2104. 006699 2021.
[21] Jianxin Li, Qingyun Sun, Hao Peng, Beining Yang, Jia Wu, and S Yu Philip. Adaptive sub- graph neural network with reinforced critical structure mining. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(7):8003- -0000 2023.
[22] Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. arXiv preprint arXiv:2101.00190, 2021.
[23] Yuxuan Liang, Songyu Ke, Junbo Zhang, Xiuwen Yi, and Yu Zheng. Geoman: Multi-level attention networks for geo-sensory time series prediction. In ICCAI, volume 2018, pages 3428- 3434, 2018.
[24] Xu Liu, Yutong Xia, Yuxuan Liang, Junfeng Hu, Yiwei Wang, Lei Bai, Chao Huang, Zhen- guang Liu, Bryan Hooi, and Roger Zimmermann. Largest: A benchmark dataset for large-scale traffic forecasting. arXiv preprint arXiv:2330..888 08259, 2023.
[25] Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. In International Conference on Machine Learning, pages 15524-15543. PMLR, 2022.
[26] Judea Pearl. Causal inference in statistics: An overview. 2009.
[27] Judea Pearl. Causal inference. Causality: objectives and assessment, pages 39-58, 2010.
[28] Judea Pearl et al. Models, reasoning and inference. Cambridge, UK: Cambridgeeniiversivty Press, 19(2):3, 2000.
[29] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishknn, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pages 8748-8763. PMLR, 2021.
[30] Yongming Rao, Wenliang Zhao, Guangyi Chen, Yansong Tang, Zheng Zhu, Guan Huang, Jie Zhou, and Jiwen Lu. Denseclip: Language-guided dense prediction with context-aware prompting. In Proceedings of the IEFE/CVF Conference on Computer Vision and Pattern Recognition, pages 18082-18091, 2022.
[31] Laria Reynolds and Kyle McDonell. Prompt programming for large language models: Beyond the few-shot paradigm. In Extended Abstructs of the 2021 CHI Conference on Human Fuctors in Computing Systems, pages 1-7, 2021.
[32] Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint (XX.v:9911.0875 2019.
[33] 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 data mining, pages 519-527, 2020.
[34] Chao Song, Youfang Lin, Shengnan Guo, and Huaiyu Wan. Spatial-temporal synchronous graph convolutional networks: A new framework for spatial-temporal network data forecasting. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 914-921,
2020.
12

---

[35] Alessandro Sordoni, Eric Yuan, Ziang Xiao, Arian Hosseini, Friederike Niedtner, and Nicolas Le Roux. Joint prompt optimiza- tion of stacked Ilms using variational inference. Advances in Neural Information Processing Systems, 36, 2024.
Côté, Matheus Pereira, Adam Trischler,
[36] Qingyun Sun, Ziying Chen, Beining Yang, Cheng Ji, Xingcheng Fu, Sheng Zhou, Hao Peng, Jianxin Li, and Philip S Yu. Ge-bench: An open and unified benchmark for graph condensation. In Advances in Neural Information Processing Systems, 2024.
[37] Qingyun Sun, Jianxin Li, Hao Peng, Jia Wu, Xingcheng Fu, Cheng Ji, and S Yu Philip. Graph structure learning with variational information bottleneck. In Proceedings the AAAI Confer- ence on Artificial Intelligence, volume 36, pages 16654417,, 2022.
[38] 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 Web Conference 2021, pages 2081-2091, 2021.
[39] Xiangguo Sun, Hong Cheng, Jía Li, Bo Liu, and Jihong Guan. All in one: Multi-task prompting for graph neural networks. 2023.
[40] 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.
[41] Binwu Wang. Jiaming Ma, Pengkun Wang, Xu Wang, Yudong Zhang, Zhengyang Zhou, and Yang Wang. Stone: A spatio-temporal ood learning framework kills both spatial and temporal shifts. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2948-2959, 2024.
[42] Binwu Wang, Pengkun Wang, Yudong Zhang, Xu Wang. Zhengyang Zhou, Lei Bai, and Yang Wang. Towards dynamic spatial-temporal graph learning: decoupled perspective. In Pro- ceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 9089-9999999 909999999777290 2024.
[43] Binwu Wang, Yudong Zhang, Xu Wang, Pengkun Wang, Zhengyang Zhou, Lei Bai, and Yang Wang. Pattern expansion and consolidation on evolving graphs for continual traffic prediction. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2223-2222222222222222222-2--21 2232, 2023.
[44] Kun Wang, Yuxuan Liang. Xinglin Li, Guohao Li, Bernard Ghanem, Roger Zimmermann, Huahui Yi, Yudong Zhang, Yang Wang, et al. Brave the wind and the waves: Discovering robust and generalizable graph lottery tickets. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.
[45] Kun Wang, Hao Wu, Yifan Duan, Guibin Zhang, Kai Wang, Xiaojiang Peng. Yu Zheng, Yux- uan Liang, and Yang Wang. Nuwadynamics: Discovering and updating in causal spatio- temporal modeling. In The Twelfth International Conference on Learning Representations, 2024.
[46] Kun Wang, Hao Wu, Guibin Zhang, Junfeng Fang. Yuxuan Liang, Yuankai Wu, Roger Zim- mermann, and Yang Wang. Modeling spatio-temporal dynamical systems with neural discrete learning and offeerts IEEE Transactions on Knowledge and Data Engineering, 2024.
[47] Senzhang Wang, Jiannong Cao, and S Yu Philip. Deep learning for spatio-temporal data min- ing: A survey. IEEE transactions on knowledge and data engineering, 34(8)33681-3700, 2020.
[48] Xu Wang, Lianliang Chen, Hongbo Zhang, Pengkun Wang, Zhengyang Zhou, and Yang Wang. A multi-graph fusion based spatiotemporal dynamic learning framework. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pages 294-302, 2023.
[49] Jules White, Quchen Fu, Sam Hays, Michael Sandborn, Carlos Olea, Henry Gilbert, Ashraf Elnashar, Jesse Spencer-Smith, and Douglas Schmidt. prompt pattern catalog to enhance prompt engineering with chatgpt. arXiv preprint 2132, 2023.
13

---

[50] Hao Wu, Yuxuan Liang. Wei Xiong, Zhengyang Zhou, Wei Huang, Shilong Wang, and Kun Wang. Earthfarsser: Versatile spatio-temporal dynamical systems modeling one model. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 15906-15914, 2024.
[51] Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invariance perspective. arXiv preprint wwxiv:2202.024455 2022.
[52] Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang. Graph wavenet for deep spatial-temporal graph modeling. arXiv preprint 19Xiv:9906.0010 2019.
[53] Yutong Xia, Yuxuan Liang, Haomin Wen, Xu Liu, Kun Wang, Zhengyang Zhou, and Roger Zimmermann. Deciphering spatio-temporal graph forecasting: causal lens and treatment. arXiv preprint arXiv:2309.13377 13378, 2023.
[54] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00822, 2018.
[55] Chenxiao Yang, Qitian Wu, Qingsong Wen, Zhiqiang Zhou, Liang Sun, and Junehi Yan. To- wards out-of-distributiin sequential event prediction: A causal treatment. Advances in neural information processing systems, 1422266-226700 2022.
[56] Yong Yu, Xiaosheng Si, Changhua Hu, and Jianxun Zhang. A review of recurrent neural networks: Lstm cells and network architectures. Neural compulation, 3157):125-1127, 2019,,
[57] Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 430 438, 2020.
[58] Haonan Yuan, Qingyun Sun, Xingcheng Fu, Ziwei Zhang, Cheng Ji, Hao Peng, and Jianxin Li. Environment-aware dynamic graph learning for out-of-distribution generalization. arXiv preprint arXiv:2311. 2023.
(59) Qianru Zhang, Chao Huang, Lianghao Xia, Zheng Wang. Siu Ming Yiu, and Ruihua Han. Spatial-temporal graph learning with adversarial contrastive adaptation. In International Con- ference on Machine Learning, pages 41151 1111-41163. PMLR, 2023.
[60] Qianru Zhang, Lianghao Xia, Zhonghang Li, Siu Ming Yiu, and Chao Huang. Simple yet effective spatio-temporal prompt learning.
[61] Zeyang Zhang, Xin Wang, Ziwei Zhang, Haoyang Li, Zhou Qin, and Wenwu Zhu. Dynamic graph neural networks under spatio-temporal distribution shift. Advances in Neural Informa- tion Processing Systems, 55:6074-608,, 2022.
[62] Zijian Zhang, Xiangyu Zhao, Qidong Liu, Chunxu Zhang, Qian Ma. Wanyu Wang, Hongwei Zhao, Yiqi Wang, and Zitao Liu. Promptst: Prompt-enhanced spatio-temporal multi-attribute prediction. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pages 3195-3205, 2023.
[63] Zhengyang Zhou, Qihe Huang, Kuo Yang, Kun Wang, Xu Wang, Yudong Zhang, Yuxuan Liang, and Yang Wang. Maintaining the status quo: Capturing invariant relations for ood spatiotemporal learning. 2023.
[64] Zhengyang Zhou, Yang Wang, Xike Xie, Lianliang Chen, and Hengehang Liu. Riskoracle: A levute-level citywide traffic accident forecasting framework. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 1258-1265, 2020.
[65] Zhengyang Zhou, Kuo Yang, Wei Sun, Binwu Wang, Min Zhou, Yunan Zong, and Yang Wang. Towards learning in grey spatiotemporal systems: A prophet to non-consecutive spatiotemporal dynamics. In Proceedings of the 2023 SIAM International Conference on Data Mining (SDM), pages 190-198. SIAM, 2023.
14

---

A Broader impacts
Dynamic graph learning models are widely used to support social development, such as recommen- dation systems and smart cities. However, with the increasing complexity of data scale and ap- plication scenarios, the distribution shifts between training and test data have become a significant obstacle in the development of dynamic graph learning. In light of this, our work aims to address the issue of data distribution shifts in the model and promote the broader application graph learning in various fields. Therefore, work aims to develop model with the -it-of--iitrbbutiion general- ization ability and thereby promote the widespread application of dynamic graph learning in various fields.
We ensure the full ethical compliance of our work, and all the datasets we utilize are publicly avail- able. Our work does not involve human subjects and does not introduce any potential negative social impacts or issues related to privacy and fairness.
B
Notations
Table 5: Classification accuracies for naive Bayes and flexible Bayes various data sets.
NOTATIONS
DESCRIPTIONS
9 {
A DYNAMIC GRAPH ACROSS 7 STEPS
G -VV 1","""
A t-STEP GRAPH WITH THE NODES VI, FEATURES X' AND EDGES A THE FEATURE MATRIX X OF t-STEP GRAPH SNAPSHOT
X E ERND
E RxxNxd
LEARNABLE PROMPTS MATRIX OF Txxxx
X (Xx,
HISTORICAL OBSERVATIONS IN PREDICTION TASKS
Xs = (V", ",',
HISTORICAL OBSERVATIONS REPRESENTED BY DYNAMIC SUBGRAPHS
TEMPORAL ENVIRONMENT VARIABLE PREDICTION TASKS
THE FUTURE EVOLUTION TREND IN PREDICTION TASKS
Xx
OBSERVABLE FEATURE OF HISTORICAL OBSERVATIONS
Yx
THE OBSERVED LABELS WITH EVOLUTION PATTERNS
ZE
CONTINUOUS FEATURES OF ENVIRONMENT VARIABLES
Z
NODE EMBEDDING BY ENCODING ORIGINAL FEATURES
SPATIAL VARIABLE STRUCTURAL CAUSAL MODEL.
20(-)
A ATSSSTAOTNNNO NETWORK
ho(-)
A SPATIO-TEMPORAL NETWORK BACKBONE
1+()
A SPATIO-TEMPORAL NETWORK BACKBONE FINAL PREDICTION STAGE
C Detailed Proof of Theorem 3.1
Lemma 3.1. (The Chain Rule for Mutual Information (2]) For any set of random variables X, Y. and the chain rule is expressed as
Y,) (
(17)
where I(X;Y,) Z) denotes the mutual information between X, Y, and Z, I(X;Y) represents the mutual information between X and Y, and [(X; Z(X represents the conditional mutual information between and given Y. The rule signifies that the overall mutual information in the system can be decomposed into two components; the mutual information between X and Y, and the conditional mutual information between X and Z given Y. It reflects how information transmitted and shared within complex systems.
Theorem 3.1. If there exists causal relationship between unseen environment pattern Zig and the label Xx, ZE is the optimal solution of SPL objective.
Proof. Consider The Chain Rule for Mutual Information, we derive the following equation:
1(Zg; Yx) 1(Yx; ZE) (Xx: Yx|
(18)
15

---

1[ Xx. - I(xx Yx) I(X Yx
(19)
Zg Yx). We then get (Z.g Yx) 3T: = T(x:: Xx. -x) Vx|ZE)-B1(Xx
Thus, optimizing Eq. F is to maximize T(Yx: XxX Zg) and minimize (1 [)x(xx: Yx/Zg)
(I(Xx: LE, Yx). Next, we investigate whether Ze is the result of optimization.
(i) Maximizing (Yx; Xx, Zæ) reflects the combination of Xx and Eæ can make optimal prediction. Since Xx is constant, Ze Ze ensures that the features used for prediction have the greatest overlap with the ground-truth.
(ii) Since [Xx; Ix 0 and [(x: Ze, Yx) O. If [0, the lower bound of (1 (xx; Yx Yx(ZZ) [g) (Tx:x Ze, Yx) is O. Next, we prove our SPL. can achieve T(Xx: Yx ( = 0 and T(xx; Zg. Xx)) 0 in detail. π(Xx: Yx|Z,g) represents the conditional mutual information between Xx and Yx given Z Because we manually add random noise at Eq. HL our model can be
viewed map Yx f(Zg) +.. Obviously, is independent of Yx. We can get / (Xx; Yx(Zg)
0. [Xx: gg Yx)) = 0 is also proven the independence between Xx and Z
We have proved it.
D Causal Interpretation of Dynamic Subgraphs
E
Xs
Y
(c)
Figure 5: SCMs of dynamic graph. (a) Traditional generation understanding of dynamic graph; (b)
Indirect effect of environment factors; (c) Dynamic subgraph as mediating variable.
With the causal theory [[8]] we can build a coherent progression for the proposal of EpoD.
The Structural Causal Model in the dynamic graph. The Structural Causal Model (SCM) in the dynamic graph fosters deeper understanding of the generation process spatio-temporal graphs. Many methodologies have achieved impressive performance in addressing the issue of spatial-temporal distribution shifts. The widely utilized SCM is shown in Fig. (l
E X < C. The historical observation consists of two parts: temporal environment variable and spatial context C. In many works, these aspects are often treated as disjoint factors and discussed decouplingly, i.c. E ELG C.
E + C. Temporal environment variable E and spatial context C also determine the future evolution trend Y. Most studies keep this assumption that historical observations and future evolution Y are influenced by the same E and C. However, this is not the case in the real-world dynamic graphs, giving rise to the distribution shift issue.
X Y. Historical observations are useful for predicting future evolution. A thorough understanding of historical observations serves as crucial foundation for exploring the invariant evolution model of dynamic graphs.
The mediating effect the dynamic graph. The efforts on how temporal environment factors and spatial contexts influence the evolution of dynamics graph has been extensively made. However, even though some studies claim disentanglement of spatial-temporal dependencies, it is acknowl- edged that true separation may not be fully achieved. Most of them inherently concentrated on exploring the interplay between spatial and temporal dynamics. fact, some pioneering researches have revealed the temporal evolution mostly stem from the changes over spatial dependencies. To this end, we further summarize such indirect influence as mediating effect within dynamic graph, as shown in Fig. EXb).
16

---

E + C - X. The historical observation X is seen the evolution process of spatial context C, where C covers the temporal environment information E.
X C + Y. Spatial context directly determine current observations and future evolution trend Y.
But according to the complete mediation effect theorem, this SCM eliminates the direct effect of temporal variable on future spatio-temporal evolution This necessitates us to contemplate whether C has the capacity to serve mediation variable. Given the time-varying property in dynamic graph, the only spatial context cannot sufficiently interpret the temporal evolution of graphs. Therefore, mediating variable simultaneously encapsulating spatial dependencies and temporal dynamics required.
Dynamic subgraphs as mediating variables. The dynamic spatial variations induced by environ- ment factors are essentially rooted in the changes of local dependencies. Thus, novel SCM is introduced, which employ dynamic subgraph Xs as the mediation variable as illustrated in Fig. Eic..
X + C Xs - Y. Dynamic subgraph Xs is more abundant than the spatial context C. In other words, dynamic subgraph Xs utilizes substructures to encompass spatial information C, capturing temporal environment factors E through dynamic evolutive subgraphs.
Dynamic subgraphs exhibit both temporal and spatial characteristics, also serve as the mediation variable from X
This design offers us a chance to address distribution shift issue along the practices of causal adjustment [28]. We can observe back-door path between causal path X and Y. i.c. X + C + Xs + Y. The backdoor adjustment pattern leveraging do-calculus on dynamic subgraph Xg is,
P(Y y/ = x))= P y Z, X5 = x5) P(Xs x.5)
(20)
as
In essence, our EpoD can be viewed employing backdoor adjustments to estimate P(Y|do(X) by discovering dynamic subgraphs, where the prompted environment supports subgraph discovery process.
E
Experiment Details
E.1
Datasets
Our experimental design included the selection of seven real-world dynamic graph datasets from two distinct domains. The detailed statistics of the datasets are shown in Tab. R. We select shifted link attribute from COLLAB, Yelp and ACT datasets respectively to simulate the distribution shift scenario in the real world. The shifted attribute links become accessible only during the out- of-distribution (OOD) testing stage. This scenario is more practical and challenging in real-world situations, the model cannot capture any information about the filtered links during training and validation.
PEMS08 [G4] is collected from the Caltrans Performance Measurement System (PeMS), which records the real traffic network flow data from 07/01/2016 to 08/31/2016. It delineates dynamic graph data of a traffic network with 170 sensors across 17,856 steps. Among the known traffic datasets, it falls into the category of small-scale dataset.
PEMS04 [4]] records the real traffic network flow data from 01/01/2018 to 02/28/2018. It describes dynamic graph data of traffic network with 307 sensors across 16,992 steps. It belongs medium-scan scale traffic dataset.
SD !24 is sub-dataset of the large-scale dataset CA proposed by [22]] It comprises traffic flow data recorded by 716 sensors in San Diego county from 01/01/2017 to 12/31/2021.
GBA [24]] is larger traffic dataset than SD, which is also sub-dataset of the large-scale dataset CA. contains traffic flow data provided by 2,352 sensors in counties situated in the Greater Bay Area from 01/01/2017 to 12/3 1/22.......
17

---

COLLAB |00 is an academic collaboration dataset comprising papers published between 1990 and 2006, spanning 16 graph snapshots. this dataset, nodes represent authors, and edges represent co- authorship relationships. The edges include five attributes based on co-authored publications: "Data Mining". "Database", "Medical Informatics", "Theory" a "Visualization".
Yelp [KX] is dataset containing customer reviews on businesses. In this dataset, nodes represent customers and businesses, while edges capture review behaviors. The edges are associated with five attributes based on business categories: "Pizza", "American (New) Food", "Coffee & Tea", "Sushi Bars" and "Fast Food".
ACT [ characterizes student interactions on a MOOC platform over a span of one month, consist- ing of 30 graph snapshots. In this dataset, nodes represent students or the targets of actions, while edges signify various student actions.
Table 6: Statistics of the real-world dynamic graph datasets.
DATASET
# NODES
# EDGES
# GRAPH SNAPSHOTS
TEMPORAL INTERVAL
PEMS08
170
276
17,856
5 MINUTES
PEMS04
307
338
16,992
5 MINUTES
SD
716
17.319
525,888
5 MINUTES
GBA
2,352
61,246
525,888
5 MINUTES
COLLAB
23,035
151,790
YEAR
YELP
13,095
65,375
24
MONTH
ACT
20,408
202,339
30
1 DAY
E.2
Detailed Implementation
Algorithm 1:
The training process of EpoD
Input: historical dynamic graph data X (g'TT=
Initial: dynamic graph encoders he and fa, cross-attention mechanism decoder go. learnable prompt P. the number of epochs K
for i to K do
Environment prompt stage: Zg (P, Z) e, Z ha (E ((O,))
Yx = Lincar (Zg)
Environment utilization stage:
S' = (M')T- N' as shown in Eq.
A' O (At) OA'),,
== CON ZE))
Xs = (9' = 10',"",AA7
Y (Xs)
Optimizing:
min C = EEllo P. (Y|Xs) + log Pa.o Xx, P)] (P (2
6.O.P.V
end for
Return h2g for go and P
We implement EpoD with Py PoTch 1.11.0 on server with NVIDIA A A100-PCIE-40GB. The detailed training process shown in Alg. M. All experiments are repeated with 10 different ran- dom seeds of [1.2.3.4.5.6.7.8.9.. obtained from these 10 runs.
The reported results include the mean and standard deviation
Traffic flow prediction. In the experiments of traffic flow prediction, our task is to predict the next 24 steps based on the historical 12 steps observations (12 - 24). Besides, we choose traffic data from the SD and GBA datasets from 2019 to 2020 in order to add the distribution shift scenarios arising from COVID-19. The selected spatio-temporal graph neural network backbone is Adaptive Graph Convolutional Recurrent Network (AGCRN) [E].
18

---

Social link prediction. The task of social relationship analysis is to exploit past graphs to make link prediction in the next time step. Following the measures of [6I]] we introduce perturbations to test data to simulate the scenario of distribution shift in those datasets. Specifically, we select Data Mining and Pizza as the shifted attributes COLLAB and Yelp. For dataset ACT, we employ K-Means to cluster the action features into five categories and randomly select a certain category (the 5th cluster) of edges as the shifted attribute. Besides, Disentangled Dynamic Graph Attention Networks (DDGAN) [6]]] is chosen our spatio-temporal graph neural network backbone.
E.3 Metries
We utilize Mean Absolute Error (MAE) and Root Mean Squared Error (RMSE) to assess the per- formance of EpoD and baselines. Both metrics quantify the error between model predictions and actual observations regression tasks. A smaller value for these metrics indicates better model performance. MAE less sensitive to outliers due its use of absolute differences, while RMSE is more sensitive to large errors due to its use of squared differences. Given the actual observation Y; and the corresponding predicted value Y for samples, two metrics are calculated as follows:
1 Yi Yi
MAE =
(21)
71
RMSE
Σ (Y, -
(22)
E.4 Toy dataset
We manually design toy dataset EnyST with temporal distribution shift explore the generalizabil- ity of EpoD. Tab. 7 describes the statistical information EnvST. Specifically, EnvST illustrates the evolution sequence of graph with 100 nodes across 1000 steps, where the topology of each snap- shot does not change over time. The feature of each node in EmvST encompasses three components, i.e, [ΣA, TB, Icl, where FA and z represent evolution-causse features but TB is masked after the data is generated, Ee indicates available evolution voluuion-spurious feature. To simulate the temporal distribution shift in the dynamic graph, the training and test dataset of a TB and Ie are sampled from distributions with significant differences separately. The label of each node on the Em:ST at I step activated by updated feature of (ern(a(2()) where ((-) the sigmoid function.
XA
Available evolution-causal feature Unseen evolution-caude feature
Available evolution-spuriioss featur
Figure 6: Feature description of the toy dataset.
Table 7: Statistics of the toy dataset.
NOTATION
DESCRIPTION
DIMENSION
N
THE NUMBER OF NODES IN THE GRAPH
100
T
THE NUMBER OF EVOLUTION STEPS OF DYNAMIC GRAPHS
1 1000
AVAILABLE CILLUTION-CAUSA.A FEATURE
3
TB
UNSEEN EVOLUTION-CAUSAL FEATURE
3
JC
AVAILABLE EVOLUTION -SPUUIOOS FEATURE
3
EVOLUTION LABEL
1
As shown in Fig. B the feature of each node in EnyST' encompasses three components, i.e., [I &B, Ecl. FA and 2g represent evolution-causal features but æg is masked after the data is generated,
19

---

indicates available evolution- evolution-spurious feature. To simulate the temporal distribution shift in the dynamic graph, the training and test dataset of x. z8 and ze are sampled from distributions with significant differences separately. The label of each node on the EnvST' at / step is activated by updated feature vf (e))) where (.) is the sigmoid function. The feature is updated by aggregating the neighbor information of the last & time steps.
2
Σ
Aggregate( (3))
(23)
1 EJENS
Performance (MAE)
11.0
10.5
10.0
Figure 7: Performance is influenced by spurious information.
We conduct experiments from the following two aspects: 1) we investigate whether EpoD has the capability to perceive masked environment feature zB, 2) we study whether EpoD can identify and remove the spurious correlation IC.
Powerful perception for unseen environment. Fig. 3 and b show the distribution difference between masked feature and prompted environment feature Zg. where experiments are con- ducted on EnvST under the scenario of distribution shift. There is no doubt that ZE can match the masked z in the steady historical observation sequences, before shift point in these figures. More importantly, we focus on the perception ability of prompt learning after the distribution shift occurs. First, we categorize the scenarios of temporal distribution shift into two types: sharp shifts and shifts with signals. The former indicates that any distribution shift signal can not be obtained from histor- ical sequences. Fig. Ma shows our prompted environment feature Zg can still cover more than half of the shifted features in the future steps. The latter illustrates the signals of distribution shift has begun to emerge slightly in historical observations, which is commonplace scenario in the real world. For example, those individuals who were used to planning purchased warm clothes in advance before the temperatures plummeted. As shown in Fig. Bbb), observe that our prompted environment variables can effectively cover slight early signal and utilize it to tackle OOD issue.
Robust spurious information identification ability. We then explore whether our EpoD can filter out the disturbance of rc. Specifically, we have following experiment design. Consider ve sampled NromM(ja (1,, I), we set E [0, 10) and record the performance of EpoD under the influence of different spurious information as shown Fig. We can observe that the fluctuations in prediction performance consistently fall within the acceptable error bounds. Therefore, we conclude that EpoD have the ability to identify spurious information DC.
F
More Realted Works
Dynamic Graph Learning. Graph Neural Networks (GNNs) [TU,
[6] and Sequence Neural Networks (SNNs) [56 [15]] have been extensively studied and have achieved great success in real-world tasks. The GNN models we often use are GCN, GIN, PNA, etc; SNNs include LSTM, RNN, TCN, etc. Therefore, spatio-temporal graph learning models have been widely studied in re- cent years [550, 36,, 85, IT. EKL 92). Based on varying interpretations of the correlation between tem- poral and spatial information, the current works are undertaken along two research lines. One claim to study temporal and spatial information a decoupled manner, which is potentially present in most current works
[L 19, 61]. Due to the intricate temporal and spatial relationships in reality, they
20

---

often fail to offer sufficient interpretability and generalizability. The other one argues that spatial context is influenced by the temporal information [65. b33] These methods depict spatiotemporal scenes that align more closely with the complexities of the real world. Moreover, this also presents a feasible approach to tackle the distribution shift issue arising from the changes of temporal envi- ronment. Our work falls into advancing the latter research line by exploiting causal structure model.
Subgraph Learning. Subgraph learning, with its robust causal interpretability, has achieved remark- able success in static graph applications, such as molecular property prediction and social network analysis [25 57 E8, 21]]. In essence, captures the inductive bias inherent in graph data that lo- cal dependencies are invariant patterns predicting ground-truth We argue that dynamic subgraphs may exhibit similar inductive bias apatio-tempont evolution. But dynamic subgraphs remain an unexplored area with no existing studies. To this end, this paper introduces dynamic subgraph learning mechanism address the issue of temporal distribution shift resulting from the changes of environment factors.
G Additional Results
G.1 Hyperparameter Sensitivity Analysis
We analyze the sensitivity of the hyperparameter 3 in Eq. E which functions as the trade-off for the loss in Eq. SL The value range of B is [0, 1]. We perform experiments on four real-worke datasets, i.e, PEMS08, PEMS04, SD, Yelp, and present the results in Fig The results show that the sensitivity of the prediction results to ,8 is not very drastic. But the performances of EpoD on four datasets are best when 3 E [0.2, 0.5]. Therefore, we set 0.2 in our implementation.
(a) PEMS08.
(b) PEMS04.
(c) SD.
(d) Yelp.
Figure 8: Sensitivity analysis of the hyperparameter 3 four real-world datasets.
We then analyze the sensitivity of hyperparameter L in Eq. I As shown in Tab. M we study the performance of EpoD when L is set to 11 10]. We observe that increasing the value of L tends to improve its performance. However, it is important to note that this improvement comes at the cost of increased time consumption. Therefore, we set L as a trade-off between performance and time consumption.
Table The performance (MAE) of different L in Eq.
PEMS08.
Model
1
2
3
4
5
7
10
EopD
18.87
18.21
17.76
17.25
17.43
17.13
16.92
16.65
16.58
16.96
G.2
Backbone Sensitivity Analysis
Our EpoD essentially provides solution for temporal distribution shits issue in dynamic graphs. The most prominent characteristic of EpoD the pluggability, which denotes that we can be applied to numerous existing backbones. In the task of traffic flow prediction, explore the performance associated with the selection of different models as backbones as shown Tab. g We get the following two observations.
Obs The EpoD-enhanced version consistently shows a significant improvement over the raw backbone. On large-scale datasets with distributional shits, EpoD tends to exhibit more substan-
21

---

Table 9: The MAE performance of EpoD with three different backbones (12 - 24).
MODEL
PEMS08
PEMS04
SD(2019-2020)
GBA(2019-2020)
ASTGCN LIC
19.34
22.89
28.36
32.58
EOPD+ASTGCN
17.75
21.78
26.72
28.76
DSTAGNN [19]]
17.56
21.22
26.34
30.11
EPOD+DSTAGNN
17.21
20.76
24.89
27.89
AGCRN [G]
17.30
21.19
26.19
28.74
EOPD+AGCRN
16.92
21.12
23.58
27.26
tial performance improvements. This highlights the effectiveness of our EpoD in addressing the distribution shift issue.
Obs 2.
The expressive capacity of the backbone directly influences the predictive ability of the model enhanced by EpoD. Since the performance of AGCRN already excellent, the enhancements introduced by EpoD often result in optimal results. This underscores the importance of selecting proficient backbone model for forecasting.
G.3 Interpretable Dynamic Subgraphs
In this subsection, we explore the interpretability of dynamic subgraphs under real-world scenarios. In recent years, the most notable -iaporrlldistributtin shift phenomenon is the outbreak of COVID- 19. The introduction of LargeST [22]] provides a chance for us to study this distribution shift of traffic flow under COVID-19, We choose local sensors network in GBA dataset and reconstruct its evolution data at monthly intervals from 2019 (I = 1,... T' to 2020 (L = T + 1,... + k). Then, apply our Epol) trained 2019 data partition each snapshot into bag of subgraphs, shown in the top panel of Fig. E It is evident that the nodes tend to suppress communication among themselves when the distribution is shifting, and this phenomenon is particularly pronounced around the three blue nodes. The bottom panel of Fig. visualizes the ground-truv truth of this sequence, which aligns with the information reflected in our dynamic subgraphs. This suggests that EpoD exhibit sensitivity to environment changes.
t=1
t=T-1
t= T
T+1
T
Figure 9: The interpretability dynamic subgraphs within real-world scenarios.
22

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction of this paper clearly outline contributions and important assumptions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Our manuscript contains "Limitations and Future Works" section in Sec.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

Justification:
We provide a comprehensive proof of our proposed theory.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proof's provided in appendix or supplemental material. Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We release the code using anonymous links.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
24

---

Answer: [Yes]
Justification:
We release the code using anonymous links.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g,, for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:)
//nips.com httpps..c/publicguuudeeeeee www.bl/c/gguide/odeeeututtee wtw.:idddeeeodSSeeiiiiiiesssse
sss.esuubmssiioooooccc. for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
We describe our experiment setup in detail.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The quantified results provide statistical results (mean and standard deviation), obtained from conducting experiments with 10 different random seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
25

---

It should be clear whether the enror bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative еπхо rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide the resources (type and number of GPUs) that we conduct our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary failed experiments that didn't 't make it into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We have already read the NeurIPS Code of Ethics
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss both potential positive societal impacts and negative societal im- pacts of our work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
26

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our effort aim to address unresolved questions in the field, and all datasets we used are public datasets.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We thoroughly introduce all works that related research, and care- fully check the original license.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
license, copyright information, and terms use in the pack- age should be provided. For popular datasets, soperswithcodd www.ccocccc..oc datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
assets are released,
27

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification:
We have released the license of our code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "kLM3Ex5Yik", "reviewer": "Reviewer_Zz1E", "summary": "The paper introduces EpoD, a novel dynamic graph learning model that leverages prompt learning and structural causal models to address out-of-distribution (OOD) generalization challenges. EpoD features a self-prompted learning mechanism for inferring environment variables and a node-centered subgraph extractor to capture data distribution shifts. Extensive experiments across various real-world datasets demonstrate EpoD's superior performance and interpretability, highlighting its potential for practical applications in fields like traffic forecasting and social network analysis.", "questions": "N/A", "limitations": "See in the weakness", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a novel dynamic graph learning model named EpoD, leveraging prompt learning and structural causal models to address environment inference and utilization. The self-prompted learning mechanism and node-centered subgraph extraction represent significant advancements in the field.\n\n2. The authors provide a solid theoretical framework supporting the generalizability and interpretability of EpoD. The incorporation of structural causal models and dynamic subgraphs as mediating variables showcases a deep understanding of the underlying principles of dynamic graph learning.\n\n3. The paper presents extensive experiments across seven real-world datasets from diverse domains, demonstrating the superiority of EpoD over several baseline models. The inclusion of a toy example experiment further validates the interpretability and rationality of the proposed model.\n\n4. The results indicate that EpoD consistently outperforms existing methods in terms of both mean absolute error (MAE) and root mean square error (RMSE) for traffic flow prediction, as well as AUC scores for social link prediction tasks. The significant improvements on large-scale datasets highlight the model's robustness and scalability.\n\n5. The dynamic subgraph extraction process and the use of node-centered subgraphs enhance the interpretability of the model. The paper effectively demonstrates how dynamic subgraphs can capture the impact of environment variable shifts on data distribution.\n\n6. The model's ability to generalize across different domains and datasets suggests strong potential for practical applications in various fields, such as traffic forecasting, social network analysis, and air quality prediction.", "weaknesses": "To be honest, I did not find obvious drawbacks of this work. Some minor revision might be helpful: \n\n- use the mentioned all-in-one (citation [39] in their manuscript), a more flexible graph prompt as your environment vector. Or see the impact of different graph prompt formats. \n- The discussion on future work and the limitations of the current approach could be expanded. For example, I think this work might be helpful to be applied in some sociological analysis. The environment concept might be also inspiring to the similar concept in this paper: Self-supervised Hypergraph Representation Learning for Sociological Analysis. TKDE. 2023.\n\n\nOverall, this paper presents a significant contribution to the field of dynamic graph learning, with innovative methods and strong experimental results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Zz1E,\n\nThank you for your valuable time in reviewing our manuscript. We greatly appreciate your positive comments on our work, and your insights are invaluable to us. We will provide detailed replies to your questions next.\n\n**W1. More extensive prompts design.**\n\nOne of the purposes of our work is to introduce the concept of prompt learning for the preliminary exploration of spatio-temporal OOD. This is why we designed a relatively simple node-wise learnable vector prompts. Excitingly, the effectiveness of EpoD demonstrates that prompt-based methods can bring new vitality and potential to spatio-temporal graph learning. Therefore, as you suggested, exploring more diverse forms of prompt $\\mathbf{P}$ tailored for spatio-temporal scenarios can be the next direction pursue. Specifically, we outline the following analysis and plans for future research.\n\nRef.[1] verified that graph-structured prompts can enrich the semantics of graph learning. However, directly applying this method to spatio-temporal graph learning may not offer strong interpretability. The reason lies that the dynamic nature of spatio-temporal graph introduces new challenges, particularly concerning the impact of temporal heterogeneity on the inserting patterns and number of designed prompts.\n\n- Regarding the graph-structured prompts $\\mathbf{P}$, we will explore whether to insert $\\mathbf{P}$ into $G$ in a manner similar to [1], or to design an interactive framework to achieve semantic learning as proposed in EpoD.\n\n- Further, we will investigate whether it is necessary to design temporal-specific graph prompts to fully capture the underlying environmental information in each time step.\n\n\n\n**W2. Sociological analysis.**\n\nWith a preliminary investigation,  we find that social networks share the similar spatiotemporal evolution process of the ST graph investigated in this work. To this end, our work has significant potentials for application in sociological analysis, leading to a promising direction of our future research. As Ref.[2] mentioned, regarding the social equivalence and social conformity effect, individuals in social networks tend to either form their own groups or become assimilated into the environment over time. We argue that the key characteristics of this process are its gradual temporal progression and environmental orientation.\n\nOn one hand, the changes of individuals are usually not sudden; instead, they gradually become apparent over time and eventually lead to transformation. This temporal progression provides a solid foundation for studying social networks from a spatio-temporal perspective.\n\nOn the other hand, individual evolution typically aligns with the direction of the environment. However, the environmental space within social networks is complex and challenging to capture. As a result, inferring the local or global social environment within these networks becomes a crucial challenge. Fortunately, the environment inference and subgraph learning in our EpoD have the potential to effectively address this challenge.\n\nThese two aspects indicate that our work has the potential to be applied to sociological analysis. Specifically, the environment inference and subgraph learning mechanism we proposed naturally align with these challenges. We are very interested in further exploring this direction in our future work, and we will incorporate above analysis into our manuscript.\n\nThank you for your insightful comments, many of which deepen our understanding on this work. They also inspire our future research directions. We appreciate your thorough review once again.\n\n\n**References:**\n\n[1] All in one: Multi-task prompting for graph neural networks.\n\n[2] Self-supervised Hypergraph Representation Learning for Sociological Analysis.", "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": "", "extra_scores": {}}, {"review_id": "CWnBFpM7tE", "reviewer": "Reviewer_XPEX", "summary": "The paper is about dynamic graph learning, which is an interesting topic. The authors propose a novel dynamic graph learning model named EpoD based on prompt learning and structural causal model to comprehensively enhance both environment inference and utilization. The paper is well written and well organized. However, there are several concerns in the current version of the paper that addressing them will increase the quality of this paper.", "questions": "As above.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1 New perspectives on theory.\n\n2 Good writing.\n\n3 Fully experimented.", "weaknesses": "1 Regarding the OOD research of dynamic graphs, I have a question: when new nodes appear in the data (rather than the known number of nodes), how should the model construction be handled?\n\n2 Would like to see a discussion of computational complexity, both time complexity and space complexity.\n\n3 The details of the datasets should be included in the text (rather than in the appendix), such as the size of the datasets. In addition, it seems that the size of these datasets is limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer XPEX,\n\nThank you very much for your thoughtful review! We have carefully considered your comments, and we will provide detailed responses below. We hope these details can address your concerns.\n\n**W1. The ability to counter structural distribution shifts of EpoD.**\n\nAddressing node-scale distribution shifts is a key challenge in spatio-temporal OOD research. Actually, our EpoD can effectively resist structural distribution shifts with simple modifications. Here, we introduce a strategy of modifying EpoD to counter these shifts, along with the rationale behind it.\n\n- The learnable prompt tokens $\\mathbf{P} \\in \\mathbb{R}^{N \\times d}$ is the only component in EpoD sensitive to node scale. To counter structural distribution shifts, we can introduce a neighbor-sharing prompt strategy. When a new node is added, the prompt token for this new node will be populated based on the prompt token of the node to which it is most closely connected, resulting in a new environment prompts $\\mathbf{P} \\in \\mathbb{R}^{(N + 1) \\times d}$. When a node is removed, we eliminate the corresponding node's prompt token, resulting in a new environment prompt $\\mathbf{P} \\in \\mathbb{R}^{(N - 1) \\times d}$. The new prompt is utilized to update the following learning flow. \n\n- The insight of this design lies in that both temporal and structural distribution shifts can be distilled into the shifts of environmental variables. Specifically, temporal distribution shifts arise from the shift of environmental factors, while structural distribution shifts essentially impact the expression of environments in spatiotemporal data. \n\nTo verify the effectiveness of this modification, we conduct some preliminary empirical studies on the adjusted SD-2019 dataset, i.e., SD-2019-MaskNodes. Specifically, we randomly mask 10\\% of the nodes in the training set and restore them to 716 nodes in the test set. We present the final performance (MAE) by averaging the results from two runs conducted on an NVIDIA A100-PCIE-40GB. Since none of the existing methods are designed to address the structure distribution shift, we were unable to find a suitable baselines for comparison. As shown in the following table, EpoD shows only a slight performance degradation on SD-2019-MaskNodes, and outperforms most methods on SD-2019.\n\n|      | SD-2019 | SD-2019-MaskNodes|\n|   :--:   | :--:   | :--:   | \n| EpoD(MAE) | 16.89 | 17.12 |  \n\n\n**W2-1. Time complexity analysis.**\n\nWe analyze the efficiency of EpoD theoretically and practically. \n\n- We utilize $|V|$ and $|E|$ to denote the number of nodes and edges in the graph, $d$ to represent the dimension of implicit representation, and $T$ to represent the time step of historical observations. The time consumption mainly comprises three components: the spatio-temporal graph aggregation process, the prompt answer process, and the dynamic subgraphs sampling process. The time complexity of the spatio-temporal aggregation is $O(T \\cdot (|E| \\cdot d + |V| \\cdot d^2))$. The prompt answer process primarily involves a cross-attention operation, with a time complexity of $O(T \\cdot |V| \\cdot d)$. The dynamic subgraphs sampling module implements node-centered sampling, with a time complexity of $O(T \\cdot |V|)$. Therefore, the time complexity of EpoD is $O(T \\cdot d  \\cdot |E| + T \\cdot (1+d+d^2) \\cdot |V|)$. In conclusion , EpoD exhibits linear time complexity concerning the number of nodes and edges, which is competitive with existing dynamic GNNs such as DIDA, EAGLE, and CaST.\n\n- We also conduct efficiency comparisons of EpoD, DIDA, and EAGLE in COLLAB, Yelp, and ACT datasets, measuring the time taken per epoch (s/epoch). All experiments are run on an NVIDIA A100-PCIE-40GB. Empirically, we observe that the operational efficiency of our method is competitive with existing approaches.\n\n|      | DIDA | EAGLE| EpoD |\n|   :--:   | :--:   | :--:   |  :--: |\n| COLLAB | 11.21 | 12.05 |  11.84 |\n| Yelp |  6.89  | 7.38 |  7.34  |\n| ACT | 9.27 |  9.76  |  9.59 |\n\n\n\n**W2-2. Parameter scale analysis.**\n\nThe increased complexity of EpoD is mainly reflected in the introduction of the environment prompt module. As shown in following Table, we compare the number of parameters with several baseline models on SD-2019. We find that the increase of our model size was not prominent. Given the performance  achieving 1.8\\% improvements on MAE  under temporal shifts, such sacrifice in parameter complexity is acceptable and deservable.\n\n|      | GWNET | STGNCDE| DSTAGNN | CaST| EpoD |\n|   :--:   | :--:   | :--:   |  :--: |:--:   | :--:   | \n| Parameters | 311K | 729K |  3.9M | 652K |  894K |\n\n\n\n**W3. The details of the datasets.**\n\nDue to the page limitations of each submission, we had to place some static content, including the dataset description and baseline details, into the appendix. We appreciate your feedback and will move Tab. 5 into the main text in the next version.  \n\nMoreover, we have already chosen some of the largest datasets in the field, such as the large-scale traffic datasets LargeST (SD, GBA), as well as large-scale social network datasets COLLAB and ACT. When new large-scale datasets are introduced, we will promptly validate our EpoD on them.\n\n\nThank you again for your constructive comments on our work. We will take your comments into account to further improve our manuscript. Looking forward to your feedback!", "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": "", "extra_scores": {}}, {"review_id": "TTmBAZ1gF4", "reviewer": "Reviewer_5ZgN", "summary": "This paper provides a novel dynamic graph learning framework EpoD to tackle the temporal distribution shift issue by exploiting prompt learning. EpoD addresses two limitations of existing works regarding inference and exploitation of unseen environments. The EpoD includes two modules, i.e., self-prompted environment inference component and dynamic subgraph learning component, where the former extracts underlying environment variables that potentially influence data distribution, while the latter effectively and interpretably exploits the inferred environment embedding for dynamic subgraph generation. The experiments design several distribution scenarios for evaluation and empirically demonstrate impressive performance under distribution shift scenarios.", "questions": "Please answer the questions in Weaknesses.", "limitations": "The authors have discussed the broader social impacts and limitations of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**S1.**  Well-written and clearly organized. This work decouples the OOD issue into environment inference and utilization challenges, addressing each separately. Moreover, empirical examples and theoretical analysis enhance the accessibility of the paper for readers.\n\n**S2.** Qualified technical contributions. EpoD addresses two limitations of existing works regarding inference and exploitation of unseen environments with two well-designed modules, environment prompting and dynamic subgraph learning, which innovatively leverage successful experiences from LLMs to address the OOD generalization issue in dynamic graph learning. \n\n**S3.** Good experiment designs and comprehensive evaluations. The authors especially design several distribution scenarios for OOD task evaluation with consideration of the COVID-19 period.  Seven cross-domain real-world dynamic graph datasets are selected to evaluate the performance of EpoD.", "weaknesses": "**W1.** More detailed explanations and analysis will be more welcome and help readers better understand this manuscript. What is the unique superiority of the self-prompted learning mechanism in inferring unseen environments in spatio-temporal graph data? \n\n**W2.** It seems that self-prompt is borrowed from LLMs, thus what is the intuitive designing idea of self-prompt learning here, and how it works for environment inference?\n\n**W3.** Any other considerations besides efficiency when designing node-specific and time-shared prompt tokens? \n\n**W4.** There are many methods to extract subgraphs, the most popular one is to drop edges to realize the partition of graph data. What do you think are the advantages of node-centered dynamic subgraphs?\n\n**W5.** Some typos: \n\n- In line 254, \"dynamics graph\" should be modified to \"dynamic graph\".\n\n- In line 385, \"we\" should be modified to \"our\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 5ZgN,\n\nThank you for taking the time to review our work. We greatly appreciate your positive feedback and will address your comments with careful consideration.\n\n\n**W1. Advantages of self-prompted learning mechanism.**\n\n\nOur self-prompted mechanism has two key advantages that distinguishes from existing works:\n\n1. Our self-prompted mechanism focuses on modeling historical observations to infer the environmental space, which has not been explored. This approach ensures that the extracted environmental space aligns with spatio-temporal evolution patterns, rather than being an arbitrary expansion.\n\n2. We do not assume a predefined environmental scale. Our design infers unseen environment factors into a continuous space, which is remarkably distinctive from previous methods with predefined and discrete environment scales.\n\nActually, the above analysis has already been discussed in Sec. 3.1.\n\n\n**W2. Explanations of environment inference process.**\n\n\nOur self-prompted learning framework achieves the inference of unseen environment by a novel squeezing strategy, which is derived from analyzing the relationships between environmental variables $\\textbf{E}$, observable features $\\textbf{X}_ \\textbf{X}$, and evolutionary patterns $\\textbf{Y}_ \\textbf{X}$. Although inspired by LLMs, this insight makes our self-prompted module distinct from LLMs in both its objectives and implementation manners.\n\nSpecifically, given the availability of $\\textbf{X}_ \\textbf{X}$,  $\\textbf{Y}_ \\textbf{X}$ and $\\textbf{C}$, we adopt the strategy that infers  the environment in historical observations, i.e., $\\textbf{E} \\leftarrow {g_ \\theta }(\\textbf{X}_ \\textbf{X}, \\textbf{Y}_ \\textbf{X},\\textbf{C})$. \n\n$$\\mathbb{P}(\\textbf{X}, \\textbf{Y}|\\textbf{E},\\textbf{C}) = \\mathbb{P}(\\textbf{Y}|\\textbf{X},\\textbf{E},\\textbf{C})\\mathbb{P}(\\textbf{X}|\\textbf{E},\\textbf{C})$$\n\n\n\n\n**W3. Design principles of learnable prompt tokens.**\n\nOur prompt design is based on the principle that nodes in a dynamic graph have a baseline environment, but as time evolves, the environment tends to deviate from this baseline environment, resulting in data distribution shifts.\n\nThe node-wise and temporal-shared environment prompts $P$ we designed effectively construct such the baseline environments for each node, using learnable parameters to capture such environment factors in spatio-temporal data. Furthermore, the prompt answers, obtained through the interactive prompt-answer squeezing mechanism, reflect  the real environment representation at each time step.\n\n\n**W4. The advantages of node-centered dynamic subgraphs.**\n\nThe primary advantage of node-centered subgraph is its ability to accurately reflect the real-world influence of environment factors on dynamic graphs. Concretely, this design stems from a profound understanding of dynamic graphs, which is the shifts of environments  invariably lead to changes in the asymmetric correlations between nodes. For example, in a traffic network, environmental changes are often reflected by shifts in the flow direction between nodes. \n\nOur node-centered dynamic subgraph extractor can capture such node-specific asymmetry, with each node having a unique subgraph tailored for its environmental state. Compared to subgraphs obtained by simply dropping edges, node-centered subgraphs have a superior ability to capture and characterize spatio-temporal distribution shifts.\n\n\n**W5. Some typos.**\n\nThank you very much for your careful review, we will carefully check our manuscript to correct all typos.\n\nWe are very grateful for the constructive comments you provided on our work. Next, we will carefully refine our manuscript based on your suggestions. Looking forward to your further feedback!", "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": "", "extra_scores": {}}, {"review_id": "Hze2xZkK3F", "reviewer": "Reviewer_YNjr", "summary": "This work investigates the issue of spatio-temporal data distribution shift, which is a long-standing challenge in dynamic graph learning. First, the authors systematically analyze the limitations of existing works over OoD  challenge, and then propose a comprehensive solution to address their limitations.  Specifically, a self-prompted learning mechanism is proposed to extract underlying environment variables that potentially influence data distribution, and a novel causal pathway that leverages dynamic subgraphs as mediating variables is further introduced to effectively utilize the inferred environment embedding.  Comprehensive experiments on seven real-world datasets demonstrate the superiority of proposed EpoD.", "questions": "-  How can we understand the sentence \"Historical observations $X$ can be divided into the accessible environment features $X_X$ and observed labels with evolution patterns $Y_X$\" in Line 90?\n\n- This work presents a winding causal path to guide the utilization of environment variables. Is this causal path specific to dynamic graphs, can it be extended to other types of data? \n\n- It is intuitively meaningful to use the asymmetric quantization principle to extract the node-centered subgraph. Is there more illustrative exampls to depict such asymmetry?", "limitations": "This manuscript contains sections \"Broader impacts\" and \"Limitations and Future Works\". The authors have described the impact of this work, and discuss its limitations in those sections.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The motivation of this work is clearly described and convincing. This work proposes a novel framework to systematically tackle the  environment inference and utilization problem via profound understanding of the environment perception and limitations in existing OoD literatures.\n\n- This work proposes some interesting and pioneering learning components for dynamic graphs, including self-prompted learning and dynamic subgraph learning. \n\n- Sufficient experimental studies support the insights and framework of the paper. A toy dataset  verifies that the model can capture interpretable causal associations.", "weaknesses": "- It is widely agreed that unobservable environmental factors are the primary cause of shifts in data distribution. How does the self-prompted design ensure that prompt answers can capture unobserved environmental factors, without overlapping with the observable information?\n\n- There are some  minor typos, e.g.,  in Line105,  more consistent with -> is more consistent with.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer YNjr,\n\nWe would greatly appreciate your positive comments on our work. We have carefully considered your questions and have provided detailed answers as follows.\n\n**W1. The design of our self-prompted mechanism.**\n\nThere are some readily accessible environment factors in the original spatio-temporal data, such as recorded weather or the day of the week. These available environment variables are clearly not what our environment prompter intended to learn. Actually, our self-prompted mechanism is designed to avoid redundant learning, ensuring that our environment answers can  capture underlying environments that genuinely influences spatiotemporal evolution.  Specifically, the first term ${\\rm{KL}}(\\mathbb{P}_ \\theta({\\textbf{Z}_  E})||\\mathbb{P}_ \\phi(\\textbf{Z}))$ in the learning objective of Eq. 5 constrains our environment prompts to be dissimilar with the representations of the original data.\n\n\n$$\\mathop  {\\min }\\limits_ { \\phi ,\\theta, \\textbf{P}}{{\\cal L}_ P} =  \\beta \\mathbb{E}[ {\\rm{KL}}(\\mathbb{P}_ \\theta({\\textbf{Z}_ E})||\\mathbb{P}_ \\phi(\\textbf{Z}))]- \\mathbb{E}[ \\log  {\\mathbb{P}_ {\\phi ,\\theta}}({{\\textbf{Y}_ \\textbf{X}}}|{{\\textbf{Z}_ E}})]$$\n\n\n\n**W2. Minor typo.**\n\nThank you for your careful review on our manuscript. We have corrected the typo you pointed out and carefully reviewed our manuscript for other additional typos.\n\n\n**Q1. Interpretation of historical observations division.**\n\n\nAs above described, the original spatio-temporal data may contain some accessible environment features that are crucial for inferring future spatio-temporal evolution patterns. We take a more fine-granular approach by dividing the historical observations $X$ into accessible features $X_X$, such as the day of the week, and the evolution of labels in the historical observations $Y_X$. \n\nOur design differs from existing autoregressive methods that focus solely on historical evolution $Y_X$, as well as from approaches that mix $X_X$ and $Y_X$ into a single modeling entity $X$. The advantage of our approach is that it provides a comprehensive understanding of spatio-temporal data from a data generation perspective and helps us infer underlying environmental variables (features).\n\n\n\n\n**Q2. Explanation of the winding causal path.**\n\n\nOne of the most remarkable characteristics of spatio-temporal data is its dynamic nature, which results in the winding causal paths driven by environment shifts during evolution. In contrast, such winding causal paths are difficult to reasonably explain in non-temporal static data.\n\n\nThere exists a concept of environment in the graph data, e.g. graph size, which is the main factor affecting the data distribution shift. However, the causal paths in the graph data are generally invariant, such as the decisive role of specific functional groups in a molecule on its properties. Therefore, changes in the environment are less likely to alter these causal paths. In contrast, dynamic graphs are far more complex. It is challenging to distill a stable and invariant causal path of spatio-temporal evolution. In conclusion, we contend that this winding causal path is unique to dynamic graphs and time series.\n\n\n\n\n**Q3. Asymmetric quantization principle.**\n\nHere we offer a more intuitive explanation to clarify the concept  of asymmetry.\n\n\n- In traffic networks, traffic flow always maintains a directional and asymmetric transmission between nodes. Asymmetry means that the number of vehicles traveling between nodes is not equal. When the environment changes, the original asymmetric transmission mode will alter. For example, the change of weather conditions always leads to a shift in the direction of traffic flow, and build new asymmetric transmission.\n\n\n- In social networks, the influence of individuals is asymmetrical. People of high social status always have a profound influence on their followers, but the reverse is not necessarily true.  When the environment changes, the original asymmetric relationship may shift or break, leading to the formation of a new asymmetric relationship.\n\nInspired by such characteristics of dynamic graphs, we propose an asymmetric criterion to quantify environment effects. Further, we provides more interpretable insights through node-centered subgraphs.\n\n\nWe greatly appreciate your constructive feedback on our work. We will carefully refine our manuscript based on your suggestions and look forward to your further comments!", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a new dynamic graph learning method, which leverages prompt learning and structural causal models to tackle the challenge of out-of-distribution generalization. Reviewers raised some comments regarding technical details, complexity, assumptions, and paper writing, which have been mostly addressed in the authors' rebuttal. The authors are highly encouraged to improve the final version of their paper according to the suggestions from reviewers.
Decision: Accept (poster)