Pruning Spurious Subgraphs for Graph Out-of-Distribution Generalization
Authors: Tianjun Yao
Haoxuan Li
Yongqiang Chen
Tongliang Liu
Le Song
Eric P. Xing
Zhiqiang Shen
Venue: NeurIPS 2025 poster ()
Keywords: OOD generalization
invariant learning
graph neural networks
Primary area: deep_learning

Abstract: Graph Neural Networks (GNNs) often encounter significant performance degradation under distribution shifts between training and test data, hindering their applicability in real-world scenarios. Recent studies have proposed various methods to address the out-of-distribution (OOD) generalization challenge, with many methods in the graph domain focusing on directly identifying an invariant subgraph that is predictive of the target label. However, we argue that identifying the edges from the invariant subgraph directly is challenging and error-prone, especially when some spurious edges exhibit strong correlations with the targets. In this paper, we propose $\texttt{PrunE}$, the first pruning-based graph OOD method that eliminates spurious edges to improve OOD generalizability. By pruning spurious edges, $\texttt{PrunE}$ retains the invariant subgraph more comprehensively, which is critical for OOD generalization. Specifically, $\texttt{PrunE}$ employs two regularization terms to prune spurious edges: 1) _graph size constraint_ to exclude uninformative spurious edges, and 2) _$\epsilon$-probability alignment_ to further suppress the occurrence of spurious edges. Through theoretical analysis and extensive experiments, we show that $\texttt{PrunE}$ achieves superior OOD performance and outperforms previous state-of-the-art methods significantly.

Pruning Spurious Subgraphs for Graph Out-of-Distribution Generalization
Tianjun Yao
Haoxuan Li
Yonggiang Chen 1.2 Tongliang Liu
Le Song' Eric Xing Zhiqiang Shen'
Mohamed bin Zayed University of Artificial Intelligence
2 Carneeiie Mellon University 'The University of Sydney
(tianjun. yao, haoxuan. li, yingooiggnng Chenuama ac. ae
tongliang. liu@sydney. edu.au, au, (le. song, eric. eric.xing, zhiqiang. shen) @mbzuai ac. ae
Abstract
Graph Neural Networks (GNNs) often encounter significant performance degrada- tion under distribution shifts between training and test data, hindering their applica- bility in real-world scenarios. Recent studies have proposed various methods to address the out-of-disttibution (OOD) generalization challenge, with many methods in the graph domain focusing on directly identifying an invariant subgraph that is predictive of the target label. However, argue that identifying the edges from the invariant subgraph directly is challenging and error-prone, especially when some spurious edges exhibit strong correlations with the targets. In this paper, propose PrunE, the first pruning- based graph OOD method that eliminates spurious edges improve OOD generalizability. By pruning spurious edges, PrunE retains the invariant subgraph more comprehensively, which is critical for OOD generalization. Specifically, PrunEemploys
regularization terms to prune spurious edges: 1) graph size constraint to exclude uninformative spurious edges, and 2) e-probability alignment to further suppress the occurrence of spurious edges. Through theoret- ical analysis and extensive experiments, we show that PrunE achieves superior OOD performance and outperforms previous state-of-the-art methods significantly. Codes are available at: http://gthh..coooiiayyoaooaaaaap
1
Introduction
often encounter significant performance degradation under distribution shifts between training and test data, hindering their applicability in real-world scenarios [18 19 27 To address the out-of-distribution (OOD) generalization challenge, recent studies propose to utilize the causally invariant mechanism to learn invariant features that remain [Q]. In graph domain, various methods have
Graph Neural Networks (GNNs) 25
61 55
stable across different environments 44
23
29
(44), Most OOD methods, both in the general domain and the graph domain, aim learn invariant features directly. To achieve this, many graph-specific OOD methods utilize a subgraph selector to model independent edge probabilities directly identify invariant subgraphs that remain stable across different training However, we argue that directly identifying invariant subgraphs can be challenging and error pronee, particularly when spurious edges exhibit strong correlations with target labels. In such scenarios, certain edges in the invariant subgraph Ge may be misclassified (i.c., assigned low predicted probabilities). leading partial preservation of the invariant substructure and thereby degrading OOD generalization performance. In contrast, while subset of spurious edges may correlate strongly with targets, the majority of spurious edges are relatively uninformative and easier to identify due to their weak correlations with labels. Consequently, pruning these less 39th Conference on Neural Information Processing Systems (NcurIPS 2025).
been proposed to address the OOD generalization problem [59] 34
38
52
16
environments [9 42 59

---

informative edges is more likely to preserve the invariant substructure effectively. In this work, we raise the following research question:
Can we prume spurious edges instead of directly identifying invariant edges to enhance OOD generalization ability?
To address this question, we propose the first pruning-based OOD method. Unlike most existing graph OOD methods that aim to directly identify edges in the invariant subgraph,
our method focuses on pruning spurious edges to achieve OOD generalization (Figure D
We first begin with case study to investigate the differences between our method and previous ones that directly identify invariant subgraphs, in terms of how the induced subgraph selector estimates edges from the invariant subgraph Ge and spurious subgraph G.. Specifically, we ob- serve that previous methods tend to misclassify some edges in Ge as unimportant edges with low probabilities, while assigning high probabilities to certain edges in Gg. As a result, the invariant substructure in the graph is not preserved. In contrast, our pruning based method preserves the invariant subgraph more effectively (i.c.. esti- mating the edges in Ge with high probabilities), although a small number of spurious edges may still remain due to the strong correlation with the targets. However, by preserving the invari- ant substructure more effectively, our method PrunE(Pruning spurious Edges for OOD generalization) achieves enhanced OOD performance compared to previous approaches that directly identify invariant subgraphs.
scde pesced edges
Arno
A Arune
(a) Identiff edges from the invariant subgraph direcly
(b) Prune odges from the spurious subgraph
Figure 1: Illustration of two learning paradigms for graph-specific OOD methods. Previous methods seek to identify edges from the invariant subgraph directly, while our approach prunes edges from the spurious subgraph, which more effective at preserving the invariant substructure.
The core insight behind PrunE is that Empirical Risk Minimization (ERM) tends capture all "useful" features that are correlated with the targets (26] 8 In our context, ERM pushes the subgraph selector to preserve substructures that are more informative for prediction. By forcing uninformative edges to be excluded, Ge is preserved due to its strong correlation with the targets and the inherent inductive bias of ERM. To prune spurious edges, our proposed OOD objective consists of two terms that act the subgraph selector, without adding additional OOD objective: 1) graph size constraint. This constraint limits the total edge weights derived from the subgraph selector to n|G' for graph G, where 1 < 1, thereby excluding some uninformative edges. 2) e-probability alignment. This term aligns the probabilities the lowest K% edges to be close to zero, further suppressing the occurrence of uninformative edges. Through theoretical analysis and extensive empirical validation, we demonstrate that PrunE significantly outperforms existing methods in OOD generalization, establishing state-of- of-the-art performance across various benchmarks. Our contributions are summarized as follows:
Novel framework. We propose a pruning- based graph OOD method PrunE, which introduces a novel paradigm focusing on removing spurious edges rather than directly identifying edges in Ge. By pruming spurious edges, PrunEpreserves more edges in Ge than previous methods, thereby improving its OOD generalization performance.
Theoretical guarantee. We provide theoretical analyses, demonstrating that: 1) The proposed graph size constraint provably enhances OOD generalization ability by reducing the size of G.; 2) The proposed learning objective (Eqn. provably identifies the invariant subgraph by pruning spurious edges.
Strong empirical performance. We conduct experiments both synthetic datasets and real- world datasets, compare against 15 baselines, PrunEoutperforms the second-best method by up to 24.19%, highlighting the superior OOD generalization ability.
2 Preliminaries
Notation. Throughout this work, an undirected graph G with n nodes and m edges is denoted by G = EV,E,, where V is the node set and È denotes the edge set. G is also represented by the

---

adjacency matrix A E R"x" and node feature matrix X E R with D feature dimensions. We use Ge and G2 to denote invariant subgraph and spurious subgraph. Go and G. denote the estimated invariant and spurious subgraph. t: R=x= x IR" + R refers to a learnable subgraph selector that models each independent edge probability, G ~ ((G) represents G is sampled from (GG). We
use to denote vector, and W to denote a matrix respectively. Finally, a random variable is denoted as W. set is denoted using W. A more complete set of notations is presented in Appendix A
10
odga
edgee in C2
Avg. # of odges
Tes: Accurnes
OOD Generalization. We consider the problem of graph classification under various forms of distribution shifts in hidden environments. Given set of graph datasets G = {G* heEE,,, GNN model f == p ht com- prises encoder h: RR x RaxD -> IR. that learns a representation by for each graph G, followed by a downstream classifier p: RF + Y to predict the label
EDSS 1M8 truett 2014
0
1.5c GSAT CIGA AIA Cnaeee
1.5c 1.5c
1.5c
1.5c
YG = p(hc). In addition, a subgraph selector t(-) is em- ployed to generate graph with structural modifications. The objective of OOD generalization in our work is to learn an optimal composite function fo l that encodes stable features by regularizing t(:) to prune spurious edges while preserving the edges in Ge.
PrinF.
top X predicted edges
Figure 2: Illustration of the average num- ber of edges from G. and G, included in the top-K predicted edges, where c de- notes |Grl-
Assumption 1. Given a graph G E G. there exists a stable subgraph Ge for every class label Y V, satisfying: a) Ve,e' E,,, (Y G.) pe' (Y Go): b) The target Y can be expressed as Y = =f (Go) + where e 1 G represents random noise.
Assumption D posits the existence of a subgraph Ge that remains stable across different environments and causally determines the target Y, thus is strongly correlated with the target labels. Our goal in this work is identify edges in Ge by excluding spurious edges to achieve OOD generalization.
3 Should We Identify Invariant Subgraphs or Prune Spurious Subgraphs?
Datasets, We use GOODMotif 15] dataset with base split for the case study. More details of this dataset can be found in Appendix !
In this section, we conduct a case study to explore the differences between previous graph OOD methods and our proposed approach in the estimated edge probabilities. Through experiments, we observe that our pruning-basee
method more effective at preserving G, compared to previous methods that aim to directly identify Ge. thereby facilitating better OOD generalization performance for our approach. Next we detail the experimental setup and observations.
Experiment Setup. We use GSAT (2). CIGA (]. and AIA [52] as baseline methods representing three different lines of work for comparison, all of which utilize a subgraph selector to directly identify Ge for OOD generalization. After training and hyperparameter tuning, we obtain model and well-trained subgraph selector for each method. We evaluate the test performance on the Motif- base dataset and calculate the average number of edges in G. and G. among the top- - predicted edges for all methods. Here, we set K- G.l. For our method, we also present the statisties under different values of K.
Observations. From Figure 2, we observe that: (1) PrunE outperforms all the baselines by a significant margin, demonstrating superior OOD generalization ability; (2) When K = 1.5]Gel. our method preserves more edges from Ge compared to other methods. Moreover, as K transitions from 5 G. to 1.5. the average number of edges in Ge remains nearly constant, while the number of edges from G. decreases significantly. This indicates that most edges from Ge have predicted probabilities greater than those from G.; (3) When compared with the oracle, the average number of edges in G. under our method still slightly lower than the oracle value, suggesting that a small number of spurious edges are estimated with high probability. In conclusion, compared to directly identifying invariant edges (i.e., edges in G.), pruning spurious edges preserves more edges in G.., even if some spurious edges remain challenging to climinate. However, the OOD performance can be
3

---

