Learning Graph Invariance by Harnessing Spuriosity
Authors: Tianjun Yao
Yongqiang Chen
Kai Hu
Tongliang Liu
Kun Zhang
Zhiqiang Shen
Venue: ICLR 2025 Poster (2025)
Keywords: Out-of-Distribution Generalization
Invariant Learning
Graph Neural Networks
Primary area: learning on graphs and other geometries & topologies
TL;DR: We investigate the advantages of learning graph invariant features indirectly over existing OOD methods, and propose a learning framework that adopts this indirect learning paradigm for graph OOD generalization.

Abstract: Recently, graph invariant learning has become the _de facto_ approach to tackle the Out-of-Distribution (OOD) generalization failure in graph representation learning. They generically follow the framework of invariant risk minimization to capture the invariance of graph data from different environments. Despite some success, it remains unclear to what extent existing approaches have captured invariant features for OOD generalization on graphs. In this work, we find that representative OOD methods such as IRM and VRex, and their variants on graph invariant learning may have captured a limited set of invariant features. To tackle this challenge, we propose $\texttt{LIRS}$, a novel learning framework designed to **L**earn graph **I**nvariance by **R**emoving **S**purious features. Different from most existing approaches that _directly_ learn the invariant features, $\texttt{LIRS}$ takes an _indirect_ approach by first learning the spurious features and then removing them from the ERM-learned features, which contains both spurious and invariant features. We demonstrate that learning the invariant graph features in an _indirect_ way can learn a more comprehensive set of invariant features. Moreover, our proposed method outperforms the second-best method by as much as 25.50% across all competitive baseline methods, highlighting its effectiveness in learning graph invariant features.

