Invariant graph representation learning aims to learn the invariance among data from different environments for out-of-distribution generalization on graphs. As the graph environment partitions are usually expensive to obtain, augmenting the environment information has become the de facto approach. However, the usefulness of the augmented environment information has never been verified. In this work, we find that it is fundamentally impossible to learn invariant graph representations via environment augmentation without additional assumptions. Therefore, we develop a set of minimal assumptions, including variation sufficiency and variation consistency, for feasible invariant graph learning. We then propose a new framework Graph invAriant Learning Assistant (GALA). GALA incorporates an assistant model that needs to be sensitive to graph environment changes or distribution shifts. The correctness of the proxy predictions by the assistant model hence can differentiate the variations in spurious subgraphs. We show that extracting the maximally invariant subgraph to the proxy predictions provably identifies the underlying invariant subgraph for successful OOD generalization under the established minimal assumptions. Extensive experiments on datasets including DrugOOD with various graph distribution shifts confirm the effectiveness of GALA.
Paper
Similar papers
Peer review
Summary
The paper proposes a new framework called Graph invAriant Learning Assistant (GALA) to address the problem of learning invariance among data from different environments for out-of-distribution generalization on graphs. The authors argue that the performance of graph neural networks (GNNs) can be seriously degraded by graph distribution shifts caused by mismatches between the training and test graph distributions. GALA incorporates an assistant model to differentiate the variations in spurious subgraphs and identify the underlying invariant subgraphs. The authors conduct extensive experiments on 12 datasets with various graph distribution shifts and show that GALA brings improvements in multiple graph datasets.
Strengths
1. Originality: The paper proposes a novel framework, Graph invAriant Learning Assistant (GALA), that introduces a new assistant model to differentiate the variations in spurious subgraphs and identify the underlying invariant subgraphs. 2. Quality: The authors do extensive experiments to validate the effectiveness of the proposed approach. They also provide a detailed analysis of the results and compare their approach with several state-of-the-art methods. 3. Clarity: The paper explanations of the key concepts, the methodology, and detailed experimental results. 4. Significance: The paper's contributions are significant because they provide a new perspective on the problem of learning invariant graph representations and offer a practical solution that can be applied to real-world problems.
Weaknesses
1. It would be preferable to provide the definition of the problem before presenting your proposed method. 2. The novel concepts introduced in your proposal would benefit from a more detailed explanation. For instance, the concept of 'two-piece graphs' is somewhat confusing. It would be helpful if you could elaborate on why you have incorporated this concept and provide additional motivation. 3. It appears that Assumption 3.5 may not appropriately be considered as an assumption. Instead, you could simply explain that $H(C|Y)\neq H(S|Y)$. Treating "either $H(C|Y)>H(S|Y)$ holds or $H(C|Y)<H(S|Y)$ holds" as an assumption may seem unusual in this context.
Questions
1. I have difficulty understanding the expression $G_{c}:=f_{gen}^{G_c}(Y^{e}\cdot Rad(\alpha_{e}))$ on line 125. It seems to me that $G_{c}$ is determined purely by the label and not influenced by randomness ($Rad(\alpha_{e})$). Could you please clarify this for me? 2. In your discussion, you mentioned that when $\hat{G}_c$ contains parts of $G_s$, assigning the same labels to the generated graph is more likely to reinforce the spurious correlation between $G_s$ and $Y$. I would appreciate it if you could provide a detailed explanation of how your method effectively prevents this pitfall. 3. On line 179, you stated that "Any learning algorithm will fail in either $E_{tr}$ or $E_{tr}$". Could you please explain this sentence using clearer and more precise mathematical language? 4. In Figure 1, the last sentence mentions "pulling graphs with the same label but from $\{G_{p}\}$ and $\{G_{n}\}$ closer in the latent space." However, the figure seems to depict "pulling graphs with different labels but from $\{G_{p}\}$ and $\{G_{n}\}$ closer in the latent space." Is this a typographical error? 5. I am curious about your final loss function as mentioned in Algorithm 1. Equation 9 does not seem to be optimized directly. Could you please clarify what the final loss function is?
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
2 fair
Contribution
2 fair
Limitations
The writing in the paper is somewhat ambiguous, leading to occasional confusion. For more specific details, please refer to the sections labeled 'Questions' and 'Weaknesses' mentioned earlier.
A summary of rebuttal in response to Reviewer voKo
Dear Reviewer voKo, Thank you for reviewing our paper. We have addressed your concerns, which are summarized as follows: - We have improved the presentation according to your suggestions, by including the definition of the problem, the explanation of the “two-piece graphs”, and making Assumption 3.5 more concise; - We have clarified the randomness involved in our data model and how our method addresses the previous failure case; - We have provided a mathematical explanation for line 179, Fig. 1, and the final loss function used in Algorithm 1. Please let us know if you have any other concerns/questions and we would try our best to address them.
Thanks for the responses. I still have some concerns: 1. The OOD problem studied in this paper seems to focus only on the specific case: correlation shift, but leaving the covariate shift untouched. If only correlation shift is covered, it is hard to claim the "successful OOD generalization". 2. There are some related works missing, in both lines of data augmentation and invariant learning on graphs: - G-Mixup: Graph Data Augmentation for Graph Classification. ICML 2022 - Causal Attention for Interpretable and Generalizable Graph Classification. KDD 2022 - Graph Rationalization with Environment-based Augmentations. KDD 2022 - Robust Optimization as Data Augmentation for Large-scale Graphs. CVPR 2022 So currently, I keey my score unchanged.
Response to new questions of Reviewer voKo
Thanks for your response. Let us clarify your new questions. Regarding the distribution shifts studied in this paper, we studied the distribution shifts characterized by the causal models of [1], following the line of invariant learning [2], which could be generalized to both conditional and covariate shifts[1,3,4]. We need to clarify that our focus is to study the feasibility of learning invariant subgraphs for **successful OOD generalization under the causal model**, instead of a single type of distribution shift. We thank you for bringing up these related works that we have included the discussion of them in our revised paper. We need to clarify that: - [5,6] are general graph data augmentation methods that can be applied to most of the methods. We believe it is a promising future direction to incorporate [5,6] into the methods to further improve the OOD generalization on graphs; - [7,8] both are variants of DIR [9] that seek for generating new environments by simulating "causal intervention", i.e., by concatenating the information of invariant subgraphs with various spurious subgraphs. In Sec. 3.1, we showed that it is impossible to generate faithful new environments for boosting OOD generalization performance on graphs. **We indeed discussed and evaluated GREA[8] in our paper**, which has shown promising improvements over DIR. However, GREA still fails to achieve a satisfactory OOD generalization performance, aligned with our theory. We hope our response could clarify your new questions. Please let us know if there are any further comments/questions. We would appreciate it if you could jointly consider our responses when making the final evaluation of our paper. **References** [1] Learning causally invariant representations for out-of-distribution generalization on graphs, NeurIPS'22. [2] Invariant risk minimization, arXiv'22. [3] Invariant Models for Causal Transfer Learning, JMLR'18. [4] GOOD: A Graph Out-of-Distribution Benchmark, NeurIPS'22. [5] G-Mixup: Graph Data Augmentation for Graph Classification, ICML'22. [6] Robust Optimization as Data Augmentation for Large-scale Graphs, CVPR'22. [7] Causal Attention for Interpretable and Generalizable Graph Classification, KDD'22. [8] Graph Rationalization with Environment-based Augmentations, KDD'22. [9] Discovering invariant rationales for graph neural networks, ICLR'22.
Follow-up response
Dear Reviewer voKo, We would appreciate it very much if you could find time to take a look at our responses to your concerns, as the rebuttal will be closed in less than 2 days. We hope we would be able to discuss with you the concerns you have raised within the rebuttal period. Thank you.
More results
Thank you again for your efforts in reviewing our paper. To further justify our claims and theoretical results, we additionally provide results of CAL[7] on two piece graphs. It can be found that CAL[7] has the same behaviors as GREA[8] under invariance dominated and spuriousness dominated cases. | Datasets | {0.8, 0.6} | {0.8, 0.7} | {0.8, 0.9} | {0.7, 0.9} | |-----------|--------------|--------------|--------------|--------------| | ERM | 77.33(±0.47) | 75.65(±1.62) | 51.37(±1.20) | 42.73(±3.82) | | GREA | 82.11(±0.38) | 81.39(±0.86) | 57.38(±4.64) | 41.20(±2.99) | | CAL | 82.67(±0.24) | 81.39(±0.86) | 51.87(±1.59) | 39.18(±2.39) | | GALA | 81.69(±0.57) | 79.15(±0.60) | 72.03(±2.68) | 67.10(±2.44) | As the discussion phase is closing, we sincerely hope that you could take our previous responses into consideration when evaluating our paper.
Summary
This paper investigates OOD problems on graphs without environmental information. The authors show that it is impossible to learn invariant graph representations without additional assumptions. The authors propose a novel graph OOD method namely GALA based on a new assumption. An auxiliary model is used to make proxy predictions and then the proxy predictions are used to help identify invariant subgraphs. Experiments on 12 datasets show the effectiveness of the proposed method.
Strengths
S1. The authors clearly demonstrate that the identifiability of causal subgraphs is ill-posed without environment labels. Thereby, the authors give A3.3 and A3.5 and then propose GALA based on these two assumptions. S2. Both theoretical and experimental analyses are used to support the claim.
Weaknesses
W1. This is a math-heavy paper, but the notations are unclear to me, thus making it hard to read. For example, in lines 78-79, should there be something like $e \in \mathcal{E}_{all}$? In Equation 1, there is no definition about $\widehat{G}_c$. There are more examples, I will not list them all. W2. I think GALA can be used as a general OOD method. Why do the authors focus on graph data? I don't see any specific design only for graphs. Why not test GALA on other data types (ex., images)? W3. I don't understand why ERM still learns the spurious correlations in invariance dominated cases. Can this be justified theoretically?
Questions
Q1. I am confused about how to get the Oracle performance on these datasets. Can the authors provide more explanations? Q2. I don't understand why Disc fails on all the datasets except CMNIST-sp. Besides, on CMNIST-sp, only GALA and Disc have some improvement over ERM.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
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
2 fair
Presentation
1 poor
Contribution
3 good
Limitations
The authors didn't discuss the limitations of the proposed method.
Summary
This paper discusses the challenges of learning invariance among data from different environments for out-of-distribution generalization on graphs. The authors propose a new framework called Graph invAriant Learning Assistant (GALA) that incorporates an assistant model to differentiate the variations in spurious subgraphs. The paper also includes experiments on 12 datasets, including DrugOOD, with various graph distribution shifts to verify the superiority of GALA.
Strengths
- The paper tackles an interesting problem. Distributions shifts between training and test sets hinder and limit the potential applicability of graph neural networks methods into real world scenarios. - To the best of my knowledge, the method proposed in this paper is novel. - The paper is, mostly, well written and makes an effort to be easily understandable. - The paper presents valid theoretical arguments to back its main claims. - Finally, the paper presents an extensive sets of experiments that back the validity of the proposed method.
Weaknesses
- In the tables that contain results, the best values are bolded. However, the presentation of the results would be more fair if two different colours/markers would be used when the best result is within the confidence interval of another result. - The paper would be easier to follow if, along figure 2, a plausible real world example was used. - In the last part of the introduction section the authors convey their contributions. In my opinion, this part is one of the less clear in the paper. To improve the clarity, I suggest the authors make a bullet list of their contributions. In particular, I would like the authors to distinguish their original contributions and how they differ from the work of Lin et al [36].
Questions
I am interested in knowing if the authors believe there exists a connection between this work and the explainability literature. In particular, the counterfactual explainability subfield (like the work from [A], just to provide a reference). _[A] Lucic, Ana, et al. "Cf-gnnexplainer: Counterfactual explanations for graph neural networks." International Conference on Artificial Intelligence and Statistics. PMLR, 2022._
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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
3 good
Presentation
3 good
Contribution
3 good
Limitations
-
A summary of rebuttal in response to Reviewer m4Xg
Dear Reviewer m4Xg, Thank you for reviewing our paper. We have addressed your concerns, which are summarized as follows: - We have revised our tables and highlighted the best results with a confidence interval excluding the corresponding second best result, as shown in the rebuttal pdf. - We have provided real world examples for Fig.2 for readers easier to follow and listed our contributions distinguishing from Lin et al. [36]. - We have discussed the connection between the explainability literature (e.g., [A]). Please let us know if you have any other concerns/questions and we would try our best to address them.
A gentle reminder for the closing rebuttal window
Dear Reviewer m4Xg, We would appreciate it very much if you could find time to take a look at our responses to your concerns, as the rebuttal will be closed in less than 2 days. We hope we would be able to discuss with you the concerns you have raised within the rebuttal period. Thank you.
I thank the reviewer for their time and effort in making the rebuttal. The authors have successfully addressed some of my concerns/questions, in particular regarding the position of this paper in the current state of the art. However, having also read other reviews I was influenced by some of their points, like the concerns regarding the generalization capabilities of the method. All things considered, I maintain my original score.
Summary
Invariant graph learning methods aim to extract invariant patterns among different training environments for OOD generalization on graphs. A plethora of approaches focuses on augmenting environment information from training samples as the environment label is difficult to obtain. This work provides both theoretical and empirical analysis of the faithfulness of the existing environment augmentation methods for learning invariant graph representations. They demonstrate that it is impossible to learn invariant graph representations by environment augmentation without a set of minimal assumptions developed in the paper, including variation sufficiency and variation consistency. Based on these assumptions, they then propose GALA, Graph invAriant Learning Assistant, a new graph invariant learning framework via an assistant model providing proxy predictions to differentiate spurious variations. Experiments on 12 real-world graph OOD datasets demonstrate GALA's effectiveness.
Strengths
1. This paper is very well-written and organized. The problem studying (i.e., whether the existing environment augmentation methods are faithful for learning invariant graph representations) is significant, and the motivating synthetic experiments clearly demonstrate the pitfalls of existing environment augmentation. 2. Although the variation sufficiency and variation consistency assumptions seem intuitive, this paper is the first to develop these minimal assumptions systematically and utilize them to derive the impossibility results for existing methods. 3. GALA is technically sound and the authors provide theoretical analysis to demonstrate GALA is able to identify invariant subgraph patterns. 4. Experiments are comprehensive and extensive. The results of proof-of-concept and ablation studies are consistent with the theoretical results derived in the paper, and the real-world experiments demonstrate a considerable improvement among all the baselines. 5. The authors did a great job of citing related works (in the appendix).
Weaknesses
1. The environment assistant model is trained with vanilla ERM on spuriousness-dominated data to identify spurious correlations. My major concern is the vanilla ERM model should learn both spurious correlations and invariant patterns, and then how to guarantee the environment assistant model only learns environment-dependent patterns? I wonder if the authors have tried other biased ERM models as backbone and it would be great if they could elaborate more on this question. 2. In this paper, the authors divide the training sets into spuriousness-dominated and invariance-dominated sets. I wonder what if the whole training sets only contains spurious and invariance patterns distributed equally? 3. The authors did not discuss the computational complexity of GALA. I wonder if they could discuss it in detail.
Questions
1. The 3 questions mentioned in the Weaknesses part. 2. Since this work is proposed to tackle OOD generalization on graphs, I wonder if the authors made some attempts on OOD generalization on Euclidean data?
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
4 excellent
Contribution
3 good
Limitations
The authors discussed the broader impacts in the appendix.
A summary of rebuttal in response to Reviewer waKT
Dear Reviewer waKT, We want to thank you again for your insightful comments and suggestions. We have addressed your concerns, which are summarized as follows: - We have elaborated more on the curious questions of using other biased ERM architectures and whether the assistant model could learn both invariant and spurious patterns (under any cases); - We have discussed the computational complexity and compared our method with other competitors; - We have shown that our method indeed is able to generalize to Euclidean data, as shown in the experiments on CMNIST-sp and Graph-SST2. Please let us know if you have any other concerns/questions and we would try our best to address them.
A gentle reminder for the closing rebuttal window
Dear Reviewer waKT, We would appreciate it very much if you could find time to take a look at our responses to your concerns, as the rebuttal will be closed in less than 2 days. We hope we would be able to discuss with you the concerns you have raised within the rebuttal period. Thank you.
Re: Rebuttal by Authors
Thank you for the detailed rebuttal. I appreciate the authors providing an empirical analysis regarding GALA's computational complexity, which addresses my concern about the model's computational complexity. Regarding the questions about the environment assistant model, I now understand the intuition and agree it would learn spurious correlations on spuriousness-dominated graphs. However, I am still not fully convinced about the environment assistant model's ability to distinguish different environments, as the goal of the environment assistant model is trying to distinguish different environments from extracted spurious correlations, while the ERM-based model (e.g., vanilla GNN) learns both invariant and spurious correlations. I think the current design of the environment assistant model is in the middle of an invariant learning model and a model only learns spurious correlations. Thus, I feel maybe an extra feature-selection step or designing a biased ERM model as backbone rather than vanilla GNN might help. That being said, I think the above concerns are minor, and I would like to keep my score as an Accept.
Thank you for checking our rebuttal and for your further comments
Thank you for checking our rebuttal and for your further comments. > Regarding the environment assistant model's ability to distinguish different environments In fact, the current design of the environment assistant model aims to distinguish the variations of spurious features instead of the specific environment partitions. As spurious correlations are more unstable than invariant correlations (Variation sufficiency assumption), the partitioned positive and negative graph sets could amplify the instability of spurious correlations. Then, GALA could locate the invariant subgraphs by finding the subgraphs that preserve the maximal invariance across the positive and negative graph sets. As shown in Fig. 3a, no matter which of the invariant or spurious correlations is stronger (Variation consistency assumption), the invariant subgraph maintains the maximally invariant correlations across the positive and negative graph sets partitioned by a simple ERM-based model. Nevertheless, we agree there are limitations in the current design of the environment assistant model as you pointed out. Incorporating additional design such as selecting/identifying spurious features, or an even more biased assistant model, is definitely a promising future direction to extend and improve our framework. We have included the discussion in our revised draft. Thank you again for your constructive comments and suggestions!
Summary
The paper proposes Graph invAriant Learning Assistant (GALA), targeting at out-of-distribution (OOD) generalization on graphs leveraging invariant graph representation learning. Authors argue that environment augmentation cannot achieve this without additional assumptions, leading to the development of minimal assumptions—variation sufficiency and variation consistency. GALA utilizes an assistant model to distinguish variations in spurious subgraphs sensitive to environment changes or distribution shifts. Empirical experimental results support the efficacy of GALA. **Post Rebuttal**: I have read the rebuttal of the authors and will keep my rating.
Strengths
- This paper provides a thorough theoretical explanation with step-by-step illustration. It builds a strong theoretical case for the proposed framework, establishing a set of minimal assumptions required for invariant graph learning. Practically GALA has a new design using an assistant model to differentiate variations in spurious subgraphs. - Empirically, authors present extensive experimental results on both synthetic and real-world data, showing the effectiveness of the proposed method.
Weaknesses
- Considering that scalability has always been an issue for GNNs, it would be better if the authors can also discuss the overhead of further introducing a new assistant module. - The proposed method seems specialized in the OOD generalization of graph structures, whereas the feature OOD is also a major problem in the graph OOD setting. Considering this the applicability of this method may be restrained.
Questions
- The assistant model that needs to be sensitive to graph environment changes, but how do you guarantee that?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
3 good
Limitations
The authors may not explicitly discuss the limitations of the proposed method.
A summary of rebuttal in response to Reviewer W1GV
Dear Reviewer W1GV, Thank you for reviewing our paper. We have addressed your concerns, which are summarized as follows: - We have discussed the computational overhead of our method and compared it with the competitors; - We have clarified that our method indeed can be applied to address distribution shifts on node features, as shown in CMNIST-sp experiments. - The sensitivity to graph environment changes of the assistant model is **guaranteed by the nature of ERM** (We provided more details in the [response](https://openreview.net/forum?id=EqpR9Vtt13¬eId=DrbfXyaIu5) to Reviewer 3cig). It is theoretically proved in [8] that ERM will learn **any correlations presented in the data**, no matter whether the correlation is invariant or spurious. If we look into the first two columns in Table 1, it can be found that **GNNs trained with ERM still have a large gap from the oracle models**, meaning that GNNs trained with ERM still learn the spurious correlations. Please let us know if you have any other concerns/questions and we would try our best to address them.
A gentle reminder for the closing rebuttal window
Dear Reviewer W1GV, We would appreciate it very much if you could find time to take a look at our responses to your concerns, as the rebuttal will be closed in less than 2 days. We hope we would be able to discuss with you the concerns you have raised within the rebuttal period. Thank you.
Thank you for reading our rebuttal
Thank you for checking our rebuttal and we're glad that we addressed more of your concerns. If any of your remaining concerns are not addressed, do please let us know and we would try our best to address them, or at least discuss with more details in the paper as we believe this could improve our work. Thank you again.
Decision
Accept (poster)