substantially improved by retaining the invariant subgraphs, which explains why our mounin--bsee method outperforms previous approaches. We also provide a detailed discussion in Appendix[Mon why traditional graph OOD methods tend to assign low probabilities to edges in Ge. and how our pruning-basee basend approach avoids this pitfall. Next, we detail the design of our pruning-based method.
Proposed Method
In this section, we present our pruning-based method PrunE, which directly regularizes the subgraph selector without requiring any additional OOD regularization. The pseudocode of PrunE is shown in Appendix H
Subgraph selector.
we model each edge Cij (ernoulli(ps) independently which is parameterized by Pij. The probability of the graph G factorized over all the edges, i.e., P(G) Hee Pij. Specifically, we employ GNN model to derive the node representation for each node v, followed by an MLP to obtain the logits way as following:
Following previous studies 666
40
59
h, GNN(U G), VEV,
Wi MLP (h,, hy. h,llh)) esj E
here || denotes the concatenation operator. To ensure the sampling process from Wy is differentiable and facilitate gradient- based optimization, we leverage the Gumbel-Softmar reparameterizzation trick [ 41]. which is applicd as follows:
Pij = σ (lloge E - log(1 - c) + wiy) /T), U(0,
(2)
À 1 sg(pt) + Pij.
here A denotes the sampled adjacency matrix, T is the temperature, sg(-) denotes the -rogggrad operator, and (/ 1) denotes the uniform distribution. Aij is the edge weight for egy. which remains binary and differentiable for the gradicnt- based optimization.
Next, we introduce the proposed OOD objectives in PrunE that directly act on the subgraph selector to prune spurious edges: (1) Graph size constraint, which excludes portion of uninformative spurious edges by limiting the total edge weights in the graph; (2) c-probability aligument, which further suppresses the presence of uninformative edges by aligning the predicted probabilities of certain edges close to zero.
Graph size constraint. We first introduce a regularization term Le which encourages graph size distinction between G ~ t(G) and G:
Dossiee A.j. [3]
2
L. = EEg
11
(3)
where 7) is hyper-parameter that controls the budget for the total number of edges pruned by t(-). The core insight is that when L. acts as a regularization term for ERM, the subgraph selector will prune spurious edges while preserving edges in Ge, since ERM learns all useful patterns that highly correlated with the target labels (26 8] Therefore, given Assumption I G. will be preserved due to its strong correlation the targets, and subset of) edges in G. will be excluded. In practice, we find that E {0.5, 0.75, 0.85) works well for most datasets. In Proposition [ we demonstrate that the graph size regularization L. provably prunes spurious edges while retaining invariant edges.
c-probability alignment. Although L. is able to prune a subset of spurious edges, it is challenging to get rid of all spurious edges. To further suppress the occurrence of spurious edges, we propose the following regularization on t(.):
C, Eg E
Σ Ei
Pij - cl.
(4)
Here.e is a value close to zero, Pij denotes the normalized probability of the edge eij. and E, is the lowest K% of edges among all estimated edge weights wij by the subgraph selector ((-).
The key insight is that edges from Ge are likely to exhibit higher predicted probabilities compared to edges in G.. Thus, by aligning the bottom K% edges with the lowest predicted probability to small

---

probability score it becomes more likely to suppress spurious edges rather than invariant edges. When K gets larger, L. will inevitably push down the probabilities of edges in Ge. However, ERM will drive up the probabilities of informative edges for accurate prediction, ensuring that the important edges are included in Ge. Therefore, the penalty for L, should be relatively small compared the penalty of ERM. In practice, we find that 2 E {le-2, 2, 1e-3) 3} work stably across most datasets. In all experiments, set [g|'
which works well for all the datasets.
Final objective. The overall objective is formulated as:
L = Lor + Ae + X2h.,
(5)
here A E {1,2} are hyperparameters that balance the contribution of each component to the overall objective, and LGr denotes the ERM objective:
LGT
-Eg Σ Yu log (J(LG)))),
(6)
where Yg denotes the class label &s for graph G, f(t(G)) is the predicted probability for class & of graph G.
5 Theoretical Analysis
In this section, we provide some theoretical analysis on our proposed method PrunE. All proof's are included in Appendix FF
Proposition 1. Under Assumption 7 the size constraint loss Le, when acting as regularizer for the ERM loss LGT, will prune edges from the spurious subgraph G., while preserving the invariant subgraph Ge given suitable 1).
Prop. | demonstrates that by enforcing graph size constraint, Le will only prune spurious edges, thus making the size of G, to be smaller. Next we show that Le provably improves OOD generalization ability by shrinking [Gz].
Theorem 5.1. Let [((s,, Zz, y, G); 0) denote the 0-1 loss function for predicting whether edge eij presents in graph G using t.)), and
L(:
1 ni
Σ
[[ G);,),,,,,))),,.... E E.
(a.,e, G.G)D
L(0,8): = m Σ
U( G);0), E E
(2,
where D and S represent the training and test distributions, respectively.c is constant, and and m denotes the sample size in training set and test set respectively. Then, with probability at least
1 5 and v0 E O we have:
L(00)) 2(c 1)M,
(8)
where M [n(1))) 1- lm(5)
Inf In(1
2m
Theorem 5. establishes an OOD generalization bound that incorporates |G,l due to domain shifts. When G, 0, Eqn. 1egn.8recie reduces to the traditional in nn-distrbbttinn generalization bound. Theorem 5.1 shows that C. enhances the OOD generalization ability by reducing the size of G, and tightens the generalization bound.
Theorem 5.2. Let O* = arg L(O), where e- = (+), For any graph G with target label y E Y, we have G. ze Et (G).. Consequently, sampling from (G) in expectation will retain only the invariant subgraph Go. which remains stable and sufficiently predictive for the target label y-
Theorem 5.2 demonstrates the ability to retain only G. by sampling from (G). While previous
methods aim directly identify Gz, PrunE able to achieve the similar goal more effectively by pruning spurious edges.
5

---

Table Performance on synthetic and real-world datasets. Numbers in bold indicate the best perfor- mance, while the underlined indicates the second best performance. * denotes the test performance is statistically significantly better than the second-bess method, with p-value less than 0.05.
GOODMotif
GOODHIV
EC50
OGBG-Molbbbp
Method
base
size
scaffold
size
scaffold
size
ussay
scaffold
size
FRM
68.6614475
51.74
69.58
59.94
62.77
61.03
64.9316.25
68.10_1
78.29.17
IRM
70.65=4117
41,41
67.97=184
59.00
63.96-321
62.47=115
72.27+341
67.22-1115
47,56=244
GroupDRO
68.24=892
51.95+536
70.64=257
58.98=215
64.13+181
59.06=150
70.52+335
66,47=239
79.27=243
VREx
71.47a6m
52.67a5.44
70.77
58.53
64.23
63.54.1m
68.23
68.74_108
78.76:239
DrepEdge
45.08=446
45.63+451
70.78:1138
28.53
63.91
61.93
73.79
66.49=1.55
78.32#3.44
G Mixup
59.66.2m
52.811875
70.01
59 59.34.244
61.90:206
61.062174
69.28
17,
78.55:446
FLAG
61.12
51.6614444
68.45
60.59
64,98
64.28.054
11
6
79.26.22.
LISA
54.59=481
53.464431
70,38=145
52.36
02.00=342
60.96=1177
69.73+062
68, 68.11=
78, 78,62=334
DIR
62.07=#75
52.27:44.6
68.07=22>
58 28.08=231
63.91=292
61.91=302
66.13++20
66,86=225
76.40=443
DisC
51.08:30s
50.39
68.07
58.76:091
59,10
57.64:155
61.94:7.55
67.12=211 16.59
CAL
65.63
51.181500
67
57.95
65.032111
60.92.2mm
14.93
68.06_20
79.50=441
GREA
56.744921
13=10m
67.79.2%
60.71
64.67=143
12.17
11
69,72=166
77.34=35:
GSAT
60.4214
53.201111
68.66113
58.00 18.0621 Ms
65.122110
61.90a212
74.77
66.78g144 75.63
CIGA
68.71 14
69.40=23
59, 59,55
65,42:155
64.47
74.94
64.92=20
65,98=331
AIA
72.91=542
55.85+788
71.15#181
61.64#337
64.71=a50
63.43=133
76.01
70.79=159
81.03=5.1
PrunE
91.48" =0,00
66.53' +8.55
71.84"
64.99* =143
67.56"
:4:34
65.46
78.01
=0:2
70.32=1.7 81.39
6 Related Work
OOD generalization on graphs. To tackle the OOD generalization challenge on graph, various methods have been proposed recently. MoleOOD (62. GII. (34 and MIIII [57] aim to learn graph
invariant features with environment inference. CIGA 9 adopts supervised contrastive learning
to identify invariant subgraphs for OOD generalization. Several methods (59
38 52 22
utilize graph data augmentation to enlarge the training distribution without perturbing the stable patterns in the graph, enabling OOD generalization by identifying stable features across different augmented environments. SizeShiftReg (5] proposes method for size generalization for graph-level classification using coarsening techniques. GSAT 42 uses the information bottleneck principle (53) to identify the minimum sufficient subgraph that explains the model's s prediction. EQuAD [64] and LIRS [65] learn invariant features by disentangling spurious features in latent space. Many existing methods attempt to directly identify the invariant subgraph to learn invariant features. However, this approach can be error-prone, especially when spurious substructures exhibit strong correlations with the targets, leading the failure to preserve the invariant substructure and ultimately limiting the OOD generalization capability. In contrast, PrunE aims to exclude spurious edges without directly identifying invariant edges, resulting in preserving the invariant substructure more effectively, and enhanced generalization performance.
Feature learning in the presence of spurious features. Several studies have explored the inductive bias and SGD traiming dynamics of neural networks in the presence of spurious features [45] 46 49 [49] shows that in certain scenarios neural networks simple spurious features, while ignoring the core features. More recently, [26] and [8] found that even when neural networks heavily rely spurious features, the core (causal) features can still be learned sufficiently well. Inspired by these studies, the subgraph selector should be able to include Ge to encode invariant features using ERM the learning objective, given that Ge is both strongly correlated with and predictive of the targets (Assumption []. This insight motivates us to propose a pruning-based graph OOD method. Compared to previous approaches, PrunE capable of preserving more intact set of edges from Ge to enhance OOD performance, at the cost that certain spurious edges may remain difficult eliminate.
suffer from simplicity bias and rely on
7 Experiments
In this section, we evaluate the effectiveness of PrunE on both synthetic datasets and real-world datasets, and answer the following research questions. RQ1. How does our method perform compared with SOTA baselines? RQ2. How do the individual components and hyperparameters in PrunE affect the overall performance? RQ3. Can the optimal subgraph selector L (G) correctly identify G.? RQ4. Do edges in G. predicted by 1(-) exhibit higher probability scores than edges in G.? RQ5. How does PrunE perform on datasets with concept shift? RQ6. How do different GNN architectures impact

---

50.0
71.84
71.71
70.17
0.001
71.04
68.61
71.12
69.22
16a Koa
70.0
71.04
69.11
70.33
0.1
71.84
71.71
50
90.0
69.15
68.41
68.69
1.0
68.07
70.17
30
Mclf-Sam
MerthGiis
1-7--Saa
0.5
0.75
0.85
10.0
40.0
A1
(a) Ablation study.
(b) Hyperparameter sensitivity analysis.
Figure 3: (a) Ablation on L. and C,; (b) Hyperparameter sensitivity on GOODHIV-scafood..
the OOD performance? More details on the datasets, experiment setup and experimental results are presented in Appendix !
7.1 Experimental Setup
Datasets. We adopt GOOD datasets [5]. OGBG-Molbbbp datasets
18 60
and DrugOOD
datasets [21) to comprehensively evaluate the OOD generalization performance of our proposed framework.
Baselines. Besides ERM 54 we compare our method against two lines of OOD baselines: (1) OOD algorithms Euclidean data, including IRM (]. VREx (29), and GroupDRO 443; (2) graph-specific methods which utilize a subgraph selector for OOD generalization, and data augmentation methods,
including DIR [59]. GSAT [42), GREA 38
DisC (Л]) CIGA 9 AIA [52). DropEdge (47
G-Mixup 17 FLAG 28 and LiSA 667.
Evaluation. We report the ROC-AUC score for GOOD-HIV OGBG-Molbbbp. and DrugOOD datasets, where the tasks are binary classification. For GOOD- datasets, we use accuracy as the evaluation metric. We run experiments 4 times with different random seeds, and report the mean and standard deviations on the test set.
7.2 Experimental Results
We report the main results on both synthetic and real-world datasets, as shown in Table I
Synthetic datasets. In synthetic datasets, PrunE outperforms graph OOD methods that attempt to directly identify G. by large margin, and surpasses the best baseline method AIA by 19% and 19.13% in Motif-base and Motif-size datasets respectively. This highlights the effectiveness of the pruning-base based paradigm. We also observe that on the Motif-size dataset, the performance of most methods drop significantly, which can be attributed to the increased size of G and the presence of more complex spurious substructures, leading to the overestimation of spurious edges by PrunE, as well as by other baselines that rely on invariant subgraph identification for OOD generalization.
Real-world datasets. In real- world datasets, many graph OOD algorithms exhibit instability, occa- sionally underperforming ERM. In contrast, our approach consistently achieves stable and superior performance across a diverse set of distribution shifts, and outperforms the best baseline method AIA which seeks to identify invariant subgraph directly by an average of 2.38% in 7 real- world datasets. This also demonstrates that the proposed pruning-based paradigm can be effectively applied to various real-world scenarios, highlighting its applicability.
7.3 Ablation Study
In this section, we evaluate the impact of Le and L, using the GOODMotif and GOODHIV datasets. As illustrated Figure 3a) removing either L. or L, leads to a significant drop in test performance across all datasets, and larger variance. The removal of L. results in more significant decline, as this regularization penalty is stronger (e-g.. Å set to 10 or 40 in the experiments). However, even with Le, some spurious edges may still exhibit high probabilities, potentially inducing large variance.

---

True Positive Rate
Mockdaancur E.5
Mill stoiiid Gene 0.30)
False Positive
(a) Visualizations on learned subgraph by ("()), where blue nodes are (b) The ROC-AUC curve for predicted ground-truth nodes in Ge, and red nodes are tround-truth nodes in G.. edges and ground-truth edges on The highlighted hlue edges are top-K edges predicted by (-), where K GOODMotif-base and GOODMotif- is the number of ground-truth invariant edges.
size datasets.
Figure 4: Empirical visualization and analysis on t t-)).
By further employing L.. PrunE effectively reduce predicted probabilities for most spurious edges, thus further reduce the variance and improve the performance.
7.4
Sensitivity
In this section, We study the impact of hyperparameter sensitivity on the edge budget nj in Ces the bottom K% edges with the lowest probability, and the alignment probability in L.. Ad- ditionally, we investigate the effects of varying the penalty weights a and X2 for be and L.
As illustrated in Figure 3(b) the test perfor-
mance for GOODHIV scaffold remains stable
Table 2: Test performance with varying
across different hyperparameter settings. Ad-
ditional results on more datasets are included
base Motif-size EC50-assay
in Appendix ! which also exhibit stable per-
formance across wide range of hyperparame- ter settings, further highlighting the stability of PrunE. Furthermore, we investigate the impact of in L.. As shown in Table 2 the optimal performance is observed when is small value close zero. As increases, the test perfor- mance declines, especially on synthetic datasets. This decline occurs because larger values of e weaken the suppression effect, potentially leading adverse effect that hinder generalization. Notably, when e [E]. the suppression strength is dynamically adjusted for each graph instance, resulting in stable performance across diverse datasets. In summary, although setting certain hyperparameters outside appropriate ranges may lead failures in OOD generalization for example, small r) (e.g.. 0.1) may prune edges in Ge. and small X1 may have insufficient effect on suppressing spurious cdges-Prunf PrunE exhibits stable performance across variety of datasets when hyperparameters are chosen within reasonable ranges (hyperparameters in Figure 3(b).
0.01
91.631:073
60.3828.35
77.7641.11
0.1
88.14:10.67
62.38::10.66
76.65+1192
0.3
80.93:1:433
50.65::4995
76.07:1:2.55
= 0.5
74.52+119.89
50.28188.35
75.93+11.27
6 [E]
91.48:10.40
66.51.1..55
78.01
7.5 In-depth Analysis
Can (*))) identify G.? To verify whether (*(.) can indeed identify Ges we conduct experiments using GOOD-Motif datasets with both Motif-buse and Motif-size splits. These synthetic datasets are suitable for this analysis as they provide ground-truth labels for edges and nodes that are causally related to the targets. First, collect the target label for each edge. and the predicted probability score from t* (-) for correctly predicted samples and plot the ROC- AUC curve for both the validation
and test sets for the two datasets. As illustrated in Figure 4(b the AUC scores for both datasets exhibit high values, demonstrating that (*) accurately identifies Ge. which is consistent with the theoretical insights provided in Theorem [5.2] Figure 4(a iillustrates some visualization results using
(-). demonstrating that t* (.) correctly identify invariant edges from G,,. More visualization results for the identified edges using (-) provided in Appendix]]
Do edges in G. exhibit a higher probability than edges in G.? We assess the probability scores and ranking of edges in Ge compared to those in G2 using the GOOD Motif datasets. Specifically,

---

0.85
50
1.0
0.80
Avg. marking
Avg. malking ingiing
prob
0.9
40
40
0.75
0.70
0.8
Avp. edge nrbb
30
edgt edge ninking
0.65
Aug. rarkingkking
Stadd Rice
20
30
20
40
Epoch
Epoch
MoniFloawe
Moti-aii
(b) Performance with different
(a) Average predicted probability and ranking of edges Ge-
GNN encnders.
Figure 5: (a) Average probability and ranking of edges in Ge for every training epoch. Invariant edges are generally assigned higher scores, though spurious edges may be overestimated due to label correlation. (b) Test performance with different GNN encoders. PrunE benefits from expressive architectures under OOD settings.
we plot the average probability and ranking of edges in Ge over the first 40 epochs (excluding the first 10 epochs for ERM pretraining), using the ground-truth edge labels. As shown in Figure ((a) for both the Motif-base and Motif-size datasets, the invariant edges in G, exhibit high probability scores, ranking among the top 50% in both datasets. This demonstrates that the edges from the invariant subgraph generally get higher predicted probability scores compared to spurious edges. However, certain spurious edges may still be overestimated due to their strong correlation with the target labels.
How does PrunE perform on datasets with concept shift? In the main results, we use covariate shift to evaluate the OOD performance of various methods, where unseen environments arise in validation and test datasets. We also adopt concept shift to evaluate the effectiveness of PrunE, where spurious correlation strength varies in training and test sets. As shown in Table 3 PrunE also outperforms the SOTA methods significantly. For Motif-base dataset, most of the methods underperform ERM, while PrunE achieves 90.28% test accuracy, which is 10.86% higher than ERM. How do different GNN encoders affect the model perfor- mance? We examine the effect of using different GNN en- coders, specifically GCN [25] and GIN [6]], with the same hidden dimensions and number of layers as h(-). As illustrated in Figure 5(b) across all four datasets, employing GIN as the feature encoder leads to increase in test performance. This is likely due GIN's higher expressivity than GCN [61], being as powerful as the 1-WL test [3I]. which allows it to gener- ate more distinguishable features compared to GCN. These enhanced features benefits the optimization of t(-), thereby im- proving the identification of G. for OOD generalization. This also highlights another advantage of PrunE: utilizing GNN encoder with enhanced expressivity may further facilitate OOD generalization by more accurately identifying G. through ((-).
Table 3: Model performance with concept shift.
Method GOODHIV GOODMotif
size
base
ERM
63,26+247
81. 20.44
IRM
59.90+3115
80.7 10.46
VRex
60.23+1.7
81 31.562233
GSAT
56.7647.16
76.07+3.44
GREA
60.07++3.4
78.27+4.29
CIGA
73.62.0..6
81.68
AIA
74.21+1.81 82.51
PrunE
79.50
90.28
Conclusion
Many graph-specific OOD methods aim to directly identify edges in the invariant subgraph to achieve OOD generalization, which can be challenging and prone to errors. In response, we propose PrunE, a pruning- bbase OOD method that focuses on removing spurious edges by imposing regularization terms on the subgraph selector, without introducing any additional OOD objectives. Through a case study, we demonstrate that, compared to conventional methods, PrunE exhibits enhanced OOD generalization capability by retaining more edges in the invariant subgraph. Theoretical analysis and extensive experiments across various datasets validate the effectiveness of this novel learning paradigm. Future research directions include: (1) Extending the pruning-based paradigm to self- supervised setting without relying on the power of ERM; (2) Expanding this learning paradigm to other scenarios, such dynamic graphs under distribution shifts.

---

References
[1] Kartik Ahuja, Ethan Caballero, Dinghuai Zhang, Jean- Caan-Chrittophe Gagnon-Auder, Yoshua Bengio. Ioannis Mitliagkas, and Irina Rish. Invariance principle meets information bottleneck for out-of-distriuttion generalization. Advances in Neural Information Processing Systems, 34:3438-3450, 2021.
[2] Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk ninimization. arXiv preprint wrw.iv:907.0089900 2019.
[3] Guy W Bemis and Mark A Murcko. The properties of known drugs. 1. molccular frameworks, Journal of medicinal chemistry, 39(15):2887-289, 1996.
[4] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXi::1308.3432 2013.
[5] Davide Buffelli. Pietro Liò, and Fabio Vandin. Sizeshiftreg: regularization method for improving size- sizeggeneralization graph neural networks. Advances Neural Information Processing Systems. 35:31871-31889 2022.
[6] Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. In International conference on machine learning, pages 1695-1706 PMIR, 2021.
[7] Yongqiang Chen, Yatao Bian, Kaiwen Zhou, Binghui Xie, Bo Han, and James Cheng. Does invariant graph learning via environment augmentation learn invariance? In Thirty-seventh Conference on Neural Information Procexsing Systems, 2023.
[8] Yonggiang Chen. Wei Huang, Kaiwen Zhou, Yatao Bian, Han, and James Cheng. Understanding and improving feature learning for out-of oi-distribttion generalization. Advances in Neural Information Processing Systems, 36:68221 (1666221-687777 2023.
[9] Yongqiang Chen, Yonggang Zhang, Yatao Bian, Han Yang, MA Kaili, Binghui Xie, Tongliang Liu, Bo Han, and James Cheng. Learning causally invariant representations for graphs. Advances in Neural Information Processing Systems, 35:22131-22148, 2022.
generalization on
[10] Elliot Creager, Jöm--enrik Jacobsen, and Richard Zemel. Environment inference for invariant learning. In International Conference on Machine Learning, pages
PMLR, 2021.
[11] Shaohua Fan, Xiao Wang, Yanhu Mo, Chuan Shi, and Jian Tang. Debiasing graph neural networks via learning disentangled causal substructure. Advances in Neural Information Processing Systems, 35:24934 24946, 2022.
[12] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric, 2019.
[13] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint / 1803.03635, 2018.
[14] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George F. Dahl. Neural message passing for quantum chemistry. In International Conference Machine Learning, pages 1263-1272. PMLR, 2017.
[15] Shurui Gui, Xiner Li, Limei Wang, and Shuiwang Ji. GOOD: A graph out-of-distribution benchmark. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
[16] Shurui Gui, Meng Liu, Xiner Li, Youzhi Luo, and Shuiwang Ji. Joint learning of label and environ- ment causal independence for graph out-of-distribution generalization. Advances in Neural Information Processing Systems, 36, 2023.
[17] Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. In International Conference on Machine Learning, pages 8230-8248. PMLR, 2022.
[18] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems, 33:22118-222 18-22133, 2020.
[19] Kexin Huang. Tianfan Fu, Wenhao Gao, Yue Zhao, Yusuf Roohani, Jure Leskovec, Connor Coley, Cao Xiao, Jimeng Sun, and Marinka Zitnik. Therapeutics data commons: Machine learning datasets and tasks for drug discovery and development. arXiv preprint arXiv:2102.095.. 09540, 2021.
10

---

[20] Bo Hui, Da Yan, Xiaolong Ma, and Wei-Shinn Ku. Rethinking graph lottery tickets: Graph sparsity matters. arXiv preprint arXiv:2305.02190. 2023.
[21] Yuanfeng Ji, Lu Zhang, Jiaxiang Wu, Bingzhe Wu, Long- Kai Huang. Tingyang Xu, Yu Rong, Lanqing Li, Jie Ren, Ding Xue, al. Drugood: Out-of-distribution (ood) dataset curator and benchmark for ai-aided drug discovery-a focus on affinity prediction problems with noise annotations. arXiv preprint axXiv:2001.096377, 2022.
[22] Tianrui Jia, Haoyang Li, Cheng Yang, Tao Tao, and Chuan Shi. Graph invariant learning with subgraph co-mixup for
generalization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 8562 8570, 2024.
[23] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Domain extrapolation via regret minimization. arXiv preprini arXiv:2006. 03908, 3, 2020.
[24] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint TrXiv:1412.6988 41860980. 2014.
[25] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations. 2017.
[26] Polina Kirichenko, Pavel Izmailov, and Andrew Gordon Wilson. Last layer re- training sufficient for robustness to spurious correlations. In The Eleventh International Conference on Learning Representations, 2023.
[27] Pang Wei Koh, Shiori Sagawa, Hearik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: A benchmark of in- the-wild distribution shifts. In International Conference Machine Learning, pages 5637-5664. PMLR, 2021.
[28] Kezhi Kong, Guohao Li, Mucong Ding, Zuxuan Wu, Chen Zhu, Bernard Ghanem, Gavin Taylor, and Tom Goldstein. Robust optimization as data augmentation for large-scale graphs. Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 60-69, 2022.
[29] David Krueger, Ethan Caballero, Joern- Henrik Jacobsen, Amy Zhang. Jonathan Binas, Dinghuai Zhang. Remi Le Priol, and Aaron Courville. Out-of-distribution generalization via risk extrapolation (rex). In International Conference Machine Learning, pages
PMLR, 2021.
[30] Steinar Laenen. One-shot neural network pruning via spectral graph sparsification. In Topological, Algebruic and Geometric Learning Workshops 2023, pages 60-71. PMLR, 2023.
[31] Andrei Leman and Boris Weisfeiler. A reduction of graph to canonical form and an algebra arising during this reduction. Nauchno-Teccnniceen
Informatsiya, 2(9):12-16, 1968.
[32] Gaotang Li, Marlena Duda, Xiang Zhang, Danai Koutra, and Yujun Yan. Interpretable sparsification of brain graphs: Better practices and effective designs for graph neural networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1223-1234, 2023.
[33] Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu 7hu. Ood-gnn: -iitri--ittiiuutionn generalized graph neural network. IEEE Transactions on Knowledge and Data Engineering, 2022.
[34] Haoyang Li, Ziwei Zhang, Xin Wang, and Wenwu Zhu. Learning invariant graph representations for out-of-distribute generalization. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[35] Haoyang Li, Ziwei Zhang, Xin Wang, and Wenwu Zhu. Invariant node representation learning under distribution shifts with multiple latent environments. ACM Transactions on Information Systems, 42(1):1- 30, 2023.
[36] Xiner Li, Shurui Gui, Youzhi Luo, and Shuiwang Ji. Graph structure and feature extrapolation for out of-ddsstibuttin generalization. arXiv preprint arXiv:2306. 2023.
[37] Xiner Li, Shurui Gui, Youzhi Luo, and Shuiwang Ji. Graph structure extrapolation for outto--disttibutiin generalization. In Forty-first International Conference on Machine Learning, 2024.
[38] Gang Liu, Tong Zhao, Jiaxin Xu, Tengfei Luo, and Meng Jiang. Graph rationalization with environment- based augmentations. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '22. ACM, August 2022.

---

[39] Yang Liu, Xiang Ao, Fuli Feng. Yunshan Ma. Kuan Li. Tat-Seng Chua, and Qing He. Flood: A flexible invariant learning framework for out-of-distribution generalization on graphs. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1548-1558. 2023.
[40] Dongsheng Luo. Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in Neural Information Processing Systems, 33: 196120199631, 2020.
[41] Chris J Maddison, Andriy Mnih, and Yee Whye Tch. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint 1rXiv:161 1.00077,, 2016.
[42] Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. In International Conference on Machine Learning, pages 15524-15543. PMLR, 2022.
[43] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf. Edward Yang. Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style,
deep learning library, 2019.
[44] Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society Series B: Statistical Methodology: 78(5):977-111, 2016.
[45] Mohammad Pezeshki, Oumar Kaba, Yoshua Bengio, Aaron C Courville, Doina Precup, and Guillaume Lajoie. Gradient starvation: A learning proclivity in neural networks. Advances in Neural Information Processing Systems, 34:1256-1272, 2021.
[46] N Rahaman, A Baratin, D Arpit. F Draxler, M Lin, F Hamprecht, Y Bengio, and A Courville. On the spectral bias of neural networks: International conference machine learning. arXiv, 2019.
[47] Yu Rong, Wenbing Huang. Tingyang Xu, and Junzhou Huang, Dropedge: Towards deep graph convolu- tional networks on node classification. arXiv preprint arXiv: 1907. 10903, 2019.
[48] Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint arXiv: (9X1v:911.0083) 2019.
[49] Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Praneeth Netrapalli. The pitfalls of simplicity bias in neural networks. Advances in Neural Information Processing Systems, 33:9573-9585. 2020.
[50] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang. Christopher D. Manning, Andrew Ng. and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In David Yarowsky, Timothy Baldwin, Anna Korhonen, Karen Livescu, and Steven Bethard, editors, Proceedings of the 2013 Conference on Empirical Methods in Natual Language Processing, pages 1631-1642, Seattle, Washington, USA, October 2013, Association for Computational Linguistics.
[51] Yong-Duo Sui, Xiang Wang, Tianlong Chen, Meng Wang. Xiang-Nan He, and Tat-Seng Chua. Inductive lottery ticket learning for graph neural networks. Journal of Computer Science and Technology, 19(3) 1237, 2024.
[52] Yongduo Sui, Qitian Wu, Jiancan Wu, Qing Cui, Longfei Li, Jun Zhou, Xiang Wang, and Xiangnan He. Unleashing the power of graph data augmentation on covariate distribution shift. Advances in Neural Information Processing Systems, 36, 2023.
[53] Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle, 2015.
[54] Vladimir N. Vapnik. The nature of statistical learning theory. Springer-Verlag New York, Inc., 1995.
[55] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint 17Xiv:1710..000 2017.
[56] Kun Wang, Yuxuan Liang, Pengkun Wang, Xu Wang, Pengfei Gu, Junfeng Fang, and Yang Wang. Searching lottery tickets in graph neural networks: A dual perspective. In The Eleventh International Conference on Learning Representations, 2022.
[57] Ruijia Wang. Haoran Dai, Cheng Yang. Le Song, and Chuan Shi. Advancing molecule invariant represen- tation via privileged substructure identification. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 3188-30 0198,,19,2200 2024.
12

---

[58] Qitian Wu, Hengrui Zhang, Junchi Yan. and David Wipf. Handling distribution shifts graphs: An invariance perspective. arXiv preprint arXiv:2202.02466 02446, 2022.
[59] Yingxin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. In International Conference on Learning Representations, 2022.
[60] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 922:5133-330 2018.
[61] Keyulu Xu, Weihua Hu. Jure Leskovec. and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.008220 2018
[62] Nianzu Yang, Kaipeng Zeng. Qitian Wu, Xiaosong Jia, and Junchi Yan. Learning substructure invariance for out-of-distibutiin molecular representations. In Alice H. Oh, Alekh Agarwal. Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems. 2022.
[63] Huaxiu Yao. Yu Wang. Sai Li, Linjun Zhang, Weixin Liang, James Zou, and Chelsea Finn. Improving of-distribution robustness via selective augmentation. In International Conference on Machine Learning. pages 25407-25437. PMLR, 2022.
[64] Tianjun Yao, Yongqiang Chen, Zhenhao Chen, Kai Hu, Zhiqiang Shen, and Kun Zhang. Empowering graph invariance learning with deep spurious infomax. Forty-first International Conference on Muchine Learning, 2024.
[65] Tianjun Yao, Yongqiang Chen, Kai Hu. Tongliang Liu, Kun Zhang, and Zhiqiang Shen. Learning graph invariance by harnessing spuriosity. In The Thirteenth International Conference on Learning Representations, 2025.
[66] Zhitao Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[67] Junchi Yu, Jian Liang, Ran He. Mind the label shift augmentation--ased graph ood generalization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 11620- 11630, 2023.
[68] Hao Yuan, Haiyang Yu. Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. IEEE transactions on pattern analysis and machine intelligence, 45(5):5782-5799, 2022.
[69] Guibin Zhang, Kun Wang, Wei Huang, Yanwei Yue, Yang Wang, Roger Zimmermann, Aojun Zhou, Dawei Cheng, Jin 7eng, and Yuxuan Liang. Graph lottery ticket automated. In The Twelfth International Conference on Learning Representations, 2024.
[70] Xiang Zhuang, Qiang Zhang, Keyan Ding, Yatao Bian, Xiao Wang, Jingsong Lv, Hongyang Chen, and Huajun Chen. Learning invariant molecular representation in latent discrete space. Advances in Neural Information Processing Systems, 36, 2023.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main contributions are highlighted in the abstract and introduction section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
13

---

It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have discussed the limitations of our work in the Appendix.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specification, asymptotic upproximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
We have provided detailed proof in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
14

---

Answer: [Yes]
Justification: We have provided detailed experimental setup in the Appendix, and disclose our project code anonymously.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We use public datasets, and disclose our code anonymously.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
public/ public/guides/ httae//guiiiee/teeubmmssssee
(CodeSSbmissiioooooiiooo. for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https //nips.cc/pubbe http:////gguiiee///deeeuuiiiiiss
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
15

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Yes, details about experimental setting are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We run experiments four times, and report error bars for the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric eтror bars that would yield results that are out range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have detailed our hardware and software used in the experiments in the appendix.
16

---

Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
Our research won't bring any potential harmful societal impact.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We have included a section in appendix regarding broader impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
17

---

Answer: [NA]
Justification:
The safeguards is not related to our study.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We have cited the relevant work for data and code.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: There new assets in work.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
18

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This topic is not related with our work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This topic is related with our work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
The declaration is not required for our study.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.MM policy futtps://neur// wwwpurrpsscc/Cooffeeeeeeeeeeee / for what should or should be described.
19

---

Appendix of PrunE
Contents
Notations
21
Broad Impact
21
More Preliminaries
21
Additional Related Work
22
Algorithmic Pseudocode of PrunE
23
Proofs of Theoretical Results
23
F1 Proof of Proposition
23
F2 Proof of Theorem 5.
24
F3 Proof of Theorem 5.2
25
More Discussion on Pruning-based Learning Paradigm
26
H
Complexity Analysis
26
The Pitfall of Directly Identifying Edges in Ge
27
More Details about Experiments
27
Datasets details
27
J.2
Detailed experiment setting
28
J.3 More Experimental Results
29
Limitations of PrunE
Software and Hardware
32
20

---

A
Notations
We present set of notations used throughout our paper for clarity, Below are the main notations along with their definitions.
Table 4: Notation Table
Symbols
Definitions
G
Set of graph datasets
Eur
Set of environments used for training
Eall
Set of all possible environments
G
An undirected graph with node set V and edge set & Node set of graph G Edge set graph G Adjacency matrix of graph G
V
3
A
X
Node feature matrix of graph G
D
Feature dimension of node features in X
Ge
Invariant subgraph G Spurious subgraph of G Estimated invariant subgraph
G
Ge
G.
Estimated spurious subgraph
G
The number of edges in graph G.
Y
Target label variable
w
vector
W
A matrix
W
random variable
W
A set
f p
GNN model comprising encoder h(-) and classifier p(-)
t(-)
Learnable data transformation function for structural modifications
(x)())
A view sampled from t(-), e.g., G ~ t(-). We may use t(G) to denote sampled view
from via t(-), e.g., I(;; t(G)
h
Representation of node V of graph
B
Broad Impact
This work proposes novel paradigm for OOD generalization that departs from conventional invariant learning approaches, which typically attempt to learn invariant features directly through various optimization objectives [
[ 23 29 [00. Instead, advocate for complementary perspective: en- hancing OOD generalization by explicitly pruning spurious features. the graph domain, we realize this paradigm by pruning spurious edges, which allows the model retain invariant substructures. This shift in perspective offers a new direction with substantial potential, especially in domains where identifying invariant substructures offers valuable insights.
The proposed method not only achieves strong empirical performance under distribution shifts but also offers better explainability by providing explicit insights into which parts of the graph structure effectively explains the model prediction. This contributes toward more transparent and trustworthy machine learning models. Furthermore, approach is generally applicable to graph-structured data across a wide range applications, including molecular property prediction, social network analysis, and knowledge reasoning.
C More Preliminaries
Graph Neural Networks. this work, we adopt message-passing passing GNNs for graph classification
due to their expressiveness. Given simple and undirected graph G X) with nodes and edges, where A {0, 1jnxa is the adjacency matrix, and X e gaxd is the node feature
21

---

matrix with d feature dimensions, the graph encoder h G - I aims to learn meaningful graph-level representation hig- and the classifier p : R + Y is used to predict the graph label YG = p(hc). To obtain the graph representation lGg, the representation he of each node in a graph G is iteratively updated by aggregating information from its neighbors M(v). For the I-th layer, the updated representation is obtained via an AGGREGATE operation followed by an UPDATE operation:
m AGGREGATE ((N!- : ( m
(9)
h UPDATE (n!-",m!")
(10)
where h = Xx is the initial node feature of node e in graph G. Then GNNs employ a READOUT function to aggregate the final layer node features ho:
[bb
(1) 1 e
V) into graph-level representation
bg = READOUT
((n.)
(11)
D Additional Related Work
OOD Generalization Graphs. Recently, there has been growing interest in learning graph- level representations that are robust under distribution shifts, particularly from the perspective of invariant learning. MoleOOD [62] and GIL (34] propose to infer environmental labels to assist in identifying invariant substructures within graphs. DIR [59] GREA (38) and iMoLD 77 employ environment augmentation techniques to facilitate the learning of invariant graph-level representations. These methods typically rely on the explicit manipulation of unobserved environmental variables to achieve generalization across unseen distributions. AIA [52] employs an adversarial augmenter to explore OOD data by generating new environments while maintaining stable feature consistency. To circumvent the need for environmental inference or augmentation, CIGA 9 and GALA ( utilizes supervised contrastive learning to identify invariant subgraphs based on the assumption that samples sharing the same label exhibit similar invariant subgraphs. LECI [16] and G-Splice (36] assume the availability of environment labels, and study environment exploitation strategies for graph OOD generalization. LECI [16] proposes to learn a causal subgraph selector by jointly optimizing label and environment causal independence, and G-Splice [36] studies graph and feature space extrapolation for environment augmentation, which maintains causal validity. EQuAD (44 and LIRS (65) learn invariant features by disentangling spurious features via two stage learning paradigm, i.e., learning spurious features via self-supervised learning followed by disentangling spurious features via ERM. On the other hand, some works do not utilize the invariance principle for graph OOD generalization. DisC IT initially learns a biased graph representation and subsequently focuses on unbiased graphs to discover invariant subgraphs. GSAT [42 utilizes information bottleneck principle (53) to learn a minimal sufficient subgraph for GNN explainability, which is shown to be generalizable under distribution shifts. OOD-GNN 33 proposes to learn disentangled graph representation by computing
global weights of all data.
Node-level OOD Generalization. There has been substantial work on OOD generalization for adopt invariant learning to address node-level OOD challenges. Compared to graph-level OOD generalization, node-level OOD problems face unique difficulties, including: (1) distinct types of distribution shifts (e.g., structural or feature-level shifts), (2) non-i.i.d. node dependencies due to the interconnected nature, and (3) computational bottlenecks from subgraph extraction when reducing to graph-level OOD tasks. Due to these challenges, our pruning- based approach cannot be directly extended to node-level tasks. We leave this adaptation to future work.
node-level classification tasks. Most existing methods [58 39 35 67
Lottery Ticket Hypothesis and Graph Sparsification. The Lottery Ticket Hypothesis B suggests that large neural networks contain small subnetworks (i.e., winning tickets) that, when trained in isolation, can match the performance of the original model. This idea has been extended to GNNs through the Graph Lottery Ticket (GLT) Hypothesis, which posits that sparse subgraphs can preserve GNN performance. (6] introduced unified framework for pruning both GNN parameters and edges, that improve pruning strategies, robustness, and
with many follow-up studies 20 30 32 56
51 69
even transferability across graphs.
22

---

end for While both graph sparsification and PrunE perform edge pruning, they differ in motivation and optimization. GLT and Graph sparsification targets large-scale graphs where computational bot- tlenecks are critical, seeking maximal compression while preserving performance through lottery ticket principles. In contrast, PrunE addresses graph-level OOD generalization on smaller graphs where efficiency is not the primary concern. Technically, graph sparsification optimizes masks under ERM with sparsity regularization and employs rewinding operations. PrunE follows the typical OOD optimization framework where ERM loss is regularized to encourage invariance. Thus, while both involve edge pruning, graph sparsification seeks compact subnetworks for efficiency backed by lottery ticket hypothesis, whereas PrunE leverages pruning regularization strategy to suppress spurious edges and improve OOD generalization.
E Algorithmic Pseudocode of PrunE
In this section, we provide the pseudocode of PrunE in Algorithm] |
Algorithm The proposed method
1: Input: Graph dataset G. epochs E. learning rates 1), hyperparameters λ1 Au
2: Output: Optimized GNN model f" p" hi", and the subgraph selector 6" (-).
3: Initialize: GNN encoder io... classifier p(.), and the learnable data transformation f(-).
4: for epoch = 1 to E do
5: for each minibatch B E do
6: Calculate W.y using Equ. 1 for each graph G E B
7:
Calculate L. using Eqn.
8:
Calculate L, using Eqn. 4
9:
Sample G (G) using t(-) each G E B
10:
Calculate cross- entropy loss LGT using Eqn. Compute the total loss C. = LGT + Ce + Agh Perform backpropagation to update the parameters of h(-), p(-), and t(-)
11:
12:
13:
end for
F Proofs of Theoretical Results
F.1 Proof of Proposition 1
Proof. We begin by expanding the cross-entropy loss Lcr as:
Let -EEg [log P( {()))
(12)
where G ~ t(G). Supposing that | |Gel, which be controlled by the hyperparameter
Eqn. further assume that & does not include the invariant subgraph G.. Let a subgraph y be subtracted from T and [g] = [G2], we then define a new subgraph G' = G g. and we add G, to to form the new graph G" U..
Under Assumption [ we know that the invariant subgraph G. holds sufficient predictive power Y. and Ge is more informative to Y than G., therefore including G. will always make the prediction more certain, i.e.,
P(Y ((G' P(Y I(G
(13)
As result, Ler will become smaller. Therefore, we conclude that under the graph size regularization imposed by C., the optimal solution G ~ I(G) will always include the invariant subgraph G., while pruning edges from the spurious subgraph G., This completes the proof.
D
23

---

Remark. When is set too small, the loss term L. may inadvertently prune edges in Ge. thereby corrupting the invariant substructure and degrading OOD generalization performance. In practice, we observe that 1 (0.5, 0.75, 0.85) works well across most datasets stably.
F.2 Proof of Theorem 5.1
Proof. We first formally define the notations in our proof. Let ((111, G); denote the 0-1 loss for the edge Eig being presented in graph G, and
L(0; D) = Σ
n
(14)
L(,
Σ
[(z, U. ())
where D and S represent the training and test distributions, with n and m being their respective sample sizes. We define:
Lo(
1 n (B)2),,,G)~D
Σ
[[1 G.) Vey E Go.
(15)
L), T (G)
E
2z (,);),, Veg G..
Similarly, (0 and L, S) be defined for the distribution. Under Assumption L.(0; D) and (0; S) are identically distributed due to the stability of G. across environments, while (0; D) and (0; 8) differ because of domain shifts in Gg. We assume:
|
Lg (0: = clG. Lo(0;
(16)
where e is a proportionality constant. As (.(.) defined to summation over all spurious edges, we put [G,, in the r.h.s to account for this factor. When |G 0, the loss reduces to the in-distribution case (0:-).
[L(0;: D) - [(005)]
[0;(0; D) (0; D) L,(0:,) (0,(0)))
(17)
< (o; D) L.(0; S)| [L, D) (0:
(18)
(o; D) [c(0: S) c|G,l [0c D) (0;
(19)
(c|G.| 1) D) S):
(20)
To bound [L((0; D) Lc(0; S) we decompose as:
[.((0; D) (0) < (0; D) - E (T, D)]1 + |E (T.,(0;)) (0;
(21)
Applying Hoeffding's Inequality to each term:
( (0; D)] (0: D)I < 2exp (-262n)
(22)
P ( [0) (0: 2 c) $ 2 2xx (-262
(23)
Union bounding over all e:
P(30 E e (0: (O) L.(0: [.: 2 exp (-2e2n)
(24)
- P(30 E θ [. 2 & 2 exp (-2c2m)
(25)
24

---

Setting both probabilities to 6/2 and solving for e:
cD In(4 - ln())
(26)
|n(4 1n(6)
(27)
2m
Thus, with probability at least 6:
s ED + ES
(28)
/ In(4 (o)
In(4|0)) In(ō)
(29)
2n
2m
Substituting into Eqn. 20
[L(0; D) I(005)) & 2(cGaa + 1) (1
(In((100)) In(d)
[nn(|(1)) )(n()))))(())))
(30)
2n
2m
Letting M
|n((1)))-
In
obtain the final bound:
2n
2m
-(0:))-((0:5))
1)M.
(31)
0
F.3 Proof of Theorem 5.2
Proof. Our proof consists of the following steps.
Step 1. We start by decomposing E|t" (G)) into two components: the invariant subgraph G, and partially retained spurious subgraph G?.
Elt" (G)) = E [Ge + G
= E [G.] [G]]]
(32)
Ge + E [G,]]
In Eqn. 32
E G. Ge is due to that for any given label y. Ge is constant according to Assump- tion while G.,² is a random variable.
Step 2. We then model G? as set of independent edges, and calculate the expected total edge weights of G, and G respectively. First, we define W. as the sum of binary random variables corresponding the edges in Ge. Each edge eij in Ge is associated with Bernoulli random variable X,y such that:
W. Σ X
(33)
es EG
Similarly, we define WP as the sum of binary random variables corresponding to the edges in G.. Each edge esy in GP is associated with Bernoulli random variable X such that:
WP Σ X
(34)
CG
W. and WP denoted random n.v. for the total edge weights of G, and G..
25

---

Step 3. We then calculate the expected edge weights E[W.] and E[W?] as following.
W
= E
Σ
Xisl = Σ
E[Xis] = |Gel,
(35)
Exy EGfEGe
61g EGs
|
n/8| |Gel
E = E Σ O: CG
=
Σ GGE
x
[8]
[E
(36)
Here& & is the set of edges in graph G, n/E| is the total edge number limits due to L.- In Eqn. 35
[[Xaa] = 1. Veij E G. is due to that P(();)) = 1. as (C) always include G, using the results [X = E Vey E G.. due to that P(X))) = [ enforced by 6- probability alignment penalty C.. Therefore, given suitable that prunes spurious edges from G.. E > n- GG i.e., E((" (G)] will be dominated by G. in terms of edge probability mass, therefore, we conclude that G. 2 (())
from Prop. 1 In Eqn. 36
G More Discussion on Pruning-based Learning Paradigm
While PrunE focuses on pruning spurious edges for OOD generalization, recent studies 63
65
attempt to disentangle spurious features from ERM-learned representations in the latent space, demonstrating capability in capturing more invariant substructures [65]. In Table additional comparisons with LIRS [65].
3 we provide
For synthetic dataset, LIRS and PrunE exhibit notable differences in performance across datasets with different characteristics. Specifically, on the Motif-base dataset, PrunE achieves 91.40% 11.00% accuracy, significantly outperforming LIRS (75.51% 1)). contrast, on the Motif-size dataset, LIRS performs better than PrunE. This also hightlights the different inductive bias between these two methods: For a graph with more complex spurious patterns and large graph size, PrunE struggle to prune all the spurious edges, thus leading to decreased performance, while LIRS adopt self-supervised learning to capture spurious features first, smaller ratio of G. would lead to more effective spuriosity learning, thus facilitating the subsequent feature disentanglement. In contrast, the learning of spurious features would be more challenging in Motif- base due to the large ratio of invariant subgraph.
In real-worls datasets, we observe that the performance of PrunE is on par with LIRS, however, PrunE presents several advantages over LIRS 65] and EQuAD 64. Specifically, (1) LIRS involves multiple stages, with nearly 100 hyperparameter combinations in total; In contrast, PrunE demonstrates robust performance with limited set of hyperparameters across datasets, greatly reducing model tuning efforts. Moreover, as PrunE only introduces two lightweight regularization terms, it is highly efficient runtime and memory cost, and 3.x faster than LIRS in terms of running time. (2) 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.
Table 5: Test OOD performance on synthetic and realworld datasets.
Motif
GOODHIV
EC50
Base
Size
Scaffold
Size
Assay
Size
Scaffold
LIRS
75.51
74.51
72.82
66.64
76.81
64.20
65.11
PrunR
91.4
66.53
71.84
64.99
78.01
65.46
67.56
H Complexity Analysis
Time Complexity. The time complexity is OCCmmF), where k is the number of GNN layers, m is the total number of edges in graph G, and F is the feature dimensions. Compared to ERM, PrunE incurs an additional constant C > 1, as it uses GNN model ((.)) for edge selection, and another GNN encoder h.))) for learning feature representations. However, C is a small constant, hence the time cost is par with standard ERM.
26

---

Space Complexity. The space complexity for PrunE is O(C") where |B| denotes the batch size. The constant C" is due the additional subgraph selector t(.). As C' is also small integer, the space complexity of PrunE is also on par with standard ERM.
In Table we report the memory consumption and runtime of various OOD methods. While PrunE incurs higher overhead than IRM and VRex due to the usage of subgraph selector, it remains more efficient than most graph OOD baselines. This is attributed objectives, in contrast to the more computationally intensive operations such as data augmentations and contrastive training employed by other methods. Notably, PrunE is 3.15x faster than LIRS on the Molbbbp dataset, owing to its single-stage training paradigm. When considering the additional over- head from hyperparameter tuning, the runtime advantage of PrunE becomes even more pronounced.
the use of two lightweight OOD
Table 6: Memory consumption and running time Motif-base and OGBGG-ollbbp datasets.
(a) Memory overhead (in MB).
(b) Runtime (in Second)
Method Motif-base Molbbbp
Method
Motif-base
Molbbbp
ERM 40.62
32.43
ERM
494.34 1: 117.6
92.42 1:
IRM
51.76
36.19
IRM
968.94 1 164.09
151.84 7.53
VRex
51.52
35.92
VRex
819.94 1 124.54
129.13
GREA
103.22
76.28
GREA
1612.43 1: 177.36
262.47 45.71
GSAT
90.12
58.02
GSAT
1233.68 +: 396.19
142.47 25.11
CIGA
104.43
72.47
CIGA
1729.14 355.62
352.14
+: 93.32
ATA
99.29
81.55
AIA
1422.34 +: 69.33
217.36 + 11.04
LIRS
89.15
107.37
LIRS
504.87 2404
421.32 19.86
PrunE
501.62 +
133.35 3.47
PrunE
74.15
61.07
The Pitfall of Directly Identifying Edges in Ge
Most graph-specific OOD methods that model edge probabilities incorporate OOD objectives as regularization terms for ERM. These OOD objectives attempt to directly identify the invariant subgraph for OOD generalization. For example, GSAT 42 utilizes the information bottleneck to learn a minimal sufficient subgraph for accurate model prediction; CIGA [9] adopt supervised contrastive learning to identify the invariant subgraph that remains stable across different environments within the same class; DIR (59) and AIA (52) identify the invariant subgraph through training environments augmentation. However, when spurious substructures exhibit comparable or stronger correlation strength than invariant edges (i.c., edges in Ge) with the targets, these methods are unlikely to identify all invariant edges, and preserve the invariant subgraph patterns Since the spurious substructure may be mistakenly identified as the stable pattern. Consequently, while achieving high training accuracy, these methods suffer from poor validation and test performance.
In contrast, PrunE avoids this pitfall by proposing OOD objectives that focus on pruning uninforma- tive spurious edges rather than directly identifying causal ones. While strongly correlated spurious edges may still persist, edges in G, are preserved due to their strong correlation with targets. As key conclusion, PrunE achieves enhanced OOD performance compared to prior methods, the invariant patterns are more likely to be retained, even if some spurious edges cannot be fully excluded.
J More Details about Experiments
J.1 Datasets details
In our experimental setup, we utilize five datasets: GOOD- GOOD-Motif, SPMotif, OGBG- Molbbbp, and DrugOOD. The statistics of the datasets illustrated in Table
GOOD-HIV [5]. GOOD-HIV a molecular dataset derived from the MoleculeNet 60 benchmark, where the primary task is to predict the ability of molecules to inhibit HIV replication. The molecular
27

---

structures are represented as graphs, with nodes as atoms and edges as chemical bonds. Following [5]. We adopt the covariate shift split, which refers changes the input distribution between training and testing datasets while maintaining the same conditional distribution of labels given inputs. This setup ensures that the model must generalize to unseen molecular structures that differ in these domain features from those seen during training. We focus on the Bemis-Murcko scaffold [ and the number nodes in the molecular graph as two domain features to evaluate our method.
GOOD-Motif [5]. GOOD-Motif is a synthetic dataset designed to test structure shifts. Each graph in this dataset is created by combining a base graph and motif, with the motif solely determining the label. The base graph type and the size are selected as domain features to introduce covariate shifts. By generating different base graphs such as wheels, trees, or ladders, the dataset challenges the model's 'ss ability to generalize to new graph structures not seen during training. We employ the covariate shift split, where these domain features vary between training and testing datasets, reflecting real-world scenarios where underlying graph structures may change.
SPMotif [59]. In SPMotif datasets (59], each graph comprises a combination of invariant and spurious subgraphs. The spurious subgraphs include three structures (Tree, Ladder, and Wheel), while the invariant subgraphs consist of Cycle, House, and Crane. The task for a model is to determine which one of the three motifs (Cycle, House, and Crane) is present in a graph. A controllable distribution shift can be achieved via a pre-defined parameter b. This parameter manipulates the spurious correlation between the spurious subgraph G. and the ground-truth label Y. which depends solely on the invariant subgraph G.. Specifically, given the predefined bias b, the probability of specific motif (e.g., House) and specific base graph (Tree) will co-occur is b while for the others (1 - b)/2 (e.g., House-Ladder, House- Wheel). When b = ! the invariant subgraph is equally correlated to the three spurious subgraphs in the dataset.
3
OGBG-Molbbbp [8] OGBG-Molbbbp is real-world molecular dataset included in the Open Graph Benchmark 18 This dataset focuses on predicting the blood-brain barrier penetration of
molecules, critical property in drug discovery. The molecular graphs are detailed, with nodes representing atoms and edges representing bonds. Following (author?) [52], we create scaffold
shift and graph size shift to evaluate our method. Similarly to (author?) [15). the Bemik-Murcko
scaffold [3] and the number of nodes in the molecular graph are used as domain features to create scaffold shift and size shift respectively.
DrugOOD 21 DrugOOD dataset is designed for OOD challenges in Al-aided drug discovery. This benchmark offers three anvironment-spliting strategies: Assay, Scaffold, and Size. In our study, we adopt the EC50 measurement. Consequently, this setup results in three distinct datasets, each focusing on a binary classification task for predicting drug-target binding affinity.
Table 7: Details about the datasets used in our experiments.
DATASETS
Split
TRAINING # VALIDATION # TESTING CLASSES METRICS
Base
18000
3000
3000
3
ACC
GOOD-Motif
Size
18000
3000
3000
3
ACC
SPMotif
Correlation
9000
3000
3000
ACC
Scaffold
24682
4113
4108
2
ROC-AUC
GOOD-HIV
Size
26169
4112
3961
2
ROC-AUC
OGBG-Molhbhp
Scaffold
1631
204
204
ROC-AUC
OGBG-Molbace
Scaffold
1210
152
151
2
ROC-AUC
Assay
4978
2761
2725
2
ROC-AUC
EC50
Scaffold
2743
2723
2762
2
ROC-AUC
Size
5189
2495
2505
2
ROC-AUC
J.2 Detailed experiment setting
GNN Encoder. For COOD-Motif datasets, we utilize a 4-layer GIN 61 without Virtual Nodes 14. with hidden dimension of 300; For GOOD-HIV datasets, we employ 4-layer GIN without Virtual Nodes, and with hidden dimension of 128; For the OGBG-Molbbbp dataset, we adopt 4- GIN with Virtual Nodes, and the dimensions of hidden layers is 64; For the DrugOOD datasets,
28

---

use a 4-layer GIN without Virtual Nodes. For SPMotif datasets, we use a 5-layer GIN without Virtual Nodes. All GNN backbones adopt sum pooling for graph readout.
Training and Validation. By default, we use Adam optimizer (24) with a learning rate of le - 3 and batch size of 64 for all experiments. For DrugOOD, GOOD-Motif and GOOD-HIV datasets,, our method is pretrained for 10 epochs with ERM, and for other datasets, we do not use ERM pretraining. We employ an early stopping of 10 epochs according to the validation performance for DrugOOD datasets and GOOD-Motif datasets, and do not employ early stopping for other datasets. Test aceuracy or ROC-AUC is obtained according the best validation performance for all experiments. All experiments are run with 4 different random seeds, the mean and standard deviation are reported using the 4 runs of experiments.
Baseline setup and hyperparameters. In our experiments, for the GOOD and OGBG-Molbbbp datasets, the results of FRM, IRM, GroupDRO, and VREx are reported from [15), while the results for DropEdge, DIR, GSAT, CIGA, GREA, FLAG, G-Mixup and AIA on GOOD and OGBG datasets are reported from [52]. To ensure fairness, we adopt the same GIN backbone architecture as reported in [52]. For the EC50 datasets and SPMotif datasets, we conduct experiments using the provided source codes from the baseline methods. The hyperparameter search detailed as follows.
For IRM and VREx, the weight of the penalty loss is searched over {le - 2, 1c 1.1). For GroupDRO, the step size is searched over (1.0, le 1, 1c 2}. The causal subgraph ratio for DIR is searched across {1e- - 2, le - 1, 0.2, 0.4, 0.6). For DropEdge, the edge masking ratio is searched over: 10.1, 0.2, 0.3). For GREA, the weight of the penalty loss is tuned over {le 2, le 1,-1,, 1.0), and the causal subgraph size ratio is tuned over (0.05, 0.1, 0.1,0.. 0.2, 0.3, 0.5). For GSAT, the causal graph size ratio is searched over (0.3, 0.5, 0.7). For CIGA, the contrastive loss and hinge loss weights searched over {0.5, 1.0, 2.0, 4.0, 8.0]. For DisC, we search over in the GCE loss: {0.5, 0.7, 0.9}. For LiSA, the loss penalty weights are searched over: le 1, le 2, le 3). For G-Mixup, the augmented ratio is tuned over {0.15, 0.25, 0.5). For FLAG, the ascending steps are set to 3 as recommended in the paper, and the step size is searched over {le 3, le 2, le 1}. For AIA, the stable feature ratio is searched over {0.1.00 0.3, 0.5, 0.7, 0.9), and the adversarial penalty weight is searched over {0.01, 0.1, 0.2, 0.5, 1.0, 3.0, 5.03.
Hyperparameter search for PrunE. For PrunE, the edge budget r in Le is searched over: (0.5, 0.75, 0.85); K for the K% edges with lowest probability score in Ls is searched over: (50. 70, 90); X1, A2 for balancing L. and L, are searched over: (10, 40} and {le- 1, le 2, le 3} respectively. The encoder of subgraph selector t(-) is searched over {GIN, GCN), with
the number of layers: {2,3),
J.3 More Experimental Results
We provide more experiment details regarding: (1) Experiment results when there are multiple invariant substructures in a graph. (2) Experiment results for more application domains. (3) Ablation study on ERM pretraining. (4) The capability of PrunE of identifying spurious edges. (5) More
visualization results on GOOD-Motif datasets in Figure Figure (6) Hyperparameter sensitivity analysis on Motif-base, OGBG-Molbbbp, and EC50 assay datasets, Figure
Table 8: Experimental results on SPMotif datasets with 2 invariant subgraphs in each graph.
SPMotif (#G. = 2)
Method
b == 0.40
b = 0.60 b = 0.90
ERM
53.48+3331
52.5944.61
56.76=8.06
IRM
52.47+3.63
55.62+7.0
48.66+2.33
VRex
49.6848.6
48.8944.79
47.97
GSAT
59.3417.96
58.43
55.68
GREA
64.87
67.66116.29
59.40
CIGA
69. 69.74
71.194246
65.83
AIA
71.61 72.01
58,14
PrunE
70.4147.53
74.61+3.17
66.75
29

---

Model performance for graphs with multiple invariant subgraphs. While Assumption | as- sumes the existence of single invariant substructure causally related to each target label, many real-world graph applications [8 13 may contain multiple such invariant subgraphs. However, Assumption
1 can be reformulated to accommodate multiple Ge without compromising the validity of our assumptions and theoretical results. Specifically, suppose there are K invariant subgraphs, denoted as G.., for E [K]. For any specific Ge.s. the spurious subgraph G², can be redefined as G", G. U { i a i]. Given this redefinition, and under the presence of G.. Assumption still holds. Consequently, the assumptions and theoretical results presented in this work remain valid, when multiple G. exist within the datasets. To further support claim, curated dataset based on SPMotif [39], where in the train/ trin//alid/test datasets, two invariant substructures are attached to the spurious subgraph. Our method performs effectively under this scenario, as shown in Table g
Experiment results on more application domains. To further evaluate the effectiveness of PrunE across different application domains, we conduct experiments on GOOD-CMNIST [15] and Graph- Twitter (50 68 datasets, the evaluation metric for these datasets is accuracy.
Table 9: Test performance on GOOD-CMNIST and Graph-Twitter datasets.
Method CMNIST Graph-Twitter
ERM
28.60
60.47=2224
IRM
27.83 56.93=1099
Vrex
28.48
57.54
DisC 24.99 1.78
48.61 18.86
GSAT
18.17
60.96:11.18
GREA
29.02=3.26
59.47
CIGA
32.22+2267
62.3 1 1.63
AIA
36.37
61.10=20.7
PrunE
33.89+1.65
63.37
As demonstrated in Table PrunE also achieves superior performance in application domains beyond molecular applications, indicating its superior OOD performance and broad applicability.
Ablation study on ERM pretraining. We conduct ablation study across datasets without using ERM pretraining. The results are presented in Table I0 As illustrated, incorporating ERM pretraining improves OOD performance in most cases, as the GNN encoder is able to learn useful representations before incorporating Le and C. to train t(-). Intuitively, this facilitates the optimization of f(-), therefore improving the test performance.
Table 10: Ablation study on test datasets.
Motif-basis Motif-size EC50-Assay
EC50-Sca HIV-size
w/ pretraining 91.48 66.53
78.01 :0.2
67.56+1.63
64.99
w/o pretraining
91.04+0.76 61.48
76.58
66. 66.1991.56 65,46
The capability of PrunE to identify spurious edges. To verify the ability of PrunE to identify spurious edges while preserving critical edges in G., we conduct experiments and provide empirical results on Recall@ K and Precision @ K on GOODMotif datasets, where K denotes the K% edges with lowest estimated probability scores. As illustrated in Table[[] PrunE is able to identify a subset of spurious edges with precision higher than 90% across all datasets, even with K 50, indicating that PrunE can preserve Gz, thus enhancing the OOD generalization performance.
Visualization results on GOOD-Motif datasets. We provide more visualization results on GOOD- Motif datasets in Figure and Figure 7 in which the blue nodes represent the ground-truth nodes in Ge, and blue edges are estimated edges by (-).. We visualize top-K edges with highest probability scores derived from I(.). As shown, PrunE is able to identify edges in G., demonstrating the effectiveness of pruning spurious edges, and aligns with the theoretical results from Theorem 5.2
30

---

Table 11: Recall @K and Precision @ K for Motif- and Motif-size datasets, where denotes the K% edges with lowest estimated probability scores.
Motif-base
Motif-size
%%
Recall Precision
Recall Precision
10%
0. 0417
1.0000
0.0963
0.9199
20%
0.3076
0.9831
0.2023
0.9602
30%
0,4556
0.9465
0.3093
0.9735
40%
0.6056
0.9374
0.4153
0.9801
50% 0.7356
0.9017
0.5243
0.9841
Figure 6: More visualization results Motif-base dataset. The blue nodes ground-truth nodes in G., and red nodes are ground-truth nodes G., The highlighted blue edges are top-K edges predicted by 1" (.), where K is the number of ground-truth edges from Ge in graph.
More visualization results Motif-size dataset. The blue nodes ground-truth nodes in Ge, and red nodes are ground-truth nodes G,- The highlighted blue edges are top-K edges predicted by t" (-), where K is the number of ground-truth edges from Ge in graph.
Figure 7:
Hyperparameter sensitivity. We provide more experimental results hyperparameter sensitivity on synthetic and real-world datasets. As shown in Figure PrunE exhibits stable performance across the real-world datasets, highlighting its robustness the Motif-base dataset, the performance not as stable as on real-world datasets. However this behavior expected: when 7) is set low, PrunE may mistakenly prune invariant edges, resulting in performance degradation. Since G. constitutes around 50% of the graph in Motif-base dataset, setting 0.5 leads to the removal of edges in G., ultimately causing failure in OOD generalization. Therefore, setting 7) 2 0.75 leading to enhanced OOD performance.
varying hyperparameter configurations. For
K Limitations of PrunE
While our proposed framework introduces novel and effective pruning-based paradigm for invariant learning, currently tailored to graph-structured data due its reliance on a learnable subgraph selector. Extending this approach other data modalities, such text images, remains non-trivial.
31

---

0.001
54.38
91.38
91.48
50.0
67.20
91.38
87.40
0.01
52.59
56.36
79.47
X 70.0
59.42
79.87
74.02
0.1
52.51
65.80
67.20
1.0
53.77
64.33
47.93
90.0
61.18
91.48
87.45
10.0
49.27
46.88
49.86
0.5
0.75
0.85
1.0
10.0
40.0
n
A1
(a) Hyperparameter sensitivity on Motif-base dataset.
50.0
81.59
80.30
78.80
0.001
79.20
79. 12
80.55
70.0
79.20
80.55
80.33
0.01
80.30
77.30
78.80
90.0
78.53
77.84
78.24
0.1
80.33
81.59
78.75
0.5
0.75
0.85
1.0
10.0
40.0
n
(b) Hyperparameter sensitivity on OGBG-Molbbbp size.
50.0
75.88
75.45
76.17
0.0001
76.80
78.01
K 70.0
77.86
76.88
76.78
0.001
77.86
77.25
90.0
78.01
77.25
76.47
0.01
76.19
76.53
0.5
0.75
0.85
10.0
40.0
A1
(c) Hyperparameter sensitivity on EC50 assay.
Figure 8: Hyperparameter sensitivity analysis across different datasets.
Additionally, although our method effectively removes a significant portion of spurious edges, some spurious edges may still persist due to their strong correlation with target labels. Developing more effective pruning approaches an important direction for our future research.
L Software and Hardware
We conduct all experiments using PyTorch 43
(v2.1.2) and PyTorch Geometric 12] on Linux
servers equipped with NVIDIA RTX4090 GPUs and CUDA 12.1.
32


Reviews:
[{"review_id": "APUgMzrCHQ", "reviewer": "Reviewer_Crbf", "summary": "The paper improves GNN robustness and generalization by identifying and pruning spurious subgraphs—structures correlated with predictions but not causally relevant. Using a causal framework, it employs counterfactual reasoning to detect these subgraphs and a generative model to create perturbed graphs for comparison. Pruning the spurious parts reduces shortcut learning and enhances out-of-distribution performance.", "questions": "Same to weakness. Overall I think this is a good paper.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:1.Well-motivated problem: The issue of spurious correlations in GNNs is important and underexplored. The paper provides a strong motivation grounded in causal inference and generalization theory. 2. Novel integration of causality in GNN pruning: While causality has been used in graph learning, this paper’s combination of generative counterfactual modeling and pruning of subgraphs for generalization is novel. 3.Good use of visualizations: Diagrams and figures help illustrate key components like the counterfactual generation and pruning mechanism.\n\nWeaknesses: 1. Overall, this is a solid work. However, \"spurious subgraphs are structural patterns in the input graph that are correlated with prediction labels in the training data but are not causally relevant to the true task.\" Is there any real world example besides the MUTAG dataset that demonstrate this? I am not sure this issue existed for every datasets in the realworld. Therefore not sure how this \n\n2. Figure 6 and Figure 7's results shows the model successfully find the important subgraphs. It seems this results are similar to a lot of GNN explanation work. For example, if I use GNNExplainer for find the subgraph, will this be very different from yours ?", "was_revised": true, "final_justification": "The authors' rebuttal has addressed my concerns and I remain my score as accept.", "rebuttal": "Thank you for your insightful comments and positive feedback! Please see below for our responses to your comments and concerns.\n\n> **W1: Spurious structural patterns in real-world applications.**\n\n__Response:__ We thank the reviewer for raising this important question. Below, we provide concrete evidence from three distinct application domains to illustrate the widespread presence of spurious subgraphs in real-world datasets:\n\n- **Molecular property prediction.**  For instance, in the **GOOD-HIV** dataset [1] with scaffold or size-based splits, the *invariant* substructures are functional groups that causally determine HIV inhibition. In contrast, *spurious* subgraphs include specific ring scaffolds or overall molecular size that co-occur with the label in the training distribution but are not causally relevant.\n\n- **Social-media analysis.** In rumor detection datasets such as Twitter15/16 and PHEME [2], the *invariant* components are propagation paths reflecting veracity-relevant interactions. Meanwhile, *spurious* structures arise from event-specific cascade motifs that are memorized during training. \n\n  - For instance, in PHEME’s Hurricane Sandy thread, a *Y-shaped cascade*—where `@WeatherNews` is retweeted by `@StormTracker` and `@CityNews`, both subsequently retweeted by `@LocalReporter`—is unique to that event and spuriously correlated with the label.\n\n- **Brain-network studies.** In functional connectivity graphs derived from resting-state fMRI [3,4], edges represent pairwise BOLD (Blood‑Oxygen‑Level‑Dependent) correlations. *Invariant* subgraphs correspond to biologically meaningful neural interactions (e.g., within the default mode network). *Spurious* subgraphs  are introduced by head motion artifacts, which often correlate with diagnosis or demographic variables. These artefactual edges can mislead models into attributing predictions to motion-related noise, thus harming generalization.\n\n---\n\nThese examples demonstrate that structural spuriosity is a pervasive issue across domains, highlighting the practical significance of our proposed pruning-based approach to improve OOD generalization.\n\n> **W2: Comparison with GNNExplainer.**\n\n__Response:__ While both GNNExplainer and PrunE are capable of identifying instance-level important subgraphs, the fundamental difference lies in their goals and technical solutions:  \n\n- GNNExplainer is designed for **in-distribution** explanation. It identifies subgraphs that are important for a trained GNN's prediction on the training distribution, but it does not explicitly distinguish between **invariant** and **spurious** correlations.  \n- In contrast, **PrunE** is specifically developed to identify **invariant subgraphs** under OOD settings by introducing regularization terms that explicitly suppress spurious correlations.\n\nWe conducted additional experiments using the GOOD-Motif dataset under both base and size splits, comparing our method against GNNExplainer (We use the GNNExplainer functionality from PyTorch Geometric), we report the AUC score for the predicted edge probability resulted from GNNExplainer and PrunE. Specifically, we first calculate per-sample AUC score, and report the average across all test samples.\n\nTable 1: AUC score of predicted edge probability for GNNExplainer and PrunE.\n| Method         | Motif-base (AUC) $\\\\uparrow$ | Motif-size (AUC) $\\\\uparrow$ |\n|----------------|:------------------:|:------------------:|\n| GNNExplainer   | 0.47             | 0.42            |\n| **PrunE (ours)** | **0.90**         | **0.74**         |\n\nAs shown, our method significantly outperforms GNNExplainer on both splits. This gap arises from the differing training regimes:\n\n- **GNNExplainer** is a post-hoc method, and it is applied after pre-trained GNN (e.g., GIN) model with ERM. The explainer then optimizes a soft mask to select a subgraph that preserves the model's prediction. However, **ERM tends to learn both invariant and spurious features**, therefore the optimized edge masking will also identify important edges that are strongly correlated with the labels as consequences, which is aligned with the results in **Table 1**, i.e., GNNExplainer utilizes edges from both ivnariant and spurious subgraphs to make predictions.\n- In contrast, PrunE incorporates OOD-specific regularization terms to regularize ERM. These terms facilitates the model to **prune spurious edges during training**. As a result, PrunE preserves invariant subgraphs more accurately and achieves substantially better identification performance in OOD scenarios.\n\n\n---\n\nWe sincerely thank the reviewer for the careful review and insightful feedback. We hope that our responses have adequately addressed your concerns regarding our study. Please let us know if there is anything we could further discuss, your further feedback would be greatly appreciated.\n\n\n\n**References**\n\n1. Gui, et al., GOOD: A Graph Out-of-Distribution Benchmark. NeurIPS 2022.\n\n2. Wu, et al., Probing Spurious Correlations in Popular Event-Based Rumor Detection Benchmarks, arXiv:2209.08799.\n\n3. Satterthwaite, et al., Motion artifact in studies of functional connectivity: Characteristics and mitigation strategies, Human Brain Mapping.\n\n4. Xu, et al., BrainOOD: Out-of-distribution Generalizable Brain Network Analysis. ICLR 2025."}, {"review_id": "E5i5zwUkQj", "reviewer": "Reviewer_vGyB", "summary": "The proposed method, *PrunE* addresses OOD generalization problem in graph representation learning from a novel perspective, graph sparsification. Compared to previous graph OOD methods, *PrunE* adopts a surprisingly simple yet effective prune strategy, which is designed to preserve more invariant substructure, at a cost of slightly increased uninformative edges. The proposed methods demonstrate extraordinary performance in extensive empirical studies.", "questions": "It seems to me that the *PrunE* method itself is similar to some very old graph sparsification methods[1]. However, such work (as well as the whole graph sparsification domain, e.g., [2]) is not introduced in the paper, and the well-known **lottery ticket theory** is not even mentioned in the paper. Can authors justify or clarify this?\n\n[1] Chen, Tianlong, et al. \"A unified lottery ticket hypothesis for graph neural networks.\" ICML 2021.\n\n[2] Bo Hui and Da Yan and Xiaolong Ma and Wei-Shinn Ku, Rethinking Graph Lottery Tickets: Graph Sparsity Matters, ICLR 2023", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The authors introduce a novel perspective for addressing the graph OOD problem, graph sparsification. \n2. The proposed method, *PrunE*, demonstrates significant performance improvements over a wide range of baseline methods in various datasets.\n3. The paper is well written, and the motivation is clear.\n\nWeaknesses:\n1. The theory in this paper is very similar to the graph lottery ticket, but the related works are not cited.\n2. Graph sparsification is a large research area. The proposed *PrunE* leverages a very basic method, and according to the basic theory, other graph sparsification methods may also work in an OOD scenario. However, this is not noted in the paper.\n3. There is a typo in Table 2. The reported number is EC50-assay instead of EC50-sca.", "was_revised": true, "final_justification": "During rebuttal, the authors directly respond to my concerns and clarify the connection and distinction between the proposed method and graph sparsification. Considering the empirical significance and technical soundness of this method, I vote for Accept.", "rebuttal": "Thank you for your constructive feedback! Please see below for our responses to your comments and concerns.\n\n> **W1 & Q1: Connection to lottery ticket and graph sparsification.**\n\n__Response:__ We thank the reviewer for kindly drawing our attention to the graph lottery ticket and graph sparsification literature. After carefully reading the papers mentioned by the reviewer, we agree that graph sparsification and lottery ticket approaches share some high‑level conceptual similarity with our work, in that they both prune edges in the graph. We have cited the papers pointed out by the reviewer, along with other relevant studies in recent years in this area. However, we wish to clarify that while both PrunE and graph‑sparsification methods perform edge pruning, their objectives and optimization paradigms are fundamentally different from PrunE:\n\n1. **Motivation & Goal**  \n   - Graph sparsification methods are driven by scalability concerns in node‑ or link‑level tasks on large‑scale graphs. The objective is to prune as many edges and model parameters as possible while maintaining predictive performance, which is backed up by graph lottery ticket hypothesis.\n   - In contrast, PrunE, and graph‑level OOD work in general, targets graphs of at most a few thousand nodes and computational bottleneck is not a primary concern. Our goal is to remove spurious edges so that the remaining graph retains the invariant subgraph, thereby improving OOD generalization.\n\n2. **Technical differences**  \n   As the motivation and goal is different, the **optimization paradigms** between graph sparsification and our study are also fundamentally different:\n\n   - **Graph sparsification.** Methods such as UGS optimize continuous masks for both graph edges and model weights under an ERM loss with sparsity regularization, for instance, in [1]:\n     $$\n     \\mathcal{L}\\_{\\mathrm{UGS}}\n       = \\mathcal{L}\\bigl(\\{ m_g \\odot A, X \\}, m_\\theta \\odot \\Theta \\bigr)\n         + \\gamma_1 \\lVert m_g \\rVert_1\n         + \\gamma_2 \\lVert m_\\theta \\rVert_1,\n     $$\n     and run this iteratively until the target sparsity ratio is reached. And in [2], this is taken a step further by using a min–max formulation to optimize the edge masks, i.e., the inner maximization adversarially perturbs the graph edges, while the outer minimization adapts the model weights, makeing the subnetwork more robust. This line of work  are inspired by the *lottery ticket hypothesis*, which posits that *inside a large randomly initialized dense network lies a sparse subnetwork that can reach full performance when trained from the same initialization*, these methods apply a **rewinding operation** to prune a portion of weights and edges and reset the surviving parameters to their initialization, and then retraining the sparsified model:\n     $$\n     \\min\\_{\\Theta}  \\\\mathcal{L}\\_{ERM}\\bigl(\\{ m_g \\odot A, X \\}, m_\\theta \\odot \\Theta_0 \\bigr),\n     $$\n     where $m_g, m_\\theta$ are the learned masks and $\\Theta_0$ is the initial dense parameter set. Backed by lottery ticket hypothesis, this sparsified subnetwork can often preserve the predictive accuracy of the dense model at high sparsity.\n\n   - **PrunE.** In contrast, our method follows the optimization framework commonly adopted in OOD studies, where the ERM loss is explicitly regularized to encourage invariance: $\\\\mathcal{L}\\_{\\Theta}= \\\\mathcal{L}\\_{ERM}(\\Theta) + \\\\lambda \\\\mathcal{L}\\_{OOD}(\\Theta)$.  While prior OOD methods design $\\mathcal{L}\\_{OOD}$ to directly learn invariant features (e.g., by minimizing variance across domains), PrunE is inspired by the observation that directly learning invariant features is error-prone. Instead, we propose $\\mathcal{L}\\_e$ (graph size constraint) and $\\mathcal{L}\\_s$ ($\\epsilon$-probability alignment) as $\\mathcal{L}_{OOD}$ terms, which regularize ERM to prune spurious edges. This indirect approach makes it easier to preserve the invariant subgraph under distribution shifts.\n\nIn summary, although graph sparsification and PrunE both involve pruning edges, they are inspired by different motivations and adopt fundamentally distinct optimization paradigms. Graph sparsification seeks compact subnetworks for efficiency, which is backed up by graph lottery ticket hypothesis; whereas PrunE leverages pruning as a regularization strategy to suppress spurious edges and thereby improve OOD generalization.  \n\nGiven these similarities and differences, we have included more discussions on graph sparsification and the graph lottery ticket hypothesis in the appendix. We sincerely thank the reviewer again for highlighting this important line of research, which helps us further clarify the positioning and contributions of our work.\n\n> **W2: Typos.**\n\n__Response:__ We appreciate the reviewer’s careful review. The typos have been corrected in the revised version.\n\n---\n\nWe sincerely thank the reviewer for the careful review and insightful feedback. We hope that our responses have adequately addressed your concerns regarding our work. Please let us know if there is anything we could further discuss, your further feedback would be greatly appreciated.\n\n\n**References**\n\n1. Chen, Tianlong, et al. \"A unified lottery ticket hypothesis for graph neural networks.\" ICML 2021.\n\n2. Bo Hui and Da Yan and Xiaolong Ma and Wei-Shinn Ku, Rethinking Graph Lottery Tickets: Graph Sparsity Matters, ICLR 2023"}, {"review_id": "WLIfuNQygU", "reviewer": "Reviewer_hmUG", "summary": "The paper introduces PrunE, aiming to improve out-of-distribution (OOD) generalization in Graph Neural Networks (GNNs). Specifically, instead of directly identifying invariant subgraphs, PrunE, focuses on pruning spurious edges from the graph, employing two main regularization terms, i.e., graph size constraint and probability alignment: Forces the lowest K% of edge probabilities toward zero, further reducing the presence of spurious edges. Theoretical analysis and extensive experiments on both synthetic and real-world datasets seem to demonstrate the effectiveness of the proposed method.", "questions": "Please refer to my summary of weakness.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The strengths of this paper can be summarized as follows:\n\n+ PrunE introduces an intuitive and simple learning paradigm for OOD generalization in graphs: rather than directly identifying invariant subgraphs, it prunes spurious edges. The method is conceptually simple, with only two lightweight regularization terms, making it easy to implement and tune.\n\n+ In addition, by operating directly in the input space and pruning explicit edges, PrunE offers clear interpretability: the retained subgraph after pruning highlights the parts of the graph most relevant to the prediction. Additionally, the method is computationally efficient, with runtime and memory overheads comparable to standard ERM and lower than many other OOD methods.\n\nMeanwhile, this paper also has the following weakness:\n\n- It seems counterintuitive to model the edges in the graph independently.\n\n- The simplicity of the method is both a strengths and weakness. The two regularization terms seem ad hoc, where the motivation of combining them together need to be further enhanced in the paper.", "was_revised": true, "final_justification": "I have carefully read the rebuttal and will maintain my positive score.", "rebuttal": "Thank you for your constructive feedback! Please see below for our responses to your comments and concerns.\n\n> **W1: Modeling edges independently.**\n\n__Response:__  We thank the reviewer for the thoughtful comment and we agree that modeling graph edges independently may appear counterintuitive at first glance. However, this design choice is supported by both practical and theoretical considerations:\n\n  - **Simplification for analysis and implementation.** Modeling edge probabilities independently allows for a **tractable formulation** of the subgraph selector, which greatly simplifies both the **theoretical analysis** (e.g., generalization bounds) and the **optimization pipeline**. Specifically, we can employ a GNN encoder followed by an MLP to estimate the probability of each edge in a differentiable manner.\n  - **Consistency with prior literature.** This assumption is also aligned with many previous work in graph invariant learning [1-4] and GNN explainability [5-6], where edge probabilities are also modeled independently. This common design pattern in prior studies further justifies the validity of our modeling choice.\n\n\n> **W2: Justification of the two regularization terms jointly.**\n\n__Response:__ As discussed in Lines 177–190 of the draft, the graph size constraint loss $\\mathcal{L}_e$ effectively prunes many spurious edges but cannot guarantee that *all* such edges retain low probability scores. This leads to high variance across runs. To address this, we introduce the $\\epsilon$‑probability alignment loss $\\mathcal{L}_s$, which explicitly suppresses the spurious edges. \n\nFigure 3(a) in our draft shows that combining $\\mathcal{L}_e$ and $\\mathcal{L}_s$ yields both reduced variance and improved test performance, whereas removing either term results in larger variance and degraded results. This justifies our joint‑regularization design. \n\n---\n\n\nWe sincerely thank the reviewer for the careful review and insightful feedback. Please let us know if there is anything we could further discuss, your further feedback would be greatly appreciated.\n\n\n**References**\n\n1. Wu, et al., Discovering invariant rationales for graph neural networks, ICLR 2022.\n\n2. Chen, et al., Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs, NeurIPS 2022.\n\n3. Sui, et al., Unleashing the Power of Graph Data Augmentation on Covariate Distribution Shift, NeurIPS 2023.\n\n4. Gui, et al., Joint Learning of Label and Environment Causal Independence for Graph Out-of-Distribution Generalization, NeurIPS 2023.\n\n5. Ying, et al., GNNExplainer: Generating Explanations for Graph Neural Networks, NeurIPS 2019.\n\n6. Luo, et al., Parameterized Explainer for Graph Neural Network, NeurIPS 2020."}, {"review_id": "ylwsQgajJL", "reviewer": "Reviewer_S6ZW", "summary": "The paper proposes a graph OOD generalization algorithm via graph pruning. The motivation is that the key of OOD generalization is to identify the invariance parts (subgraphs) but some sprious edges prevent the model find the true invariant subgraphs. Thus, the authors want to prune these edges to let the model better understand the invariances in the graph.", "questions": "1. Do the authors can provide an in-depth analysis to show whether the sprious edges would be the key limitation in identifying the invariant subgraphs and why the edge pruning be the most suitable strategy?", "limitations": "See weaknesses.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper is easy to follow and well-written.\n2. The motivation of pruning sprious edges seens to make sense. \n3. The theoretical analysis further reveals the superiority of the method. \n\nWeaknesses:\n1. Despite the authors claim sprious edges is a significant issue in identifying key subgraphs, they do not provide an analysis on how and why it happen. \n2. Following the previous one, the authors also do not clearly answer why the edge pruning could be suitable to handle the issue. Do there have any other strategies?", "was_revised": true, "final_justification": "This work provides a novel method in solving graph OOD problem. It shows an elegant method with strong theoretical basis, with desirable performance. I think the paper is above the bar of the NeurIPS.", "rebuttal": "Thank you for your constructive feedback! Please see below for our responses to your comments and concerns.\n\n---\n\n> **W1: How and why spurious edges arise.**\n\n__Response:__ We appreciate the reviewer’s question. Spurious edges occur **naturally** in many real‑world domains due to the way data are collected or generated. Below we provide three concrete examples to illustrate this phenomenon:\n\n- **Molecular property prediction (e.g., GOOD-HIV [1]).** In molecular graphs, nodes represent atoms and edges represent chemical bonds. The *invariant* subgraphs are functional groups (e.g., –OH, –COOH) whose chemical bonds (edges) causally drive HIV inhibition. The *spurious edges* come from bonds forming large ring scaffolds or linking atoms that increase overall molecular size. These edges co‑occur with labels in training data because scaffolds and larger molecules are overrepresented among active compounds, even though these bonds are not causally responsible for inhibition.\n\n- **Social‑media analysis (e.g., Twitter15/16, PHEME [2]).** In rumor‑propagation graphs, nodes are users and edges represent retweet/reply interactions. The *invariant* structures are propagation paths (edges) that genuinely reflect veracity‑related user engagement. By contrast, *spurious edges* are event‑specific retweet links that form distinctive motifs, such as in PHEME’s Hurricane Sandy thread where retweet edges from `@WeatherNews` to `@StormTracker` and `@CityNews`, and then to `@LocalReporter`, form a Y‑shaped cascade. These edges are unique to that event and spuriously correlate with rumor labels without causal relation to truthfulness.\n\n- **Brain‑network studies (resting‑state fMRI [3,4]).** In functional connectivity graphs, nodes are brain regions and edges represent statistical correlations between BOLD (Blood‑Oxygen‑Level‑Dependent) signals. The *invariant* edges correspond to genuine neural interactions. The *spurious edges* are those inflated by head‑motion artifacts, such as correlations between frontal poles caused by micromovements. These edges often co‑vary with demographic or diagnostic variables, misleading models into associating motion‑induced noise with disease labels.\n\nThese examples show that spurious edges are not artificially imposed but are an inherent **byproduct** of real‑world data collection processes, which further justifies our pruning‑based approach for graph OOD generalization.\n\nTo be more self‑contained, we have added a discussion in the appendix explaining why and how spurious correlation arise and how they impact OOD performance. \n\n> **W2: Why edge pruning is suitable.**\n\n**Response:** The key reason why edge pruning is suitable for OOD generalization is that, as shown in Section 3 of our paper, state‑of‑the‑art methods that directly attempt to identify invariant edges are error‑prone: spurious edges with strong label correlations are often **misclassified** as invariant, leading to incomplete or incorrect estimation of the true invariant subgraph. In contrast, pruning a subset of spurious edges provides a more reliable way to preserve $G_c$, making it easier to retain the invariant structure. This is why pruning spurious edges is particularly suitable for enhancing OOD generalization ability.  \n\nIndeed, there exist many other strategies and methods in the graph OOD literature that address this challenge through alternative strategies, including supervised contrastive learning, data augmentation, information bottleneck, and other regularization‑based techniques. However, all of these methods focus on directly identifying invariant edges; none of them explicitly leverage **edge pruning** as a means to improve OOD generalization. PrunE is the first to explore this pruning‑based paradigm, and both our theoretical analysis and empirical results demonstrate its effectiveness compared to prior approaches. \n\n\n> **Q1: The necessity of pruning spurious edges.**\n\n__Response:__ We thank the reviewer for this perceptive question. Please see our response below:\n\n### **1. Spurious edges as the core limitation**\n\nIt is widely acknowledged that *spurious subgraphs* are a primary driver of poor generalization in graph OOD literatures. For instance, in molecular property prediction, GNNs often exploit ring scaffolds or overall molecule size for prediction, which correlate with training labels but lack causal effect on target labels.\n\nAs demonstrated in Section 3 of our draft, state‑of‑the‑art methods that attempt to *identify invariant edges* tend to misclassify spurious edges as “causal edges”, leading to incorrect subgraph estimation and degraded OOD performance. This implies that spurious edges are the key limitation for current SOTA methods to estimate invariant subgraphs accurately. \n\n### **2. Pruning as the most suitable strategy**\n\nWhile it is challenging to rigorously prove that pruning is the most effective (optimal) way, our experiments show that PrunE significantly outperforms a broad range of general and graph OOD approaches that seek to directly identify invariant edges, on both synthetic and real-world splits. Moreover, our OOD regularization is conceptually simple and insensitive to hyperparameter variations, further underscoring the potential and practical appeal of the pruning paradigm.\n\nTogether, these points illustrate why **pruning spurious edges** is especially effective in OOD settings for graph-structured data. \n\n\n---\n\nWe sincerely thank the reviewer for the careful review and insightful feedback. We hope that our responses have adequately addressed your concerns regarding our study. Please let us know if there is anything we could further discuss, your further feedback would be greatly appreciated.\n\n\n**References**\n\n1. Gui, et al., GOOD: A Graph Out-of-Distribution Benchmark. NeurIPS 2022.\n\n2. Wu, et al., Probing Spurious Correlations in Popular Event-Based Rumor Detection Benchmarks, arXiv:2209.08799.\n\n3. Satterthwaite, et al., Motion artifact in studies of functional connectivity: Characteristics and mitigation strategies, Human Brain Mapping.\n\n4. Xu, et al., BrainOOD: Out-of-distribution Generalizable Brain Network Analysis. ICLR 2025."}]

Author rebuttal:

Meta-review: The paper addresses the critical challenge of out-of-distribution (OOD) generalization in GNNs by pruning spurious subgraphs—structures correlated with labels but not causally relevant. The proposed method, PrunE, employs a causal framework with counterfactual reasoning and a simple yet effective pruning strategy supported by two regularization terms. The approach is conceptually clear, computationally efficient, and interpretable, as pruning occurs in the input space. Extensive experiments on synthetic and real-world datasets show strong and consistent improvements over baselines. 

Reviewers appreciate the well-motivated problem, clear writing, novel method, and thorough empirical validation. Weaknesses include limited discussion of real-world prevalence of spurious subgraphs, incomplete comparison with other sparsification and explanation methods, and the need for stronger justification of design choices. Despite these, the paper makes a meaningful contribution to OOD robustness in graph learning.
Decision: Accept (poster)