Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs
Authors: Yongqiang Chen
Yonggang Zhang
Yatao Bian
Han Yang
MA KAILI
Binghui Xie
Tongliang Liu
Bo Han
James Cheng
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Neural Networks
Out-of-Distribution Generalization
Graph Representation Learning
Invariant Learning
Causal Representation Learning
Drug Discovery

Abstract: Despite recent success in using the invariance principle for out-of-distribution (OOD) generalization on Euclidean data (e.g., images), studies on graph data are still limited. Different from images, the complex nature of graphs poses unique challenges to adopting the invariance principle. In particular, distribution shifts on graphs can appear in a variety of forms such as attributes and structures, making it difficult to identify the invariance. Moreover, domain or environment partitions, which are often required by OOD methods on Euclidean data, could be highly expensive to obtain for graphs. To bridge this gap, we propose a new framework, called Causality Inspired Invariant Graph LeArning (CIGA), to capture the invariance of graphs for guaranteed OOD generalization under various distribution shifts. Specifically, we characterize potential distribution shifts on graphs with causal models, concluding that OOD generalization on graphs is achievable when models focus only on subgraphs containing the most information about the causes of labels. Accordingly, we propose an information-theoretic objective to extract the desired subgraphs that maximally preserve the invariant intra-class information. Learning with these subgraphs is immune to distribution shifts. Extensive experiments on 16 synthetic or real-world datasets, including a challenging setting -- DrugOOD, from AI-aided drug discovery, validate the superior OOD performance of CIGA.

Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs
Yongqiang Chen'; Yonggang Zhang', Yatao Bian", Han Yang', Kaili Ma', Binghui Xie
'The Chinese University of Hong Kong "Hong Kong Baptist University
hyann, klma, bhxie21, Zhengg@cse.cuhk.eduuue yatao. an@gmall.com
Tongliang Liu', Bo Han", James Cheng'
Tencent Al Lab 'TML Lab, The University of Sydney
tongliang. liudsydney.edu.a au (csygzhang, bhanml joompl//ocohhhhuuuuuuu...
Abstract
Despite recent success in using the invariance principle for outtr--distribution (OOD) generalization on Euclidean data (e.g., images), studies on graph data are still limited. Different from images, the complex nature of graphs poses unique challenges to adopting the invariance principle. In particular, distribution shifts on graphs can appear in a variety of forms such attributes and structures, making it difficult to identify the invariance. Moreover, domain or environment partitions, which are often required by OOD methods on Euclidean data, could be highly expensive to obtain for graphs. To bridge this gap, we propose new framework, called Causality Inspired Invariant Graph LeArning (CIGA), to capture the invari- ance of graphs for guaranteed OOD generalization under various distribution shifts. Specifically, we characterize potential distribution shifts on graphs with causal models, concluding that OOD generalization on graphs is achievable when models focus only on subgraphs containing the most information about the causes of labels. Accordingly, propose information-theoreti objective to extract the desired subgraphs that maximally preserve the invariant intra-class information. Learning with these subgraphs is immune distribution shifts. Extensive experiments 16 synthetic or real-world datasets, including a challenging setting DrugOOD, from Al-aided drug discovery, validate the superior OOD performance of CIGA!.
Introduction
Graph representation learning with graph neural networks (GNNs) has gained great success in tasks involving relational information [45, 35, 99, 106, 107]. However, it assumes that the training and test graphs are drawn from the same distribution, which is often violated in reality [37, 47, 38, 40]. The mismatch between training and test distributions, i.e., distribution shifts, introduced by some underlying environmental factors related to data collection or processing, could seriously degrade the performance of deployed models [7, 24]. Such out- aadt---distribution (OOD) generalization failures become the major roadblock for practical applications of graph representation learning [40].
Meanwhile, enabling OOD generalization regular Euclidean data has received surging attention and several solutions were proposed [4, 81, 10, 49, 23, 48, 2]. In particular, the invariance principle from causality is at the heart of those works [76, 74, 79]. The principle leverages the Independent Causal Mechanism (ICM) assumption [74, 77] and implies that, model predictions that only focus on the causes of the label can stay invariant to a large class of distribution shifts [76, 4, 2].
Work done during an internship at Tencent Lab. Code is available at tttpp://gittee
Com/LFhase//Cie
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Invariant Subgraph Identification
Classification
Algorithm
Guarantee
Regime
Known
SCM Support
IRM
Yes
R
Yes
PILF
TB-IRM [2]
Yos
PUFAFFII
EUL [23]
Yes
R
No
PILF
DANN [31]
N/A
N/A
MatchDG [6]]
N/A
Yes
FHIF
"House""
GroupDro [81]
N/A
R
Yes
N/A
fc
CNC [124]
N/A
No
N/A
G House
"Cycle"
GBB [120]
Yes
G
No
FILP
A
DIR [104]
FIF
CIGA (Ours)
Ves
No
PHFFFIIF
f Cycle
(b)
Figure 1: (a) Illustration of Causality Inspired Invariant Graph LeAming (CIGA): GNNs need to classify graphs based on the specific motif ("House" or "Cycle"). The featurizer g will extract an (orange colored) subgraph G. from each input for the classifier fc to predict the label. The training objective of g is implemented in a contrastive strategy where the distribution of G. at the latent sphere will be optimized maximize the intra-class mutual information, hence predictions will be invariant to distribution shifts; (b) An overview of potential algorithms for OOD generalization on graphs.
Despite the success of the invariance principle on Euclidean data, the complex nature of graphs raises several new challenges that prohibit direct adoptions of the principle. First, distribution shifts on graphs are more complicated. They can happen both attribute-level and structure-level, and be observed in multiple forms such as graph sizes, subgraph densities and homophily [113, 11, 102]. On the other hand, each of the shifts can spuriously correlate with labels in different modes [4, 71, 2]. Consequently, the entangled complex distribution shifts make it more difficult to identify and capture the invariance on graphs. Second, OOD algorithms developed and analyzed on Euclidean data often require additional environment (or domain) labels for distinguishing the sources of distribution shifts [4]. However, the environment labels could be highly expensive obtain and thus often unavailable for graphs, as collecting the labels usually requires expert knowledge due to the abstraction of graphs [37]. These challenges render the problem studied in this paper even more challenging:
How could one generalize the invariance principle enable OOD generalization on graphs?
To solve the above problem, we propose Causality Inspired Invariant Graph LeArming (CIGA), new framework for capturing the invariance of graphs to enable guaranteed OOD generalization under different distribution shifts. Specifically, we build three Structural Causal Models (SCMs) [74] to characterize the distribution shifts that could happen on graphs: one model the graph generation process, and the other two are to model two possible interactions between invariant and spurious features during the graph generation, i.e., Fully Informative Invariant Feature (FIIF) and Partially Informative Invariant Feature (PIIF) (Sec. 2.2). Then, we generalize the invariance principle to graphs for OOD generalization: GNN models are invariant to distribution shifts if they focus only on invariant and critical subgraph Ge that contains the most of the information in G' about the underlying causes of the label. Thus, the problem of achieving OOD generalization on graphs can be rephrased into two processes: invariant subgraph identification and label prediction. Accordingly, shown as Fig. (a)), we introduce a prototypical invariant graph learning algorithm that decomposes GNN into: featurizer g for identifying the underlying invariant subgraph G. from G; b) classifier fo for making predictions based on G.- To extract the desired subgraph Ge, we derive an anformation-theorettic objective for the featurizer to identify subgraphs that maximally preserves the invariant intra-class information across a set of different (unknown) environments. We theoretically show that this approach can provably identify the underlying G. under mild assumptions (Sec. 3).
Experiments on 16 synthetic and real-world datasets with various distribution shifts, including a challenging setting from Al-aided drug discovery [40], show that CIGA can significantly outperform all of existing methods up to 10%, demonstrating its promising OOD generalization ability (Sec. 4).
Related Work. We review existing methods that might improve the OOD generalization on graphs, summarize the main differences between our solution and them in Table ((b), and leave thorough discussions to Appendix B.2. On Fuclidean data, Invariant Learning [4, 23, 2], Group Distributionally Robust Optimization [49, 81, 124], Domain Adaption and Domain Generalization [31, 93, 52, 27, 61,

---

100] are three widely adopted approaches to enable OOD generalization. However, they all have their own limitations when being applied to graphs. First, previous invariant learning methods are mostly developed and analyzed for Euclidean data [4. 2. 23), or under specific SCM assumptions [4], making the theoretical results hardly able to generalize to the complicated graph data [80] that can have multiple types of distribution shifts [71]. Group Distributionally Robust Optimization that minimizes the gap between worst group risk and average risk [49, 81, 124], and Domain Adaption(Geeerraiiatioo
methods that aim to learn class-conditional domain invariant representations [31, 93, 52, 27, 100], cannot guarantee a min-max optimal predictor without additional assumptions [126, 4, 2]. Moreover, most existing methods require environment labels that are however expensive to obtain in graphs, which limits their applications to graphs [4, 49, 2, 81, 31, 93, 27, 61]. In contrast, we aim to develop OOD algorithms for graphs that provably generalizable under different types of distribution shifts.
Another line of relevant works about GNN explainability that aims to find a subgraph of the input as the explanation for GNN prediction [116. 122]. Although some may leverage causality to justify the generated explanation [53]. they mostly focus on understanding the predictions of GNNs instead of for OOD generalization. The closest works to ours are two interpretable GNNs that aim to explicitly extract a subgraph for both predictions and explanations guided by information theory [120] and causality [104], respectively. However, they focus graphs and shifts generated under a specific SCM. Although one of them can provide theoretical guarantee for OOD generalization [120] by using the information bottleneck criteria [2], they would inevitably fail to generalize to graphs generated under different SCMs. More discussions about the failure are deferred to Appendix D.4. Besides, Bevilacqua et al. [11] also discuss OOD generalization on graphs but limited to specific graph family and graph size shifts. Wu et al. [103] propose OOD) generalization algorithms on graphs for the task of node classification, also limited to graphs and shifts under a specific SCM.
To the best of our knowledge, there is no existing work that could handle more comprehensive graph distribution shifts than CIGA, while also achieving provable OOD generalization performance.
2 OOD Generalization on Graphs through the Lens of Causality
2.1 Problem Setup
In this work, we focus on OOD generalization in graph classification. Specifically, we are given set of graph datasets D {D*), je collected from multiple environments Ean, Samples (G;, Y;) E De from the same environment are considered as drawn independently from an identical distribution P
GNN poh generically has an encoder h G + R² that learns meaningful representation heg for each graph G to help predict the label YG p(hc) with downstream classifier p: Rhh + y. The goal of OOD generalization on graphs is to train a GNN p o with data from training environments Dtr JeE&,CE that generalizes well to all (unseen) environments, i.e., to minimize max.g5,, R", where 1e is the empirical risk of o under environment e 197, 4J. We leave more details about the background of GNN for graph classification and invariant learning in Appendix B.
It is known that OOD generalization impossible without assumptions on the environments Ear [74, 21. Thus, we will first formulate the data generation process with structural causal model and latent- variable model [74, 77, 50]. to characterize the distribution shifts that could happen on graphs. Then, we investigate whether the existing methods are generalizable under these distribution shifts.
2.2 Graph Generation Process
We take a latent- variable model per- spective on the graph generation pro- cess and assume that the graph is generated through mapping fgen
E
E
Ge
S
2 > G, where C T is the la- tent space and G U
UN (0, 1] x R Nxd is the graph space. Let E de- note environments. Following previ- ous works [50, 2], we partition the la- tent variable from into an invariant part C C = =e and varying part
(a) G-Gen. SCM
(b) FIIF SCM
(c) PIF SCM
Figure 2: SCMs on graph distribution shifts.
3

---

S S = R, s.t., n nr + R2,, according to whether they are affected by E or not. Similarly in images, C and S can represent content and style while E can refer to the locations where the images are taken [7, 125, 50]. Furthermore, C' and S control the generation of the observed graphs (Assump- tion 2.1) and can have multiple types of interactions at the latent space (Assumptions 2.2, 2.3).
Graph generation model. We elaborate the SCM for the graph generation process in Assumption 2.1 and Fig. 2(a), where noises in the structural equations are omitted for simplicity [77].
Assumption 2.1 (Graph Generation Structural Causal Model).
Ge : fgo (C',,
Gg == GG (S),
G= C==fgonGao (Ge G&).
In Assumption 2.1, fgen is decomposed into fgen fgen and fge to control the generation of Ge,. G.. and G, respectively. Among them, Ge inherits the invariant information of C that would not be affected by the interventions (or changes) of E [74, 77J. For example, certain properties of molecule usually be described by sub-molecule,
functional group. which is invariant across different species or assays [12, 92, 40J. On the contrary, the generation of G, and G will be affected by the environment E' through S. Thus, graphs collected from different environments (or domains) can have different distributions of structure-level properties (e.g., graph sizes [11, 102]) as well as feature-level properties (e.g.. homophily [62. 17)) Therefore, the subgraph G. inherits the spurious feature about Y [125]. In fact, Assumption 2.1 is compatible with many graph generation models by specifying the function classes of fgei fye and f [89, 57, 11J. Since our goal to characterize the potential distribution shifts in Assumption 2.1, we focus on building a general SCM that is compatible to many graph families and leave graph family specifications and their implications to OOD generalization in future works. More discussions are provided in Appendix C.
Interactions at latent space. Following previous works [4, 2], we categorize the latent interactions between C' and S into Fully Informative Invariant Features (FIIF, Fig. 2(b)) and Partially Informative Invariant Features (PII, Fig. 2(c))², depending on whether the latent invariant part C' is fully informative about label Y, i... (S, E) IL Y.C. Formal definitions of the corresponding SCMs are given as follows, where noises are omitted for simplicity [74, 77].
Assumption 2.2 (FIIF Structural Causal Model). Y := fim (C), S := Sapu (Opu(C, E), G == fgem S). Assumption 2.3 (PIIF Structural Causal Model). Y = fim (C), S S S (Y, E), G= Sgen(C,
In the two SCMs above, fgen corresponds to the graph generation process in Assumption 2.1, and fapu is the mechanism describing how S is affected by C and E at the latent space. By definition, S is directly controlled by C' in FIIF and indirectly controlled by C' through Y in PII,, which can exhibit different behaviors in the observed distribution shifts. In practice, performances of OOD algorithms can degrade dramatically if one of FIIF or PIIF is excluded [5, 71]. This issue can be more serious in graphs, since different distribution shifts can have different interaction modes at the latent space. Moreover, fim : C + y indicates the labelling process, which assigns labels Y for the corresponding G merely based on C. Consequently, C is better clustered than S when given Y [13, 15, 86, 87], which also serves as the necessary separation assumption for a classification task [69, 16, 65].
Assumption 2.4 (Better Clustered Invariant Features). HCCYY) S (SSY))
2.3 Challenges of OOD Generalization on Graphs
Built upon the graph generation process, we can formally derive the desired GNN that is able to generalize to OOD graphs under different distribution shifts, which implics the invariant GNN below?.
Definition 2.5 (Invariant GNN). Given set of graph datasets {D*}. e and environments Eall that follow the same graph generation process in Sec. 2.2, considering GNN po h that has permutation invariant graph encoder h : 9 -> & and a downstream classifier p : ARth -> V, p o is an invariant GNN if it minimizes the worst case risk among all environments, i.e., min max R
Can existing methods produce a desired invariant GNN model? We find the answers to be negative unfortunately, Based on the synthetic BAMotif graph classification task [58, 104] shown in Fig. 3,
NNote that FIIF and PIIF can be mixed as Mixed Informative Invariant Features (Appendix 6(d)) several ways, while our analysis will focus on the axiom ones for the purpose of generality.
A discussion Def. 2.5 and its relation to the SCMs is provided in Appendix E.

---

Traininn lait
Testing Data
Six
"Baus""
Accuracy
Acouracy
"Iamma"
"Cyde"
0.6 Blaces
(a) Failure cases for existing methods. (b) Structure and attribute (cifts.(c) Mixed with graph size shifts.
Figure 3: Failures of OOD generalization on graphs: (a) GNNs required classify whether the graph contains a "house" or "cycle" motif, where the colors represent node features. However, distribution shifts in the training data exist both structure-level (from left right: "house" mostly co-occur with hexagon), attribute-level (from upper to lower: nodes are mostly colored green if the graph contains a "house", or colored blue if the graph contains a "cycle"), and graph sizes, making GNNs hard to capture the invariance. Consequently, ERM can fail for leveraging the shortcuts and predicting graphs that have a hexagon or have nodes mostly colored green as "house". IRM can fail as the test data are not sufficiently supported by the training data. (b) GCNs optimized with neither ERM nor IRM can generalize to OOD graphs under structure-level shifts (Struc-) or mixed with feature shifts (Mixed-). (c) When more complex shifts presented, GNNs can fail more seriously.
we theoretically and empirically analyze whether existing methods could produce an invariant GNN, through the investigation of the following aspects. More details and results are given in Appendix D.
Can GNNs trained with ERM generalize to OOD graphs? As shown in Fig. 3, find that GNNs trained with the standard empirical risk minimization (ERM) algorithm [97] are not able to generalize to OOD graphs. As the data biases grows stronger, the performances of GNNs drop dramatically. Furthermore, when graph size shifts are mixed in the data, GNNs can have larger variance at low data biases, indicating the instability of learning the desired relationships for the task. The reason is that ERM tends to overfit to the shortcuts or spurious correlations presented in specific substructures or attributes in the graphs [33]. This phenomenon has also been shown exist in GNNs equipped with more sophisticated architectures such as attention mechanisms [99], under graph size shifts [46].
Can OOD objectives improve OOD generalization of GNNs? Mcanwhile, as shown in Fig. 3, OOD objectives primarily developed on Euclidean data such as invariant risk minimiza- tion (IRM) [4] also cannot alleviate the problem. On the contrary, IRM can fail catastrophi- cally at non-linear regime if without sufficient support overlap for the test environments, i.e., supp((") & Uege, (P" [80]. In addition to IRM, the failure would also happen for alternative objectives [49, 9, 2] as proved by Rosenfeld et al. [80]. Besides, different distribution shifts on graphs can be nested with each other where each one can have distinct spurious correlation type, e.g., FIIF or PII.. OOD objectives will also fail seriously either of the correlation types is not supported [5, 71]. Moreover, non-trivial environment partitions labels are required for performance guarantee of these OOD objectives [4, 49, 81, 2]. However, collecting meaningful environment partitions of graphs requires expert knowledge about graph data. Thus, the environment labels can be expensive to obtain and are usually not available [67, 28, 37J. Alternative options such as random partitions tend not to alleviate the issue [23, 55], as it can be trivially deemed mini-batching.
Challenges of OOD generalization on graphs. The aforementioned failure analysis reveals that existing methods objectives fail to elicit invariant GNN primarily due to the following two challenges: a) Distribution shifts on graphs are more complicated where different types of spurious correlations can be entangled via different graph properties; b) Environment labels are usually not available due to the abstraction of graphs. Despite these challenges, we are still highly motivated to address the following research question: Would it be possible to learn invariant GNN that is generalizable under various distribution shifts by lifting the invariance principle to the graph data?
3 Invariance Principle for OOD Generalization on Graphs
We provide affirmative answers to the previous question by proposing new framework, CIGA: Causality Inspired Invariant Graph LeArning Specifically, built upon the SCMs Sec. 2.2, we generalize the invariance principle to graphs and instantiate the principle with theoretical guarantecs.
5

---

3.1 Invariance for OOD Generalization on Graphs
Towards extending the invariance principle to graphs under SCMs in Sec. 2.2, we need identify set of variables that have stable causal relationship with Y under both FIIF and PIIF (Assumption 2.2, 2.3). According to the ICM assumption [77], the labeling process C - Y not informed nor influenced by other processes, implying that the conditional distribution P(YIC) remains invariant to the interventions on the environment latent variable E' [74]. Consequently, for a GNN with a permutation invariant encoder h 9 + Ia and a downstream classifier p E + y. if h can recover the information of C from G in the learned graph representations, then the learning of p resembles traditional ERM [97] and can achieve the desired min-max optimality required by an invariant GNN (Def. 2.5). However, recovering C' from G is particularly difficult, since the generation of G from C involves two causal mechanisms fgo and fge in Assumption 2.1. The unavailability of E further adds up the difficulty of enforcing the independence between the learned representations and E.
3.2 Invariant Graph Learning Framework
Causal algorithmic alignment. To enable a GNN to learn to extract the information about C. from G. we propose the CIGA framework that explicitly aligns with the two causal mechanisms fgen and fgen in Assumption 2.1. The idea of alignment in CIGA is motivated by the algorithmic reasoning results that a neural network can learn a reasoning process better if its computation structure aligns with the process better [108. 110]. Specifically, we realize the alignment by decomposing a GNN into two sub-components": a) a featurizer GNN g G - Ge aiming to identify the desired G,: b) a classifier GNN fe Ge + y' that predicts the label Y based on the estimated Go. where Go refers to the space of subgraphs of G. Formally, the learning objectives of fe and g can be formulated as:
max 9 I(Ga: Y), s.t. G. I E, G. = gGG),
where maximizing I I(G:; Y) is equivalent to minimizing a variational upper bound of R(fo(G.)) [3, 120] that takes G. as inputs to predict label Y for G through fe and g. and G. is the estimated subgraph containing the information about C' and hence needs to be independent of E. Moreover, the extracted G2 can either shares the same graph space with input G or has its own space with latent node and edge features, depending the specific graph generation process. In practice, architectures from the literature of interpretable GNNs are compatible with CIGA [122], hence can serve as practical choices for the implementation of CIGA. More details are given in Appendix F.
Although we can technically align with the two causal mechanisms with g and fe, trivially optimizing this architecture cannot satisfy G_ 1 E. Formally, merely maximizing I(G Y) may include a subgraph from G. in G. since G. also shares certain mutual information with Y. Moreover, the unavailability of E prevents the direct usage of E in enforeing the independence that is often adopted by previous methods [4, 49, 81, 31, 93], making the identification of Ge more challenging.
Optimization objective. To mitigate this issue, we need to find and translate other properties of Ge into some differentiable and equivalent objectives to satisfy the independence constraint G. 1 E. The goal of the desired objective. We begin by considering a simplistic setting where all the invariant subgraphs Ge have the same size 8c, i.e., |Grl = S.¹. When maximizing I(G Y) in Eq. 1, both FIIF and PIIF can introduce part of G, into Ge. In FIFF (Fig, 2(b)), as Ge already contains the maximal possible information in G about Y, G. is solution to max Y.) However, some subgraph of G. can be replaced by some subgraph of G. that is equally informative about Y. In PIIF (Fig. 2(c)), there also exists some subgraph of G, that contains additional information about Y than G., hence G. is more likely to involve some subgraph of G.. Thus, the new objective needs to eliminate the auxiliary subgraphs of G. from G, such that the estimated G. can only contain Ge.
An important property of Ge- Under both FIIF and PIIF SCMs (Fig. 2). for G2,, G that relate to the same causal factor e under two environments ej and 62, the desired G G in e and eg tend to have high mutual information, i.c., (G G E arg max I (h) G.?). While for G
'The encoder of the GNN in CIGA can be regarded as composition of g and the graph encoder in fc. 'Throughout the paper. we use generalized set operators for the ease of understanding. They can have multiple implementations in terms of nodes, edges or attributes.

---

and another Go corresponding to a different c' * c. under the same environment 61, including any subgraph from G in ,2, C will enlarge their mutual information, or in other words, (G C arg min ( G Thus, we can derive an important property of G.. that is, Vε1, e2 E Eail
G E arg max I(G C IC - c) - I(G -= #c).
where G and T are the estimated invariant subgraphs corresponding to the same causal factor under environment 6 and e2. respectively, while G corresponds to different causal factor c'.
Deriving CIGAv/ based on the identified property G.. practice, C' is not given. Nevertheless, since C and Y shares a stable causal relationship in both FIIF and PIIF SCMs, Y can serve proxy of C' in Eq. 2. Moreover, as Eq. 2 holds for any Vei, C2 E Eall the environment superscripts can be eliminated without affecting Eq. 2. Furthermore, when both I(G2: ; G [C = c) and I(C:: Y) are maximized, I( G22 IC = é' d' * c) is automatically minimized, otherwise all classes will collapse to trivial solutions which is contradictory given I I(G:: Y) being maximized. Therefore, we can derive an alternative objective to Eq. 1 by leveraging Eq. 2 to replace the independence condition:
(CIGAv1)
max (GGs (G);)), s.t. Go E arg max fe.8
T(G.; Gol)),))))
8.
where G g(G) and G ~ P(GJY), i.e., G is sampled from training graphs that share the same label Y as G. In Theorem 3.1, we show how Eq. 3 is equivalent to Eq. 1. Nevertheless, Eq. 3 requires a strong assumption on the size of Ge- However, the size of Ge usually unknown or changes for different Cs. In this circumstance, maximizing Eq. 2 without additional constraints will lead to the presence of part of G2 in Ge. For instance, G. G' is trivial solution to Eq. 3 when se
Deriving CIGAv2 by resolving size constraint on G. in CIGAvI. To this end, we further resort to the properties of G.. In both FIIF and PIIF SCMs (Fig. 2), G, and Ge can share certain overlapped information about Y. When maximizing [G G.lY) and I[Ge; Y). the appearance of partial G, in G. will not affect the optimality. However, it can reduce the mutual information between the left part G. = G G. and i.e., T(G,;; Y). Therefore, by maximizing T(G,; Y), we can reduce including part of G. into G.. Meanwhile, to avoid trivial solution that G. C G. during maximizing G Y), we can leverage the better clustering property of G. implied by Assumption 2.4 to derive the constraint I[ Y) < T(G.;)). Thus, we can obtain
objective CIGAv2 follows:
maxf.. (GGo;))= + (G.;)) Y), s.l. Go E arg gax
(4)
(CIGAv2)
I(G.;)) & (( G. = G GGG).
where G. = g(G), Go = g)G) and T ~ P(G]Y), i.e., T is sampled from training graphs that share the same label Y as G. We also prove the equivalence between Eq. 4 and Eq. in Theorem 3.1.
3.3 Theoretical Analysis and Practical Discussions
Theorem 3.1 (CIGA Induces Invariant GNNs). Given a set of graph datasets {D*), and environ- ments Eall that follow the same graph generation process in Sec. 2.2, assuming that (a) f and f in Assumption 2.1 are invertible, (b) samples from each training environment are equally distributed, (D.l = (Dal, Vē, ē E Em then:
(i). 1f Ser then each solution to Eq. 3, elicits an invariant GNN (Def. 2.5).
(ii). Each solution to Eq. 4, elicits an invariant GNN (Def. 2.5).
We prove Theorem 3.1 (i) and (ii) in Appendix E.2, E.3, respectively.
Practical implementations of CIGA objectives. After showing the power of CIGA, we introduce the practical implementations of CIGAvI and CIGAv2 objectives. Specifically, an exact estimate of the second term T[G G. Y) could be highly expensive [96, 8). However, contrastive learning with supervised sampling provides practical solution for the approximation [42, 20, 82, 96, 8]:
I(G G.G: x (,. log
(5)
é hac + DM e alha. hoy)
7

---

Table I: OOD generalization performance on structure and mixed shifts for synthetic graphs.
SPMOTIE-STRUC"
SPMOTII-MIXED' BIAS=0.60
B1AS=0.33
BIAS=0.60
BIAS=0.90
BIAS=0.33
BIAS=0.90
AVG
ERM
(3.50)
55.48 (4.84)
49.64
58.18 (4.30)
(8.17)
41.36 (3.29)
52.24
ASAP
64.87 (13.8)
64.85 (10.6)
57.29 (14.5)
66.88 (15.0)
59.78 (6.78)
50.45 (4.90)
60.69
58.73 (11.9)
48.72 (14.8)
(9.39)
67.28 (4.06)
(14.1)
38.58 (5.88)
$1.14
IRM
57.15 (3.98)
61.74
45.68 (4.88)
(1.97)
49.29 (3.67)
40.73 (1.93)
52.13
V-REX
54.64 (3.05)
53.60 (3.74)
48.86 (9.69)
(5.93)
48.25 (2.79)
43.27 (1.32)
$1.07
EIIL
56.48 (2.56)
60.07 (4.47)
45.14 (6.54)
53.91 (3.15)
48.41 (5.53)
41.75 (4.97)
52.73
IB-IRM
58.30 (6.37)
54.37 (7.35)
(2.11)
50.83 (1.51)
40.27 (3.68)
51.10
CNC
70.44 (2.55)
66.79 (9.42)
50.25 (10.7)
65.75 (4.35)
59.27 (5.29)
41.58 (1.90)
59.01
CIGAVI
71.07 (3.60)
63.23 (9.61)
51.78 (7.29)
74.35 (1.85)
64.54 (8.19)
49.01 (9.92)
62.33
CIGAV2
77.33 (9.13)
69.29 (3.06)
63.41 (7.38)
72.42 (4.80)
(7.54)
54.25 (5.38)
ORACLE (LID)
88,70 (0.17)
88.73 (0.25)
HHigher accuracy and lower variance indicate better OOD generalization ability.
where positive samples (Ge, G.) are the extracted subgraphs of graphs that share the same label as G. negative samples are those having different labels, (GI)'= [/])"=>y -Y) is the push-forward distribution of P = Y) by featurizer y. P(G Y) refers to the distribution of G given the label Y, P(G Y) refers to the distribution of G given the label that is different from Y, hhg. h,g lig: are the graph presentations of the estimated subgraphs, and Φ is the similarity metric for graph representations. As M - cc, Eq. 5 approximates I(G;; G.\Y), which can be regarded as non- parameteric resubstitution entropy estimator via the von Mises-Fisher kernel density [1, 41, 101]. Thus, plugging it into Eq. 3 and Eq. 4 can relieve the issue of approximating (Go; GolY) in practice.
To implement I G Y) given the constraint I( Y) I ((GaY) in CIGAv2, a practical choice is to adopt hinge loss that implement the constrained / (G,;; Y) as Rg I[RR, S RRa)) where N is the number of samples, Il is an indicator function that outputs when the inner condition is satisfied otherwise 0, and RG, and RG. are the empirical risk vector of the predictions for each sample based on the corresponding G. and G... More implementation details be found in Appendix F.
Discussions and implications generalization is not new in the literature [27, 61, 124], previous methods cannot yield OOD guaran- tees in graph circumstances due to the highly non-lincarity and the unavailability of domain labels E. In particular, CIGA can be reduced to directly applying contrastive learning when without the decomposition for causal algorithmic alignment. However, in the experiments we found that merely using the contrastive objective, i.e., CNC [124], yields unsatisfactory OOD generalization performance, which further implies the necessity of the decomposition in CIGA.
CIGA. Although using contrastive learning to improve OOD
Moreover, the architecture of CIGA can have multiple other implementations for both the featurizer and classifier, such as identifying G. at the latent space [86, 87J. Since we cannot enumerate every possible implementation, in this work we choose interpretable GNN architectures as a prototype validation for CIGA and leave more sophisticated architectures as future works. particular, when optimized with ERM objective, CIGA can be reduced to interpretable GNNs. However, merely using interpretable GNNs such as ASAP [78], GIB [120] or DIR [104] cannot yield satisfactory OOD performance. As shown in Table 1(b) and discussed in Appendix. D.4, GIB can only work for FIIF, while DIR cannot yield OOD guarantees for neither FIIF and PII SCMs. These results are also empirically validated in the experiments. We provide more detailed discussions in Appendix B.
Empirical Studies
We conduct extensive experiments with 16 datasets verify the effectiveness of CIGA.
Datasets. We use the SPMotif datasets from DIR [104] where artificial structural shifts and graph size shifts are nested (eMotif--ttuuc) Besides, we construct a harder version mixed with attribute shifts (SPMotif-Mixed). To examine CIGA real-world scenarios with more complicated relationships and distribution shifts, we also use DrugOOD [40] from Al-aided Drug Discovery with Assay, Scaffold, and Size splits, convert the ColOTedMNIST from IRM [4] using the algorithm from Knyazev al. [46] inject attribute shifts, and split Graph-SST SST [122] to inject degree biases. To compare with previous specialized OOD methods for graph size shifts [113, 11], we use the datasets in Bevilacqua al. [11] that are converted from TU benchmarks [67]. More details can be found in Appendix G.
Baselines and our methods. Besides the ERM, we also compare with SOTA interpretable GNNs, GIB [120], ASAP Pooling [78], and DIR [104], to validate the effectiveness of the optimization
8

---

Table 2: OOD generalization performance on complex distribution shifts for real-world graphs.
DATASETS
DRUG-ASSAY
DRUG-SCA
DRUG-SIZE
CMNIST-sP
GRAPH-SSTS
TWITTER
AvG (RANK)*
ERM
71,79 (0.27)
68.85 (0.62)
66.70 (1.08)
(5.46))
43.89 (1.73)
60.81 (2.05)
54,33 (6.00)
ASAP
70.51 (1.93)
66.19 (0.94)
64.12 (0.67)
10.23
44.16 (1.36)
60.68 (2.10)
52.65 (8.33)
GIB
63.01 (1.16)
62.01 (1.41)
55.50 (1.42)
(3.91)
38.64 (4.52)
48.08 (2.27)
(70.0
DIR
(1.40)
63,91 (1.36)
(1.40
15.50 (8.65)
(1.12
59.85 (2.98)
51.51 (9.33)
72.12(0049)
(0.65)
66.54
31.58 (9.52)
43.69
(1.20))
57.69 (4.50)
V-REX
(1.25)
68.92 (0.98)
66.3 (0. 74)
10.29 (0.46)
43.28 (0.52)
63.21 (1.57)
54.01 (6.17)
BIIL
(0.47)
68.45 (0.53)
66.38 (0. (0.66)
30.04 (10.9)
42.98 (1.03)
62.76 (1.72)
57.20 (5.33)
IB-IRM
72.50 (0.49)
68.50 (0.40)
(0.28)
39.86 (10.5)
40.85 (2.08)
61.26 (1.20)
58.27 (5. 33)
CNC
72.40 (0.46)
67.24 (0.90)
65.79 (0.80)
12.21 (3.85)
42.78 (1.53)
61.03 (2.49)
53.56 (7.50)
CIGAVI
72.71 (0.52)
69.04 (0.86)
67.24 (0.88)
19.77 (17.1)
44.71 (1.14)
63.66 (0.84)
56.19 (2.50)
CIGAY2
73.17 (0.39)
69.70 (0.27)
67.78 (0.76)
44.91 (4.31)
45.25 (1.27)
64.45 (1.99)
60.88 (1.00)
ORACLE (IID)
85.56 (1.44)
84.71 (1.60)
85.83 (1.31)
62.13 (0.43)
48.18 (1.00)
64.21 (1.77)
Averaged rank is also reported in the blankets because of dataset heterogeneity, Lower rank is better.
objective in CIGA. We use the same selection ratio (i.e.. se) for all models. Moreover, to validate the effectiveness of the decomposition in CIGA, we compare CIGA with SOTA OOD objectives including IRM [4], v-Rex [49] and IB-IRM [2], for which we apply random environment partitions following [23]. We also compare CIGA with EIIL. [23] and CNC [124] that do not require environ- ment labels, where CNC [124] has a more sophisticated contrastive sampling strategy for combating subpopulation shifts. More implementation and comparison details are deferred to Appendix G.2.
Evaluation. We report the classification accuracy for all datasets, except for DrugOOD datasets where we use ROC-AUC following [40], and for TU datasets where we use Matthews correlation coefficient following [11]. We repeat the evaluation multiple times, select models based on the validation performances, and report the mean and standard deviation of the corresponding metric. For each dataset, we also report the "Oracle" performances that run ERM on the randomly shuffled data.
OOD generalization performance on structure and mixed shifts. In Table 1, we report the test accuracy of each method, where we omit GIB due its poor convergence. Different biases indicate different strengths of the distribution shifts. Although the training accuracy of most methods converges more than 99%, the test accuracy decreases dramatically as the bias increases and as more distribution shifts are mixed, which concurs with our discussions in Sec. 2.3 and Appendix D. Due to the simplicity of the task as well as the relatively high support overlap between training and test distributions. interpretable GNNs and OOD objectives can improve certain OOD performance, while they can have high variance since they donot have OOD generalization guarantees, In contrast, CIGAvI and CIGAv2 outperform all of the baselines by significant margin up to 10% with lower variance, which demonstrates the effectiveness and excellent OOD generalization ability of CIGA.
OOD generalization perfor- mance realistic shifts. In Table 2 and Table 3, we exam- ine the effectiveness of CIGA in real-world data and more com- plicated distribution shifts. Both averaged accuracy and ranks are reported because of the dataset heterogeneity, Since the tasks are harder than synthetic ones, inter- pretable GNNs and OOD objec- tives perform similar to or even under-perform the ERM base- lines, which also consistent to the observations in non-linear benchmarks [34, 40]. However, both CIGAvI and CIGAv2 con-
Table 3: 00D generalization performance on graph size shifts for real-world graphs in terms of Matthews correlation coefficient.
DATASETS
NCII
NC1109
PROTEINS
DD
AvG
ERM
0.15 (0.05)
D.16 (0.02)
0.22 (0.09)
0.27 (0.09)
0,20
ASAP
0.16 (0.10)
0.15 (0.07)
(0.16)
0.21 (0.08)
0.19
GIB
0.13 (0.10)
0.16 (0.02)
0.19 (0.08)
0.01 (0.18)
0.12
DIR
0.21 (0.06)
0.13 (0.05)
(0.144
0.20 (0.10)
0.20
IRM
0.17
(D.0)
0.21 (0. (0.09)
0.22 (0.08)
V-REX
0.15
0.15 (0.04)
0.22 (0.06)
0.21 (0.07)
0.18
BILL
0.14 (0.03)
0.16
0.20 (0.05)
0:23 (0.10)
0.19
IR-IRM
(..2()
D.15 (0.06)
0.21 (0.06)
(0.13)
CNC
0.104(0.04)
0.16 (0.04)
0.19 (0.08)
0.27 (0.13)
0.20
WI. KERNEL
0.39 (0.00)
0.21 (0.00)
0.00 (0.00)
0.00 (0.000000)
0.15
GC KERNEL
0.02 (0.00)
(0.00)
0.29 (0.00)
0.00 (0.00)
0.08
P
(0.08)
0.25 (0.06)
0.12
0.23 (0.08)
0.19
FEIN
(0.04)
0.18 (0.04)
(0.11)
(0.06)
I TRIGIN
0.26 (0.05)
0.20 (0.04)
0.25 (0.12)
0.20 (0.05)
0.23
CIGAVI
0.22 (0.07)
0.23 (0.09)
0.40 (0.06)
0.29 (0.08)
0.29
CIGAV2
0.27 (0.07)
0.22 05.05)
0.31 (0.12)
0.26 (0.08)
0.27
ORACLE (II))
0.32 (0.05)
0.37 (0.06)
0.39 (0.09)
0.33 (0.05)
sistently and significantly outperform previous methods, including previous specialized methods GNNs [11] for combating graph size shifts, demonstrating the generality and superiority of C.GA.
Comparisons with advanced ablation variants. As discussed in Sec. 3.3, CIGA can be reduced to interpretable GNNs and contrastive learning approaches. However, across all experiments, we can observe that neither the advanced interpretable GNNs (DIR) nor sophisticated contrastive objectives with specialized sampling strategy (CNC) can yield satisfactory OOD performance, which serves as strong evidence for the necessities of the decomposition as well as the objective in CIGA. Furthermore, although CIGAvI can outperform CIGAv2 when may have a relatively accurate

---

matthees correlation coefiic ceeeeeet
71.0
105t aMC
OGAN
alpha
alpha
aloha
(a) SPMetif-Mixed (bias=0.9)
(b) DrugOOD-Scafiin
(c) NC1109
Figure Hyperparameter sensitivity analysis on the coefficient of contrastive loss (a)).
methhews correlation coeffice coeffictet
am
1055
613
35
beta
beta
beta
(a) SPMotif- (bias=0.9, a=4) (b) DrugOOD-Scafoold (a=1)
(c) NCT109 (a=1)
Figure 5: Hyperparameter sensitivity analysis on the coefficient of hinge loss (3).
Se. the improvements in CIGAv1 not as stable CIGAv2 or even unsatisfactory when the assumption is violated. This phenomenon also reveals the superiority of CIGAv2 in practice.
Hyperparameter sensitivity analysis. To examine how sensitive CIGA is to the hyperparamters a and / for contrastive loss and hinge loss, respectively. We conduct experiments based on the hardest datasets from each table (i.e., SPMotif-Mixed with the bias of 0.9, DrugOOD-So --cfffold and the NCT109 datasets from Table 1, Table 2, and Table 3, respectively.) with different a and 3. When specific value under which the model has relatively good
changing the value of 3, we fix the performance (but not the best, to fully examine the robustness of CIGA in practice).
The results shown in Fig. 4 and Fig. 5. It can be found that both CIGAvI and CIGAv2 are robust to different values of a and B, respectively, across different datasets and distribution shifts. Besides, the results also reflect the effects of the additional penalty terms in CIGA. For example, in Fig. 16, when is too small, the invariance of the identified invariant subgraphs G may not be guaranteed, resulting worse performances. Similarly, as shown in Fig. 17, when / becomes too small, some part of the spurious subgraph may still appear in the estimated invariant subgraphs, which yields worse performances. Besides, when and 8 become too large, the optimization of CIGA can be affected due their intrinsic conflicts with ERM, hence a better optimization scheme for CIGA can be promising future direction [18]. We provide more details and additional analysis on the efficiency of CIGA and single environment OOD generalization performance of CIGA in Appendix G.4, as well as the visualization examples of the identified invariant subgraph in Appendix G.5.
Conclusions
We studied the OOD generalization on graphs via graph classification, and propose a new solution CIGA through the lens of causality. By modeling potential distribution shifts on graphs with SCMs, we generalized and instantiated the invariance principle graphs, which was shown to have promising theoretical and empirical OOD generalization ability under a variety of distribution shifts.
Acknowledgments and Disclosure of Funding
We thank the reviewers for their valuable comments. This work was supported by GRF 14208318 from the RGC of HKSAR and CUHK direct grant 4055146 TL was partially supported by Australian Research Council Projects DP180103424, DE-1101111473 IC- 19-190100031, 20P2220102121. and FT-2201 00318. YZ and BH were supported by the RGC Early Career Scheme No. 22200720, NSFC Young Scientists Fund No. 62006202, Guangdong Basic and Applied Basic Research Foundation No. 2022A15 5501 1652, and Tencent AI Lab Rhino- Bird Gift Fund.
10

---

References
[1] I. Ahmad and P.-E. Lin. A nonparametric estimation the entropy for absolutely continuous distributions (conresp.). IEEE Transactions on Information Theory, 22(3):372 -75, 1976.
[2] K. Ahuja, E. Caballero, D. Zhang, J.-C. Gagnon-Audet, Y. Bengio. I. Milliagkas, and I. Rish. Invariance principle meets information bottleneck for out-of-distribution generalization. In Advances in Neural Information Processing Systems, 2021.
[3] A. A. Alemi, I. Fischer, and J. V. D. and. Deep variational information bottleneck. In International Conference on Learning Representations, 2017.
[4] M. Arjovsky, L. Bottou, I. Gulrajani, and D. Lopez-Paz. Invariant risk minimization. arXiv 2019.
preprint, utXiv:1907.022:
[5] B. Aubin, A. Stowik, M. Arjovsky, L. Bottou, and D. Lopez-Paz. Linear unit-tests for invariance discovery. arXiv preprint 0rXiv:2102.10866 2021.
[6] P. W. Battaglia, Pascanu, M. Lai, J. Rezende, and K. Kavukeuoglu. Interaction networks for learning about objects, relations and physics. In Advances in Neural Information Processing Systems, pages 4502-4510, 2016.
[7] S. Beery, G. V. Horn, and P. Perona. Recognition in terra incognita. In Computer Vision European Conference, Part XVI, volume 11220, pages 472-489, 2018.
[8] M. I. Belghazi, A. Baratin, S. Rajeshwar, S. Ozair, Y. Bengio, A. Courville, and D. Hjelm. Mutual information neural estimation. In International Conference on Machine Learning, volume 80, pages 531-540, 10-15 Jul 2018.
[9] A. Bellot and M. van der Schaar. Generalization and invariances in the presence of unobserved confounding. arXiv preprint, arXiv:2007 10653, 2020.
[10] Y. Bengio, T. Deleu, N. Rahaman, N. R. Ke, S. Lachapelle, O. Bilaniuk, A. Goyal, and C. J. Pal. A meta-transfer objective for learning to disentangle causal mechanisms. In International Conference on Learning Representations, 2020.
[11] B. Bevilacqua, Y. Zhou, and B. Ribeiro. Size-invariant graph representations for graph classification extrapolations. In International Conference on Machine Learning, volume 139, pages 837-851, 28-24 Jul 2021.
[12] R. S. Bohacek, C. McMartin, and W. C. Guida. The art and practice of structure-based drug design: molecular modeling perspective. Medicinal Research Reviews, 16(1):3-50, 1996.
[13] Burshtein, V. Pietra, D. Kanevsky, and A. Nadas. Minimum impurity partitions. The 1992.
Annals of Statistics, 20(3):
[14] S. Chang, Y. Zhang, M. Yu, and T. S. Jaakkola. Invariant rationalization. In International Conference on Machine Learning, volume 119, pages 1448-1458, 2020.
[15] O. Chapelle, Schölkopf, and Zien. Semi-Supervised Learning. The MIT Press, 2006.
[16] P.-H. Chen, C.-J. Lin, and B. Schölkopf. A tutorial v-support vector machines. Applied Stochastic Models in Business and Industry, 21 2005.
[17] Y. Chen, H. Yang, Y. Zhang, K. Ma, Liu, B. Han, and J. Cheng. Understanding and improving graph injection attack by promoting unnoticeability. In International Conference on Learning Representations, 2022.
[18] Y. Chen, K. Zhou, Y. Bian, B. Xie, Ma, Y. Zhang, H. Yang, B. Han, and J. Cheng. Pareto invariant risk minimization. arXiv preprint, arXiv:2206.07766. 2022.
[19] Z. Chen, L. Chen, S. Villar, and J. Bruna. Can graph neural networks count substructures? In Advances in Neural Information Processing Systems, 2020.
[20] S. Chopra, R. Hadsell, and Y. LeCun. Learning a similarity metric discriminatively, with application to face verification. In 2005 IEEE Computer Society Conference Computer Vision and Puttern Recognition (CVPR 2005), 20-26 June 2005, San Diego, CA, USA, pages 539-546, 2005.
[21] C. Chuang, A. Torralba, and S. Jegelka. Estimating generalization under distribution shifts via domain-invariant representations. In International Conference on Machine Learning, volume 119, pages 1994-1994. PMLR, 2020.

---

[22] T. M. Cover and J. A. Thomas. Elements of Information Theory (Wiley Series in Telecommuni- cations and Signal Processing). Wiley-Intersciene USA, 2006. ISBN 0471241954.
[23] E. Creager, J. Jacobsen, and R. S. Zemel. Environment inference for invariant learning. In International Conference on Machine Leurning, volume 139, pages 2189-2200, 2021.
[24] A. J. DeGrave, J. D. Janizek, and S. Lee. Al for radiographic COVID-19 detection selects shortcuts over signal. Nature Machine Intelligence, 3(7)x610-619 2021.
[25] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 4171-4186, 2019.
[26] L. Dong, F. Wei, C. Tan, D. Tang. M. Zhou, and K. Xu. Adaptive recursive neural network for target-dependent twitter sentiment classification. In Anmual Meeting of the Association for Computational Linguistics, pages 49-54, 2014.
[27] Q. Dou, D. C. de Castro, K. Kamnitsas, and B. Glocker. Domain generalization via model- agnostic learning of semantic features. In Advances in Neural Information Processing Systems, pages 6447-6458, 2019.
[28] V. P. Dwivedi, C. K. Joshi, T. Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks, arXiv preprint, arXiv:2003. 2020.
[29] M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[30] O.-E. Ganea, X. Huang, C. Bunne, Y. Bian, R. Barzilay, T. S. Jaakkola, and A. Krause. Independent -quiiaaqua models for end-to-end rigid protein docking. In International Conference on Learning Representations, 2022.
[31] Y. Ganin, E. Ustinova, H. Ajakan, P. Germain, H. Larochelle, F. Laviolette, M. Marchand, and
V. S. Lempitsky. aavasnaadversariil training of neural networks. Journal of Mache Learning Research, 17:59:1-59:35: 2016.
[32] M. Gardner, Grus, M. Neumann, O. Tafjord, P. Dasigi, N. F. Liu, M. E. Peters, M. Schmitz, and L. Zettlemoyer. Allennlp: A deep semantic natural language processing platform. arXiv preprint,
2018.
[33] R. Geirhos, J. Jacobsen, C. Michaelis, R. S. Zemel, W. Brendel, M. Bethge, and F. A. Wich- mann. Shortcut learning deep neural networks. Nature Machine Intelligence, 2(1 (211))6656677 2020.
[34] I. Gulrajani and D. Lopez-Paz. In search of lost domain generalization. In International Conference on Learning Representations, 2021.
[35] W. L. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1024-1034, 2017.
[36] K. Han, B. Lakshminarayanan, and J. Z. Liu. Reliable graph neural networks for drug discovery under distributional shift. In NeurlPS 2021 Workshop on Distribution Shifts: Connecting Methods and Applications, 2021.
[37] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems, 2020.
[38] K. Huang, T. Fu, W. Gao, Y. Zhao, Y. H. Roohani, J. Leskovee, C. W. Coley, C. Xiao, J. Sun, and M. Zitikk Therapeutics data commons: Machine learning datasets and tasks for drug discovery and development. In Advances in Neural Information Processing Systems Datasets and Benchmarks Track (Round 1), 2021.
[39] S. loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, volume 37, pages 448-456, 2015.
[40] Y. Ji, L. Zhang, J. Wu, B. Wu, L.-K. Huang, T. Xu, Y. Rong, L. Li, J. Ren, D. Xue, H. Lai, S. Xu, J. Feng. W. Liu, P. Luo, S. Zhou, J. Huang, P. Zhao, and Y. Bian. DrugOOD: Out-of- Distribution (OOD) Dataser Curator and Benchmark for Al-aided Drug Discovery - A Focus on Affinity Prediction Problems with Noise Annotations. arXiv preprint, arXiv:2201 00667, 2022.
12

---

[41] K. Kandasamy, A. Krishnamurthy, B. Poczos, L. Wasserman, and j. m. robins. Nonparametric von mises estimators for entropies, divergences and mutual informations. In Advances in Neural Information Processing Systems, volume 28, 2015.
[42] P. Khosla, P. Teterwak, C. Wang, A. Sarna, Y. Tian, P. Isola, A. Maschinot, C. Liu, and
D. Krishnan. Supervised contrastive learning. In Advances Neural Information Processing Systems, volume 33, pages 18661-18633, 2020.
[43] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
[44] T. N. Kipf and M. Welling. Variational graph auto-encoders. arXiv preprint, arXiv: 1.Xiv:1611.073000 2016.
[45] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017.
[46] B. Knyazev, G. W. Taylor, and M. R. Amer. Understanding attention and generalization in graph neural networks. In Advances in Neural Information Processing Systems, pages 4204 4214, 2019.
[47] P. W. Koh, S. Sagawa, H. Marklund, S. M. Xie, M. Zhang, A. Balsubramani, W. Hu, M. Ya- sunaga, R. L. Phillips, I. Gao, T. Lee, E. David, I. Stavness, W. Guo, B. Earnshaw, I. Haque, S. M. Beery, J. Leskovee, A. Kundaje, E. Pierson, S. Levine, C. Finn, and P. Liang. WILDS: A benchmark of in in-the-wild distribution shifts. In International Conference on Machine Learning,, pages 5637-5664, 2021.
[48] M. Koyama and S. Yamaguchi. Out-of-distribution generalization with maximal invariant predictor. arXiv preprint, arXiv:2008.0 018.8, 2020.
[49] D. Krueger, E. Caballero, Jacobsen, A. Zhang. J. Binas, D. Zhang, R. L. Priol, and A. C. Courville. dittr--disttibbtionn generalization via risk extrapolation (rex). In International Conference on Machine Learning, pages 5815-5826, 2021.
[50] J. V. Küggelgen, Y. Sharma, Gresele, W. Brendel, Schölkopf, M. Besserve, and Locatello. Self-supervised learning with data augmentations provably isolates content from style. In Advances in Neural Information Processing Systems, pages 16451-16467, 2021.
[51] Q. Li, Z.. Han, and X. Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In AAAI Conference on Artificial Intelligence, pages 3538-3545, 2018.
[52] Y. Li, X. Tian, M. Gong, Y. Liu, T. Liu, K. Zhang, and D. Tao. Deep domain generalization via conditional invariant adversarial networks. In European Conference on Computer Vision, pages 647-663, 2018.
[53] W. Lin, H. Lan, and B. Li. Generative causal explanations for graph neural networks. In International Conference on Machine Learning. pages 6666-6679, 2021.
[54] Y. Lin, H. Dong, H. Wang, and T. Zhang. Bayesian invariant risk minimization. In JEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16000-16009, 2022.
[55] Y. Lin, S. Zhu, and P. Cui. ZIN: when and how to learn invariance by environment inference? arXiv preprint arXiv:2203.055.
2022.
[56] S. Liu, H. Wang, W. Liu, J. Lasenby, H. Guo, and J. Tang. Pre-training molecular graph representation with 3d geometry. In International Conference on Learning Representations, 2022.
[57] L. Lovász and B. Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory. Series B, 96(6):933-99)) 07733997,222 2006.
[58] D. Luo, Cheng. D. Xu, W. Yu, B. Zong, H. Chen, and X. Zhang. Parameterized explainer for graph neural network. In Advances in Neural Information Processing Systems. pages 19620-19631, 2020.
[59] Luo, K. Yan, and Ji. Graphdf: A discrete flow model for molecular graph generation. In International Conference on Machine Learning, pages 7192-7203, 2021.
[60] K. Ma, H. Yang, H. Yang, T. Jin, P. Chen, Y. Chen, B. F. Kamhoua, and J. Cheng. Improving graph representation learning by contrastive regularization. arXiv preprint, arXiv:2101.11522 1.21.
13

---

[61] D. Mahajan, S. Tople, and A. Sharma. Domain generalization using causal matching. In International Conference on Machine Learning, pages 7313-7324, 2021.
[62] M. McPherson, L. Sovth-Lovin, and M. Cook. Birds of feather: Homophily in social networks. Annual Review of Sociology. 27(1):415-444, 2001.
[63] D. Mendez, A. Gaulton, A. P. Bento, J. Chambers, M. D. Veij, E. Felix, M. P. Magariños, J. F. Mosquera, P. Mutowo-Meullenet, M. Nowotka, M. Gordillo-Maraión, M. I. Hunter, L. Junco, G. Mugumbate, M. Rodríguezz-López F. Atkinson, N. Bosc, C. J. Radoux, A. Segura- Cabrera, A. Hersey, and A. R. Leach. Chembl: towards direct deposition of bioassay data. Nucleic Acids Research, 4/DDubbas-IsseeeDDD000----
2019.
[64] S. Miao, M. Liu, and P. Li. Interpretable and generalizable graph learning via stochastic attention mechanism. In International Conference on Machine Learning, pages 15524-15543, 2022.
[65] S. Mika, G. Ratsch, J. Weston, B. Scholkopf, and K.-.. Mullers. Fisher discriminant analysis with kemels. In Neural networks for signal processing IX: Proceedings of the 1999 IEEE signal processing society workshop (cat. no. 98th8468), pages 41 41-48, 1999.
[66] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference on Artificial Intelligence, pages 4602 0002-4609,440 2019.
[67] C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint, arXiv:2007.0866 2020.
[68] C. Morris, Y. Lipman, H. Maron, B. Rieck, N. M. Kriege, M. Grohe, M. Fey, and K. M. Borgwardt. Weisfeiler and leman go machine learning: The story so far. arXiv preprint, mrXiv:2112.0990 2021.
[69] K.-R. Muller, S. Mika, G. Ratsch, K. Tsuda, and B. Scholkopf. An introduction kernel- learning algorithms. IEEE transactions on neural networks, 142)):81-201) 2001.
[70] R. L. Murphy, B. Srinivasan, V. A. Rao, and B. Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pages 4663-4673, 2019,
[71] V. Nagarajan, A. Andreassen, and B. Neyshabur. Understanding the failure modes of out- of-distribution generalization. In International Conference on Learning Representations, 2021.
[72] H. Namkoong and J. C. Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In Advances in Neural Information Processing Systems, pages 2208-2216 2016.
[73] A. Paszke, S. Gross, F. Massa, A. Lerer. J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Te- jani. S. Chilamkurthy, B. Steiner, L. Fang, Bai, and S. Chintala. Pytorch: An imperative style, Srigh-peffrrance deep learning library. In Advances in Neural Information Processing Systems, pages
2019.
[74] J. Pearl. Causality. Cambridge University Press, 2 edition, 2009.
[75] J. Pearl. The seven tools of causal inference, with reflections on machine learning. Communi- cations of the ACM, 62(3):54 60, feb 2019. ISSN 0001-0782.
[76] J. Peters, P. Bühlmann, and N. Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society: Series (Statistical Methodology), 7854771711 2016.
[77] J. Peters, D. Janzing, and B. Schlkopf. Elements of Causal Inference: Foundations and Learning Algorithms. The MIT Press, 2017. ISBN 0262037319.
[78] E. Ranjan, S. Sanyal, and P. P. Talukdar. ASAP: adaptive structure aware pooling for learning hierarchical graph representations. In AAAI Conference Artificial Intelligence, pages 5470-5477, 2020.
[79] M. Rojas-Carulla, B. Schölkopf, R. Turner, and Peters. Invariant models for causal transfer learning. Journal of Machine Learning Research, 19(36):1-34, 2018.
14

