Improving Generalization of Dynamic Graph Learning via Environment Prompt

Dear Reviewer YNjr,

We would greatly appreciate your positive comments on our work. We have carefully considered your questions and have provided detailed answers as follows.

W1. The design of our self-prompted mechanism.

There 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({**Z**_ E})||\mathbb{P}_ \phi(**Z**))$ in the learning objective of Eq. 5 constrains our environment prompts to be dissimilar with the representations of the original data.

\mathop  {\min }\limits_ { \phi ,\theta, **P**}{{\cal L}_ P} =  \beta \mathbb{E}[ {\rm{KL}}(\mathbb{P}_ \theta({**Z**_ E})||\mathbb{P}_ \phi(**Z**))]- \mathbb{E}[ \log  {\mathbb{P}_ {\phi ,\theta}}({{**Y**_ **X**}}|{{**Z**_ E}})]

W2. Minor typo.

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

Q1. Interpretation of historical observations division.

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

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

Q2. Explanation of the winding causal path.

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

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

Q3. Asymmetric quantization principle.

Here we offer a more intuitive explanation to clarify the concept  of asymmetry.

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

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

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

We 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!

Dear Reviewer 5ZgN,

Thank you for taking the time to review our work. We greatly appreciate your positive feedback and will address your comments with careful consideration.

W1. Advantages of self-prompted learning mechanism.

Our self-prompted mechanism has two key advantages that distinguishes from existing works:

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

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

Actually, the above analysis has already been discussed in Sec. 3.1.

W2. Explanations of environment inference process.

Our 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 $**E**$, observable features $**X**_ **X**$, and evolutionary patterns $**Y**_ **X**$. Although inspired by LLMs, this insight makes our self-prompted module distinct from LLMs in both its objectives and implementation manners.

Specifically, given the availability of $**X**_ **X**$,  $**Y**_ **X**$ and $**C**$, we adopt the strategy that infers the environment in historical observations, i.e., $**E** \leftarrow {g_ \theta }(**X**_ **X**, **Y**_ **X**,**C**)$.

$\mathbb{P}(**X**, **Y**|**E**,**C**) = \mathbb{P}(**Y**|**X**,**E**,**C**)\mathbb{P}(**X**|**E**,**C**)$

W3. Design principles of learnable prompt tokens.

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

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

W4. The advantages of node-centered dynamic subgraphs.

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

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

W5. Some typos.

Thank you very much for your careful review, we will carefully check our manuscript to correct all typos.

We 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!

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.

Dear Reviewer XPEX,

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

W1. The ability to counter structural distribution shifts of EpoD.

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

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

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

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

W2-1. Time complexity analysis.

We analyze the efficiency of EpoD theoretically and practically.

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

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

W2-2. Parameter scale analysis.

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

W3. The details of the datasets.

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

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

Thank 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!

Dear Reviewer Zz1E,

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

W1. More extensive prompts design.

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

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

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

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

W2. Sociological analysis.

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

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

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

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

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

References:

[1] All in one: Multi-task prompting for graph neural networks.

[2] Self-supervised Hypergraph Representation Learning for Sociological Analysis.

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.