Improving Generalization of Dynamic Graph Learning via Environment Prompt

Authors: kuo  yang
zhengyang  zhou
qihe  huang
limin  li
yuxuan  liang
yang  wang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 05:06:29

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.

Main paper: 
 introduction: 
 Dynamic graph learning aims to capture the evolution patterns of individual feature and global topology in spatio-temporal graphs over time. It has extensive applications in real-world scenarios, such as social relationship analysis [6, 61] , traffic flow forecasting [3, 59, 64] and air quality prediction [16, 23] . The dynamic evolution is a prominent characteristic of spatio-temporal graphs [4, 16, 47] , such as human interest and social development naturally undergo changes over time. This characteristic inevitably gives rise to a issue of data distribution shifts. Given this issue, enabling models to get temporal out-of-distribution (OOD) generalization ability poses a major challenge in dynamic graph learning [51, 55, 63] .Actually, recent studies have paid attention to tackling the issue of temporal OOD generalization [53, 58, 61] . They demonstrate that unseen temporal environments contribute to such distribution shift. For example, potential urban-hosted events can lead to out-of-distribution traffic state, and unrecorded academic communication between individuals in citation networks may hide new patterns of cooperation. Therefore, the research line relying on environment inference present a promising solution for addressing the temporal OOD issue. This paradigm focuses on inferring underlying environment 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 [53, 58] , there remain limitations in both environment inference and utilization.The judgment of existing limitations stems from two crucial observations. Firstly, unseen environments 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, 58] , which may infer unrealistic environment results. Secondly, the shift of environments in dynamic graphs fundamentally reflects in the changes of structural associations [48, 65] . 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 to augment raw features, overlooking capturing the evolving structural associations [53, 58, 61] . Therefore, the existing dynamic graph OOD efforts face issues in both environment extraction and utilization, and the comprehensive solution to address both problems is currently lacking.To tackle these limitations, we propose an Environment-prompted Dynamic Graph Learning (EpoD) architecture. Firstly, we propose a novel self-prompted learning mechanism to infer underlying environment representation. Given the lacking of environment labels and explicit scaling of environments, our aim is to 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 [14, 31] . We propose a self-prompted learning mechanism for spatio-temporal data to infer environment variables from historical data. By designing 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 [61] , we design a node-centered subgraph extractor specifically tailored for spatio-temporal data. This design is derived from a profound understanding of dynamic graph that the shift of environments within dynamic graphs invariably result 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 to evaluate the generalizability of EpoD. On the one hand, we perform experiments over multiple cross-domain datasets and introduce a more intricate long-series prediction task. On the other hand, we design an environment-shaded 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 subgraphs are equipped with both generalizability and interpretability. Our contributions are summarized as follows:• We systematically investigate the environment-based 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 a novel Environment-prompted Dynamic Graph Learning (EpoD) architecture. Specifically, we introduce a self-prompted learning mechanism for spatio-temporal data to infer underlying environment variables without preset scale. For the exploitation 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.• We conduct experiments over multiple cross-domain datasets, including traffics and social networks, to verify the effectiveness of our framework. And a toy dataset is designed to demonstrate the generalizability and interpretability of EpoD.  
background: 
 Preliminaries. We denote G = {G t } T t=1 as a dynamic graph across T steps, where G t = (V t , X t , A t ) represents a snapshot of the graph at step t. The tensor X t ∈ R N ×D indicates observed features of N = |V t | nodes at step t, where D denotes the feature dimension. A t ∈ {0, 1} N ×N is the adjacency matrix describing the connectivity of graph G t . Given the historical data X = {G t } T t=1 , dynamic graph learning aims to predict the future evolution patterns Y = {G t } T +K t=T +1 , where K denotes the number of predicted future time steps. Historical observations X can be divided into the accessible environment features X X and observed labels with evolution patterns Y X , e.g., volumes in traffic datasets, or links in social networks.Problem Definition. There is a consensus that unseen environment factor, E, considered as the primary reason for temporal OOD issue [58, 53] . In 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 to systematically tackle the challenges in existing environment-centered OOD approaches. Our specific practice in environment 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 to adaptively infer environment variables from historical data by using well-designed prompt tokens. Different from existing efforts relying on predefined environment scale [53, 58] , our methods advantageously eliminates human biases and ensures accurate extraction of the environment from real historical data. On the other hand, we propose a novel SCM with dynamic subgraph as mediating variable. Compared to simply attaching environment embeddings to existing representations, 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 [61] , we propose a 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, 11] . By utilizing well-designed prompts, the model can effectively capture a broader space of data distributions and patterns during training, which is better at adapting to 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 to have superior performance [29, 20] . Therefore, prompt learning is thriving in computer vision research and graph learning [22, 30, 39] . 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 ability. However, there is lacking systematical research on prompt learning addressing temporal OOD problems. 
methodology: 
 In this section, we introduce a novel Environment-prompted Dynamic Graph Learning architecture named EpoD. First, we propose a 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 variables is presented. Last, we provide theoretical analysis of EpoD from causal perspective to interpret its excellent generalization ability.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 semantics and the multimodal generalization of large language models (LLMs) [49, 35, 39] , we propose a self-prompted learning mechanism (SPL) to realize this environment inference principle.Spatial-specified prompt design. Our SPL focuses on guiding models to effectively extract environment 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 different 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 i for each node, which is shared across temporal steps. However, the absence of prior knowledge about environment information hinders us from adopting the template-based approach to initialize p i . Fortunately, learnable prompts have revealed satisfactory performances on capturing hidden mappings [39, 30] . Therefore, we initialize a learnable prompt token p i ∈ R d for each i ∈ V, where d denotes the dimension of latent embedding space. The environment prompt tokens P for G is then denoted as,P = {p i } N i=1 ∈ R N ×d .(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 of R T ×N ×d by cloning T times.Prompt-answer mechanism for environment squeezing. The next challenge to address is how to effectively utilize the well-designed prompts to guide the model in extracting underlying environment representations Z E ∈ R T ×N ×d . 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, X denotes historical observations, which is the combination of X X and Y X defined in Sec. 2. This causal model can be formalized as, P(X, Y|E, C) = P(Y|X, E, C)P(X|E, C).(2) Therefore, we aim to squeeze environment variables E from the observable feature X X and the observed labels with evolution patterns Y X , which is similar to solving cloze problems. To accomplish this, we design an interactive squeezing mechanism g θ (•) to guide the model to squeeze out the underlying environment variables through the interaction of learnable prompts P and the observable features X X . Specifically, we first perform a spatio-temporal network backbone h ϕ (•) to get nodes embeddingZ = {z t 1 , • • • , z t N } T t=1 ∈ R T ×N×d by taking observable features X X as inputs. Then, g θ (•) decodes the learnable prompts P and encoded embedding Z to obtain prompt answers Z E . In implementation, g θ (•) consists of three families of learnable parameters, i.e., W Q , W K , W V ∈ R T ×d×d . Three hidden state matrices are calculated by,EQUATION)The prompt answer Z E is obtained by,EQUATION)where ϵ ∼ N (0, I). Random noise is added to further enhance the robustness of inferred environment representation. Then, the ground-truth Y X serves as the learning goal during this squeezing process. We design a tractable objective to squeeze unseen environment representation Z E , min ϕ,θ,PEQUATIONwhere β ∈ [0, 1] is a preset hyperparameter, and its sensitivity analysis is provided in Appendix G.1.• The first term captures the similarity between environment states Z E and node embedding Z.• The second term predicts the evolution rule Y X only using inferred unseen environments Z E .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 [53, 58] . Our extracted Z E 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 is still indistinctness about the feasibility of our design. From the perspective of information theory [2, 5] , the learning objective of SPL can be restated as, max ϕ,θ,PEQUATIONWe will replace Eq. 5 with above Eq. 6 for later proof. Theorem 3.1. If there exists a causal relationship between unseen environment pattern Z * E and the label Y X , Z * E is the optimal result of SPL objective.Theorem 3.1 demonstrates the feasibility of SPL and we can always extract additional environment factor if it exist. Detailed proof is provided in Appendix C. With the well-learned environment answers, how to exploit such representations to achieve spatio-temporal prediction becomes a natural problem. Existing environment-centered approaches tend to directly treat the perceived environment embedding Z E as the additional feature. However, from the perspective of data generation, the influence of environments on data distribution shifts is usually reflected in the changes of node-wise correlations. Current methods fail to capture the causal effects of environment variables in dynamic graphs. In this subsection, we introduce a spatio-temporal invariant learning approach using node-centered dynamic subgraph as the mediating variable.X C E Y X C E Y X C E Y (a) (b) (c) X SA winding causal path in dynamic graph. We revisit the role of E in the spatio-temporal causal model, and propose a novel SCM with dynamic subgraph X S as mediating variable as shown in Fig. 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 a flow direction between nodes in traffic network and certain node pairs may have different influence or importance to each other in social network. As a 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 a shift in the direction of traffic flow instead of bring any new paths. Different from partition-based subgraph learning strategies investigated in static 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 to clustering effects, such as the asymmetrical importance between the prominent individuals and their followers brings stable connectivity. We leverage the relative entropy (Kullback-Leibler Divergence) to measure such asymmetry. Relative entropy is a metric employed to quantify the disparity between two probability distributions, which exhibits a notable feature of asymmetry, i.e., KL(P||Q) ̸ = KL(Q||P). KL(P||Q) quantifies the degree of match when using P as the reference distribution and approximating it with Q, while KL(Q||P) 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 environment distributions. This is because the asymmetric dependencies of environment distributions also considers the influence of one environment factor on another as the reference basis. However, computing the KL divergence between every pair of nodes KL(Z t E(i,:) ||Z t E(j,:) ) is computationally intensive. To this end, we propose linear complexity quantification method using the mean distribution of node-level environment distributions as a proxy. S t (i,j) represents the dependence from i on j at time t,EQUATIONwhere Zt E = MEAN(Z t E ) denotes the mean distribution of node-level environment embedding. This method utilizes Zt E as an intermediary to measure the environment dependency from node i to j. The larger of S t (i,j) indicates a greater gap of environment difference from node i to j, which reflects the strong dependence. The asymmetric correlation matrix S t ∈ R N ×N at time t can be calculated as,S t = (M t ) T • N t . (9) M t ∈ R 1×N and N t ∈ R 1×Nare respectively calculated from the two terms in Eq. 8,EQUATIONEQUATIONS t (:,i) denotes potential nodes centered on node i and KL(•||•) indicates the Kullback-Leibler divergence. We can extract node-centered L-hop subgraph A t ∈ R N ×N based on this environmentenhanced correlation matrix S t ,EQUATIONwhere ⊙ denotes element-wise multiplication of matrices and L is a hyperparameter. L is set to 5 and its sensitivity is discussed in Appendix G.1. I(•) is an indicator function that assigns a value of 1 to elements in the matrix that are greater than 0, and assigns a value of 0 to the rest. We can get a series of dynamic subgraphs that evolves over time A ∈ R T ×N ×N . Meanwhile, we combine the features of each node by concatenating environment answerEQUATIONThe historical data enhanced by dynamic subgraph with environment representation is denoted as,EQUATION)Dynamic graph prediction with generalizability. Finally, f ψ encodes the dynamic subgraphs X S via a spatio-temporal network backbone to predict future dynamic evolution. We obtain the learning objective of EpoD,EQUATIONWe provide the training process of EpoD in Alg. 1. It is worth noting that our EpoD systematically resolves 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 coupled. Moreover, our EpoD is pluggable that can be flexibly integrated with various backbones. In the experiments of traffic flow and social relationship prediction, we select Adaptive Graph Convolutional Recurrent Network (AGCRN) [3] and Disentangled Dynamic Graph Attention Networks (DDGAN) [61] as 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 information to 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 discussion can further validate such intuition.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 acknowledged 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 pioneering 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 in Fig. 2(b) . But according to the complete mediation effect theorem, this SCM eliminates the direct effect of temporal variable E on future spatio-temporal evolution Y. This requires us to contemplate whether C can serve as a mediation variable. Given the time-varying property of dynamic graph, the only spatial context cannot sufficiently interpret the graphs evolution. Therefore, a mediating variable simultaneously encapsulating spatial dependencies and temporal dynamics is required.Dynamic subgraphs as mediation variable. The dynamic spatial variations induced by environment factors are essentially rooted in the changes of local dependencies. Thus, a novel SCM is introduced, which employ dynamic subgraph X S as the mediation variable as illustrated in Fig. 2(c ). Dynamic subgraphs exhibit both temporal and spatial characteristics, also serve as the mediation variable from X to Y. This design offers us a chance to address distribution shift issue along the practices of causal adjustment [28] . We can observe a back-door path between causal path X and Y, i.e., X ← C → X S → Y. The backdoor adjustment pattern leveraging do-calculus on dynamic subgraph X S is,EQUATION)In essence, our EpoD can be viewed as employing backdoor adjustments to estimate P (Y|do(X)) by discovering dynamic subgraphs, where the prompted environment representations support the subgraph discovery process. More discussion is provided in Appendix D.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes]Answer: [Yes] Justification: We release the code using anonymous links.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experiment setup: 
 We introduce datasets, baselines and experiment settings, and details are leaved in Appendix E.Datasets. We employ seven cross-domain real-world dynamic graph datasets to evaluate our EpoD. PEMS08 and PEMS04 [34] are classic medium-scale traffic network datasets from California with 5-minute intervals; SD and GBA [24] are newly proposed large-scale traffic network datasets. COL-LAB [40] is an academic collaboration dataset comprising papers published in 16 years; Yelp [33] is a business review dataset; ACT [18] shows students' actions on a MOOC platform over 30 days.Baselines. We compare EpoD with two families of baselines, i.e., six traffic flow prediction models and six social link forecasting methods. Traffic flow prediction models: GWNET [52] , AGCRN [3] , Z-GCNETs [8] , DSTAGNN [19] , STGNCDE [9] , CaST [53] . Social link forecasting models: DySAT [33] , IRM [1] , VREx [17] , GroupDRO [32] , 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 to 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 a 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 a shifted attribute link from COLLAB, Yelp and ACT to simulate the distribution shift scenario encountered in the real world [61] . Traffic flow prediction. We evaluate our EpoD with baselines based on Mean Absolute Error (MAE) and Root Mean Square Error (RMSE), where lower values of them represent better performance. Tab. 1 shows the results of EpoD on traffic flow data. We have two observations: 1) our EpoD outperforms all baselines on three datasets. The powerful long-sequence prediction ability of EpoD demonstrates that our design is robust to environment perturbations and excels in capturing the evolution patterns of dynamic graph. We also note that CaST [53] obtains suboptimal results on most datasets and even optimal results on PEMS04. This indicates that it is effective to tackle the temporal distribution shift issue by studying environment factors under the guidance of causal theory. 2) EpoD exhibits 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 G.3. 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.We manually design a toy dataset EnvST with temporal distribution shift to explore the generalizability of EpoD. The feature of each node in EnvST encompasses three components, i.e., [x A , x B , x C ], where x A and x B represent evolution-causal features but x B is masked after the data is generated, x C indicates available evolution-spurious feature. To simulate the temporal distribution shift in the dynamic graph, the training and test dataset of x A , x B and x C are sampled from distributions with significant differences separately. The label of each node on the EnvST at t step is activated by updated feature y t i ∼ Bern(σ(z t i )), where σ(•) is the sigmoid func-tion. We conduct experiments from the following two aspects: 1) we investigate whether EpoD has the capability to perceive masked environment feature x B , 2) we study whether EpoD can identify and remove the spurious correlation x C . More analysis can be found in Appendix E.4. As shown in Fig. 3 (b), we 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 x C . Specifically, we have the following experiment design. Consider x C is sampled from N (µ, I), we set µ ∈ [0, 10] and record the performance of EpoD under the influence of different spurious information as shown in Fig. 7 . 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 x C . We conduct ablation studies from the following two aspects.Temporal shared learnable prompts. In spatio-temporal graphs, we can observe different nodes always reveal heterogeneous evolution patterns. Thus, we design temporal shared node-wise learnable prompts. In essence, this design is driven by both resource consumption and real-world scenarios. There 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 ∈ R d ; the latter assigns learnable prompts to each node of each snapshot P ∈ R T ×N ×d . To this end, we compare three design methods in terms of accuracy and efficiency. Fig. 4 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. O(T • d • |E| + T • (1 + d + d 2 ) • |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-40GB. Empirically, we observe that the operational efficiency of our method is competitive with existing approaches. 