---

[80] E. Rosenfeld, P. K. Ravikumar, and A. Risteski. The risks of invariant risk minimization. In International Conference on Learning Representations, 2021.
[81] S. Sagawa", P. W. Koh* T. B. Hashimoto, and P. Liang. Distributionally robust neural networks. In International Conference on Learning Representations, 2020.
[82] R. Salakhutdinov and G. E. Hinton. Learning& a nonlinear embedding by preserving class neighbourhood structure. In International Conference Artificial Intelligence and Statistics, pages 412-419, 2007.
[83] A. Sanchez-Gonzalez N. Heess, Springenberg, J. Merel, M. A. Riedmiller, R. Hadsell, and P. W. Battaglia. Graph networks as learnable physics engines for inference and control. In International Conference on Machine Learning, pages 4467-4476, 2018.
[84] A. Santoro, F. Hill, D. G. T. Barrett, A. S. Morcos, and T. P. Lillicrap. Measuring abstract reasoning in neural networks. In International Conference on Machine Learning, volume 80,
pages 4477-4486, 2018.
[85] D. Saxton, F. Grefenstette, F. Hill, and P. Kohli. Analysing mathematical reasoning abilities of neural models. International Conference on Learning Representations, 2019.
[86] B. Schölkopf. Causality for machine learning. arXiv preprint, arXiv:1911.10500 2019.
[87] B. Schölkopf, F. Locatello, S. Bauer, N. R. Ke, N. Kalchbrenner, A. Goyal, and Y. Bengio. Toward causal representation learning. Proceedings of the IEEE, 109(5):12-6334 2021.
[88] O. Sener and V. Koltun. Multi-task learning as multi-objectivve optimization. Advances in Neural Information Processing Systems, pages 525-536, 2018.
[89] T. A. Snijders and K. Nowicki. Estimation and prediction for stochastic blockmodels for graphs with latent block structure. In Journal of Classification, volume 14, pages 75-100, 1997.
[90] Socher, A. Perelygin, J. Wu, J. Chuang, C. D. Manning, A. Ng. and C. Potts. Recursive deep models for semantic compositionality over sentiment treebank. In Conference on Empirical Methods in Natural Language Processing, pages 1631-1642, 2013.
[91] N. Srivastava, G. E. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(1):1929-195)
2014.
[92] T. Sterling and J. J. Irwin. Zine 15 ligand discovery for everyone. Journal of Chemical Information and Modeling, 55(1 1):2324-2337, 2015.
[93] Sun and K. Saenko. Deep CORAL: correlation alignment for deep domain adaptation. In European Conference Computer Vision, pages 443-450, 2016.
[94] H. Tang, Z. Huang, J. Gu, B. Lu, and H. Su. Towards scale-invariant graph-related problem solving by iterative homogeneous gnns, In Advances Neural Information Processing Systems, 2020.
[95] N. Tishby, F. C. Pereira, and W. Bialck. The information bottleneck method, Annual Allerton Conference Communication, Control and Computing, pages 368-377, 1999.
[96] A. van den Oord, Y. Li, and O. Vinyals. Representation learning with contrastive predictive coding. arXiv preprint, 1rXiv:1807.10
2018
[97] V. Vapnik. Principles of risk minimization for learning theory. In Advances in Neural Information Processing Systems, pages 831-838, 1991.
[98] P. Velickovie, R. Ying, M. Padovano, R. Hadsell, and C. Blundell. Neural execution of graph algorithms. In International Conference on Learning Representattions, 2020.
[99] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In International Conference on Learning Representations, 2018
[100] J. Wang, C. Lan, C. Liu, Y. Ouyang. and T. Qin. Generalizing to unseen domains: A survey on domain generalization. In International Joint Conference on Artificial Intelligence, pages 4627-4635, 2021.
[101] T. Wang and P. Isola. Understanding contrastive representation learning through alignment and uniformity on the hypersphere. International Conference on Machine Learning, pages 9929-9939, 2020.
15