Published as a conference paper at ICLR 2025
LEARNING GRAPH INVARIANCE BY HARNESSING SPURIOSITY
Tianjun Yao
Yonggiang Chen
Kai Hu?
Tongliang Liu
Kun Zhang!?
Zhiqiang Shen'
Mohamed bin Zayed University of Artificial Intelligence
2 Carnegie Mellon University
The University of Sydney
{tianjun. yao, yonggiang. chen @mmzuaai combzuai.ac.at ac. ae, kaihuêcs, cmu, edu
tongliang. leleeluuueeee edu. au, (kun zhang, zhiqiang. Aebzuaii ae
ABSTRACT
Recently, graph invariant learning has become the de facto approach tackle the Out-of-Distribution (OOD) generalization failure in graph representation learning. They generally follow the framework of invariant risk minimization capture the invariance of graph data from different environments. Despite some success, it re- mains unelear to what extent existing approaches have captured invariant features for OOD generalization on graphs. In this work, we find that representative OOD methods such as IRM and VRex, and their variants on graph invariant learning may have captured limited set of invariant features. To tackle this challenge, we propose LIRS, a novel learning framework designed to Learn graph Invariance Removing Spurious features. Different from most existing approaches that di- rectly learn the invariant features, LIRS takes an indirect approach by first learning the spurious features and then removing them from the ERM-leamed features. We demonstrate that learning the invariant graph features in an indirect way enables the model capture a more comprehensive better OOD generalization performance in novel environments. Notably, LIRS surpasses the second-best method by as much as 25.50% across all competitive baselines, underscoring its efficacy in OOD generalization.
of invariant features, leading
INTRODUCTION
Graph representation learning with graph neural networks (GNNs) (Kipf & Welling 2017 Xu al., 2019 Veličkovíć et al. (017) has proven to be highly successful tasks involving relational in- Formation (Qiu al.J 2018) Wu al. 2022b) Yu al. 2018 Zhang et al. (022c). Despite their achievements, GNNs often assume that the training and test data share the same distribution. This assumption often does not hold in real-world applications (Hu al. 2020 Huang al., 2021 Ji et al. 2022, Koh et al. 2021) due to changes in the underlying data generation process, leading to distribution shifts. Such phenomenon can severely degrade the performance of GNN models, which
presents critical challenge for their deployment in practical scenarios (DeGrave et al. 2020).
To address the OOD generalization challenge, graph invariant learning has become the de facto ap- proach. Inspired by the success of invariance principle (Arjovsky et al., 2020 Kreuzer et al.) [021]
graph invariant learning aims to identify invariant subgraphs that are causally related with the tar-
gets Yang et al. 2022 Li al. 2022b Liu al. 2022; Zhuang al. 2023 Chen et al., 2022
ct al. 2022a). Typically, they follow the framework of Invariant Risk Minimization (IRM) (Arjovsky al. 2020 or Variance-Risk Minimization (VRex) (Krueger et al.] 2021). which aim capture in-
variant features by learning an equipredictive classifier across different environments. Despite some success, many graph invariant learning methods only perform similarly compared to the traditional Empirical Risk Minimization (ERM) (Vapnik) 1995) in graph OOD benchmarks (Gui et al. 2022
raises a critical yet overlooked question:
To what extent do the graph invariant learning algorithms capture the graph invariance?
"ooee available at httpp////////hhhh.c.o//o/a//a/aa ICI,2205

---

Published as a conference paper at ICLR 2025
In this work, address this question by investigating two representative OOD algorithms, namely IRMv1 (Arjovsky et al. 2020) and VRex (Kreuzer et al. 2021). in graph-level OOD classification scenarios. These algorithms are widely used, and many graph invariance learning algorithms based on their variants or extensions (Li et al. 2022h Liu et al. 2022 Zhuang et al. 2023 Wu et al., 2022c). Surprisingly, we find that TRM, Rex and their variants on graph invariant learning may only learn subset of invariant features (Sec. B). In contrast, the learning paradigm that learns invariant features indirectly by removing spurious features from the ERM-leamed features may render learning more comprehensive set of in-
variant features ( and Sec. 3}. Motivated by this observation, we propose novel learning framework LIRS: Learning graph Invariance by Removing Spuriosity. Different from most exist- ing approaches that directly learn the invariant fea- tures, LIRS adopts the indirect learning paradigm. Specifically, LIRS first leverages the biased info- max principle (Def. 3) to effectively learn graph spuriosity (Theorem 4.1). then employees class- conditioned cross entropy loss to effectively learn graph invariance 4.22 Extensive experi- ments on synthetic datasets demonstrate that LIRS is able to learn more invariant features compared to state-of-the-arr graph invariant learning methods that adopt the direct invariant learning paradigm. Furthermore, LIRS shows superior OOD perfor- mance real-world datasets with various types of distribution shifts, highlighting its effectiveness in learning graph invariant features. Our contribu- tions can be summarized as follows:
[a] Invariant learning directly
GNN Encoele
h
Aspu
h1.
Apisent
(b) Inveriant learning indirectly
Figure 1: Illustration of the two graph invariant learning paradigms. Compared with the invari- ant learning methods Ar that adopt the direct learning paradigm, our proposed method first adopts spuriosity learner Aspu to learn spu- rious features, then learns invariant features by removing the spurious features using the fea- ture disentanglement module ADieent.
We reveal that learning invariant features indirectly i.e., by first learning and then removing spurious features, can be more effective in capturing invariant features than existing (graph) invariant learning algorithms that learn invariant features directly.
We propose LIRS, novel framework that adopts the indirect learning paradigm for learn- ing invariant features, which consists of: a) The biased infomax principle, a contrastive learning algorithm that provably learns graph spuriosity; b) class-conditioned cross-entropy loss, a learning objective that effectively learns graph invariance by removing spurious fea- tures from ERM-leamed features.
Extensive experiments demonstrate that LIRS outperforms second- baseline methods by up 25.50% across 17 competitive baselines on both synthetic and real-world datasets with various distribution shifts.
2 PRELIMINARY
Notations. An undirected graph G with n nodes and m edges is denoted by := EV,E), where is the node set and & is the edge set. G is also represented by the adjacency matrix A and the node feature matrix X E R with D feature dimensions. We use Ge and G, to denote invariant and spurious subgraph for graph G respectively, and h. and h, invariant and spurious features in the latent space. h, and he denote the estimated representations for node U; and graph G respectively. Finally, we use [K] == {1,2 2....... ... K) to denote an index set, w to denote a scalar value, w to denote vector, W to denote matrix, W to denote a random variable, and W to denote a set. more complete set of notations is presented in Appendix A
Problem Definition. We focus on OOD generalization in graph classification hidden environ- ments. Given a set of graph datasets DD {g Jeee, GNN model f. denoted as p h, comprises an encoder h G > R.F that learns a representation h& for each graph G, followed by Y to predict the label Yū p(hc). The objective of OOD generalization on graphs is to learn an optimal GNN model f*(.) G - Y using data from train- ing environments Drr {g*) Joee, that effectively generalizes across all (unseen) environments:
downstream classifier p : RF
2

---

Published as a conference paper at ICLR 2025
f(() arg m &u R(f e), where Rff e) ((f() Y)] is the risk of the predic- tor f on the environment and ((:-)) Y Y + R4 denotes loss function.
Assumption 1. (Stable and predictive subgraphs) Given a graph G E D, there exists a set of stable (causal) substructure patterns Ge for every class label Y = y, satisfying: a) Ve, el E Etr, Ge
Ge: Ip (Y G.) = pp' (Y G.); and b) The target Y can be expressed as Y = = (G.) + where LL G represents random noise, and 1 indicates statistical independence.
Assumption | posits that one or more substructure patterns in G. are not only stably associated with the target label Y across different environments but also possess sufficient predictive power to accurately determine Y. This assumption is well-aligned with real-world scenarios. For instance, in the GOODHIV dataset (Gui et al., 2022 Hu et al. 2020 Wu et al., 2018). molecule's ability to inhibit HIV may depend on the presence of several functional groups interacting with various parts of the virus. Moreover, recent study also provides empirical evidence for graph applications, suggesting that multiple substructures remain stable and predictive of the targets (see Appendix E.2 Therefore, when the OOD algorithms are able to learn a broader set of invariant substructures (features), they will generalize more effectively across different environments.
in Bui et al. (2024)), thereby supporting the validity of Assumption [
3 WHY LEARNING INVARIANT FEATURES INDIRECTLY?
In this section, we motivate our study by addressing the ques- tion: Why might learning invari- ant features indirectly be more effective thun learning them di- rectly? We begin by presenting an intuitive hypothesis related to our research question, followed by an empirical study syn- thetic datasets to support this hy- pothesis. Consider dataset D where each sample ())) com-
40
(So 032
Vise 0.31 CASA (LD
35 21:122
GIEA
30 Dux
Dun D.1
28
25
20
10
..s -0.4 -02
0.0
0.2
0.4
0.6
d8
1.0
..8 .0.4 .02
0.0
0.2
0.4
0.6
0.8
1.0
Apm
SPMotif-0.40
SPMoti-0.60
Figure 2: Comparison of the distribution P Arob across different OOD algorithms.
prises invariant features (h (1 and spurious features {h (t) 19, s.j 1=1 with n. and n, denoting the number of invariant and spurious features respectively. Any subset of the invariant features (h()) 1he maintains stable relationships with Y, consequently OOD objectives that aim directly learn invariant features (e.g.. IRMv1 and VREx) may only capture a subset of these invariant fea- tures if a subset of invariant features can already achieve accurate predictions in the training set. In contrast, an OOD objective that seeks to remove the spurious features {h (6) )= from the ERM- learned features may result in learning a more complete set of invariant features from (h 1n. 1==1> thus facilitating OOD generalization unseen environments.
Empirical Study. To validate our hypothesis that learning invariant features by removing spurious features may facilitate learning more invariant features, we perform experiments using variant of SPMotif datasets (Wu et al. 2022cc Ying et al. 2019). Specifically, for each sample three invariant subgraphs are attached to the base spurious subgraph the training and validation sets. In the test dataset, we perform model inference and record the estimated probability for correctly predicted samples, denoted as v/.) Subsequently, we randomly removed two invariant subgraphs from these
samples and compute the new estimated probability score, denoted as g( We then fit the distribu- tion PApres using Kernel Density Estimation (KDE) (Terrell & Scott 1992). based on the changes
in probability Aprob g. y
(i) Vi,j. illustrated in Figure 2 If the encoder h(-) can in- deed learn all invariant features in the test set, then removing two invariant subgraphs should not
(5) Therefore, the closer P PA,,..s is to O, the more it indicates that the encoder has learned the full set of invariant features. In addition to the density function of Aprot- we also calculate the Wasserstein distance of each algorithm to null distribution, where the probability mass is entirely centered at O. As demonstrated in Figure IRMv1 (Arjovsky et al. 2020) and VRex (Krueger et al.) 202T) exhibit significant changes in A prob. implying that for some samples, IRMv1 and VRex learn
change 5/
3

---

Published as a conference paper at ICLR 2025
only subset of the invariant patterns. GIL (Li al. 2022b) and GREA (Liu al. 2022 two variants of VRex and IRM that learn invariant features directly by performing environment infer- ence and environment augmentation respectively. As shown in Figure 2 the Wasserstein distances for GIL (Li et al. 2022b) and GREA (Liu et al.) 2022) are also greater than that of our proposed method. This highlights the advantages of the learning paradigm that indirectly learns invariant features by first learning and then removing spuriosity. However, one may raise concerns that while learning invariant features by first removing spurious fea- tures may indeed lead to capturing a more complete set of invariant features for the correctly predicted samples, it may also introduce spurious patterns if the spurious features are not effectively removed, which could render such a learning paradigm suboptimal in practice. To ad- dress this concern, we report test accuracy under vary- ing strengths of spurious correlations, following previous experiments. As the strength of the spurious correlation increases, it becomes more challenging eliminate the spurious features. From Figure 3 we have three observa- tions: a) Our method consistently achieves superior OOD performance across different correlation strengths; b) Our method is less sensitive to the increased spurious corre- lations compared to other representative OOD methods, which is evident by the flatter curve in Figure 3 c) The higher test accuracy, combined with the distribution of probability changes from the previous experiment, suggests that our method enables a larger num- ber of test samples to learn more complete set of invariant features. Based on these observations and analysis, we conclude that indirectly learning invariant features is more effective than learning them directly.
62.5
60.0
57.5
Accuracy
52.5
50.0
IRM
VRex
45.0
GREA
Curs
0.5
0.6
0.7
0.8 6.9
Spurious correlation strengths
Figure 3: Test accuracy under vary- ing spurious correlation strengths of the variant of SPMtoif datasets.
4 METHODOLOGY
Motivated by the observations in Sec. 3 we now introduce our proposed LIRS framework, which learns invariant features on graphs indirectly.
4.1 LEARNING GRAPH SPURIOSITY VIA BIASED INFOMAX
The first step of learning invariant features in the LIRS framework is to effectively learn graph spuriosity. In this section, we first propose variant of the infomax principle (Hjelm et al. 2019 Veličković et al. 2019 Linsker 1988), namely biased infomax, which encourages spuriosity learn- ing by suppressing invariant signals. We then present a more practical version of biased infomax, suitable for the real-world datasets. We first formally define spuriosity learning in below:
Definition 1. (Spuriosity Learning) Assuming each data instance ( in a dataset 'D is composed of two parts he and ()) an algorithm A is said to be spuriosity learner if (i) A(G()), Vi, ie., A learns only the spurious features for all instances in D.
One such algorithm to encourage spuriosity learning is the global-local infomax principle (Hjelm) ctt al. 2019 Veličković et al. 2019 Linsker 1988), which maximizes the mutual information (MI) between global representation and local node representations, as defined in the following: Definition 2. (The Infomax Principle) The infomax principle optimizes the following optimization objective in Eqn. I w.r.t the GNN encoder ho(.).
1 Σ1 (f. G
max Eo-S
s.t. h, ho(G), READOUT
(I)
WEG
The encoder ha(-) will primarily learn spurious features Yao et al. 2024). However, it will still increases, the learned global representation hi will increasingly capture invariant representations Yao et al. 20244.. To mitigate this constraint and further facilitate spuriosity learning, we propose the biased infomax principle.
be constrained by [Gel, the size of the invariant subgraph. As IG.
4

---

Published as a conference paper at ICLR 2025
Definition 3.
(The Biased Infomax Principle) The biased infomax principle optimizes the following optimization objective in Eqn. 2 w.r.t the GNN encoder he (.).
(5 NeEGG
(he, (ha, ) s.t. h, = -ho(G), He READOUT(hh)
max R |G|
(hg ho) I
Σ EG
(2)
By maximizing MI across nodes U; E G2 and minimizing MI across nodes v4 E Ge. the biased infomax principle yields encoder he- (-) that encourages the learning of spurious patterns while suppressing invariant ones. Formally, we can demonstrate that the biased infomax principle achieves spuriosity learning.
Theorem 4.1. Given that the invariant subgraph Ge contains invariant patterns that are causally related to the target labels, and G, contains only spurious patterns, the biased infomax principle achieves spuriosity learning, i.e., the encoder hg- (+) learns solely the spurious features for each data sample G in D.
To achieve invariant learning by removing spuriosity, it is crucial to effectively learn the spurious features first. Theorem demonstrates that the biased infomax principle can learn graph spuriosity more effectively the vanilla infomax, as defined in Def. 2 However, in real-world scenarios, Ge is often unobservable, which hinders the practicality of the biased infomax principle. To make the proposed algorithm more practical, we propose an instance-level adaptive biased infomax, which incorporates a GNN explainer to identify the important nodes first, and then performs instance-wise counterfactual inference to determine whether the selected nodes should be biased not.
Instance-level adaptive biased infomax. At first glance, the biased infomax principle appears impractical due to the necessity of knowing Ge and G.. To address this limitation, we employ an approximation algorithm identify G., which serves nodes 2 E Ge to realize the biased infomax principle. In practice, we utilize GSAT (Miao al, 2022 a GNN explainer e(.) that is robust under distribution shifts, to identify G. and G. = G. Nevertheless, the approximation error may inadvertently bias the algorithm by amplifying invariant signals and suppressing spurious ones, as demonstrated in the following proposition.
estimate for Ge- Subsequently, we treat
Proposition Given an error rate p% in the approximation algorithm for Ge. i.e. Go contains 1-p% nodes from G. and p% nodes from G., let the learning objectives for the biased infomax with the ground-truth subgraphs Ge and G, and with the approximated subgraphs Ge and G2 be denoted as L(A"; D) and ; DD respectively. The difference between L(0"; ; (D) and L(B'; DD) can be expressed as:
2 Gl
Σ I (ba EED
Σ ((n:ffic) NEENG.
Eg-Ø
Here pG denotes p% nodes in graph G. When hng learns primarily spurious features, / (h:; haa
I (hy:he). Ve, E G., E Ge. then Prop. I implies that as p% increases, the gap between the ground-truth learning objective and the learning objective with approximation will also increase, thus leading to inaccurate graph representations. To reduce the approximation error and mitigate this issue, we conduct counterfactual inference for graph G by evaluating the changes in predicted probability with and without G, derived from the GNN explainer. Assuming G. = e(G, Y' closely approximates the ground-truth Gz, the removal of G_ should result in significant change in the predicted probability score. Under this condition, for graph G, bias v, G.. Otherwise, employ vanilla infomax without the bias operation. Specifically, we use pre-defined threshold т. For each graph data instance
=(6) denote the predicted probability (1)) with target label j. let of5") and y;
scores before and after the removal of G., respectively, We then bias the infomax for graph (Oi) if
(s) v > - using Eqn. 2 otherwise, we use Eqn. learn the graph representation.
5

---

Published as a conference paper at ICLR 2025
4.2 LEARNING GRAPH INVARIANCE VIA CLASS-CONDITIONED CROSS-ENTROPY LOss
class-conditioned cross-entropy loss. So far we have obtained the spurious graph representations h, for every instance G in the dataset. Next we consider how to learn graph invariance by re- moving the spurious features from ERM-learned representations. To solve this challenge, previous study (Yao et al., 2024) takes spurious features h, and target label Y as inputs to train a linear classifier using cross cross-entropy loss to obtain the logits, which capture spurious correlation for each sample G, and use these (spurious) logits for subsequent spurious feature removing. Although the input only contains spurious features, we argue that: The logits generated may be inaccurate to cap- ture the spurious correlation strengths due to the overlapping of spurious patterns across different classes. To see this, we propose Prop. to demonstrate this issue:
Proposition 2. Given a linear regression model with parameters {01,02 02, and spurious features {I1, 12), the correlation strength for feature I1 is p and for 22 is 1 p when Y = 0. Similarly, the correlation strength for feature 21 is q and for 222 is 1 when Y = 1. Assuming the spurious features 1ı and x2 can each take values in {0, },, we obtain the following parameter estimates using Mean Squared Error (MSE) loss: 01
p+4" 02
--
Prop. 2 demonstrates the issue brought by the interference of overlapping spurious features across different classes. For instance, when p q. 01 = 0g = 1. the generated logits fail to distinguish different spurious patterns. To mitigate this issue, we propose class-conditinned cross-entropy loss.
Specifically, we first perform clustering within each class based on the spurious features (h. (1) J The resulted clusters will reflect different spurious patterns and environments accurately given the spurious features learned by the biased infomax objective. However, employing hard labels can result in loss of information regarding the relative positions of samples within a cluster. To address this, we refit a linear classifier using the cluster labels as targets. This approach ensures that samples near the cluster boundaries exhibit higher entropy their spurious logits, thereby preserving the information about their position within the cluster. Given the estimated spurious logits s R k with K clusters in each class, we propose the following learning objective for spurious feature removing:
K w w 60) log (o(5 s.t., 8(), = pp(( ERK
Linv ;= Ey-- E Σ
(3)
Here, a.) denotes the softmax function, p((-) : R.F RC represents the clustering classifi- cation head, which takes hig from the GNN encoder h--) as input. The reweighting coefficient for each sample ())) is denoted as w()), which adjusts the weight for samples from the majority group by reducing it and increases the weight for samples from the minority group. The general-
ized cross-entropy (GCE) method (Zhang & Sabuncu 2018 is employed to calculate w(O), i.e.,
()) (
where j is the ground-truth clustering label for sample G and ς hyper- parameter. Finally, The loss objective for feature disentanglement is:
L= + XLinus
where LoT denotes the ERM loss. Line, serving as a regularization term, will guide the learning process to learn invariant features by removing spurious features from the EeM-leared features. Formally, we present the following theorem.
Theorem 4.2. There exists a suitable & and clustering number K, such that minimizing the loss objective C = LeT + XLinv will lead to the optimal encoder he (-) which elicits invariant features for any graph G. i.e., he h (G) he-
The proof is included in Appendix D In the proof of Theorem 4.2 we show that Cine will guide the ERM- features to focus on invariant features by removing or unlearning the spurious ones. More concretely, given ERM learns both invariant and spurious features (Kirichenko et al.) 2023 Chen et al. 2023b), i.e., hō = k(h,, h2), where x(-) is a functional mapping to graph representation hg given set of invariant features h. and set of spurious features h, Line regularizes the learning

---

Published as a conference paper at ICLR 2025
Table 1: Performance on synthetic and real-world datasets. Numbers bold indicate the best performance, while the underlined numbers indicate the second best performance.
GOOD-Mottf
GOOD-HIV
OGBGG-Molbace
OGBGGMMllhhhp
Method
base
size
scaffold
size
scaffold
size
scaffold
size
ERM
68.66
51.74
69.58a221
29.94_1.7
75.11
83.601347
10
18.29
IRM
70.65
51.411375
67 11
29.00
75.47.122
83.124258
67.22
77.56.2.48
GroupDRO
68.24
51.95:586
70.644257
58.98-236
66,47
+2.27
VREx
71.47=6.99
52.67+5554
70.77=284
58,53-2.88
72.81=4299
82.55+251
68. 1..03
78.76=22.7
RSC
46.12.13.6
51.701547
69.16.1325
61.17
14.59
84.34.225
69.01-2.84
78.07 133.9
DiverseModel
54.24
41.01
69.174362
61.59-223
73.48:3356
79.40
68,04-3.27
1..62
DropEdge
45.08=4446
45.63+4411
70.78+138
58.53-1.36
70.81+2112
76.39
66.49-1.55
78.32+3344
FLAG
61.12=5.9
51.661414
68.45+2.30
60.59-2.6
80.37+1.54
84.72+088
67.69
79.26=22.6
LISA
54,59=4.81
53.46#3411
70.38
52.36=1.73
78.05
83.92+2.52
68.11=0.5
78.62
DIR
62.07=x475
52.27
68. 68.07+229
58.08-2.31
75.49=2.00
77.42+743
66.86-2.25
76.40=443
DisC
51.08=108
50.39
68.07:175
58.76-0.1
57.78+36
71.13
67.12-2.11
56.59: 10.09
CAL
65.6324429
51.1815560
67.371361
57.95-2.34
76.29:1100
79.68
68.06_2.0
79.50
GREA
56.74
54.1311001
67.791255
60.71-220
77.161137
83.151907
69.72_1.66
17.34
GSAT
62.80=11.41
53,20
68 15
58.06-1.98
72.32225.6
82.45+273
66.78-144
75.63
CIGA
66.43
49.141884
69 29.40.2339
59.55_2.6
76.44
83,95
64.92_2.08
AIA
73.64...15
35.851795
71.151181
61.64_...7
79.42.1101
85.11
70.79-1.53
81.03
OOD-GCL
56.46=461
60.23:8.49
70.85
58,48-294
75,96
85.34
67.28-3,09
78. 78.11
EQuAD
67.11=10.11
59.72+36p
72.24+0044
64.19-0.56
79.15
86.41+563
70.22
80.82+55.2
LIRS
75.51
74.95
72.82:161
66.64=1.4
81,91
88.77
0..04
82.19
process to optimize x-). such that big contains only h While previous OOD methods achieve a similar goal (to learn only invariant features), our approach differs by first learning the spurious features and then leveraging them to identify the causal features from the ERM-learned features, a process we refer as spurious feature removing or unlearning.
EXPERIMENTS
In this section, we perform empirical study on both synthetic and real-world datasets. More details about the datasets and experiment setup are included in Appendix H
5.1 EXPERIMENTAL SETUP
Datasets. We adopt GOODMotif and GOODHIV datasets (Gui et al., 2022), OGBG-Molbace and DGBG-Molbbby datasets (Hu et al. 2020; Wu et al., 2018) to comprehensively evaluate the OOD generalization performance of our proposed framework. For GOODMotif datasets, adopt base shift and size shift, for OGBG datasets, in addition to scaffold shift, we also create size shift, fol- lowing previous studies (Gui al. 2022 work are included in Appendix
Sui et al. 2023). More details the datasets used in
Baselines. Besides ERM (Vapnik 1995). we compare our method against three lines of OOD
baselines: (1) OOD algorithms on Euclidean data, including IRM (Arjovsky et al.) 2020).
VREx KKueger al. 2021), and GroupDRO (Sagawa et al. 2019); (2) Diverse feature learning methods, including RSC (Huang et al. 2020), and DiverseModel (Teney et al.) 2022). (3) graph- specific OOD and data augmentation algorithms without requiring environment labels, including DIR (Wu al. 2022c). GSAT (Miao et al. (022). GREA (Liu et al. (022). DisC (Fan et al. 2022
CIGA (Chen et al.) 2022]. AIA (Sui et al. 2023), OOD-GCI (Li et al. 2024a). EQuAD ( (ao al.,
2024). DropEdge (Rong al. 2019), FLAG (Kong et al. 2022), and LiSA (Yu et al. 2023). Details of the baselines and their implementation are provided in Appendix H
Evaluation. We report the ROC-AUC score for GOOD-HIV, OGBG-Molbbbp. and OGBG- Molbace datasets, where the tasks are binary classification. For GOOD-Motif and SPMotif datasets, accuracy the evaluation metric. We run experiments 4 times with different random seeds, select models based on the validation performance, and report the mean and standard deviations on the test set.
7

---

Published as a conference paper at ICLR 2025
5.2 EXPERIMENTAL RESULTS
In this section, we report the main results on both synthetic and real-world datasets.
Synthetic datasets. LIRS achieves superior performance on GOOD-Motif, surpassing the second- best method by 12.51% (base split) and 25.50% (size split). This highlights its effectiveness in capturing domain-invarien
features. While EQuAD also removes spurious features, its infomax- based learning may inadvertently retain them, whereas LIRS's ' biased infomax effectively suppresses spurious signals. OOD-GCL (Li al. 2024a) employs contrastive learning without labeled data, making invariant feature learning more challenging. As shown in Table LIRS outperforms OOD- GCL across all datasets. benefiting from labeled data during training. We also compare LIRS with RSC et al. (2020) and DiverseModel Teney et al. (2022), which aim to learn diverse features via ERM. As illustrated in Table | although RSC and DiverseModel perform well on real-world datasets, they achieve suboptimal results on the GOOD-Mott datasets. This discrepancy may arise from the fact that these methods attempt to capture diverse features, while in the GOOD-Motif datasets, only one invariant subgraph is causally related to the target. As a result, these methods may mistakenly capture -onereeerlll patterns in G.. In contrast, LIRS leverages biased infomax to effectively learn spurious patterns and subsequently identify the invariant subgraph by unlearning the spurious patterns. Lastly, LIRS significantly outperforms other OOD methods that aim to directly leam invariant features, showcasing the efficacy of the proposed learning paradigm.
Real-world datasets. In real-world datasets, which present more complex and realistic distribution shifts, many graph OOD algorithms exhibit instability, occasionally underperforming ERM. In con- trast, LIRS adopts an indirect learning paradigm, which may enable the learning of more invariant features compared to previous graph invariant learning methods, leading to more effective OOD generalization. Similarly to the results on synthetic datasets, LIRS also demonstrates superior OOD performance under both scaffold shift and size shift compared other methods. EQuAD, which adopts a similar learning paradigm as LIRS, shows a comparable trend, with a more significant advantage under the size shift relative to other methods. Furthermore, the improvements of LIRS over EQuAD across various datasets highlights the effectiveness of the biased infomax principle and the intra-class cross-entropy loss for learning spurious features and invariant features respec- tively. Compared to other baselines that learns invariant features directly, LIRS outperforms the best method (AIA) by 4.62% in size shift and 1.95% in scaffold shift respectively.
5.3 IN-DEPTH ANALYSIS
Can LIRS learn more invariant features? To further validate the quality of invariant features learned by LIRS, we curated a dataset derived from the SPMotif dataset. Specifically, we con- structed a binary classification dataset where the motifs House and Crane corresponds to la- bel O, and Diamond and Cycle corresponds to label 1. During the construction of each class's 's samples, we attached both invariant subgraphs to the base subgraph with 50% chance, while in the remaining 50%, we randomly attached one invariant subgraph the base spurious sub- graph. For the test set, we randomly attached a single invariant subgraph to the base subgraph. Similar to the SPMotif dataset, the base spuri- ous subgraph was correlated with the target la- bels, maintaining an equal correlation strength with the labels in the test set. In addition to evalu- ating LIRS against traditional methods such as IRM, VRex and their variants, we also incorporated strong graph-specific OOD baselines, including CIGA, AIA, and EQuAD for comparisons. The ex- perimental results in Table 2 demonstrate that LIRS consistently outperforms other baselines across varying spurious correlation strengths, indicating its superior ability to learn more invariant features. Similarly, EQuAD, adopting a similar learning paradigm, also achieves competitive performance in SPMotif Minarr datasets. This demonstrates that learning invariant features indirectly can lead to
Table 2: Performance on the SPMotif-binary datasets under varying spurious correlations.
SPMotif-binary
Method
b - 0.40
b 0.60
8 0.90
ERM
74.93
72.78
63.78
IRM VREx
76.01
70.85
666.55
19.03
73.78
65.27
GIL
77.15
#3.85
68.90=7.28
GREA
79.65
73.01 #7.99
69, 09,85:20.35
CIGA
76.93
71.70
66.80
AIA
78.46=3319
71.83=
64.37
EQuAD
80.82
74.20
69.79
LIRS
82.17
75.32
71.29 #:212
8

---

Published as a conference paper at ICLR 2025
learning more comprehensive set of invariant features and achieving better OOD generalization ability.
85
72.03
12.22
72.05
83
72.42
80
72.05
21.43
75
15
71.51
70
Test A2o
65
70.85
71.00
80
55
0.90
63.74
24:15
41.00
61.70
00.21
60
02.04
04.50
6130
$3.90
83.37
45
64.15
06.23
40
G0ODMatT-Bsee GOODMart-Size
GOODHIV-S:s
GOODHIV-S28
LIRS
w/o bissed__iieee infomax
wib intra_llsss class_loss
GOODHMASSO
(a) Ablation study on biased infomax and intra-class cross-entropy loss.
(b) Hyperparameter sensitivity analysis on GOODHII datasets.
Figure 4: Ablation and hyperparameter sensitivity studies for LIRS.
Ablation study. We conducted an ablation study on biased infomax and class-conditioned (intra- class) cross-entropy loss to evaluate their effectiveness in LIRS. As illustrated in Figure replacing biased infomax with vanilla infomax to generate spurious features leads to performance degradation across all datasets. This decline is primarily due to the enhanced capability of biased infomax in learning spurious features, which is crucial for subsequent steps for learning graph invariance. Fur- thermore, replacing class-conditioned cross-entropy loss with standard cross-entropy loss also led to negative effects, which is mainly due to the interference of spurious patterns across different classes, discussed in Sec. 4 One typical empirical support arises from the Motif-size dataset, where each spurious pattern is correlated with different target labels with nearly equal strength. As result, even though biased infomax can generate accurate spurious features, the logits generated using the standard cross-entrop loss are not sufficiently precise, which aligns with Prop. - This limitation significantly constrains the test performance, illustrated in Figure 4al In contrast, the class-conditioned cross-entropy loss is able to generate more accurate spurious logits, thus enhanc- ing the OOD performance.
Hyperparameter Sensitivity. We investigate the impact of hyperparameters in LIRS, including the reweighting coefficient 7, the penalty weights X, and hyperparameters related to biased infomax. Specifically, we analyze the derived
Table 3: Performance on OGBG datasets using a different size split pro- cedure, where the graphs in the train- ing set have smaller number of nodes compared to those in the test set.
effect of the epoch E which embeddings from biased infomax and the threshold used to determine whether a sample should be considered biased not. As illustrated in Figure (4b] for both the GOODHIV-Sea and GOODHIV-Sin datasets, LIRS demonstrates stable performance, highlighting its robustness to variations in hyperparameter settings. This consistency suggests that LIRS is agnostic to hyperparameter tuning, which further emphasizes its applicability in real-world scenarios.
OGBG Dutasets
Method
OGBG-Mulbace
OGBG- RGBG-Mulbbbp
ERM
76.31
87.31
IRM
79.444105
88.774245
VREx
76,381175
84,2011.0
GREA
77.461887
88.184
GSAT
72.291445
87.46.227
CIGA
77.894365
87,941a8
AIA
78.624285
19.18
How do different size split methods affect the OOD performance? For the real-world datasets, the size split was performed in descending order, where the graphs in the training set have larger number of nodes compared to those in the test set. To evaluate the impact of varying graph sizes on generalization ability of various OOD methods, we also performed size splits based on ascending order for the OGBG- presented in Table
EQUAD
82.34+342
88.65+383
LIRS
84.62:004
90.24::414
Molbace and OGBG-Molbbbp datasets. The results of these experiments As shown, LIRS continues to outperform all competitive baselines under this alternative size split. Specifically, LIRS achieves the highest ROC-AUC scores both OGBG-Molhace and OGBG-

---

Published as a conference paper at ICLR 2025
Molbbbp datasets. This highlights the superiority of LIRS in generalizing to larger graphs when trained on smaller ones, further confirming its potential for real-world applications.
RELATED WORK
Learning invariant features. OOD generalization is a critical challenge in machine learning, where models trained on a specific data distribution often fail to generalize well to unseen distributions. Recently invariance learning has been proposed to tackle this issue, which builds upon the theory of
causality (Peters et al. 2016 Pearl (209) to learn causally-related representation that remain stable
across different environments (Arjovsky et al. 2020 Parascandolo et al., 2022 |Mahajan et al.) [202T]
Wald et al. 2021; Ahuja et al. 2020; 2021) Inspired from IRM (Arjovsky et al. (020), several
invariant learning methods on graphs are proposed (Yang et al. 2022 Li et al. [022bb Fan et al.
2022 Liu ct al. 2022 Wu al., 2022c; Chen et al., [202]] 2203a Gui et al.) 2023 Sui al. [203]]
Li et al. 2024b) to learn graph-level representations that are robust to distribution shifts. Most of
these methods aim to learn invariant features directly by training an equipredictive classifier. Recent
study (Yao et al. 2024) has proposed a new learning paradigm to learn graph invariance indirectly by learning spurious features first, then disentangle them from the ERM-learned representations. In this work, we adopt this learning paradigm for learning graph invariance.
Self-supervised learning induces spuriosity. Self-supervised learning (SSL) has emerged potent paradigm for learning representations from unlabeled datasets. The fundamental concept involves devising pretext tasks that maximize similarity between two augmented views of the same data point, often utilizing the InfoNCE loss (Oord et al. 2018). This approach has been widely applied in domains such as images (Chen et al. 2020a b) and graphs (Veličković et al. 2019 Sun et al.] 2019 Zhu et al.) (2020) You al.] Recent work have shown that SSL may tend to learn spurious features in both image domain (Hamidieh et al.] 2024) Meehan et al.) 2023) and graph domain (Yao et al. 2024). Hamidieh et al. (2024) attempted to enhance SSL model performance by addressing this issue and promoting the learning of invariant features. In contrast, our goal in this work is to improve SSL model ability to capture spuriosity, thereby facilitating better feature disentanglement for invariant learning.
Learning diverse features. Recent studies have shown that ERM tends to encourage models to learn the simplest predictive features (Hermann & Lampinen, 2020 Kalimeris et al. 2019; Neyshabur ett al. 2014: Pezeshki al.) 2021). This simplicity bias causes the models to rely simple (spu- rious) but non-causal features, ignoring more complex patterns that might be equally predictive. To address this challenge, [Huang al. (2020) employs self-challenging mechanism to force the
model to learn diverse patterns by discarding dominant features, while Teney et al. (2022) constructs diverse features by training collection of classifiers with diversity regularization. Additionally, Zhang et al. (2022a); [Chen et al. (2023b) adopt DRO to iteratively explore new features. While pre- vious works aim to encourage models to learn diverse set of predictive patterns, our method takes a different approach. Specifically, we aim to remove or unlearn spurious features from ERM-learned features, thereby allowing the model to capture more invariant features.
7 CONCLUSIONS
In this study, we identified a critical limitation in IRM, VRex and their variants on graph invariant learning, i.c., these methods may only capture a subset of the invariant features. thereby limiting their OOD generalization performance. To address this issue, we investigate the effectiveness of learning invariant features indirectly by first learning and then removing spurious features. Our theoretical and empirical analyses demonstrate that this approach facilitates the learning of a more comprehensive set of invariant features than traditional (graph) invariant learning methods, thereby improving generalization to unseen environments. We then propose LIRS that adopts this learning paradigm, which consists of: a) The biased infomax principle, and b) The class condiiiond cross- entropy loss, which elicit effective spuriosity learning and invariant learning respectively. aiming to learn more invariant features. Extensive experiments on both synthetic and real-world datasets demonstrate the superiority of our proposed method over existing of-h-atft OOD algorithms.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENT
We would like to acknowledge the support from NSF Award No. 12.222 the AT Institute for Societal Decision Making (AI-SDM), the National Institutes of Health (NIH) under Contract ROIHL159805, as well as grants from Quris AI, Florin Court Capital, and the MBZUAI-WIS Joint Program.
REFERENCES
Kartik Ahuja, Karthikeyan Shanmugam, Kush Varshney, and Amit Dhurandhar. Invariant risk min- imization games. In International Conference on Machine Learning, pp. 145-155. PMLR, 2020.
Kartik Ahuja, Ethan Caballero, Dinghuai Zhang. bean-Christophe Gagnon-Audet, Yoshua Bengio, Ioannis Mitliagkas, and Irina Rish. Invariance principle meets information bottleneck for out-of- distribution generalization. Advances in Neural Information Processing Systems, 34:3438-3450, 2021.
Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization, 2020.
Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Liò, and Andrea Passerini. Global explain- ability of gnns via logic combination of learned concepts. arXiv preprint arXiv:2210.07147 2022.
Guy W Bemis and Mark A Murcko. The properties of known drugs. 1. molecular frameworks. Journal of medicinal chemistry, 39(15))2887-289; 1996.
Ngoc Bui, Hieu Trung Nguyen, Viet Anh Nguyen, and Rex Ying. Explaining graph neural networks via structure-aware interaction index. arXiv preprint arXiv:2405.14352, 2024.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. International conference on machine learning, pp. 1597-1607. PMLR, 2020a.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003., 20Xx:20003.04297, 2020b.
Yongqiang Chen, Yonggang Zhang, Yatao Bian, Han Yang, MA Kaili, Binghui Xie, Tongliang Liu, Bo Han, and James Cheng. Learning causally invariant representations for out-of citoof-distribution generalization on graphs. Advances Neural Information Processing Systems, 35:22131-223 2022.
Yongqiang Chen, Yatao Bian, Kaiwen Zhou, Binghui Xie, Bo Han, and James Cheng. Does invariant graph learning via environment augmentation learn invariance? In Thirty-sevnnth Conference on Neural Information Processing Systems, 2023a.
Ed=
Yongqiang Chen, Wei Huang, Kaiwen Zhou, Yatao Bian, Bo Han, and James Cheng. Understand- ing and improving feature learning for out-of-distribution generalization. Advances in Neural Information Processing Systems, 36, 2023b.
Alex J. DeGrave, Joseph D. Janizek, and Su-In Lee. Ai for radiographic covid-19 detection se- lects shortcuts over signal. medRxiv, 2020. BtLhttps::// /ttttps//api..oo www.nticchooccoaaaao...oo org/
CCopuuID:222153662
Qi Dou, Daniel Coelho de Castro, Konstantinos Kamnitsas, and Ben Glocker. Domain generaliza- tion via model-agnostic learning of semantic features. Advances in neural information processing systems, 32, 2019.
Cian Eastwood, Shashank Singh, Andrei L Nicolicioiu, Marin Vlastelica Pogančić, Julius von Kügelgen, and Bernhard Schölkopf. Spuriosity didn't kill the classifier: Using invariant pre- dictions to harness spurious features. Advances Neural Information Processing Systems, 36, 2023.
11

---

Published as a conference paper at ICLR 2025
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 Sys- tems, 15:24934-249466 2022.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric, 2019.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario March, and Victor Lempitsky. nomain-adversarte training of neural networks. Journal of machine learning research, 17(59):1 2016.
Shurui Gui, Xiner Li, Limei Wang, and Shuiwang Ji. GOOD: graph out-of-distribution bench- mark. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Bench- marks Track, 2022. URL http:::/ppppereeeeeeeeeeeeeeeeee net/ www.nneeeeooummddmt.e..
p-h
Shurui Gui, Meng Liu, Xiner Li, Youzhi Luo, and Shuiwang Ji. Joint learning of label and envi- ronment causal independence for graph out-of-distribution generalization. Advances in Neural Information Processing Systems, 36, 2023.
Kimia Hamidieh, Haoran Zhang, Swami Sankaranarayanan, and Marzyeh Ghassemi. Views can be deceiving: Improved SSL through feature space augmentation. In The Twelfth International Conference on Learning Representations, 2024. (tL.tttps://pperreeeee net forum?
Id=mut
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International conference on machine learning, pp. 4116-4126. PMLR, 2020.
Katherine Hermann and Andrew Lampinen. What shapes feature representations? exploring datasets, architectures, and training. Advances in Neural Information Processing Systems, 33: 9995-10006, 2020.
Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchiloe Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization, 2019.
Weihua Hu, Gang Niu, Issei Sato, and Masashi Sugiyama. Does distributionally robust supervised learning give robust classifiers? In International Conference on Machine Learning, pp. 2029- 2037. PMLR, 2018.
Weihua Hu, Matthia 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, 18-22133, 2020.
Kexin Huang, Tianfan Fu, Wenhao Gao, Yue Zhao, Yusuf Roohani, Jure Leskovee, Connor W 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.09548; 2021.
Zeyi Huang, Haohan Wang, Eric P Xing, and Dong Huang. Self-challenging improves cross-domain generalization. In Computer vision-ECCV 2020: 16th European conference, Glasgow, UK, Au- gust 23-28, 2020, proceedings, part 11 16, pp. 124-140. Springer, 2020.
Yuanfeng Ji, Lu Zhang, Jiaxiang Wu, Bingzhe Wu, Long-Kai Huang, Tingyang Xu, Yu Rong, Lan- (ood) dataset curator and bench-
qing Li, Jie Ren, Ding Xue, et al. Drugood: mark for ai-aided drug discovery-a focus affinity prediction problems with noise annotations. arXiv preprint
.09637,097777001 2022.
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. Sgd on neural networks learns functions of increasing complexity. Advances in neural information processing systems, 32, 2019.
Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishman. Supervised contrastive learning. Advances in neural information processing systems, 33:18666 8661-1867,,,, 2020.
12

---

Published as a conference paper at ICLR 2025
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6990, 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional
networks. In International Conference on Learning Representations, 2017. URL https:
//openzeview. http:///ooommmmm-SS-a--a
Polina Kirichenko, Pavel Izmailov, and Andrew Gordon Wilson. Last layer re-training is sufficient for robustmess to spurious correlations, 2023.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Bal- subramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: A benchmark of in-the-wild distribution shifts. In International conference on machine learning. pp. 5637-5664. PMLR, 2021.
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. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 60-69, 2022.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618-211 216292, 2021.
David Krueger, Ethan Caballero, Joern-Herrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. Out-of-distribution generalization via risk extrapo- lation (rex). In International Conference Machine Learning, pp. 5815-5826. PMLR, 2021.
Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu Zhu. Ood-gnn: Out-of-distribution generalized graph neural network. IEEE Transactions on Knowledge and Data Engineering, 2022a.
Haoyang Li, Ziwei Zhang, Xin Wang, and Wenwu Zhu. Learning invariant graph representa- tions for nut-of-distribution generalization. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022b. URL
net wtt.://wwweeeeeoooooooooooooaoo.
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, 2023a.
Haoyang Li, Xin Wang, Zeyang Zhang, Haibo Chen, Ziwei Zhang, and Wenwu Zhu. Disentangled graph self-supervised learning for disto--distribution generalization. In Forty-first International Conference on Machine Learning, 2024a.
Xiner Li, Shurui Gui, Youzhi Luo, and Shuiwang Ji. Graph structure and feature extrapolation for out-of-distribution generalization. arXiv preprint wrXiv:2306.08076, 2023b.
Xiner Li, Shurui Gui, Youzhi Luo, and Shuiwang Ji. Graph structure extrapolation for out-of- distribution generalization. In Forty-first International Conference on Machine Learning. 2024b.
URL htttthts:///pereeeeeeeee
net. /ooumm 1d=
Ya Li, Xinmei Tian, Mingming Gong, Yajing Liu, Tongliang Liu, Kun Zhang, and Dacheng Tao. Deep domain generalization via conditional invariant adversarial networks. In Proceedings the European conference on computer vision (ECCV), pp. 624-639, 2018.
R. Linsker. Self-organization in a perceptual network. Computer, 21(3):105-117, 1988. doi: 10. 1109/2.36.
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 Knowledge Discovery and Data Mining, KDD '22 ACM, August 2022, doi: 10.1145/3534678 3539347. URL http://dxx doi wewiiiorgg11..0 10e...11533333
3539347
13

---

Published as a conference paper at ICLR 2025
Yang Liu, Xiang Ao, Fuli Feng, Yunshan Ma, Kuan Li, Tat-Seng Chua, and Qing He. Flood: A flexible invariant learning framework for -utoof-distriuution generalization on graphs. In Pro- ceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp- 1548-1558, 2023.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances neural information pro- cessing systems, 33: 13:10911-1931,, 2020.
Divyat Mahajan, Shruti Tople, and Amit Sharma. Domain generalization using causal matching, In International conference on machine learning, pp. 7313-7324, PMLR, 2021.
Casey Meehan, Florian Bordes, Pascal Vincent, Kamalika Chaudhuri, and Chuan Guo. Do ssl models have déjà vu? a case of unintended memorization in self-supervised learning. Advances in Neural Information Processing Systems, 36, 2023.
Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic atten- tion mechanism. In International Conference on Machine Learning, pp. 15524-15543. PMLR, 2022.
Hongseok Namkoong and John C. Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16. pp. 2216 22224, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization deep learning. arXiv preprint arXiv:1412.6611 2014.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding, arXiv preprint arXiv:1807.03744 2018.
Giambattista Paruscandolo, Alexander Neitz. Antonio Orvieto, Luigi Gresele, and Bernhard Schölkopf. Learning explanations that are hard vary. arXiv preprint arXiv:2009.00329, 2020.
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, Ed- ward Yang. Zach De Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library, 2019.
Judea Pearl. Causality. Cambridge University Press, Cambridge, UK, 2 edition, 2009. ISBN 978- 0-521-89560-6. doi: 10. 10.107//C099700 1803161.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant pre- diction: identification and confidence intervals. Journal of the Royal Statistical Society Series B; Statistical Methodology, 1875):947-1012 2016.
Mohammad Pezeshki, Oumar Kaba, Yoshua Bengio, Aaron Courville, Doina Precup, and Guil- laume Lajoic. Gradient starvation: A learning proclivity in neural networks. Advances in Neural Information Processing Systems, 34: 1272 2021.
Phillip E Pope. Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Ex- plainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 10772-10781, 2019.
Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang. Deepinf: Social influence prediction with deep learning. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery amp: Data Mining, KDD '18, ACM, July 2018 doi: 10. 005532219889.32200777 URL URL /tttt:///x.... doi org/ 0. 1041114//211 981 3220077
14

---

Published as a conference paper at ICLR 2025
Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint arXiv: 2019.
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 generaliza- tion. arXiv preprint arXiv: /91 1.08731, 2019.
Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T Schüit,, Klaus-Robert Müller, and Grégoire Montavon. Higher-order explanations of graph neural networks via relevant walks. IEEE transactions on pattern analysis and machine intelligence, 44(11):7511-759 2021.
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.
Baochen Sun and Kate Saenko. Deep coral: Correlation alignment for deep domain adaptation, 2016.
Fan-Yur Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. arXiv preprint arXiv:I908..00 00000000000,,,,.000000000000,,00 2019.
Damien Teney, Ehsan Abbasnejad, Simon Lucey, and Anton Van den Hengel. Evading the simplicity bias: Training a diverse set of models discovers solutions with superior ood generalization. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 16761- 16772, 2022.
George R Terrell and David W Scott. Variable kernel density estimation. The Annals of Statistics, pp. 1236-1265, 1992.
Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle, 2015.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
Vladimir N. Vapnik. The nature of statistical learning theory. Springer- Springer-Verlag New York, Inc., 1995. ISBN 0-387-94559-8.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903 2017.
Petar Veličković, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. arXiv preprint ar0iv: 10341, 2018.
Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations, 2019. URL [tkL[tttpps//eeereiviee net.e/ewwweeeeeeeeeeeeeeeeeeeeee Eorum? wdw.rl11irrrkiiiikeeak
Yoav Wald, Amir Feder, Daniel Greenfeld, and Uri Shalit. On calibration and out-of-domail gener- alization. In A. Beygelzimer, Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URLhtttss: /owpr//ieeeeeeieeeeeeooom net forum?
(d=xwYJ25-yTRR
Xiaoqi Wang and Han-Wei Shen. Gnninterpreter: A probabilistic geneeaat model-level explanation for graph neural networks. arXiv preprint htt.:220090099244, 2022.
Qitian Wu. Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts graphs: An invariance perspective, 2022a.
Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recommender systems: A survey. ACM Compur. Sure, 55(5), dec 2022b. ISSN 0360-0300. doi: 145/ 3535101. URL htt.thttt///doot
15

---

Published as a conference paper at ICLR 2025
Yingxin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. In International Conference on Learning Representatiins, 2022c. URtpptts:///ppeeeeeee
net / Eor.mmmo--n...3rrri.... ottpppaawaaaaa.a..oooooooooooaaa
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 learn- ing, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00822 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? In International Conference Learning Representations, 2019. URL https: //openreview. fort/foumm? wtw.roormmmmaayyyiiaaa A5Km
Nianzu Yang, Kaipeng Zeng. Qitian Wu, Xiaosong Jia, and Junchi Yan. Learning substructure invariance for out-of-distriuttin molecular representations. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Prucessing Sys- lems, 2022. URL htttss/t://////tt/// http::///peereeeeeeee net ftt/://oommmmm///m0m/
d= 2nWUNT jm
Huaxiu Yao, Yu Wang, Sai Li, Linjun Zhang, Weixin Liang, James Zou, and Chelsea Finn. Im- proving out-of-distribute robustness via selective augmentation. In International Conference on Machine Learning, pp. 25407-25437. PMLR, 2022.
Tianjun Yao, Yongqiang Chen, Zhenhao Chen, Kai Hu, Zhiqiang Shen, and Kun Zhang, Em- powering graph invariance learning with deep spurious infomax. Forty-first International Conference on Machine Learning, 2024. URL https: httt:s:///penrevieee net forum? ?id=
U9oSQtujCF
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitiik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 33: 5812-5823, 2020.
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Opatio-tempont graph convolutional networks: A deep learning framework for traffic forecasting. In Proceedings of the Twenty-Seventh Inter- national Join! Conference Artificial Intelligence, IJCAI-2018. International Joint Confer- ences on Artificial Intelligence Organization, July 2018. doi: 10.24963/jecai221185555. URL
http: doi. 1tt.:..0000......33/3/./..... 2018///00...111555.500
Junchi Yu, Jian Liang, and Ran He. Mind the label shift of augmentation-bass graph ood general- ization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recogni- tion, pp. 11620-11630 2023.
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 430-438, 2020.
Jianyu Zhang, David Lopez-Pac Paz, and Léon Bottou. Rich feature construction for the optimization- generalization dilemma. In International Conference on Machine Learning, pp. 26397-26411 PMLR, 2022a.
Michael Zhang, Nimit S Sohoni, Hongyang R Zhang, Chelsea Finn, and Christopher Ré. Correct-n- contrast: A contrastive approach for improving robustness to spurious correlations. arXiv preprint arXiv:2203.01517. 2022b.
Zehong Zhang. Lifan Chen, Feisheng Zhong, Dingyan Wang, Jiaxin Jiang, Sulin Zhang, Hualiang Jiang. Mingyue Zheng, and Xutong Li. Graph neural network approaches for drug-target in- teractions. Current Opinion in Structural Biology, 73:102327, 2022c. ISSN 440X. doi:
hutps///oi.og//0..00./.b.b.b 102377 URL https: //www www. sciencedirect. com/
16

---

Published as a conference paper at ICLR 2025
Zhilu Zhang and Mert R. Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels, 2018.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint arXiv:2006.0411 0411,,,,,,,,,,, 2020.
Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. An Empirical Study of Graph Contrastive Learn- ing. arXiv.org, September 2021.
Xiang Zhuang, Qiang Zhang, Keyan Ding, Yatao Bian, Xiao Wang, Jingsong Lv, Hongyang Chen, and Huajun Chen. Learning invariant molccular representation in latent discrete space, Advances in Neural Information Processing Systems, 36, 2023.
17

---

Published as a conference paper at ICLR 2025
APPENDIX
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
set of graphs
G XA
graph with the adjacency matrix A {0, 13m1 and node feature matrix X E ggxd random variable for labels content factor style factor environment
S
he
invariant representations (features) spurious representations (features)
h,
Ge
the invariant subgraph with respect G the spurious subgraph with respect to G the estimated invariant subgraph the estimated spurious subgraph
G.
G.
G.
he
the estimated graph representation for graph G the estimated node representation for node i E the estimated invariant graph representation, interchangeably with Ò in our paper the estimated spurious graph representation, interchangeably with S in paper The jth entry of the spurious logits derived from h! for sample G The jth of the estimated spurious logits for sample ((1)
h;
he
h,
encoder
p(-)
classification head for LGr classification head for Lrav reweighting coefficient for sample ( index set with K elements all-one (column) vector with K entries
p(())
(1)
K =
[1, 2,
K
1K
vector
W
matrix
W
random variable set
B MORE BACKGROUND AND PRELIMINARIES
Graph Neural Networks. In this work, we adopt message-passing GNNs for graph classification due to their expressiveness. Given simple and undirected graph G = (A, X) with n nodes and m edges, where A {0, 1]mxa is the adjacency matrix, and X E gaxd is the node feature matrix with d feature dimensions, the graph encoder h G + Rh aims to learn a meaningful graph- level representation lig. and the classifier Rº - Y is used to predict the graph label Yo p(ha). To obtain the graph representation hGs the representation h! of each node e in a graph G is iteratively updated by aggregating information from its neighbors (V)). For the 1-th layer, the updated representation obtained via an AGGREGATE operation followed by an UPDATE operation:
AGGREGATE (fN!--) uu : .uEN()))))
(5)
h UPDATE (L(1) (n!-),m!l .m!)
(6)
18

---

Published as a conference paper at ICLR 2025
where hg X, is the initial node feature of node in graph G. Then GNNs employ READOUT
function to aggregate the final layer node features (2) : E V into graph-level representation he:
(n u (n :e
hg READOUT
Data Generating Process. The presumed data generating process adopted in this work is similar the previous studies (Arjovsky et al., 2020 Ahuja et al. 2020; Chen et al.] [022] 2023a Wu et al. 2022a). The dynamics of graph generation are fundamentally grounded upon the principles of Structural Causal Models (SCM) (Peters et al.) 20T6), capturing the complex interplay between latent variables and their influence observable graph characteristics. This model assumes the graph generation as a function fgen 2 - G, where S I2" denotes the latent space, and G is the graph space. Through the lens of SCM, the generation process is decomposed into the invariant subgraph Ge, the spurious subgraph Gs, and the observed graph G respectively, as formulated the following equation:
== Sen gen (C), G₁ ggn (S);
G:
S gge (Ges G.):
Furthermore, the latent interactions among C, S, and Y can exhibit two types of conditional
independence: (i) Y 1 S C and (ii) Y L S C. In case (i), the invariant factor C is fully informative (FIII) to the target label Y, and the latent spurious factor provide no further in- formation. In case (ii), the invariant factor C' is only partially informative (PIIF) about Y. spu- rious factor S can further provide additional in- formation to aid the prediction of Y, however, S is directly affected by E, it is stable across different environments. The SCMs for the two scenarios are illustrated in Figure For the PIIF SCM, the structure equation is:
(a) PII SCM
(b) FIIF SCM
Figure 5: Structure causal models for graph data generation.
Y == Xm. -
+ t
(8)
while for FIIF SCM, the structure equation is:
Y + n2 n2 E..
(9)
Here Xe and X, denote the random variables for invariant factor and spurious factor respectively. n and n2 represent random Gaussian noise, and e stands for an environmental variable, which causes the spurious correlation between X, and Y.
C ADDITIONAL RELATED WORK
OOD Generalization. OOD generalization is critical challenge in machine learning, where mod- els trained on a specific data distribution often fail to generalize well to unseen distributions. Several approaches have been proposed to address this issue, including domain generalization, distributional robustness optimization (DRO), and invariance learning. Domain generalization aims to learn fea- tures that are invariant across different domains or environments. Previous studies, such as Ganin et al. (2016);(uun & Saenko (2016): Li et al.] (2018): Dou et al. (2019), regularize the learned features to be domain-invariant. DRO methods focus on training models to perform robust against the worst- case scenarios among diverse data groups. Namkoong & Duchi (2016); Hu et al. (2018); Sagawa et al. (2019) regularize models to be robust to mild distributional perturbations the training dis- tributions, expecting the models perform well in unseen test environments. Building upon this, Liu et al. (2022) Zhang et al. (20226) and Yao et al. (2022) propose advanced strategies to improve robustness by assuming that models trained with ERM have strong reliance spurious features.
19

---

Published as a conference paper at ICLR 2025
Invariance learning leverages the theory of causality (Peters al., 2016 Pearl 2009) and intro- duces causal invariance to the learned representations. The Independent Causal Mechanism (ICM) assumption in causality states that the conditional distribution of each variable given its causes does not inform or influence other conditional distributions. Despite changes to the intervened variables, the conditional distribution of intervened variables and the target variable remains invariant. [ jovsky et al. (2020) proposes the framework of Invariant Risk Minimization (IRM) that allows the adoption of causal invariance in deep neural networks, inspiring various invariant learning works such as Parascandolo et al. (2020); Mahajan et al. (2021) Wald et al. (2021); Ahuja et al. (2020)
202T Krueger et al. (2021).
Graph-Level OOD Generalization. Recently, there has been a growing interest in learning graph- level representations that are robust under distribution shifts, particularly from the perspective of invariant learning. MoleOOD Yang et al. (2022) and GII. et al. (022b)) propose to infer environ- mental labels to assist in identifying invariant substructures within graphs. DIR Wu et al. (2022c), GREA Liu et al. (2022) and iMoLD Zhuang et al. (202)) employ environment augmentation tech- niques to facilitate the learning of invariant graph-leved representations. These methods typically rely on the explicit manipulation of unobserved environmental variables to achieve generalization across unseen distributions. AIA |uu et al. (2023) 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 Chen et al.] (2022) and GALA Chen al. (2023a) utilizes supervised contrastive learning to identify invariant subgraphs based on the assumption that samples sharing the same label exhibit similar invariant subgraphs. EQuAD Yao al. (2024) adopts self-supervised learning to learn spuriosu efatures first, followed by learning invariant features by unlearning spurious features. LECI Gui et al. (2023) and G-Splice Li et al. (2023b) assume the availability of environment labels, and study environment exploitation strategies for graph OOD generalization. LECI Gui et al.] (2023) proposes to learn causal subgraph selec- tor by jointly optimizing label and environment causal independence, and G-Splice Li et al. (2023b) studies graph and feature space extrapolation for environment augmentation, which maintains causal validity. On the other hand, some works do not utilize the invariance principle for graph OOD gen- eralization. DisC Fan et al. (2022) initially learns biased graph representation and subsequently focuses on unbiased graphs to discover invariant subgraphs. GSAT Miao et al. (2022) utilizes in- formation bottleneck principle (Tishby & Zaslavsky (2015) to learn minimal sufficient subgraph for GNN explainability, which is shown to be generalizable under distribution shifts. OOD-GNN Li al. (2022a) proposes learn disentangled graph representation by computing global weights of all data. Parallel to all previous studies, we propose ELiSD, which utilizes spurious subgraph diver- sification to provably identify Ge for OOD generalization, and uplift the lower bound of [(; to enhance feature learning simultaneously. In this study, we adopt the same learning paradigm as EQuAD, and we propose instance-level adaptive biased infomax and intra-class cross entropy loss to enhance the efficacy of learning spurious and invariant features respectively.
Node-Level OOD Generalization. There has also been a substantial amount work focusing on the OOD generalization problem on node-level classification tasks. Most of these studies (Wu et al.) 2022a Liu et al. 2023)] Li et al.] 2023a Yu et al. 2023) also focus on environment generation, which facilitates the subsequent invariant learning. These methods are also likely to learn only subset of invariant features, thus limiting their ability to generalize to OOD data.
GNN Explainability. GNN explanation methods can be broadly categorized into instance- level (Luo et al.] 2020; Ying et al., 2019| PPope et al.] 2019 (Schnake et al., 2021) and model- level (Azzolin et al. [002)] Yuan et al., 2020 Wang & Shen 2022) explanations. The main goal of the instance-level explanation methods is to explain why a certain prediction is made for a par- ticular instance. Specifically, the important input subgraph and features that contribute the most to model predictions are identified for a given instance. In this work, we employ instance-level GNN explanation methods to approximate the invariant subgraph Ge, and utilize off-the-shelf method GSAT (Miao et al.] (022). that is robust under distribution shifts, to identify the important nodes in a graph to facilitate the learning of graph spuriosity through adaptive biased infomax in real-world datasets.
20

