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

W2: 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.

We agree on the importance of theoretical gaurantee and acknowledge the challenge of providing one given the complexity of the SDE procedure. We would like to highlight the pioneering contribution of our work in designing a tractable conditional reverse-time SDE framework to mitigate graph covariate shifts, offering a fresh perspective on addressing this significant challenge in the field. The design of our SDE is carefully justified with clear principles, and the empirical results demonstrates a clear improvement. We believe the empricial and practical contribution of this work should not be diminished. We want to further explain the principles that support our design.

Prior Knowledge of Out-of-Distribution (OOD) Samples: As outlined in [5], our prior knowledge about the out-of-distribution aspect of input graphs $G$ is that they comprise two distinct components: the causal variable $C$ and the non-causal variable $S$, such as the House motif and the Tree base in the GOOD-Motif dataset. Here, $C$ serves as the sole endogenous parent crucial for determining the ground-truth label $y$, while $S$ is an element that varies across different environments. When synthesizing OOD samples, we use the label variable $y$ as prior knowledge and conditions to control the diffusion procudure, detailed as follows.

Conditional Reverse-time SDE with Label Knowledge: Our approach specifically maintains the integrity of the causal part $C$ while exploring the unstable non-causal part $S$ through the application of a conditional reverse-time Stochastic Differential Equation (SDE), as presented in Eq. (6). In Eq. (6), the condition $y_G$ controls the generated graph to maintain the label knowledge (i.e., keeping causal part $C$), and the condition $y_\text{ood}$ augments the graph to explore the environment (i.e., varying non-causal part $S$). This equation has never been proposed before, and the solution balancing label preservation and enrivonment exploration is nontrivial. To model this, we propose formulating the distribution $p_t\left(\mathbf{y}_{\text {ood }}=\lambda \mid G_t, \mathbf{y}_G\right)$ as proportional to the negative exponent of the joint density of $G_t$ and $\mathbf{y}_G, p_t\left(G_t, \mathbf{y}_G\right)$. This derives the expression for the gradient of the log probability for conditional reverse diffusion, as presented in Eq. (9). Eq. (9) is featured with the following properties:

Preserving the Label Knowledge by $y_G$: The second term $\log p_t\left(\mathbf{y}_G \mid G_t\right)$ aims to maximize the prediction probability of the graph's ground-truth label $y_G$ for each step. This essentially maintians the prior label knowledge when synthesizing the OOD samples.

Exploring the Training Distribution by $y_\text{ood}$: Combining two terms, the conditional score function creates a marginal distribution proportional to $p_t\left(G_t, \mathbf{y}_G\right)^{1-\sqrt{\lambda}}$.

When environmental graphs are explored, their patterns exist in the low-density regions of the original distribution. Conversely, un-explored graphs exist in high-density regions. With exploration strength $\lambda=0$, the marginal distribution becomes $p_t\left(G_t, \mathbf{y}_G\right)$,

which denoises the synthesized graphs from the augmented distribution to follow the original distribution $P_{\operatorname{tr}}(G, Y)$, thus both casual part $C$ and non-casaul part are preserved. By adjusting $\lambda$, we regulate dispersion, allowing generated graphs to maintain the causal $C$ and explore non-causal $S$, thus increasing the divergence between $P_{\mathrm{tr}}\left(G, Y \mid \mathbf{y}_{\text {ood }}=\lambda\right)$

and $P_{\mathrm{tr}}(G, Y)$.

Thus, our formulation achieves a tractable conditional reverse-time SDE. This advancement not only simplifies the generating OOD graphs by converting it into a conditional generation problem, but also presents a novel application of reverse-time SDE techniques in this context of graph covariate shifts.

W3: An important covariate shift-related baseline [4] should be compared, though this method leverages environment labels.

We acknowledge the necessity of including a performance comparison with the baseline [4] related to covariate shifts that you mentioned. In the final version of our paper, we will incorporate this baseline and thoroughly discuss the comparative results. This will allow us to provide a comprehensive view of how our method performs under our specific assumptions versus those that leverage additional environment labels. Below is the comparison.