---

[102] B. Wu, Li, C. Hou, G. Fu, Y. Bian, L. Chen, and J. Huang. Recent advances in reliable deep graph learning: Adversarial attack, inherent noise, and distribution shift. arXiv preprint arXiv:2202.0711 14, 2022.
[103] Q. Wu, H. Zhang. J. Yan, and D. Wipf. Handling distribution shifts on graphs: An invariance perspective. In International Conference on Learning Representcatonss 2022.
[104] Y. Wu, X. Wang, A. Zhang, X. He, and T.-S. Chua. Discovering invariant rationales for graph neural networks. In International Conference on Learning Representations, 2022.
[105] L.-P. A. C. Xhonneux, A. Deac, Veličković, and Tang. How to transfer algorithmic reasoning knowledge to learn new algorithms? In Advances in Neural Information Processing Systems, pages 19500-19512, 2021.
[106] K. Xu, Li, Tian, Sonobe, K. Kawarabayashi, and Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pages 1449954555 2018.
[107] K. Xu, W. Hu, J. Leskovec, and Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[108] K. Xu, Li, M. Zhang, S. S. Du, K. Kawarabayashi, and S. Jegelka. What can neural networks reason about? In International Conference Learning Representations, 2020.
[109] K. Xu. M. Zhang, S. Jegelka, and K. Kawaguchi. Optimization of graph neural networks: Implicit acceleration by skip connections and more depth. In International Conference on Machine Learning, pages 11592-11602, 2021.
[110] K. Xu, M. Zhang. J. Li, S. S. Du, K. Kawarabayashi, and S. Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In International Conference on Learning Representations, 2021.
[111] M. Xu, L. Yu, Y. Song, C. Shi, S. Ermon, and J. Tang. Geodiff: A geometric diffusion model for molecular conformation generation. In International Conference on Learning Representations, 2022.
[112] H. Yang, K. Ma, and J. Cheng. Rethinking graph regularization for graph neural networks. In AAAI Conference on Artificial Intelligence, pages 4573-4581, 2021.
[113] G. Yehudai, E. Fetaya, E. Meirom, G. Chechik, and H. Maron. From local structures to size generalization in graph neural networks. In International Conference on Machine Learning, pages 11975-11986, 2021.
[114] R. Yeung. Information Theory and Network Coding. 01 2008. ISBN 978-0-387-79233-4
[115] Z. Ying, J. You, C. Morris, X. Ren, W. L. Hamilton, and J. Leskovec. Hierarchical graph repre- sentation learning with differentiable pooling. In Advances Neural Information Processing Systems, pages 4805-48480 4815, 2018.
[116] Z. Ying, D. Bourgeois, J. You, M. Zitnik, and J. Leskovee. Gnnexplainer: Generating explanations for graph neural networks. In Advances in Neural Information Processing Systems, pages 9240-9251, 2019.
[117] J. You, R. Ying, X. Ren, W. L. Hamilton, and J. Leskovec. Graphrn: Generating realistic graphs with deep regressiee models. In International Conference on Machine Learning, pages 5694-5703, 2018
[118] You, T. Chen, Y. Sui, Chen, Z. Wang, and Y. Shen. Graph contrastive learning with augmentations. In Advances in Neural Information Processing Systems, pages 5812-5823, 2020.
[119] Y. You. T. Chen, Y. Shen, and Z. Wang. Graph contrastive learning automated. In International Conference on Machine Learning, pages 12121-12132, 2021.
[120] J. Yu, T. Xu, Y. Rong, Y. Bian, Huang, and R. He. Graph information bottleneck for subgraph recognition. In International Conference on Learning Representations, 2021.
[121] J. Yu, J. Liang, and R. He. Finding diverse and predictable subgraphs for graph domain
generalization. arXiv preprint, arXiv:2206.09%: 09345, 2022.
[122] H. Yuan, H. Yu, S. Gui, and S. Ji. Explainability in graph neural networks: taxonomic survey, arXiv preprint, arXiv:2012. 2020.
16