---

Published as a conference paper at ICLR 2025
D THEORETICAL RESULTS
D.1 THEORETICAL DISCUSSION ON VREX IN LEARNING INVARIANT FEATURES
We first outline the objective function of VRex as following:
Rez = min Ee [C (w o (X), +) 3 Var, (w ,
(10)
here w and & denote the classifier and feature extractor, respectively. B is the hyperparameter to control regularization strength. Next we prove the following proposition.
Proposition 3. Let w", Ø" argminLv then hag = w" (X) learns invariant features, however
w,
hGg may only contain a subset of invariant features. given our PIIF data generating assumption:
Y + = Y n2 + E where X == Xxii ;= ===xx, X
(1I)
and FIIF data generating assumption:
Y Xx + n1, X, = n22 + 6", where N Σ X Xa,i X, == Σ Xs.
xx:=)
(12)
when using linear classifier ((X) Wi + W2X and f(w 6(X)) R(e) = ((x))-Y?
Here, we assume an additive model for Xe, i.e., A set of invariant features X is combined through summation to obtain the final Xe, and similarly for X,.
Proof. To prove Prop. 3 we first expand Var, (ate)) E. (e) (E)()) then take derivative w.r.t. Wi and u2, we then show that Equ. 10 can elicit w² that learns invariant features, however, may only learn subset of them.
Given R(e) = (Ø(X) 2)² and Var Vare(H((e) = E. (e) - R(e), we have:
i Vare(R(e)) (Ex - 1) E²((o(X) - Y) Own
Owh
(13)
( X.] 4E, [R()]] [x
Similarly, for (Rle)) we have:
thoz
a (Rre(((e)) 4EE [(((X) r)a -Xe nı n2 + E5] -EE [R [(x -Y) (X. + m n2 + c))
Owz
(14)
Now we expand d(X) Y:
((X) = wiXe + W2X
X, X. ni + n2 E
x(X) = (w) + w2) X, + won + W2 + Wye
(15)
Y = X.
x(X) - = = (w) + w/ 1) X + (w 1) n2 + w2 Wae"
Next, we show that wi = 1, و2 = 0 is a optimal solution for minimizing Eqn. 1, W2 0, and plug into o(X) and (X) Y. get:
10
We set wi
21

---

Published as a conference paper at ICLR 2025
o(X) - wi + w2X, - -1 = -xe:
(16)
and
Y= X n1
(17)
(XX) Y = X - (Xe + n1) = -11-
Substitute Eqn.
I6 into Eqn. 13 we get:
4 [()(X) y)s X.] 4 En m1 [(-n1] )3 xx]] =0
(Ee[n = 0)
Ee R(e)] Eg |n o²
(18)
Ee [miing mz ((-11) Xc]] 0,
therefore, we have (R(e)) For Own
Vara (R(e))
(Eqn. 14h. the first term can be expanded as:
Ows
Eg ( (-n1)² X
Ee Bai,n
[-mi1) m1
Ee [Ens,n [ni]] -30
(19)
Eg
Emni
(-n ). n2 0
Egg
Eni.na
(-R1) 3 .e 0,
thus:
4Eg
E
(-n1)² (Xe + nn + +i2 m = 4. (-30"))
120
(20)
For the second term in Eqn. 14
[R()) E. Eny,ng [(-m1) (Xe + + n2 + +e)]] = 40 (-o2)) = 4 nlo
(21)
substitute Eqn. 20 and into Eqn. 14
we get:
Vare()(e)) 1
(22)
Owo
As is the standard deviation of n1, where X. is causally related with Y, we assume 0.1 is small value, hence the high-order term ( 0. Therefore, we show that wy 1, W2 is (approxiamately) optimla solution for Eqn. 10 indicating that only the invariant features are used in the classifier o² (X). Now we have:
Y 6X) = X E
(23)
Given fixed value X. x, there may be multiple combinations for (Xe,i) that result in X. xr The set of invariant features {Xc,i} naturally arises from the learning process of deep neural net- works. Some invariant features might be easier learn due their salience or higher frequency in the dataset. Consequently, although the VRex objective promotes the learning of invariant encoders (as we have proved above), it does not guarantee the identification of all invariant features {Xo,i).
For FIIF data generating process, similarly we get:
Φ(X) wi X. + w2X., X, no + Y = X, 11 ((X) - Y = (w) - 1)X. + won2 + W2E - fl.
(24)
22

---

Published as a conference paper at ICLR 2025
The variance of the loss across environments is:
Vare [(o(X) - y) Ee [(o(X) y) (EEs -
(25)
Recall that ((X) w1 + W2 and X. n22 + E", we have:
((X) - (wi 1) X. + w2r12 + W2E" n1.-
(26)
The squared expected loss term can be expanded as:
Ee [[o(X) - y) Ee [(11] 1) X + u2 + uze n1
(wi - 1)² Eg [X]] + wgEK [ng]]
(27)
+ E En [(0)²]] + E [n]]]
+ (wi - 1) Wy [x
Given the independence between X n1. n2 and we have:
Ee [(((X) - r) = (wi - 1) E. [x?] + w [n]]] + =ngRe [(0)]]]
+ R. [n]]]
(28)
For E. [(Ø(X) - -Y we have:
B. -()(X)-Y) = -E [(u)) 1) Xo + w2l22 + w22 n1)²
-
(wi - 1)a Ee [x*]] + Bg [mš]]
(29)
+ Wy [(e))]] + B. [nt]]
Taking derivative with respect to wy and W2:
B. [(((X) r- 2 (wi E, E. [x]]
Own
E. [(d(X) ryt (wi 1)a Ee [X]]
Owl
(30)
E, [((() - Y)Π = 2w² Eg [n]] + E. (()))2)
Ow'
0
Ee [(o(X) yy Aw
Eg
[n]]]
E. [(ce)(]
Owa
conclusion, for both PIIF and FIF data generating scenarios, VRex only learns invariant features, however given an additive model, it may only learn a subset of invariant features that are significant or frequently appears in the training set.
Setting Eqn. 30 to zero, we get wi = 1, w2
D.2 THEORETICAL DISCUSSION ON IRMv1 IN LEARNING INVARIANT FEATURES
Using a similar derivation process, we can prove that IRMv1 may only learn a subset of invariant features. We first outline the objective of IRMv1 as follows:
LIRMET = min E, [w (X), w.p
wf (w (X), 1)
(31)
here w and denote the classifier and feature extractor, respectively.
23

---

Published as a conference paper at ICLR 2025
Proposition 4. Let w x argminCrRMel then heg w² (X) learns invariant features, how-
w,
ever big may onty contain subset of invariant features, given data generating assumption:
Y Y= x + n2 E where X Σ Xo := Exxxxx Xsii
(32)
and FIIF data generating assumption:
y= X = +
n1, X, = n2 + E", where X == Σ Xxixxxx== Xx Σ X
(33)
when using linear classifier 6(X) X + W2 x and L(w ((X)) = R((e) = (d(X) vY
Proof. The IRMv1 objective can be simplied into:
LIRMeT Vulu=roo((u
o() (X), (6(X)-Y)+
(34)
given:
((X) = wi W/ + u2 X.
X, X. + m1 + n22 t
(35)
Y Nx + n1,
we get:
o(X) wIX. w2 (Xe + + n2 + =0) (wi + W2) X. w2nl W2n2 was"
(36)
o(X) - Y = (w1 + w2 1) Xx + (w2 - n1 + w2 + W2E
Taking gradient w.r.t. wi and w2 respetively:
- 4(0(X) -Y33 0(o(X) - Y) Ow
Owl
(37)
=((((X) 2)3 X.:
and
0(o(X) 8)a ( v)3. 0(o(X) - YY Ow2
Owz
(38)
=(6(()- y)3, (X. n1 + 12 + t
Plugging in w1 = 1, u2 we get:
x(X) = X. ((X) = 1711
(39)
Substitue Eqn.
39 into Eqn. 37 and Eqn.
we get:
E, (oo())-))
E. [Emjong [-4n] Xo]] 0,
(40)
Own
and
24

---

Published as a conference paper at ICLR 2025
-
Eg
= Ee [-4n] (Xe n + n2 + e*)]
Oku'
-me Emi
[n9- Xc]
AE, Eni,na ni n1l 1.,, [n n2l 4E, Eni,na
[n] _ (41)
given that:
B m2 [n]] Xc] 0
Bny, 22 [n]] n1
E En [nt] 30
(42)
E Eng, .12
[n]] 122
Em,,. n2 [i E-] = 0,
120 with similar assumption that the standard error 0nd of the Gaussian noise nı of the causal variable X. is small, we conclude that Eg O(oti) = O. Hence IRMv1 learns invariant features under the data generating process. Now have:
have E
(()(X)-Y)** Owz
-()(
Owz
Y (x) = Xx = Σ X
(43)
For FIIF generating process, applying the same technique, we have:
x(X) - =w + W2 (n2 + E (Xe + n2) = (wi X) + W2 W2e n1
@LIRMol Owl
4(0(X) y)3. Ô
(6(X) - -Y).
Ow
(44)
θ Ow
(6(X) Y) X
Therefore:
0LIRMul = 4(0(X) - Y)3 .x. = =4( 1) Xe + w2n2 + wze" - n11) Xo.
Owi
(45)
ILIRMel 4(0(X) - Y)3 θ (Ø(X) Y) 4(((() VY3 (mz + (0)
Owy
Owy
Substitute w1 W2 into o(X) - Y,:
((X) - Y = X - (Xe + n1) --1
(46)
Taking derivative w.r.t. wi and W2:
OLIRMv
E
-4Ec [n] = 0,
(47)
Owi
Eg
4E
n (n2 + e² =
(48)
Owz
Therefore show that for the widely used FIFF and PII data generating process, IRMv1 is able to learn invariant features. However, with a similar reasoning as VRex, there may be multiple combinations of the assignments for (Xar) } to lead to fixed value X, x, and the objective of IRMv1 (Eqn. 31) won't ensure the learning of all invariant features.
25

---

Published as a conference paper at ICLR 2025
D.3 PROOF OF THEOREM 4.1
Theorem D.I. [Restalement of Theorem 4.1 Given that the invariant subgraph Ge contains in- variant patterns causally related to the target labels, and G, contains only spurious patterns, the biased infomax principle achieves spuriosity learning. Specifically, the encoder h)))) learns solely the spurious features for each data sample in D.
We begin by stating the assumption underlying our proof, followed by a proof by contradiction.
Assumption 2. (Existence of spuriosity learner) There exists a learning algorithm capable of achiev- ing spuriosity learning defined in Def. 2
Most invariant learning algorithms aim learn invariant features, and large collection of literature
has demonstrated the existence of such algorithms (Arjovsky et al. 2020) Kreuzer et al. 2021
Parascandolo al. 22200; Mahajan al. [202] Wald al.J 2021; Ahuja et al. 2020: 202
Chen
et [022 Gui et al. [023] et al. (022). In contrast, we assume the existence of algorithms that
learn spurious features. One such example is provided by Fastwood al. (023). where the method
learns both invariant and spurious features, supporting the plausibility of our assumption. Recent studies have shown that self-supervised contrastive learning tends to learn spurious features (Yao)
et al., 20244, Hamidich et al., 2024; Meehan et al.) 2023). Therefore, self-supervised contrastive learning would be one form of the spuriosity learner. Based on the above, we first sketch our proof.
Proof sketch. sketch. As biased infomax is a more general form of the infomax principle, with exponentially many node configurations (Def. 4. the encoder (-) under the optimal node configuration must result in spuriosity learner, which also maximizes the learning objective. We then employ proof by contradiction to demonstrate that the node configuration corresponding to biased infomax in Def leads to larger mutual information, thereby eliciting contradiction, leading to the conclusion that the node configuration corresponding to Detßeelicin the spuriosity learner.
Definition 4. (Node configurations) Let the general form of biased infomax be:
1
Σ 1 (hu
Σ 1 (bu: (mn: NEEGY
max E
GG
(49)
s.t. h ho( hG READOUT (n.))
A node configuration c (c1, 02, qvv) such that G {-1, 1}. corresponds to one specific
instantiation in Eqn. 49 where C; = 1 denotes that U; E G, and Q; = - means U; G \ G. The set of all possible node configurations can be denoted as H. (c q 1)}.
Given definition 4 the infomax principle (Eqn. D is therefore special case of the biased infomax c2l"
principle, where 1ly. For notation simplicity, let == |2
RGG. C2 E R| be two vectors for the node configurations of G, and Ge. Assuming for the optimal node configuration, there are i elements in с₁ with 1, and |G.| k elements with - (denoted as V and V!), similarly, there are t elements in C2 with 1, and |Gel elements with 1., denoted as V and VI. We then compare such node configuration e* with c' = [1c.]. -1,,,1
Proof. First, under the node configuration c*, the optimal parameter to optimize the learning objec- tive is:
0" = arg max Ea
1
Σ I (hu:hio) + Σ I (ha - Σ I
hi (ha: - Σ 1
8
[
WEV!
14 E
WEV! (50)
and under the node configuration c', the optimal parameter is:
26

---

Published as a conference paper at ICLR 2025
0' = arg max BGNg Gl
Σ
I
(hu:
-
Σ I (Bashe))
(51)
weEG
Let
((0); == Ba- := G
Σ
I
(hi:hh))
Σ
(hi:
Σ
I
h
Σ PEVE
(his
NEV!
BLEV!
NEV!
SSiiilarl,, we can define
f(0':D,')) = Bang |G
1
Σ I (h;:ho)) - Σ UNEG,
I (he; (ba;
W.EG.
According to Eqn. 51 we can conclude that f(0' (('; > D(0"; and we also have that he- (-) he only learns spurious features 0 is the maximizer for the objective under c², and (-) hg learns both invariant and spurious features, as 0 is the maximizer for the objective under c'. Let by = hg- (G), and bg = (G), therefore we have:
I hi li = 0, Ve; E Goi
(52)
I
hig hg)
Ye Ge
(53)
hi ng
=q: Vo Gsi
(54)
[ (b) =d', Vu EGi
(55)
Eqn. 52 is due to hg- (.) is obtained under c", hence only learn spuriosity. Eqn. 53 is due to that her (-) learns both spurious and invariant features. We also have q > qf due to the same reason. Now
compare f0'; D, e') with f(0;; D, c') as follows:
9- E
(00 - (O'; = Ea-
losEG,
BEG.
1
((Gal -Glll-'' 1Gel (Gl..c) c))
G
EG G
(|Gella g') + |Gel c) > 0,
(56)
leading to a contradiction that f(0': D')) > D. c') for any node configuration * c', there- fore conclude that e' the optimal configuration that elicits the spuriosity learner, which corre- sponds to the biased infomax objective in Eqn. 2
D.4 PROOF OF PROPOSITION T
Proposition 5. [Restatement of Proposition Ty Given an error rate p% in the approximation al- gorithm for Gz, let the learning objectives for the biased infomax with the ground-truth subgraphs G. and G. and with the approximated subgraphs G. and G. be denoted as ;( and L(';; respectively. The difference between C( D) and L(0': DD be expressed
Eg-g
2 Gl
Σ 1 (bu;bbo)
Σ ErEPG.
I (fu; (fu:ho))
)
27

---

Published as a conference paper at ICLR 2025
Proof. We first expand DD) and D)) follows.
[()";D) - G
1
Σ
his hi) - Σ I (ies fic)
(misfic)
1 |G|
1
Σ
(fistic)
+ E I (
Σ
I ((oibio)
Σ I (fu:tic) mEpDC
PrE(1-p)G.
nEp
nE(I-p)Ge
and
C(0';D) ((0:D)=EGws) BG G
Σ
1 (mrilio)
Σ "EE(I-DiG.upG,
1 (misTec)
(57)
(LE((-p))
the gap of the two learning objectives AL is:
AC = L(0":D) L()::D)
E |G|
1
E
1 (brifio)
Σ
(hi
Σ
I (meilic)
Σ mppple
(bi: (is)
(nE((L-)G.
usEpG.
wEE(L-)]G
Σ
I (hi;hee)
Σ
I (fes (ics
(Massies)
[
1:E(1 p)G.upG.
= Ea-g
2
Σ
(hi;ho)
Σ
(hi;
|G|
L.EPG.
(58)
We conclude the proof.
D.5 PROOF OF PROPOSITION 2
Proposition 6. [Restatement of Proposition 2 Given linear regression model with parameters (01, 02} and spurious features 22), the correlation strength for feature D1 is p and for x2 is 1 1-p when
- q when Y = 1. Assuming the spurious features Iı and X2 can each take values in {0, 1}, we oblain the
Similarly, the correlation strength for feature x1 q and for 32
following parameter estimates using Mean Squared Error (MSE) loss: 01 = *ptq" ppp O2 = 2-p-9
-
1-9
Proof. The linear model for predicting Y is: y 01æ1 0232, with Mean Square Error (MSE) loss, for Y = with samples, 21 = and T2 = 0; with (1 - p)n samples, æ1 0, 22 1; For Y with qn samples, 21 1, with (1 q)n samples, 21 0, x2 The MSE loss LMSE consists of 4 terms:
pn
(1-p)r p)n
gm
(1-g)n
LMSE Σ (0) 0)² + Σ (02 0)2 Σ (0, 1)
Σ
(02 1)²
i=1
i=1
= pm - 07 + (1 - p)n 62 + qn (01 - 1) + (1 - q)n (02 - 1)²
pOR (1 03 + q (0, - 1)² (1 4) (02 1)2
Taking partial derivative w.r.t. 0::
28

---

Published as a conference paper at ICLR 2025
ULMSE
4 [2p0, + 2q (0) 1)]
001
10 + 90, q 0
01
p + q
Similarly for 02.
ÔLMSE
1 [2(1 - p2(1-p)02+22 + 9) (02 1)]
002
+ (1 - p)0 + (1 (1-1111 g)0 (1 - 9) =
(2 p 0) = 4
02 2 p q
As demonstrated in Proposition 2] the presence of spurious feature overlap across different classes hinders the linear classifier's ability to generate distinguishable (symmetric) logits. For instance, when p q, both 01 = 0.5 and 02 0.5, resulting in a loss of distinguishability among different spurious patterns. To mitigate this issue, we propose class-conditioned (intra-class) cross entropy loss which reduces the interference across different classes. To show that class-conditioned (intra- class) cross entropy loss is able to maximize the conditional entropy ((s() we propose the following proposition.
Proposition
Given the spurious features h YG E and a suitable clustering number K
that corresponds the number of environmental groups in each class Y y. the loss objective Lrav (Eqn.) will maximize the conditional entropy (() 610 ) e
To prove that optimizing Live maximizes the conditional entropy H(s() (()) we show that (()) ~ Cat( with K clusters, hence maximizes (s()) (1)
Proof. First, have:
mar H(s
((0 hg
H (((66) H(s (()))
(59)
Here, /'(-) is the classification head for cluster labels st) For notation simplicity, will omit superscript (i), and denote (( and = g(1) Now using softmax loss, have:
29

---

Published as a conference paper at ICLR 2025
K Σ j=1
e²)
L
S) log (aT))),, where (s)) =
(60)
=k=1
Oo
(S)
0 (5) (6ig (8).)
(61)
09:
OL
K
i log (a (8)
8j
(62)
05:
05
j=1
0L
(s:
o ( )
(63)
0%
Taking expectation on both side of Eqn.
63
we get:
0L
E
- (s; (
(64)
0s:
0
(E [s:] (S)
(65)
1
0
E [o(3))
(66)
K
E [
= K
(67)
Eqn. 66 is due that Ejs:] K. as each cluster derived from the spurious embedding repre- sents environmental group, and with appropriate reweighting within each cluster, the samples will be weighted equally across clusters, i.e., samples from majority group and minority group will be weighted equally. Given that this expectation holds over all training samples, one optimal solution for Eqn. 67 is: (S); = K Vi [K] for K class labels. This aligns with the assumption that within each class, there exists a stable pattern G., and if the encoder is able to effectively capture invariant patterns Ge while discarding spurious correlations, (()), will be fixed and constant value. With this constraint, the solution o (8(0) = } 1 implies that the model learns invariant features. Further- more, this stable solution maximizes the conditional entropy H (s(0) (()) as a ($(+)) is independent of (+).
Remark. While (3(1)) = 1 is a sufficient condition to minimize Cinv, there exists other solu- tions that exploit spurious features to achieve high training accuracy. To guide the model toward the stable solution that satisfies (s(
an explicit regularization term, such as ()) R 1 llg, can be added the objective in Equ. However, our empirical results show that such explicit reg- ularization does not significantlly affect performance. This may be attributed to the limited number of class labels and node features in graph-level OOD datasets, which inherently enforce a (B())) to be similar across all training samples, facilitating convergence the stable solution.
D.6 PROOF OF THEOREM 4.2
Theorem D.2. [Restatement of Theorem 4.2g There exists a suitable 7 and clustering number K, such that minimizing the loss objective L Ler + >LIne will lead the optimal encoder ht h-) which elicits invariant features for any graph G, i.e. he (G) =h. h
Proof. We aim to show that minimizing the objective L encourages the encoder h h-)-) to learn rep- resentations he that contain only invariant features h First, consider that under ERM, i.., mini- mizing LeT alone, the encoder h(-) learns both invariant and spurious features, given the empirical and theoretical evidence in previous studies (Kirichenko et al., 2023 Chen et al. 2023b). Now, we introduce the invariant loss Liar, according Proposition 7 will maximize the conditional entropy
30

---

Published as a conference paper at ICLR 2025
(((())))) [ba] for each sample G(), This encourages the learned representation lig to be uninforma-
tive about the spurious features 5 In the following proof, we drop superscript for simplicity.
Next, our goal to show that minimizing L leads to hig = ha- We consider the following three cases:
Case I: The encoder learns only spurious features (hg = h,). In this case, the representation he informative about s but not about h The conditional entropy Hss)h)) is minimized but not maximized.
Case 2: The encoder learns both invariant and spurious features (bg = <(h,, h2)). Here, hgg is informative about both he and ha While this may minimize Lor in the training environments, ha remains informative about hg, thus not maximizing Hssha))
Case 3: The encoder learns only invoriant features (hg = hz). this case, hg is uninformative about hg therefore, (s(ha) is greater than previous two cases, furthermore he also minimizes Ler given the invariant features hold the sufficient predictive power for the targets labels (Assump- tion
Therefore, conclude that the encoder ht (-) will only learn invariant features, conditioning spurious features h, will not maximize H(s(ba) Additionally, it is important to note that there exists "uninformative" features which may also maximize (() he) without including he- This phenomenon has been demonstrated in EQuAD (Yao et al.] 2024). where model performance dete- riorates when À > 1. However, when À < L, LoT emphasizes useful features that correlate with the target labels, while Line acts as regularization term that encourages the model to remove spurious features and focus on learning invariant features.
E COMPLEXITY ANALYSIS
We provide time and space complexity analysis for LIRS, followed by empirical running time anal- ysis on GOODMotif-bat and OGBG-Molbbbp datasets.
Space complexity. The space complexity for LIRS is ((BB) m)), where [B] denotes the batch size, H denotes the hidden feature dimension, and m denotes the average number of edges. Therefore the memory overhead is on par with ERM, and may outperform other graph data augmentation method such as DIR (Wu al. [022c) and GREA (Liu et al. (022), as for each samples, they generate spurious subgraphs for each sample using [B] samples in the same minibatch, which leads to O ((1B)2 + Hm).
Time complexity. The time complexity of LIRS is O(KCmF), where & is the number of layers in GNN encoder, C 1 is constant as LIRS runs GNN encoder multiple times, F is the hidden dimension size. Notably, most other graph invariant learning algorithms also exhibit a complexity of O(CkmF)) as they require multiple GNN encoders for subgraph extraction and feature encoding respectively. Therefore, the time cost gap between LIRS and other methods is not significant, We provide detailed running time analysis using the Motif-base and Ogbg-Mollbie in Table On the Motif-base dataset, the biased infomax only requires 20 epochs training, making its time cost comparable ERM. On the beog-boobbbp dataset, the time cost of LIRS exceeds that of other methods since the biased infomax requires training for 100 epochs, and GSAT must be run to annotate node labels to enable adaptive biased infomax. We provide a breakdown of the time cost for each stage in LIRS to provide a better understandings in Table
datasets, as shown
The first three components account for the majority of the time cost in LIRS, however they only need to be run once. Retraining the GNN encoder is both fast and stable, with less variance Liaw is merely a cross-entropy loss. This presents a key advantage of LIRS in terms of hyperparameter selection. Specifically, most of OOD methods require hyperparameter search, and for most methods, the process must be restarted entirely for each run, incurring significant time costs. In contrast, for LIRS, only the final GNN retraining step needs to be run multiple times for hyperparameter
31

---

Published as a conference paper at ICLR 2025
Table 5: Running time analysis (in seconds) on various OOD methods
Method
Motif-base
OGBBG-Molbbbp
ERM
494.34=117.8
92.42=0.42 151.84+7.53
IRM
968.94=164.0P
Vrex
819.94=124.54
129.13=12.93
GSAT
12334396.19
142.47=25.71
GREA
1612.43+177.36
262.47+45.71
CIGA
1729.144355.62
352. 452.14+93.32
AIA
1422.34469.33
217.36=11.04
OOD-GCL
10813+28.12
8455.51=68.61
EQuAD
747.87434.71
278.85+16.64
LIRS
504.87424.04
421.32+19.86
Table 6: Running time analysis (in seconds) of LIRS
Method
Motif-base
OGBG-Molbbbp
Biased Infomax
302.12
214.24
MinibatchKmeans-SST
6.63
3.04#0.35
Mark Nodes
142.47+25.71
GNN Retraining
196.12424.04
61.57+6.86
search, leading significantly reduced time cost when conducting multiple runs compared to other methods.
F MORE DISCUSSION ON LIRS
Comparison with EQuAD (Yao et al., 2024). While LIRS and EQuAD share similarities in the learning paradigm, our study make several distinctions compared with Yao al.) (2024). First, while EQuAD primarily addresses the limitations of existing OOD methods that are sensitive to varying spurious correlation strengths, does not fully explain why the proposed learning paradigm is effective when spurious correlation strength remains stable. In contrast, our work answer this important question and demonstrates that this learning paradigm enables learning broader set of invariant features; Second, We curate the SPMotif-bing which can serve as benchmark for future studies to evaluate the effectiveness of methods in learning broader set of invariant features; Third. While EQuAD uses standard infomax objective to learn spurious features, we propose new algorithm that addresses the limitations of the vanilla infomax approach. Specifically,
dataset based the SPMotif datasets,
introduce the biased infomax to overcome size constraints and further incorporate additional procedure (i.e., a GNN explainer) to annotate critical nodes with adaptive thresholding realize biased infomax in real-world datasets; Finally, We identify the limitations of the cross-entropy loss in disentangling spurious features and propose a novel loss objective that is more effective in learning invariant features. Additionally, our proposed loss does compromise computational efficiency.
Comparison with Supervised Contrastive Learning (Khosla al. 2020) and Deep Graph In- fomax (Veličković et al. 20188). The biased infomax principle also share similarity with Supervised Contrastive Learning (SCT) and Deep Graph Infomax (DGI). However, SCL and DGI primarily target in-distribution (ID) data and are designed to improve performance
predictive tasks. In contrast, our proposed biased infomax is specifically designed for OOD data, with the goal of learn- ing enviromment-related features rather than features that directly benefit classification tasks. This makes our approach conceptually distinct from SCL and DGI; Second, In SCL the contrastive loss operates the inter-sample level, where explicit labels available for each image. However, in our graph-level OOD setting, biased infomax operates at the node level, where such labels are un- available. Due to the absence of node labels, approximate critical nodes using GNN explainer
32

---

Published as a conference paper at ICLR 2025
with adaptive thresholding. This additional procedure also distinct biased infomax from SCL and DGL.
Comparison with OOD-GCL (i et al., 2024a). LIRS and OOD-GCL both utilize contrastive learning to graph invariant features, however, LIRS relies on labeled data in the subsequent stage to effectively learn invariant features, in contrast, OOD-GCL aims to learn invariant features with- out labeled data, followed by fine-tuning a linear classifier on downstream tasks. This distinction highlights different assumptions and goals in the design of the two methods. Due the unavail- ability of labelled data, OOD-GCL underperforms LIRS across all the datasets. In terms of running time, DOD-GCL, is also significantly slower than LIRS and all other methods, as it requires multiple rounds of clustering in every epoch and additional invariance regularization, which must be applied for each channel and cluster.
G ALGORITHMIC PSEUDOCODE
We provide pscudocode for the proposed LIRS framework, which consists of 3 stages for learning spurious features and invariant features respectively. The code will be made publicly available upon acceptance of our work.
H
MORE DETAILS ABOUT EXPERIMENTS
H.1 DATASETS DETAILS
Table 7: Details about the datasets used in our experiments.
DATASETS
Split
TRAINING
# VALIDATION
TESTING
# CLASSES
METRICS
Scaffold
24682
4113
4108
ROC-AUC
GOOD-HIV
Size
26169
4112
3961
ROC-AUC
Base
18000
3000
3000
ACC
GOOD-Motif
Size
18000
3000
3000
ACC
Scaffold
1631
204
204
ROC-AUC
OGBG-Molbbbp
Size
1633
203
203
ROC-AUC
Scaffold
1210
ROC-AUC
OGBG-MMllace
Size
1211
151
ROC-AUC
SPMatif-binary
Correlation
6000
2000
2000
ACC
SPMotif(#G.
Correlation
9000
3000
3000
ACC
In this subsection, we provide detailed introduction to the datasets used in this work, the dataset statistics are illustrated in Table
SPMotif dataset. Following Wu et al. (022cc. generate 3-class synthetic datasets based BAMotif (Ying et al.) 2019). In these datasets, each graph comprises a combination of invariant and spurious subgraphs, denoted by Ge and G,, The spurious subgraphs include three structures (Tree, Ladder, and Wheel), while the invariant subgraphs consist of Cycle, House, and Crane. The task for model is determine which one of the three motifs (Cycle, House, and Crane) is present in 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 the invariant subgraph G,, Specifically, given the predefined bias the probability is b while for the others is (1 6)/2 (c.g.. House-Ladder, House- Wheel). When 6 1. the invariant subgraph is equally correlated to the three spurious subgraphs in the dataset. SPMotif datasets, directly influenced by C, and C is causally related with Y. For the variant of the SPMotif datasets used in Section 3] we attach 3 invariant subgraphs Ge to a base spurious subgraph, and in the test dataset, only invariant subgraph is attached to G.,
a specific motif (e.g.. House) and a specific base graph (Tree) will co-oceur
SPMotif binary dataset. To evaluate the feature learning quality of various OOD methods, We curate binary classification dataset based the SPMotif dataset, which is utilized in Section 5.3
33

---

Published as a conference paper at ICLR 2025
Algorithm The LIRS framework
Require: Graph dataset D with labels )"; training epochs E, E'; threshold т; hyperparameter Y regularization weight À
Ensure: Trained GNN model f p
1: Initialize GNN encoder (t(-)
2: for epoch
E do for each graph ( in D do
D Step Learning spurious features via biased infomax
3:
4:
Obtain graph representation h < h(G)))
5:
Use GNN explainer e(-) to identify important nodes G
Remove GO from GO to get G(i)
6:
Compute predicted probabilities g(() p(hgg) and g( p(h(G(())
7:
8:
if (g() g then
9:
Obtain h using Eqn.
(biased infomax)
10:
else
11:
Obtain hG using Eqn. end if
(standard infomax)
13:
end for
end for
15:
Obtain spurious embeddings (h!²) from the trained encoder f(())
for each class y in do
Step 2: Clustering and Re-fitting Classifier
17: Collect spurious embeddings (h.) gy(0) = y}
Perform clustering using Minibatch KMeans on (h!") get cluster labels {c(*)
19: Train a linear classifier (c.g., SVM) on (h!" ,c()) to obtain spurious logits (5)
end for
21: Re-initialize GNN encoder h(-), and classification head p(-), p'(.) & Step 3: Learning invariant features
22: for epoch t = 1 to E' do
23:
for each graph (()) in G do
24:
Obtain graph representation 66
h(G())
25:
Compute estimated spurious logits g(i) + o/bb)
(s (1) y>
26:
Compute reweighting coefficient w
where j is the cluster label
7
Compute invariant loss using Eqn.
28:
Update model parameters by minimizing:
L LERM XLinv
30:
end for
31:
end for
32: return Trained model f po
Specifically, the motifs House and Crane are assigned label and Diamond and Cycle assigned label I. During the construction of each class's samples, we attached both invariant subgraphs to the base subgraph with 50% chance, while in the remaining 50%, we randomly attached one invariant subgraph to the base spurious subgraph. For the test set, we randomly attached single invariant subgraph the base subgraph. Similar the SPMotif dataset, the base spurious subgraph was correlated with the target labels where b controls the correlation strengths, and in the test set an equal correlation strength is assigned for the samples in the same class.
GOOD-HIV is molecular dataset derived from the MoleculeNet Wu et al. (018) benchmark, where the primary task is to predict the ability of molecules to inhibit HIV replication. The molecular structures are represented as graphs, with nodes atoms and edges chemical bonds. Following Gui et al. (022), We adopt the covariate shift split, which refers to changes in 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
34

---

Published as a conference paper at ICLR 2025
scaffold Bemiss& & Murcko (1996) and the number of nodes in the molecular graph two domain features to evaluate our method.
GOOD-Motif is synthetic dataset designed to test structure shifts. Each graph in this dataset is created by combining a base graph and a motif, with the motif solely determining the label. The base graph type and the size 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 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.
Open Graph Benchmark. We also use 2 molecule datasets from the graph property prediction task on Open Graph Benchmark Hu et al. (2020) or known as OGBG. They were originally collected by MoleculeNet (Wu et al. 2018) and used to predict the properties of molecules, including (1) blood-braie barrier permeability in MoIBBBP: (2) inhibition to human f-secretase I in MoIBACE.
For all molecule datasets, we use the scaffold splitting procedure as OGBG adopted (Hu et al., 2020).
attempts to separate structurally different molecules into different subsets, which provides a more realistic estimate of model performance in experiments (Wu et al. 2018). In addition, we also adopt
size split to evaluate the OOD generalization ability for various OOD methods following Sui et al. 2023 Gui al. (022))
H.2 EXPERIMENTAL SETUP
Encoding spurious features with biased infomax. We adopt MVGRL (Hassani & Khasahmadi 2020) the contrastive learning method for learning spurious features. To realize instance-level adaptive biased infomax, we first utilize GSAT (Miao et al. 2022) as the GNN explainability frame- work identify important nodes in a graph. The biased infomax principle is realized using con- trastive learning, with InfoNCE (Oord et al. 2018) loss as the neural mutual information estimator. The estimated nodes from GSAT in a graph G is treated as negative samples rather than positive ones. Consequently, for graph G, the graph representation is optimized to align closely with nodes from G2 while diverging from the representation of nodes in G.. The GNN backbone for GSAT is 5-layer GIN (Xu et 2018). the hidden dimension is set to 64 for all the datasets except MolHIV, where the hidden dimension is 128. During inference stage, we obtain top-K edges with highest probability in each graph instance and perform counterfactual inference, i.e., after the removal of the subgraph induced by the top-K edges, we record the change in the prediction score Aprob- and compare with pre-defined threshold to decide whether it should be biased not. The nodes in a graph will be treated as negative examples during training MVGRL if Aprob > т. In all the experiments, K is searched over: {8, 12). is searched over: {0.2, 0.3). For SPMotif datasets, directly use the ground-truth nodes from Ge, and don't 't employ GSAT for approximation.
Generating logits from spurious features and target labels. We useMiniBatth KMeans algorithm to obtain the clustering label. To generate (soft) logits as targets from spurious features learned via biased infomax in each cluster, we use linear svm followed by a probability calibrator.
GNN encoder. For SPMotif dataset and SPMotif-binary dataset, we adopt 5-layer GIN (Xu et al., 2018 as backbone GNN encoder with mean pooling: For GOOD-Motif datasets, we utilize a 4- layer GIN with sum pooling, and a hidden dimension of 300; For GOOD-HIV datasets, we employ a 4-yayer GIN with sum pooling, and hidden dimension of 128; For the OGBG-Molbbbp and OGBG-Molbace dataset, we adopt a 4-yayer GIN with sum pooling, and the dimensions of hidden layers is 64.
Optimization and evaluation. By default, we use Adam optimizer (Kingma & Ba 2014) with learning rate of le 3 and batch size of 64 for all experiments. we also employ an early stopping of 10 epochs according to the validation performance for all datasets. Test accuracy or ROC-AUC is obtained according to the best validation performance for all experiments. All experiments are with 4 different random seeds, the mean and standard deviation are reported using the 4 runs of experiments.
Baseline setup and heprpaaraeeters. In our experiments, for the GOOD and OGBG-Molbbbp datasets, the results of ERM, IRM, GroupDRO, and VREx are reported from Gui et al.) (2022). while the results for DropEdge, DIR, GSAT, CIGA, GIL,, GREA, FLAGG G-Mixup and ATA on
35

---

Published as a conference paper at ICLR 2025
GOOD and OGBG datasets are reported from Sui al. (2023). To ensure fairesss, adopt the same GIN backbone architecture as reported in Sui et al. (2023).
). For the remaining datasets and methods, 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 (1e 11e-1,11 1,, 1e2). The causal subgraph ratio for DIR is searched across {le 1 1, le 1, 1.0.2 0.4, 0.6). For RSC, the masking ratio searched over {0.2, 0.3, 0.4]. For DiverseModeel, the number of classifciation headers is searched over {5, 10, 20 and the penalty weight of the diversification loss is searched over {le 1, le 2, 1e - -3. For DropEdge, the edge masking ratio is seached over: {0.1, 0.2, 0.33. For GREA, the weight of the penalty loss is tuned over {le 2, le 1, 1,1.0,, and the causal subgraph size ratio tuned over (0.05, 0.1, 0.2, 0.3, 0.5). For GII., the penalty weight is searched over {le 5, le 3, le - 1, 1.0). and the number of environments is searched over {3, 10). For GSAT, the causal graph size ratio is searched over (0.3, 0.5, 0.7). For CIGA, the contrastive loss hinge loss weights are searched over {0.5, 1.0, 2.0, 4.0, 8.03. For DisC, we search over q in the GCE loss: {0.5, 0.7, 0.9). For LiSA, the loss penalty weights are searched over: le- 1, 1e - 2, le -3). For FLAG, the ascending steps over 11e-3,15 1e-2, 1c 1c-1). 1}. For AIA, the stable feature ratio is searched over (0.1.0.3, 0.5, 0.7, 0.9), and the adversarial penalty weight is searched over {0.01, 0.1, 0.2, 0.5, 5.0, For EQuAD, the penalty weight is searched over {le le - 2, le - 3). and the reweighting coefficient is searched over {0.1, 0.3, 0.5, 0.7, 0.9].
set to 3 as recommended in the paper, and the step size is searched
Hyperparameter search for LIRS. The penalty weight for Lio in LIRS is searched over {le 1, le 3). The reweighting coefficient 7 is searched over {0.1, 0.3, 0.5, 0.7, The cluster number C' is searched over {3, 5, 10). The training epoch E' at which the spurious embedding is derived from the biased infomax searched over {50, 60, 70, 80, 90) for real-world datasets, and (0,,60,
for the synthetic datasets, The training epoch E is searched over (5, 6, 7,9.
Implementation of LIRS. We extend the code from GSAT (Miao al. 2022) annotate the nodes in each graph to be biased in real-world datasets. We adopt PyGCI. (Zhu et al. 2021) package and modify the source code in DualBranchConrrast to implement the biased infomax to generate spurious embeddings. To generate logits from the spurious embeddings, linearSVC, and CalibrateCClasssiecCV in Scikit-Learn package (Pedregosa et al. 2011). We use PyTorch Paszke et al. (2019) and eetorch-Geomette Fey & Lenssen (2019) for the remaining im- plementation.
use MiniBatchKMeans,
H.3 ADDITIONAL EXPERIMENTAL RESULTS
Visualization latent features derived from the biased infomax. We provide visualization of the 2d latent embedding derived form the biased infomax. Specifically, we utilize the SPMotif datasets and GOODMotif datasets assess the correlation between the learned embeddings after dimen- sionality reduction and environment labels within each class. We annotate each data sample with the environment label corresponding to three spurious patterns (Tree, Ladder, and Wheel). We then use the spurious features obtained from the biased infomax objective, apply t-SNE Van der Maaten & Hinton (2008) for dimensionality reduction, and use KMaans for clustering and visualization. The epoch which the latent embedding is obtained is selected according to the best hyperparameter. In Fig points of different colors correspond to different environment labels. It can be observed that within each class, the clusters highly correlate with environments, indicating that the biased infomax effectively captures different spurious patterns.
H.4 SOFTWARE AND HARDWARE
All the experiments are ran with PyTorch (Paszke et al. 2019 and PyTorch Geometric (Fey & Lenssen 2019). We run all the experiments on Linux servers with RTX 4090 and CUDA 12.2.
36

---

Published as a conference paper at ICLR 2025
Y=0
Y=1
Y=2
(a) GOODMotif base
(b) SPMotif-0.60 (#C. 3)
Y=0
(c) SPMotif-0.90 (#. 3)
Y=0
lpoc eox Unted
libe nea
40-
-00
-40
-60
-16
-10
-00
(d) SPMotiffbinary--O.e
20
-00
-00
(c) SPMotif-binne -0Motif-binarr-O.600
Figure 6: Clustering visualizations using latent embeddings derived from the biased infomax. The clusters resulted from latent embeddings obtained from the biased infomax are highly correlated with the environment labels.
37


Reviews:
[{"review_id": "TcpaVzSL43", "reviewer": "Reviewer_8xLE", "summary": "This paper introduces LIRS, a framework designed to improve Out-of-Distribution (OOD) generalization in graph representation learning by decoupling spurious and invariant features. The authors propose a two-step approach: (1) identifying and removing spurious features using a biased infomax principle, and (2) isolating invariant features through a class-conditioned cross-entropy loss. This method is positioned as an alternative to learning invariant features directly from graph representations, offering a new perspective on handling spurious correlations in graph learning.", "questions": "- How does the multi-step process of identifying and removing spurious features impact overall model efficiency? Have any time or resource costs been benchmarked compared to existing methods?\n\n- Can the authors provide a more detailed explanation of how LIRS differs from related works like EQuAD or OOD-GCL?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-structured and easy to follow, with clear motivation for the proposed approach.\n\n- The strategy of first learning and removing spurious features is an interesting and novel perspective on OOD generalization in graph learning. This decoupling of spurious and invariant features is a unique contribution to the field, offering a potential advantage over direct approaches.", "weaknesses": "- The two-stage process introduces additional complexity in the learning pipeline, which may increase computational costs and practical challenges. A more detailed discussion of potential trade-offs, such as time complexity and training efficiency, would be beneficial.\n\n- The novelty of the contribution could be clearer, as parts of the method bear resemblance to existing work, particularly in the use of biased infomax and cross-entropy loss. A deeper comparison with related approaches, such as OOD-GCL or EQuAD, would strengthen the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "B9EtTbPz6S", "reviewer": "Reviewer_Nv5f", "summary": "This paper proposes LIRS, a learning framework designed to Learn graph invariance, which consists of: a) The biased infomax principle, and b) The class-conditioned crossentropy loss, which elicit effective spuriosity learning and invariant learning respectively, aiming to learn more invariant features. Different from most existing approaches that directly learn the invariant features, LIRS takes an indirect approach by first learning the spurious features and then removing them from the ERM-learned features.", "questions": "See the Weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.  The structure of the paper is clear and easy to follow.\n2.  The paper conducts comprehensive experiments to demonstrate the performance of proposed method.", "weaknesses": "1.  The novelty seems limited. The core idea of LIRS is three parts, i.e., graph Invariance learning by removing spurious features, the biased infomax principle, and the class-conditioned cross-entropy loss. However, the first part is inspired by [1], the second part seems to be a combination of SCL[2] and DGI[3], the third part is the generalized cross-entropy (GCE) method[4]. The technical contribution is a little weak. It is recommended that the author provide a clearer description of the contribution.\n2.  The proposed LIRS requires training the GNN encoder twice, which is more cost than the end-to-end methods. It is recommended that the authors provide an overall time cost.\n3.  LIRS takes an indirect approach by first learning the spurious features by self-supervised and then removing them from the ERM-learned features. OOD-GCL[5] proposes a contrastive learning module with invariance regularization so that spurious correlations between latent factors in graph representation can be eliminated and OOD predictions in downstream tasks can be achieved. It is suggested that the authors analyze and compare OOD-GCL that directly learns invariant representations by self-supervised.\n\n[1] Empowering graph invariance learning with deep spurious infomax. ICML, 2024.\n\n[2] Supervised contrastive learning. NeurIPS, 2020.\n\n[3] Deep graph infomax. ICLR, 2019.\n\n[4] Generalized cross entropy loss for training deep neural networks with noisy labels. NeurIPS, 2018.\n\n[5] Disentangled Graph Self-supervised Learning for Out-of-Distribution Generalization. ICML 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "swRTNtuQi7", "reviewer": "Reviewer_6k7Q", "summary": "This paper presents LIRS (Learning graph Invariance by Removing Spurious features), a novel framework for improving Out-of-Distribution (OOD) generalization in graph representation learning. It critiques existing methods like IRM and VRex for capturing only limited invariant features. Instead of directly learning invariant features, LIRS first identifies and removes spurious features from those learned via Empirical Risk Minimization (ERM). The framework utilizes the biased infomax principle for learning spurious features and a class-conditioned cross-entropy loss for isolating invariant features. This work offers a robust approach to enhancing OOD generalization in graph learning.", "questions": "Is there an analysis of how the multi-step process in this indirect learning approach affects the overall results? Additionally, during empirical training, what observations did you make? If the final performance does not improve, how would you analyze the sources of performance issues?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and easy to follow.\n2. The strategy of decoupling invariant and spurious features is common in the field, but learning the spurious features first before removing them offers a new perspective. This approach provides a novel way to tackle the challenges of OOD generalization in graph representation learning.", "weaknesses": "Complexity: The process of first identifying spurious features and then removing them may introduce additional complexity in the learning pipeline. Discussing the computational efficiency and potential challenges in this two-stage process would be useful for understanding the trade-offs involved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AVaMy6IF6P", "reviewer": "Reviewer_vWa5", "summary": "This paper presents a graph invariant learning method based on spurious feature learning, termed LIRS. The authors argue that directly learning invariant features is challenging, prompting them to first learn spurious features in order to decouple them from graph representation to get the invariant parts, thus this approach necessitates training the encoder for two times, separately. They introduce a learning objective called bias infomax for the spurious feature encoder, and a loss function $L_{inv}$ designed to encourage the encoder to learn invariant features. The authors validate the effectiveness of both loss functions through theoretical analysis. \n\n\nHowever, I find the theoretical feasibility of $L_{inv}$  to be somewhat questionable (see the question part). Additionally, the proposed method appears to be more complex than standard graph invariant learning methods, yet there is no discussion of its efficiency (e.g., time complexity or reported training times), which raises concerns for me. Therefore, I rated it a 5, anticipating that the authors will address my issues, which may prompt me to reconsider my score.", "questions": "1.  About $L_{inv}$, I think it's implemented using cross entropy, $\\hat{s}^{i}$ is the prediction of the environmental label ${s}^{(i)}$ by using $\\hat{h_G}$ , and look forward to by minimizing the cross entropy to make prediction closer to real label. Intuitively, i don't think this is helpful for learning invariant learning, because if the learned representation is the invariant feature, I don't think $\\hat{h_G}$ should be able to predict the correct  ${s}^{(i)}$, since it should only be related to labels. Mathematically speaking, the authors claim in Proposition 7 in the Appendix that minimizing $L_{inv}$ is equivalent to maximizing the conditional entropy $H(s^{(i)}|\\hat{h_G^i})$, \nwhich I doubt is valid. Known $L_ {inv} $ is cross entropy, we have a $H(s^{(i)}|\\hat{h_G^i})$ = $H(s^{(i)},\\hat{h_G^i})$-$H(\\hat{h_G^i})$ .Minimizing the cross-entropy loss ($H(s^{(i)},\\hat{h_G^i})$) fails to maximize the conditional entropy.\n2. LIRS requires multi-step training and involves multiple models (GSAT,SVM, etc.). Is it less efficient than existing graph-invariant learning models? \n3. What is the difference between you and the existing method (EQuAD)? Is LIRS an incremental improvement version of it?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. I agree that learning invariant features indirectly is intuitively likely to be easier and achieve better performance than a direct approach.\n\n2. The authors provide some experimental analysis to support its motivation, as well as some theoretical analysis to justify the two optimization objectives.\n\n3. Good experimental performance.", "weaknesses": "1. The author lacks a clear description of the differences between this method and the existing methods. As far as I know, for example, EQuAD, which the author has cited many times, I checked the article and found that the model pipeline of LIRS is very close to it, and the differences seem to be only whether utilize bias infomax and the definition of $s$ in $L_{inv}$.\n\n2. Missing details about the model, such as how to optimize bias infomax? As far as I know mutual information is hard to calculate, how does GSAT get the subgraph? Why choose this approach?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)