As shown in the table, OODA achieves performance comparable to that of environment-aware methods on the GOOD-CMNIST, GOOD-HIV, and GOOD-SST2 datasets. We believe it would be a valuable future work to further improve the OOD performance by incorporating environment labels into our framework.

Q1: Will this generation process eliminate important components of graphs?

By design, we aim to preserve important graph components (i.e., the label information) during the generation process via the modeling of $\log p_t\left(\mathbf{y}_G \mid G_t\right)$, as the second term in Eq. (9) shows.

Our evaluations, presented in Figures 3, 4, and 5, verify OODA's capability to generate OOD graphs while effectively retaining stable patterns. This is evidenced by the expected probability $\mathbb{E}_{\tilde{G}_0 \sim \tilde{P}}\left[p\left(\mathbf{y}_G \mid \tilde{G}_0\right)\right]$ consistently exceeds $0.90$ as $\lambda$ increases. Additionally, visualizations in Table 3 demonstrate that as $\lambda$ increases, there are gradual modifications to the base graph structures, while key motifs remain intact. Finally, results in Table 1 illustrate that OODA outperforms state-of-the-art methods across diverse datasets. Such improvements would not be achievable if important graph components were eliminated during the generation process. The retention of these components is crucial for enhancing model performance and ensuring the reliability of generated graphs.

Q2: Is the OOD guidance targeting generating samples with low likelihood under the original distribution? Is it the only assumption used? Any other constraints?

Yes, the OOD guidance indeed aims at generating samples with low likelihood under the original distribution.

In addition to focusing on low-likelihood samples, we adopt the assumption, based on [2], that input graphs $G$ consist of two distinct components: the causal part $C$ and the non-causal part $S$. For instance, in datasets like GOOD-Motif, the House motif and Tree base exemplify this structure. The causal part $C$ is considered the sole endogenous parent that determines the ground-truth label $Y$, while the non-causal part $S$ varies across different environments, represented as $C \rightarrow Y$. Therefore, OODA uses a novel guidance scheme that generates augmented graphs, concurrently retaining predictive stable patterns and incorporating explored environments.

As highlighted in [3], ensuring meaningful exploration requires keeping deviations within a certain range from the original distribution to maintain the integrity of the causal component $C$. Therefore, the choice of $\lambda$ is crucial and must be meticulously calibrated based on performance metrics from OOD validation sets across diverse datasets to ensure effective and responsible exploration.

Thank you for your insightful comments and requests for clarifications. We will try addressing your concerns below:

W1: The understanding of the OOD literature is not deep or accurate enough, which leads to misleading descriptions.

Thank you for pointing out the discrepancy in our description. We appreciate your guidance on ensuring our references accurately reflect the literature.

We will revise the statement to accurately reflect the insights from [1]. The new sentence will read: "Without explicit environmental information and additional assumptions, separating environmental components could be inherently unfeasible." This aligns with the authors in [1], who state: "Invariant and spurious subgraphs are denoted as $G_c$ and $G_s$. More formally, if $\exists G_s$, such that $P^{e_1}\left(Y \mid G_s\right)=P^{e_2}\left(Y \mid G_s\right)$ for any $e_1, e_2 \in \mathcal{E}_{\text {tr }}$,

where $P^e\left(Y \mid G_s\right)$ is the conditional distribution $P\left(Y \mid G_s\right)$ under environment $e \in \mathcal{E}_{\text {all }}$, it is impossible for any graph learning algorithm to identify $G_c$."

Q3: What do you mean more uniform relative to the original data distribution? (line 279)

By "more uniform relative to the original data distribution," we refer to a broadening or dispersion of the original distribution $P_{\mathrm{tr}}\left(G, Y\right)$. We have changed the original statement in the modified version to avoid confusion. In the original distribution, the data for a class $Y$ often appears as a tightly centered cluster within the data space, with well-defined causal relationships. When we increase $\lambda$, it modulates this distribution to enhance variability and exploration. As $\lambda$ increases, it influences the distribution to be more dispersed. This enhanced dispersion allows for the sampling of graphs that retain the critical causal components responsible for determining label $Y$. However, these graphs also incorporate more diverse and novel non-causal elements, sampled from $P_{\mathrm{tr}}\left(G, Y \mid \mathbf{y}_{\mathrm{ood}}=\lambda\right)$. This enables the inclusion of a wider array of graph features, fostering exploration beyond the tightly clustered native structures, which can lead to novel insights and robust model learning.

References:

[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] Wu, et al. Discovering invariant rationales for graph neural networks. https://arxiv.org/abs/2201.12872

[3] Sui, et al. Unleashing the Power of Graph Data Augmentation on Covariate Distribution Shift. https://arxiv.org/abs/2211.02843

[4] 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).

W6: It is better to provide some theoretical insights for the generated samples to preserve stable patterns and promote the diversity.

We agree on the importance of theoretical gaurantee and acknowledge the challenge of providing one given the complexity of the SDE procedure. We would like to highlight the pioneering contribution of our work in designing a tractable conditional reverse-time SDE framework to mitigate graph covariate shifts, offering a fresh perspective on addressing this significant challenge in the field. The design of our SDE is carefully justified with clear principles, and the empirical results demonstrates a clear improvement. We believe the empricial and practical contribution of this work should not be diminished. We want to further explain the principles that support our design.

Prior Knowledge of Out-of-Distribution (OOD) Samples: As outlined in [5], our prior knowledge about the out-of-distribution aspect of input graphs $G$ is that they comprise two distinct components: the causal variable $C$ and the non-causal variable $S$, such as the House motif and the Tree base in the GOOD-Motif dataset. Here, $C$ serves as the sole endogenous parent crucial for determining the ground-truth label $y$, while $S$ is an element that varies across different environments. When synthesizing OOD samples, we use the label variable $y$ as prior knowledge and conditions to control the diffusion procudure, detailed as follows.

Conditional Reverse-time SDE with Label Knowledge: Our approach specifically maintains the integrity of the causal part $C$ while exploring the unstable non-causal part $S$ through the application of a conditional reverse-time Stochastic Differential Equation (SDE), as presented in Eq. (6). In Eq. (6), the condition $y_G$ controls the generated graph to maintain the label knowledge (i.e., keeping causal part $C$), and the condition $y_\text{ood}$ augments the graph to explore the environment (i.e., varying non-causal part $S$). This equation has never been proposed before, and the solution balancing label preservation and enrivonment exploration is nontrivial. To model this, we propose formulating the distribution $p_t\left(\mathbf{y}_{\text {ood }}=\lambda \mid G_t, \mathbf{y}_G\right)$ as proportional to the negative exponent of the joint density of $G_t$ and $\mathbf{y}_G, p_t\left(G_t, \mathbf{y}_G\right)$. This derives the expression for the gradient of the log probability for conditional reverse diffusion, as presented in Eq. (9). Eq. (9) is featured with the following properties:

Preserving the Label Knowledge by $y_G$: The second term $\log p_t\left(\mathbf{y}_G \mid G_t\right)$ aims to maximize the prediction probability of the graph's ground-truth label $y_G$ for each step. This essentially maintians the prior label knowledge when synthesizing the OOD samples.

Exploring the Training Distribution by $y_\text{ood}$: Combining two terms, the conditional score function creates a marginal distribution proportional to $p_t\left(G_t, \mathbf{y}_G\right)^{1-\sqrt{\lambda}}$.

When environmental graphs are explored, their patterns exist in the low-density regions of the original distribution. Conversely, un-explored graphs exist in high-density regions. With exploration strength $\lambda=0$, the marginal distribution becomes $p_t\left(G_t, \mathbf{y}_G\right)$,

which denoises the synthesized graphs from the augmented distribution to follow the original distribution $P_{\operatorname{tr}}(G, Y)$, thus both casual part $C$ and non-casaul part are preserved. By adjusting $\lambda$, we regulate dispersion, allowing generated graphs to maintain the causal $C$ and explore non-causal $S$, thus increasing the divergence between $P_{\mathrm{tr}}\left(G, Y \mid \mathbf{y}_{\text {ood }}=\lambda\right)$

and $P_{\mathrm{tr}}(G, Y)$.

Thus, our formulation achieves a tractable conditional reverse-time SDE. This advancement not only simplifies the generating OOD graphs by converting it into a conditional generation problem, but also presents a novel application of reverse-time SDE techniques in this context of graph covariate shifts.

References:

[1] Thompson, et al. On Evaluation Metrics for Graph Generative Models. https://arxiv.org/abs/2201.09871

[2] Chen, et al. D4Explainer: In-Distribution GNN Explanations via Discrete Denoising Diffusion. https://arxiv.org/abs/2310.19321

[3] Preuer, et al. Fréchet ChemNet Distance: A metric for generative models for molecules in drug discovery. https://arxiv.org/abs/1803.09518

[4] Sui, et al. Unleashing the Power of Graph Data Augmentation on Covariate Distribution Shift. https://arxiv.org/abs/2211.02843

[5] Wu, et al. Discovering invariant rationales for graph neural networks. https://arxiv.org/abs/2201.12872

W3: Experimental comparisons may not be fair, as prior works use GNN as backbone and OODA uses graph transformer. What are the time and space complexity?

Fair comparison using GNN backbone: Thank you for bringing attention to clarify the experimental setups. We would like to highlight that in our work, we trained graph transformers only to compute the conditional reverse-time SDE, and after using the trained diffusion model to generate augmented graphs, we still follow prior works to use the same GNN architecture as backbones for the graph classification task, as elaborated in Appendix A.4.2.

Time and memory complexity: Our pipeline consists of two stages: data augmentation, and trainng of the GNN classifier on augmented graphs. The second stage of classification follows general GNN training setup, without introducing additional complexity: the time/memory complexity per layer of using Graph Isomorphism Networks (GIN) as backbone is $\Theta(n + e)$, where $n$ is the number of nodes and $e$ is the number of edges. For the data augmentation stage, we introduce graph transformer whose memory and time complexity per layer is $\Theta(n^2)$. This arises from the computation of attention scores and predictions across each edge.

W4: 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.

We apologize for the confusion. The goal of this experiment (Figure 3), along with the experiment for Figure 2, is to demonstrate whether our graph generator achieves the two desired properties: preserving stable patterns (i.e., the generated graph preserves its ground-truth label), and exploring environment patterns (i.e., the generated distribution is distant from training distribution). Since the graph transformer is to model $p_t\left(\mathbf{y}_G \mid G_t\right)$ in the augmentation stage, it is more reasonable to directly use its accuracy to verify the label information is effectively captured in the reverse-time SDE procedure.

W5: How different values of $\lambda$ affect the graph diversity and model performance?

We have conducted a comprehensive visualization of the generated OOD graphs under various $\lambda$ values, as depicted in Table 3. This table illustrates that increasing $\lambda$ systematically alters the structures of the base graphs, while the core motifs remain consistently preserved. This indicates that $\lambda$ plays a crucial role in modulating structural modifications without compromising key patterns.

The choice of $\lambda$ is informed by its evaluated performance on OOD validation sets across a range of datasets, as detailed in Appendix A.4.2. Below are additional ablation results to showcase the impact of different $\lambda$ values on model performance:

Thank you for your insightful comments and requests for clarifications. We now try to address your concern below:

W1: Quantify the diversity of the generated graphs.

Thank you for highlighting the importance of assessing the diversity of the generated graphs. We appreciate the opportunity to clarify our approach and provide additional details to address this key component of our work.

MMD as a quantitative diversity metric: In [1], comprehensive experiments were conducted to rigorously evaluate and benchmark metrics for assessing the diversity of generated graphs. In its Section 4.2, it highlights the correlation between random Graph Isomorphism Networks (GIN)-based Maximum Mean Discrepancy (MMD) with RBF kernel and the diversity of generated graphs, demonstrating the rationale of why MMD can serve as a reasonable diversity metric. Consequently, we employ this metric to assess the discrepancy between augmented and training distributions. As illustrated in Figures 2 and 5, MMD with the RBF kernel increases as $\lambda$ grows, indicating an enhanced diversity as the exploration strength increases. Additionally, we provide examples of the generated OOD graphs in Table 3, offering further qualitative evidence of their diversity. Similarly, Figure 8 in [2] employs visualization to further evaluate and substantiate the diversity of the generated graphs.

