Learning Invariant Graph Representations for Out-of-Distribution Generalization
Authors: Haoyang Li
Ziwei Zhang
Xin Wang
Wenwu Zhu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Representation Learning
Graph Neural Network
Out-of-Distribution Generalization

Abstract: Graph representation learning has shown effectiveness when testing and training graph data come from the same distribution, but most existing approaches fail to generalize under distribution shifts. Invariant learning, backed by the invariance principle from causality, can achieve guaranteed generalization under distribution shifts in theory and has shown great successes in practice. However, invariant learning for graphs under distribution shifts remains unexplored and challenging. To solve this problem, we propose Graph Invariant Learning (GIL) model capable of learning generalized graph representations under distribution shifts. Our proposed method can capture the invariant relationships between predictive graph structural information and labels in a mixture of latent environments through jointly optimizing three tailored modules. Specifically, we first design a GNN-based subgraph generator to identify invariant subgraphs. Then we use the variant subgraphs, i.e., complements of invariant subgraphs, to infer the latent environment labels. We further propose an invariant learning module to learn graph representations that can generalize to unknown test graphs. Theoretical justifications for our proposed method are also provided. Extensive experiments on both synthetic and real-world datasets demonstrate the superiority of our method against state-of-the-art baselines under distribution shifts for the graph classification task. 