---

[123] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Representations, 2017.
[124] M. Zhang, N. S. Sohoni, H. R. Zhang, C. Finn, and C. Ré. Correct-n-contrast: A contrastive approach for improving robustness to spurious correlations. arXiv preprint, arXiv:2203.01517, 2022.
[125] Y. Zhang, M. Gong, T. Liu, G. Niu, X. Tian, B. Han, B. Schölkopf, and K. Zhang. Ad- versarial robustness through the lens of causality. In International Conference Learning Representations, 2022.
[126] Zhao, T. des Combes, K. Zhang, and G. Gordon. On learning invariant representations for domain adaptation. In International Conference on Machine Learning, pages 7523-7532, 2019.
[127] Zhou, Y. Lin, W. Zhang, and T. Zhang. Sparse invariant risk minimization. In 39th International Conference on Machine Learning, pages 27222-27244, 2022.
[128] R. S. Zimmermann, Y. Sharma, Schneider, M. Bethge, and W. Brendel. Contrastive learning inverts the data generating process. In International Conference Machine Learning, pages 1 2021.
17

---

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] See Sec. B,4 in the appendix.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Sec. A in the appendix.
(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] See Sec. C and Sec. in the appendix.
(b) Did you include complete proofs of all theoretical results? [Yes] See Sec. E in the appendix.
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 as URL)? [Yes] The code and the other required materials are provided in https: tiggt cww/ htt//LaaaaeeCGaaa
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Sec. G.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Sec. G.
(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] See Sec. G.3.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If 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'l 're using/curating? [N/A] The data used are all publicly available datasets.
(e) Did you discuss whether the data you are 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, if applicable? [N/A] We didn't It conduct research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] We didn't ' conduct research with human subjects.
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A] We didn't 't conduct research with human subjects.
18