FCD as a diversity metric for molecules: As demonstrated in [3], the Fréchet ChemNet Distance (FCD) metric incorporates chemically and biologically relevant information about molecules and assesses the diversity of generated sets through their distribution. Consequently, we utilize FCD to evaluate the discrepancy between augmented and training molecules. As illustrated in Figure 4, FCD increases with higher values of $\lambda$, also matching the previous conclusion under MMD metric.

In addition to these two metrics, we are more than happy to include more if the reviewer have suggestions on any specific diversity metrics.

W2: The framework’s effectiveness in addressing size shifts is unclear.

As detailed in Appendix A.4.2, we have employed a flexible approach to account for size variations across different datasets. Specifically, for GOOD-SST2-length and GOOD-Motif-size, where $\lambda = 0.01$ corresponds to an increase of one node, we employed a grid search with $\lambda \in\{0.01,0.02, \ldots, 0.14\}$ and $\lambda \in\{0.01,0.02,0.03,0.04,0.05\}$, respectively. For GOOD-HIV-size, $\lambda = 0.01$ represents a decrease of ten nodes, utilizing the same $\lambda$ values as GOOD-Motif-size. This method allows generated subgraphs to vary in node count, rather than being constrained to match the original subgraph sizes.

Our model demonstrated a $10.89\%$ performance improvement on the GOOD-HIV-size benchmark over empirical risk minimization (ERM). Additionally, it achieved a $17.53\%$ performance improvement on the GOOD-Motif-size dataset. Therefore, the model performs effectively across both the GOOD-HIV-size and GOODMotif-size datasets. This indicates its robust generalization capacity in handling size shifts effectively.

OODA is expressly crafted to tackle not only shifts in graph structures but also variations in node and edge features. This multi-faceted capability allows OODA to effectively handle covariate shifts across both feature and structural distributions simultaneously. In comparison, its performance is analogous to the state-of-the-art method AIA [4] (NeurIPS 2023) on synthetic datasets like GOOD-Motif. While AIA improved upon the SOTA method VREx by $3.04\%$ on the GOOD-Motif-base dataset, OODA outperformed AIA by $2.19\%$. This reflects a competitive enhancement, demonstrating that both methods achieve comparable progress, yet with differing strengths in specific contexts.

W3 & Q3: The ablation studies are limited.

Thank you for your insightful question regarding the hyperparameter and generated graph examples in the ablation studies.

Sensitivity of hyperparameter $\lambda$: We understand the importance of hyperparameter selection and its impact on model performance. As detailed in Appendix A.4.2, we determine the value of $\lambda$ by evaluating its effectiveness on OOD validation sets across various datasets. Below are the ablation results that illustrate the sensitivity of our method to different $\lambda$ values:

More realistic graph examples: The reason we demonstrate generated graphs for the synthetic data GOOD-Motif-base is that the ground-truth casual part is known and intuitive to verify. In addition to the GOOD-Motif-base graphs, we are currently compiling and visualizing a diverse set of graph examples for other datasets in an intuitive way, and will include them in the final version of the paper once available.

Q4: Can we use the generated graphs to improve the performance of other graph OOD methods?

Thank you for your insightful question about the potential of our OOD generation method. We have explored this application by incorporating our generated graphs with one of the state-of-the-art method, AIA [7]: applying AIA upon the augmented graph set produced by our method. Our preliminary results indicate that integrating our generated graphs with existing methodologies can indeed lead to measurable performance improvements.

These initial findings demonstrate that our approach has the potential to complement and enhance the effectiveness of other established graph OOD methods like AIA. By leveraging the diversity and novelty of the graphs produced by our model, we can offer an enriched training data set that strengthens the robustness and generalization capabilities of these methods.

References:

[1] Du, et al. Implicit Generation and Modeling with Energy-Based Models. https://arxiv.org/abs/1903.08689

[2] Grathwohl, et al. Your Classifier is Secretly an Energy Based Model and You Should Treat it Like One. https://arxiv.org/abs/1912.03263

[3] Wu, et al. Energy-based Out-of-Distribution Detection for Graph Neural Networks. https://arxiv.org/abs/2302.02914

[4] Bazhenov, et al. Towards OOD Detection in Graph Classification from Uncertainty Estimation Perspective. https://arxiv.org/abs/2206.10691

[5] Wu, et al. Discovering invariant rationales for graph neural networks. https://arxiv.org/abs/2201.12872

[6] Liu, et al. Data-Centric Learning from Unlabeled Graphs with Diffusion Model. https://arxiv.org/abs/2303.10108

[7] Sui, et al. Unleashing the Power of Graph Data Augmentation on Covariate Distribution Shift. https://arxiv.org/abs/2211.02843

Thank you for your constructive comments and requests for clarifications. We respond to your concerns below:

W1 & Q1: To what extend the proposed strategy could preserve the stable features.

We appreciate the detailed questions to clarify the design of our method.

How the classifier is trained: First, the classifier is trained using noisy graphs (i.e., $G_t$) sampled at random time steps to model $p_t\left(\mathbf{y}_G \mid G_t\right)$. During this process, we split the OOD training data into separate training and validation sets, selecting the classifier that exhibits the best performance on the validation set. Note that neither the OOD validation set nor the OOD test set is utilized during this training phase. Figure 3 demonstrates the predictive probability of the classifier on the ground-truth label, and a consistant high value (>0.95) highlights the ability of the proposed strategy in preserving the stable label information.

Can the classifier itself already be used for tackling covariate shifts: Although the classifier is instrumental in modeling $p_t\left(\mathbf{y}_G \mid G_t\right)$, it is not employed to directly address covariate shifts of $p_0\left(\mathbf{y}_G \mid G_0\right)$, where $G_0$ represents the clean graph. The classifier's training on noisy graphs aims to capture the underlying feature dynamics under distorted conditions, without presupposing reliability in tackling covariate shift scenarios independently. To further illustrate that the classifier alone cannot effectively tackle covariate shifts, we present its performance on OOD test data. The results indicate that the classifier's performance is lower than that achieved by empirical risk minimization (ERM), confirming its limitations in addressing covariate shifts as it is not designed to do so.

Why $y_\text{ood}$ could specify the amount of OOD exploration: Our approach utilizes the understanding that OOD samples are characterized by low likelihood, as demonstrated in [1, 2, 3, 4]. Following this principle, we model the distribution $p_t\left(\mathbf{y}_{\text {ood }}=\lambda \mid G_t, \mathbf{y}_G\right)$ to be inversely proportional to the joint density of $G_t$ and $\mathbf{y}_G$, denoted as:

$p_t\left(\mathbf{y}_{\text {ood }}=\lambda \mid G_t, \mathbf{y}_G\right) \propto p_t\left(G_t, \mathbf{y}_G\right)^{-\sqrt{\lambda}}=p_t\left(G_t\right)^{-\sqrt{\lambda}} p_t\left(\mathbf{y}_G \mid G_t\right)^{-\sqrt{\lambda}}.$

Intuitively, as $\lambda$ approaches 1, this distribution sharpens, with the negative exponent accentuating conditions indicative of OOD instances. This characteristic allows $\lambda$ to calibrate the extent of OOD exploration by amplifying the emphasis on regions in the distribution where the probability values are inherently smaller, effectively modeling the OOD phenomena.

We hope these clarifications address your concerns, and we are open to further discussion and questions regarding our approach.

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

We respectfully argue that our approach offers more than a simple modification of diffusion models on graphs. As demonstrated in Section 4, we derive a novel and desired conditional reverse-time Stochastic Differential Equation (SDE), as presented in Eq. (6). Eq. (6) has never been proposed before, and the solution balancing label preservation and enrivonment exploration is nontrivial. To model this, we propose formulating the distribution $p_t\left(\mathbf{y}_{\text {ood }}=\lambda \mid G_t, \mathbf{y}_G\right)$ as proportional to the negative exponent of the joint density of $G_t$ and $\mathbf{y}_G, p_t\left(G_t, \mathbf{y}_G\right)$. This derives the expression for the gradient of the log probability for conditional reverse diffusion, as presented in Eq. (9). In Eq. (9), when $\lambda$ increases from 0, the augmented distribution becomes broader compared to the original data distribution $P\left(G \mid \mathbf{y}_G\right)$. Consequently, the generated samples are more likely to originate from the out-of-distribution context of $P\left(G \mid \mathbf{y}_G\right)$.

Thus, our formulation achieves a tractable conditional reverse-time SDE. This advancement not only simplifies the generating OOD graphs by converting it into a conditional generation problem, but also presents a novel application of reverse-time SDE techniques in this context of graph covariate shifts.

Thank you for your insightful comments and requests for clarifications. We will try addressing your concern below:

W1: Question on motivation: why the diffusion processes can synthesize OOD samples without enough prior knowledge of the OOD.

We appreciaite the question to help clarify how our conditional reverse-time SDE can maintain prior label knowledge and explore OOD environment simultaneously.

Prior Knowledge of Out-of-Distribution (OOD) Samples: As outlined in [1], our prior knowledge about the out-of-distribution aspect of input graphs $G$ is that they comprise two distinct components: the causal variable $C$ and the non-causal variable $S$, such as the House motif and the Tree base in the GOOD-Motif dataset. Here, $C$ serves as the sole endogenous parent crucial for determining the ground-truth label $y$, while $S$ is an element that varies across different environments. When synthesizing OOD samples, we use the label variable $y$ as prior knowledge and conditions to control the diffusion procudure, detailed as follows.

Conditional Reverse-time SDE with Label Knowledge: Our approach specifically maintains the integrity of the causal part $C$ while exploring the unstable non-causal part $S$ through the application of a conditional reverse-time Stochastic Differential Equation (SDE), as presented in Eq. (6). The condition $y_G$ controls the generated graph to maintain the label knowledge (i.e., keeping causal part $C$), and the condition $y_\text{ood}$ augments the graph to explore the environment (i.e., varying non-causal part $S$). The derivation in our paper illustrates that the gradient of the log probability for this conditional reverse diffusion is expressed in Eq. (9).

which is featured with the following properties:

Preserving the Label Knowledge by $y_G$: The second term $\log p_t\left(\mathbf{y}_G \mid G_t\right)$ aims to maximize the prediction probability of the graph's ground-truth label $y_G$ for each step. This essentially maintians the prior label knowledge when synthesizing the OOD samples.

Exploring the Training Distribution by $y_\text{ood}$: Combining two terms, the conditional score function creates a marginal distribution proportional to $p_t\left(G_t, \mathbf{y}_G\right)^{1-\sqrt{\lambda}}$.

When environmental graphs are explored, their patterns exist in the low-density regions of the original distribution. Conversely, un-explored graphs exist in high-density regions. With exploration strength $\lambda=0$, the marginal distribution becomes $p_t\left(G_t, \mathbf{y}_G\right)$,

which denoises the synthesized graphs from the augmented distribution to follow the original distribution $P_{\operatorname{tr}}(G, Y)$, thus both casual part $C$ and non-casaul part are preserved. By adjusting $\lambda$, we regulate dispersion, allowing generated graphs to maintain the causal $C$ and explore non-causal $S$, thus increasing the divergence between $P_{\mathrm{tr}}\left(G, Y \mid \mathbf{y}_{\text {ood }}=\lambda\right)$

and $P_{\mathrm{tr}}(G, Y)$.

Balancing Label Preservation and Environment Exploration: As demonstrated in [2], exploration must remain within a meaningful deviation range from the original distribution to avoid disrupting the causal component $C$. Hence, $\lambda$ must be carefully selected based on performance metrics from OOD validation sets across various datasets.

W2: Discussion on selecting hyperparameter $\lambda$ across different datasets, impacting reproducibility and usability.

A2: We determine the value of $\lambda$ by evaluating its performance on OOD validation sets across different datasets, as detailed in Appendix A.4.2. This section provides a comprehensive discussion on our selection criteria, which ensures that the chosen $\lambda$ optimizes model performance while maintaining generalizability. Additionally, we explore the impact of varying $\lambda$ on navigating the space of the original distribution, as illustrated in Figures 2, 4, and 5. These figures demonstrate how different $\lambda$ values influence both the preservation and exploration of distributional shifts, thereby providing insights into its role in our methodology. This thorough analysis enhances the reproducibility and applicability of our approach across diverse datasets.