Dynamic graph neural networks (DGNNs) are increasingly pervasive in exploiting spatio-temporal patterns on dynamic graphs. However, existing works fail to generalize under distribution shifts, which are common in real-world scenarios. As the generation of dynamic graphs is heavily influenced by latent environments, investigating their impacts on the out-of-distribution (OOD) generalization is critical. However, it remains unexplored with the following two major challenges: (1) How to properly model and infer the complex environments on dynamic graphs with distribution shifts? (2) How to discover invariant patterns given inferred spatio-temporal environments? To solve these challenges, we propose a novel Environment-Aware dynamic Graph LEarning (EAGLE) framework for OOD generalization by modeling complex coupled environments and exploiting spatio-temporal invariant patterns. Specifically, we first design the environment-aware EA-DGNN to model environments by multi-channel environments disentangling. Then, we propose an environment instantiation mechanism for environment diversification with inferred distributions. Finally, we discriminate spatio-temporal invariant patterns for out-of-distribution prediction by the invariant pattern recognition mechanism and perform fine-grained causal interventions node-wisely with a mixture of instantiated environment samples. Experiments on real-world and synthetic dynamic graph datasets demonstrate the superiority of our method against state-of-the-art baselines under distribution shifts. To the best of our knowledge, we are the first to study OOD generalization on dynamic graphs from the environment learning perspective.
Paper
Similar papers
Peer review
Summary
This paper proposes EAGLE to improve OOD generalization in DGNNs. It focuses on modeling and inferring complex environments on dynamic graphs with distribution shifts and identifying invariant patterns within inferred spatio-temporal environments. The EAGLE incorporates an environment-aware model, an environment instantiation mechanism for diversification, and an invariant pattern recognition mechanism for OOD prediction. The authors claim that EAGLE outperforms current methods on various dynamic graph datasets, marking the first approach to OOD generalization on dynamic graphs from an environment learning perspective.
Strengths
1. The problem to be solved in this article is significant. 2. The authors conducted sufficient experiments to verify their claim.
Weaknesses
1. The paper lacks a clear definition of 'environment', particularly in the context of multiple graphs. As the environment seems to correlate with time (T), the authors should elucidate whether the environment changes with T. Given the evident correlation between time and environmental changes - as seen in the authors' own example of transitioning from school to a company (past classmates --> current colleagues) - this should be addressed in the discussion. 2. It is not apparent whether the different environment K is determined by the dataset or is a hyperparameter. The paper should elucidate the relationship between the environment number K and the graph data T. 3. Assumption 1, which emulates a significant amount of existing work [1-4], seems to have a miswritten part (b) where the noise term should be placed outside the brackets. 4. The article uses notations that are confusing, making it difficult to read. For instance, it is unclear why the same symbol, z, is used to represent the result set obtained by the set operation in line 134. The meanings of symbols e and s should be clarified. 5. The author should provide more explanation about Proposition 1 and Proposition 2, rather than simply stating the theories and placing the proofs in the appendix. A brief explanation of what these theorems illustrate would be beneficial. 6. Several remarks and statements in the article are wrong. For example: - The absolute statement, "Existing works fail to generalize under distribution shifts ..." overlooks recent works [4] addressing distribution shifts. - The sentence on lines 140-141, "We regard the learned node embeddings as environment samples drawn from the ground-truth distribution of latent environment", is ambiguous and warrants clarification. How can we learn "ground-truth" distribution? In summary, the main issue with this paper is its lack of clarity, manifested in confusing mathematical symbols, unclear theorem and formula meanings, and an ill-defined problem statement. [1] Handling Distribution Shifts on Graphs: An Invariance Perspective, ICLR 2022 [2] Learning Invariant Graph Representations for Out-of-Distribution Generalization, NeurIPS 2022 [3] Learning Substructure Invariance for Out-of-Distribution Molecular Representations, NeurIPS 2022 [4] Dynamic Graph Neural Networks Under Spatio-Temporal Distribution Shift, NeurIPS 2022
Questions
plz refer to Weaknesses.
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
1 poor
Contribution
2 fair
Limitations
plz refer to Weaknesses.
Summary
This paper proposes a novel framework called EAGLE to address the challenge of out-of-distribution generalization in dynamic graphs. The authors investigate the impact of latent environments on dynamic graphs and develop methods to model and infer these environments. They propose techniques to recognize spatio-temporal invariant patterns and perform fine-grained causal interventions. The rationality and correctness of EAGLE are guaranteed by rigorous reasoning and mathematical proof. Experimental results demonstrate the superiority of their method in handling distribution shifts in dynamic graph datasets.
Strengths
(1) First attempt to explicitly model the environment on dynamic graphs. Through the innovative Environment “Modeling-Inferring-Discriminating-Generalizing” paradigm, the influence of open environment on OOD generalization on dynamic graphs is explored, and the generalization ability of the model in this scenario is improved. (2) Well-organized derivation and mathematical proofs. Based on causality theories, the proposed method is proven to satisfy the invariance assumptions and propositions, directing the optimization that achieves OOD generalization for in-the-wild extrapolations by fine-grained causal interventions. (3) Reasonable experiment settings and sufficient results. Appropriate baseline methods are compared under multiple OOD environment settings. The results of the main experiment and several auxiliary experiments demonstrate the effectiveness and superiority of the proposed method. (4) This method can be easily extended to other sequential models to perform temporal convolutions, or compounded with any attention/reweighting mechanisms in environment modeling. This paper is well-organized and easy to follow. The background problems and method design are clearly explained.
Weaknesses
(1) Variable symbols are kind of complicated, and their expressions are not very clear, which brings difficulties in understanding theoretical proofs. (2) Computational complexity and sufficient analysis are not discussed in the main contents. (3) The distribution shifts in the experiment datasets are manually designed. I wonder if there exist naturally formed dynamic graph OOD datasets that measure on their OOD degree, and conduct experiments based on those datasets.
Questions
(1) Are there other OOD types besides the links and node features? How to demonstrate that the proposed model improves generalization performance on the other OOD types? (2) It is better to explain the details of the baselines and datasets, like the differences with the proposed model, the statistical information of the datasets, etc. in the main contents.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Y
Summary
In this paper, the authors propose a novel framework EAGLE, Environment-Aware dynamic Graph LEarning, which tackles the OOD generalization problem by modeling complex dynamic environments and exploiting spatial-temporal invariant patterns. Following the Environment “Modeling-Inferring-Discriminating-Generalizing” paradigm, EAGLE consists of three modules. Firstly, an Environment-Aware Deep Graph Neural Network (EA-DGNN) is designed to model environments by learning disentangled representations under multi-channel environments. EAGLE then diversifies the observed environments' samples with the environment instantiation mechanism, which infers environment distributions by applying the multi-label variational inference. Finally, EAGLE discriminates spatio-temporal invariant patterns for out-of-distribution prediction by the invariant pattern recognition mechanism and performs fine-grained causal interventions node-wisely with a mixture of observed and generated environment samples. Extensive experiments on real-world datasets demonstrate that EAGLE outperforms baseline methods on dynamic graph OOD tasks.
Strengths
1. The OOD generalization problem on dynamic graphs is important, especially when considering changes in latent environments. EAGLE is the first model to tackle this problem by modeling the impact of environments on dynamic graphs under distribution shifts. 2. The proposed Environment “Modeling-Inferring-Discriminating-Generalizing” paradigm is technically sound and easy to understand, and using the proposed Environment Instantiation Mechanism to generate instances for inferring environment is novel. 3. The experiments are extensive (real-world datasets under distribution shifts on link attributes and node features, ablation studies on proposed mechanisms), and the results are considerably better than existing methods.
Weaknesses
1. The requirement of the environment information is not specified. Especially, whether EAGLE requires the environment label to be known or not. The reviewer thinks one of the main contributions of EAGLE should be inferring environments from samples, but there are not any detailed explanations, and it seems that the number of environments is pre-determined in the experimental setting. The reviewer wonders if the authors could discuss the requirement of environment labels in detail and how to select the proper number of environments if the environment label is unknown. 2. Proposition 2 is difficult to understand and lacks details about how to obtain the optimal $\mathbb{I}^*(\cdot)$. It would be great if the authors could provide further explanation and a concrete example to help readers better understand the proposition. 3. The related work part should also add literature related to disentangled representation learning and further discuss the difference between EAGLE and DIDA [61] in detail. Minor issues: typo: line 145, multi-lables -> multi-labels
Questions
1. Please see the first two questions in Weaknesses. 2. Compared to DIDA, what is the advantage of EAGLE for modeling the complex dynamic environment? It would be great if the authors could provide some examples for explanation. 3. When the training data is homogeneous (i.e., only contains few environments), how does EAGLE generalize to unseen test environments with OOD shifts? 4. How to select an appropriate number of generated instances for Invariant Pattern Recognition to exploit spatio-temporal invariant patterns? 5. The authors discussed EAGLE's computational complexity in the appendix. What is EAGLE's space complexity?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
The authors did not address the limitations of their work. The reviewer thinks that the authors should make the description of the problem setting, the definitions of spatio-temporal invariant patterns, and variant patterns more clear.
Summary
This paper proposes a novel framework called EAGLE for out-of-distribution generalization on dynamic graphs. EAGLE models the complex environments that influence the generation of dynamic graphs and exploits the spatio-temporal invariant patterns that can generalize under distribution shifts. EAGLE consists of four mechanisms: environment-aware dynamic graph neural network, environment instantiation, invariant pattern recognition, and causal intervention. EAGLE achieves superior performance on future link prediction tasks on both real-world and synthetic datasets compared to existing methods. The paper also provides theoretical analysis and empirical studies to support the effectiveness of EAGLE.
Strengths
1. The illustration in Figure 2 is clear and aids in understanding the proposed method. 2. Theoretical analysis and proofs are provided as necessary. 3. Overall, the proposed solution for OOD Dynamic link prediction seems reasonable. The idea of generating spatio-temporal environments is novel.
Weaknesses
1. The generated environment patterns lack explainability. These patterns are produced through disentangling, making it difficult to explicitly understand their specific meaning in reality. 2. The author should include further discussion on how the proposed method can contribute to link prediction in a new environment, as exemplified in Figure 1. If the model successfully distinguishes environment-invariant patterns in previous graphs, how will it capture new patterns in a different environment to improve prediction? 3. The writing style is not reader-friendly for those unfamiliar with the task and techniques. It would be beneficial to provide more intuitive explanations to enhance understanding.
Questions
1. What does the one-hot multi-label y introduced in line 142 represent? Does it means what index of the environment which the observed z belongs to, or does it also include the index of the time step? 2. Could the author provide a more detailed explanation of the visualization experiment mentioned in Section 4.4?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
3 good
Contribution
3 good
Limitations
N/A
Thank you author for the rebuttal. I found some concerns after reading this article and DIDA [1] carefully. 1. There are a lot of over-declarations in the article, such as "this is the first trial to explore the impact of environments on dynamic graphs under OOD shifts. However, the OOD problem on dynamic graphs has been studied and defined by other works, such as DIDA. And DIDA has also explored the environment or variant patterns. Therefore, the contribution of the article is insufficient. 2. In addition, a lot of content is imitated from the work of DIDA, such as the problem description in Section 2, and Assumption 1. So I think this part of the contribution is also insufficient. 3. I am also very surprised why there is no detailed comparison with DIDA in this article. For example, what are the problems in the work of DIDA, and what are the advantages of this work compared with DIDA? In summary I do not decide to revise my score. [1] Dynamic Graph Neural Networks Under Spatio-Temporal Distribution Shift, NeurIPS 2022
We thank the reviewer for the discussion. After carefully reading the reviewer's comments, we think there exist some misunderstandings and would like to clarify the concerns point by point. **Q1.1:** There are a lot of over-declarations in the article, such as “this is the first trial to explore the impact of environments on dynamic graphs under OOD shifts”. However, the OOD problem on dynamic graphs has been studied and defined by other works, such as DIDA. **A1.1:** Thank you for your concerns and comment. - We would like to claim that, we **do** propose to **explore the impact of environments** on dynamic graphs under OOD shifts **for the first time**, by applying the novel Environment “Modeling-Inferring-Discriminating-Generalizing” paradigm of our EAGLE. - Our above contribution **does not imply** we are the first to study the problem of OOD on dynamic graphs, as **we reiterated that DIDA [1] is the sole prior work that tackles distribution shifts on dynamic graph** (e.g., lines 304-305), but **we are the first to utilize “environment” to solve the problem**. Specifically, we tackle this problem from a **novel** perspective (the latent environments) and gain **better** performance due to our **advantages** compared to DIDA [1] (please see A3 for details). In summary, these declarations emphasize the contribution of investigation into “environments” (first time), rather than works on the dynamic OOD problem. --- **Q1.2:** And DIDA has also explored the environment or variant patterns. Therefore, the contribution of the article is insufficient. **A1.2:** Thank you for your comment. - In terms of “environment”, we have rechecked DIDA [1] carefully and found there are **no investigations on “environment” or other similar terms**. - **The variant patterns exploited by DIDA [1] are different from the “environments” in our work**. Specifically, DIDA [1] defines variant/invariant patterns as subsets of ego-graphs across time stamps whose predictively to labels are (not) stable across time periods and graph communities **(all in only one embedding space)**, while our explanations for “environments” are $K$ **latent embedding spaces**, which are formed under the impacts of complex spatio-temporal node interactions, causing the relationships to be multi-attribute.
(continue) **Q2:** In addition, a lot of content is imitated from the work of DIDA, such as the problem description in Section 2, and Assumption 1. So I think this part of the contribution is also insufficient. **A2:** Thank you for your comment. - **[Section 2]** First, we would like to clarify that **we never mentioned the “problem” defined in Section 2 is new or it should be considered as our contribution**. We have cited DIDA [1] accurately and comprehensively in the main paper and Appendix. However, **we tackle the problem, i.e., OOD generalization on dynamic graphs, from a totally different perspective with a novel method**, enjoying superior advantages and achieving better results. - **[Assumption 1]** We have replied to this concern in the rebuttal (please see Q3.1 and A3.1 for details). We would like to explain it again. Assumption 1 is **a universally acknowledged and widely accepted assumption** in almost all works based on the Independent Causal Mechanism (ICM) and the Invariant Learning theory, not only in graph OOD related works [1-4], but also in works of other fields [5-7]. So we do not consider this as imitations or emulations of DIDA [1] or our main contributions. Besides, most related works **do not** provide the support that their models can be optimized to satisfy this assumption. **We propose Proposition 3 supporting that optimizing EAGLE can help satisfy Assumption 1, which is our contribution**. We further provide their proofs in Appendix C.3.
(continue) **Q3:** I am also very surprised why there is no detailed comparison with DIDA in this article. For example, what are the problems in the work of DIDA, and what are the advantages of this work compared with DIDA? **A3:** Thank you for your comment. We would like to point out that **we have provided detailed comparisons with DIDA [1] in the rebuttal and we will add the comparison in the revised version**. We also explain the comparisons again as follows. - **[Problems]** We acknowledge that we solve the same problem and follow the same task settings proposed by DIDA [1], which is not considered our contribution. We have made citations accurately and comprehensively in the contents. However, we tackle the problem from a new perspective with a novel framework, achieving better results. - **[Advantages]** Due to the page limit, we briefly discuss the comparison with DIDA in the main paper (lines 270-271) and experimentally validate the advantage of our method compared with DIDA [1]. The detailed difference and EAGLE’s advantages are: - **[Modeling environments]** EAGLE is the **first** to explicitly model latent environments on dynamic graphs by variational inference. DIDA [1] neglects to model complex environments, which weakens its ability in identifying invariant patterns. - **[Representation learning]** EAGLE learns node embeddings by $K$-channel environments disentangling and spatio-temporal convolutions, which helps better understand multi-attribute relations. DIDA [1] learns with single channel convolutions with attentions. - **[Invariant learning]** EAGLE discriminate spatio-temporal invariant patterns by **the theoretically supported $\mathbb{I}^\star(\cdot)$** for each node individually, leading to better removal of spurious correlations. DIDA [1] divides invariant/variant parts simply and heuristically with a minus operation for all nodes. - **[Causal intervention]** EAGLE perform fine-grained causal interventions with **both** observed and generated environment samples, better minimizing the variance of extrapolation risks, generalizing to unseen distributions better. DIDA [1] intervenes coarse-grainedly with only observed samples. --- We will make sure to provide the necessary clarifications and avoid these misunderstandings in the revision. Should you have any further questions or concerns, we are glad to continue the discussion and provide further clarifications. [1] Dynamic graph neural networks under spatio-temporal distribution shift. NeurIPS, 2022. [2] Learning invariant graph representations for out-of-distribution generalization. NeurIPS, 2022. [3] Learning substructure invariance for out-of-distribution molecular representations. NeurIPS, 2022. [4] Handling distribution shifts on graphs: An invariance perspective. ICLR, 2022. [5] Out-of-distribution generalization with causal invariant transformations. IEEE CVPR, 2022. [6] Causal inference by using invariant prediction: identification and confidence interval. Journal of the Royal Statistical Society Series B: Statistical Methodology, 2016. [7] Invariant risk minimization. arXiv, 2019.
Thanks, I have read the author's rebuttal and I decided to keep my score unchanged.
Thanks for the time and effort in reviewing our work and we would like to express our sincere gratitude to you for providing constructive suggestions. Hope our additional experiments and clarifications have addressed your concerns. We are happy to discuss with you further if you have other questions.
Thanks the authors for their careful rebuttals and efforts, which have resolved all my questions and concerns, and proposed corresponding improvement in the revision. In summary, this paper proposes a novel framework to address the challenge of out-of-distribution generalization in dynamic graphs. The authors investigate the impact of latent environments on dynamic graphs for the first time and extensive experiments demonstrate their superiors compared to baselines. It is worth noting that, OOD generalization on dynamic graphs is under-explored, and this work emphasizes the importance of the latent environments, which I think is insightful for the upcoming works. I suggest this paper to be accepted.
Dear Reviewer YPMZ, We would like to express our sincere gratitude to you for endorsing our work and providing constructive suggestions. OOD generalization on dynamic graphs is an interesting but under-explored task, and our work investigates the impact of latent environments on dynamic graphs for the first time, which brings a new perspective to the upcoming work in this field. Thanks again for the time and effort in reviewing our work!
Re: Rebuttal by Authors
Thank you for the detailed rebuttal. I appreciate the authors providing the experimental results for selecting the appropriate $K$. However, I feel like the warm-up mechanism cannot fully convince me, as we usually do not know which kind of features (i.e., invariant or spurious) are learned by the model in the first 10 epochs, and the experimental results demonstrate that different $K$ affects the AUC score. Therefore, I would like to keep my score unchanged.
We thank the reviewer for the feedback. We would like to further clarify your concerns as follows. **Q:** I feel like the warm-up mechanism cannot fully convince me, as we usually do not know which kind of features (i.e., invariant or spurious) are learned by the model in the first 10 epochs, and the experimental results demonstrate that different $K$ affects the AUC score. **A:** Thanks for your question. $K$ reflects the number of underlying environments, which is closely related to the datasets. Thus, we indeed need to decide the most appropriate $K$ for each dataset. As a general practice, we treat $K$ as a hyper-parameter and tune it on the validation set for the first 10 epochs, as we explained in the last response. Following your suggestion, we further demonstrate that 10 epochs are sufficient to decide the most appropraite $K$ empirically. Specifically, we show the AUC on COLLAB dataset with different $K$ as follows: | $K$ | 2 | 4 | 6 | 8 | 10 | | --- | --- | --- | --- | --- | --- | | Epoch 2 | 61.07 | 62.79 | 63.91 | 63.11 | 60.22 | | Epoch 4 | 63.44 | 64.32 | 65.23 | 64.60 | 61.34 | | Epoch 6 | 64.21 | 67.51 | 67.79 | 67.35 | 62.98 | | Epoch 8 | 66.58 | 68.23 | 69.95 | 68.83 | 64.05 | | Epoch 10 | 68.29 | 69.96 | 71.26 | 70.24 | 66.12 | | Final Epoch (converged) | 80.33 | 81.17 | 84.41 | 83.65 | 81.94 | The above results show that, though not converged, the model performance for the first 10 epochs is able to determine the optimal $K$ value, which is **consistent with the final result, validating the effectivness of our warm-up mechanism.** We will incorporate the results in the revision. Besides, we would like to clarify that the warm-up mechanism is a training “trick” we adopted in practice to improve the training efficiency, and we do not consider it as a main contribution. **There’s no big difference to fine-tune** $K$ **with complete epochs without applying the warm-up mechanism.** We will leave exploring more advanced methods to decide $K$ as future works. Should you have any further questions or concerns, we are glad to provide further responses.
Dear Reviewer iWRC, As we draw closer to the rebuttal deadline, I would like to inquire if you have any additional questions or concerns about our work. We greatly value your feedback. Thank you! Best, Authors from submission 1276
Re: Official Comment by Authors
Thank the authors for their response and efforts. I agree that the warm-up mechanism for selecting appropriate $K$ is not the main contribution of the paper, but I feel it still has a significant impact on the model performance, as it reflects the number of environments. Therefore, without further improvement on the mechanism for selecting appropriate $K$, I would like to keep my score as is.
Thanks for your question. As we regard $K$ a hyperparameter, its impact on the model performance demonstrates our understanding and investigation of the latent environments on dynamic graphs is rational. Though choosing the appropriate $K$ by fine-tuning is a common way, we will improve the mechanism to determine the most suitable $K$ for different datasets in the revised version. Thanks for the time and effort in reviewing our work and we would like to express our sincere gratitude to you for providing constructive suggestions.
Decision
Accept (poster)