Diversifying Spurious Subgraphs for Graph Out-of-Distribution Generalization

How does iSSD surpasses existing method in terms of capturing spurious/variant subgraphs?

• To clarify, we provide a novel perspective and approach of removing spurious edges while preserving $G_c$. Specifically, previous methods attempt to directly identify $G_c$ to enhance OOD generalization ability, but this approach can be error-prone, especially when some spurious edges are highly correlated with the targets and exhibit high probability. In contrast, our ranking-based approach prunes a subset of spurious edges, therefore ensure $G_c$ can be correctly preserved, which is at the cost of including a portion of high-probability spurious edges that are challenging to be get rid of.
• Previous methods often rely on deterministic graph composition strategies to combine estimated invariant and spurious subgraphs, which can limit the diversity of the generated graphs. To address this, we diversify the spurious edges for the generation of spurious subgraphs and producing diverse spurious patterns. Our method promotes diversity while ensuring the preservation of $G_c$, thus facilitates the model’s ability to extrapolate to unseen environments effectively.

W2: Novelty of the method.

Responses: Thank you for your insightful comments, we would like to clarify the main differences between our method and the mentioned previous methods as follows.

Comparison to EERM

• EERM indeed employs multiple auxiliary context generators to mimic diverse training environments from the training data. However, these generators may still suffer from strong spurious correlations and generate inaccurate environments due to their objective of maximizing the variance loss with model-feedback, which is somewhat similar to AIA.
• In contrast, our approach directly randomizes the lowest $K\\%$ edges for environment extrapolation. By relying on a ranking-based approach, the issues caused by spurious correlations can be mitigated through an appropriate choice of $K$.
• Additionally, since EERM primarily focuses on node-level OOD generalization, and given the unique challenges and differing task characteristics, we primarily compare our method with graph-level invariant learning and data augmentation methods, such as AIA, which also aims to learn diverse environments using an adversarial augmentation generator.

Comparison to DIR

In Section 5, we provide a detailed discussion on how our approach differs from prior studies, despite the use of a learnable data transformation module.

• In brief, although the concept of a learnable data transformation is not novel and is not our contribution, our work identifies potential limitations in terms of the quality of augmented graph in previous studies which adopt the graph composition strategies with restrictive form (see Appendix G for details).
• Motivated by this observation, we introduce a new perspective on how to mitigate these limitations for more effective environment extrapolation.
• Concretely, our method discards any graph composition strategy with restrictive form, and introduce spurious subgraph diversification with a graph size constraint.
• Our method significantly simplifies the process compared to previous approaches while maximally extrapolate to novel environments, therefore enhancing the OOD generalization ability.

W3: Minor typos

Responses: Thank you for your careful review. We have thoroughly proofread the draft and corrected the identified typos, with changes highlighted in blue.

We sincerely thank you for your careful review and approval of the effectiveness and theoretical analysis. We hope we have addressed your concerns on the novelty and soundness of our approach.

References

[1] Wu, et al., Discovering invariant rationales for graph neural networks, ICLR 2022.

[2] Chen, et al., Learning causally invariant representations for out-of-distribution generalization on graphs, NeurIPS 2022.

[3] Li, et al., Learning invariant graph representations for outof-distribution generalization, NeurIPS 2022.

[4] Liu, et al., Graph rationalization with environment-based augmentations. KDD2022.

[5] Sui, et al., Unleashing the Power of Graph Data Augmentation on Covariate Distribution Shift. NeurIPS 2023.

[6] Gui, et al., Joint Learning of Label and Environment Causal Independence for Graph Out-of-Distribution Generalization. NeurIPS 2023.

We sincerely thank your valuable feedback and constructive suggestions! We are encouraged that you acknowledged the problem importance, detailed theoretical analysis and comprehensive experiments. Please see below for our responses to your comments and concerns.

W1: 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".

Responses: Thank you for your insightful comments!

Some spurious edges have strong correlations with the labels for the model to exploit, and thus for these edges model has high predicted probabilities.

• We agree with the reviewer that such cases exist in some scenarios, and some spurious edges may indeed exhibit high predicted probabilities. However, we respectively claim that in such cases our method can still accurately identify (a subset of) the spurious edges, due to the following main reasons.

  • First, our method is ranking-based. Therefore, even if a few spurious edges have stronger correlation with the labels and exhibit high probabilities, utilizing the bottom K% edges with the lowest prediction probability can still identify a subset of spurious edges. Moreover, as edges in $G_c$ tend to also exhibit high probabilities (Prop.2), the bottom K% edges won't include edges in $G_c$ with high probability given a suitable $K$.
  • Second, the theoretical guarantee in Proposition 2 only requires the mutual information $I(G_C; Y)$ is greater than $I(G_S; Y)$, in which both measures are defined on the population-level, not edges-level. That is, Proposition 2 holds as long as most of (rather than all) the invariant edges have stronger correlations with the labels compared to the spurious edges.

• To verify the effectiveness of our method for capturing spurious edges while preversing edges in $G_c$ when some spurious edges have strong correlations, we have included more experiments on the GOODMotif datasets, with the following discussions.

  • For the Motif-base dataset, where no strong correlation exists in $G_s$, iSSD achieves superior performance, comparable to in-distribution ERM performance.
  • However, for the Motif-size dataset, the increased topological complexity in $G_s$ results in some spurious substructures having strong correlations with the targets. Consequently, as the reviewer pointed out, our method cannot capture all spurious edges. Nevertheless, we can still identify a subset of these edges, which explains why our method can still achieve ~66% accuracy in this more challenging scenario, outperforming all other baselines.
  • To verify the capability of capturing spurious edges while preserving stable edges, we added more experimental results on Recall and Precision for the GOODMotif datasets on $K\\%$ lowest probability edges predicted by $t(\cdot)$.

Table: Recall and Precision for the Motif-base dataset

Table: Recall and Precision for the Motif-size dataset

As illustrated, on the more challenging Motif-size dataset, our method can stably identify a subset of spurious edges with precision higher than $90\\%$ even with bottom $50\\%$ edges. Moreover, our method outperforms other baseline methods by a large margin even when only a subset of spurious edges is identified.

Dear Reviewer Jzm8,

As the discussion deadline approaches, we are wondering whether our responses have properly addressed your concerns regarding the soundness and novelty of our work? Your feedback would be extremely helpful to us. If you have further comments or questions, we hope for the opportunity to respond to them.

Many thanks,

Authors

Once again, we are grateful for your time and effort for reviewing our paper. Since the discussion period will end in a few days, we are very eager to get your feedback on our response. We understand that you are very busy, but we would highly appreciate it if you could take into account our response and reconsider your evaluation if some concerns are addressed. Thank you!

Authors

We sincerely thank you for your valuable feedback and constructive suggestions. We are encouraged that you acknowledged we propose a novel idea to tackle OOD graph generalization, with sufficient empirical analysis to justify their design choices and insights to support theoretical claims. Please see below for our responses to your comments and concerns.

W1: Limited data diversity

Responses: Thank you for the great suggestion! We have added the GOOD-CMNIST and Graph-Twitter datasets, which come from different application domains to enhance data diversity.

• GOOD-CMNIST: This dataset is based on a modified version of the classic MNIST dataset, where digits are represented as graphs with nodes and edges. We adopt the covariate shift setting for this dataset.

• Graph-Twitter: This dataset converts sentiment sentence classification datasets SST-Twitter into graphs, the split is based on degree shift.

The results are presented below:

Table: Experimental results on the GOOD-CMNIST and Graph-Twitter datasets

As demonstrated, iSSD also achieves superior performance in application domains beyond molecular applications, this hightlight the broad applicability of our proposed method.

We have added these additional results in Appendix H.3 in our revised draft to improve our paper quality.

Q1: performance drop and rise with different $\eta$ and $K$

Responses: This is a great observation! We reran the experiments on the Motif-Base dataset with different random seeds. For $K=70$ and $\eta=0.85$, the accuracy reached an average of around 86% over 3 runs and around $72\%$ for $\eta=0.75$. So it may be caused by the random initialization. Since the model need to sort based on the lowest probability edges and then diversify on these edges, the randomness can introduce some uncertainty, thereby affecting the final results. However, as a general guideline, selecting an $\eta$ that is not too small, such as 0.75 or 0.85, and choosing penalty weights for $\mathcal{L}_{div}$ that are not too large, such as 1e-2 or 1e-3 is usually good for various datasets.

Q2: Reason that $\mathcal{L}\_{div}$ and $\mathcal{L}\_{e}$ cause high variance

Responses: Please see our response below:

• As $\mathcal{L}\_{div}$ maximally randomizes the spurious subgraphs by setting the edge probability to $0.5$, it generates a variety of novel spurious patterns for environment extrapolation. However, this approach also introduces substantial randomness by diversifying the spurious subgraphs, which can lead to higher variance.
• Regarding $\mathcal{L}\_{e}$, without the diversification, the model struggles to extrapolate effectively to unseen environments. Consequently, in test datasets with novel environments, the model may inadvertently prune edges in $G_c$, leading to performance instability.

When iSSD combines $\mathcal{L}\_{div}$ and $\mathcal{L}\_{e}$, the model can effectively prune spurious edges, and extrapolate to unseen environments, therefore reducing variance on test dataset. One such example is Motif-base dataset, where the spurious edges are removed, while causal edges are preversed, therefore the variance is very small. In contrast, for Motif-size dataset, as there exists some edges in $G_s$ cannot be pruned due to the large size and topological complexity, which leads to high variance in this dataset.

Q3: Rationale for using ERM pretraining and associated ablation study.

Responses: Thank you for this insightful question. The reason for using ERM pretraining to train the GNN encoder is to allow the encoder to first learn useful representations before incorporating $L_e$ and $L_{div}$ to train $t(\cdot)$. Intuitively, this facilitates the optimization of $t(\cdot)$. Similarly, CIGA also adopts ERM pretraining, and GSAT gradually decays $r$ (the prior for the edge distribution) from 0.9 to a fixed value, which is conceptually similar to ERM pretraining.

While other baseline methods do not explicitly use ERM pretraining, they incorporate techniques unique to their methods to achieve better performance. For example, AIA employs CosineAnnealingLR as the learning rate scheduler and only evaluates on the test set after certain epochs (e.g., after 70 epochs). Similarly, GREA also adopts CosineAnnealingLR and trains for up to 400 epochs, as reported in their papers.

To further analyze the impact of ERM pretraining, we added an ablation study across 5 datasets without using ERM pretraining. The results are presented in the following table:

Table: Ablation study on ERM pretraining

As we can see from the results, incorporating ERM pretraining improves OOD performance in most cases. However, for larger datasets such as GOODHIV-size, the improvement is less significant and may not be as helpful.

We have added these additional results in Appendix H.3 in our revised draft and highlight it in blue.

Q4: Performance on datasets with concept shift.

Responses: Intuitively, diversifying spurious subgraphs helps weaken the spurious correlations in the training data, thereby facilitating OOD generalization. To address the reviewer's concern, we have added experiments on 3 datasets with concept shift, as demonstrated in the following table:

Table: Experimental results on addressing concept shift

The results of ERM,IRM and VRex for GOODHIV-size are obtained from [1]. As shown in the table, our method achieves the best test performance, indicating that iSSD effectively handles concept shift through spurious subgraph diversification combined with graph size constraints.

We have added these additional results in Appendix H.3 in our revised draft and highlighted it in blue.

Q5: How restrictive is $\mathcal{L}_e$, and the edge distribution from $t(G)$.

Responses: $\mathcal{L}_e$ is primarily used to encourage $t(\cdot)$ to induce sparsity in terms of the total number of edges. In practice, our hyperparameter analysis on the Motif-base dataset (Figure 2) and OGBG-Molbbbp dataset (Figure 6) indicates that the penalty for $L_e$ should be relatively large (e.g., 10 or 40) to achieve optimal performance.

To address the reviewer's question regarding the edge distribution sampled from $t(G)$, we further analyzed the distribution of edges on the GOOD-Motif dataset. We have the following observations:

• In the Motif-base dataset, most spurious edges are driven down to near zero probability, while all causal edges in $G_c$ exhibit high probabilities as predicted by $t(\cdot)$. This explains why iSSD performs almost identically to in-distribution ERM on the Motif-base dataset.
• In the Motif-size dataset, the problem is more challenging because $G_s$ is significantly larger than $G_c$, and the topology of $G_s$ is more complex compared to Motif-base. As a result, many substructures within $G_s$ may resemble those in $G_c$. While $t(G)$ predicts high probabilities for most causal edges in Motif-size dataset, some spurious edges also have high probabilities of being sampled by $t(G)$, which negatively impacts OOD performance. Nevertheless, while most OOD methods perform similarly to ERM, iSSD significantly outperforms ERM and state-of-the-art OOD methods by a large margin in Motif-size dataset.

We also provide 2 examples from each dataset to offer a more intuitive understanding of these observations as follows:

The first tensor indicates the edge probability predicted by t(G), the second tensor is the ground-truth for the edges.

For Motif-base dataset,

# graph-1

tensor([2.27e-18, 3.79e-03, 2.27e-18, 1.49e-23, 1.49e-23, 1.49e-23,
 1.49e-23, 1.49e-23, 1.49e-23, 7.72e-27, 7.72e-27, 1.73e-36,
 1.73e-36, 3.79e-03, 9.99e-01, 9.99e-01, 9.99e-01, 4.80e-01,
 4.80e-01, 4.80e-01, 4.80e-01, 9.99e-01, 4.80e-01, 4.80e-01,
 4.80e-01, 4.80e-01] )
tensor([False,  True, False, False, False, False, False, False, False, False,
        False, False, False,  True,  True,  True,  True,  True,  True,  True,
         True,  True,  True,  True,  True,  True])

# graph-2

tensor([1.73e-36, 1.73e-36, 1.17e-21, 1.17e-21, 9.38e-05, 9.38e-05,
    9.38e-05, 1.00e+00, 9.38e-05, 2.27e-18, 2.27e-18, 1.49e-23,
    1.49e-23, 1.49e-23, 1.49e-23, 1.49e-23, 1.49e-23, 1.49e-23,
    1.49e-23, 7.72e-27, 7.72e-27, 1.73e-36, 1.73e-36, 1.00e+00,
    1.00e+00, 1.00e+00, 1.00e+00, 3.79e-03, 1.00e+00, 3.79e-03,
    3.32e-13, 3.32e-13, 3.79e-03, 1.00e+00, 1.00e+00, 3.79e-03])
tensor([False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False,  True,  True,  True,  True,  True,  True,
         True,  True,  True,  True,  True,  True])

# graph-2

tensor([2.5662e-07, 2.5662e-07, 9.7500e-03, 9.7500e-03, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.9852e-01, 4.9852e-01, 9.8725e-01, 9.8725e-01, 9.8725e-01, 1.0000e+00,
        1.0000e+00, 9.8725e-01, 4.9852e-01, 4.9852e-01, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.9852e-01, 4.9852e-01, 9.6026e-01, 9.6026e-01, 9.6026e-01, 1.0000e+00,
        9.6026e-01, 4.9852e-01, 4.9852e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.9852e-01, 4.9852e-01, 9.6378e-01,
        1.0000e+00, 9.6378e-01, 9.6378e-01, 9.6378e-01, 4.9852e-01, 4.9852e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.9852e-01, 4.9852e-01, 9.6026e-01, 9.6026e-01, 9.6026e-01, 1.0000e+00,
        9.6026e-01, 4.9852e-01, 4.9852e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01, 4.0217e-01,
        4.0217e-01, 9.7500e-03, 9.7500e-03, 2.5662e-07, 2.5662e-07, 1.0000e+00,
        9.9999e-01, 1.0000e+00, 9.9999e-01, 9.9961e-01, 1.0000e+00, 9.9961e-01,
        9.9961e-01, 9.9961e-01, 9.9999e-01, 1.0000e+00, 1.0000e+00, 9.9999e-01])
        
tensor([False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
         True,  True,  True,  True, False,  True,  True,  True,  True, False,
         True,  True])

We are grateful for your positive evaluation of our well-motivated design choice, presentation, novelty, and effectiveness. We hope our responses address your concerns. We appreciate your support and we are happy to engage further if there are any further questions!

Reference

[1] Gui, et al., GOOD: A Graph Out-of-Distribution Benchmark, NeurIPS2022.

For Motif-size dataset,

# graph-1

tensor([9.99e-01, 9.99e-01, 9.99e-01, 1.00e+00, 1.00e+00, 9.99e-01,
        1.00e+00, 1.00e+00, 1.00e+00, 1.00e+00, 1.00e+00, 1.00e+00,
        1.00e+00, 1.00e+00, 1.00e+00, 1.0000e+00, 1.0000e+00, 1.0000e+00,
        1.0000e+00, 1.0000e+00, 1.0000e+00, 6.2184e-02, 6.2184e-02, 1.0000e+00,
        1.1312e-02, 9.8619e-01, 1.0000e+00, 1.0000e+00, 6.2184e-02, 6.2184e-02,
        1.0000e+00, 9.9632e-01, 6.2184e-02, 1.0000e+00, 6.2184e-02, 9.9632e-01,
        1.0000e+00, 6.2184e-02, 6.2184e-02, 1.0000e+00, 9.9632e-01, 9.9632e-01,
        1.0000e+00, 6.2184e-02, 6.2184e-02, 6.2184e-02, 4.3103e-06, 4.3103e-06,
        6.2184e-02, 4.3103e-06, 4.3103e-06, 1.1312e-02, 2.8521e-07, 2.8521e-07,
        8.2258e-02, 9.8619e-01, 5.2499e-01, 1.8020e-02, 6.2184e-02, 4.3103e-06,
        4.3103e-06, 6.2184e-02, 4.3103e-06, 4.3103e-06, 9.9632e-01, 2.1233e-02,
        7.8001e-01, 6.2184e-02, 4.3103e-06, 4.3103e-06, 6.2184e-02, 4.3103e-06,
        4.3103e-06, 9.9632e-01, 2.1233e-02, 5.4943e-01, 6.2184e-02, 4.3103e-06,
        4.3103e-06, 6.2184e-02, 4.3103e-06, 4.3103e-06, 9.9632e-01, 2.1233e-02,
        7.8472e-01, 9.9632e-01, 7.8472e-01, 2.1233e-02, 6.2184e-02, 4.3103e-06,
        4.3103e-06, 6.2184e-02, 4.3103e-06, 4.3103e-06, 4.3103e-06, 4.3103e-06,
        4.3103e-06, 4.3103e-06, 2.8521e-07, 2.8521e-07, 5.2499e-01, 7.0776e-01,
        1.8020e-02, 4.3103e-06, 4.3103e-06, 4.3103e-06, 4.3103e-06, 2.1233e-02,
        7.8001e-01, 9.9999e-01, 4.3103e-06, 4.3103e-06, 4.3103e-06, 4.3103e-06,
        2.1233e-02, 5.4943e-01, 7.0776e-01, 4.3103e-06, 4.3103e-06, 4.3103e-06,
        4.3103e-06, 2.1233e-02, 1.0000e+00, 7.8472e-01, 8.2258e-02, 7.8472e-01,
        2.1233e-02, 4.3103e-06, 4.3103e-06, 4.3103e-06, 4.3103e-06, 9.9999e-01,
        1.0000e+00, 1.0000e+00, 1.0000e+00, 9.9961e-01, 9.9961e-01, 9.9961e-01,
        9.9961e-01, 1.0000e+00, 9.9961e-01, 9.9961e-01, 9.9961e-01, 9.9961e-01])