Learning Invariant Graph Representations for Out-of-Distribution Generalization
Haoyang Li, Ziwei Zhang, Xin Wang, Wenwu Zhu*
Tsinghua University
lihy188mails wastgaghhiisssstsaataaaa tsinghua.... edu en, (zwzhang, xin_wang, wwzhu)@tsinghua edu.
Abstract
Graph representation learning has shown effectiveness when testing and training graph data come from the same distribution, but most existing approaches fail generalize under distribution shifts. Invariant learning, backed by the invariance principle from causality, can achieve guaranteed generalization under distribution shifts in theory and has shown great successes in practice. However, invariant learn- ing for graphs under distribution shifts remains unexplored and challenging. To solve this problem, we propose Graph Invariant Learning (GIL) model capable of learning generalized graph representations under distribution shifts. Our proposed method capture the invariant relationships between predictive graph structural information and labels mixture of latent environments through jointly optimiz- ing three tailored modules. Specifically, first design GNN-based subgraph generator to identify invariant subgraphs. Then we use the variant subgraphs, i.e., complements of invariant subgraphs, to infer the latent environment labels. We further propose an invariant learning module to learn graph representations that can generalize unknown graphs. Theoretical justifications for our proposed method are also provided. Extensive experiments on both synthetic and real-world datasets demonstrate the superiority of our method against state-of-the-ar baselines under distribution shifts for the graph classification task.
1 Introduction
Graph structured data is ubiquitous in the real world, e.g., social networks, biology networks, chemical molecules, etc. Graph representation learning, which encodes graphs into vectorized representations, has been the central topic in graph machine learning in the last decade. For example, graph neural networks (GNNs) [ design end-to-end learning schemes to extract useful graph information and are shown be successful in variety of applications.
Despite the enormous success, the existing approaches for learning graph representations heavily rely on the I.I.D assumption, i.e., the testing and training graph data are independently drawn from an identical distribution. However, distribution shifts of graph data widely exist in real-world scenarios and are usually inevitable due the uncontrollable underlying data generation mechanism [4]. Most existing approaches fail to generalize to out-of-distributio (OOD) testing graph data. One critical bottleneck is that the existing methods ignore the invariant graph patterns and tend rely on correlations that are variant for graphs from different environments. Therefore, it is of paramount significance to learn graph representations under distribution shifts and develop methods capable of out-of-distrine ditto--distribution (OOD) generalization. Such studies are particularly critical for high-stake graph applications such as medical diagnosis (5), financial analysis ( molecular prediction (7). etc.
In this work, we propose a brand new methodology to learn invariant graph representation under distribution shifts. Invariant learning, which aims exploit the invariant relationships between
"Corresponding authors
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

features and labels across different distributions while disregarding the variant spurious correlations, can provably achieve satisfactory OOD generalization under distribution shifts [ Though invariant learning has been studied for images and texts [ I1 it remains largely unexplored in
the literature of graph representation learning. However, invariant graph representation learning is non-trivial due to the following challenges. First, graph data usually comes from mixture of latent
environments without accurate environment la- bels, shown in Figure Since most invariant methods require multiple training environments with explicit environment labels, these existing methods cannot be directly applied to graphs. Second, the formation process of graphs is af- fected by the complex interaction of both invari- ant and variant patterns. How identify the invariant patterns among latent environments is even more challenging. Last but not least, even after having obtained the environmental labels, how to design a theoretically grounded learning scheme to generate graph representations capable of OOD generalization remains largely unexplored.
Labels
Training Sat
Prediction
cycle
Lateet
Testing Sot
Poor Pradiction
Figure 1: An example of distribution shifts under mixture of latent environments, which leads to poor generalization.
To tackle these challenges, in this paper, we propose Graph Invariant Learning method (GIL) which is able to capture invariant graph patterns in a mixture of latent environments and capable of OOD generalization under distribution shifts. As shown in Figure 2 our proposed method can capture the invariant relationships between predictive graph structural information and labels in mixture of latent environments through jointly optimizing three mutually promoting modules, with each module tackling one aforementioned challenge. Specifically, in the invariant subgraph identification module, we design a GNN-based subgraph generator to identify potentially invariant subgraphs from the complex interaction between invariant and variant patterns. Then, we use the variant sub- graphs, i.e., the complement of invariant subgraphs, to infer environment labels by clustering these ietrromment-dicciiinaaee
features. The variant subgraphs capture variant correlations under differ- ent distributions and therefore contain informative features to infer environment labels. Lastly, in the invariant learning module, we propose to optimize the maximal invariant subgraph generator criterion given the identified invariant subgraphs and inferred environments to generate graph representations capable of OOD generalization under distribution shifts. We theoretically show that the OOD gener- alization problem on graphs can be formulated as finding a maximal invariant subgraph generator of our GIL, and further prove that our GIL satisfies permutation invariance. We conduct extensive experiments on both synthetic graph datasets and real graph benchmarks for the graph classification task. The results show that the representations learned from GIL achieve substantial performance gains on the unseen OOD testing graphs compared with various state-of-the-an art baselines.
Our contributions are summarized follows.
We propose novel Graph Invariant Learning method (GIL) to learn invariant and OOD generalized graph representations under distribution shifts. To the best of our knowledge, we are the first to study invariant learning for graph representation learning under mixture of latent environments.
Our proposed method can automatically infer the environment label of graphs from a mixture of latent environments without supervision.
We propose maximal invariant subgraph generator criterion to learn graph representations capable of OOD generalization under distribution shifts.
We theoretically show that finding maximal invariant subgraph generator of GIL can solve the OOD generalization problem. Extensive empirical results demonstrate the effectiveness of GIL on various synthetic and benchmark datasets under distribution shifts.
2 Notations and Problem Formulation
N Notations. Let G and Y be the graph and label space. We consider graph dataset G [(G,, Y)) /== where G; E G and Y, E W. Following the OOD convention [1] g
9 we assume the dataset is col- lected from multiple training environments, i.c., g = {g") )eEsupp(((E)))) where G = {GG), Y; ==1 denotes the dataset from environment e, supp(Etr) is the support of the environmental variable the training data. We use G and Y to denote the random variables of graph and label, and G and Y to

---

Lateni endironments
000
Invariant Subgraph Identification
Environment Inference
(D(+)
Cluster varlant subgraphs [Gy) infor environments
5L" cu"
Labels: V
Greph delaoe!
subgrashs (Gy]
Lackeer
Wheol
Informed enviionments
Training Dataset
GNN
Invariant Learning
Ladber
Mu Rann 2
Edig Mank
Giophs frmm modure bebed anvimemmente
Hungraphe (fr)
Elunee
Shared
Emsper
Ay
bistrbbtion shilts
Inveriat& & varant si higgpet (6: (6)
assiiication lods
Testing Dataset 4.
++
mmariann
Objective function
(
W o g(
Prediction
(G) w g (G)
Figure 2: The framework of GIL model. Our proposed method jointly optimizes three modules: (1) In the invariant subgraph identification module, GNN-based subgraph generator ((-) identifies the invariant subgraph Gr and the variant subgraph Gv. (2) The environment inference module uses the variant subgraphs {Gy} } to infer the latent environments by clustering the representations of {Gv }. (3) The invariant learning module jointly optimizes the invariant subgraph generator Φ(-), the representation learning function g(-). and the classifier w(-). Training stage (shown by grey arrows): we back propagate with the objective function to update model parameters. Testing stage (shown by green arrows): we use the optimized model to make predictions.
specify random variables from environment e. The environment label for graphs unobserved since it is prohibitively expensive to collect graph environment labels for most real scenarios.
Problem Formulation. We formulate the generalization under distribution shifts on graphs as:
Problem 1. Let denote the random variable indices of all possible environments. Our goal is to find an optimal predictor (-): G + V that performs well on all environments:
(-))) argmin sup R(fle), eesupplE)
(1)
where Risle) = (UU)) Y]] is the risk of the predictor f on the environment e, and E(.,
Y x Y R denotes a loss function. We further decompose f(-) w h, where h(-) G Rd is
the representation learning function, d is the dimensionality, and w(-) .Rd +Y is the classifier.
Note that supp(E(r) C supp(E). Besides, distribution shifts indicate that Pe Y) # pe' (G, Y). E supp(Etr), E supp(E) supp(E,r), i.e., the joint distribution of the graph and the corresponding label is different for training and testing graph data.
Problem is difficult to be solved since supp(E) is unobserved latent g 9 In addition, for most graph datasets, we do not have access to accurate environment labels or environment partitions. Therefore, focus on jointly inferring the environments of the graph dataset and achieving good OOD generalization performance under the inferred environments. The problem is formulated as:
Given a graph dataset G collected from a mixture of latent environments but without environment labels, the task is jointly infer graph environments Einfer, i.e., ( (essuppp)) and learn graph predictor f (-) in Problem under the inferred environments Einfer achieve good OOD generalization performance.
Problem 2.
3 Method
In this section, we introduce our proposed method in detail, whose framework is shown in Figure 2 We first present the invariant subgraph identification module. Then, we infer environment labels by clustering the variant subgraphs. Next, we introduce the maximal invariant subgraph generator criterion to generate graph representations which can generalize to test graphs under distribution shifts. Lastly, provide some discussions of our proposed method.
3

---

3.1 Invariant Subgraph Identification
We assume that each input graph G E G has an invariant subgraph G2 C so that its relationship with the label is invariant across different environments. We refer the rest of the graph, i.e., the complement of G₁, as the variant subgraph and denote it as Gv. Gy represents the graph part whose relationship with the label is variant across different environments, e.g., spurious correlations. Therefore, the model will have a better OOD generalization ability if it can identify the invariant subgraph and only uses structural information from G₁.
We denote a generator to obtain the invariant subgraph as G, = (G)). Following the invariant learning literature [2], we make an assumption (G) as follows:
Assumption 3.1. Given G, there exists an optimal invariant subgraph generator 4 (G) satisfying:
Invariance property: Ve, e' E Supp(E), P P*(Y( p (Y)+
b. Sufficiency property: Y w ("" (G)) + c G, where g (.) denotes representation learning function, w* is the classifter, 1 indicates statistical independence, and is random noise.
The invariance assumption means that there exists a subgraph generator such that it can generate invariant subgraphs across different environments. The sufficiency assumption means that the generated invariant subgraphs should have sufficient predictive abilities predicting the graph labels.
Under this assumption, we instantiate (-()) with learnable parameters. Consider an input graph instance G with nodes. The corresponding adjacency matrix is denoted A {0. 1)mx",, where
A.j 1 represents that there exists an edge between node i and j, and Ai, = 0 otherwise. To split the input graph G' into G2 and Gv, a common strategy use a binary mask matrix M = (0, 1) ] on the adjacency matrix A. However, directly optimizing a discrete matrix M is intractable G has exponentially many subgraph candidates [13. Besides, learning M for each graph separately hinders the method from handling unseen test graphs [14.. Therefore, we adopt shared learnable GNN (denoted as GNNM) to generate soft mask matrix M Rexn as follows:
M.j
Z (m)
z (m))
GNN GNNM(G). (G),
(2)
where ((m) is the node representation. Then, we obtain the invariant and variant subgraphs as:
A Top, (M O Ay Ar.
A
where A and Av denotes the adjacency matrix of G, and Gy, respectively, @ means the element- wise matrix multiplication, and (.), selects the top 1-percentage of elements with the largest values. The parameters of GNNM are trained on all available graphs to generate the corresponding Gj and Gy. Using the inductive learning ability of GNNs, it can also be used to unseen test graphs, as opposed to directly optimizing mask matrices.
3.2 Environment Inference
After obtaining the invariant and variant subgraphs, infer the environment label Ein The intuition is that since the invariant subgraph captures invariant relationships between predictive graph structural information and labels, the variant subgraphs in turn capture variant correlations under different distributions, which are environment-discriiinnn variant subgraphs infer the latent environments. We adopt another GNN encoder, whose parameters are also shared among different graphs, to generate the representation of the variant subgraph Gy:
features. Therefore, we can use the
Zv GNN (Gv), hv = READOUT (Zvv)
(4)
where READOUT is permutationninnariian readout function that aggregates node-level representa- tion Zy into graph-level representation hy. The representation of all the variant subgraphs denoted as H = [hy,..... h. After obtaining H, we use an off- -hel- clustering algorithm to infer the environment label Ein/er- In this paper, we adopt k-means [5 as our clustering algorithm:
Em.eer k-means(HH H)).
(5)
Using Einfer, we can partition the graph dataset into multiple training environments, i.e., G [eE)ppppp(EEmee The environment inference module purely unsupervised without needing any ground-truth environment labels.

---

3.3 Invariant Learning
After obtaining the inferred invariant subgraphs and environment labels, we propose the invariant learning module which can generate OOD generalized graph representations under distribution shifts.
Recall that both the invariant subgraph identification module and environment inference module heavily depend on the generator Ob Therefore, we aim to learn the optimal generator 4' in Assump- tion 3.1 by proposing and optimizing the maximal invariant subgraph generator criterion. First, following the invariant learning literature (9), we give the following definition.
Definition 1. The invariant subgraph generator set I with respect to & is defined as:
It (+(+) PS (=(Y)((()) pd (Y (D(G),, e, E supp(E))-
(6)
Then, we show that the optimal generator 4* satisfies the following theorem.
Theorem 3.2. A generator (G) is the optimal generator that satisfies Assumption 3.1 if and only if it is the maximal invariant subgraph generator, i.e.,
arg max T (Y:4(G)) WEIg
(7)
where [(:-) is the mutual information between the label and the generated subgraph.
The proof is provided in Appendix. Eq. 7 provides us objective function optimize the subgraph generator. However, directly solving Eq. for a non-linear & is difficult [9]. Following the invariant learning literature (9), transform Eq. into invariance regularizer:
Feesupp(Einge..) RD (f(G). Y;0) + >trace(Vare (Vo (VoR")),
(8)
where f()) = w o I o $, Einfer is the infered environment label, and denotes all the learnable parameters. Recall that g(-) is the representation learning function of the invariant subgraphs and wn.) is the classifier. We instantiate g as another GNN as follows:
Z, = (CN hy = READOUT (Zz).
Z, and h, are the node-level and graph-level representations of invariant subgraph G,, respectively. w(.) is instantiated as a multilayer perceptron followed by the softmax activation function. By optimizing Eq. (8), we can get our desired generator & and the subgraph representation learning function g(-), which collectively serve as our representation learning method f((),, i.e., h = go o Q.
3.4 Discussions
Training Procedure. We present the pseudocode of GIL in Appendix.
Time Complexity. The time complexity of our GIL is O(EE d d [VI where [V] and |E| denotes the number of nodes and edges, respectively, and d is the dimensionality of the representations. Specif- ically, adopt messsag--pssingg GNNs to instantiate our GNN components, which has complexity of O(LE) + VVld), Since we only need to generate mask for the existing edges in graphs, the time complexity of generating invariant and variant subgraphs and further obtaining their representations d( ).). The time complexity of environment inference is ([ is the batch size, T is the number of iterations for the k-means algorithm, and [Ein denotes the number of inferred environments. The time complexity of the invariance regularizer is O((Emferrd ld?). as the number of parameters for most GNNs is (d2). Since [B], feanfell, and T are small constants, the overall time complexity of GIL is O( d [V) In comparison, the time complexity of other graph representation methods is also O(IE) d + [V]d)). Therefore, the time complexity of our proposed GIL is on par with the existing methods.
where [B]
4 Theoretical Analysis
In this section, we theoretically analyze our GIL model by showing that the maximal invariant subgraph generator can achieve OOD optimal. The proofs are provided in Appendix.
Theorem 4.1. Let th" be the optimal invariant subgraph generator in Assumption Hnd denote the complement as G G\ (G), ie., the corresponding variant subgraph. Then, we can obtain the optimal predictor under distribution shifts, i.e., the solution to Problem 1
as follows:
arg min o g 4² (G) arg min sup R(fle),
(10)
W
eErupp(E)
5

---

if the following conditions hold: (1) (G) 1 (G): and (2) v/ Ig, 3 e' E supp(E) such that P (G, Y) = p (*) Y (G) and p (D(G) (*))))
The theorem shows that we can transform the OOD generalization problem into finding the optimal invariant subgraphs while maintaining the optimality.
We also prove that our GIL satisfies permutation invariance in Appendix.
5
Experiments
In this section, we evaluate the effectiveness of our GIL on both synthetic and real- datasets.
5.1 Experimental Setup
Datasets, We adopt one synthetic dataset with controllable ground-truth environments and four real-world benchmark datasets for the graph classification task.
SP-Motif: Following [13 [6], we generate synthetic dataset where each graph consists of one variant subgraph and one invariant subgraph, i.e., motif. The variant subgraph includes Tree, Ladder, and Wheel (denoted by V 0, 1, 2, respectively) and the invariant subgraph includes Cycle, House, and Crane (denoted by /=0, 1, 2). The ground- truth label Y only depends on the invariant subgraph which is sampled uniformly. The spurious correlation between V and Y is injected by controlling the variant subgraphs distribution as: P(V) Intuitively, r' controls the strength of the spurious correlation. We set to different values in the testing and training set to simulate the distribution shifts.
if V = I and P(V) (1 r)/2 if V &f T.
MNIST-75sp [17] The task is classify each graph that is converted from an image in MNIST [8] into the corresponding handwritten digit. Distribution shifts exist on node features by adding random noises in the testing set.
Graph-SST2 [9]: Each graph is converted from a text sequence. Graphs are split into different sets based on average node degrees to create distribution shifts.
Open Graph Benchmark (OGB) [20]: We consider two datasets, MOLSIDER and MOLHIV. The default split separates structurally different molecules with different scaffolds into different subsets.
We compare our GIL with some representative state-of of-the-art methods. The first group of these methods generates masks graph structures to filter out important subgraphs using different GNNs, including Attention [2), Top-k Pool [21]. SAGPool [22), and ASAP (23). The second group
Baselines.
is invariant learning methods, including standard ERM, GroupDRO 24 IRM 8 V-REx (25).
DIR [6] We also consider a recent interpretable graph learning method GSAT 26 For a fair comparison, we use the same GNN backbone as GIL for the baselines.
The adopted GNNs and READOUT functions including GNN GNNV. GNN!, READOUTY, and READOUT are listed in Appendix. The hyper- parameter À in Eq. (8) is chosen from (10-5, 10-3 10-3,10-111 10- The number of clusters in Eq. (5) is chosen from [2, 4]. They are tuned on the validation set. We report the mean results and standard deviations of five runs. More details on the datasets, baselines and implementations in Appendix.
Optimization and
5.2 Experiments on SP-Motif
Settings. To simulate different degrees of distribution shifts, we vary r in both the training and testing datasets. For the training set, we select Ttrain from {1/3, 0.5, 0.6, 0.7, 0.8. 0.9). A larger Ttrein indicates a higher spurious correlation between Y and Gv in the training set, while Ttrain 1/3 implics that the training set is balanced without any spurious correlation. For the testing set, we consider two settings: (1) Theat 1/3, which simulates that the invariant subgraphs and variant subgraphs are randomly attached without spurious correlations; (2) Ptest = 0.2, which indicates that the testing set has reversed spurious correlations and thus is more challenging.
Quantitative Results. The results are shown in Table I We have the following observations. Our proposed GIL model consistently and significantly outperforms the baselines and achieves the best performance on all settings. The results demonstrate that our proposed method can well handle graph distribution shifts and have remarkable out-of-distributie generalization ability.

---

Table 1: The graph classification accuracy (%) testing sets of the synthetic dataset SP-Motif. In each column, the boldfaced and the underlined score denotes the best and the second- best result, respectively. Numbers in the lower right corner denote standard deviations.
Secuario
1/3
Sccmorio 2:
0.2
F= 1/3
0.5
0.5
0.7
0.5
0.9
1/33
0.5
0.6
0.7
0.8
0.0
ERM
53,00
51,24
47.04
38, 91
57.84
57 57.44
55
41.72
3692
35.72
28.00
19,60eres
Amention
54.3
53.24:33e
42.52.320
35. 2000m
34.08 11
33. 11.88
$4.051435
31.061297
25.72
24,30:409
23:20
18.042235
Top- Pool
54.68.mm
53.12
44.56-245
37,44220
35.24 25.2
54 14.28
45 681316
34.20.43:
31.00:29
30
29
29.1622:5
27.56a25
SAG Pool
54.8831
52,60g355
44.68.311
37.68amm
54.28x:
33.72s1 8
44 35
38.662117
$1.36.481
12.84:155
26.72
25.602517
ASAP
54,00.421
51.92
45.12.158
36.25.a3
34.24.232
34,40:315
29:881400
54.52:435
27.00.281
27.20:235
27.96.119
22.88.433
GroupDRO
53.20
51,40
48.32.555
39.12:427
33 13,001176
37.64.1.9
12.08:433
43.08:415
51.92
34.36:141
28.38:134
20.32:114
IRM
52,00.234
50,00:354
47.84:38
18.80:317
39.84:121
39 39.00:3
50
41.60:435
35.241235
34.92
29.0612.
21.342377
V-KEX
53.16.325
46.04
45.36.30
40.34:1
39,48:130
39 19.12
50.564243
37.16.53
34.52
29.72:451
27.32
24.44cm
DIR
$2.96 L54
$2.08
50.12
49.84124
45. 15.201111
41.241435
50.0815.0
19.96.13
45.4-1cm0
40.561236
39.921455
32.521459
GSAT
53.67 LM/
$3.54
$1.4133
50.12.15
45.831431
14.221537
51.361421
50.48:191
26.9111
43.55
40.25:421
33.8715.11
GIL
55.44-31
34,56:30
53.00
53.12221
51.24:18
46.04:11
54.00:14
52.48.L
5000654:
47.44:330
46.36:330
35.00:54
01
SAG Fa
Test Accuracy (%)
Text Accuracy
Sthouatte Score
Enronments
0.35
60-
Siloouttee Score
Precision@5
50
0.29
40-
0.23
30
0.5
0.6
0.7
0.8
0.9
5 10 15
20 Epoch
25
30
Trrai
Figure 5: The en- vironment inference results when train- ing is finished.
Figure 3: The results of discovering the ground-truth invariant subgraphs on SP-Motif (Ftest 0.2).
Figure 4: The test accuracy and the performance of environment infer- ence over different training periods.
As ltrain grows larger, the performance of all the methods tends to decrease since there exists larger degree of distribution shift. Nevertheless, our proposed method able to maintain the most relatively stable performance. In fact, the performance gap between GIL and the baselines becomes more significant as the degree of distribution shift increases. For example, when Itest 1/3, the accuracy of all baselines drops by more than 7% when Ttrain changes from 0.5 to 0.8, indicating their poor OOD generalization ability. In contrast, our method only has 3% performance drop.
When the degree of distribution shift is relatively small, GNNs with different pooling methods to generate subgraphs generally report better results. On the other hand, when the degree of distribution shift is large, invariant baselines show more stable performance. Among them, DIR, which is a recently proposed invariant method specifically designed for graphs, is one competitive baseline. Nevertheless, our proposed method outperforms DIR by more than 3% in terms of the classification accuracy in most cases. GSAT achieves promising gains over the other baselines, but our GIL still performs better than GSAT. When Itest = Ptrain 1/3, i.e., no distribution shifts, our proposed method also achieves the best results, indicating that learning invariant subgraphs is also beneficial.
Analysis. To analyze whether our proposed method can accurately capture the invariant subgraph, we compare GIL with baselines that also output subgraphs using the ground-truth invariant subgraphs. The evaluation metric is Precision @5. We report the results in Figure The results show that GIL has clear advantage in discovering invariant subgraphs under latent environments, while the other baselines cannot handle distribution shifts well.
Top-k Pool (b) SAG Pool
DIR
(d) GSAT
(c) GIL
(f) Ground Truth
Figure 6: Visualizations of the learned invariant subgraph for showcase from the testing set of SP-Motif. In Figures (a)-(e), the red lines indicate the learned invariant subgraph, and the ground-truth is shown by the black lines in Figure (f).
7

---

Table 2: The graph classification results (%) on
Train set
Test set romantic
testing sets of the real-world datasets. We report the accuracy for 75pp and Graph-SST2, ROC-AUC for MOLSIDER and MOLHIV.
posilive
the
ncturs
daniel
world
best
auteuil
delightful
comedy
nogalee 1
Gy
G1
MNIST-75kp
Grapb-SST2
MOI SIDER
MOLHI
onto screen
and
stupid
14
44aanc
57.57
76.20
Attenion
16.44575
81.57:0071
56.99
15.8
the
lond
Violent
mindless
unbelicvably
Top-k Pool
15,0224es
79.78
60 60.6321.22
73:01=110
SAG Pool
19. 79
80.24.117
61 29
73.26_114
ASAP
15.
81.57,n8
73.81-117
Figure 7: Four showcases of sentences with positive/negative sentiments of train/test sets on
GroupDRO
15.72,4435
11:44
56.31a115
75.44.116
IRM
18.74
81.01 11.
57. 10
74.46-211
V-REx
18
81. 11.76.10m
57.76 97.761977
75.62_414
Graph-SST2 learned by our GIL. Blue edges in-
DIR
17:38
83.29
57.741143
77.05
dicate the learned invariant subgraphs, while the
82.95:n.5
76.47-133
GIL
21.94:005
83.44:007
63.50
79.08-154
others are variant subgraphs.
Besides the quantitative evaluation, plot showcase from the testing set of SP-Motif (Ttrain 0.8 and fess = 0.2) in Figure 6 The figure shows that the learned invariant subgraph of our method is more accurate than baselines.
5.3 Experiments on Real-world Graphs
We further evaluate the effectiveness of our method on real-world graph datasets. The experimental results are presented in Table Our GIL achieves the best performance all four datasets, indicating that GIL can well handle distribution shifts on real-world graphs. For example, GIL increases the classification accuracy by 1.8% on MNIST-75sp and ROC-AUC by 2.0% on MOLHIV against the strongest baselines respectively. On MOLHIV, the results most baselines are worse than ERM, indicating that they fail to achieve OOD generalization in this dataset. Besides, different datasets have different distribution shifts, e.g., Graph-SST2 has different node degrees, the distribution shift of MNIST-75sp is on node features, and OGB is split based scaffold. Therefore, the results show that our proposed method can well handle diverse types of distribution shifts in real graph datasets.
For MOLHIV, besides adopting GIN 3 as back- bone (shown in Table [ our method is also compatible with the other popular GNNs, We try using HIG and CIN (27 (Rank #2 and #8 on the MOLHIV leaderboard") as the backbone since these models are orthogonal to ours. Table shows that our GIL can consistently improve these models.
Table 3: The test results with different backbones.
CIN
GIL (CIN Backbone)
HIG (Rank #2)
PASaFP: (Rank A1)
GH.
(Rank 48)
(HG Backbone)
80.94
S1.15
84.03
81.20.aas
s4.23
In addition, we present some showcases of the learned invariant subgraph of the proposed GIL, on both the train and test set of Graph-SST2. This dataset consists of sentences with positive/negative sentiments and is more understandable for humans. Figure shows that our method can learn invariant subgraphs by consistently focusing on the positive/negative words that are salient for sentiments and distinguishing invariant/variant parts under distribution shifts. For example, the subgraph "The world's 's best actors" identified by GIL has a predictive and invariant relationship with the positive sentiment label, while the subgraph "daniel auteuil" may reflect variant sentiments in different sentences. These results validate: (1) the invariant and variant subgraphs widely exist in real-world datasets, and (2) our GIL can well identify invariant subgraphs under distribution shifts and further make predictions with high accuracy based on the learned invariant subgraphs.
5.4 Analysis of Environment Inference
In our proposed model, all components are jointly optimized. To show that the environment inference module and invariant learning module can mutually enhance each other, we record the test accuracy and the Silhouette score (28] which is commonly used evaluation metric for clustering, as the model is trained. The results on SP-Motif (Ptrain = 0.8, Fiest = 1/3) are shown in Figure We can observe that the test accuracy and the clustering performance improve synchronously over training. A plausible reason is that, as the training stage progresses, the invariant subgraph generator is optimized so that it can generate more informative invariant subgraphs and therefore improve the performance on the testing set. On the other hand, accurately discovering invariant subgraphs can also promote
8

---

identifying variant subgraphs, which capture the environment irriioonment-diciiinattt features and better infer the latent environments. To verify that GIL can infer the environments accurately, we use t-SNE [29] to plot the discovered environments on a 2D-plane when the optimization is finished. Figure shows that the variant subgraphs perfectly capture the anvironment-discriiin features. Notice that GIL achieves such results without needing any ground-truth environment label.
5.5 Hlpper-pe Seyper--prannnn parameter Sensitivity
We investigate the sensitivity of hhper-parametter of our method, including the number of environ- ments ferl the invariance regularizer coefficient X, and the size of the invariant subgraph mask t in Eq. (3). For simplicity, we only report the results on SP-Motif (Ftrain = 0.8 and Itest = 1/3) and MSIST-75sp in Figure while the results other datasets show similar patterns.
First, the number of environments has a moderate impact on the model performance. For SP-Motif, the performance reaches peak when [Einferl 3, showing that GIL achieves the best result when the number of environments matches the ground truth. For MNIST-75sp, the best number of environments is [Enterl = 2. A plausible reason is that a large number of environments will bring difficulty in inferring the latent environment, leading to sub-optimal performance. Sec- ond, the coefficient/ À also has slight influence the performance, indicating that we need to properly balance the classification loss and the invariance regularizer term, Finally, a proper value of the mask size / is important, very large & will result in too many edges in the in- variant subgraph and bring in variant structures, while a small & may let the invariant subgraph become too small to capture enough structural information. Although an ap- propriate choice of hyper-pane parameeetsssssss can further improve the performance, our method is not very sensitive to hyper- parameters. Figure shows that GIL can outperform the best baselines with wide range of caaper-parameteny choices.
(a) The number of environments fonterl
(h) The regularizer coefficient
5,0 138 coe
(c) The invariant subgraph mask size Figure 8: The impact of different hyper- parameters. Yellow and blue lines de- note the results of GIL and grey dashed lines are the best results of all baselines.
6 Related Works
Graph neural networks. Recently, graph neural networks (GNNs) have shown enormous success in graph representation learning [133] demonstrating their strength in various tasks (30-36). GNNs generally adopt a neighborhood aggregation (message passing) paradigm, i.e., the representations of nodes iteratively updated by aggregating representations of their neighbors. The representation of the whole graph is summarized on node representations through the readout function (i.c., pooling) [3] 22]. However, most existing GNN models do not consider the cuttof-distribution generalization ability (37 so that their performances can drop substantially on testing graphs with distribution shifts.
Generalization of GNNs. Early works 38 for analyzing the generalization ability of GNNs do not consider distribution shifts [7
More recently, the generalization ability of GNNs 45 46)
447 find that encoding task-specific non-linearities in the architecture or features can improve GNNs extrapolating graph try to encourage GNNs to perform well on testing graphs with different sizes. Some works [50] 51] are proposed to deal with node-level tasks. EERM [52) studies the OOD generalization in node classification. However, little attention has been paid to learning graph-level representations under distribution shifts from the invariant learning perspective. One exception is the work DIR [16), which conducts interventions on graphs to create interventional distributions.
under distribution shifts starts to receive research attention 44
16
algorithmic tasks. [17 48 49
However, performing causal intervention relies on strong assumptions (53) that could be violated and expensive satisfy in practice [54]. GSAT (26] applies graph information bottleneck criteria for generalization, but its goal is mainly to build inherently interpretable GNNs.
Invariant Learning. Invariant learning aims to exploit the invariant relationships between features and labels across distribution shifts, while filtering out the variant spurious correlations. Backed by causal theory, invariant learning model can lead to OOD optimal models under some assumptions [[]

---

9. However, most existing methods heavily rely multiple environments that have to be explicitly provided in the training dataset, Such annotation is not only prohibitively expensive for graphs, but also inherently problematic the environment split could be inaccurate, rendering these invariant learning methods inapplicable. A few works study OOD generalization on latent environments in computer vision [55, 56) or raw feature data [57], which cannot be directly applied to graphs. In summary, how to learn invariant graph representations without explicit environment label under distribution shits remains largely unexplored in the literature.
7 Conclusions
In this paper, propose the graph invariant learning (GIL) model to tackle the problem of learning invariant graph representations under distribution shifts. Three tailored modules are jointly optimized to encourage the graph representations to capture the invariant relationships between predictive graph structural information and labels. Theoretical analysis and extensive experiments on both synthetic and real-world datasets demonstrate the superiority of GIL.
Acknowledgements
This work was supported in part by the National Key Research and Development Program of China No. 2020AAA0106300 and National Natural Science Foundation China (No. 62250008, 62222209, 62102222, 62206149), China National Postdoctoral Program for Innovative Talents No. BX20220185,
China Postdoctoral Science Foundation No. 2022M711813.
References
[1] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
[2] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[3] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[4] Yoshua Bengio, Tristan Deleu, Nasim Rahaman, Rosemary Ke, Sébastien Lachapelle, Olexa Bilaniuk, Anirudh Goyal, and Christopher Pal. A meta-transfer objective for learning to disentangle causal mechanisms. International Conference on Learning Representations, 2019.
[5] Yang Li, Buyue Qian, Xianli Zhang, and Hui Liu. Graph neural network- betwork-based diagnosis prediction. Big Duta, 8(5):379-390, 2020.
[6] Yiying Yang, Zhongyu Wei, Qin Chen, and Libo Wu. Using external knowledge for financial event prediction based on graph neural networks. In Proceedings of the 28th ACM International Conference Information and Knowledge Management, pages 2161-2164, 2019.
[7] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, (2):51335330 2018
[8] Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk mini- mization. arXiv preprint /007:/900.00200 00299,, 2019.
[9] Masanori Koyama and Shoichiro Yamaguchi. Out-of-distribution generalization with maximal invariant predictor. arXiv preprint arXiv:2008.01883 2020.
[10] Kartik Ahuja, Ethan Caballero, Dinghuai Zhang, Yoshua Bengio, Ioannis Mitliagkas, and Trina Rish. Invariance principle meets information bottleneck for out-of-distribution generalization. Neural Information Processing Systems (NeurIPS), 2021.
10

---

[11] Shiyu Chang, Yang Zhang, Mo Yu, and Tommi Jaakkola. Invariant rationalization. In Interna- tional Conference on Machine Learning, pages 1458. PMLR, 2020.
[12] Mateo Rojas-Carulla, Bernhard Schölkopf, Richard Turner, and Jonas Peters. Invariant models for causal transfer learning. The Journal of Machine Learning Research, 19(1):109-1132,, 2018.
[13] Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32:9240, 2019.
[14] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances Neural Information Processing Systems, 33, 2020.
[15] John A Hartigan and Manchek A Wong. Algorithm 136: A k-means clustering algorithm. Journal of the royal statistical society. series с (applied statistics), 28(1):100-105 1979.
[16] Yingxin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. In International Conference on Learning Representations, 2022.
[17] Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and gener- alization in graph neural networks, Advances in Neural Information Processing Systems, 32: 4202-4212, 2019.
[18] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 86(11))2278-222 1998.
[19] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. arXiv preprint arXiv:2012.15445 2020.
[20] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Neural Information Processing Systems (NeurIPS), 2020.
[21] Hongyang Gao and Shuiwang Ji. Graph u-nets. international conference on machine learning, pages 2083-2092 PMLR, 2019.
[22] Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International Conference on Machine Learning, pages 3734-3743. PMLR, 2019.
[23] Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar. Asap: Adaptive structure aware pooling for learning hierarchical graph representations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5470-5477, 2020.
[24] 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.087: 2019.
[25] David Krueger, Ethan Caballero, Joern-Henil Jacobsen, Amy Zhang. Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. Out-of-distribution generalization via risk extrap- olation (rex). In International Conference Machine Learning, pages 5815-5826. PMLR, 2021.
[26] Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. In /CML, 2022.
[27] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang. Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Neural Information Processing Systems, 2021.
(28) Peter Rousseeuw. Silhouettes: a graphical aid the interpretation and validation of cluster analysis. Journal of computational and applied mathematics, 20:53-65, 1987.
11

---

[29] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(1)) 2008.
[30] Jianxin Ma, Peng Cui, Kun Kuang, Xin Wang, and Wenwu Zhu. Disentangled graph convolu- tional networks. In International conference on machine learning, pages 4212-4221. PMLR, 2019.
[31] Haoyang Li, Xin Wang, Ziwei Zhang, Jianxin Ma, Peng Cui, and Wenwu Zhu. Intention-aware sequential recommendation with structured intent transition. IEEE Transactions on Knowledge and Data Engineering. 2021.
[32] Haoyang Li, Xin Wang. Ziwei Zhang, Zehuan Yuan, Hang Li, and Wenwu Zhu. Disentangled contrastive learning on graphs. Advances in Neural Information Processing Systems, 34: 21872-21884, 2021.
[33] Xin Wang. Hong Chen, Yuwei Zhou, Jianxin Ma, and Wenwu Zhu. Disentangled representation learning for recommendation. IEEE Transactions Pattern Analysis and Machine Intelligence, 2022.
[34] Haoyang Li, Peng Cui, Chengxi Zang, Tianyang Zhang, Wenwu Zhu, and Yishi Lin. Fates of microscopic social ecosystems: Keep alive or dead? In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 668-676, 2019.
[35] Haoyang Li, Ziwei Zhang, Xin Wang, and Wenwu Zhu. Disentangled graph contrastive learning with independence promotion. IEEE Transactions on Knowledge and Data Engineering, 2022.
[36] Yijian Qin, Xin Wang. Peng Cui, and Wenwu Zhu. Gqnas: Graph q network for neural architecture search. 2021 IEEE International Conference on Data Mining (ICDM), pages 1288 1293. IEEE, 2021.
[37] Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu Zhu, Out-of-distribution generalization on graphs: A survey. arXiv preprint arXiv:2202.07987, 2022.
(38] Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac-bayesian approach to generalization bounds for graph neural networks. In International Conference on Learning Representations, 2020.
[39] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference Machine Learming, pages 3419-3430. PMLR, 2020.
[40] Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural networks. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1539-1548, 2019.
[41] Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapnik-shervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248 259, 2018.
[42] Huaxiu Yao, Caroline Choi, Yoonho Lee, Pang Wei Koh, and Chelsea Finn. Wild-time: A benchmark of tethhewwld distribution shift over time. In Proceedings of the Thirty-sixth Conference Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
[43] Zeyang Zhang, Ziwei Zhang, Xin Wang, and Wenwu Zhu. Learning to solve travelling salesman problem with hardness-aued adaptiie curriculum. In 36th AAAI Conference on Artificial Intelligence (AAAI), 2022.
[44] Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu Zhu. Ood-gnn: cittof-ddsttibbutin gen- eralized graph neural network. IEEE Transactions on Knowledge and Data Engineering, 2022.
[45] Yijian Qin, Xin Wang, Ziwei Zhang, Pengtao Xie, and Wenwu Zhu. Graph neural architecture search under distribution shifts. In International Conference on Machine Learning, pages 18095-18095. PMLR, 2022.
12

---

[46] Zeyang Zhang, Xin Wang, Ziwei Zhang, Haoyang Li, Zhou Qin, and Wenwu Zhu. Dynamic graph neural networks under spatio-temporal distribution shift. In Thirty-Sixth Conference on Neural Information Processing Systems, 2022.
[47] Keyulu Xu, Mozhi Zhang, Jingling Li, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In International Conference Learning Representations, 2021.
[48] Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In International Conference on Machine Learning, pages 1975--19886 PMLR, 2021.
[49] Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invariant graph representations for graph classification extrapolations. In Proceedings of the 38th International Conference on Machine Learning, pages 837-851, 2021.
2021.
[50] Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi. Shift-robust gnns: Overcoming the limitations of localized graph training data. Advances in Neural Information Processing Systems, 34, 2021.
[51] Shaohua Fan, Xiao Wang, Chuan Shi, Kun Kuang, Nian Liu, and Bai Wang. Debiased graph neural networks with agnostic label selection bias. IEEE transactions neural networks and learning systems, 2022.
[52] Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invariance perspective. In International Conference on Learning Representations (ICLR), 2022.
[53] Miguel A Hernán and James M Robins. Causal inference, 2010.
[54] Tan Wang, Chang Zhou, Qianru Sun, and Hanwang Zhang. Causal attention for unbiased visual recognition. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3091-3100, 2021.
[55] Toshihiko Matsuura and Tatsuya Harada. Domain generalization using mixture of multiple latent domains. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 11749- 11756, 2020.
[56] Elliot Creager, Lörn-Henrt Jacobsen, and Richard Zemel. Environment inference for invariant learning. In International Conference on Machine Learning, pages
PMLR, 2021,
[57] Jiashuo Liu, Zheyuan Hu, Peng Cui, Bo Li, and Zheyan Shen. Heterogeneous risk minimization. In International Conference on Machine Learning. PMLR, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
13

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "S4ICvql11X6", "reviewer": "Reviewer_uGwK", "summary": "This paper studies the out-of-distribution (OOD) generalization problem on graphs under a mixture of environments. \n\nIt proposes a graph invariant learning (GIL) solution to learn a maximally invariant graph predictor, which composes an environment inference module and an invariant subgraph identification module. ", "questions": "As mentioned above, the main concern is about the novelty and lack of adequate literature discussions. ", "limitations": "No obvious potential negative societal impact. This paper should also discuss a bit about the applicability of the assumptions made in this paper.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The problem this paper studied is important, i.e.,  OOD generalization of GNNs, and it proposes an out-of-distribution generalization framework for GNNs, which composes environment inference and invariant subgraph identification/generalization.\n2. The presentation logic flow is clear.\n\nWeaknesses:\n\n1. The novelty and significance of this paper are a concern as some important literature is not discussed in this paper. There are several works also studying OOD generalization on graphs but corresponding discussions are missing in the paper. \n\t1. Wu et al. 2022 [1] study the OOD generalization in node classification, and takes similar assumptions and solutions in this paper.\n\t2. Miao et al., 2022 [2] also discussed the application of graph information bottleneck criteria for OOD generalization.\n2. Especially, in the literature on invariant learning, the key method in this paper shares many similarities with HRM[3], which should be discussed and compared substantially.\n3. In experiments, [1,2] should all be included as baselines, and direct applying [3] to graph data should also be included as a baseline.\n\n\n[1] Qitian Wu, Hengrui Zhang, Junchi Yan, David Wipf. Handling Distribution Shifts on Graphs: An Invariance Perspective. ICLR 2022.\n\n[2] Siqi Miao, Miaoyuan Liu and Pan Li. Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism. ICML 2022.\n\n[3] Jiashuo Liu, Zheyuan Hu, Peng Cui, Bo Li, and Zheyan Shen. Heterogeneous risk minimization. ICML 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AtIJ3WLKRzU", "reviewer": "Reviewer_PXQD", "summary": "This paper studies OOD generalization with a mixture of graph environments without environment labels. The method first generates the invariant subgraph and the variant subgraph based using a graph generator model. It then infers the environment labels by conducting k-means clustering on the variant subgraphs. This step assumes that the environment labels are correlated with variant subgraphs and are irrelevant to the invariant subgraph. The method then conducts invariant learning optimization across the different inferred environments.", "questions": "As shown in [1], the ground truth environment partition does not always lead to the best OOD generalization performance. Is this also true in the graph domain? If yes, how does the proposed kmeans clustering lead to better environment partitions for OOD generalization? \n\nReference:\n[1] Environment Inference for Invariant Learning. In ICML 2021.", "limitations": "The authors have well addressed the limitations in the paper.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper firstly studies OOD generalization for graphs without environment labels. The problem is clearly defined and discussed in the paper. Based on the assumptions, the author proposes a method that aligns with the identified challenges. The method later shows significant improvement over the baselines.\n\nAs for the weakness, I find gaps between the steps in theoretical analysis. In Equation (7), the optimization uses the ground truth environment $\\mathcal{E}$, while Equation (8) uses the inferred environments $\\mathcal{E}\\_{infer} $ . The difference between $\\mathcal{E}$ and $\\mathcal{E}\\_{infer} $ should be discussed to understand the proposed algorithm. The discussion should answer questions like \"does $\\mathcal{E}\\_{infer}$ approximate $\\mathcal{E}$?\" and \"what are the properties of $\\mathcal{E}_{infer}$ for good OOD generalization performance?\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9RUXsIGR37", "reviewer": "Reviewer_oeB7", "summary": "The paper investigates a new research problem of learning invariant graph representations under distribution shifts by considering the latent environment labels. The proposed method, graph invariant learning (GIL), is a joint learning framework combing three different GNNs of various functions. With good empirical results on several datasets and related theoretical analyses, the paper justifies the effectiveness of the proposed GIL. ", "questions": "1. It might be somehow confusing for the invariance property in Assumption 3.1 for its connection with the true labels of graphs. Two graphs of different environments are likely to be classified correctly even though they are not perfectly samples. So, what is the main difference between the invariance property and  $P^e(\\Phi^*(G))=P^{e^{\\prime}}(\\Phi^*(G))$ as in the last condition of Theorem 4.1? Is it harder to be achieved? Or, can it provide a better guarantee?\n2. The optimization process of the three used GNNs is unclear, which could be an essential design of the proposed system. I.e., how do the GNN$^M$, GNN$^V$, and GNN$^I$ be jointly optimized? \n3. Besides, since the adjacent matrixes $A_I$ and $A_V$ are discrete, how are the gradients calculated and back propagated among these GNNs in an end-to-end manner?\n4. The clustering effectiveness in Figure 5 seems quite perfect for its accurate partition, but the Score in Figure 4 is lower than 0.75. So, where is the gap come from? It would be better for the paper to introduce more about the Silhouette score, e.g., its basic calculation and range of values.\n5. Regarding the prediction of latent environment labels are one of the main contributions, I would suggest the paper show the clustering cases without environment inference to better justify the effectiveness of such a designed module.", "limitations": "The READOUT functions, which shall be important for the proposed method, are not fully discussed and compared in the paper, including in the appendix part. Since the paper has mentioned the usage and the desired properties of READOUT functions many times, it would be better for the paper to provide a further discussion and related ablations. Besides, the influence of different GNN architectures, which served as backbones in the paper, is also missing.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros\n\n- The investigated problem is new and challenging, especially for real-world graph learning scenarios. With the well-defined research problem, the paper proposed to take the latent environment labels into consideration, which sheds an interesting direction on the current graph learning area.\n- The gained empirical improvement is quite significant with the proposed GIL framework. Several ablation studies are shown.\n- The paper is with good mathematical groundings for its provided theoretical analysis. Complexity analysis is also presented, including every single module of the proposed GIL framework.\n\nCons\n\n- The importance of the latent environment labels is not fully justified, which should be the major contribution of the paper. It seems unclear for its motivation and significance and what benefits it can bring. In addition to the hyper-parameter study, there lacks instruction to extract, utilize, and analyze the latent environment labels.\n- The technical novelty and contributions of the paper are neutral. The designed yet complicated framework seems to be the combination of several existing methods like the k-means and the invariance regularizer without presenting more insights into the new problem.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "848hHcGECpW", "reviewer": "Reviewer_52ur", "summary": "In this work the authors propose a three part method for learning graph representations that are robust to distribution shifts. First their method identifies _invariant_ subgraphs, then clusters the _variant_ complements to the invariant subgraphs to infer latent environment codes, and finally learns a representation function and linear predictor over the extracted invariant subgraphs and latent environment codes. This system is optimized end to end and they perform an empirical evaluation over synthetic and real world data to demonstrate the effectiveness of the approach.", "questions": "1. Relating to the comment above about environments sharing subgraph structure, this is very much a broad assumption in the entire work. It is _fine_ because though it is a narrow focus it is a fundamental type of distribution shift for graphs. However, it feels like conditions such as $P^{e}(\\phi(G)) = P^{e'}(\\phi(G))$ would generally be too strong in practical settings. Especially for the real world data, did you attempt to empirically verify that some of the conditions for Thm 4.1 approximately hold?\n\n2. Can you elaborate on why the number of clusters for the k-means component was limited to $[2,4]$? Having to explicitly choose this parameter is one of the obvious points of difficulty for the model with datasets comprising an unknown number of latent environments.", "limitations": "The few limitations are relatively minor:\n\n1. Methodological focus on shared subgraph/scaffold structure between environments\n2. System bottleneck on the effectiveness of the unsupervised environment identification module. Ideally they would explore different choices for the clustering algorithm.\n3. The analysis in Figures 4 and 5 of Silhouette score and the TSNE projection of clusters should be extended beyond the synthetic dataset where the environments are perfectly separable, as the claims they were used to support may not be very generalizable.\n4. Hyperparameter sensitivity analysis should be extended beyond the synthetic dataset, even though it is plausible that the trends generalize.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n**Quality**: The empirical evaluation is well scoped in its choice of datasets as well as the diversity of the shift parameter settings and types of analysis showcased. In particular the SP-Motif and OGB selections are well suited to their method's focus on shared subgraph structures. The agreement between the performance rankings of GIL/DIR on SP-Motif and MOLHIV is a good sign since shared subgraphs and scaffolds are similar concepts. The finding that ERM generally outperforms most methods matches prior work for MOLHIV and this then underscores the performance of GIL (and the competitor DIR). Finally, the fact that the performance of the method is also demonstrated on datasets derived from different underlying signals (MNIST and SST2) that are not molecule based, serves as a good generality sanity check.\n\n**Clarity**: The combination of Figure 2 and Section 3 describing their method and training procedures is well presented and easy to understand. Section 5 is broken down well into its subsections and the figures 6 and 7 are appreciated as visual references of the in/variant structures being identified.\n\n**Significance**: Performance suggests that the approach is minimally competitive, and potentially SOTA pushing on the OGB data, though the way in which SP-Motif is used at the sweep of parameter settings makes it slightly harder to directly compare to other work. Method is simpler than some competitor approaches for OOD generalization, which is preferred.\n\n### Weaknesses\n\n**Clarity**: Theorems in Section 4, especially Thm 4.2 can likely be moved to the Appendix, as they don't add very much to the impact of the work compared to the empirical results. Further, Thm 4.1, especially the RHS, is stated very generally rather than in the specific setting of subgraph-based inter-environment invariance, which is not the _only_ kind of environment differentiation one expects in real world data (i.e. feature shift or label imbalance etc. are also options - these are in fact explored in the empirical results).\n\nWork would generally benefit from a close editing pass from a native english speaker, _but this does not factor into my assessment_.\n\n**Originality/Significance**: The three components of the method are not particularly novel on their own - in particular, the invariant regularized learner is very derivative of IRM in its objective. As such the work overall feels like a DL engineering solution for an E2E system, which is not without value by any means, but overall not very methodologically novel.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept