Mitigating Graph Covariate Shift via Score-based Out-of-distribution Augmentation

Authors: Bohan Wang, Yurui Chang, Lu Lin
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Neural Network, Graph Data Augmentation, Distribution Shift

Abstract:
Distribution shifts between training and testing datasets significantly impair the model performance on graph learning. A commonly-taken causal view in graph invariant learning suggests that stable features of graphs are causally associated with labels, whereas unstable environmental features lead to distribution shifts. In particular, covariate shifts caused by unseen environmental features in test graphs underscore the critical need for out-of-distribution (OOD) generalization. Existing graph augmentation methods designed to address the covariate shift often disentangle the stable and environmental features in the input space, and  selectively perturb or mixup the environmental features. However, such perturbation-based methods heavily rely on an accurate separation of stable and environmental features, and their exploration ability is confined to existing environmental features in the training distribution. To overcome these limitations, we introduce a novel approach using score-based graph generation strategies that synthesize unseen environmental features while preserving the validity and stable features of overall graph patterns. Our comprehensive empirical evaluations demonstrate the enhanced effectiveness of our method in improving graph OOD generalization.

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

Reviews and discussion:
<thread>
creation date:
1729292165154

thread_type:
official_review

<thread_object>
creator: reviewer_hmbi

<content>
summary:
This paper introduces a innovative OOD Augmentation (OODA) method to address the issue of covariate shifts in graph learning. Specifically, the authors propose a conditional score-based graph generation strategy that synthesizes unseen graphs. Extensive experiments show that OODA outperforms many baselines on synthetic and real-world datasets, including molecular and sentiment analysis tasks, under various covariate shift conditions.

strengths:
1. The paper is easy to follow with clear logic flow.
2. Using diffusion models to generate OOD examples for OOD generalization is interesting.
3. The experiments conducted are comprehensive with non-trivial improvements.

weaknesses:
Although I find the diffusion-based OOD augmentation intriguing, there are several major weaknesses.

1. The understanding of the OOD literature is not deep or accurate enough, which leads to misleading descriptions. For example, [1] is misused in the statement “line 162: separating environmental components could be inherently unfeasible,” while the original paper actually indicates that without explicit environmental information and **extra assumptions**, it is infeasible to achieve OOD generalization.
2. While previous methods generally introduced clear assumptions and theoretical guarantees, this paper does not include any theoretical analysis. As a result, it is unclear why the proposed method would effectively solve the OOD generalization problem.
3. The authors claim that covariate shifts are relatively neglected in graph learning, but they missed an important covariate shift-related baseline [2]. I believe including a comparison with this method would make the performance results more convincing. To be clear, I don’t expect this method to outperform those that leverage environment labels. However, it is crucial to compare the performance under your assumptions and those of environment-available baselines. The performance of a good method under OOD assumptions can approach that of environment-available methods. *Essentially, with proper theoretical guarantees for optimization, comparing different OOD methods becomes a competition of assumptions.*

[1] Chen, Yongqiang, Yatao Bian, Kaiwen Zhou, Binghui Xie, Bo Han, and James Cheng. “Does invariant graph learning via environment augmentation learn invariance?” Advances in Neural Information Processing Systems 36 (2023).

[2] Gui, Shurui, Meng Liu, Xiner Li, Youzhi Luo, and Shuiwang Ji. “Joint learning of label and environment causal independence for graph out-of-distribution generalization.” Advances in Neural Information Processing Systems 36 (2023).

questions:
1. Will this generation process eliminate important components of graphs?
2. Is the OOD guidance targeting generating samples with low likelihood under the original distribution? Is it the only assumption used? Any other constraints?
3. What do you mean more uniform relative to the original data distribution? (line 279)
</content>
</thread_object>

</thread>
<thread>
creation date:
1730041823492

thread_type:
official_review

<thread_object>
creator: reviewer_cufz

<content>
summary:
This study proposes a novel framework called Out-of-Distribution Diffusion Augmentation (OODA), which employs score-based graph generation to address covariate distribution shifts in graph data. The core idea is to expand the training distribution by generating new graph samples that capture previously unseen environmental features while preserving stable, predictive patterns, thus enhancing the model’s OOD generalization capabilities.

strengths:
1. The paper is well-organized, clearly motivating the need for improved graph OOD generalization by highlighting the limitations of existing perturbation-based augmentations. 

2. Extending the score-based diffusion model to graph OOD generalization is novel, which aims to enable controlled augmentation that balances diversity with stability. 

3. Extensive experiments demonstrate the effectiveness of the proposed OODA framework. The experiments highlight the practical relevance of the method for real-world applications involving covariate shifts in graph data.

weaknesses:
1. A primary concern is the diversity of the generated graphs, which remains somewhat unclear. While the authors report that the MMD distance increases as $\lambda$ grows (Sec. 5.3), this metric alone does not sufficiently convey how diverse the generated subgraphs are for handling graph covariate shifts. The authors should conduct experiments to demonstrate the quality of the generated samples quantitatively (using some metric to quantify the degree of diversity), and better to provide a theoretical analysis as this is the key component of this work.

2. The framework’s effectiveness in addressing size shifts is unclear, as the generated subgraphs are constrained to match the original subgraphs in the total node count if I understand correctly. Despite this, the model performs well on the GOOD-HIV-size benchmark, can the authors explain how and why the method can generalize well for size shift on GOOD-HIV-size dataset but not so well on GOODMotif-size dataset? Second, OODA perform similarly to the SOTA method such AIA on synthetic datasets, e.g., GOOD-Motif. This may indicate that the samples generated by this method have limitations in terms of accuracy and diversity.

3. Experimental comparisons may not be fair, as prior methods use GNN as backbones, whereas OODA relies on multiple graph transformers for estimating score functions and for predicting class labels. Furthermore, training multiple graph trasnsformers also introduce additional time and space complexity. Can the authors discuss the time and space complexity, and report the time and memory consumption, and compare with other methods?

4. The choice to use a pretrained graph transformer for analyzing stable pattern preservation (line 435) lacks clarity, why not use the finally obtained invariant GNN for evaluation, but use the graph trasnformer,which is utilized for data augmentation.

5. $\lambda$ would affect the generated graphs’ smoothness and the degree of diversity, yet the paper lacks a sensitivity analysis for this parameter. How different values of $\lambda$ affect the graph diversity and model performance?

6. OODA modify the differential equation to incorporate labels in Eqn. 5, however, it lacks a theoretical guarantee for the generated samples to preserve stable patterns and promote the diversity. It is better to provide some theoretical insights on this aspect.

questions:
1. $\lambda$ controls the extent of the exploration and the diversity of the generated sample, does it mean higher $\lambda$ will lead to better OOD generalization performance?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730657655042

thread_type:
official_review

<thread_object>
creator: reviewer_fkfr

<content>
summary:
This work studies the data augmentation method for graph OOD generalization under covariate shifts. The authors argue that previous approaches in graph augmentation may generate inaccurate samples, as which heavily rely on an accurate separation of stable and environmental features. Therefore, they propose a new approach that adopts score-based graph generation strategies to synthesize unseen environmental features while preserving the validity and stable features of the overall graph patterns. They conduct extensive experiments on GOOD benchmark to verify the effectiveness of the proposed approach.

strengths:
(+) This work identifies a critical problem in generating valid graph examples for graph OOD generalization.

(+) The idea of adopting a score-based strategy is new and interesting.

(+) The experiments show the effectiveness of the proposed method.

weaknesses:
(-) It remains unclear to what extent the proposed score-based strategy could preserve the stable features.

(-) The technical novelty is limited.

(-) The ablation studies are limited.

questions:
1. It remains unclear to what extent the proposed score-based strategy could preserve the stable features. It seems that the preservation of the stable graph features relies on the classifier $\phi_t$. 
- However, it is unclear how the classifier is trained;
- If there exists a classifier that can already reliably approximate $p_t(y_G|G_t)$, then, it seems the classifier itself can already be used for tackling covariate shifts;
- In addition, it has been mentioned several times about the variable $y_ood$, but it has not been formally defined. Meanwhile, it is unclear why $y_ood$ could specify the amount of OOD exploration;

2. The technical novelty is limited, as it is a simple modification of the diffusion models on graphs, and no additional theoretical results are provided;

3. The ablation studies are limited:
- It is unclear how the hyperparameters are selected and whether OODA is sensitive to the choice of hyperparameters;
- It'd be great to give more examples of generated realistic graphs;

4. Can we use the generated graphs to improve the performance of other graph OOD methods?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730745595429

thread_type:
official_review

<thread_object>
creator: reviewer_iejh

<content>
summary:
The paper proposes OODA, a score-based OOD augmentation framework for graph neural networks aimed at enhancing generalization under covariate shift conditions. It leverages a score-based generative model using diffusion processes to synthesize new graph environments, retaining stable predictive patterns while introducing controlled shifts. It generates OOD graphs that maintain graph validity and stable patterns without requiring explicit environmental separation. The authors conduct experiments across synthetic and real-world datasets, demonstrating OODA's advantages over traditional augmentation and invariant learning methods.

strengths:
1. The research topic graph OOD is important. The idea of using OOD graphs with diffusion for simulating the environment is interesting.
2. The experiments with synthetic and real-world datasets show effectiveness, which is good.
3. The method is easy-to-understand overall.

weaknesses:
1. One of the main concern is the motivation of the method, which I think is not well explained. I do not understand why the diffusion processes can synthesize OOD samples without enough and well-defined prior knowledge of the out-of-distribution.
2. The methodology to adjust shifts via hyperparameters, such as λ. However, it lacks a thorough discussion on selecting these parameters across different datasets, impacting reproducibility and usability.
3. The discussions on graph OOD are very limited, especially the Invariant Graph Learning part. The authors might consider referring to the survey [1] or the other surveys for introducing more related works and comparing the differences.

[1] Li, et al. Out-Of-Distribution Generalization on Graphs: A Survey. https://arxiv.org/pdf/2202.07987

I am happy to increase my score if the concerns can be fully addressed.

questions:
See Weaknesses.
</content>
</thread_object>

</thread>


Metareview:
metareview:
(a) The paper introduces OODA, a framework designed to enhance the out-of-distribution (OOD) generalization capabilities of graph neural networks. Using score-based graph generation strategies, the method was tested across various datasets, demonstrating improved effectiveness over traditional approaches.

(b) The reviewers find the application of diffusion processes for graph OOD generalization novel and appreciate the validation of the framework's effectiveness through experiments across various scenarios.

(c) The paper does not clearly explain why diffusion processes are suitable for generating OOD samples without extensive prior knowledge of the OOD space. Several reviewers found the selection of hyperparameters like $\lambda$, crucial for adjusting shifts, confusing. Additionally, the necessity of training a classifier to guide OOD generation raised concerns about the validity of the generated samples, highlighting a potential chicken-and-egg problem depending on the classifier's effectiveness.

(d) The reviewers express reservations about the paper, citing a lack of theoretical support, increased computational demands, and potential unfair comparisons due to the use of graph transformers instead of traditional GNN architectures for the proposed method.