Pruning Spurious Subgraphs for Graph Out-of-Distribtuion Generalization

Thank you for your constructive feedback! Please see below for our responses to your comments and concerns.

Q1: Novelty Issue

Response: One significant distinction between the proposed PrunE method and most existing OOD approaches lies in its learning paradigm. Specifically, PrunE focuses on pruning uninformative spurious edges, rather than directly identifying invariant subgraphs or explicitly learning invariant features, a strategy commonly employed by most prior methods such as IRM, VRex, DIR, GSAT, CIGA, and AIA. Therefore, we respectfully emphasize that PrunE differs from the majority of existing OOD methods in both its learning paradigm and the underlying OOD objectives.

We thank the reviewer for pointing out the related work LIRS which was recently accepted. While PrunE and LIRS share some conceptual commonality, their motivations and methodology differ significantly.

• Different Motivations. LIRS aims to learn a more complete set of invariant features through a representation-level approach. In contrast, PrunE is motivated by the difficulty of directly identifying invariant subgraphs. It addresses this by pruning uninformative spurious edges, which facilitates the preservation of invariant substructures.

• Technical Design. LIRS adopts a multi-stage learning paradigm that learning spurious features followed by learning invariant features. In contrast, PrunE employs a single-stage training framework with two novel OOD regularization terms that are distinct from prior work. Compared with LIRS, PrunE presents several unique advantages:

  • Single-stage training and fewer hyperparameters. LIRS involves multiple stages, with nearly 100 hyperparameter combinations in total; In contrast, PrunE demonstrates robust performance with limited set of hyperparameters (as discussed in line 183 and 212) across datasets, greatly reducing model tuning efforts.
  • Interpretability. LIRS operates in latent space and thus lacks interpretability in terms of input structures. PrunE, by operating in the input space, not only being efficient and effective, but also offers interpretability by identifying critical subgraphs that explain the model prediction.

In summary, PrunE is technically and conceptually distinct from LIRS with different motivations, and offers several unique advantages. We appreciate the reviewer’s suggestion and will include a discussion and comparison with LIRS in our revised paper.

Q2: Comparison with LIRS and hyperparameter analysis

Response: Thank you for your thoughtful question. LIRS and PrunE exhibit notable differences in performance across datasets with different features. Specifically, on the Motif-Base dataset, PrunE achieves 91.40% accuracy, significantly outperforming LIRS (75.50%). In contrast, on the Motif-Size dataset, LIRS performs better than PrunE. This also hightlights the different inductive bias between these two methods. We will add the comparison with LIRS to our revised paper.

Regarding hyperparameter sensitivity, PrunE achieves strong performance using a fixed hyperparameter setting, thereby alleviating the need for hyperparameter search. For further details, please refer to our response to Reviewer ncwH due to character limits.

Q3: Time and space complexity analysis

Response: As discussed in Appendix E, the time complexity of PrunE is $\mathcal{O}(CkmF)$, where $k$ is the number of GNN layers, $m$ is #edges, and $F$ is the feature dimension. $C>1$ accounts for the use of both the subgraph selector $t(\cdot)$.

The space complexity is $\mathcal{O}(C'|\mathcal{B}|mkF)$, where $|\mathcal{B}|$ is the batch size and $C'$ reflects the additional memory from $t(\cdot)$. The time and memory cost are both on par with ERM.

To further address the reviewer's concern, we conducted additional experiments to evaluate its runtime and memory consumption as below.

As PrunE only introduces two lightweight regularization terms on the subgraph selector, it is highly efficient in both runtime and memory consumption (3.15x faster than LIRS in Molbbbp), highlighting its advantage in computational efficiency.

We sincerely thank the reviewer for the careful review and insightful feedback. We hope that our responses have adequately addressed your concerns regarding our study.

Thank you for your thoughtful comments and positive feedback! Please see below for our responses to your comments and concerns.

Q1: The effectiveness of PrunE to assign low probabilit y weights to spurious edges

Response: Thank you for raising this crucial point. Through extensive experiments, we find that the effectiveness of identifying and pruning spurious edges rely on two critical factors:

• The size of the spurious subgraphs $G_s$.
• The complexity of topological structures of $G_s$.

As $|G_s|$ increases and the spurious structures become more intricate, the performance of all OOD methods tends to degrade. This is primarily because certain spurious substructures may exhibit strong correlations with the target labels, leading to misclassification of invariant substructures and overestimation of spurious edges.

One such example is the Motif-Base and Motif-Size datasets, where the OOD performance of most methods drops significantly in Motif-size dataset due to the increased size of $G_s$ and the more intricate spurious subgraph topology. Similar to existing methods, PrunE will fail to assign low probabilty score to some spurious edges in these scenarios.

However PrunE is also able to assign high probability scores to invariant edges in $G_c$, while previous methods that attemp to directly identify these edges tend to assign low probability to them. This ability is critical for the improved OOD generalization performance compared to prior approaches that attempt to identify invariant subgraphs directly.

How to further identify and suppress spurious edges that are strongly correlated with target labels remains a challenging problem and represents a promising direction for our future research.

Q2: Extending to node-level and edge-level OOD tasks

Response: Thank you for raising this important point. We have conducted experiments using PrunE on the Cora-Word and Cora-Degree datasets, but the performance is comparable to that of ERM. Similarly, many OOD algorithms, such as IRM, VRex, and GroupDRO, that are effective in the vision domain and graph-level OOD tasks tend to perform on par with or even worse than ERM in node-level OOD settings, as evidenced in [1].

This discrepancy may arise from fundamental differences between the two problem settings. Specifically, in node-level OOD tasks, samples (i.e., nodes) are interconnected and thus not independently and identically distributed, whereas this issue does not arise in vision or graph-level OOD datasets, where each sample is treated independently.

Due to these different characteristics, methods designed for graph-level OOD generalization and those targeting node- or edge-level OOD challenges are typically developed separately. In line with PrunE, most existing graph-specific OOD methods, such as DIR, DisC, CAL, GREA, GSAT, CIGA, and AIA, also focus soly on graph-level OOD settings.

Q3: A new perspective from optimization

Response: While our work is inspired by recent findings [2, 3] that ERM tends to learn both invariant and spurious features, we fully agree with the reviewer that analyzing the implicit bias and regularization effects from an optimization perspective in explaining why the learned solution may generalize well is a compelling direction. We thank the reviewer for highlighting this perspective and will consider it in our future research.

Q4: Theoretical claims

Response: Thank you for your careful review! As $L_c(\theta, \cdot)$ is defined as the loss computed on the invariant subgraph which remains unchanged under any distribution shift, it follows that $\mathbb{E}\left[L_c(\theta, D)\right] - \mathbb{E}\left[L\_c(\theta, S)\right] = 0$ under Assumption 1. We have added additional discussion in Appendix D.2 to further clarify this point.

Q5: Implementation of subgraph selector $t(\cdot)$

Response: We appreciate the reviewer’s careful review. The function $t(\cdot)$ is implemented as a GNN model (e.g., a 2-layer GIN) followed by an MLP that models independent edge weights $p_{ij}$, where each edge is treated as a Bernoulli random variable. We have added additional clarification regarding this implementation detail in Section 4 of the revised manuscript.

Q6: typos

Response: Than you for your careful review! We have corrected this typo in the pseudo-codes of Algorithm 1.

We sincerely thank the reviewer for the careful review and insightful feedback. We hope that our responses have adequately addressed your concerns regarding our study.

References:

1. Gui, et al., GOOD: A Graph Out-of-Distribution Benchmark, NeurIPS 2022
2. Kirichenko et al, Last Layer Re-Training is Sufficient for Robustness to Spurious Correlations. ICLR 2023
3. Chen et al., Towards Understanding Feature Learning in Out-of-Distribution Generalization. NeurIPS 2023

Thank you for your positive feedback and careful review! Please see below for our responses to your comments and concerns.

Q1: Reproducibility issue

Response: As the official policy permits only figures and tables in the anonymous link, we have requested approval from the conference to share a link to our code. We are currently awaiting the approval and we have made the code available, along with a instruction on how to use the code.

Q2: Hyperparameter sensitivity

Response: Thank you for raising this important point. While inappropriate choices of $\eta$ and $K$ can indeed lead to performance degradation, we have found that setting $K=90$, $\lambda_1=10$, $\lambda_2=1e-3$, and $\eta \in \\{0.75, 0.85\\}$ yields consistently stable performance across both synthetic and real-world datasets, as discussed in lines 183 and 212 of our paper. This demonstrates a key advantage of PrunE over most existing graph OOD methods, which typically require extensive hyperparameter tuning. We will include additional discussion on the selection of hyperparameters in the Hyperparameter Sensitivity section of the revised paper.

Q3: Testing with more expressive GNNs

Response: Thank you for this insightful question. We primarily adopted GCN and GIN, two GNN architectures with different levels of expressiveness, for the following reasons:

• Experimental convention. Prior work in graph-level OOD generalization commonly adopts GCN and GIN as backbone architectures. Similarly, widely-used graph OOD benchmark datasets, such as GOOD [1], typically follow the same practice.

• Integration with the PrunE framework. More expressive GNNs typically involve high-order message passing, however it is non-trivial to incorporate high-order message passing into PrunE, particularly in the computation of $\mathcal{L}\_{GT}$ in Eqn. (6). This loss involves computing $f(t(G))$, where $t(G)$ down-weights spurious edges while preserving invariant ones, followed by a GNN encoder operating on the reweighted graph via first-order message passing. For high-order message passing, which involves aggregating information from non-adjacent nodes, it is unclear how to prune or control message flow in a principled way, as the pruning operation in $t(\cdot)$ do not naturally apply to higher-order interactions.

• Diverse designs of more expressive GNNs. While many expressive GNNs go beyond first-order message passing, they do so in fundamentally different ways. For instance, PPGN [2] captures pairwise node interactions using outer products, while $K$-hop GNNs [3] aggregate messages over $K$-hop neighborhoods, and subgraph-based GNNs [4] extract a rooted subgraph for each node independently. These technical differences imply that a unified pruning mechanism may not apply, and different designs may require distinct treatments for integration with PrunE.

For these reasons, we adopt GCN and GIN, both of which rely on first-order message passing and can be naturally incorporated into the PrunE framework via edge reweighting. Nevertheless, we fully agree with the reviewer that integrating more expressive GNN architectures into PrunE is a promising direction for our future research.

We sincerely thank the reviewer for the careful review and insightful feedback. We hope that our responses have adequately addressed your concerns regarding our study.

References:

1. Gui, et al., GOOD: A Graph Out-of-Distribution Benchmark, NeurIPS 2022
2. Maron, et al., Provably Powerful Graph Networks, NeurIPS 2019
3. Nikolentzos, et al., k-hop Graph Neural Networks, Neural Networks
4. Zhang, et al., Nested Graph Neural Networks, NeurIPS 2021

Thank you for your positive feedback and insightful comments! Please see below for our responses to your comments and concerns.

Q1: When and why PrunE may fail

Response: Based on our empirical observations, the OOD generalization performance of PrunE, as well as other OOD methods, can be significantly influenced by: i) the size of the spurious subgraphs $G_s$ and ii) the complexity of their topological structures.