conclusion and future work: 
 In this paper, we propose a novel dynamic graph learning framework EpoD to tackle the temporal distribution shift issue by exploiting prompt learning. Inspired by the powerful ability of prompt learning in perceiving underlying semantic and causal associations, we first introduce a self-prompted environment inference mechanism. This approach aims to extract underlying environment variables 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 interpretability via dynamic subgraphs.Limitations. One of the limitation of our work is its strong dependence on graph topology. Specifically, our subgraph discovery strategy essentially is the node filtering based on K-hop neighbors, which can be regarded as subtracting elements from the graph topology. However, the graph topology 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 to form subgraphs from an empty topology by taking into account both the perceived environment embeddings and the initial distance information. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to 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 to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: The quantified results we provide are 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, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 error rates). • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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 impacts of our work. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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 specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is 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 mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to 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 not require this, but we encourage authors to take this into account and make a 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 are related to our research, and carefully 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 Appendix: Dynamic graph learning models are widely used to support social development, such as recommendation systems and smart cities. However, with the increasing complexity of data scale and application 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 of graph learning in various fields. Therefore, our work aims to develop a model with the out-of-distribution generalization 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 available. Our work does not involve human subjects and does not introduce any potential negative social impacts or issues related to privacy and fairness.Table 5 : Classification accuracies for naive Bayes and flexible Bayes on various data sets. G = {G t } T t=1 A DYNAMIC GRAPH ACROSS T STEPS G t = (V t , X t , A t ) A t-STEP GRAPH WITH THE NODES V t , FEATURES X t AND EDGES A t X t ∈ R N ×D THE FEATURE MATRIX X t OF t-STEP GRAPH SNAPSHOT P ∈ R T ×N ×d LEARNABLE PROMPTS MATRIX OF R T ×N ×d X = (X X , Y X ) HISTORICAL OBSERVATIONS IN PREDICTION TASKS X S = {V t , X t ,EQUATIONwhere 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 I(X; Z|Y ) represents the conditional mutual information between X and Z 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 is transmitted and shared within complex systems.Theorem 3.1. If there exists a causal relationship between unseen environment pattern Z * E and the label X X , Z * E is the optimal solution of SPL objective. Proof. Consider The Chain Rule for Mutual Information, we derive the following equation:EQUATIONEQUATIONWe then getI(Z E ; Y X )-βI(Z E ; X X ) = I(Y X ; X X , Z E )-(1-β)I(X X ; Y X |Z E )-βI(X X ; Z E , Y X ).Thus, optimizing Eq. 6 is to maximize I(Y X ; X X , Z E ) and minimize (1 -β)I(X X ; Y X |Z E ) + βI(X X ; Z E , Y X ). Next, we investigate whether Z * E is the result of optimization. (i) Maximizing I(Y X ; X X , Z E ) reflects the combination of X X and Z E can make optimal prediction. Since X X is constant, Z E = Z * E ensures that the features used for prediction have the greatest overlap with the ground-truth.(ii) Since I(X X ; Y X |Z E ) ≥ 0 and I(X X ; Z E , Y X ) ≥ 0. If β ∈ [0, 1], the lower bound of (1 - β)I(X X ; Y X |Z E ) + βI(X X ; Z E , Y X ) is 0. Next, we prove our SPL can achieve I(X X ; Y X |Z * E ) = 0 and I(X X ; Z * E , Y X )) = 0 in detail. I(X X ; Y X |Z * E )represents the conditional mutual information between X X and Y X given Z * E . Because we manually add random noise ϵ at Eq. 4, our model can be viewed as a mapY X = f (Z * E ) + ϵ. Obviously, ϵ is independent of Y X . We can get I(X X ; Y X |Z * E ) = 0. I(X X ; Z * E , Y X)) = 0 is also proven the independence between X X and Z * E . We have proved it. With the causal theory [28] , we can build a coherent progression for the proposal of EpoD.X C E Y X C E Y X C E Y (a) (b) (c) X SThe Structural Causal Model in the dynamic graph. The Structural Causal Model (SCM) in the dynamic graph fosters a deeper understanding of the generation process of 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. 5 (a).• E → X ← C. The historical observation X consists of two parts: temporal environment variable E and spatial context C. In many works, these two aspects are often treated as disjoint factors and discussed decouplingly, i.e, E ⊥ C.• E → Y ← C. Temporal environment variable E and spatial context C also determine the future evolution trend Y. Most studies keep this assumption that historical observations X 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 a crucial foundation for exploring the invariant evolution model of dynamic graphs.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 acknowledged 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 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. 5(b) .• E → C → X. The historical observation X is seen as the evolution process of spatial context C, where C covers the temporal environment information E.• X ← C → Y. Spatial context C directly determine current observations X and future evolution trend Y.But according to the complete mediation effect theorem, this SCM eliminates the direct effect of temporal variable E on future spatio-temporal evolution Y. This necessitates us to contemplate whether C has the capacity to serve as a mediation variable. Given the time-varying property in dynamic graph, the only spatial context cannot sufficiently interpret the temporal evolution of graphs. Therefore, a mediating variable simultaneously encapsulating spatial dependencies and temporal dynamics is required.Dynamic subgraphs as mediating variables. The dynamic spatial variations induced by environment factors are essentially rooted in the changes of local dependencies. Thus, a novel SCM is introduced, which employ dynamic subgraph X S as the mediation variable as illustrated in Fig. 5(c ).• X ← C → X S → Y. Dynamic subgraph X S is more abundant than the spatial context C. In other words, dynamic subgraph X S 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 to Y. This design offers us a chance to address distribution shift issue along the practices of causal adjustment [28] . We can observe a back-door path between causal path X and Y, i.e., X ← C → X S → Y. The backdoor adjustment pattern leveraging do-calculus on dynamic subgraph X S is,EQUATIONIn essence, our EpoD can be viewed as employing backdoor adjustments to estimate P (Y|do(X)) by discovering dynamic subgraphs, where the prompted environment supports the subgraph discovery process.Our experimental design included the selection of seven real-world dynamic graph datasets from two distinct domains. The detailed statistics of the datasets are as shown in Tab. 6. We select a 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 outof-distribution (OOD) testing stage. This scenario is more practical and challenging in real-world situations, as the model cannot capture any information about the filtered links during training and validation.PEMS08 [34] COLLAB [40] is an academic collaboration dataset comprising papers published between 1990 and 2006, spanning 16 graph snapshots. In this dataset, nodes represent authors, and edges represent coauthorship relationships. The edges include five attributes based on co-authored publications: "Data Mining", "Database", "Medical Informatics", "Theory" and "Visualization".Yelp [33] is a 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 [18] characterizes student interactions on a MOOC platform over a span of one month, consisting of 30 graph snapshots. In this dataset, nodes represent students or the targets of actions, while edges signify various student actions. Initial: dynamic graph encoders h ϕ and f ψ , cross-attention mechanism decoder g θ , learnable prompt P, the number of epochs K for i = 1 to K do Environment prompt stage:Z E = g θ (P, Z) + ϵ, Z = h ϕ (X X ) (ϵ ∼ N (0, I)) ŶX = Linear(Z E )Environment utilization stage: S t = (M t ) T • N t as shown in Eq. 9A t = S t ⊙ (A t ) K , X = CONCAT([X , Z E ]) X S = { G t } T t=1 = {V t , X t , A t } T t=1 Y = f ψ (X S ) Optimizing: min ϕ,θ,P,ψ L = -E[log P ψ (Y|X S ) + log P ϕ,θ (Y X |X X , P)] + βE[KL(P θ (Z E )||P ϕ (Z|X X ))]end for Return h ϕ , f ψ , g θ and PWe implement our EpoD with PyTorch 1.11.0 on a server with NVIDIA A100-PCIE-40GB. The detailed training process is shown in Alg. 1. All experiments are repeated with 10 different random seeds of [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] . The reported results include the mean and standard deviation obtained from these 10 runs.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) [3] .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 [61] , 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 in 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) [61] is chosen as our spatio-temporal graph neural network backbone.We utilize Mean Absolute Error (MAE) and Root Mean Squared Error (RMSE) to assess the performance of our EpoD and baselines. Both metrics quantify the error between model predictions and actual observations in regression tasks. A smaller value for these metrics indicates better model performance. MAE is less sensitive to outliers due to 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 i and the corresponding predicted value Ŷi for n samples, two metrics are calculated as follows:EQUATIONEQUATION)We manually design a toy dataset EnvST with temporal distribution shift to explore the generalizability of EpoD. Tab. 7 describes the statistical information of EnvST. Specifically, EnvST illustrates the evolution sequence of a graph with 100 nodes across 1000 steps, where the topology of each snapshot does not change over time. The feature of each node in EnvST encompasses three components, i.e., [x A , x B , x C ], where x A and x B represent evolution-causal features but x B is masked after the data is generated, x C indicates available evolution-spurious feature. To simulate the temporal distribution shift in the dynamic graph, the training and test dataset of x A , x B and x C are sampled from distributions with significant differences separately. The label of each node on the EnvST at t step is activated by updated feature y t i ∼ Bern(σ(z t i )), where σ(•) is the sigmoid function.Available evolution-causal feature Unseen evolution-causal feature Available evolution-spurious feature As shown in Fig. 6 , the feature of each node in EnvST encompasses three components, i.e., [x A , x B , x C ]. x A and x B represent evolution-causal features but x B is masked after the data is generated,x C indicates available evolution-spurious feature. To simulate the temporal distribution shift in the dynamic graph, the training and test dataset of x A , x B and x C are sampled from distributions with significant differences separately. The label of each node on the EnvST at t step is activated by updated feature y t i ∼ Bern(σ(z t i )), where σ(•) is the sigmoid function. The feature is updated by aggregating the neighbor information of the last k time steps, We conduct experiments from the following two aspects: 1) we investigate whether EpoD has the capability to perceive masked environment feature x B , 2) we study whether EpoD can identify and remove the spurious correlation x C .EQUATIONPowerful perception for unseen environment. Fig. 3 (a) and 3(b) show the distribution difference between masked feature x B and prompted environment feature Z E , where experiments are conducted on EnvST under the scenario of distribution shift. There is no doubt that Z E can match the masked x B 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 historical sequences. Fig. 3 (a) shows our prompted environment feature Z E 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 a 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. 3 (b), we 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 x C . Specifically, we have the following experiment design. Consider x C is sampled from N (µ, I), we set µ ∈ [0, 10] and record the performance of EpoD under the influence of different spurious information as shown in Fig. 7 . 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 x C .Dynamic Graph Learning. Graph Neural Networks (GNNs) [10, 37, 54, 44, 36] 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 recent years [50, 46, 45, 41, 43, 42] . Based on varying interpretations of the correlation between temporal and spatial information, the current works are undertaken along two research lines. One claim is to study temporal and spatial information in a decoupled manner, which is potentially present in most current works [3, 19, 61] . Due to the intricate temporal and spatial relationships in reality, they often fail to offer sufficient interpretability and generalizability. The other one argues that spatial context is influenced by the temporal information [65, 53] . 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 environment. 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 remarkable success in static graph applications, such as molecular property prediction and social network analysis [25, 57, 38, 21] . In essence, it captures the inductive bias inherent in graph data that local dependencies are invariant patterns predicting ground-truth. We argue that dynamic subgraphs may exhibit a similar inductive bias spatio-temporal evolution. But dynamic subgraphs remain an unexplored area with no existing studies. To this end, this paper introduces a dynamic subgraph learning mechanism to address the issue of temporal distribution shift resulting from the changes of environment factors.We analyze the sensitivity of the hyperparameter β in Eq. 5, which functions as the trade-off for the loss in Eq. We then analyze the sensitivity of hyperparameter L in Eq. 12. As shown in Tab. 8, we study the performance of EpoD when L is set to [1, 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 = 5 as a trade-off between performance and time consumption. Our EpoD essentially provides a solution for temporal distribution shits issue in dynamic graphs.The most prominent characteristic of EpoD is the pluggability, which denotes that we can be applied to numerous existing backbones. In the task of traffic flow prediction, we explore the performance associated with the selection of different models as backbones as shown in Tab. 9. We get the following two observations. Obs 1. 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- Obs 2. The expressive capacity of the backbone directly influences the predictive ability of the model enhanced by EpoD. Since the performance of AGCRN is already excellent, the enhancements introduced by EpoD often result in optimal results. This underscores the importance of selecting a proficient backbone model for forecasting.In this subsection, we explore the interpretability of dynamic subgraphs under real-world scenarios.In recent years, the most notable temporal-distribution shift phenomenon is the outbreak of COVID-19. The introduction of LargeST [24] provides a chance for us to study this distribution shift of traffic flow under COVID-19. We choose a local sensors network in GBA dataset and reconstruct its evolution data at monthly intervals from 2019 (t = 1, ..., T ) to 2020 (t = T + 1, ..., T + k).Then, we apply our EpoD trained on 2019 data to partition each snapshot into a bag of subgraphs, as shown in the top panel of Fig. 9 . 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. 9 visualizes the ground-truth of this sequence, which aligns with the information reflected in our dynamic subgraphs. This suggests that our EpoD exhibit sensitivity to environment changes. NeurIPS Paper Checklist Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on 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, e.g., if the approach was only tested on a few datasets or with a 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 approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it 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 address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: To be honest, I did not find obvious drawbacks of this work. Some minor revision might be helpful: 

- 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. 
- 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.


Overall, this paper presents a significant contribution to the field of dynamic graph learning, with innovative methods and strong experimental results.
questions: questions: N/A
limitations: limitations: See in the weakness
paper_summary: paper_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.
strength_weakness: strength_weakness: 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?

2 Would like to see a discussion of computational complexity, both time complexity and space complexity.

3 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.
questions: questions: As above.
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: **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? 

**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?

**W3.** Any other considerations besides efficiency when designing node-specific and time-shared prompt tokens? 

**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?

**W5.** Some typos: 

- In line 254, "dynamics graph" should be modified to "dynamic graph".

- In line 385, "we" should be modified to "our".
questions: questions: Please answer the questions in Weaknesses.
limitations: limitations: The authors have discussed the broader social impacts and limitations of their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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?

- There are some  minor typos, e.g.,  in Line105,  more consistent with -> is more consistent with.
questions: 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?

- 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? 

- 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: 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.

Comments: title: Further feedback for Zz1E
Further feedback for 5ZgN
comment: Dear Reviewer Zz1E,

Thanks again for your professional insight, which will significantly enhance our work.  If you have any questions, please don't hesitate to let me know. We will answer your concerns carefully. We truly appreciate your support and wish you a wonderful day!

Authors of Paper 4911.
I have carefully read your response. Thanks
Dear Reviewer 5ZgN,

We would like to express our deep gratitude for your professional comments, which will greatly enhance our work. We are committed to refining our manuscript by offering more intuitive explanations, and conducting a thorough discussion of related techniques. 

Thank you once again, and we hope you have a wonderful day!

Authors of Paper 4911.
The authors have addressed most of my concerns. I suggest acceptance after careful refinement of the manuscript.