Dissecting the Failure of Invariant Learning on Graphs
Authors: Qixun Wang
Yifei Wang
Yisen Wang
Xianghua Ying
Venue: NeurIPS 2024 poster (2024)
Keywords: Machine Learning
Out-of-distribution Generalization
Invariant Learning
Graph Machine Learning
Primary area: graph_neural_networks

Abstract: Enhancing node-level Out-Of-Distribution (OOD) generalization on graphs remains a crucial area. In this paper, we develop a Structural Causal Model (SCM) to theoretically dissect the performance of two prominent invariant learning methods--Invariant Risk Minimization (IRM) and Variance-Risk Extrapolation (VREx)--in node-level OOD settings. Our analysis reveals a critical limitation: these methods may struggle to identify invariant features due to the complexities introduced by the message-passing mechanism, which can obscure causal features within a range of neighboring samples. To address this, we propose Cross-environment Intra-class Alignment (CIA), which explicitly eliminates spurious features by aligning representations within the same class, bypassing the need for explicit knowledge of underlying causal patterns. To adapt CIA to node-level OOD scenarios where environment labels are hard to obtain, we further propose CIA-LRA (Localized Reweighting Alignment) that leverages the distribution of neighboring labels to selectively align node representations, effectively distinguishing and preserving invariant features while removing spurious ones, all without relying on environment labels. We theoretically prove CIA-LRA's effectiveness by deriving an OOD generalization error bound based on PAC-Bayesian analysis. Experiments on graph OOD benchmarks validate the superiority of CIA and CIA-LRA, marking a significant advancement in node-level OOD generalization.