Reviews:
[{"review_id": "nLDNj69gWII", "reviewer": "Reviewer_tMnp", "summary": "The authors consider the problem of out-of-distribution generalization on graphs, where shifts in the distribution can change both the attributes and the structure of the graphs. They propose two causal DAGs describing the shift, and assume the existence of a subgraph which is invariant to the shift and that contains most of the information about the label. Then, they present two learning objectives to identify this critical subgraph which is then used for the label prediction. ", "questions": "1. What is the relationship between $E_G$ and $E$ ? I can see that $E_G \\subseteq E$ but if we replace G in the FIIF SCM with its $\\mathcal{G}$-Gen SCM, then: (1) there is no causal relationships between $E_G$ and $E$ and (2) $E_G \\perp E$, which is contradictory.\nCan't you simply remove the random variable $E_G$? \n2. From Assumption 2.1 we have $G = f_{gen}^G(G_C, G_S, E_G)$ and since $E_G \\subseteq E$ then the environment also causes G. This obviously would change the causal diagram since then there should be an arrow from the environment to G, changing all the causal models. Please clarify.\n\n", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "#### Strenghts\n1. The assumption of the presence of an invariant subgraph is interesting and reasonable, and it is in line with previous work.\n2. The empirical evaluation shows the effectiveness of the proposed approach.\n\n#### Weaknesses\n1. The learning objective assumes the presence of multiple training environments, and thus the proposed method would not work in the single environment setting.\n2.  The relationship between $E_G$ and $E$ is unclear, since they are not causally related. Also, since $E_G$ is an input of $ f_{gen}^G$, and $E_G \\subseteq E$ there should be an arrow from $E$ to $G$.\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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "_3N7KSxXut", "reviewer": "Reviewer_zrMs", "summary": "This paper discusses graph-level distribution shifts on graph neural networks. It propose a causal-based invariant learning objective based on contrastive learning and prove its equivalence/approximation of the designed invariance principles. Various experiments on synthetic and real-world shift demonstrate the effectiveness of CIGA.", "questions": "1. What's the accuracy or F1 measure on real-world graphs? It is hard to recognize the performance gap caused by distribution shifts. In other words, the negative effect of distribution shifts are not revealed in current table. \n2. What's the relatedness of graph property and proposed method / proof, maybe I am missing something during reading ( please refer to weakness 2 )  ", "limitations": "N.A.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths** \n1. This paper poses a great challenge towards existing OOD generalization algorithms on graphs and provide some sort explanation. \n3. The connection between semi-supervised contrastive learning and invariant in Eq.5 is sound.\n\n**Weaknesses** \n1. The results in the experiments are sometimes misleading. For example, in Table 3, when baselines are better, the bond font is still on proposed two methods. \n2. I read through main theorem 3.1 and its proof, most of the induction is around mutual information or information bottleneck, while the property of graph is rarely used. The author claims challenge of graph OOD is not environment label and convoluted causes of shift, while the proposed method seem to not that relevant / benefit from the nature of the graph.", "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": "HpFhRSN-bHX", "reviewer": "Reviewer_QGqs", "summary": "This paper studies the OOD generalization problem for graphs. It takes a causal view at the problem and proposes four assumptions to describe the graph generation process. Specifically, three factors C (invariant), S (varying), and E (environment) control the graph generation process. The assumptions include two types of distribution shifts in which 1) graph label Y is fully dependent on C; and 2) Y is spuriously correlated with environment E.\n\nBased on the assumptions, the authors decompose the graph learning problem into finding the an invariant subgraph $\\hat{G}_c$ and minimizing the risks on $\\hat{G}_c$, i.e., Equation (1). The remaining efforts are dedicated to resolve Equation (1)'s intractability. The main idea is to use supervised contrastive learning to maximize the agreement between the invariant part of graphs with the same label .\n", "questions": "Q1: since theoretical results mainly address the connection between the proposed method and definition2.5, it is crucial to understand the significance of definition 2.5. How is the minimax objective in definition2.5 relevant to finding the causal factor C in Figure2?\n\nQ2: in Line189-190, graph's complex properties of structures and features are identified as a key challenge for OOD generalization. It is unclear how does the proposed method resolve this challenge?\n", "limitations": "none", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n- OOD generalization for graphs is of high interest for the machine learning community. This paper present a thorough study from the causal view, which should enlighten future researchs in this field.\n- The idea is novel and motivated by theory.\n\n\n\n**Weaknesses:**\n\n- The method seems complex that includes two GNNs and three loss functions. It is unclear about the practical value of this method.\n\n- The presentation can be improved. \n    - Section3.2 is hard to parse. The reasoning process between the multiple objective functions is poorly organized and hard to evaluate.\n    - Some equations can be made clearer. For example, what does the C, C', c, c' in Equation (2) mean? Why is the risk term in Equation (1) replaced by mutual information in Equation (3)?", "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