Diversifying Spurious Subgraphs for Graph Out-of-Distribution Generalization

Authors: Tianjun Yao, Yongqiang Chen, Tongliang Liu, Le Song, Eric P. Xing, Zhiqiang Shen
Primary area: learning on graphs and other geometries & topologies
Keywords: OOD generalization, invariant learning, graph neural networks

Abstract:
Environment augmentation methods have gained some success in overcoming the out-of-distribution (OOD) generalization challenge in Graph Neural Networks (GNNs). Yet, there exists a challenging trade-off in the augmentation: On one hand, it requires the generated graphs as diverse as possible to extrapolate to unseen environments. On the other hand, it requires the generated graphs to preserve the invariant substructures causally related to the targets. Existing approaches have proposed various environment augmentation strategies to enrich spurious patterns for OOD generalization. However, we argue that these methods remain limited in diversity and precision of the generated environments for two reasons: i) the deterministic nature of the graph composition strategy used for environment augmentation may limit the diversity of the generated environments, and ii) the presence of spurious correlations may lead to the exclusion of invariant subgraphs and reduce the precision of the generated environments. To address this trade-off, we propose a novel paradigm that accurately identifies spurious subgraphs, and an environment augmentation strategy called spurious subgraph diversification, which extrapolates to maximally diversified spurious subgraphs by randomizing the spurious subgraph generation, while preserving the invariant substructures.  Our method is theoretically sound and demonstrates strong empirical performance on both synthetic and real-world datasets, outperforming the second-best method by up to 24.19% across 17 baseline methods, underscoring its superiority in graph OOD generalization.

Decision: reject
Reviewer scores: 5, 6, 6, 5

Reviews and discussion:
<thread>
creation date:
1729751154152

thread_type:
official_review

<thread_object>
creator: reviewer_jzm8

<content>
summary:
Environment augmentation methods have shown promise in addressing out-of-distribution (OOD) generalization challenges in Graph Neural Networks (GNNs), but they face a trade-off between generating diverse graphs and preserving invariant substructures. Current methods are limited by deterministic graph composition strategies and the risk of excluding important subgraphs due to spurious correlations. To overcome these challenges, the authors propose a method called spurious subgraph diversification, which randomizes spurious subgraph generation while maintaining key invariant structures, achieving up to 24.19% better performance than 17 baseline methods on both synthetic and real-world datasets.

strengths:
- The problem of graph OOD generalization is important.
- The framework provides detailed theoretical analysis, including bounds on generalization performance.
- The empirical results, involving comparisons with 17 baselines across multiple datasets, demonstrate the effectiveness of the method.
- The paper includes detailed ablation studies and sensitivity analyses to highlight the importance of each component of the iSSD framework.

weaknesses:
- A major concern is about the soundness of the method "to idenitfy edges from spurious subgraphs accurately, we utilize the bottom K% of edges with the lowest predicted probabilities as estimated spurious edges". First, this identification of spurious subgraphs may not hold in many scenarios, where some spurious edges have strong correlations with the labels for the model to exploit, and thus for these edges model has high predicted probabilities. Second, in this way, there no supervision signals for capturing spurious edges, how do the authors guarantee that the captured edges are indeed spurious? Third, a surge of works in graph ood generalization propose different methods to capture spurious/variant subgraphs, how do this method surpass these methods?

- Another major concern is about the novelty of the method. Diversifying the spurious subgraphs, or environments, to improve graph ood generalization performance has been explored in many related works, e.g., EERM in ICLR22, which is not compared as baseline.  Also, the learnable data transformation module is similar to DIR in ICLR22.

- (minor) typo. In line 72,  "idenitfy".

questions:
see weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730151914048

thread_type:
official_review

<thread_object>
creator: reviewer_cgq7

<content>
summary:
The paper proposes a novel environment augmentation method for graph out-of-distribution (OOD) generalization. Input graphs are assumed to be composed of an invariant/causal subgraph $G_c$ that predicts the target and a spurious subgraph $G_s$ that encodes environment variability. Their approach involves learning a data transformation with high sampling probability for edges in $G_c$ and a low sampling probability for edges in $G_s$. This is done via a combination of cross-entropy loss and two new regularization terms: (1) Graph size constraint $L_e$ to control the number of pruned edges during transformation; (2) Spurious subgraph diversification $L_{div}$ to maximize randomness in the spurious subgraphs retained after transformation. This is supplemented by theoretical proofs showing that $L_e$ tightens OOD generalization bound while $L_{div}$ improves OOD generalization. To empirically verify these claims, they benchmark performance against 17 baseline methods across 4 dataset classes, perform ablation studies on the regularization terms, evaluate sensitivity to hyper-parameters, and other in-depth analysis.

strengths:
1. The paper is well-written and all claims and design choices are well-motivated with appropriate references to literature. 
2. It presents a novel idea grounded in theory to tackle OOD graph generalization, a problem of interest for broader graph community
3. Along with performance comparison against baseline methods, they include sufficient empirical analysis to justify their design choices and insights to support theoretical claims.

weaknesses:
1. Limited data diversity: Apart from the synthetic GOODMotif dataset, all others pertain to molecules. In these datasets, it may be possible to ascribe target graph label to specific functional groups and thus, ascertain the invariant subgraphs. While it is alright to limit the scope of experiments, I wonder how the proposed method performs against datasets from other application domains (CMNIST, GOOD-Arxiv). It may be useful to provide more insight or comment on the broader applicability of proposed approach.

questions:
1. Do we have an intuition on why the performance drops for Motif-Base dataset on going from K=90 to 70 and rises again for K=50 for all $\eta$ in Figure 2?
2.  Do we have an insight into the cause of higher variance on removing either $L_e$ or $L_{div}$?
3. Why was ERM pre-training used? Was it used with other baseline methods as well? If not, why? Could we include performance w/o ERM training to isolate and analyze performance gains from proposed techniques?
4. Both the GOOD datasets use covariate shift split. Is the method applicable to concept shift?
5. How restrictive is the regularization from $L_e$? Do we know how the number of edges are distributed in graphs sampled from $t(G)$?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730353120257

thread_type:
official_review

<thread_object>
creator: reviewer_ww8s

<content>
summary:
This paper proposes a novel augmentation strategy for out-of-distribution (OOD) generalization by diversifying spurious subgraphs. The method, termed spurious subgraph diversification, employs randomized spurious subgraph generation to maximize diversity while preserving invariant substructures. This approach achieves state-of-the-art results on both synthetic and real-world datasets.

strengths:
1. The authors provide a unified theoretical framework for Learnable Data Transformation under graph OOD scenarios, demonstrating a solid theoretical foundation.
2. The proposed iSSD framework is easy but effective. Extensive experimental results demonstrate the superiority of proposed method.
3. The paper is well-written, and easy to follow. I really enjoy reading this paper.

weaknesses:
1. The authors propose a graph size constraint loss (Eq. 7) to make sure the model will prune edges from the spurious subgraphs. However, I am puzzled as to how this is guaranteed? Because this loss can only ensure that the model will remove edges according to the budget, it is entirely possible to minimize the Eq. 7 loss by removing the edges included in the causal subgraph.
2. I believe that the joint selection of $K$ and $\eta$ is tricky in the motif dataset. Additionally, for real-world datasets or practical model deployments, how to choose $K$ and $\eta$ without prior knowledge about the scale of "spurious subgraph"?
3. As this study focuses on augmentation-based methods for graph OOD generalization, it would be better that the authors to include additional baseline or more discussion about augmentation-based graph OOD generalization methods, such as [1-2].

[1] Graph Out-of-Distribution Generalization with Controllable Data Augmentation. TKDE 2024.

[2] Graph Invariant Learning with Subgraph Co-mixup for Out-Of-Distribution Generalization. AAAI 2024.

questions:
Please address my concern in weakness part.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730663881002

thread_type:
official_review

<thread_object>
creator: reviewer_tupv

<content>
summary:
One big challenge for graph machine learning (GML) is that real-world graph data continuously evolves over time, introducing changes in graph structure and node/edge features, causing graph distribution shift. However, retaining GNN models every time the graph is updated is expensive or sometimes infeasible. How to handle the out-of-distribution (OOD) problem in GNN model training becomes a challenging problem. This paper proposes a novel theory to identify the invariant subgraphs, whose edges exhibits high predicted probabilities in the learnable data transformation to the target graph labels, and the spurious subgraph, whose edges exhibit lowest predicted probabilities. The proposed  learning framework based on the theory exhibits stable and good performance over existing baseline models on 7 real-world datasets with an average of 2.38%

strengths:
* The paper proposes a novel theory to identify the invariant subgraphs and spurious subgraphs. The paper shows that with the proposed edge dropping function t, the graph size constraint loss L_e and the spurious subgraph diversification loss L_{div}, the proposed method can identify the invariant graphs and the spurious graphs. Furthermore, the evaluation in section 7.5 demonstrates that the proposed method can distinguish G_c and G_s using the GOOD-Motif datasets.
* The proposed methods shows stable and good performance over existing baseline models on 7 real-world datasets with an average of 2.38%.

weaknesses:
* The whole method assumes that for every label y, there exists only one G_c. Is it possible that there are more than one G_c correspond to a label y? Will all the assumptions and theorems hold in such cases?
* The proposed method can not handle OOD cases on graph tasks like node classification, link prediction, etc. This limit the scope of the method.
* Hyper-parameter \eta (L215) and K (L249) are critical to the size of G_s and are thus critical to the method. Theorem 4.1 and 4.2 rely on these two hyper-parameters. How to select the right value for these hyper-parameters without knowing the size of G_c is not discussed.
* Some proves are missing:
    * Why Theorem 3.1 is hold is not proved.
    * Why P(X^’_{ij}) = 1/|G_s| is enforced by L_{div} is not well explained.

questions:
I would suggest to move definition 2 before Theorem 3.1.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732096731973

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
Dear reviewers and AC,

We sincerely thank all reviewers and AC for their valuable feedbacks and constructive comments on our manuscript. During the rebuttal period, we have been focusing on these beneficial suggestions from the reviewers and doing our best to add several experiments and revise our draft. We believe our current carefully revised manuscript can address all the reviewers’ concerns. 