Dissecting the Failure of Invariant Learning on Graphs
Qixun Wang'
Yifei Wang? 2
Yisen Wang 1.
Xianghua Ying
State Key Laboratory of General Artificial Intelligence,
School of Intelligence Science and Technology, Peking University
CSAIL,, MIT Institute for Artificial Intelligence, Peking University
Abstract
Enhancing node-level Satt--f-DDtributiin (OOD) generalization on graphs remains crucial area of research. In this paper. we develop Structural Causal Model (SCM) to theoretically dissect the performance of two prominent invariant learning methods-Invarianl Risk Minimization (IRM) and Variance-Rist Extrapolation (VREx)-ae in node-level OOD settings. Our analysis reveals a critical limitation: due to the lack of conditonn invariance constraints, these methods may struggle to accurately identify the structure of the predictive invariant ego-graph and consequently rely on spurious features. To address this, we propose Cross- environment Intra-class Alignment (CIA), which explicitly eliminates spurious features by aligning cross-enviromment representations conditioned on the same class. bypassing the need for explicit knowledge of the causal pattern structure. To adapt CIA to node-level OOD scenarios where environment labels are hard obtain, we further propose CIA-LRA (Localized Reweighting Alignment) that leverages the distribution neighboring labels to selectively align node represen- tations, effectively distinguishing and preserving invariant features while removing spurious ones, all without relying on environment labels. We theoretically prove CIA-LRA's effectiveness by deriving OOD generalization error bound based on AAC-Bayesian analysis. Experiments on graph OOD benchmarks validate the superiority of CIA and CIA-LRA, marking significant advancement in node- level OOD generalization. The codes are available at hhtpps:/ //gi thub. com/ ittp::/eeeeetttae222eeaaaaaaaa--
NDVVlg1or664//leurrPs22- InvarianInvninnn -earnineeannnngg on- Graphs
Introduction
Generalizing to unseen testing distributions that differ from the training distributions, known as Out- Of-Distribution (OOD) generalization, is one of the key challenges in machine learning. Invariant learning, which aims to capture predictive features that remain consistent under distributional shifts, a crucial strategy for addressing OOD generalization. Numerous invariant learning methods have been proposed to tackle OOD problems in computer vision (CV) tasks (Arjovsky et al. 2020 Krueger al. 202T Bui et al. 202T Rame et al. 2022 Wang et al. 2019 Mahajan et al. [022 I| Zhang et al. 2021a Wang et al. 2022a Yi al. 2022 Wang et al. 2022b Xin al. [023]. While in recent years, enhancing OOD generalization on graph data is an emerging research direction attracting increasing
attention. In this work, focus the challenge of node-level OOD generalization on graphs.
Straightforwardly adapting the above methods nove-level graph OOD scenarios presents several challenges: 1) the prediction of node's 's label depends on its neighbored samples in ego-subgraph, causing a gap from conventional CV OOD scenarios where samples are independently predicted: and 2) environment labels in node-level tasks are often unavailable [Wu et al., 2021 Li al. 2023a
Cooresponding author: Yisen Wang byisen.wangeee wwt.ee@pppu.ccc..
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Liu et al. 2023], rendering invariant learning methods based on environment partitioning infeasible. To illustrate the failure of directly adapting traditional invariant learning to graphs. we evaluate two representative OOD approaches, Invariant Risk Minimization (IRM (Arovssyy et al., 2020 and Variance- Risk Extrapolation (VREx [Krueger et al., [02T]), D. in OOD node classification scenarios. We choose IRM and VREx for two reasons: 1) Numerous node-level graph OOD strategies [Zhang et al., 2021b Wu et al. 2021 Liu et al. 2023 Tian et al. 2024] utilize VREx as invariance regularization (details in Appendix (A.2). Therefore, analyzing VREx can cover significant portion of graph-OOD methods; and 2) IRM and VREx are two prominent OOD methods that we can theoretically prove to be effective on non-graph data (Proposition 2.2). By testing their performance on graph data, can better reveal the differences between graph and non non-graph data. We choose real-world graph datasets: Arxiv, Cora, and WebKB; synthetic datasets: CBAS and toy graph OOD dataset with spurious correlations between node features and labels for evaluation. From Table | we observe that IRM and VREx offer marginal or no improvement over ERM on both real-world and synthetic node-level graph OOD datasets. This naturally raises some questions here:
On graphs, why do traditional invariant learning methods fail? How to make them work again?
To theoretically analyze their failure modes, we build Struc-
Algoriihms
Large Cov.
Large Con.
Toy
tural Causal Model (SCM) to model the data generation process under two types of distributional shifts: concept shift and covari- ate shift, and gain a high-level understanding of the challenges in node-level OOD generalization: To correctly predict node's 's label, the structure of a predictive invariant neighboring ego- graph (which we call it causal pattern) and their invariant node features must be learned. However, identifying the correct structure of the causal pattern presents additional optimization requirements (compared to CV scenarios) for Graph Neural Networks (GNNs) since they must adjust the aggregation pa- rameters (such as the attention weights in GAT [Veličković et al.) 2018) to achieve this. IRM and VREx lack class-conditional invariance constraints, which causes insufficient supervision for regularizing the training of these aggregation parameters, leading to non-unique solutions of GNN parameters and potentially resulting in the learning of spurious features. (detailed analysis is in Section 2 To overcome this, we propose Cross-enviromment Intra-class Alignment (CIA) that further considers class-conditional invariance to identify causal pattern: We theoretically demonstrate that by aligning node representations of the same class and difterent environments, CIA can eliminate spurious features and learn the correct causal pattern, as same-class snffereett-nvironnnee samples share similar causal patterns while exhibiting different spurious features. [ shows CTA's empirical gains. To leverage the advantage of CIA and adapt it to scenarios without environment labels, we further propose CIA-LRA (Localized Reweighting Alignment), utilizing localized label distribution to find node pairs with significant differences in spurious features and small differences in causal ones for alignment, to eliminate the spurious features while alleviating the collapse of the causal ones. Our contributions are summarized as follows:
ERM
57.74
59.57
33.6
IRM
57.59
$4.9
VRÉS
58.46
59,83
33.9
(ours)
39.68
60.89
37.0
LRA (ouns)
61.94
63,03
39.1
aver- age OOD accuracy on the covari- ate/concept shift of Arxiv, Cora, CBAS, and WebKB. Toy denotes results on our toy synthetic graph OOD dataset.
Table I: Real-Cov./Con
1. By constructing an SCM, we provide a theoretical analysis revealing that VREx and IRM could rely on spurious features when using GAT-like GNN (Section (.2) in node-level OOD scenarios, revealing a key challenge of invariant learning on graphs.
2. We propose CIA and theoretically prove its effectiveness in learning invariant representations on graphs (Section B.I.p To adapt CIA to node-level OOD scenarios where environment labels are unavailable, we further propose CIA-LRA that requires no environment labels or complex environmental partitioning processes to achieve invariant learning (Section 3.2). with theoretical guarantees on its generalization performance (Section
3. We evaluate CIA and CIA-LRA on the Graph OOD benchmark (GOOD) Gui et al. 2022 on GAT and GCN (Kipf and Welling 2016). The results demonstrate CIA's superiority over
2 Althoouhh numerous node-level OOD strategies from different perspectives have been proposed such as GNN architecture design [Wu et al. [2024) or feature augmentation et al. (203b). we focus on developing an invariant learning objective that could be integrated into and improve other graph-OO) frameworks in a plug- plug-and-pa and-play manner (validated in Section serving as general solution.

---

non-grap non-graph invariant learning methods, and CIA-LRA achieves state-of-ther -ht---artttt-tttt performance (Section 5.2)
We leave comparisons of our method and existing node-level OOD works in Appendix A.3
2 Dissecting Invariant Learning on Graphs
For OOD node classification, we are given a single training graph g (A, X,Y) containing N nodes V == {ui}i=1 from multiple training environments E &g. A E [0, NN is the adjacency matrix, A.j = iff there is an edge between eN and Fy.. X E RNDD are node features. The i-th row X₃ E R represents the original node feature of 24. Y E {0, C 13 are the labels, C the number of the classes. Denote the subgraph containing nodes of environment
G (A*,, X YO), which follows the distribution Pe. Let A {0, 1) N X and DR be the adjacency matrix and the diagonal degree matrix for nodes from environment respectively, where D Ej= A Ne is the number of samples in e. Denote the normalized adjacency matrix as A = (D + IN- A + Ix-)= Ix= is the identity matrix. Let A A (D + IN=) IN= (D= + [N=)= 2. 3 Suppose the unseen test environments are Eic- The test distribution Per # pe Ve' E & Ve E &g. OOD generalization aims minimize the prediction error over test distributions.
To understand the obstacles in invariant learning on graphs, we start by examining whether IRMv1 (practical implementation of the original challenging IRM objective, proposed by Arjovsky et al. (2020) and VREx can be successfully transferred to node-level graph OOD tasks. Their objectives are follows:
(IRMv1) min [.[C (w (X + V wff== (w 6(x)), (2)
(VREx) min E.(4 L (w ø X Y*] - Var, L (w ) YT)] w.P
where and denote the classifier and feature extractor, respectively. L is the cross-entropy loss. some hyperparameter.
2.1 A Causal Data Model on Graphs
Data generation process. We construct an SCM to character- ize two kinds distribution shifts: concept shift (Figure Ia] and covariate shift (Figure [b). C' and S denote unobservable causal/spurious latent variables that affect the generation the graph G. and dashed E are environmental variables usually unobservable. We consider a simple case that each node in environment has 2-dim feature [ar,, 2?]" x x R. Denote the concatenated node features of all nodes in e as X1 R and X3 IR,N x1 corresponding ai and x respectively. For the SCM Figure l the data generation process of environment is
(a) shift
concept
(b) shift
covariate
Figure 1: Causal graphs of the SCMs considered our work.
Y = (Ár) + n1. X5 (Ár)TIY + t
(2)
where & E N+ represents the "depth" (number of hops) of the causal pattern, and m E N+ is the depth of the ego-graph determining the spurious node features. ni E N represent random Gaussian noise. e" stands for an environmental variable, causing the spurious correlations between Xς and Y. A detailed description of the model is in Appendix F.T
x1 and n22 E N=
How the proposed model considers both node feature shifts and structural shifts? X1 represent invariant node features causing Y X denotes spurious node features that vary with environments. As for structural shifts, we consider an environmental Å in Equation 2 which means the structure can vary with environments. For example, there could be spurious correlation between certain structures and the label; or, the graph connectivity or size may shift [Buffelli et al. 2022 Xia et al.
Duee to space limitation, only present the concept shift case in the main text and leave the covariate shift case in Appendix B Our following results in Section hold for both shifts.

---

2023]. We model the invariant structural feature as the structure of a node's k-layer neighboring ego-graph. See Appendix F.2 for more discussions of the structural shifts.
We also have the following assumption about the stability of the causal patterns across environments: Assumption 2.1. (Stability of the causal patterns) The k-layer causal pattern in Equation (2) is invariant across environments for every class c.
A simple multi-layer GNN. Consider L-layer GNN f parameterized by C (1, Og 01 00200 00(0) 02(0) s. 1,1= --1=1,2 1,2,
fe(A, 10)00 0
02 where
03 01
(1-1)
(1T T! (A 1)
0
1= 2..,, H1" =X1, H²
=X2-
(2(1-1)
(2(1-1)
H
(3)
where 02 and 03 (1)
scalars for i,j E [1, VL. H END are GNN representations.
Remark. In this GNN, keep only the top-layer weight matrix (0, 02]T, and let the weight matrix of lower layers 1, 1....,,
be an identity matrix. This architecture resembles an SGC [?]. 01 and 0₂ for invariant/spurious features, respectively. 01"h 0g are weights for aggregating features from neighboring nodes and 02((), 0²()) are weights for features of a centered node, this setup can be seen as GAT. When all lower-layer parameters equal 1, the GNN degenerates to GCN (see Appendix
F.2 for justification of the choice of the GNN).
We consider regression problem that aim minimize the MSE loss all environments Eny.na
E. [R())
E,
(A,, X²) 11 The optimal invariant parameter set O* is
0 =
02 0 31 E {1, L 1) s.t. 01 02(0) =0
0 = 1, 62 1, 1 L
+1
01 (1) 0, oz(0) 1, 1= L
In Equation (4) the GNN parameters for spurious features (line 2) is zero, which means it removes spurious node features. Also, it learns the correct depth the causal pattern A X, (line 3-4).
2.2 Intriguing Failure of VREx and IRM on Graphs
Now we are ready present the failure cases in this node-level OOD task: optimizing IRMv1 and VREx induces model that relies on spurious features X5 to predict, leading to poor OOD generalization. To illustrate that this failure arises from the graph data, we first prove that IRMv1 and VREx can learn invariant features under the non-graph version of SCM of Equation ().
Proposition 2.2. (IRMv1 and VREx can learn invariant features for non-graph tasks, proof is in Appendix G.I.1) For the non con-grrph version of the SCM in Equation (2)
Y X1 + R4, X Y +22 +
(5)
VREx and IRMvl can learn invariant features when using a linear network: f(X) = 8, + Hg
Now we will give the main theorem revealing the failure of VREx and IRMv1 on graphs.
Theorem 2.3. (IRMv1 and VREx will use spurious features on graphs, informal) Under the SCM of Equation (2). the IRMvl and VREx objectives have uniuueq solutions for parameters of the GNN 3 and there exist solutions that use spurious features, i.e. 82 + 0.
Intuitive illustration of the failure. From Theorem 2.3 we find that the main reason for the failure lies in the saassgg-ppssing mechanism in representation learning. Let's provide some key steps in the proof of the IRMvl case as an illustration. For the non-graph OOD task Equation (5). we can verify that when IRMv1 objective is solved, i.c. R()) for all the invariant solution 0g 0

---

leads to (81) X1 8 X1 = 0, which can be satisfied when @ = 1. However, in the graph case, 02 leads to
((A)) (A')'* - (
0, Ve,
(6)
where (A+)*X, X1 is the learned representation of the GNN, 0 T., k is the depth of the causal pattern. Now we explain why the invariant solution may not hold on graphs. When the depth of the learned aggregation pattern * k. Equation 6 cannot hold for a fixed 02 (since 9, will depend on then). This means that identifying the underlying structure of the causal pattern imposes additional difficulty for invariant learning. Moreover, even if the GNN can learn representations of different depths (e.g. GAT the proof in Appendix G.1.3 shows that IRM failed to provide sufficient supervision to optimize the aggregation parameters tj. i.j E [1 such that & = k. A similar analysis holds for VREx. In general, successful invariant learning on graphs requires capturing both invariant node features and the structure of the causal pattern, while methods like IRM and VREx that solely enforce eoossennvionmmet invariance the loss leve may not be able achieve these goals. The formal versions and proof are in Appendix G.1.3 (IRM) and G.1.2 (VREx).
3
The Proposed Methods
3.1 Cross-environment Intra-class Alignment
Inspired by the examples of VREx and IRMv1, we aim to introduce additional invariance regular- ization guide the model in identifying the underlying invariant node features and structures. We propose CIA (Cross-environmes same class across different environments, Intuitively, since such node pairs share similar invariant fea- tures and causal pattern structures while differ in spurious features, aligning their representations will help achieve our targets. Denote the representation of node as de (i) and the classifier parameterized by Or. as he, CIA's objective is:
Intra-class Alignment), which aligns the representations from the
min Ehe [C(ho, o del (e(AA xx), v") s.t. 8
min Las = E e,e' E&E eft'
(i) (e)
9
(ij))ns
(7)
is the set of nodes with same label and from two different environments, L is the cross-entropy loss. D is some distance metric and we adopt L-2 distance. Now we prove that CIA can learn invariant representations regardless of the unknown causal patterns:
where D..."' (i,j)) jJYY =Y =CAE, E, e
Theorem 3.1. Under the SCM of Equation 22 and Assumption 2.1 optimizing the CIA objective will lead to the optimal invariant solution @r in Equation (4) for parameters the GNN 3
The proof is in Appendix G.I.4 By enforcing class- conditionl invariance, which is not considered in VREx and 1,Mv1, CIA overcomes the above obstacles and eliminates spurious features. As long as a GNN has the capacity to adaptively learn the true depth of the causal pattern (such as the one considered Equation
or a GAT), CIA can identify the invariant causal pattern.
Remark. One might note that the objective of CIA is analogous to MatchDG [Mahajan et al. 2021 However, we are the first to adapt such an idea to node-level OOD tasks and theoretically reveal its advantage. In Appendix A. we compare our extension and the original MatchDG in detail.
3.2 Localized Reweighting Alignment: an Adaptation to Graphs without Environment Labels
So far, we have theoretically and empirically validated CIA's advantage on graphs, but it still requires environmental labels that are challenging to obtain in most node classification tasks (Wu et al. 2021
Liu et al. 2023 Li al. 2023a) In this section, we propose CIA-LRA (Localized Reweighting Alignment) that realizes CIA's objective without using environment labels by identifying node pairs with significant/minor differences spurious/invariant features and then aligning their representations. As illustrated in Figure 2 CIA-LRA mainly incorporates three components:
'If the GNN is GCN that has fixed aggregation depth L.e. L. it will be even impossible learn the true causal pattern we choose an A l in advance.
'IRM minimizes the loss gradient w.r.t. the classifier in each environment, and VREx minimizes the loss variance across environments.
5

---

Localard rowighting algnnsst
CIA-ERA lose
feu Spaerre 1..00 -Ao
Auti 4e (/a J representatiin
Nodar. classo
Own
Regrosentziion rode giit
Rewnighting alignmentove Localized signment (,00
Rowdyi aertetttttttttto ol degerents geriese lood
Reweighttng aligmmett
Rigunal
L=2
Training graph 600
Supgaeph Pstactor
Total loss: for A A
My Ap 46,00
Retamertators g
gront
R. Menetren therrpor vy in Marei
Ag.
dige four dienperny Home,
Classiior
Cross entropy lose:
The overall framework of our proposed CIA-LRA. The invariant subgraph extractor Φe... identifies the invariant subgraph for each node. Then the GNN encoder dhe aggregates information from the estimated invariant subgraphs to output node representations. CIA-LRA mainly contains two strategies: localized alignment and reweighting alignment. Localized alignment: the alignment to local range to avoid overalignment that may cause the collapse of invariant features (shown in Appendix D.I). Reweighting alignment: better eliminate spurious features and preserve invariant features without using environment labels, we assign large weights to node pairs with significant discrepancies in heterophilic Neighborhood Label Distribution (NLD) and minor discrepancies in homophilic NLD. See Section 3.2 for detailed analysis of CIA-LRA.
Figure 2:
restrict
Localized alignment. To avoid learning a collapsed representation of invariant features, it is crucial align node pairs that share similar invariant features. To achieve this, we align nodes close each other (about 2 to 6 hops). This is based on two observations. First, we observe that spurious features tend to exhibit larger changes within local graph areas than invariant ones, and nodes from the same class that are too distant may differ more in their invariant features than the closer ones (evidence in Appendix D.4.. This is because invariant features are generally more stable than spurious ones, according to Chen et al. [022), [Schölkopf et al. (202T). Second, we empirically find that alignment over an extensive range or too many nodes yields only marginal performance improvements, or even leads to performance degradation (see Appendix (DI)), while increasing computational costs. This may also be attributed to the feature collapse caused by excessive alignment of too many node pairs. Formally, the local pairs are defined as (c) {(i j + A Y; Y, c A d(i,j) S (), where j(i,j) represents the the shortest path length from node o; to Vy. L E N+ is hyperparameter. Also, propose to assign smaller weights to pairs more distant away from each other.
Reweighting Alignment. Since environment labels are unavailable, we need a metric reflect the distribution of the spurious and invariant representations so that node pairs with significant/small differences in spurious/invariant features can be identified. Since we assume the causal patterns of the same class are similar (Assumption 2.1). the label distribution of homophilic (i.e., same- class) neighbors directly affects the invariant features aggregated to the centered node (empirical evidence in Appendix x D.5.2). Therefore, pairs with smaller differences in the ratio of homophilic neighbors should be assigned larger weights for alignment. The ratio discrepancy can be calculated as follows: y-aame (c),, = |rs -rÿl. where rf is the ratio of the neighbors of v, of class within hops (L is the number of layers of the GNN). As for spurious features, we utilize Heterophilic (i.... different-class) Neighborhood Label Distribution (HeteNLD) as measurement, as it affects the two kinds of main distributional shifts on graphs: 1) environmental node feature shifts, and 2) Neighborhood Label Distribution (NLD) shift (both empirically verified in Appendix I. HeteNLD determines the first kind of shift when correlations exist between labels and spurious node features, e.g., concept shift. The second kind, NLD shift, which is affected by HeteNLD, can be regarded as structural shift as the discrepancy in neighborhood distribution will induce a gap in the aggregated representations (Theorem 4.4 shows this shift increases OOD error). Although aligning the representations significantly differing in homophilic neighbor ratio mitigates these two kinds of shifts, it also leads to the collapsed invariant representations and suboptimal performance (Table 4 shows this effect). Therefore we assign larger weights to the pair with larger discrepancy in HeteNLD when
alignment. The discrepancy in HeteNLD is calculated as follows: ,il (c),s) = Ed r -ry

---

Invariant Subgraph Extractor. In Section 2.1 the structural invariant features are defined as the k-hop neighboring ago-graph for ease of analysis. However, in practice, the invariant structure may merely be a subgraph of the neighborhood nodes. To better capture the invariant ego subgraph, we train an invariant subgraph extractor inspired by [i et al. [223a]] Concretely, we learn an auxiliary GNN encoder de... (parameterized by mm) to predict an soft edge mask M E IR N&N, and then apply it during training and test:
Mi, = Sigmoid (0e... To) (i), Am A where C is sample-wise multiplication. (8)
Now we are ready to present the formal objective of CIA-LRA:
min 0,000
Cha,, @e X),, Y) s.t. min E.E iy 6,0m
(..))
p d(i, ((i,,))ramme (c)is)
where W Norm
Norm(-) denotes Min-Max normalization.
( (9. is the cross-entropy loss, Ste(t), pdiff (c)a.: r same (c)a. and d(i. are defined the above analysis. In practice, we use CIA-LRA as a regularization term added to the cross-entropy loss with a weight as hyperparameter. The detailed implementation of CIA-LRA is in Appendix
In Equation
4 Theoretical Justification: an OOD Generalization Error Bound
Now will derive an OOD generalization error bound to show that optimizing CIA-LRA can minimize OOD error. To achieve this, we adopt PAC-Bayesian framework following Ma et al. [2021] and establish Contextual Stochastic Block Model (CSBM, [Deshpande et al.) 2018) for OOD
multi-classification. The proposed CSBM-OOD is as follows (more discussions
Appendix F.4):
Definition 4.1. (CSBM-OOD). For node of class from environment its node feature 24 E R consists of two parts,
[0 = where Jiny R sampled from the Gaussian distribution Niee, T²T) is the invariant feature and Tap E TR sampled from the ( o² is the spurious feature. Suppose { and {Fz} for all e and e form sets of orthonormal basis. We use p!" to denote the homophilic ratio of node i's one- neighbors and use p (c') ) to denote the heterophilic ratio of node i's one-hop neighbors of class c' (c of c²). We assume Pr(y: c) are the same for all classes c.
The GNN model used for deriving the error bound (following Ma et al. [001]): The GNN model has a I-layer mean aggregation g that outputs the aggregated feature g, E R" for node i. The GNN classifier l on top of g is ReLU-activated L-layer MLP with W Wi...., Wg as parameters for each layer. h is from a function family H. The prediction for node i is h4 E && with h,[c] representing the predicted logit for class c. Denote the largest width of all the hidden layers
Denote nodes of environment as Ve. We consider the error of generalizing from a mixed training environment e any test environment e E &e. where Va- == Unge, V. represents all training nodes. To guarantee the generalization, we need to characterize the distance between
Notations.
Ve and Vae: define eats,e maxjev,, mintev... llg; 9ill2 as the aggregated feature distance between the training and test subgroup. Define the number of nodes in environment e as N.. We consider the margin loss of environment e that is used by Ma al. (202]), Mao al. 2023
E7 (h) = N E,,ev. [hg [yx] S 7 + maxey'u; hs[c]].
Now we introduce some assumptions adapted from Ma et al. 2021 that are used in our proof.
Assumption 4.2. (Equal-sized and disjoint near sets, adapted from Assumption of of et al. [2021)
For each node ii Ver, define v(()) {j Va- l|g: 93 I Ee",et J. For any test environment e/c
et assume (+) dt of each E Ver are disjoint and have the same size No E N+
Assumption 4.3. (concentrated expected loss difference, adapted from Assumption 3 of Ma et al.
2021) Let P be a distribution on H. defined by sampling the vectorized MLP parameters from
'For OOD scenarios that spurious features are not correlated with Y, we just need to let μ are the same for all in the environment this this definition without loss of generality.
7

---

N (0) for some o² (7/Se ) parameters WT. ......
2b( AN +In 26L) For any L layer GNN classifier h H. with model
WT, :T:,.,,W. define TA max |Will2- Assume that there exists some 0 < <
satisfying
Prior (h) L-) > Not HCCe e² The Cee
7 5)
N2r
Now we present the node-level OOD generalization bound (proof in Appendix
Theorem 4.4. (Subgroup OOD Generalization Bound for GNNs, informal). Let h be any classifier
in function family H. with parameters
Wi i=1
Under Assumption 4.2 and 4.3 for any elc
Eie y 2 and large enough Ne", there exist < 1 with probability least 6, we have ce (f)) < L2 (h) + 0
C 11ite - me) (1E" - -1 -
0F
(i)
c
+
(C
Ber
-16 =1="))+ 20 Ne
E iEVer
1
Σ
(d)) -1, (c(ce)) + const.
Ne
jEVIO
d'
(b)
(c)
(10)
where (c'lc) is the ratio of heterophilic neighbors of class d' when yi c, B
V. 1gill2 is the maximum feature norm, vlū) elr := {j Ver ll.: -illl2 I Eer,er const a constant depending on a, and
The observations from Theorem 4.4 is summarized as follows: Term (a) reflects the separability of the original features of different classes [[(ee )err ;; (4C u and the distance of the aggregated features between the training and test set eg The former factor is the nature of the dataset itself. Term (b) is the distributional discrepancy between the training and test subgroups, caused by the distribution shifts in spurious features. When there exist correlations between labels and spurious features, CIA-LRA can minimize this term by minimizing the representation distance of node pairs with large discrepancy in the label distribution of heterophilic neighbors" Term (c) measures the shift in HeteNLD between the training and test subgroups, representing the OOD error caused by the shift in the aggregated features of the same class. CIA-LRA minimizes this term by enforcing stronger alignment on pairs with greater HeteNLD differences.
Experiments
5.1 Experiment Setup
We run experiments using 3-layer GAT and GCN on GOOD Gui et al. 2022], a graph OOD bench- mark. We reported the results on both covariate shift and concept shift. The detailed experimental setup and hyperparameter settings are in Appendix C We compare our methods with the following
algorithms: ERM [Vapnik] 1999]; traditional invariant learning methods: IRM, VREx, GroupDRO
(Sagawa et al. 2019]. Deep Coral [Sun and Saenko 2016), IGA [Koyama and Yamaguchi 2020];
graph OOD methods: EERM, SRGNN, CIT [Xia et al. [2023] CaNet [Wu et al. 2024 graph data
augmentation:
Mixup WWang et al. 2021a]. GTrans [iin al. 2022].
5.2 Main Results of OOD Generalization
Table 2 reports the main OOD generalization results. The observations are summarized as follows: 1) CIA- LRA improves the best baseline methods by 2.44% and 3.23% GAT and GCN, respectively,
7 "Although the term 1nE" - 1 the envireenvirn distance of the original data, it can be minimized implicitly by aligning the representation induced by the two subgroups. This because minimizing the distance between learnable representations of two node groups is equivalent to using fixed mean aggregation on two groups with closer original features (in Theorem 4.4 we fix the feature extractor to be mean aggregation layer).
8

---

Table 2: OOD test accuracy (%). Our methods are marked in bold. The best and second-best results are shown in bold and underlined, respectively. The values in parentheses are standard deviations. 'OOM' denotes Out Of Memory. Results of EERM on Cora GCN marked by are from Gui et al. 2022] since we got OOM during our running.
(a) Results on GAT
Navggapp
Creggeaai
WerkB
Cxt
CBAS
WelkB
degne
wel
fegw
oéer
1atoeday
13M
54 1:110000
71 578.16
55 306.30
31 (N1-12
57.34
66.300 180
66 66.740105)
61. 60.30L IN
6.300
74522.97)
24 26.061:300
$2.57
57.1001141
21800112
(6-241138)
(6770035)
VRIx
54 10
71 010.30
55 340
54 211718.77
56.45
(6990110
(6100033)
71500350
27 27.526770
5933
66930
Deep Coel
54 1200200
71 (78.12)
55 1515
66.22 43)
56.26
(6770021
63AD017H 74
75.903211
202003.00 30.30
60/M
17000.171
00M
00M
55 116022
25 170
00M
0KM
(3.90033)
76.3422300
243665-00
Grygh spacllc mutted
00M
000
623992200
00M
001
90.807.00
25.304-20
SRGNN
54 2600311
71 3710-77
0L9000
(6-00180)
57.1
(6200111
61 20019)
77.161.271
71.551.90
Missp
99.300113
71 111900000
N6.716.30
96.1
06.200330
73.5434411
34.590675)
61A2
00M
90M
61 901166
71 6677
00M
00M
10-901 77)
71.597.10 110
00M
000
24 6017
00M
00M
10-900178
53 43
34
OhNei
00M
0UM
33.358.14)
0227002.55
15
0GN
68.200044
13.500:411
24.3 111300
CIMERA
99.400111
97.668.33)
75.34177)
61.94
67.80.6
68666664)
78 78,46390
80 (88
63,03
(b) Results on GCN
Coeatai- 44h
Concpp di
Dveaud
Agrzz
1882
cake
wed
oder
adharste
BKM
36.9902.14)
35.700332
1514133)
51.52
620001211
61390007)
612402A0)
54.323 131
21.300.55)
6875
IRM
58.09)111) 17)
7386/3
56.70000
64800030
12.744911
52.12
65.03000)
S1ARB0M)
27.520279)
04.54
59800331)
12.22122
57.2
22
60.35
59.89
13.913000
5300
14200239
01400027)
$3590030 36
64 3430
EL.9000
26440169
61.22
Desp Cand
$1.040118
21.042300)
14720020
11000-722
3981
0341021)
132000300
56550333)
D0A
59.6102117
73.9993
9903333
05151115 98)
15802220
57.00
(602.66)
64. 42.32903 19)
61390099
60.72
CBA
71.100335)
19.292.05
19
56.26
6155811
15.71/77)
26750187)
61.41
SRINN
56.770000
51.1500255
64500335
45400140)
5636
(2.900335)
54.330371
(0060007)
27.500679)
GUN
Mosp
728223113
15690-122
Glress
00M
00M
72 39:2443
165860090
0OM
00M
55 1440 14)
55 5639 181
(8.51147)
263111 551
CTT
00M
DOM
1369
07)
(000000
CaNe
0UM
OUM
DOM
00M
000000200 204
64 06
970147)
CI6-LRA
518818144
71801820)
19:00220
39.79
67.30880)
0272/833)
68.0718.11
94.500.3))
36.7018755
65,31
achieving state-of-the-art performance. 2) CIA outperforms IRM and VREx all splits, which validates our theoretical findings in Section 2 Notably, it performs best among the non-graph-speciffc methods. 3) CIA-LRA improves CIA in most cases. This suggests that our reweighting strategy can enhance generalization on graphs even without environment labels. 4) MatchDG outperforms IRM and VREx 12 out of 16 splits but underperforms CIA average (averaged over 16 splits except on Arxiv, CIA: 57.56, MatchDG: 56.73).
5.3 CIA can be Integrated into and Improve other Graph-OOD Methods
We replace VREx with CIA in the loss function of EERM
Algorithms
Com degroe
Coea wonl
CBAS
WibKB
to show that CIA can improve generalization in a plug-and- play manner. Table 3 shows that this improves original EERM by a large margin or has comparable performances, indicating the performance of nove-level OOD algorithms can be limited by VREx.
EERM
47.34
57,80
00.1
29.36
EERM-CIA
57.27
62.37
65.01
29.50
CIA
59.53
65.24
71.91
33.41
Table 3: By replacing VREx in EERM with CIA (marked as EERM-CIA), the performance is significantly improved.
5.4 Empirical Understanding of the Role of CIA-LRA
A synthetic dataset. We construct a synthetic dataset (mentioned in Section I to validate the role of each module in CIA-LRA in eliminating spurious features and preventing the collapse of invariant representations. We generate random graph and create 4-class OOD classification task. Each node has a 4-dim feature, with the first/last two dimensions representing invariant/spurios features (details in Appendix C.3 can disentangle the learned invariant and spurious representations.

---

Figure 3 depicts the OOD accuracy, the variance of the invariant representation, and the norm of the spurious representation across training epochs for CIA and CIA-LRA. The observations are summarized below.
Concept 100 su
Algorihue
Acc. (9)
IRM
61.14
VREx
61.32
8D (
63.22
180 Goe
63.91
63.64
Covariate 000 m0 20
63.39
(clL in numeraate
62.70
Table 4: Ablation study of CIA-LRA. Results are
Figure 3: Left: OOD test accuracy. Mid: the variance of the invariant averaged on the four representation. Right: the norm of the spurious representation. CIA splits of Cora.
and CIA-LRA use À = 0.5 in this figure.
1) Aligning the large discrepancy in HeteNLD helps to eliminate spurious features concept shift and improves generalization. As evident from the right column, incorporating ,if diminishes the norm of spurious features under concept shift. For covariate shift, while pdiff will not remove environmental spurious features due to their independence from labels, it still helps generalization since it reduces the error caused by shifts in HeteNI.D as predicted by Theorem 444 2) CIA-LRA alleviates collapse of causal representation that CIA may suffer when adopting a substantial A. When using a large À (= 0.5), the performance of CIA deteriorates the level of random guessing (25%) after approximately 50 epochs. In contrast, CIA-LRA sustains its accuracy at a high level because it avoids excessive alignment by aligning only local pairs and reweighting (further evidence in Appendix D.2. The mid column shows that the invariant features learned by CIA progressively collapse, even ICCA removes most spurious features (right column). 3) Maintaining the discrepancy in homophilic neighboring label distribution y-same helps keep the variance of the invariant representation, slightly improving performance.
Ablation study. We also conduct ablation studies on CIA-LRA. Table 4 shows that removing any module causes significant performance drop, demonstrating the effectiveness of each module.
5.5 Effects of the Hyperparameters of CIA-LRA
This section analyzes the effect of and t of CIA-LRA. [ that the test accuracy increases with when λ S 0.5. Too small leads to sub-optimal performance due to insuf- ficient regularization from aligning only a few pairs. Also, most parameter combinations out- perform the baseline methods, indicating that
560
6427
0.0
0.40
0.1
55.31
55.70
55.20
55.00
570
37
6433
03.52
62.0
1:03
425
56
56.73
55.07
55.17
55.07
+5
K2.00
55
56.1
19.00
15.11
63.36
452
CIA-LRA leads to consistently superior perfor- mance. Additional studies of the effects of A and are in Appendix D.2 and D.3 respectively.
(a) Cora degree concept (b) Cora degree covariate shift. ERM: 61.36, VREx: ERM: 55.30, VREx: 61.42, IRM: 61.77.
55.07, IRM: 55.34.
Figure 4: Effect of À and the number of hops / on OOD test accuracy (%).
Conclusion
In this work, by theoretically dissecting the failure of IRM and VREx in node-level graph OOD tasks, we attribute it to the difficulty in identifying the graph-specific causal pattern structures. To address this, we propose CIA with additional class-conditional invariance constraints and its environment- label-free variant CIA-LRA tailored for graph OOD scenarios. Further theoretical and experimental results validate their efficacy. Notably, CIA can be incorporated in other graph OOD frameworks, serving as a better invariant learning objective than the widely-used VREx graphs.
10

---

Acknowledgement
Yisen Wang was supported by National Key R&D Program China (20222D0160300) National Nat- ural Science Foundation of China (92370129, 62376010), and Beijing Nova Program (20230484344, 20240484642). Xianghua Ying was supported by the National Natural Science Foundation of China (62371009).
References
Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Pazz Invariant risk minimization. In ICML, 2020.
David Krueger, Ethan Caballero, Joern-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. Out-of-distribution generalization via risk extrapola- tion (rex). In ICML, 2021.
Manh-Ha Bui, Toan Tran, Anh Tran, and Dinh Phung. Exploiting domain-specifi features to enhance domain generalization. NeurIPS, 2021.
Alexandre Rame, Corentin Dancette, and Matthicu Cord. Fishr: Invariant gradient variances for out-of-distribution generalization. In ICML, 2022.
Yisen Wang, Xingjun Ma. Zaiyi Chen, Yuan Luo, Jinfeng Yi. and James Bailey. Symmetric cross entropy for robust learning with noisy labels. In ICCV, 2019.
Divyat Mahajan, Shruti Tople, and Amit Sharma. Domain generalization using causal matching, In ICML, 2021.
Dinghuai Zhang, Kartik Ahuja, Yilun Xu, Yisen Wang, and Aaron Courville. Can subnetwork structure be the key to -atoof-distribution generalization? In ICML, 2021a.
Ruoyu Wang, Mingyang Yi, Zhitang Chen, and Shengyu Zhu. Out-of-distribution generalization with causal invariant transformations. In CVPR, 2022a.
Mingyang Yi, Ruoyu Wang, Jiacheng Sun, Zhenguo Li, and Zhi-Ming Ma. Breaking correlation shift via conditional invariant regularizer. In ICLR, 2022.
Qixun Wang, Yifei Wang, Hong Zhu, and Yisen Wang. Improving by adversarial training with structured priors. NeurlPS, 2022b.
generalization
Shiji Xin, Yifei Wang, Jingtong Su, and Yisen Wang. On the connection between invariant learning and adversarial training for out-of-distributin generalization. In AAAI, 2023.
Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invariance perspective. In ICLR, 2021.
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, (1):1-30, 2023a.
Yang Liu, Xiang Ao, Fuli Feng, Yunshan Ma. Kuan Li, Tat-Seng Chua, and Qing He. Flood: A flexible invariant learning framework for out-of-distribution generalization on graphs. In SIGKDD, 2023.
Shengyu Zhang, Kun Kuang, Jiezhong Qiu, Jin Yu, Zhou Zhao, Hongxia Yang, Zhongfei Zhang, and Fei Wu. Stable prediction on graphs with agnostic distribution shift. arXiv preprint arX.v:2110.03865, 2021b.
Qin Tian, Wenjun Wang, Chen Zhao, Minglai Shao, Wang Zhang, and Dong Li. Graphs generalization under distribution shifts. arXiv preprint arXiv:2403. 1104403..66334.. 16334, 2024.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.

---

Qitian Wu, Fan Nie, Chenxiao Yang, Tianyi Bao, and Junchi Yan. Graph ization via causal intervention. arXiv preprint arXiv:2402.1 1494, 2024.
general-
Xiner Li, Shurui Gui, Youzhi Luo, and Shuiwang Ji. Graph structure and feature extrapolation for out-of-distribution generalization. arXiv preprint arXiv:2306.068 3,000,6,, 2023b.
Shurui Gui, Xiner Li, Limei Wang, and Shuiwang Ji. Good: A graph In NeurlPS, 2022.
benchmark.
Thomas Kipf and Max Welling. Semi-supervine classification with graph convolutional networks. arXiv preprint arXiv:1609.02900 2016.
Davide Buffelli, Pietro Liò, and Fabio Vandin. Sizeshiftreg: a regularization method for improving sereeenneralizttinn in graph neural networks. In NeurIPS, 2022.
Donglin Xia, Xiao Wang, Nian Liu, and Chuan Shi. Learning invariant representations of graph neural networks via cluster generalization. In NewrlPS, 2023.
Yongqiang Chen, Yonggang Zhang, Yatao Bian, Han Yang, MA Kaili, Binghui Xie, Tongliang Liu, Bo Han, and James Cheng. Learning causally invariant representations for outto---istribuutio generalization on graphs. NeurIPS, 2022.
Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings of the IEEE, (5):612-65) 634, 2021.
Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Subgroup generalization and fairness of graph neural networks. In NeurlPS, 2021.
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. In NeurlPS, 2018.
Haitao Mao, Zhikai Chen, Wei Jin, Haoyu Han, Yao Ma, Tong Zhao, Neil Shah, and Jiliang Tang. Demystifying structural disparity in graph neural networks: Can one size fit all? In NeurIPS, 2023.
Vladimir N Vapnik. An overview of statistical learning theory. IEEE Transactions Neural Networks, (5):988-999, 1999.
Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint arXiv:1911.0873: 2019.
Baochen Sun and Kate Saenko. Deep coral: Correlation alignment for deep domain adaptation. In ECCV Workshop, 2016.
Masanori Koyama and Shoichiro Yamaguchi. When invariance useful in an out-of-distribution generalization problem? arXiv preprint trXiv:2008.0188. 2020.
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. In WWW, 2021a
Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, and Neil Shah. Empowering graph representation learning with test-time graph transformation. arXiv preprint 20.0v:2210.0356:1 2022.
Yuge Shi, Jeffrey Seely, Philip HS Torr, N Siddharth, Awni Hannun, Nicolas Usunier, and Gabriel Synnaeve. Gradient matching for domain generalization. arXiv preprint axXiv:2104.099337 2021.
Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu. Improving adversarial robustness requires revisiting misclassified examples. In ICLR, 2020.
Junchi Yu, Jian Liang, and Ran He. Mind the label shift of augmentation-baan -aase graph ood generaliza- tion. In CVPR, 2023,
12

---

Haoyang Li, Ziwei Zhang, Xin Wang, and Wenwu Zhu. Learning invariant graph representations for -f-o----ittibutiinn generalization. In NeurlPS, 2022a.
Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi. Shift-robust gnns: Overcoming the limitations of localized graph training data. In NeurIPS, 2021.
Yongqiang Chen, Yatao Bian, Kaiwen Zhou, Binghui Xie, Bo Han, and James Cheng. Rethinking invariant graph representation learning without environment partitions. In ICLR Workshop, 2023a.
Fredrik D Johansson, David Sontag, and Rajesh Ranganath. Support and invertibility in domain- invariant representations. In AISTAYS, 2019.
Ling Yang, Jiayi Zheng, Heyuan Wang, Zhongyi Liu, Zhilin Huang, Shenda Hong, Wentao Zhang, and Bin Cui. Individual and structural graph information bottlenecks for out-of-distribution generalization. IEEE Transactions on Knowledge and Data Engineering, 2023.
Ying-Xin Wu, Xiang Wang, Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. arXiv preprini arXiv:2201 12872, 2022a.
Nianzu Yang, Kaipeng Zeng, Qitian Wu, Xiaosong Jia, and Junchi Yan. Learning substructure invariance for out-of-distribution molecular representations. In NeurIPS, 2022.
Tianrui Jia, Haoyang Li, Cheng Yang, Tao Tao, and Chuan Shi. Graph invariant learning with subgraph co-mixup for out-of-distribution generalization. arXiv preprint 2Xix:2312./0988 2023.
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, 2022b.
Yongqiang Chen, Yatao Bian, Kaiwen Zhou, Binghui Xie, Bo Han, and James Cheng. Does invariant graph learning via environment augmentation learn invariance? In NeurIPS, 2023b.
Xuexin Chen, Ruichu Cai, Kaitao Zheng. Zhifan Jiang, Zhengting Huang. Zhifeng Hao, and Zijian Li. Unifying invariance and spuriousity for graph out-of-distrionn distribbutii via probability of necessity and sufficiency. arXiv preprint urXiv:2402.09165, 2024.
Shurui Gui, Meng Liu, Xiner Li, Youzhi Luo, and Shuiwang Ji. Joint learning of label and environment causal independence for graph out-of-distribution generalization. In NeurIPS, 2024.
David Burshtein, Vincent Della Pietra, Dimitri Kanevsky, and Arthur Nadas. Minimum impurity partitions. The Annals of Statistics, pages 1637-1646, 1992.
Bernhard Schölkopf. Causality for machine learning. In Probabilistic and Causal Inference: The Works of Judea Pearl, pages 765-804. 2022.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? In ICLR, 2022.
Jincheng Huang, Ping Li, Rui Huang, Na Chen, and Acong Zhang. Revisiting the role of heterophily in graph representation learning: An edge classification perspective. ACM Transactions on Knowledge Discovery from Data, 2023.
Xinyi Wu, Zhengdao Chen, William Wei Wang. and Ali Jadbabaie. A non-asymptotic analysis of oversmoothing in graph neural networks. In ICLR, 2022b.
Huayi Tang and Yong Liu. Towards understanding the generalization of graph neural networks. In ICML,, 2023.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In ICLR, 2021.
Yifei Wang. Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Dissecting the diffusion process in linear graph convolutional networks. In NewrIPS, 2021b.
Yong Lin, Lu Tan, Yifan Hao, Honam Wong, Hanze Dong, Weizhong Zhang, Yujiu Yang, and Tong Zhang. Spurious feature diversification improves out-of-distribution generalization. arXiv preprint 230.:23309.123000 2023.
13

---

Appendix
Table of Contents
A Additional Related Works
15
A. Invariant Learning for OOD Generalization
15
A.2 Graph- OOD Works Using VREx and Similar Variants
15
Comparison with Existing Nove-level OOD Generalization Works
Graph-level OOD Generalization
B Additional Theoretical Results of the Covariate Shift Case
17
B.1
Theoretical Model Setup of the Covariate Shift Case
17
B.2 Theoretical Results of the Covariate Shift Case
17
Detailed Experimental Setup
Basic Settings
Hyperparameter Settings of the Main OOD Generalization Results
18
Details of the Toy Datasel
18
D
Additional Experimental Results
19
D.I
Excessive Alignment Leads to the Collapse of the Invariant Features,
19
D.2
CIA-LRA Alleviates Representation Collapse Caused by Excessive Alignment
19
D.3
Effect of the Number of Hops for Localized Alignment
20
D.4
Discussion Validation
Assumption on the Rate Change Causal and borhood Label Distribution Discrepancy
Spurious Features w.r.t Spatial Position
Discussion and Validation the Assumption on the Feature Distance and Neigh-
21
D.6 Validation of the True Feature Generation Depth
26
D.7 Time Cost of CIA-LRA
29
E
Detailed training procedure
30
F
Additional Discussion of Theoretical Settings and Results
30
F11
Detailed Setup of the Theoretical Model in Section 2
30
F2
Discussion of the Structural Feature Considered in the Theoretical Model and
Justification for the Choice of the Analyzed GNN]
31
F3
Discussion of the Failure Solution for GNNs of VREX and IRMvI
31
F4
The Superiority of the Proposed CSBM-OOD
32
Tightness of the Error Bound of Theorem
32
G
Prools of the Theoretical Results
32
Proofs of the Concept Shift Case Presented in the Main Text
32
2 Proof of the Covariate Shift Case
39
Proof 1eeorem|44
45
Limitations
48
Broader Impacts
48
Compute Resources
49
14

---

A Additional Related Works
A.1 Invariant Learning for OOD Generalization
Invariant learning seeks to find stable features across multiple training environments to achieve OOD
generalization [Arjovsky et al. 2020, Krueger et al.) [022]] Bui al., 2021 Rame et al. 2022 Shi
et al.,
2021
Wang et al. [020 Mahajan et al. 2021 Wang et al. 2022a Yi et al.] 2022 Wang
al. 2022b IRM [Arjovsky et al. 2020] and VREx two of the most well-known methods.
The goal of IRM is to learn a representation that elicits a classifier to achieve optimality in all
training environments. VREx [Krueger al. 2021] reduces the variance of risks across training environments to improve robustness against distribution shifts. Mahajan et al. 2022 1 argues that the invariant features can also change across environments. Hence, they proposed MatchDG to align the representations of the so-called same "object" of different environments. To the best of our knowledge, we are the first work theoretically analysis the limitations of IRM and VREx in OOD node classification problems.
It's worth emphasizing that although the CIA objective is similar MatchDG MMahajan et al. 2021 our extensions of MatchDG on graphs are non-trivial:
1) The extensions from MatchDG to CIA are mainly theoretical.
We extend the idea of MatchDG to the node-level OOD task by providing theoretical char- acterization of CIA's working mechanism on graphs (Theorem 3.1I. revealing its superiority in node-level OOD scenarios for the first time.
We establish the connection between node-level OOD error and two kinds of distributional shifts: (1) environmental node feature shifts and (2) the heterophilic neighborhood label distribution shifts (see Theorem 4.4) giving further explanation of CIA and CIA-LRA's performance gain in node-level OOD generalization.
2) The methodological extensions of CIA-LRA:
It identifies the node pairs with significant differences in spurious features without using environment labels, providing new perspective that the widely adopted environment
partition paradigm Wu et al. [2021), Yu et al. [2023), Li et al.) (2023b a 2022a Liu et al. [2023] may not be necessary for node-level OOD generalization. One can remove spurious features by leveraging neighboring label distributions (analysis in Section 3.2). shedding
light on the role of neighborhood label distribution compensation for the absence of
environment labels.
It's the first node-level OOD method explicitly considering the OOD error caused by shifts in heterophilic neighborhood label distribution, (pointed out by term (c) in Theorem 4.4) Such shifts can be regarded as a kind of structural shift that has been first observed Mao et al. 2023
It's the first node-level OOD method using homophilic neighborhood label distribution reflect the find-grained distribution of the invariant features, avoiding the collapse of invariant features.
A.2 Graph-OOD Works Using VREx and Similar Variants
We summarize the graph-OOD works that include VREx or IGA as part of the training objectives below. Node-level works, which can be covered by our analysis:
EERM (Wu et al. 2021] Equation (5):
K L (gw; (G),
min Var ((L (9w; (G), 0 :.sks
+
Σ
(1I)
K k=
where goo (G) is the generated k-th environment.
INL Li et al. 2023a], Equation (8):
Eg supp(Emme R (f (Gv), y; 0) + A trace (Vargme (VoR"),
(12)
where Einter is the inferred environment label.
15

---

FLOOD
Liu et al. 2023 Equation (12):
min Lirinn -[(,ww) ) + aRy- aRV-REX(W) (6) 0
(13)
Zhang et
2021b Equation (10):
Lelobal
Σ
(Coice
-ppoo )²
(14)
e,e'EE
they claimed: "We note that minimizing the pair-wise distance of losses as defined in Equation 10 equivalent to minimizing the variance of losses." "
GLIDER (Tian et al. 2024 Equation (9):
min Ve [e (Ja (g (G))), vf) + a. [e (Ja (g (G))),
(15)
Graph-level works, which not covered in analysis:
LiSA (Yu al. 2023]. Equation (15): min Cats (f, Lo 1 Vare (Cos (f.g.)) 1~
(16)
where 9f are the augmented training subgraphs of representing different environments.
G-splice [L et al. 2023b). Equation (6):
3 == argminE
P. (ff(G)) Varee(Euea)
[E(G)) Vateeeeue
(fo (G),))]
(17)
where EΛ are the augmented environments.
GIL Li et al. 2022a]. Equation (8):
Begsupp(Es. ser)) R (f(G), Y: + trace (Vargma (V+R)))
(18)
where Einfer is the inferred environment label.
A.3
Comparison with Existing Node-level OOD Generalization Works
Among the graph OOD methods, one line of research focuses the node-level OOD generalization
[Wu et al., [202]] Liu et al. 2023 Zhu et al. 2021 Li et al. 2023a| Xia et al., 2023]. We summarize the drawbacks of previous node-level OOD methods follows. 1) it is hard for environment- inference- methods to generate reliable environments. To generate environments, FLOOD Liu
et al. 2023] uses random data augmentation that lacks sufficient prior. EERM (Wu al. 2021 generates environments by maximizing loss variance, which may not necessarily enlarge differences in spurious features across environments that have been proven to be crucial for invariant learning
(Chen et al., 2023a] Also, the adversarial learning of its environment generation process may lead to unstable performance (Table and high training costs. INL [Li et al. 2023a] relies on an estimated invariant ego-graph of each node, whose quality could significantly affect performance. Moreover, all these methods need to manually specify the number of environments, which could be inaccurate. 2) previous node-level invariant learning objectives also have some limitations. For instance, Zhang al. 2021b Wu et 2021] Liu al. [2023] Li al. [023a]] Tian et al. (2024) use VREx Krueger et al. 2021 as their invariance regularizzu regulaiization.. However, we theoretically prove its potential failure on nove-level OOD tasks in Section 2.2, SRGNN [Zuu al.) [02T] only aligns the marginal distribution p(X) between the biased training distribution and the given unbiased distribution, which has been proved have failure cases [Johansson et al. 2019). 3) some work are based on intuitive guidelines and lacks theoretical guarantees on the OOD generalization performance [Liu et al., 2023 Zhu et al., 2021 Yang et al. 2023). Our proposed CIA-LRA achieves invariant learning without complex environment inference that could be unstable through representation alignment manner. Additionally, we provide theoretical guarantees for our invariant learning objective and empirically validate its working mechanism.
Comparison between our Theorem 2.3 and Theorem Wu al. [202]] It's worth mentioning
that Theorem 1 of Wu et al. [021 proves mine V [e[R(e) will min / [gy e) e|22, where q<2[²) is the
induced distribution by encoder db This seems to conflict with Theorem 2.3 This is because the upper
bound derived in Wu et al. 2021 T(u e|z) < PPa.(q(21)) [B. [[(s < Va [R(e]]] is not tight.
Thus, minimizing the variance loss across training environments does not necessarily minimize
mutual information between the label and the environment given the learned representation.
16

---

A.4
Graph-level OOD Generalization
There has been a substantial amount of work focusing on the OOD generalization problem on graphs.
The vast majority have centered on graph classification tasks tasks[Chen et al. 2022, Wu et al., [002a Li
itt al.
2022a
2023b
Yang et al. [022 Yu et al. [023 Chen et al. 2023a| Buffelli et al., 2022 Jia
ar.
2023 Li et al. 2022b Chen et al. 2023b| 2024 Gui et al. 2024). Most works aim at identifying
the invariant subgraph whole graph through specific regularization so that the model can use
when inference. Compared to node-level OOD generalization, the graph-level one is more akin to
traditional OOD generalization, as the individual samples (graphs) are independently distributed. We focus on the more challenging node-level OOD generalization in this work.
B
Additional Theoretical Results of the Covariate Shift Case
B.1 Theoretical Model Setup of the Covariate Shift Case
In this section, we will extend our theoretical model in the main text to the covariate shift setting. The causal graph of the covariate shift is shown in Figure Tb For the covariate shift setting, spurious features are independent of Y, while X changes with environment Thus we can model the data generation process for environment E as
y = (A
X5
12 + c²,
(19)
where the definition of nı and n2 are the same as Section 2 E" represents environmental spurious features. ef (each dimension of <*) is random variable that are independent for i 1, ..., No. We assume the intra-environment expectation of the environment spurious variable is Ee, [4] = 2º E I since spurious features are consistent in a certain environment. We further assume the cross- environment expectation E. [c] = O and cross-enviromment variance V Velç]] = x²,
I..., No for simplicity. This is consistent with the covariate shift case that p(X) can arbitrarily change across different domains, and the support set of X may vary. Also, we require L Z k to ensure the GNN has enough capacity to learn the causal representations.
B.2 Theoretical Results of the Covariate Shift Case
Now we will present similar conclusions as the concept shift case. Even if VREx and IRMv1 can successfully capture invariant features in the non-graph task, they induce a model that uses spurious features. Still, CIA can learn invariant representations under covariate shift.
Proposition B.1. (VREx and IRMvl learn invariant features for non-graph tasks under covariate shift, proof is in Appendix G.2.1) For the non- non-graph version of the SCM in Equation 19.
y ===xx -x + n1, X;- = 122 c
(20)
Optimizing VREx mine LYRES = [e(R(e) and IRMvl mine LIRMI = E.lll V (.o will learn invariant features when using a I I-layer linear network: s(X) = 0, X1 + 02X2-
Proposition B.2. (VREx will use spurious features on graphs under covariate shift) Under the SCM of Equation (19) the objective mine V [R()) has non-unique solutions for parameters of the
GNN when part of the model parameters {0 02(0)) ,02(0 02((1)
} take the values
0700) = 1, (2(() = 1, 1= L - -I,... ... L - s +1 01 = 0, (2(1)) 1, 1= T. 8, I 8
O,
(21)
0 (1) 0, 02 1, 1= L 1,.,,
< < is some positive integer. Specifically, the VREx solutions of 01 and 02 are the sets of solutions of the cubic equation, some of which are spurious solutions that 0z # 0 (although 02 = 0 is indeed one of the solutions, VREx is not guaranteed to reach this solution):
(202 f2 + (0,)2 20) + cz02 - =o( + Ee[N =0 {
(22)
[ca02 - N |00020000000000000 + E. [N [N9c20002] c4 - (02)
where e1 = B[(AFe X1) T X1)]. 02 = "[((fe"x))TT
X1)], c3 = T. (Ae
C1 = Ee ((AA))*x))T IN=
a², os Eg No (Ir((de)) Tee
det) N= v((1oo))]]
17

---

Proposition B.3. (IRMv1 will use spurious features on graphs under covariate shift) Under the SCM of Equation (79. there exists s No that satisfies < < and s + such that optimizing
the IRMvl objective mine [e u w|w=1.0 R(e)ll will not lead to the invariant solution O2 = 0 foror
parameters of the GNN 3 when {0} (1) 0090) 00
(1) 00200) take the special solution:
01t0 1, 0Q 02(() 1,, 1= -. 1-1, ,.., 8 8+1 +1 0 (1) 0, 02 (1) 1,
6 =
I = L L,sL- - 1, 1,....
(23)
82 (1) = 0. 62 (() =1, I= L 1.,..,
Proposition B.4. Optimizing the CIA objective will lead the optimal solution O¹
0
82
01 (t) 1, 03 1, [ 1= L - 1, L k
(24)
0100) = 0, 82(1) =1, 1= k, L k 1,..!
C Detailed Experimental Setup
C.1 Basic Settings
All experimental results were averaged over three runs with different random seeds. Following Gui ct al. [002]], we use an OOD validation set for model selection.
GAT experiments. For experiments on GAT, we adopt the learning rate of 0.01 for Arxiv, 0.001 for Cora, 0.003 for CBAS, and 0.1 for WebKB. The reason why we didn't 't use the default learning rate in Gui et al. [2022] is that since the original GOOD benchmark didn't 't implement GAT, so we chose to tune a learning rate for adapting GAT to reach decent performance. The settings of batch size,
training epochs, weight decay, and dropout follow Gui et al. 22222)
GCN experiments. For experiments GCN, follow the default settings of batch size, training epochs, learning rate, weight decay, and dropout provided JyGui et al. 2022).
It's worth mentioning that we choose different normalization strategies for the invariant edge mask of CIA-LRA to achieve better performance for GCN. Equation 8 we use Sigmoid as normalization. However, we find it is better to use Min-Max normalization for GCN on some of the datasets. Specifically, for experiments on GCN, we use Sigmoid normalization for CBAS, Arxiv (time concept); Sigmoid for training and Min-Max for testing for WebKB (covariate); Min-Max normalization for the other dataset splits. For GAT, we use Sigmoid during training and testing for all datasets.
C.2 Hyperparameter Settings of the Main OOD Generalization Results
Most hyperparameter settings are adopted from Gui et al. [2022). except that for EERM we reduce the number of generated environments from 10 to 7 and reduce the number of adversarial steps from 5 to I for memory and time complexity concerns. For each method, we conduct a grid search for about 3~7 values of each hyperparameter. The hyperparameter search space is presented in Table 5
C.3 Details of the Toy Dataset
The synthetic dataset consists of four classes. Each node has a 4-dim node feature. The first/last two dimensions correspond to the invariant/spurious feature for each of the four classes, shown in Table 6a and 6b We artificially create both concept shift and covariate shift this dataset.
Now we introduce the setting of the toy synthetic task of Figure 3
To explicitly disentangle the learned invariant and the spurious components for quantitative analysis. we employ a 1 l-layer GCN. We take the output of the first/last two dimensions of the weight matrix as the invariant/spurious representation.
18

---

Table 5: Hyperparameter setting of the experiments.
Alporihhm
Search Space
IKM
A- B.1, 10, 100
1000
GroupDRO
X-b:001, 0.01.
Deep Coral
A-0.01, 0.1,
IGA
1-0.1 I, I. 10, 100
Mixup
a-04, L., 2.0
3,3
number of generated enviromments k=?
EERM
advensarial training steps [w]
numbers sodes for each node should be modifted the link with s=5
subgraph generator loamnng
0.001,
SRGNN
0.000001 0,00001, 0.0001
GTrans
Scature learning case 7,00000005 0,00001, 0.0001
structuree leaming rg=0.01, 0.1
optimization stops
CIA
A=0.0001,
0.001, 0.005, 0.01, 0.05, (GCN)
0=0,0001, O. 0.0005, 0,001, 0.01, 0.05 (GAT)
A- 0:001, 0,005, 0.01, 0,05, 0.T (GCNN)
CIA-LRA
mask loamiig (GATT)
(GCN Anxiv, Com, CBAS):
0.805,
adge musk GNN leorning rate 1000000 (GAT)
6,
Table 6: Information of the toy dataset of Figure
(a) The invariant part (the first two dimensions) the (b) The spurious part (the last two dimensions) of the node features in the synthetic dataset.
nodes features in the synthetic dataset.
class
class
carpa
dan
11.2) Wi 1 N(1 11,1) WI 1)
Mita
Mi
saanng
NU, (.8.)
818. 56.
800.8.0
M144..
MtB -600
M06.0.11 D
D Additional Experimental Results
D.1 Excessive Alignment Leads to the Collapse of the Invariant Features.
One may wonder why CIA underperforms CIA-LRA even if CIA uses the ground truth environment labels. this section, we will show that CIA may suffer excessive alignment, which will lead to the collapse of the learned invariant features and consequently hurt generalization. We use the intra- class variance of the representation corresponding to invariant features (averaged over all classes) to measure the degree of collapse of invariant features. Base this measurement, the excessive alignment can be caused by:
1) Using that is too large. Evidence: on the toy dataset of Figure 3 a larger À leads to smaller intra-class variance of invariant representations. We also compute the intra-class variance of invariant representations at epoch 50 on the toy dataset,
2) Aligning the representations of many nodes. Evidence: we show that aligning fewer node pairs can alleviate the collapse of invariant representation. By modifying CIA to align local pairs (same-class, cifferenttenvviommment nodes within 1 hop), termed "CIA-local", the results in Table 7b show that when by aligning local pairs instead of all pairs, CIA-local avoids the collapse that CIA suffers and achieves better performance.
D.2 CIA-LRA Alleviates Representation Collapse Caused by Excessive Alignment
In Figure we illustrate the impact of À on OOD accuracy. Both CIA and CIA-LRA experience a performance decline at 0.5, indicating that excessive alignment can hinder generalization. Furthermore, CIA shows earlier and more pronounced performance drop than CIA-LRA. This suggests that the CIA-LRA method mitigates representation collapse by aligning fewer pairs and selectively focusing pairs with smaller differences in invariant features.
19

---

Table 7: Experimental evidence of the factors that can cause the collapse of the learned invariant representations.
(a) Using that is too large can cause the collapse.(b) Aligning the representations of too many nodes The intra-class variance of invariant representations on can cause the collapse. Accuracy and the variance of the invariant representations on the toy dataset of Figure 3 at epoch 200.
the toy dataset of Figure 3 at epoch 50.
8005
A 0.1
A 0.5
variance of the invariant represcntation
0.061
0.039
0.011
CIA
CLA-local
Concept shift, accurey
0.253
0.354
Concept shif, variance of the invoiaai representaiion
0,0003
0.2327
Concept shift, accuracy
0.250
0.312
Concept shift, variacce invariant representation
0.0002
0.1699
(a) Cora degree concept (b) Cora degree covariate (c) CBAS color concept (d) CBAS color covariate
Figure 5: The effect of X OOD accuracy. CIA exhibits an earlier and more severe performance drop than CIA-LRA, demonstrating that CIA-LRA can alleviate the feature collapse caused by excessive alignment.
The role of CIA-LRA in alleviating the collapse of the invariant features can also be reflected in Figure [6 in which the representation learned by CIA collapsed to a compact region. However, CIA-LRA does not exhibit such collapse, maintaining the diversity of the causal representation.
(a) ERM
(b) CIA
(c) CIA-LRA
(d) CIA-LRA w/o s0
Figure 6: Visualization of the learned representations at epoch 100 on the toy dataset (concept shift).
Classes are distinguished by color. À = 0.5 for CIA and CIA-LRA.
D.3 Effect of the Number of Hops for Localized Alignment
In Figure 7 we plot the OOD accuracy curve of CIA-LRA against the number of hops t for localized alignment (with 0.05). CIA-LRA achieves optimal performance within local range of 6 to 10 hops. Performance is notably lower at smaller hops (t 2), due to limited regularization from aligning only a few pairs of representations. As increases, performance gains diminish and can even degrade, particularly aligmment optimal OOD performance is attained by aligning nodes within about 10 hops. Extending the alignment range further does not enhance performance significantly and may lead performance drops and higher computational costs. These findings support the hypothesis in Appendix [D.4] that invariant features distant the graph differ substantially, and their alignment could induce invariant feature collapse, leading to a suboptimal generalization performance.
the CBAS color covariate. This underscores the importance of localized
D.4 Discussion and Validation of the Assumption on the Rate of Change of Causal and Spurious Features w.r.f Spatial Position
To verify the intuition presented Section 3.2 that spurious features exhibit larger changes within local range (about 5 to 10 hops) graph compared to invariant features, we conduct experiments
20

---

Dot
505
175
41.
013
(a) Cora degree concept (b) Cora degree covariate (c) CBAS color concept (d) CBAS color covariate
The effect of the number of hops t for localized alignment on OOD accuracy. Too small t will lead to suboptimal performance. Too large t brings limited performance gain or even deteriorates the performance.
Figure 7:
on real-world datasets Arxiv and Cora. To extract invariant features, we use a pre-trained VREx model and take the output of the last layer invariant feature: To obtain spurious features, we train an ERM model to predict the environment label and take the output of the last layer spurious features. For each class, we randomly sample 10 nodes and generate corresponding 10 paths using Breadth-Firee Firstt Search (BFS). We extract invariant and spurious features of the nodes on each path and plot the 1-2 distances between the node representations on the paths and the starting node. The results of Cora are in Figure and 9
and the results of Arxiv are in Figure and [1] We chose some of the classes to avoid excessive paper length; the results for the other classes are similar.
We observe that: despite the curve's slight fluctuations, the invariant feature difference shows clear positive correlation with the distance from the starting point. Specifically, within about 5~10 hops, the changes of spurious features grow more rapidly than those in invariant ones. This insight led us align the representations of adjacent nodes to better eliminate spurious features and avoid the collapse of the invariant features. This also explains why we add weighting term d(i. in our loss function to assign smaller weight node pairs farther apart. Additional experimental evidence supporting the importance of localized alignment is in Appendix D.3, which shows that alignment over a large range may lead to suboptimal performance and increasing computational costs.
This assumption aligns with those adopted in a series of previous works on causality and invariant learning [Chen et al. 2022 Burshtein al. 1992 Schölkopf 2022 Schölkopf al. 2021]. These works assume that invariant features are better clustered than spurious features. In the node-level graph OOD scenario, we observe this phenomenon primarily within local parts of graph. In some cases, when two nodes are too far apart, their invariant features can vary more than the spurious features, as seen in Figure (a) path 1.2,4.6,9 and 10. Therefore, matching the representations in a local region helps alleviate the invariant feature collapse problem.
D.5 Discussion and Validation of the Assumption on the Feature Distance and Neighborhood Label Distribution Discrepancy
D.5.1
Heterophilic Neighborhood Labels Distribution Reflect Spurious Feature Distribution
In this section, we will empirically validate the key intuition of CIA-LRA: the neighbors from different classes (which call Heterophilic Neighborhood Label Distribution, HeteNLD) reflects the spurious representation of the centered node. In node-level OOD scenarios, the distributional shifts of spurious features originate from two main sources: (1) the shifts in spurious node features associated with environmente and (2) the shifts in Neighborhood Label Distribution (NLD), which affects the aggregated representation of the centered node. The first type of spurious feature is analogous to those defined in Computer Vision (CV) OOD domains, while the second type specific to graph structures. The NLD shift more general instance of the graph heterophily problem [a et al., 2022) Huang et al. 2023 Mao et al. 2023). where changes in the ratio of homophilic neighbors from training to test graphs can degrade performance. This occurs because the changes in the homophilic ratio lead to the distributional shift in the aggregated representation of the
the label distribution of
same-class nodes. Most previous methods [M et al. 2022 Huang al. 2023 Mao et al. 2023)
'though we reveal in our theory that VREx may rely on spurious features, we still use VREx here to approximately extract invariant features as many previous graph OOD works have done since VREx already demonstrated some advantages in their works
21

---

Path
Path
Path
Path
Path
20.0
Ioveriant
Invariant
Inserfent
Dizaanee Start
piopncs from Scart
MW
Diotanoe from Stae
15.0
Distance Iram Start
20-
12.5
D.C2
8a.0
10.0
0.00
7.3
-0.c2
2.5
Invorbast Footure
Spase LADO Pouliur
Path Langth
Path Langoh
PAth J4noah
Path Langes
Lamgth
Path
Path
Path
Path 10
20.0
20.0
20-
12.00 Rem Sart
Oettanne toom Stort
D7.eetance Qatt
12.5
18
22.5
22.0
75
7.5
2.5
2.5-
hos.rar PoSt.re
2.5
Invariant FOSEL Spurtrux Teature
0.0
Spurizuu TTa
Hatle
(a) class 16 of Cora
Path
Parh
Path
Fath
Pathh
UFftiinc from scart
Uatsiin frtm SCat
Disuncc from star
Distann from Start
20-
Fovar
meature
Path
Path
Path
Path
Path
Path
Path
Fath
Fath
(Scance hare Sant
Uipanno Nur stant
Lauisan foo zDit
Lisuun from ztint
Dastnnc turn start
20
20
15
(b) class 17 of Cora
Figure 8: Visualization of the rate of change of invariant features and spurious features on Cora (part
1).
22

---

Fath
Parhh
Fatt
Path
Parh 5
O30 fro Shatt
Dodveee Keart
20
Didperr from
20
op rooture
L2 Distanca
33-
20
Falh Langth
Path Lamgohh
Pach Lenight
Path Langoh
Path
Path
Fath
Path
Path 10
70
20-
12000 kon Stnt
DeDeiaace too Matt
25.0
12 Set
A2.9
20.0
7:5
2.5
Invariant Peatare Spurtoss Teature
Bivar ant Noaturr
Spuiious Tratiane
(a) class 39 of Cora
Path
Parh
Fath
Path
Path
12:00002 8-m Statt
Urfiiinct fram start
Dr from Shar
21
20-
15
20
20
to
Path Length
Path
Path
Path
Path
Path
Fath
Fath
Path
Uistinn forn stant
Desarroe Start
Dasanne form Stant
25-
Damarce Shnn
20-
20-
10
15
(b) class 41 of Cora
Figure 9: Visualization of the rate of change of invariant features and spurious features on Cora (part
2).
23

---

Farh
Path
Fath
Path 4
Path
Invariant
11.5
Innirient
Dattette from Shatt
22.0
12:03aee fro
25-
1.5
Dislance
thadeeee
rosture
Langth
Puth Langgh
Path Length
3ath Langth
Langth
Fath
Path
Path
Path
17.5
70
12:00 bon Stnt
statt
Lisssinn Bum stat
32%
Oillance
7.5
25-
Peclitenghh
Puth
(a) class 25 of Arxiv
Path
Path 2
Fath 3
Pathh 4
Path
37.5
M
37.5
12 E.n St4t
15.5
Dartente Shart
Lrutsaans from Scat
0.00
22.3
0.00
Spurious Heature
Fration::
20
7.5
-0.00
5.0
-0.04
2.5-
Invoriant Feature Suar Kols Pooline
Path Langth
Path
Pal:
Path
Sath
Path
Poth
Fath
Fath
Path
Sparictic
25.0
12 Dottnce more Start
Lostaann Nore stort
22.3
W
20.0
0.00
10
Spunibus Peatter
2.5
-0.04
(b) class 29 of Arxiv
Figure 10: Visualization of the rate of change invariant features and spurious features on Arxiv (part 1).
24

---

Path
Path 2
Fath
Path 4
Patn
Inverient
17.5
54.
15.0
12.03aae fon Statt
Disaanc tran Start
Disancc from start
20
9
8
3.0
14
2.5
InvoRont Footure
Invarint Focture
3ya Sous Posture
Supeioore Postuure
Camgah
Path Langth
Pach Langth
Puth Langtti
Pathi Langth
Path
Path
Path
Path
Path
12000 bom Stat
Oisaanos tom start
L2sisinc bun stott
3.00
2-
20-
Invorlant heaoure Sour oua Tealure
0.04
(a) class 13 of Arxiv
Fath
Fath
Fatt:
Fattt
Path
315
2.75
3.50
4.5
Siart
20.
25
D42
2.0
1.00
20
spurious
0,2
0.00
3-
-0.1
Path
Length
Path Length
Pach Langth
Path
Path
Fath
Fath
Fath
Fath
15.0
3.2
3,2
DScanee hure Stat
12.5
Oisance 25
Diraane
30.0
Healure Spurious Peature
Invamint
Spurious
Invarark t.a...7 Spuriuu Peatture
Iruar wrtk Spuniou
3.0
Langth
(b) class 17 of Arxiv
Figure 11: Visualization of the rate of change invariant features and spurious features on Arxiv (part22 2).
25

---

only focus on the chasiyccassifiiattio setting, where changes in the homophilic neighbor ratio are equivalent changes in the heterophilic neighbor ratio. However, we consider the more general multi- classification tasks. Therefore, we propose to use HeteNI.D as measurement, considering every class different from the central class and using their distribution to reflect shifts in the aggregated representation. Although the ratio of homophilic neighbors also affects environmental spurious features and NLD, it affects the invariant representation as well. Assigning larger weights to the pair with significant differences in the ratio of homophilic neighbors will simultaneously eliminate environmental spurious features and learn a collapsed invariant representation. As evidenced in Table ② will lead to significant performance
4 moving the yo (c)a.) to the numerator of Equation decrease. Hence use (c))))) instead of yame (c).. in Wij-
In the following part, we will empirically validate our intuition that HeteNLD can reflect the two spurious representation distributions on concept shift, where X) varies across environments, and covariate shift, where p(X) changes with environments, respectively. We will show that HeteNLD affects the spurious features of the centered node in different manners under concept shift and covariate shift.
Covariate shift. For covariate shifts on graphs, since spurious features are not necessarily correlated with labels, the environmental spurious features cannot be reflected by HeteNLD. However, we can still measure how HeteNLD affects the aggregated neighborhood representation. To obtain neighborhood representation, we train 1-layer GCN that aggregates neighboring features and discards the features of the centered node. We hope to observe whether the gap of HeteNLD accurately reflects the distance of neighborhood representation. To ensure that the discrepancy in the aggregated neighboring feature is caused solely by heterophilic neighbors, we only use point pairs with the same number of homophilic neighbors. Specifically, the neighborhood representations of two nodes with the same number of class-same neighbors, and plot its trend w.r.t. the distance of HeteNLD (according to the definition of r in Equation (9). except that we didn't 't normalize by the node degree here). We run experiments on Cora to veriry both word shifts (node feature shifts) and degree (graph structure shifts) for
compute the L-2 distance between
this. We evaluate comprehensive understanding. We show the results of the first 30 classes of Cora. The results in Figure 12 and 13 clear positive correlation between the neighborhood representation distance and HeteNLD diserepancy under covariate shifts, indicating HeteNLD discrepancy can reflect the distance of the aggregated representation.
Concept shift. As for concept shift, spurious features are correlated with labels, thus the label of a node contains information about spurious features correlated with this class. Hence, by observing HeteNLD, we can measure the distribution of the spurious feature. For concept shift, we train a GNN to predict environment labels to obtain spurious representations. Table 14 and 15 also show a clear positive correlation between spurious feature distance and HeteNLD discrepancy on concept shift, indicating that HeteNLD discrepancy can reflect the distance of the environmental spurious features.
D.5.2 Homophilic Neighboring Labels Reflect Invariant Feature Distribution
Now will validate that the ratio of the same-class neighbors reflects the aggregated invariant represen- tation. We use VREx to approximately extract invariant features and compute their distance w.r.t. the discrepancy of the ratio of the same-class neighbors. We evaluate on 4 splits of Cora: word+covariate, wordtconcept, degrectcovariate and degreetconcept. For each data split, we randomly choose 5 classes with sufficiently large differences in homophilic neighbor ratios for visualization. The results in Figure 16 also show a positive correlation trend between the distance of the invariant representations and the difference in the ratio of same-class neighbors, indicating the latter can reflect the former.
D.6 Validation of the True Feature Generation Depth
For the theoretical model in Section 2 we assume that the number of layers of the GNN L is greater than the depth of the causal pattern k. In this section, we empirically verify how large really is on real-world datasets. Specifically, we use GCN with different layers predict the ground-truth label Y on Cora and Arxiv datasets respectively (results are in Table Da and 9b). As mentioned above, since GCN with L layers will aggregate features from L-hop neighbors for prediction, if the depth
26

---

The relationship between the distance of the aggregated neighborhood representation and distance of HeteNLD on Cora word domain, covariate shift. Each sub-figur class, and each dot in the figure represents a node pair in the graph. The red line is obtained by linear regression. The positive correlation is clear.
Figure 12:
Figure 13: The relationship between the distance of the aggregated neighborhood representation and distance of HeteNLD on Cora degree domain, covariate shift. The positive correlation is clear.
27

---

Figure 14: The relationship between the distance of environmental spurious features and distance of HeteNLD on Cora word, concept shift. The positive correlation holds for most classes.
Figure 15: The relationship between the distance of environmental spurious features and distance of HeteNLD on Cora degree, concept shift. The positive correlation holds for most classes.
28

---

Figure 16: The relationship between the distance of invariant representations and discrepancy in the same-class neighbor ratio (the ratios in the figure are multiplied by node degree) Cora degree, concept shift. Line 1 to 4 results of Cora word+covariate, word+concept, degreetcovariate and degree+concept. respectively. Each subgraph marks class, and each point in the subfigure represents a node pair. There positive correlation between the invariant feature distance and the difference in neighboring label ratio of the same class as the centered node.
Table Time cost (seconds) to achieve optimal test performance on Arxiv using GAT on a single RTX 3090 GPU.
ERM
Coral
Mixup
EERM
SRGNN
GTrans
CIT
CIA-LRA (6 hops)
Arxiv degree covariate
74
551
758
OOM
34887
OOM
OOM
1248
Arxiv degree concept
30
OOM
3960
OOM
OOM
1132
Arxiv time covariate
46
246
1207
OOM
1993
OOM
OOM
292
Arxiv time concept
440
OOM
11628
OOM
OOM
of the GCN equal to the true generation depth, then the performance should be close to optimal. Therefore, use the layer number that yields the optimal empirical performance (denoted L*) to approximate k. We find that the L < 4 in most cases. This indicates that our assumptions L S hold easily.
D.7 Time Cost of CIA-LRA
To show the running time of CIA-LRA, we show the time cost to reach the best test accuracy on our largest dataset Arxiv (with 50k 60k nodes). The results are in Table below. The time cost of CIA-LRA is comparable to baseline methods.
(a) OOD accuracy on causal prediction (%) of GCN with (b) OOD accuracy (%) GCN with different numbers different numbers of layers on Arxiv.
layers on Cora.
(degree)
57.2800.09)
58.92/0.14)
60.1800411
(degres)
55.7600
concept
22.9000211
65.410013)
concept
62.80034)
61,500
60.240040)
71.1700211
71.710211
64,500.18
45.110.121
64.58/0.10)
concopt
12)
67.3600.07)
65.2010.26)
67.490005)
cunoagt
64.8500.10)
64.1610.33)