tensor([False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False,  True,  True,  True,  True,  True,  True,  True,  True,
         True,  True,  True,  True] )

Dear Reviewer CgQ7,

As the discussion deadline approaches, we are wondering whether our responses have properly addressed your concerns and questions? Your feedback would be extremely helpful to us. If you have further comments or questions, we hope for the opportunity to respond to them.

Many thanks,

Authors

Recently, I carefully reviewed the theoretical analysis section again and discovered some important issues. I hope the author can provide a response during the discussion stage so that I can better examine the contribution of this article.

1. Formula 15 has an error, it should be $I(f(\tilde{G});Y) = H(Y)-H(Y|f(\tilde{G})$
2. Formula 17 in the appendix is correct, but it does not correspond to Formula 2 in Theorem 3.1 in the main text. But this is actually more reasonable, as minimizing $H(Y|f(\tilde{G}))$ is equivalent to optimizing the downstream task of OOD generalization.
3. The assumption in Equation 22 is quite strong. Why is $L_s$ proportional to $|G_s|$? This assumption is central to the derivation of the generalization bound in this work and requires careful consideration.
4. In Formula 42, why is $E[X_{ij}^{'}] = 1/|G_s|$? I believe, based on the author's alignment of the edge sampling probability for the spurious subgraph to a uniform distribution ($\mathcal{L}_{div}$), it should be 1/2.
5. I also have doubts about the derivation of formula 36. Based on my step-by-step deduction, formula 35 remains correct. However, the conclusion of formula 36 should be based on a probability of $1-\delta$ that |L_c(\theta;D) - L_c(\theta; S)| \leq 2\sqrt({\frac{ln(4|\Theta|-ln\(\delta)}{2n}}).

Based on the above concerns about theoretical analysis, I have to unfortunately lower my score judgment first. I strongly encourage the theoretical contribution of this article, but enough clarify is needed. I look forward to the author's further response, so that I can revise my views on these issues.

Q5: Derivation in Eqn.36

Responses: We sincerely appreciate your constructive suggestions in helping us improve the quality of our paper. Upon carefully double-checking our proof, we found that we indeed missed the coefficient 2 before $\sqrt{\frac{\ln(4|\Theta|)-\ln (\delta)}{2 n}}$ in Eqn.36. We have corrected this issue in our updated draft, and further improved the clarity of the derivation, with the changes highlighted in blue.

To facilitate the reviewer's reading process, we provide the changed part of the revised proof below:

To upper bound Eqn.31 with probability $1-\delta$, for both terms $\left|\mathbb{E}\left[L_c(\theta ; D)\right]-L_c(\theta ; D)\right|$ and $\left|\mathbb{E}\left[L_c(\theta ; S)\right]-L_c(\theta ; S)\right|$, we set the right-hand side of Eqn.34 and Eqn.35 as $\delta/2$, that is,

Therefore, we conclude that with probability at least $1-\delta$, we have

Finally, we get:

Once again, thank you for your very careful reading, especially the appendix section - it makes for a significant improvement in the quality of our manuscript!

We are grateful for your positive evaluation of our presentation, novelty, and effectiveness. We hope our responses address your concerns. We appreciate your support and we are happy to engage further if there are any other point we missed! Thank you!

We sincerely thank you for your valuable feedback and constructive suggestions in reviewing our paper! We also appreciate your follow-up careful comments on the theoretical aspects. Please see below for our responses to your comments and concerns.

W1: Why graph size constraint loss as expected?

Responses: Thank you for your insightful question! The graph size constraint $\mathcal{L}\_e$ alone indeed cannot guarantee that the removed edges belong solely to the spurious subgraph. However, as we demonstrate in Proposition 2, when $\mathcal{L}\_e$ acts as a regularizer of Empirical Risk Minimization (ERM) and under Assumption 2, $\mathcal{L}\_e$ will effectively prune only the spurious edges. The high-level reasoning is that when $I(G_c; Y) > I(G_s; Y)$, ERM tends to retain $G_c$ to support accurate predictions, which encourages pruning of edges in $G_s$ instead.

W2: How to choose $K$ and $\eta$ appropriately.

Responses: When no prior knowledge is given, it indeed presents a challenge to choose suitable values for $K$ and $\eta$. However, through our hyperparameter sensitivity conducted on multiple real-world datasets, we observe that $K$ and $\eta$ only require searching within a limited range (e.g., $\eta \in \\{0.5, 0.75, 0.85\\}$ and $K \in \\{50, 70, 90\\}$). In addition, our hyper-parameter sensitivity analysis (Figures 2 and 6) demonstrates that our method can stably outperform the baseline methods across a variety of real-world datasets. This stability alleviates the challenge of selecting hyperparameters.

W3: Including more related work in discussion.

Responses: As suggested by the reviewer, we have added more discussion on the mentioned studies in Section 5, highlighted in blue in our revised draft.

Q1-2: Issues in Eqn.15 and Eqn.17

Responses: Thank you for the great catch! We have corrected Eqn.15 accordingly in line 908 in the revised PDF. In addition, we have updated Eqn.2 in line 154 to make it consisitent with Eqn.17, both are highlighted in blue.

Q3: Why $L_s$ is proportional to $|G_s|$?

Responses: Thank you for your insightful comments! This assumption is motivated by, and aligns closely with the empirical observations. For instance, in the SPMotif datasets: $G_s$ and $Y$ are correlated with a predefined bias $b$ in training set, and the correlation strength is equal across the validation and test datasets. Additionally, there is a graph size shift in the test dataset, where $|G_s|$ is larger than that in the training and validation sets, the test performance is significantly worse than validation performance due to the increase in $|G_s|$.

Similarly, for any dataset experiencing a graph size shift, we can observe the same trend. Therefore, we constrain the form of $L_s(\theta ; D)$ to be proportional to $|G_s|$, which is consistent with our experimental findings, i.e., as $|G_s|$ increases, the OOD performance gets worse.

Q4: Derivation in Eqn.42

Responses: Thank you very much for catching this typo in our derivation. We have corrected the proof and provided an updated version, with changes highlighted in blue starting from line 1117. We would also like to clarify that this typo does not compromise the validity of our theoretical results. To facilitate the reviewing, we present the key part of the revised proof as follows:

$\mathbb{E}[W_c] = \mathbb{E}[\sum_{e_{ij} \in G_c} X_{ij}] = \sum_{e_{ij} \in G_c} \mathbb{E}[X_{ij}] = \left|G_c\right|,$

$\mathbb{E}[W\_s^{\mathcal{P}}] = \mathbb{E}[\sum_{e_{ij} \in G_s^{\mathcal{P}}} X'\_{ij}] = \sum_{e_{ij} \in G_s^{\mathcal{P}}} \mathbb{E}[X'_{ij}] = \frac{|G_s^{\mathcal{P}}|}{2} = \frac{\eta|\mathcal{E}|-|G_c|}{2}.$

Therefore, given a suitable $\eta$ that prunes spurious edges from $G_s$, $2|G_c| \gg \eta |\mathcal{E}| -|G_c|$, i.e., $\mathbb{E}[t^*(G)]$ will be dominated by $G_c$ in terms of edge probability mass, therefore, we conclude that $G_c \approx \mathbb{E}[t^*(G)]$.

Discussion: This theoretical result also implies a trade-off between the distinguishability of $G_c$ in $t(\cdot)$ and the capability to extrapolate to new environments. Specifically, setting $p < 1/2$ in $\mathcal{L}\_{div}$ can better guide $t(G)$ to identify $G_c$, as it emphasizes the extraction of $G_c$. However, this comes at the cost of reduced diversity of the generated subgraphs, which hurts the model's OOD generalization performance in novel environments. Thus, setting $p = 1/2$ in $\mathcal{L}\_{div}$ strikes a balance between the effectiveness of identifying $G_c$ and maintaining maximal diversity for environments extrapolation.

Dear Reviewer Ww8s, thank you for your follow-up comment. We wish to address your concerns as follows:

Assumption of $L_s(\theta; \cdot)$ Proportional to $|G_s|$

• In addition to the motivations mentioned in our previous discussions, we clarify that $L_s(\theta; \cdot)$ is defined as a summation over all spurious edges in $G_s$ (as shown in Eq. 21). Therefore, we respectfully argue that assuming proportionality to $|G_s|$ is a reasonable and rational assumption.
• While the definition $L_s(\theta ; D):= c\left|G_s\right| L_c(\theta ; D)$ may seem restrictive, it maintains sufficient flexibility since $c$ can absorb other relevant factors such as the model architecture and the topological complexity of the graph. This form ensures adaptability across different datasets and models.
• Furthermore, this OOD generalization bound, inspired by Assumption 1, accurately reflects the OOD generalization performance across datasets. For example, in the Motif-base dataset, where $|G_s|$ is smaller, all methods achieve better OOD generalization performance. Conversely, in the Motif-size dataset, where $|G_s|$ constitutes a significant portion of the graph, the bound becomes looser, resulting in worse OOD performance across all methods. This demonstrates the broad applicability and validity of the proposed generalization bound.

Scaling Factor in Theorem 4.2

• We thank the reviewer’s feedback again, which allowed us to refine the scaling factor in our revision.
• The scaling factor is directly associated with the diversification strength. The factor of $2$ represents a trade-off between improved extrapolation capability and explainability, balancing these two objectives.
• This theoretical result implies that, under in-distribution settings, we can set the aligning probability to be less than $0.5$ to prioritize explainability while de-emphasizing environment extrapolation. This highlights the flexibility of our proposed framework, iSSD, to adapt to different use cases.

We hope our response resolves the reviewer’s concerns about the theoretical aspects of our work. Please do not hesitate to reach out if you have further questions. Thank you for your valuable comments!

Once again, we are grateful for your time and effort for reviewing our paper. Since the discussion period will end in a few days, we are very eager to get your feedback on our response. We understand that you are very busy, but we would highly appreciate it if you could take into account our response and reconsider your evaluation if some concerns are addressed. Thank you!

Authors

We sincerely thank you for your valuable feedback and constructive suggestions in reviewing our paper! We are encouraged that you acknowledged we propose a novel theory to identify the invariant subgraphs and spurious subgraphs with comprehensive experiments. Please see below for our responses to your comments and concerns.

W1: Assumption of multiple $G_c$

Responses: Thank you for your insightful question! We agree that in real-world graph applications, it is indeed possible for a graph to contain multiple invariant substructures that are causally related to $Y$.

Despite assuming a single $G_c$ as in most of the previous studies [1-3], we emphasize our approach can be naturally extended to the case of multiple $G_c$.

• Specifically, suppose there are $K$ invariant subgraphs, denoted as $G_{c,i}$ for $i \in [K]$. For any specific $G_{c,i}$, we can redefine the spurious subgraph $G_s'$ as $G_s' = G_s \cup \\{ G_{c,j} \mid j \neq i \\}$. Under the presence of $G_s$, our assumption $I(G_{c,i}; Y) > I(G_s'; Y)$ remains valid for any $i \in [K]$. Therefore, the assumptions and theoretical results in our work remain valid even when multiple $G_c$ exist in the datasets.
• To verify the effectiveness of our method in the presence of multiple $G_c$, we added experiments on a curated dataset based on SPMotif. In the train/valid/test datasets, two invariant substructures are attached to the spurious subgraph. The results are shown below.

Table: Experimental results on the SPMotif datasets with 2 invariant subgraphs.

The above results validate the effectiveness of our approach given the presence of multiple $G_c$.

We have added a detailed discussion and new experimental results on the multiple $G_c$ scenarios in Appendix H.3 in the revised draft, highlighted in blue.

W2: Only applicable for graph-level OOD generalization

Responses: Thank you for the insightful comment. We would like to first clarify the unique challenges and inherent differences between node-level (link-level) and graph-level OOD generalization, then discuss the potential of extending our method to tackle the node-level OOD generalization.

• Topological characteristics: Graph-level tasks treat an entire graph as a single instance, whereas node-level tasks take the entire graph as input and focus on individual nodes. As a result, node-level OOD methods often exploit topological information from the graph structure [4-5], while such information is not applicable for graph-level tasks.
• Dataset characteristics: Many graph-level OOD datasets, particularly in the molecular domain, have very limited or even no node features, relying heavily on graph structures. In contrast, node-level OOD datasets are typically rich in node features, which presents distinct challenges and opportunities.
• Different types of distribution shifts: The types of distribution shifts also differ between the two levels. For example, molecular datasets commonly exhibit scaffold shifts and size shifts, which are prevalent in graph-level tasks. In contrast, temporal shifts and domain shifts are more frequently observed in node-level OOD datasets.

Given these distinctions, methods for handling graph-level and node-level (or link-level) OOD generalization have been developed in parallel to address their respective unique challenges. As such, in this work, we focus on comparisons with graph-level invariant learning and data augmentation methods that align with the scope of our work.

Despite the different challenges, we find it is beneficial to discuss the potential for our method to adapt to node-level and link-level tasks. For instance, our approach could be extended by diversifying the $K$-hop subgraphs for each node to weaken spurious correlations. Considering the higher information density in node features for node-level and link-level tasks, we could further diversify node features as part of the augmentation strategy as an enhancement. Similarly, for node-level and link-level tasks, we could constrain the size of ego-networks and the information density of node features to improve generalization. These extensions present promising directions for our future work.

To enhance the applicability of our approach, we have added a discussion on the applicability of iSSD for node-level and link-level OOD generalization in Appendix C.

W3: Hyper-parameter selection.

Responses: Thank you for the great question! In practice, the selection of these hyper-parameters can be approached in two ways depending on the availability of domain knowledge:

• With domain knowledge: When domain knowledge is available, e.g., we know the percentage of the spurious edges among all edges, $\eta$ and $K$ can be directly set to suitable values without the need for extensive tuning.
• Without domain knowledge: We agree with the reviewer that choosing appropriate values for $\eta$ and $K$ in the absence of domain knowledge could be challenging. However, our hyper-parameter sensitivity analysis (Figures 2 and 6) demonstrates that our method can stably outperform the baseline methods across different hyperparameter settings on a variety of datasets. This stability alleviates the challenge of selecting hyperparameters.

W4: Minor issues in proofs.

Responses: Please see our response below.

The proof of Theorem 3.1

We wish to clarify that the proof of Theorem 3.1 can be found in Appendix E.1. To improve clarity, we have added: "We prove Theorem 3.1 in Appendix E.1" in line 157, and highlighted in blue.

Why $P(X_{ij}^{'})=1/|G_s|$

We appreciate the reviewer's observation regarding the issues in our proof. Specifically, $P(X_{ij}^{'})$ should be $1/2$. We have revised the relevant sections of the proof accordingly and highlighted the changes in blue, from lines 1117 to 1120. To facilitate the reviewer's reading, we provide the changed part of the revised proof below:

$\mathbb{E}[W_c] = \mathbb{E}[\sum_{e_{ij} \in G_c} X_{ij}] = \sum_{e_{ij} \in G_c} \mathbb{E}[X_{ij}] = \left|G_c\right|,$

$\mathbb{E}[W_s^{\mathcal{P}}] = \mathbb{E}[\sum_{e_{ij} \in G_s^{\mathcal{P}}} X'\_{ij}] = \sum_{e_{ij} \in G_s^{\mathcal{P}}} \mathbb{E}[X'\_{ij}] = \frac{|G_s^{\mathcal{P}}|}{2} = \frac{\eta|\mathcal{E}|-|G_c|}{2}.$

Therefore, given a suitable $\eta$ that prunes spurious edges from $G_s$, $2|G_c| \gg \eta |\mathcal{E}| -|G_c|$, i.e., $\mathbb{E}[t^*(G)]$ will be dominated by $G_c$ in terms of edge probability mass, therefore, we conclude that $G_c \approx \mathbb{E}[t^*(G)]$.

Discussion. This theoretical result also implies a trade off between the distinguishability of $G_c$ in $t(\cdot)$ and the capability for environment extrapolation. Specifically, setting $p < 1/2$ in $\mathcal{L}\_{div}$ can better guide $t(G)$ to identify $G_c$, as it emphasizes the extraction of $G_c$. However, this comes at the cost of reduced diversity in the generated subgraphs, which hurt the model's OOD generalization performance in novel environments. Thus, setting $p = 1/2$ in $\mathcal{L}\_{div}$ strikes a balance between the effectiveness of identifying $G_c$ and maintaining sufficient diversity for environment extrapolation.

Q1: Paper structure.

Responses: Thank you for the suggestion! We found your suggestion useful and have placed Def.2 before Theorem 3.1.

We sincerely thank you for your insightful questions and approval of the presentation, novelty, and effectiveness. We hope we have addressed your concerns.

References

[1] Wu, et al., Discovering invariant rationales for graph neural networks, ICLR 2022.

[2] Chen, et al., Learning causally invariant representations for out-of-distribution generalization on graphs, NeurIPS 2022.

[3] Li, et al., Learning invariant graph representations for outof-distribution generalization, NeurIPS 2022.

[4] Wu, et al., Handling Distribution Shifts on Graphs: An Invariance Perspective, ICLR2022.

[5] Wang, et al., Dissecting the Failure of Invariant Learning on Graphs, NeurIPS2024.

Thank you for the follow-up and inspiring question. Please see our response below for more evidence on why iSSD can be extended to node-level and link-level OOD cases:

• Similar Assumptions: Previous studies on node-level OOD problems often share similar assumptions to our work, as discussed in [1, 2, 3]. A key distinction is that, instead of assuming an invariant subgraph, they generally assume a $K$-hop ego-network $G_i$ (with invariant features) for each node $v_i$, which is both stable and sufficiently predictive of the target label $y$. To enhance OOD generalization performance, these methods also aim to identify invariant substructures (and node features). This shared assumption provides a solid foundation for extending iSSD to node-level and link-level OOD problems.

• Connections to Existing Work: Previous studies, such as EERM [1], also employ multiple context generators to create subgraphs by maximizing variance loss, which conceptually aligns with the idea of diversifying subgraphs. In contrast, we adopt a different approach for maximally diversifying subgraphs. This similarity supports our claim that our method holds great potential for node-level and link-level OOD tasks.

• Addressing New Node or Link Emergence: We agree with the reviewer that the emergence of new nodes or links poses additional challenges for node-level OOD. However, this inductive setting closely resembles the graph-level OOD setting, as graph-level datasets are inherently inductive (each test sample is unseen), unlike the transductive setting in traditional node-level datasets. Below, we discuss why iSSD can handle emergent nodes and links:

  • New links emerge: By diversifying edges with the lowest probabilities, and assuming that for each node $v_i$ an invariant substructure exists, our approach can diversify spurious edges similarly to the graph-level OOD setting. When new links emerge, our method remains effective in identifying critical edges, as the diversification process extrapolates to many unseen environments. This allows the model to generalize better in link-level OOD tasks.
  • New nodes emerge: Similarly, iSSD can effectively handle cases where new nodes emerge in the ego-network. By extrapolating to unseen environments, nodes that are not critical to the central node $v_i$ are likely to be excluded. For classifying new nodes, the presence of rich node features, and given that similar nodes tend to share similar invariant structures, allows our method to adapt effectively to unseen nodes by leveraging similarities with nodes in the training set.

In summary, while challenges remain, the shared assumptions and superior capability of iSSD to extrapolate to unseen environments imply that iSSD has significant potential to be adapted for node-level and link-level OOD tasks.

Please kindly let us know if our explanations above clarify your concerns. Otherwise, we would be happy to have a further discussion!

References

[1] Wu, et al., Handling Distribution Shifts on Graphs: An Invariance Perspective, ICLR2022.

[2] Gui, et al., GOOD: A Graph Out-of-Distribution Benchmark, NeurIPS2022

[3] Wang, et al., Dissecting the Failure of Invariant Learning on Graphs, NeurIPS2024

Thank you for recognizing our discussion of the multiple $G_c$ assumption. Please see our response below for more details on the curated SPMotif datasets.

More Details on SPMotif Datasets with Two $G_c$:

Vanilla SPMotif Datasets: In the vanilla SPMotif datasets, each graph is generated as follows:

1. A spurious subgraph is first generated from a set of predefined base graphs (Tree, Ladder, Wheel).
2. An invariant subgraph (House, Cycle, Crane) is then randomly selected with equal probability and attached to the spurious subgraph.

Modified SPMotif Datasets with Two $G_c$: To align with the multiple $G_c$ assumption, we modify the dataset generation process as follows:

1. A spurious subgraph is first generated from the same predefined base graphs (Tree, Ladder, Wheel).
2. One invariant subgraph pattern (House, Cycle, Crane) is randomly selected with equal probability, and 2 subgraphs of the selected pattern (e.g., Cycle) are randomly attached to the spurious subgraph at different locations.

By introducing two invariant subgraphs per graph, we can evaluate the performance of various OOD methods under the new assumption of multiple $G_c$.

We hope this clarifies the details of the SPMotif dataset generation and how it accommodates the multiple $G_c$ assumption. Please feel free to reach out if any further questions!

Dear Reviewer tUpV,

As the discussion deadline approaches, we are wondering whether our responses have properly addressed your concerns and follow-up questions? Your feedback would be extremely helpful to us. If you have further comments or questions, we hope for the opportunity to respond to them.

Many thanks,

Authors

Thank you for your response! To address your concern, we have provided the following discussions on how to adapt iSSD to node-level OOD problem, and provide a proof for it. We begin by stating the assumptions, followed by the adaptation and proof.

Assumptions for Node-Level OOD Generalization

Assumption 1: Given a graph $G$, consider the $l$-layer ego-network of a node $v_i$, denoted as $G^{(i,l)}$. Within this ego-network, there exists an invariant subgraph $G_c^{(i,l)}$ and invariant features $H_c^{(i,l)}$ stable across environments $e$ and $e'$, satisfying:

1. For any environments $e, e' \in \mathcal{E}_{tr}$,

   $$P^e(Y \mid G_c^{(i,l)}) = P^{e'}(Y \mid G_c^{(i,l)}) \quad \text{and} \quad P^e(Y \mid H_c^{(i,l)}) = P^{e'}(Y \mid H_c^{(i,l)}).$$

2. The target $Y$ can be expressed as

   $$Y = f^*(G_c^{(i,l)}, H_c^{(i,l)}) + \epsilon,$$

   where $\epsilon \perp (G^{(i,l)}, H^{(i,l)})$ represents random noise, and $\perp$ indicates statistical independence.

Assumption 2: For the $l$-layer ego-network of a node $v_i$, the mutual information between the invariant components and the target $Y$ satisfies:

1. For the subgraph, we have: $$I(G_c^{(i,l)}; Y) > I(G_s^{(i,l)}; Y).$$
2. For the node-level features, we have: $$I(H_c^{(i,l)}; Y) > I(H_s^{(i,l)}; Y).$$

These assumptions ensure that the invariant subgraph and features are both more stable and more predictive of $Y$ compared to their spurious counterparts. With the above extended assumptions for node-level or link-level OOD settings, the size constraint can be extended further to account for node features:

where:

• $\mathcal{E}^{(i,l)}$ is the edge set of the $l$-layer ego-network for node $v_i$,
• $\tilde{\mathbf{A}}_{uv}^{(i)}$ is the adjacency matrix after applying $t(\cdot)$,
• $\|H^{(i,l)}\|_1$ represents the L1 norm of the node features in the $l$-layer ego-network, added to induce sparsity,
• $\eta$ is a hyperparameter controlling the edge budget, and $\lambda$ balances the graph size and feature regularization terms.

This constraint encourages sparsity in both the structure and features of the ego-network, ensuring that spurious components are pruned while invariant features are preserved.

Next we prove that: Under Assumption 2, the size and feature constraint loss $\mathcal{L}\_e$, when acting as a regularizer for $\mathcal{L}\_{GT}$, will prune edges from the spurious subgraph $G\_s^{(i,l)}$ and features from $H_s^{(i,l)}$, while preserving $G_c^{(i,l)}$ and $H_c^{(i,l)}$.

Proof (Graph Structure):
We start by expanding the cross-entropy loss $\mathcal{L}\_{GT}$:

where $\tilde{G}^{(i,l)} \sim t(G^{(i,l)})$. Assume that $|\tilde{G}^{(i,l)}| > |G_c^{(i,l)}|$, which is controlled by the hyperparameter $\eta$. Further, assume that $\tilde{G}^{(i,l)}$ does not include the invariant subgraph $G_c^{(i,l)}$.

Let a subgraph $g$ be subtracted from $\tilde{G}^{(i,l)}$ such that $|g| = |G_c^{(i,l)}|$. Define:

and construct a new graph:

By Assumption 1, the invariant subgraph $G_c^{(i,l)}$ holds sufficient predictive power for $Y$, and by Assumption 2, $G_c^{(i,l)}$ is more informative to $Y$ than $G_s^{(i,l)}$. Thus:

As a result, $\mathcal{L}_{GT}$ will decrease when $G_c^{(i,l)}$ is included in $\tilde{G}^{(i,l)}$. Therefore, the graph size regularization term $\mathcal{L}_e$ ensures that $\tilde{G}^{(i,l)}$ contains $G_c^{(i,l)}$ and prunes edges from $G_s^{(i,l)}$.

Proof (Node Features):
Suppose the optimal feature set $\tilde{H}^{(i,l)}$ is encoded by a GNN encoder $h(\cdot)$ from the $l$-layer ego-network $G^{(i,l)}$ and does not include the invariant features $H_c^{(i,l)}$. Define a feature set:

where $|h| = |H_c^{(i,l)}|$, and construct:

Under Assumption 1, the invariant features $H_c^{(i,l)}$ retain sufficient predictive power for $Y$, and by Assumption 2 for features:

Thus, adding $H_c^{(i,l)}$ to $\tilde{H}^{(i,l)}$ will increase the certainty of predictions:

However, by definition, $\tilde{H}^{(i,l)}$ is the feature set output by the encoder $h(\cdot)$ acting on $G^{(i,l)}$. If $H_c^{(i,l)}$ were excluded, the encoded features $\tilde{H}^{(i,l)}$ would lead to reduced predictive signals for $Y$ under Assumption 2. This leads to a contradiction, as including $H_c^{(i,l)}$ would always produce a lower loss $\mathcal{L}_{GT}$, making it part of the optimal solution.

Extended Formulation for $\mathcal{L}_{\text{div}}$

To incorporate diversification for both spurious subgraphs and node features, we extend the regularization term $\mathcal{L}\_{div}$ as follows:

where:

• $\mathcal{E}\_s^{(i,l)}$ represents the set of spurious edges in the $l$-layer ego-network of node $v_i$,
• $w_{uv}$ is the normalized probability for edge $e_{uv}$,
• $\mathrm{KL}(\tilde{H}^{(i,l)}, \mathcal{U})$ is the KL-divergence between the encoded node features $\tilde{H}^{(i,l)}$ and a uniform distribution $\mathcal{U}$,
• $\lambda$ balances the contributions of graph and feature diversification.

The first term diversifies the spurious subgraph, while the second term encourages the node features $\tilde{H}^{(i,l)}$ to align with a uniform distribution, increasing uncertainty in the spurious features.

Next we prove that the KL term will diversify the spurious node features by aligning it with uniform distribution.

Proof for the Extended $\mathcal{L}\_{\text{div}}$

Objective: Maximize the mutual information (MI):

where $\eta$ is a small constant (e.g., 0.01) that ensures feature alignment with the uniform distribution does not dominate predictive accuracy.

Step 1: Expand $\tilde{H}^{(i,l)}$ into invariant and spurious components

We decompose $\tilde{H}^{(i,l)}$ as:

where $H_c^{(i,l)}$ and $H_s^{(i,l)}$ denote the invariant and spurious features, respectively.

Using the chain rule for MI:

Step 2: Simplify Using Assumptions

1. For $I(\tilde{H}^{(i,l)}; Y)$:

   • By Assumption 2, $H_c^{(i,l)}$ is highly predictive of $Y$, while $H_s^{(i,l)}$ is not.
   • Thus, $I(H_s^{(i,l)}; Y \mid H_c^{(i,l)}) = 0$, leaving: $$I(\tilde{H}^{(i,l)}; Y) = I(H_c^{(i,l)}; Y).$$

2. For $I(\tilde{H}^{(i,l)}; \mathcal{U})$:

   • Due to the regularization effect of empirical risk minimization (ERM), $H_c^{(i,l)}$ is aligned with the target $Y$ and does not resemble a uniform distribution, The KL-divergence term $\mathrm{KL}(\tilde{H}^{(i,l)}, \mathcal{U})$ encourages $H_s^{(i,l)}$ to align with the uniform distribution, maximizing $I(H_s^{(i,l)}; \mathcal{U} \mid H_c^{(i,l)})$. Thus, $I(\tilde{H}^{(i,l)}; \mathcal{U})$ is maximized due to the diversification of spurious node features $H_s^{(i,l)}$.

Step 3: Overall Objective

Substituting into the objective:

we have:

• The first term, $I(H_c^{(i,l)}; Y)$, ensures that the invariant features $H_c^{(i,l)}$ remain predictive for $Y$.
• The second term, $\eta I(H_s^{(i,l)}; \mathcal{U} \mid H_c^{(i,l)})$, guides the spurious features $H_s^{(i,l)}$ to align with the uniform distribution, reducing their influence on $Y$.

The adaptation to the node-level OOD problem shares a conceptual similarity with the graph-level OOD problem.

• In addition to diversifying spurious subgraphs, we propose two additional terms to enforce node-feature diversification and information constraints.
• Furthermore, we provide a theoretical justification for the proposed regularization on node-feature constraints. However, adapting our approach to the node-level task involves significant modifications to the workload, including the implementation and benchmarking of multiple state-of-the-art methods specifically for node-level OOD tasks across various datasets, which is beyond the current scope of this work.
• Nonetheless, the proposed adaptation is conceptually straightforward to implement and comes with theoretical guarantees.
• It is worth emphasizing that our work aligns with prior studies, which evaluate methods under graph-level OOD setting [1-5]. By benchmarking against 17 baseline methods, we believe we have sufficiently demonstrated the superiority of iSSD in addressing graph OOD challenges.

We hope this response addresses the reviewer’s concerns regarding the adaptation to node-level OOD problems and reconsiders the evaluation of our work.

References

[1] Wu, et al., Discovering invariant rationales for graph neural networks, ICLR 2022.

[2] Chen, et al., Learning causally invariant representations for out-of-distribution generalization on graphs, NeurIPS 2022.

[3] Liu, et al., Graph Rationalization with Environment-based Augmentations, KDD 2022

[4] Sui, et al., Unleashing the Power of Graph Data Augmentation on Covariate Distribution Shift. NeurIPS 2023.

[5] Gui, et al., Joint Learning of Label and Environment Causal Independence for Graph Out-of-Distribution Generalization. NeurIPS 2023.

Dear Reviewers and Area Chair,

During the rebuttal phase, We identified an typo in the manuscript from our actual code implementation. Specifically, the aligning probability (in Eqn. 10) in our final implementation is not $1/2$ as stated, but rather $1/|\mathcal{E}_s|$.

The uniform distribution applies to the entire estimated spurious subgraph, not to each individual edge. We have updated the draft to reflect this correction in Section 4 (line 255-263).

Additionally, the proof of Theorem 4.2 have been updated accordingly (line 1119-1124). Specifically, the scaling factor is now $|\mathcal{E}_s|$ instead of 2, which provides a stronger results for: $G_c \approx \mathbb{E}_G\left[t^*(G)\right]$.

Our code implementation is available at: https://anonymous.4open.science/r/TempProj-1B2A to facilitate code checking. The code implementation for $\mathcal{L}_{div}$ can be found in line 528 of modelNew/utils.py.

These updates are also highlighted in $\textcolor{blue}{\text{blue}}$ in the revised draft.

We apologize for the oversight and the late update to our draft due to this inconsistency. Thank you for your understanding and for reviewing our work.