As $|G_s|$ increases and the spurious substructures become more intricate, the performance of all methods tends to degrade. This is primarily because certain spurious substructures may exhibit strong correlations with the target labels, leading to misclassification of invariant substructures and overestimation of spurious edges.

One such example is the Motif-Base and Motif-Size datasets, where the OOD performance of most methods drops significantly in Motif-size dataset due to the increased size of $G_s$ and the more intricate spurious subgraph topology.

While this phenomenon also affects the performance of PrunE, our experimental analysis reveals that, despite occasionally assigning high probabilities to spurious edges (as seen in other methods), PrunE is also able to consistently estimate invariant edges with high confidence. This ability is critical for its superior OOD generalization performance relative to prior approaches.

Nonetheless, how to identify and suppress spurious edges that are strongly correlated with target labels remains a challenging problem and represents a promising direction for our future research.

Q2: Computational efficiency and scalability

Response: We thank the reviewer for raising this point. In the context of graph-level OOD generalization, each sample corresponds to an individual graph, typically containing at most a few hundred nodes. This contrasts with node classification tasks, where each sample is a node within a potentially massive graph comprising millions of nodes. As such, scalability is generally not a major concern for graph-level classification datasets.

To further address the reviewer’s concern regarding computational efficiency, we conducted additional experiments to evaluate runtime and memory overhead on two datasets.

Table 1: Memory consumption of vairous methods (in MB)

Table 2: Runtime of various methods (in seconds)

As shown in the tables above, compared to most graph-specific OOD methods, PrunE exhibits advantages in computational efficiency, as it introduces only two lightweight regularization terms on the subgraph selector. In contrast, many existing methods rely on more expensive operations such as data augmentation or contrastive learning. This highlights the computational efficiency of our approach.

We sincerely thank the reviewer for the careful review and insightful feedback. We hope that our responses have adequately addressed your concerns regarding our study.