---

O. E Detailed training procedure
Table shows the detailed training procedure (pseudo code) of CIA-LRA. We use the same GNN encoder for the invariant subgraph extractor. Empirically, we add CIA CIA-LRA after epoch of ERM training.
Algorithm I Detailed Training Procedure of CIA-LRA
Require:
A labeled training graph G = XY) a GNN fe. and invariant subgraph generator GNN fe... The number of hops t, CIA-LRA weight X, the number of classes C, total iterations T, model learning rate 71, invariant subgraph generator learning rate 72, the number of fe layers
Ensure:
Updated model fe with parameter +
1: for iterations in [1, 2, ...,, T] do
2: Randomly sample a subgraph A' R from A NoxNo
3: Compute and apply the edge mask according Equation (8) obtain the masked adjacency matrix Am + A' 3 M E RNNN
4: Initialize LCIA-IRA-
5:
Calculate the node representations 6(Am X) E RXD.
6: ### Calculate A'. where the (i,j))-th element of A' equals the length of the shortest path from node i to j if the length is less than else infinity:
7:
Initialize A (i j) < Inf i # j. A (i, 1, Atem + Am
8:
for hop h in 1..,... do
9:
Atem f- Am Atem
10:
if Atem (i. > 0 and Atem (1.)) < (i, then
11:
Ai,j &-
12:
end if
13:
end for
14:
Compute the ratio of neighbored nodes of each class: Compute the normalized adjacency matrix A, where A's i-th row A, + Ami/ Dr, Ami the i-th row of Am and D, R is the degree of node i. Initialize the neighbored label ratio < Y E NxC where R(i, c) is the ratio of node i's neighbors of class within L-hop range, Y the hop labels. for in [1, 2.... L] do
###
15:
16:
17:
18:
R AR
19:
end for
20:
for in [1, 21, .... C] do
21:
Sample the nodes of class e from A and form AC. Use A to screen for pairs of nodes not exceeding a distance of hops (t)(). Compute CIA-LRA loss of class c: LEAALRA according to Equation 9 using Pe((), R, A
22:
and o( :(Am:X);
23:
LCIA-LRA + LCIA-LRA + LETALRA
end for
25:
Compute final loss + (feAA ALCIALRA. Loe is the cross-entropy loss Update model parameters - θ rV pn Om rVam
27:
end for
F Additional Discussion of Theoretical Settings and Results
F1 Detailed Setup of the Theoretical Model in Section 2
The proposed data generation process. the theoretical model of Equation ( each dimension of
ni E N x1 and nı E N x1 are i.i.d, following standard Gaussian distribution. E R x1 is an environment spurious variable. ef (each dimension of e are independent random variables, i = 1,.., No. We further assume the cross-environment expectation E,[[s] = O and cross-enviromment variance E. [ef] = o², i 1,.., Ne for brevity.
30

---

The considered multi-layer GNN. In the analyzed GNN of Equation we simplify the classifier an identity mapping. Such simplification has been adopted by various previous theoretical works on graphs [Wu et al. 2022b Tang and Liu 2023 We assume I. 2 k to ensure the model has enough capacity to learn invariant features. We verify this assumption by using GCNs with different numbers of layers to predict the ground-truth labels (see Appendix (.6)
F.2 Discussion of the Structural Feature Considered in the Theoretical Model and Justification for the Choice of the Analyzed GNN
Structural Features and Structural Shifts Considered in Section 2.1 To reflect reality as much as possible, is necessary to consider both nodal and structural invariant and spurious features in the theoretical model. As mentioned in Section 2.1] we model the invariant structural feature as the structure of the k-hop subgraph.. natural question is raised here:
Can we find other ways to define the invariant/spurious structural features?
The answer is yes. For example. the invariant structure can be modeled as the subgraph of the ego-graph of node, following Li et al. [023aa]. However, it is fundamentally impossible for GNNs using mean aggregation (like GCN) to learn such causal structures. This is because such GNNs will assign fixed weights to each neighboring node feature, and they can't can't split the causal substructure from the neighbored ego-sgraph. Therefore, we make the causal structure feasible for GCN-like GNNs learn by defining the causal structure as the whole k-hop neighboring ego-graph, rather than a subgraph, and show that OOD failure can still happen (Theorem (.3). Then, under this setting, the remaining challenge becomes identifying the true by optimizing the shallow layer GNN parameters. However, in real practice, the invariant causal pattern may still be an ego-subgraph. This can be reflected the performance gain of the invariant subgraph extractor used in CIA-LRA.
Why Do We Choose Such a GNN in Section 2.12 From the above analysis, we show that such a choice is compromise solution between the case of GCN (that can only extract whole ego-graph) and GAT-like GNNs (that can extract a subgraph from an ego-graph). Although in this GNN each neighbored node is solely assigned the same weight, the shallow layer parameters be optimized to realize the aggregation of different depths to capture the causal structures of different depths.
F.3 Discussion the Failure Solution for GNNs of VREx and IRMv1
In Theorem G.2 and G.3 (the formal version Theorem 2.3 show that VREx and IRMv1 could induce a model that uses spurious features. Now we'll give an intuitive explanation of this failure
mode. When the lower-layer parameters of the GNN 01 o1 (1)
(1)
02(0) 0z(") take the specific solution
O in Equation
21). we have
H (H(()) L))
HHL (L) 001 (n)
A= X1, H (L)
kmm
X1,
(25)
003 (1)
holds for i = 1,2, 1 = 1, L - and every environment Thus, get
OC Oc
a(H(")0)
OC H (T)
001
0(H 0,) 00,
0(H
(1) 01)
Oc a(H((W) ac
(26)
((H(1) (1) 01) 005(0) 00 (1) 0,¹
= 1,2, 1= 1, L
Oc ac = 0. The same is true for 20, and OC This means the solution of the top-level parameters 0N and 0g of the GNN will only BOECh
(+) is because Equation 25 Therefore,
0C 0
00,
00: 10
be constrained by two equations, dc and àc = 0, rather than be constrained by all gradient 80,
20g
functions ac ao! 0, i 1,2. By analyzing the specific loss of VREx and IRMv1, conclude that they will induce non-zero 02.
31

---

Note that the failure solution O here is not the unique one, we choose Og just for the elegant expression and to better convey the intuition. In effect, the conclusion 20,
ac 0 =
ae: 13 = 0 and
dc
Sc
8c holds long as the lower-layer aggregation parameters satisfy a03
30,
0 1, 0P 8Q(1) = 1, I 1,... L - 81 +
01 (1) 0, 0 (t)
L,
I= L 81, L 51 1,...?
6%
for some $1, 82 E 1
8 = 1, 2 (1) = 1,
== L 1,.., L - 82 +1
0 (1)
0, 03 1, I 82, L 82 1y...
(27)
ie., we don't require the spurious branch of the GNN to be identity mapping as equation 36 does.
This failure mode can happen to GCN (all 0j 1, = 2, = 1, 2) and also for GAT.
E4
The Superiority of the Proposed CSBM-OOD
Our CSBM-OOD in Section introduces several advancements over the conventional CSBMs (Ma 2021 Mao et al., 2023]: 1) It supports multi-class classification, extending beyond the binary classification framework of traditional CSBMs: 2) It accommodates unique neighboring label distributions for each node, in contrast to the traditional models that assume a uniform class- shared ones don't.
et al.
ratio across all nodes; 3) our model integrates OOD shifts, while traditional
F.5 Tightness of the Error Bound of Theorem 4.4
When there are distributional shifts in spurious node features and heterophilic neighborhood distribution between training and test environments, the terms (a)-(d) in Eq. (109) becomes zero, and
the upper bound becomes 2 (h) + const = 2 (h) +
LC(28 1/L
i... our bound 71/1.
only larger than the ideal error 2. (h) by a constant const. When the number of training samples Ner is large, const will be small enough and can be negligible. Hence, the tightness of our bound is guaranteed.
G Proofs of the Theoretical Results
G.1 Proofs of the Concept Shift Case Presented in the Main Text
In this section, we give proof of the propositions of the concept shift model presented in the main text.
G.1.1 Proof of the non-Graph Success Case of VREx and IRMvl under Concept Shift
We restate Proposition 2.2 as Proposition G. below.
Proposition G.1. For the non non-graph version of the SCM in Equation 2
= X1 + m,, X Y n2 c:
(28)
VREx and IRMvl will learn invariant features when using 1-layer linear network: f(X) 0,X1 + 02
Proof. VREx. Denote X101 X502 X1 72 as le. The variance of loss across environments is: V. [R()( E. [R² (e)]
E² [R()]
| + (X1 n1 + e0 X1 mm112)) 27
Eng
Emni.n
(29)
E2
Enging
|| + (Xi + n2 + e0 (X1 ni 1111
E. [Bnym
(o.(4))11 E Eni m2 [[]6]]]
32

---

Take the derivative of V. [R(e)) with respect to 81:
8V 8%. [R()]]
Ee 22 [o [e] Bn,,ns [21]] X1]]
001
(30)
2 [Bm1,0 [e EE [B [21
x1]
Using the fact that Eng mg [1]] Exg ma [22] O, E na [m] n²)
= Eni ma [n2 n1 0 and
Enging [n]] ni] - Eng,ng my [ng n2] Ne if is the noise from Eng T é*] Bni,ng [ng e5] 0 and using the assumption that Ee [[]][[]]]]]]]_ = o², we have
E. [2 [. Emy,n2 [21 x1]]
x, 301 02 + 0,0, (3022(3x7(X3 + o [X
+ X,0 +C
(31)
03 -o (3x + [ + 38 (XF x x2(x E.(N))
-30 - 0,02(6X]; + (
and
Eg Em [b]] E. [Em, m2 [21 x1]
x 30, 20 + 010,² 2 ax](X] + +²) (X
(X) x (N
(32)
-00 - 0,,0 + 2X [NC] (3X3 + +
+3x(3x + E. [N + 30 (x+ X(Rx - +
Plug Equation (31 and
32 back into Equation (30p. we have
0%. [R(e)
02 TT
(33)
00,
8V. [R(e] 00,
Let
0, we have 0g =
[Re] Let's calculate 802
[R(e) when 892
Now we need validate 02 is also a solution 0g 0:
0V [R()
Ee
[2Eng,n m2
[1. [e] Emg.ma [21_ (X1 + n1 + 122 + Ee]]]
002
[E .2 XO3
2E,
[ Ee Eng [21_ (X1 + ni + n2 + c']]
(34)
20, + X? + (0, -X3 - -x
x07 20, 20, X? + X? + (O - X² -7-EA -E,N%
=0.
So far, we have proved 0g is the solution for VREx, hence will learn invariant features. We finish the proof for VREx.
IRMv1. The objective of IRMvl is E. v( When IRMv1 loss optimized to zero, we have V R(e) = 0 for all environments e.
[2(0,X, V V. R(e)) = | + 02X, - (Xi + n1)) ni)) (0, + +2X22)
2((01)xxx X1 (02) + + e + 2N + 20,02X (x)+
(35)
-0,X X1 (x X, X e NN))
To realize V., R(e) 0 for all we must let 02 = 0 (and consequently 0, 1), otherwise the solution of 0g will include terms related to e and Ne that vary with environments, and single value 82 cannot fit all these values. Thus finish the proof for IRMv1.
D
33

---

G.1.2 Proof of the Failure Case on Graphs of VREx under Concept Shift
We present the formal version of the VREx part in Theorem 2.3 as Theorem G.2 below.
Theorem G.2. (VREx will use spurious features on graphs under concept shift, formal) Under the SCM of Equation 2 the objective mine Ve [R())] has non-unique solutions for parameters of the
GNN when part of the model parameters (0) (1) -02(0) 002 ,02!!) take the values
0f (1) 1, 1,0g() 1,
1 1= L- - 1, ..... L 8+11 ++
8 (1) = 0, (7(1) 1, 1= L 8, L
1,.., 1
(36)
0100 0, 02 =1, 1= 1,,...
for some < 8 < L. Specifically, the VREx solutions of 01 and 02 are the sets of solutions of the cubic equation, some of which are spurious solutions that 82 (although 82 is indeed one of the solutions, VREx is not guaranteed to reach this solution):
(3c10102 + e1 (02)² 20g02)o² - (2c (01 02) -c)) c-02 =0 {
(37)
(2c (01 + 02) co)lo20, - c-)(c3- c1)02 - (02 + 02) - csl( =0
where 0 = [e X1) T X1)). 02 = - (1+ X1) Ae X1), c3 = Be[(Ae" x1) TI).
C1 = Ee(((A= 11, Gs = E.[N x1) TA=² A="x, X1 + ar((A=)) "Aee" + No + og))]
C6 = [e((A""X1) (AA" X1)), C7 E.fe T T( X1)).
Proof. We will use some symbols to simplify the expression of the toy GNN. Denote Âmm + + yy. Use the following notations to represent the components of the L-layer GNN model:
(A x) 01 +11
01 (1) A (...07(0) (3) (01 (2) (0)00) A(0 Á (2 1)x, 09 (0) A+ 09 1)(1)) + +...]
(1)
C
1 11(11-1) A (..00b()) (B1 (2) ()
A(Oh
Ā (2 T) A X1
02 (0 A +
+..) 02
C
+ 11 11(6-11 A (...0) (011 (2) A( A (2(1)
(2)
Dyn
22) (02 A+ 02 Iim) +.220mmm) +...] 02
-,0 (C2 2)02.
(38)
C1, Z E N We use C₁ C2 and 2 to denote the variables from the corresponding environment e. We further denote C3 = C2's A X1, 7 C5' Using these notations, the loss of environment is
R(e)= Eng m2
[Ilf((A Y01
(39)
||c50, (CH 2=) A X1 Ae"xx nn
Eng,
2
Denote the inner term C₁02 + (CS Z0)02 Ae X1 n1 as la.
The variance of loss across environments is:
V. [R(e)] EE, nR2 (e)] [e))
A=xx1 CT0 + (C2 2=)02 A X1 - [111 (1)
27
Ee
Eni.es
(40)
E
E Eni
CT01 (C5 70 Āe* x1 m1
[mnimz
(1.(6)2] E² [En [1. [o]]
34

---

Take the derivative of V. (R[R(e) with respect to 81:
0% [V.[R(e)]
Ee [2Em my [Te te] Ens,ma [21]] cil
081
(41)
2 [2 [L [b]] Ee [lmm.m2 [21] ci]
Calculate the derivative by terms:
Eni,no m2 10 [e] Eni
CT (T00):/---CGG--00000000000000000 (A
X101 CTTTine n10
+ + C2 Z - C5 05 (A*)* - Cÿ n102
+ C50,2 + C((6) ((A+))(1)) (C(0; + +C80)) ((4))*x1) - + ((Ar)* X1) (A'r)> X1
- (Ar)* X102 Z n102
+ (1) m1 - ni (C + C500) - n 00 + n (A+) X1 + n. ml]
(42)
Since n1 and n2 are independent standard Gaussian noise, we have En [11]] = Em [1n] = 0,
Eniiaa ["] n2] = in [n] ni] = 0 and E2g,n [m]] ni] = Enn.ng [n] 1t2] = No if the noise from e. Also, since e and ni, n2 are independent, we have Rn [n] e = E Ep [n] e*] = 0.
When
0100 = 1, 87(0) = 1, == - 1,,,, L 8 s+1 (1) 0, 02 1,
(43)
01 (1) = O, 02 =1, =1, 1=1.-1,..,
we have C³' IN- E RN=x N and Cf = Å²'X, Consequently, we get En Ize ni] =
tr(O5' Ae = tr(AAe). Eng ma IZeT 70] (( N + Tea
Use the above conclusions and rewrite Equation (42) as (here we only plug in the value of Ciy)):
En 1...221..e [=] (F + Cf CGTC5000 ( + CC C3(02) CS T (At)*x102 +rr ((i=")((AE)) (0z)²- - (CF0) ((A)))))) X1 + No (1 + (02)2) (*)
2
HCT ca + + To + + -e)
e2 (**),
(44)
(+) and (**) represent terms that are independent and associated with e", respectively. Additionally,
T C7 + Eng,ne2217 Ci1 = 2 c T cT + +
((A))));)
(45)
2 CT C10, + C CT0 + T C702 10002-(66) -922-((1))))))))) ((A))((()))))
Multiplying Equation
44p and 45 and take the expectation e, using the assumption that [[(( 1 o² (c", is the i-th element of c.):
Eg [2En, mz I7. te Emy.
[21] Gi]l 4E (+) (O c70 + T C5' - ((Ae)*x;) ci)
+ 4E,
(ÁE (i) A=" Xi X3( + (02)²) 2(A=² X1) ((Ac)* 0202
+ +4E, [N TT (Ac X1)
(46)
Next target is to compute 2E, m, [.]] and E, [E,,,, ma [2) Ci]]. Since e" has zero mean, we
have:
2E. [.,, mE [.Tle]] = [(+] + (0,
(47)
35

---

and
Ee Be( mz 12 Cfll
2B
09 c +
(48)
Use Equation 46 (47 and 48) and
let
@v. [[(]]]
0, we have:
001
Es 3(A= " T (1) + +0( (A))(00000
-((Ae (())(((A)>* x1)00/ 0² Te Xi)]a
-E. ((A- X1) (1) + +2) - ((A)))x,) T 020² =0.
(49)
Now start calculating the expression of 8V. (R(e)) 00g
0V. [R()]]
= R. [2Emyynng [o [e] Emy.ng
[21] (C2 + T²]]]
062
(50)
21E,
EB m2 [[_ E. [Enim [2 (Cg + -*]
[R(e] 0:
Let
00g
E.
(CT
T C2 C2 Cg'
2((A)))xx)) TT' + + 0T CTT)0 10,0 (CT) -((())))(((()))x) TC5'0)
(O2 T 0202 - ((Ae)* x1) (1 03' o²
Eg
E. N CTTCOO C/ + C C₁02 - -(Aee}xxi) C2 ir(((Te))T''' No Cg. CO' (02)²
= O.
(51)
Plug Equation
49 in 51
we reach:
Re No
N (Ae
x1) (A= (0) + 02) ((AT))xx)) 0² BTloTTeeTTT x 02
E. (A=" X1) 1N-02 (Ae** X1) X IN=)
Ee NN ((Ac XT) T
Ar x (0: + +b2) -(A- (A''x,) X1) Ar T tr(((A")) No (1+ +z2) (02)²
=0.
(52)
Let C1 = =x)
x1) (A'" x1)l 02 = (d= X1, cs = E.i(A'* (() T1)
C4 E.I((A 11)
x Cs E..[N"(AA** x,)_ Ae X1 IT((A=")TAA Tx²²)) No +z))]
c6 E. (()('')))T (AA= X1)), 07 Eele TT (A=" X1)].
x1)
we conclude that
{
(3c10,02 + c) -0,)22220000)) - NNe (0, 02) 02) (c3 02 (0, + 62) (0,) =
(0, + 02) - -2) + c002 =0
(53)
As for the derivative respect to 01 (1)
g2(1)
01 (1)
03 00((1) when they take the special value in Equation 0V, Meee]
(43 we have 0y [[(]]] 0 04 [[(e]]
[V. 0 and aV.[M(e)
0
30
80,
363
[R()) 0, - = L...., L. So we conclude the solution induced by Equation 20210
53 is the solution of
the objective, and 0g = O is not a valid solution.
36

---

G.1.3 Proof of the Failure Case on Graphs of IRMv1 under Concept Shift
We present the formal version of the IRM part in Theorem 2.3 as Theorem G.3 below.
Theorem G.3. (IRMvI will use spurious features on graphs under concept shift, formal) Under the SCM of Equation 2 there exists N+ that satisfies 0 < <, L and + k such that optimizing the IRMvl objective mine E. L1V 11 will not lead to the invariant solution 02 = 0 foror
parameters of the GNN 3 when {0} ,02() 02 0z20) take the special solution:
07 = 1, 07(() = 1,
I 1= L -..... L - sst1 ++1
O
01 = 0, 02(0) 1,
1= L. 10--, 8, L. 1 1, 1,,..
(54)
0 (1) 0, (2 1, 1 1,.,,
Proof. From the proof of non-graph IRMv1 case Appendix G.I.I we know that when IRMy1
objective is optimized, have V R(c) for all e. For the graph case, the expected risk of environment e is
R(e) = my |10 Cf + 02 zタ) ( 11
(55)
where the definition of Cf. C. and z follows Equation 38). Now let's check if the invariant solution 02 = 0 is a valid solution. If 02 = 0 holds, then the following equation must hold for every environment
V R(e) Em, +2 =2) (A-) (0:C7 (2 Z-)] (C) (C+ +0) 00 (C5 + 2
(0:)20 (1))( (Z)
(56)
-0,C7 -0,CTT ((Ae))Xx++n))
(()))) ((A+)*x))
=
((,")",, When s k we have 0 (()+)-x,) (((a))'')'''' The value of this solution of 0 varies with environment e, and thus is not a valid solution.
However, now will show that optimizing IRMv1 does not necessarily lead to lower-layer parame- ters such that s = To reveal this, by taking the derivative of LIRMI w.r.t. 0, and 02 and let them = 0, we can get two cubic equations:
0LRMM1
[EC (T [C((CCTTT((0))+++ (C
+ + T e 2N +c
00,
x1) CC
To
[A X,) T + N
+ + +n]+ (12))
(57)
(20 To _ 0 + (CF Cj+ - c)0² (A' X1) [C]]] =0
and
1iRMM1
-E. (T())))TT(())) + (C= 05 20 + 22 + -e ==]2(22)2
002
e0 (At X1) T [90 - [[A=* X1) +N + nnj (0)))
(58)
(2(C) C5 + 20 E 2N + eT 9)0 + (C C + TT c)0
-(Ā x1) (C + + + No + nI T =0
we know that as long as the lower-layer parameters take any value that satisfies the form in Equation 27 even if 8 + k. we can get @Cama
From the analysis in Appendix F3
&Laya
BGaya
80,
86;
and aLans
0Cumu 003
@Cunu Thus, IRM cannot necessarily learn a = k. At this time (when 30
89,
@CRMal 00,
@C 80
0C 09,
= 0 and dCRMA @Cras 80,
@C = 0 but + k), from the form of 092
00,
Equations 57) and 558
know that there exist solutions that 02 H O. and the solution of O, and 02
both depend on E.,
((e)), where F(e) is some random variable associated with e.
37

---

G.1.4 Proof of the Successful on Graphs Case of CIA under Concept Shift
Theorem G.4. Optimizing the CIA objective will lead to the optimal solution @*
0 1
02 = 0 and 31 E {1..... 1) s.I. 0 (1) = =02
0100) 1, 11 1, [= L 1, .... k +
(59)
01 0, 0,0000
1, 1 1= L - k, L k 1,..,,
Proof. For brevity, denote a node representation of Cf. as Cj and the one of Ci' as C₁. The same true for Cj and C3. In this toy model, we need to consider the expectation of the noise, while in real cases such noise is included in the node features taking expectation Therefore, we add Eng,ng in this proof, and this expectation is excluded in the formal description of the objective in the main paper.
will handle this.
LCIA
E,e Eo EE opc'
[(
[ele. Φe (clle))
)[(1vy)) ((ell)))))))))))))
(WEm
(60)
E e,e' exc'
En Eng E&E
W (Wi))Ma
11;00 + +C 2-)0 Ci - (C) + 2 00212
dCCIA
00,
E e,a exe
En, mg E.E
i (WE)
(C
2z )8)8 (Cf
(61)
Let 8hcs 081
0, we have:
E eee E. W
(c)- -C²
=0 (62)
exfe' (Ween
Also, we have:
dCCIA
(C)-C) + [[0} c (O))(CC (C) C/) (z
z 02) 02
E Be
E&E
is (.))n
802
axte
(63)
Further let 092
0Cru
0, combining Equation 62) and using Assumption
2.1 we get
{
01 or El (1..... L 1) s.t. 81th (1) 0p(0)
(64)
0₂
or, if # 0 and 4T E (1, ..,,,., T. 1}, the parameters of that layer 1 of the invariant branch of the
GNN are not all zero: (1) # 0 or 07 # 0, then we get
- -C (Ci - TCC Cy) + +C
Og E n.6' ext' (
E, by
- -C--C)CC----------3- -2d
=0
(655
According to Cauchy-Schware inequality, F unless 31 E {1, ..., L 1} s.t.
01 (1)
02(0)
To ensure
dhTs we conclude that 02 = 0 or 31 E {1, L-1. 1} s.t. 03 02 0.
36,
In conclusion, to satisfy the constraint of CIA, no matter whether the invariant branch has zero output, the spurious branch must have zero parameters, i.e.,
0g or 31 E (1..., I 1} s.t. 02.00 02(0) =
(66)
Thus, CIA will remove spurious features.
Now we show that when CIA objective has been reached (the spurious branch has zero outputs), the objective of ming E.[C(f(AA' Xx), y*)] will help to learn predictive paramters of the invariant branch 01, (1( and 02(1). When Equation (6) holds,
38

---

[E,[[(fo(Ar r
[ - (dr))x, - m)
22, Ba m2
C9
001
(67)
(CE))-((e)(x)) Cf
= 2e
Let 83, (l,](((((AA'"")))) 091
0, we get the predictive parameters
0, 1
03 11, -1,0(1)
-,, 1= L 1, m L k +
(68)
0100) 0, 020
=1 1= I, k I. - k 1...,
Plug the final solution back in
DCCIA (0)
aCoA 00
8CcA
aCcA 20g .
00p (
(LL(A[a(AA 301
8E. (C Xx ).,
009
003
we can
verify that these
terms are all when further letting EI E {1,..., L 13 s.t. 8 (1) = 03
G.2 Proof of the Covariate Shift Case
G.2.1 Proof of the non-Graph Success Case of VREx and IRMvl under Covariate Shift
We restate Proposition B.I as Proposition G.S below.
Proposition G.5. (VREx and IRMv1 learn invariant features for non-graph tasks under covariate shift, proof is in For the non-graph version of the SCM in Equation 19
Y = X1 + Ti, X = 122 +
(69)
Optimizing VREx ming LYRES = Vo( and IRMvl mine LIRMII = E.[l V R()= will learn invariant features when using a I-layer linear network: s(X) = 02 X1 + 02X2.
Proof. VREx. For covariate shift, denote X²0 + X582 X1 ng as le. the expected risk in environment e is R(c) = m,l6___ 1 + 82(m2 + +c)) - (X1 + n2 I12. Take the derivative of the
VREx objective V. [R(e)] with respect to 0,:
8V, [R(e)] Ee [2
[To le] Eny,ng - xi]]
00,
(70)
21E [Enima
[6_ [e]] EE [m [21] X1]]
Calculate these terms:
E. [., m2 [' Le] X.]]
Xi]
=(0,) X1) 0, 0,2)) X,02 +X]XIXNN'++ T(
X1 - - (NT)
(X (3xx x + E.(N)) - Xx) x1) Ec(N9)
(71)
E. [., .ng [e Em, 1 X1]
(X) x1) 01 (02)) X10² + XI (
(X) X1 - x1)2) (xx)²(XT X1) (0² Be(N')
(X, x, (3(XT [ - (X X1) ((X, X2) + E((N
Hence,
0V [R()] (02)) X103) + (02) 2(0))2x10²
(72)
00,
Let 8V. [R(e) 0, we have 02 = 80,
When 0g = 0 and when 0, 1, we get
Em 11 (no e)) = 0.xIe e- XTe e 0.
(73)
39

---

As result,
(V.[R(()
[2 .22
[o [odc]] Eng,ng [21]] (nz + e*]]
082
2
[m
m2 [e Ee [lmmimn [21] (n2 E3)]]
(74)
In conclusion, 81 = 1 and 02 = 0 is the solution of the VREx objective in this non-graph covariate shift task.
IRMv1. The objective of IRMv1 is E. V w RBe When IRMv1 loss optimized to zero, we have v. R(e) 0 for all environments
V R(e) Eng [2(0)X] + 02X2 (Xi (.)) + 02X2))
(((0))2x] X1 (02) ( + + 20,02X,
(75)
01 X1 02X] c
To realize V R(e) = for all e. we must let 02 = 0 (and consequently 01 1), otherwise the solution of 0g will include terms related to E" and N that vary with environments, and single value 8g cannot fit all these values. Thus we finish the proof for IRMv1.
G.2.2 Proof of the Failure Case on Graphs of VREx under Covariate Shift
We restate Theorem B.2 Theorem G.6
Theorem G.6. (VREx will use spurious features on graphs under covariate shift) Under the SCM of Equation (7). the objective mine Ve[ [R(e)] has non-unique solutions for parameters of the GNN
3 when part of the model parameters {0} (1) 02(0). 00 (1) 02()) take the values
01 1, 02(1) (1) 1,
I - L - 1, -,,.., L + ++
Oo
0 (1) = 0, (2(1) 1,
1 8, L 8
(76)
01 (1) 0, 02 1,
1= L ....!
0 s < L is some positive integer, 81 and 02 have four sets of solutions of the quadratic equation, some of which are spurious solutions that 02 + 0 (although 02 = 0 is indeed one of the solutions, VREx not guaranteed to reach this solution):
{
c20 02 + (02)² 2 22) + cg02 - oe E.[N"] =0
(77)
[cs02 E. [N
[N 2100 0162 + E. [N 02] Ci cs (02)
where B((Ae X1) (A X1)). 02 -E(
(Aie* Xi)l. c3 = E, T xi)]o?
EE ((Ac)*X)) T IN 02, lE No (Ir((A=") TA Aet) N=(1))))]]
A
Proof. We will use some symbols to simplify the expression of the toy GNN. Denote n2 + e as Use the following notations to represent the components of the L--layer GNN model:
(e(A, X)
0 1 10 (LLL-1) A (...03100
(0000)(000) A0 A+ (2 1)X1
A+ 02 (
(2 + ...x))
C
10 11)(1-1) A (...8) (0) A(o!
(1)
A 82(h) Iyn
82 (2)
(0)
(1)
A+
02.00 Imn) +..)] 02
= Z8g.
(78)
C₁ 7 E Nx1 We use Cj and Ze denote the variables from the corresponding environment We further denote Ze C5 77.
40

---

Using these notations, the loss of environment is
R(()) Eny,,
( - -
(79)
C98, + 2=0 A= X1 n1
Denote the inner term C70, + 02 - Ae X1 as la The variance of loss across environments
is:
Ve [R()) = E. RR² [e)] - -E][R(e]]
CG01 + -= - A= X1 m/ 11]
27
E,
Emi,a2
(80)
C50 + Zº02 A X1 - 12 1/-
E²
Emgin
= E (mmi.n
R22 Bnnina [o [o)]]
Take the derivative of V. [R()) with respect 01:
0V. [Ree]]
Ee [2Em, ma [Le [e] Eny,a [21 Ci]]
00,
(81)
2 [mny.ng
[c
Ee Emn, [2 Ci
Calculate the derivative by terms:
En, mol
[o [e] = Enn.na [C1 -00 (f) Ci m10
+ Z C,0,0++ z (Ar)*x100 Z (²))))²
zz n102 - -(AA))x))) C - ((Ar)* X1) Xz) + ((A9)* x,) ((Ac)*Xx
(82)
+ (((A)){x))T mm - m ni z + ni (Ar)* X1 + n,nnl
Since n, and n2 are independent standard Gaussian noise, we have E,g m2 [1a]] En ma [mg] = 0,
En mz [n]] n2) En [n]] m1] = 0 and Ex,, [n]] n1] = Eng s [n] n22 Ne if it is the noise from Also, since e and nı, are independent, we have Bng mg [n]] 6 = En,, mg [n] c*) 0.
When
(1) 1, 00 1,
1= I. - 1,.., 01 (1) 0, 0,077() =1, -= - S
(83)
01 = O, 02(0) =1, 1= --11--. 1,.... 1
we have Ce' Ix E XN' and Cf = Ae X,. Consequently, we get E. Byy, [ZeTnz) m1] = 0.
E,, m2 [Z 7
= No + Te.
Use the above conclusions and rewrite Equation 82 as (here we only plug in the value of Cty):
oF -
No (1+ (1+ (02))) (+)
(84)
-((Ár)*X)) + (()) N T 09
T c = TTq001 + E (((2)) -((2))=-((((A))) (() eB (*+),
(+) and (**) represent terms that independent and associated with c. respectively.
Additionally,
mn [21] CT) = 2 CT CT0 + + 0,02 ((Ac)*xx)T
T
(85)
41

---

Multiplying Equation 84) and 185) and take the expectation on using the assumption that E.[(c") .) o² (e"; the i-th element of c"):
E. [2Em ma malle le m2 [21] Ci]] = 4EE (+) (c) C50 (TTT00 - ((Ae)) x1) x [c:]
+ 4Ec (A- X1) " (20 + (02) - -2(A="X)) ((Ar)) 020²
c T T (A X1)
(86)
Next target is to compute 2B. [En m2 Pe [e]] and Ee [Bm [2]] Ci]] Since ef has zero mean, we have:
[Eng
2 [mn my [e] B[{+)] + [[22
(87)
and
Eg [B ma [2 Ci]l
2E
C T C50 ((A-)* X1) C7
(88)
84. [R(e)] 0, have:
Use Equation 16 (87 and 88 and let
891
Ee
2(A= X1) (A (0 + 2 (02)²) 2((A² X1) (1) ((Ar)*
0² + =Bl T (Ax))00))))
E [AAc* x1) (1A (A (1)) - ((Aa)* X2) [cp] 820 =0.
(89)
Now we start calculating the expression of 0v. [R(e) 86g
0V [V([](e)] Eg [2Em, na [L [e] En m [21]] ]
002
(90)
- 2E Emi.na
[e te
Ee Eni. nz [21] 2
8V. [R()) 0:
Let
06g
Eg
( T C²' + Of
CI 10,02 (z''2² -1( C3'02 Re (-((At)(xx)) 0²
Ee [Ne (Ir((ā=") A + No - cg'o²) (B2)
0.
(91)
Plug Equation 89 in 91.. we reach:
Ee No N (Á= " X1) (A X1)01 - ((Ar(() [T] 020²- - -ETeTT (At (Ae))())))) Ee (-(Ae" x1) xx)x
Eee Ne (I(((A=))
"e(((ã=)TT<c) Ac
(1++ (02)²
O.
(92)
Let C E[(A"* x1) (A= X1)], C2 E[(Á x1) (A X1)), C3 E. T x,)30?
T
C4 Ee (((At))xi) INo 0², c5 LEe |vee (Ir((E=)) T (
we conclude that
c202 02 + (02)² - 2020002) + 03 No 00, + [Ne 220 = 0 {
(93)
[ca02 - E. [N"]c]20010 + E. [N ci - cs (02)²=
As for the derivative respect to 01 01 (2(()
01 (1)
03 00(()) when they take the special value in Equation 0v, Meee]
183 we have @V_ [[(e]]
04 [R(e)]
[V. 0 and aV.(l(e)l 0
0
89,
36
80,
363m
RR()) 0, = L...., L. So we conclude the solution induced by Equation 93 is the solution of 802i0
the objective, and 0g = O is not a valid solution.
42

---

G.2.3 Proof of the Failure Case on Graphs of IRMv1 under Covariate Shift
We restate Theorem B.3 as Theorem G.7 below:
Theorem G.7. (IRMvl will use spurious features on graphs under covariate shift) Under the SCM of Equation (99. there exists E N+ that satisfies 0 < s < L and s # k such that optimizing
will not lead to the invariant solution 02 = 0 for the IRMvl objective mine Ee [1V 1.
3 when {0} _0900 0 (0) _020)) take the special solution:
parameters of the GNN
0) (1) 1, 09
1,
== L 1.,,. s+1
0 0, 0z (1)
1, 1= -, 1,..,,
(94)
02 (1) = 0, 02(0) 1, == 1,,.,
Proof. From the proof of non non-graph IRMv1 case Appendix G.I.I we know that when the IRMv1 objective is optimized, we have V. R(e)) = 0 for all e. For the graph case, the expected risk of environment is
R(e) = E,,, mg [1|0: + 02
1 nu m1112]
(95)
where the definition of Cf and z follows Equation (78) Now let's check if the invariant solution 0g = is a valid solution. Let 02 = 0,
V R(e) = En,, [01CC + 02 (At) - n1) T (0,C5
(0i) (()e)()))))))) ((Ae)=(()))))))))))))))))))))))) (02) + (6) 20 (0(0(((())))))) 01 ((Ae)) ((Āe)* ()))))(xx---))) - 02
(96)
+ If 02 0 is feasible solution, then the following equation must hold for every environment
(0, ((A))(( X1) ((A+)*x))) 01 ((Ae)*x)))) ((A+)* (((())*x,)) X1) = 0.
(97)
When * k. we get 01 = T
((A")*X)) ((A))x))) (we discard the trivial solution of 01 = 0). The value of this solution of 02 varies with environment and thus is not valid solution. However, now will show that optimizing IRMvl does not necessarily lead to lower-layer parameters such that & = k. To reveal this, by taking the derivative of LIRMII w.r.t. 01 and 02 and let them O. get two cubic equations:
@LIRM1
[E.[(CT (0, + (N + Te) + OT c0,02 - (At x1) 090,)
00,
(98)
(2CT Ti 0, oT c02 (A+ X1) CT) =0
ILIRMv
-Re( ([(())))) + (No + + (O)2) oi c0 - (Ax=xx)" x,)
002
(99)
(2(N' T e0 + (CT C + CT e)0 =0
From the analysis in Appendix F3 we know that as long as the lower-layer parameters take any value that satisfies the form in Equation 27). even 8 f k. we can get
LL
00,
60
80;
and
&Ease 002
&Cama At this time (when 8E & 003
@C
= 0 and C
0e 2
801
ae
00;
802
0Cuma 80
DC 203
but 8 + k), from the form of Equations (98) and 99) we know that there exist
solutions that 0g2 + O, and the solution of 0 and 6g both depend on E. (F()), where F(e) some
random variable associated with e.
G.2.4 Proof of the Successful Case on Graphs of CIA under Covariate Shift
Theorem G.8. Optimizing the CIA objective will lead to the optimal solution e*:
02
02
=1 I = L - 1, .... L k + 01(0)) O, 02
8) 1,02(1)
(100)
= -1, [=
k, L k
43

---

Proof. For brevity, denote node representation of Ci as Cj and the one of Of as C₁. The same is true for Cj and C2. In this toy model, need consider the expectation of the noise, while in real cases such noise is included in the node features so taking expectation on will handle this. Therefore, add En,,ng in this proof, and this expectation is excluded in the formal description of the objective in the main paper.
LCAAC E e.e E mg efe'
B.
[D(des ( [ello)))) x )
(101)
E e,,' E ma expe"
E.E (dE)n
|1q + 2e -ct - 1
OCCIA
Ci8 + C/O zd/as] (Ci C})
E end exfe!
E Ba n2 E.B
(102)
001
f (1.))
Let 0Cms 00,
0, we have:
ee E. e
(C- - -() =0
(103)
(I.))
Thus, we get two possible solutions of the invariant branch. The first valid solution is the optimal one:
0 =
01 1, 1,07 = 1, == L 1, 1,... ...,, L k 0100 0, 00077") = 1, I= L k, L - k 1,....
(104)
The second valid solution is a trivial one:
0 0 EE E (1...., - 1) s.t. 01 =02!1 0
(105)
Take the derivative of the objective w.r.t. O2:
aLciA 002
E e,e' E.E expe"
W (1
[[ zz' TZ= zo) 02] 22222 8z
(Z
(106)
Let 0Crs 092
O, we get 02 O. Thus, CIA will remove spurious features.
Now show that when CIA objective has been reached (the spurious branch has zero outputs), the objective ming Ee[C(fe(A' Xx), Yo) will help to learn predictive parameters of the invariant branch 0, () and 02(1). When 0g
(E, Y
(Ar)* - mi) c9 ((A))-
2E, En nz
00,
(107)
(c90) ((90)-(A9)*X1) oi
2E.
Let (2.12(/(('' XX) 091
= O, we get the predictive parameters
{
0 0150) 1, 1,0301) =, 1 1= 1, L
k +
(108)
01(0) O, 07!1) 1,
1= L
k. L k 1 1.....
Plug the final solution back in
aCas 20
aCrAs
aCas
aCrIA 00get
8E_ [C(fo(A"" 80
aogeht
(4 az, (2.
DE, [C( _X")
we can verify that these
801
00g
terms are all 0.
44

---

G.3 Proof of Theorem 4.4
The following proof of Theorem adapted from Ma al. 2021 and Mao et al. [2023). We
restate Theorem 4.4 Theorem G.9 below.
Theorem G.9. (Subgroup Generalization Bound for GNNs). Let h be any classifier in a function
family H with parameters Wi i-1" large enough Nov, with probability least 6, we have
Under Assumption 4. and 4.3 for any el E Exes 7 2 0, and
C. (h) S (h)
C
+0
Σ
V live Me) ( -2) co"
σ²
c=1 c'
(a)
+2
(C
B) 1ig - Me
(b)
(109)
Ne E ΣE
(c(e))
20 Ne
VEVer
jEV()
c'
(6)
b
W
(cor 2214 +const)
(7/8)2/L
(d)
where 1h! (c(lc) is the ratio of heterophilic neighbors of class d' when yi c, consl N In LC(2B.a) is term independent of aggregated feature distance and the difference in 71/6
neighboring heterophilic label distribution, where Be maxieVauv, llg:lla l2 is the maximum feature norm.
To prove Theorem G.9 we need the following lemma that bounds the expected loss discrepancy between the train and the test node subgroups.
Lemma G.10. Given a distribution P over H. for > define the expected loss discrepancy between V. and Va with respect to (P.7, X) as D (P:A) == In Ee (C7/2(M)-23 Under
Assumption 4.2
we have
C
C 2222) + > (C B) - -16")
D7/2
Ilme - (1n - (2")
c=1
c=
New Σ ΣΣWNN (cl)) - -x((())))
20 Ne
VEV.r
jEv(i c=ld#e
(110)
45

---

Proof. According to Eq. (14) of Lemma 5 in Ma et al. 2021 under 4.2
we already have
Ce- L2((1 (h)
E
1 Σ
(Pr(y, clgy)
Pr(y: -cg)))
Ne
seVe
JEVV
E 2VV
E
Σ
(Pr(y) - clgi) - Pr(y - cc):))
Ne
N
jEV(O
(111)
In the following proof, multi-classffication OOD generalization setting. Using the Bayes theorem, we have
the main goal is to bound the term (Pr(y, = =lg)) - Pr(y: = clg.)) under the
E VVV
Σ
Σ
(Pr(y =lgg)) - Pr(ys = =clg))
No
No
jEV e=1
Pr(gily; = c) Ee'pe Pr(gi M/ = c) - Pr(gil = C) Pr(grluj = c')
N
N
EE Pr(gj و By = c'))(E Pr(gi =c))
1VV
jEV
(112)
Pr(g. (kg Pog (ي:
for each d' + c, and bound all these terms respectively. When yi c, denote (c) E R Dx as the matrix composed of all the class means of node uz's heterophilic neighbors, i.e. the columns of pa(c) 1', c' E {1, 2,., C)/(c) [cc]-- The elements of pht E RC-1 are corresponding p."(c) c' E (1,2, C)..c.. According to Definition we have
Let consider the term
(E9 - Pr(g. by [()=
Pr(gelys c) V2TTo2D
exp( 1
1191 lp! pe )
v TT +(ule)) P T 12)
202
(113)
Denote EEo=1 Pr(g, 1u5 = cc)) Pr(glv: = c)) as exp(M) [0, where M >
constant, have
Pr(gily;
c) Pr(gily; d) Pr(gilu c) Mj = =d)
CC Pr(gi M1 c')) Pr BE = =c))
=/exp(
20 l1g: - 1p) hm Pe + (m(())p)) ip, bm ME
+ (ms(c)) 25 TT
exp(
2 Ily:
W!!TNT + (( :P. ne
+ (mild)) p. T
(114)
exp(
W (mi(d))))) ae
+ (as(d)) 2) TTTBB
20
exp(
|lg:
Ip!mm? Me (T :p km Pe
(ma()) ).T)T IBB) exp(-M)
2
Further arranging the formula, we obtain:
Pr(g,lu; Pr = -r(gllu = c) 10; = =d)
(Ee=) Pr(gj |y; = =C Pr(gc = =c))
=| exp( ||g W + (M(())29)) T: " T
+ (m,(c) PIT
20
1g, - (p/mmp? + (1 Tpp! "ppmpp T
+ (milee))* oM phh) T M)
(115)
202
-exp(- 119; -ID)" + (Hi(e)))))
pet T
+ (Hy(d)) TI
20
1g. 1p! (Hilc)p!") T
in mm
TT
(milc) p P
-M)
20²
46

---

Using Lagrange mean value theorem, we have
exp(-x) exp(-y)) =exp(-))l x| s a vl
(116)
for x, y > and { E [x, vl (or E [y, x)). Using Equation (166, we get
Pr(gily; = c) =d) Pr(gilue c)pr(gslus d)
(Ed=1 Pr(gs My C' Pr(gcl = =c))
1
20 (1lg) Ip) He + (H((c)p))) :P' + (H5(C)) p3) T
+119:
I hm u + (mi(d)p,,) T, :P; hm de
+ (mild) p.,) " 12
11g, 10 v + (u((e)) pp MC
(ws(d)) P9 1
l19. IAAT ue + (mi(c)pp") T ;p:-p PC ="
+ (mu(c)) p. TT
(l(me -me): ; -1²) (19,)) ".pp"") + [0; (ug
)T (V6" - -1x2) Tlapp
+ (c)g: (c)gg) + 10: 1p" (c)gs
(A)
-Wuiin 1E "[02" (d)g)) 10: 1n)
10: (c) [0; 10 Ip)
+ 20 ((p)m - pm (1mee11 112 - |/ (13) + pm | 12 - -!-
r!-! 1 10 [13] (B)
2o (6g) - (c) )lleell 112 + (c)) 11 " 1
-
(c)
(c)) (c)) Ml (c)) 1 (c)""))
(117)
Let's bound (A), (B) and (C) respectively
(0) 1 (A)
σ² (1((Mc Me)) (nE." - -15) 11ll9 95112 + (lug" - wE" I + 1 - 1 Deal
+lluo He"" 11ll: -ill2 + 1Ind: I119a - gill2
+ +(mm5 - - In - 1151)))))))
(
oz (WVIICu - No)):((E - 16" ) + +222) - -i (1m6" - -v6"l + 1u - D1 (19i1+ l9s1))
2 (W/lCV - M To - 1 ) + +222) 16 - 9s ll2 + 2B (1ug" - - +I - we'l)
(118)
(a) uses the fact that 1g 9.r..m < |g - 11ll2 and p.tm (c), (c)),, p.m (c), (c)) are
all < 1, and (b) is because of the assumption that ||vT u I| IIdi '1I = V2.
Also, since the class means are normalized, we have (B) 0.
Similarly, we have
20 (c) - (c)² - (d)( - (d)3)) (C)
(119)
< 202 (c) (c)) + (e) (c)))
47

---

Using these results, we have
C22 - Ege (h)
Pr(gilus 6) E Ed Pr(gi y5 d) Pr(gilv: Ed Pr(gs) 1/
Σ
Ne iVV
Net
(E Pr(gj Uj = = = =d))
Pr(gi
JEV
c=1
Σ ΣΣΣ
o ((y 11(eo Me)
2V2) -95112)
Now
Nok
V
jEV e= c'zc
2
Σ (C 1)B ve'l
0²
Not Σ Σ -((clc)))(((1)))
20 No
jEV( c=l c'
|1(ee (e) (16 - 11 |T] + 2v 2e + E(
(C - B) 11g -
c=1 tCc
c=1
Σ N
(d)(c) (cl(c)))
20 Ne VeV,
New
jEV
cof
(120)
Now we can proceed with the proof of Theorem G.9
Proof. Directly replace the result of Lemma in Ma et al. [202] with that of Lemma G. 10 and
following the proof of Lemma and Theorem 3 in Ma et al. 2021 under Assumption 4.3 we finish the proof of Theorem G.9
H Limitations
The theoretical analysis is limited to linear GNNs. However, there some justification for using a
linear GNN. 1) Some recent works (Zhu and Koniusz 2021 Wang et al., 2021b] observed that linear
GNNs achieve comparable performance to nonlinear GNNs. Tang and Liu [2023) also theoretically
proved that SGC can outperform GCN under some mild assumptions. 2) many recent works on the
theoretical analysis of graphs/OOD generalization adopt linear networks (Lin et al. 2023 Wu et al.
2022b Mao et al. 2023). 3) Our theory matches the experimental results on the nonlinear GCN and
GAT that CIA outperforms IRM and VREx.
We didn't implement some of the node-level OOD methods in our main experiments including Li ett al. 2023a], Liu et al.) 22023] because they didn't release the code. Another limitation is that we didn't provide in-depth theoretical comparison between our method and existing node-level OOD methods, but only revealed the difficulty of invariant learning on graphs through the examples of VREx and IRM. However, this theoretical finding is sufficient inspire the CIA solution and its enhanced version, CIA-LRA. We reserve a more comprehensive analysis of the failure of OOD methods on graphs and broader guidance for designing graph-OOD work for future research.
I Broader Impacts
Our work contributes to improving the node-level OOD generalization of GNN models. We believe our work could positively impact various fields by improving predictive accuracy in areas like healthcare, social networking, etc., potentially leading to hetter-personalizee services and enhanced safety.
48

---

J Compute Resources
We use one NVIDIA GeForce RTX 3090 4090 GPU for each single experiments. All algorithms except EERM and GTrans can be executed on a single 24GB GPU when processing the largest dataset, Arxiy, without encountering out-of-memory.
49

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction concisely state how we dissect the challenges of invariant learning graphs and out strategies to tackle it. In the introduction, we list all our contributions and indicate the sections in which they are made.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We point out the limitations in Appendix H we didn't compare the empirical results with some of the node-level OOD works because their codes are unavailable; we didn't 't theoretically analyze all invariant learning methods.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
50

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All supplementary assumptions, formal versions of the theorems, and full proofs can be found in Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have provided all basic experimental settings and the hyperparameter search space in Appendix to reproduce all our results. The detailed training procedure of CIA-LRA is provided in Appendix [ We will release our implementation of CIA and CIA-LRA following the acceptance of our work.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
51

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: The datasets utilized in our paper are publicly accessible and remain unmodi- fied. We will release our code following the acceptance of our work, complete with detailed instructions to ensure the faithful reproduction of the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
Stwpe//oSoouuueeiiiiiieiee www.bmmmsssioooociioioooi for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurIPS code and data submission guidelines (https / /nips.cc/publicc corooliccggideeee htte://guuddeeeoooSuuubieiie wwiobbmmssiooooiiioiooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We adopt the default training details open-source GOOD benchmark, and we have stated some modifications the setting in the main text and the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The improvements offered by CIA-LRA exceed the error bars of the best existing methods, Also, CIA significantly outperforms VREx and IRM across most dataset splits.
52

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the eπror bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Appendix ! we report the type of GPU we use and the memory costs. Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttpp////aaarrr....//////////le
Answer: [Yes]
Justification:
Our research conforms, in every respect, to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
53

---

Justification:
We discuss the potential impacts of out work in Appendix !!
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Yes. All assets used in our research, including code, data, and models, are properly credited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
54

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, palasets.papersstt paperswi thcode. com con/datases has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
55

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
56


Reviews:
[{"review_id": "RKoL8lboLZ", "reviewer": "Reviewer_empj", "summary": "This paper analyzes the failures of standard invariant learning techniques for node classification.\nThrough theoretical analysis, they argue that methods such as IRM and VREx will learn spurious features on graph data. Using this as motivation, they design a new method, CIA, that introduces additional invariance regularization to better guide the GNN to learn better representations. They verify the effectiveness of their method on multiple benchmark datasets.", "questions": "1. What's IRMv1? You begin by mentioning the failure of IRM but then start calling it IRMv1. What's the difference?\n2. On line 135, the authors mention that the GNN used in their analysis resembles SGC. I'm curious how this effects the analysis. How different would the conclusions be if we considered a more standard GNN like GCN? To be clear, I'm not asking for a full analysis here or anything, I'm just curious of the practical limitations of considering SGC in the analysis.\n3. Could you share the time complexity of your method?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. I think the authors do a good job of showing the failures of methods such as IRM and VERx on graph data. In particular, the theoretical analysis is interesting.\n\n2. The proposed method is straightforward and follows naturally from the theoretical analysis. Furthermore, the theoretical justification in Section 4 is welcome.\n\n3. The performance of the proposed method is good compared to baselines.", "weaknesses": "1. The authors seem to leave out some baselines in their experiments. For example, see [Wu et al., 2024] and [Li et al., 2023b]. From Footnote 1 at the bottom of page 2, I surmise that this is because they are not \"general solutions\". However, I find this to be a weak reason for not including them as baselines. Why should that be a disqualifying measure? The authors should better motivate which baselines they compare against and which they don't.\n\n2. Similarly, the authors should include the performance when using MatchDG. In the paper, the authors note the similarity of their method to MatchDG. As such, it reasons that it should be included in the experiments as a baseline. If not, the authors should provide sufficient reasons why to not include it.\n\n3. There's a lack of discussion on the efficiency (time complexity) of the method. This is important, as the authors note that the performance of CIA-LRA peaks at around 6-10 hops (see line 674). I'm curious as to how efficienct it is to consider such a large number of hops, especially on larger graphs. Naively, this seems to me that it can be a drawback of applying this method on larger graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer empj for your careful reading and detailed comments! We'd like to address your concerns in the following points:\n\n****\n\nQ1: **The authors seem to leave out some baselines in their experiments. The authors should better motivate which baselines they compare against and which they don't.**\n\nA1: As you advised, we've added experiments of **CaNet** [Wu et al., 2024]. We didn't compare with [Li et al., 2023b] since their methods require the graphs of different environments to have the same nodes and edges so that their proposed locally stable regularizer can be applied, however, the datasets used in our experiments don't have this property. To include more baselines, we further implement **CIT** ([7], NeurIPS 2023, suggested by reviewer LzeD), a recent node-level Graph OOD method. The results are included in Table B in the global author rebuttal PDF. We use the default hyperparameters for CaNet and CIT. **We observe that CIA-LRA outperforms CIT and CaNet on all splits.**\n\nQ2: **As such, it reasons that MatchDG should be included in the experiments as a baseline.**\n\nA2: We've added the experiments of MatchDG in Table B in the rebuttal PDF. **The results show that: 1) MatchDG outperforms IRM and VREx on 12 out of 16 splits. 2) MatchDG underperforms CIA on average (averaged over 16 splits except on Arxiv, CIA: 57.56, MatchDG: 56.73), and MatchDG got out of memory on Arxiv**. We emphasize that although CIA is similar to MatchDG, our contribution is that we're the first to extend the idea of MatchDG to the node-level OOD task by providing a theoretical characterization of CIA’s working mechanism on graphs (Theorem 3.1) and reveal its superiority in node-level OOD scenarios. More importantly, our main contribution is that we further extend CIA to the scenarios where environment labels are unavailable by proposing CIA-LRA, which shows significant empirical gains (Table B) with theoretical guarantees (Theorem 4.2).\n\nQ3: **There's a lack of discussion on the efficiency (time complexity) of the method.**\n\nA3: To show the running time of CIA-LRA, we show the time cost to reach the best test accuracy on our largest dataset Arxiv (with 50k~60k nodes). The results are in Table C below. The time cost of CIA-LRA is comparable to baseline methods.\n\nTable C: Time cost (seconds) to achieve optimal test performance on Arxiv using GAT on a single RTX 3090 GPU. \n\n|                        | ERM  | Coral | Mixup | EERM | SRGNN | GTrans | CIT  | CIA-LRA, hop=6 |\n| ---------------------- | ---- | ----- | ----- | ---- | ----- | ------ | ---- | -------------- |\n| Arxiv degree covariate | 74   | 551   | 758   | OOM  | 34887 | OOM    | OOM  | 1248           |\n| Arxiv degree concept   | 30   | 360   | 747   | OOM  | 3960  | OOM    | OOM  | 1132           |\n| Arxiv time covariate   | 46   | 246   | 1207  | OOM  | 1993  | OOM    | OOM  | 292            |\n| Arxiv time concept     | 440  | 1481  | 272   | OOM  | 11628 | OOM    | OOM  | 989            |\n\nQ4: **What's IRMv1? You begin by mentioning the failure of IRM but then start calling it IRMv1**\n\nA4: Sorry for the lack of clarity. IRMv1 refers to the practical implementation of the original challenging IRM objective, which is proposed by the authors of IRM. IRMv1 relaxes the bi-leveled optimization of IRM that $w$ should be the optimal classifier in all training environments to a gradient penalty term:\n\n$(\\\\text{IRM}) \\\\min_{w, \\\\phi} \\\\mathbb{E}_e\\\\left[\\\\mathcal{L}\\\\left(w \\\\circ \\\\phi\\\\left(X^e\\\\right), Y^e\\\\right)]  \\\\quad \\\\text{s.t.} w\\\\in \\\\arg\\\\min\\_{\\\\bar{w}} \\\\mathcal{L}\\\\left(\\\\bar{w} \\\\circ \\\\phi\\\\left(X^e\\\\right), Y^e\\\\right)\\\\right\\\\|_2^2 ~ \\\\text{for all} ~ e \\\\in \\\\mathcal{E}^{tr}$\n\n$(\\\\text{IRMv1}) \\\\min_{w, \\\\phi} \\\\mathbb{E}_e\\\\left[\\\\mathcal{L}\\\\left(w \\\\circ \\\\phi\\\\left(X^e\\\\right), Y^e\\\\right)+\\\\beta\\\\left\\\\|\\\\nabla\\_{w|w=1.0}\\\\mathcal{L}\\\\left(w \\\\circ \\\\phi\\\\left(X^e\\\\right), Y^e\\\\right)\\\\right\\\\|_2^2\\\\right]$\n\nQ5:  **How different would the conclusions be if we considered a more standard GNN like GCN**\n\nA5: When we consider a GCN rather than an SGC, the main difference is that we will apply a weight matrix at each layer rather than just at the final layer. Still, consider the simple 2-dim data case, for a GCN (without activation functions), we can rewrite the inference of a layer as: \n$$\n\\left(\\begin{array}{ll}\nH_1^{(l)} & H_2^{(l)}\n\\end{array}\\right)=\n\\bar{A} \\left(\\begin{array}{ll}\nH_1^{(l-1)} & H_2^{(l-1)}\n\\end{array}\\right)\n\\left(\\begin{array}{ll}\n\\theta_1^{(l)}\\\\\n\\theta_2^{(l)}\n\\end{array}\\right)\n$$\nwhere $H_1^{(l)}$ and $H_2^{(l)}\\\\in\\\\mathbb{R}^{N\\\\times1}$ follows the definition of the original paper in Eq.(3), $\\\\theta_1^{(l)}$ and $\\\\theta_2^{(l)}\\\\in \\\\mathbb{R}^{1\\\\times2}$ . For the GCN, the parameters of the first layer of the weight matrix  $\\\\theta_1^{(1)}$ and $\\\\theta_2^{(1)}$ correspond specifically to invariant (first dimension of $x$) and spurious (second dimension of $x$) features, respectively.  From the second layer upwards ($l\\\\geq 2$), both dimensions of the representation at layer $l$ will be the linear combination of the two dimensions of the representation at layer $l-1$. Hence, the GCN removes spurious features only when the parameter at the first layer $\\\\theta_2^{(1)}=0$.  In conclusion, we only need to focus on the first layer to analyze wether GCN learns spurious node features. This resembles the case of SGC where we only need to focus on the weights at the last layer. So the conclusions of the SGC could be easily extended to the GCN.", "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": "AuEdzyW97O", "reviewer": "Reviewer_LzeD", "summary": "This paper addresses OOD generalization in node-level graph neural networks. The authors theoretically analyze why popular invariant learning methods like IRM and VREx fail on graph data, and propose two novel solutions: CIA and its environment-label-free variant, CIA-LRA. These methods enforce intra-class similarities to improve OOD generalization. The authors provide theoretical guarantees, including an OOD generalization error bound under the PAC-Bayesian framework. Experimental results on graph OOD benchmarks demonstrate the effectiveness of the proposed methods, particularly CIA-LRA, in improving node-level OOD generalization performance.", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a comprehensive theoretical investigation into why existing invariant learning methods struggle with graph data, supported by formal proofs.\n2. The proposed CIA and CIA-LRA methods offer innovative approaches to tackle node-level OOD generalization, addressing limitations of previous methods.\n3. The authors conduct comprehensive experiments on multiple datasets and compare against various baselines, demonstrating consistent performance improvements.", "weaknesses": "1. Limited comparison to recent node-level OOD method [1].\n2. Lack of visualization of the overall method architecture to help readers understand intuitively.\n3. While Appendix J briefly mentions GPU requirements, a more detailed analysis of the computational complexity and runtime comparisons of CIA and CIA-LRA against baselines would be valuable.\n4. Insufficient citations of recent methods, such as [2] [3].\n\n[1] Learning invariant representations of graph neural networks via cluster generalization\n\n[2] Joint Learning of Label and Environment Causal Independence for Graph Out-of-Distribution Generalization\n\n[3] Individual and structural graph information bottlenecks for out-of-distribution generalization", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer LzeD for your careful reading and detailed comments! We'd like to address your concerns in the following points:\n\n****\n\nQ1: **Limited comparison to recent node-level OOD method [1].**\n\nA1: We've added the evaluation of **CIT** [1], the results are in Table B of the rebuttal PDF. We use the default hyperparameter setting for CIT from the code provided by the authors of [1]. **CIA-LRA outperforms CIT on all splits.**\n\nQ2: **Lack of visualization of the overall method architecture to help readers understand intuitively.**\n\nA2: We've added a figure to better illustrate the overall framework of CIA-LRA, please refer to Fig. A in the rebuttal PDF file. \n\nQ3: **a more detailed analysis of the computational complexity and runtime comparisons of CIA and CIA-LRA against baselines would be valuable.**\n\nA3: We show the time cost to reach the best test accuracy on our largest dataset Arxiv (with 50k~60k nodes) in Table C below. On smaller datasets (Cora, WebKB, CBAS), the running time gap is small and negligible (all methods including CIA-LRA only cost less than 60s to reach the best performance). Table C shows that the time costs of CIA-LRA and CIA are comparable to baseline methods. \n\nTable C: Time cost (seconds) to achieve optimal test performance on Arxiv using GAT on a single RTX 3090 GPU. \n\n|                        | ERM  | Coral | Mixup | EERM | SRGNN | GTrans | CIT  | CIA  | CIA-LRA, hop=6 |\n| ---------------------- | ---- | ----- | ----- | ---- | ----- | ------ | ---- | ---- | -------------- |\n| Arxiv degree covariate | 74   | 551   | 758   | OOM  | 34887 | OOM    | OOM  | 1409 | 1248           |\n| Arxiv degree concept   | 30   | 360   | 747   | OOM  | 3960  | OOM    | OOM  | 155  | 1132           |\n| Arxiv time covariate   | 46   | 246   | 1207  | OOM  | 1993  | OOM    | OOM  | 1428 | 292            |\n| Arxiv time concept     | 440  | 1481  | 272   | OOM  | 11628 | OOM    | OOM  | 221  | 989            |\n\nQ4: **Insufficient citations of recent methods, such as [2] [3].**\n\nA4: Thank you for pointing out the missing related works. \n\n[2] address the graph-level OOD generalization. Their task settings differ from ours in two aspects: 1) They focus on covariate shift, so they enforce $Y\\\\perp G_s$ which doesn't hold for concept shifts. However, our proposed CIA and CIA-LRA work for both covariate and concept shifts. 2) They assume the availability of environment labels while our work tackles invariant learning without environment labels.\n\n[3] address both the graph-level and node-level OOD generalization. They proposed to minimize the mutual information (MI) between the input graph and its representations to eliminate spurious features and maximize the MI between the representations and corresponding labels to learn invariant features. However, their method lacks rigorous analysis of how it can achieve the above two goals. Additionally, their setting is also different from ours: [3] assumes the availability of multiple graphs, while our work focuses the learning on a single graph.", "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": "nLNP6iqTaN", "reviewer": "Reviewer_yNy3", "summary": "The paper investigate the failure case of IRMv1 and VRex for graph data, and develop a novel approach CIA for node-level OOD generalization.  To adapt for the scenarios without environment labels, the authors propose CIA-LRA for the datasets without environment labels.", "questions": "1. CIA-LRA learns masked subgraph, is the experiment inductive or transductive?\n\n2. In line 318-321, why CIA will be less performant than CIA-LRA, it seems not reasonable, as CIA will adopt environment labels while CIA-LRA doesn’t. \n\n3. $\\theta_m$ is separated from $\\theta$, how to ensure it will learn the invariant subgraph, under what assumptions?", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The paper is well-written and provides clear motivation.\n\n2. The paper is solid in both theoretical and empirical aspects.\n\n3. The evaluations are fair and convincing.", "weaknesses": "1. The author may want to clarify the reasoning behind the two SCMs corresponding to the two types of distribution shifts, as this connection is not entirely clear.\n\n2. In Equation 9, it should be $\\phi_\\theta(j)$.\n\n3. Assuming the sample label corresponds to the same invariant factors, it is unclear why $r_{\\text{same}}$ is necessary for reweighting.\n\n4. It appears that CIA-LRA requires all labels for reweighting alignment. However, the typical node-level classification setting is semi-supervised, which limits the applicability of this method.\n\n5. Line 231: \"to pairs with\" should be corrected to \"to pair with\".\n\n6. Line 854: In the proof of the non-graph case, $(A^e)^k$ appears, which seems to be an oversight.\n\n7. The general idea of sampling nodes from the same target label and different environments is similar to CIGA [1], which performs supervised contrastive learning to identify invariant subgraphs. The objective in CIGA may be a specific form of $d(\\cdot)$. The authors may want to compare and contrast their approach with CIGA.\n\n\n__reference__\n\n[1] Chen et al., Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs, Neurips 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer yNy3 for your careful reading and detailed comments! We'd like to address your concerns in the following points:\n\n****\n\nQ1: **The author may want to clarify the reasoning behind the two SCMs corresponding to the two types of distribution shifts, as this connection is not entirely clear**\n\nA1: Here we'd like to clarify the connection between the SCMs and the two type of distributional shifts. \n\nDefinitions of the two shifts: \n\nConcept shift: $p_{Y|S}(y|s)$ changes across environments, and $p_X(x)$ is invariant across environments; Covariate shift: $p_X(x)$ changes across environments,   and $p_{Y|S}(y|s)$ is invariant across environments.\n\nConcept shift and Fig. 1(a): Suppose $X=f(C, S)$. In Fig. 1(a), $S$ is the direct cause of $Y$ and the mapping from $Y$ to $S$ is affected by environments $E$. This means $p_{S|Y}(s|y)$ changes across environments. Now we show that this makes $p_{Y|X}(y|x)$ varies with environments.   $p_{Y|X}(y|x)=\\\\frac{p_{X,Y}(x, y)}{p_X(x)}=\\\\frac{\\\\sum_{c, s: x=f(c, s)} p_{Y \\\\mid C, S}(y \\\\mid c, s) \\\\cdot p_{C, S}(c, s)}{p_X(x)}\n$. Taking out the $p_{Y \\\\mid C, S}(y \\\\mid c, s)$ in the molecule, we have $p_{Y \\\\mid C, S}(y \\\\mid c, s)=\\\\frac{p_{S|Y}(s|y)p_{C|Y}(c|y)p_Y(y)}{p_{C,S}(c,s)}$. Since $p_{S|Y}(s|y)$ varies with environments, we conclude that $p_{Y|X}(y|x)$ is also variant, which matches the definition of the concept shift.\n\nCovariate shift and Fig. 1(b): In Fig. 1(b), $S$ is independent of $Y$ and only depends on $E$, which means $p_{Y|X}(y|x)$ is invariant across environments. Additionally, $p_X(x)=\\\\sum_{c,s}p_{X|C,S}(x|c,s)p_{C,S}(c, s)=\\\\sum_{c,s:x=f(c,s)}p_{C,S}(c,s)=\\\\sum_{c,s:x=f(c,s)}p_{C|S}(c|s)p_{S}(s)$. According to Fig. 1(b), $S$ is the direct cause of $E$ so $p_{S}(s)$ changes with environments. Hence, we conclude that $p_X(x)$ changes with environments, which matches the definition of the covariate shift.\n\nQ2: **Assuming the same label corresponds to the same invariant factors, it is unclear why $r^{same}$ is necessary for reweighting.**\n\nA2: In practice, although the causal features of the same class are basically invariant across environments, they still show slight deviation among the samples within this class (shown in Fig. 7-10), and this intra-class discrepancy in invariant features has a positive correlation with the difference in same-class neighborhood label distribution (evidence in Fig. 15). Hence, we design $r^{same}$ to prevent the over alignment that may cause the collapse of the invariant features. Table 4 and Fig. 2 reveal the positive role of $r^{same}$. \n\nNote that the main purpose of this assumption is for the ease of theoretical analysis. However, this assumption is also acceptable in practice, supported by two pieces of evidence: 1) CIA improves over most non-graph-specific baselines 2) In Table 4, merely removing $r^{same}$ (63.91) from CIA-LRA still outperforms IRM (61.14) and VREx (61.32).\n\nQ3:  **the typical node-level classification setting is semi-supervised, which limits the applicability of this method.**\n\nA3: Our experiments are exactly conducted in a semi-supervised setting in which only 30%~40% of nodes are labeled. CIA-LRA only operates on the labeled data to gain improvements.\n\nQ4: **The authors may want to compare and contrast their approach with CIGA.**\n\nA4: Differences between CIA-LRA and CIGA: \n\n* CIGA cannot solve covariate shifts. CIGAv2 maximizes the mutual information between the estimated spurious subgraph $\\\\hat{G_s}$ and labels $I(\\\\hat{G_s};Y)$ to reduce including part of $\\\\hat{G_s}$ into the true invariant graph $G_c$. For covariate shifts, $G_s$ contains no information about $Y$, thus $\\\\max I(\\\\hat{G_s};Y)$ may not capture the correct $G_s$. Therefore, the estimation of the invariant subgraph $\\\\hat{G_c}=G-\\\\hat{G_s}$ will be also inaccurate.\n* CIA-LRA works for both shifts. Our strategy doesn't rely on the concept shift assumption to minimize the OOD error. There are two main reasons. First, under covariate shifts, CIA-LRA removes environment-related spurious node features when the selected pairs potentially come from different environments. Second, CIA-LRA can simultaneously reduce the error caused by structural shifts of heterophilic neighborhood label distribution (the term (c) in the error bound in Theorem 4.2 can be minimized by CIA-LRA regardless of the type of the distributional shifts). \n\nQ5: **CIA-LRA learns masked subgraph, is the experiment inductive or transductive?**\n\nA5: All four datasets of our experiments are transductive. \n\nQ6: **In line 318-321, why CIA will be less performant than CIA-LRA, it seems not reasonable, as CIA will adopt environment labels while CIA-LRA doesn’t.**\n\nA6: The role of environment labels is to distinguish spurious features so that the they can be eliminated by cross-environment alignment. However, even if spurious features are removed (Fig. 2 right, CIA), learning a collapse representation of invariant features can also hurt generalization (shown in Fig. 2 Left and Mid, CIA). Although CIA-LRA doesn't use environment labels, it can remove spurious features by intra-class alignment and the proposed $r^{diff}$ (see Fig. 2 right, CIA-LRA and term (b) (c) in Theorem 4.2). Moreover, it avoids the collapse of invariant features caused by overalignment by only aligning local pairs and using $r^{same}$  (Fig. 2 Mid, CIA-LRA). Therefore, CIA-LRA outperforms CIA even without environment labels.\n\nQ7: **$\\\\theta_m$ is separated from $\\\\theta$, how to ensure it will learn the invariant subgraph, under what assumptions?**\n\nA7: We are sorry that we did not fully understand which parameter in Eq. (3) the \"$\\\\theta_m$\" you mentioned here refers to. We'd like to address any of your further questions.\n\nQ8: **typos**\n\nA8: Thank you for carefully identifying all typos! and we have fixed all typos you mentioned: \n\n* Eq. (9): $\\\\phi(i)\\\\rightarrow \\\\phi(j)$\n* Line 231: \"to pairs with\" $\\\\rightarrow$ \"to pair with\".\n* Line 854: Removed ${\\\\tilde{A}^e}^k$", "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": "vHTAULpvw0", "reviewer": "Reviewer_nx4e", "summary": "The authors propose a novel regularization and alignment mechanism for invariant graph learning with the goal of obtaining better out-of-distribution (OOD) generalization.  Besides proving that existing methods tackling OOD generalization in other domains do not transfer to graphs, they propose CIA (environment-label dependent) and CIA-LRA (environment-label independent) to tackle the challenge of OOD generalization on graph data. Both, theoretical and empirical evidence is provided showing that the proposed methods provide benefits in OOD generalization.", "questions": "- how often did you repeat the experiments? (Maybe it's written somewhere and I didn't see it)", "limitations": "- major parts of the analysis are rather limited as they rely on the definition of the GNN in Eq. 3 which is a linear model\n- a comparison to some more recent baseline would increase the value of the paper", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- theoretical derivation of failure of IRM and VREx on graph data\n- theoretical analysis of CIA an CIA-LRA\n- empirical evidence that the proposed methods achieve OOD generalization significantly better than IRM and VREx\n- detailed discussion of further findings and proofs in appendix", "weaknesses": "## Methodology\n- in Fig. 1 it is not clearly described what the variables exactly refer to (e.g. $G$ is not mentioned in the text)\n- while I appreciate the theoretical findings, the GNN defined in Eq. 3 is a linear model, hence the theoretical analysis is somewhat limited. However, one should keep in mind that the analysis of non-linear and highly complex networks is hard\n- line 204: it is a bit counter-intuitive why invariant node features of nodes with the same class should significantly diverge when they are far apart in the graph. Also the empirical evidence in Fig. 7/8 does not really support this statement.\n- a brief definition/discussion of concept shift and covariate shift would be beneficial for clarity\n- in line 232: why is a sum operator employed here instead of a mean? Won't a simple sum be highly influenced by the graph size and connectivity/density?\n- line 248: inconsistent naming ($x_{cau}$ and $x_{inv}$)\n- in theorem 4.2 it is unclear what $\\alpha$ is and what the inequation $0 < \\alpha < \\frac{1}{4}$ means. Further a bit of a discussion on the goodness/tightness of the given bound would be good to assess the usefulness of that bound\n- proof G 1.1.: the proof only shows that $\\theta_2 = 0$ is **a possible** solution, but not a unique solution, isn't it? (Didn't check the proofs too deeply though)\n- Eq. 34:  the entire term does not depend on $\\theta_2$, so it is unclear to me why $\\theta_2 = 0$ is **the** solution to that equation. Wouldn't any arbitrary value be a valid solution then?\n- Eq. 35: in App. F.1 it is stated that the expectation of $\\epsilon^e$ is 0. Looking at Eq. 35, won't all mutliplicative terms entailing $\\epsilon^e$ cancel out in the expectation and thus in the IRM loss? This would make the IRM loss independent of the environment **in expectation** (not for some specific environment though). Thus, I don't see how the conclusion is reached that the IRM loss depends on $\\epsilon^e$ if, in expectation, it is 0.\n- line 995: which property are you referring to exactly?\n\n## Experiments\n- since the authors present an alignment-based invariant learning strategy for graph data, it would be good to see some more recent baselines taking a similar approach such as [1] and [2]\n- line 296: why does CIA-LRA improve upon CIA? To me it is counter-intuitive since CIA-LRA has no access to the environment labels, thus I'd expect this task to be harder\n\n## General notes\n- in the Introduction there should be more on related methods based on representation alignment such as [1] and [2]\n\n## References\n[1] Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training Data. Zhu et al. NeurIPS 2021.\n\n[2] Stable Prediction on Graphs with Agnostic Distribution Shifts. Zahng et al. KDD 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer nx4e for your careful reading and detailed comments! We'd like to address your concerns in the following points:\n\n****\n\nQ1: **G in Fig. 1 is not mentioned in the text**\n\nA1: Sorry for the lack of clarity. $G$ refers to the graph data.\n\nQ2: **limitation: the definition of the GNN in Eq. 3 which is a linear model**\n\nA2: Justifications for analyzing a linear model: 1) Some recent works [8] [9] observed that linear GNNs achieve comparable performance to nonlinear GNNs. [5] also theoretically proved that SGC can outperform GCN under some mild assumptions.  2) many recent works on the theoretical analysis of graphs/OOD generalization adopt linear networks ([4] [10] [11]). 3) Our theory matches the experimental results on the nonlinear GCN and GAT that CIA outperforms IRM and VREx.\n\nQ3: **line 204: it is a bit counter-intuitive why invariant node features of nodes with the same class should significantly diverge when they are far apart in the graph.**\n\nA3: Although the invariant features of the same class are basically invariant across environments, they still show some slight intra-class deviation (see Fig. 7-10). In the same class, the invariant feature difference between nodes that are farther apart is larger than the difference between nodes that are closer together. In Fig. 7/8, despite the curve's slight fluctuations, the invariant feature difference shows a clear positive correlation with the distance from the starting point.\n\nQ4: **a brief definition/discussion of concept and covariate shift would be beneficial for clarity**\n\nA4: Due to word limitation, we invite you to refer to the A1 to the reviewer yNy3.\n\nQ5: **in line 232: why is a sum operator employed here instead of a mean?**\n\nA5: We employ a 'sum' in line 232 because $r_i^c$ is the **ratio** of nodes of class $c$ in the $L$-hop neighborhood, which has already been normalized by the size of the neighborhood. It won't be affected by the graph size/connectivity.\n\nQ6: **in theorem 4.2 it is unclear what $\\\\alpha$ is and what the inequation $0<\\\\alpha<\\\\frac{1}{4}$ means. Discussion on the goodness/tightness of the given bound?**\n\nA6: Sorry again for the lack of clarity. $\\\\alpha$ is defined in Assumption 3 of [6]: \"...... Assume that there exists some $0<\\\\alpha<\\\\frac{1}{4}$ satisfying $$\\\\operatorname{Pr}_{h \\\\sim P}\\\\left(\\\\mathcal{L}_m^{\\\\gamma / 4}(h)-\\\\mathcal{L}_0^{\\\\gamma / 2}(h)>N_0^{-\\\\alpha}+c K \\\\epsilon_m \\\\left\\\\lvert\\\\, T_h^L \\\\epsilon_m>\\\\frac{\\\\gamma}{8}\\\\right.\\\\right) \\\\leq e^{-N_0^{2 \\\\alpha}}$$\". This assumption is needed for proving Lemma 6 in [6], which we rely on to prove of Lemma G.11 in our paper. \n\n* Tightness of Theorem 4.2: when there are no distributional shifts in spurious node features and heterophilic neighborhood distribution between training and test environments, the terms (a)-(d) in Eq. 109 becomes zero, and the upper bound becomes $\\\\widehat{\\\\mathcal{L}}\\_{e^{\\\\text{tr}}}^\\\\gamma(\\\\tilde{h})+const=\\\\widehat{\\\\mathcal{L}}\\_{e^{\\\\text{tr}}}^\\\\gamma(\\\\tilde{h})+\\\\frac{1}{N_0^{1-2 \\\\alpha}}+\\\\frac{1}{N_0^{2 \\\\alpha}} \\\\ln \\\\frac{L C\\\\left(2 B_{e^{\\\\text{te}}}\\\\right)^{1 / L}}{\\\\gamma^{1 / L} \\\\delta}$, i.e., our bound only larger than the ideal error $\\\\widehat{\\\\mathcal{L}}_{e^{\\\\text{tr}}}^\\\\gamma(\\\\tilde{h})$ by a constant $const$. When the number of training samples $N_0$ is large, $const$ will be small enough and can be negligible. Hence, the tightness of our bound is guaranteed.\n\nQ7: **proof G 1.1.: the proof only shows that $\\\\theta_2=0$ is a possible solution, but not a unique solution, isn't it?**\n\nNo. $\\\\theta_2=0$ is a unique solution. Please see lines 855-861, line 868.\n\nQ8: **Eq. 34: the entire term does not depend on $\\\\theta_2$, so it is unclear why $\\\\theta_2$ is the solution to that equation. **\n\nA8: Eq. (34) is the result of plugging $\\\\theta_2=0$ into the expression $\\\\frac{\\\\partial\\\\mathbb{V}_e[R(e)]}{\\\\partial \\\\theta_2}$, thus $\\\\theta_2$ disappears. \n\nQ9: **won't all mutliplicative terms entailing $\\\\epsilon^e$ cancel out in the expectation?**\n\nA9: Although $\\\\mathbb{E}_e[\\\\epsilon^e]=0$, but $\\\\mathbb{E}_e[{\\\\epsilon^e}^\\\\top\\\\epsilon^e]=N_e\\\\sigma^2>0$, where $\\\\sigma^2=\\\\mathbb{V}_e[\\\\epsilon^e_i],~i=1,...,N_e$. So the terms multiplied by ${\\\\epsilon^e}^\\\\top\\\\epsilon^e$ won't be canceled out.\n\nQ10: **line 995: which property are you referring to exactly?**\n\nA10: For two vectors $a$ and $b$ ($a\\\\neq \\\\lambda b$, $\\\\lambda$ is any scalar), we have $|a\\\\cdot b|^2 \\\\leq |a|^2|b|^2$. \n\nQ11: **it would be good to see some more recent baselines such as [1] and [2]**\n\nA11: We have already included [1] (SRGNN) in our main experiment in Table 2 of the orginal paper. We didn't compare with [2] since it requires the graphs of different environments to have the same nodes but our datasets don't satisfy this. However, we add two more recent graph OOD methods **CIT** ([7] suggested by reviewer LzeD) and **CaNet** ([12] suggested by reviewer empj) as baselines. Please see Table B of the rebuttal PDF. **CIA-LRA outperforms CIT and CaNet on all splits.**\n\nQ12: **line 296: why does CIA-LRA improve upon CIA? It is counter-intuitive since CIA-LRA has no access to the environment labels**\n\nA12: We also invite you to refer to A6 to the reviewer yNy3.\n\nQ13: **missing related works**\n\nA13: We've already discussed [1] in Appendix A.3. Here we discuss [2]. [2] proposed to align the aggregation weights of the same edge across environments (\"locally stable learning\") and align the cross-environment loss (\"global stable learning\"). There are some drawbacks. First, the \"locally stable learning\" requires the graphs from different environments to have the same nodes and topological structures, which is impractical; second, the \"global stable learning\" is actually a VREx loss that we proved to have failure cases in node-level OOD tasks.\n\nQ14: **repeating experiments & typos**\n\nA14: We repeat our experiments with **three** different random seeds. We have fixed all typos you mentioned.", "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:
We list the references of our rebuttal here (We start numbering from [4] to avoid conflicts with the numbering used by some reviewers):

[4] Spurious Feature Diversification Improves Out-of-distribution Generalization (ICLR 2024)

[5] Towards Understanding Generalization of Graph Neural Networks (ICML 2023)

[6] Subgroup Generalization and Fairness of Graph Neural Networks (NeurIPS 2021)

[7] Learning invariant representations of graph neural networks via cluster generalization (NeurIPS 2023)

[8] Simple spectral graph convolution (ICLR 2021)

[9] Dissecting the diffusion process in linear graph convolutional networks. (NeurIPS 2021)

[10] A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks (ICLR 2023)

[11] Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All? (NeurIPS 2023)

[12] Graph Out-of-Distribution Generalization via Causal Intervention (WWW 2024)



The contents of the rebuttal PDF:

* add an illustration figure of the proposed CIA-LRA framework 
* add **MatchDG** (suggested by reviewer LzeD), **CIT** ([7] suggested by reviewer LzeD), and **CaNet** ([12] suggested by reviewer empj) as new baselines.

Meta-review: This paper studied the graph OOD problem, which proposes a Cross-environment Intra-class Alignment (CIA) method to learn invariant representations. The paper provides a theoretical analysis on the failure of IRM and VERx on graph data, and the proposed method is derived from the theoretical results. Extensive results clear validate the effectiveness of the proposed method on node-level graph OOD task. Most of concerns of reviewers have been well solved through rebuttal. I believe this manuscript is ready to publish.
Decision: Accept (poster)