As reviewers highlighted, we believe our paper tackles an important problem (**Reviewer Jzm8**) with interest for broad graph community (**Reviewer CgQ7**), introducing a novel and effective method (**Reviewer tUpV, Reviewer Ww8s, Reviewer Jzm8**) with solid theoretical foundations (**Reviewer Ww8s, Reviewer Jzm8**). 


We also appreciate that the reviewers found our draft is well-written (**Reviewer Ww8s, Reviewer CgQ7**), all design choices in our method are well-motivated with sufficient empirical analysis for justification (**Reviewer CgQ7**), and detailed ablation studies and sensitivity analyses are provided (**Reviewer Jzm8**). 


Moreover, we thank the reviewers for pointing out the concerns regarding the assumption and broad applicability (**Reviewer tUpV**), proof issues in the theorems (**Reviewer tUpV, Reviewer Ww8s**), the potential challenges in selecting $\eta$ and $K$ (**Reviewer tUpV, Reviewer Ww8s**), diversity of the datasets (**Reviewer CgQ7**),  the soundness and technical novelty of our proposed method (**Reviewer Jzm8**). In response to these comments, we have carefully revised and enhanced our manuscript with the following important changes with the added experiments:

- **[Reviewer tUpV]** We have added a discussion on the applicability of Assumption 1 in scenarios with multiple invariant subgraphs, supported by new empirical results for validation (in Appendix H.3).  
- **[Reviewer tUpV]** We have included a discussion on extending our method to node-level and link-level OOD generalization (in Appendix C).  
- **[Reviewer tUpV, Ww8s]** We have corrected issues related to Theorems 4.1 and 4.2 (in Appendix E). 
- **[Reviewer Ww8s]** We have expanded Section 5 to include additional discussions on specified related works. 
- **[Reviewer CgQ7]** We have conducted additional experiments on application domains beyond molecular datasets (in Appendix H.3) and added new results from an ablation study on ERM pretraining (in Appendix H.3). We have also included new experimental results addressing concept shift (in Appendix H.3).  
- **[Reviewer Jzm8]** We have fixed the typo in line 72 and provided new experimental results on Recall@K and Precision@K to demonstrate the effectiveness of our method in identifying spurious edges and preserve causal edges (in Appendix H.3).  

These updates are temporarily highlighted in $\textcolor{blue}{\text{blue}}$ for facilitating checking.

We hope our response and revisions address all the reviewers' concerns, and we are more than eager to have further discussions with the reviewers regarding these updates.


Thanks,

Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a new environment augmentation method for graph out-of-distribution (OOD) generalization using subgraphs. The authors have made well-motivated design choices, and the empirical results provided are sufficient to demonstrate the method's potential. However, several reviewers raised important questions that warrant further discussion.

One of the primary concerns is the reliance of the method's effectiveness on certain assumptions being true. If these assumptions do not hold in real-world scenarios, the method's performance may be compromised. This concern is exacerbated by the novelty of the approach being seen as incremental rather than groundbreaking. While the authors argue that their "ranking-based approach" is novel, it is viewed by some reviewers as a relatively minor advancement over existing work. Furthermore, the soundness and generalizability of the method have been questioned by multiple reviewers. For instance, Reviewer Jzm8 raised a valid concern about the accuracy of identifying edges from spurious subgraphs, a concern that this meta-reviewer also shares.

Reviewer tUpV pointed out an important issue regarding the method's ability to handle cases with multiple invariant subgraphs for each label. The rebuttal provided additional theoretical analysis but relies on strong assumptions that could be problematic if violated. Specifically, Assumption 2 seems overly optimistic, as spurious inputs are often highly predictive of the target on the training environment, contradicting the assumption that causal subgraph signals are more predictive. Reviewer CgQ7 expressed concerns about the method's ability to identify spurious edges, the impact of concept shift, and the restrictiveness of the graph size constraint. Unfortunately, the authors' responses to these concerns were found to be somewhat unsatisfactory, as the problem seems manageable under their assumptions but may not be robust if these assumptions are only "approximately true."

On a positive note, Reviewer Ww8s had a favorable view of the paper and identified some mistakes that were corrected by the authors. This feedback highlights the potential of the method and the authors' willingness to address issues raised during the review process. However, given the detailed analysis and the borderline nature of this submission, I lean towards a borderline reject recommendation. The primary concerns regarding the method's assumptions, its ability to generalize under various conditions, and the restrictiveness of certain constraints need more thorough addressing.

In conclusion, while this paper proposes an interesting approach to graph OOD generalization, it falls short in addressing critical concerns raised by the reviewers. To strengthen their contribution, the authors should comprehensively address these concerns, particularly by providing more robust analysis or experiments that demonstrate the method's ability to handle complex cases and relax some of the restrictive assumptions and constraints. This would enhance the method's applicability and robustness, making it a more significant contribution to the field. Ultimately, this submission highlights important challenges in achieving graph OOD generalization and underscores the need for future work to develop more robust methods that can handle a wide range of scenarios with fewer key assumptions about the data distribution.