Handling Distribution Shifts on Graphs: An Invariance Perspective
Authors: Qitian Wu
Hengrui Zhang
Junchi Yan
David Wipf
Venue: ICLR 2022 Poster (2022)
Keywords: Representation Learning on Graphs
Out-of-Distribution Generalization
Domain Shift
Graph Structure Learning
Invariant Models

Abstract: There is increasing evidence suggesting neural networks' sensitivity to distribution shifts, so that research on out-of-distribution (OOD) generalization comes into the spotlight. Nonetheless, current endeavors mostly focus on Euclidean data, and its formulation for graph-structured data is not clear and remains under-explored, given two-fold fundamental challenges: 1) the inter-connection among nodes in one graph, which induces non-IID generation of data points even under the same environment, and 2) the structural information in the input graph, which is also informative for prediction. In this paper, we formulate the OOD problem on graphs and develop a new invariant learning approach, Explore-to-Extrapolate Risk Minimization (EERM), that facilitates graph neural networks to leverage invariance principles for prediction. EERM resorts to multiple context explorers (specified as graph structure editers in our case) that are adversarially trained to maximize the variance of risks from multiple virtual environments. Such a design enables the model to extrapolate from a single observed environment which is the common case for node-level prediction. We prove the validity of our method by theoretically showing its guarantee of a valid OOD solution and further demonstrate its power on various real-world datasets for handling distribution shifts from artificial spurious features, cross-domain transfers and dynamic graph evolution.

Published as a conference paper at ICLR 2022
HANDLING DISTRIBUTION SHIFTS ON GRAPHS: AN INVARIANCE PERSPECTIVE
Qitian Wu"
Hengrui Zhang*
Shanghai Jiao Tong University echo7400s jtu. wtw.:du.uuuuu..... en
University Illinois at Chicago hzhan55@ui edu
Junchi Yan'
David Wipf
Shanghai Jiao Tong University yan junchiees jtu. edu.cn
Amazon daviwipfeamazon.co com
ABSTRACT
There is increasing evidence suggesting neural networks' sensitivity to distribution shifts, so that research on out-of dif-iiibiiittoo (OOD) generalization comes into the spotlight. Nonetheless, current endeavors mostly focus on Euclidean data, and its formulation for graph-structured data is not clear and remains under-explored, given two-fold fundamental challenges: 1) the inter-connection among nodes graph, which induces non-llD generation of data points even under the same environment, and 2) the structural information the input graph, which also informative for prediction. In this paper, we formulate the OOD problem graphs and develop a new invariant learning approach, Explore-to-EEtrapolaa Risk Minimization (EERM), that facilitates graph neural networks leverage invariance principles for prediction. EERM resorts to multiple context explorers (specified as graph structure editers in our case) that are adversarially trained to maximize the variance of risks from multiple virtual environments. Such a design enables the model extrapolate from a single observed environment which is the common case for node-level prediction. We prove the validity of our method by theoretically showing its guarantee of a valid OOD solution and further demonstrate its power on various real-world datasets for handling distribution shifts from artificial spurious features, cross-domain transfers and dynamic graph evolution'.
INTRODUCTION
As the demand for handling in-the-wild unseen instances draws increasing concerns, out-of- distribution (OOD) generalization (Mansour et al., 2009; Blanchard et al., 2011; Muandet et al., 2013; Gong et al., 2016) occupies central role in the ML community. Yet, recent evidence suggests that deep neural networks can be sensitive to distribution shifts, exhibiting unsatisfactory performance within new environments, e.g., Beery et al. (2018); Su et al. (2019); Recht al. (2019); Mancini et al. (2020). A more concerning example is that model for COVID-19 detection exploits undesired 'shortcuts' from data sources (c.g.. hospitals) to boost training accuracy (DeGrave al., 2021).
Recent studies of the OOD generalization problem like Rojas-Carulla et al. (2018); Bühlmann (2018); Gong al. (2016); Arjovsky al. (2019) treat the cause of distribution shifts between training and testing data as potential unknown environmental variable Assuming that the goal is to predict target label y given associated input x, the environmental variable would impact the underlying data generating distribution p(x, y/e) (e) p(x ())(p x, e). With & as the support of environments,
f(-) as a prediction model and ((:s)) ) as loss function, the OOD problem could be formally represented as
min max E (xx. v)le].
(1)
CEE
"This work was done during authors' internship AWS Shanghai Al Lab. "Coresponndig author is Junchi Yan. The SITU authors are also with MoF Key Lab of Artificial Intelligence, Shanghai Jiao Tong University.
Thee implementation is public available htttp::/ggithhe htw.tttuubooooo.ioooeo//oe/ wt aawiann///aaa haaggt//raoooooooooooooooo MERM.

---

Published as a conference paper at ICLR 2022
Such a problem is hard to solve since the observations in training data cannot cover all the envi- ronments in practice. Namely, the actual demand is to generalize a model trained with data from y/x.y/e = e1) to new data from y/x.yle learning domain-invariant models (Arjovsky et al., 2019) under a comnerstone data-generating assump- tion: there exists portion of information in x that is invariant for prediction on y across different environments. Based on this, the key idea is to learn a equipredictive representation model h that gives rise equal conditional distribution p(y|/1(x)) e e) for Ve E. The implication is that such representation h(x) will bring up equally (optimal) performance for a downstream classifier under arbitrary environments. The model p(y|x) with such a property is called as invariant model/predictor. Several up-to-date studies develop new objective designs and algorithms for learning invariant models, showing promising power for tackling OOD generalization (Chang et al., 2020; Ahuja et al., 2020; Krueger et al., 2021; Liu et al., 2021; Creager et al., 2021; Koyama & Yamaguchi, 2021).
e2). Recent research opens new possibility via
While the OOD problem extensively explored on Euclidean data (e-g., images), there are few existing works investigating the problem concerning graph-structured data, despite that distribution shifts widely exist real-world graphs. For instance, in citation networks, the distributions for paper citations (the input) and subject areas/topics (the label) would go through significant change time goes by (Hu et al., 2020). In social networks, the distributions for users' friendships (the input) and their activity (the label) would highly depend on when/where the networks are collected (Fakhraei et al., 2015). In financial networks (Pareja et al., 2020), the payment flows between transactions (the input) and the appearance of illicit transactions (the label) would have strong correlation with some external contextual factors (like time and market). In these cases, neural models built on graph-structured data, particularly, Graph Neural Networks (GNNs) which are the common choice, need to effectively deal with OOD data during test time. Moreover, as GNNs have become popular and easy-to- to-implement tools for modeling relational structures broad AI areas (vision, texts, audio, etc.), enhancing its robustness to distribution shifts is pain point for building general Al systems, especially applied to high-stake applications like autonomous driving (Dai & Gool, 2018 101, medical diagnosis (AlBadawy et al., 2018), criminal justice (Berk et al., 2018), etc.
Nonetheless, compared with images or texts, graph-structured data has two fundamental differences. First, many graph-related problems (like the situations mentioned above) involve prediction tasks for each individual node, in which case the data points are inter-connected via graph structure that induces non-independent and non-identically distributed nature in data generation even within the same environment. Second, apart from node features, the structural information also plays a role for prediction and would affect how the model generalizes under environment variation. These differences bring up unique technical challenges for handling distribution shifts on graphs.
In this paper, we endeavor to 1) formulate the OOD problem for node-level tasks on graphs, 2) develop a new learning approach based on an invariance principle, 3) provide theoretical results to dissect its rationale, and 4) design comprehensive experiments show practical efficacy. Concretely:
1. To accommodate the non-lID nature of nodes in a graph, we fragment a graph into a set of gro-graphs for centered nodes and decompose the data-generating process into: 1) sampling a whole input graph and 2) sampling each node's 's label conditioned on ego-graph, Based on this, we can inherit the spirit of Eq. 1 to formulate the OOD problem for love- tasks over graphs (see Section 2.1).
2. To account for structural information, we extend the invariance principle with recursive computation on the induced BFS trees of ego-graphs. Then, for out-of-distribution generalization on graphs, we devise a new learning approach, entitled Explore-to-EExrrpolate Risk Minimization, that aims GNNs at minimizing the mean and variance of risks from multiple environments that are simulated by adversarial context generators (i.e., graph editers), as shown in Fig. 1(a) (see Section 2.2 and 3).
3. To shed more insights on the rationales of the proposed approach and its relationship with the formulated OOD problem, prove that our objective can guarantee a valid solution for the formulated OOD problem given some mild conditions and furthermore, an upper bound on the OOD error can be effectively controlled when minimizing the training error (see Section 4).
4. To evaluate the approach, we design a comprehensive set of experiments on diverse real-world node- level prediction datasets that entail distribution shifts from artificial spurious features, cross- cross-domain transfers and dynamic graph evolution. We also apply our approach to distinct GNN backbones (GCN, GAT, GraphSAGE, GCNII and GPRGNN), and the results show that it consistently outperforms standard empirical risk minimization with promising improvements on OOD data (see Section 5).
2

---

Published as a conference paper at ICLR 2022
Genasiton 1
uc M
Ingut Dams (6,3)
Conted Danasakr
pub ish ave
My ciaalon Index
papor's sub aroa.
Ganerskrr
time publicationn
Explore
Exhrapoaato
FoNaa
PENGOREE Uedite
su Grodect Unddae
(h)
Figure I: (a) The proposed approach Explore-to-Exx/applaat Risk Minimization which entails K context generators that generate graph data of different (virtual) environments based on input data from single (real) environment. The GNN model is updated via gradient descent to minimize weighted combination of mean and variance of risks from different environments, while the context generators are updated via REINFORCE to maximize the variance loss. (b) Illustration for our Assumption 1. (c) The dependence among variables in the motivating example in Section 3.1.
2 PROBLEM FORMULATION
In this section, we present our formulation for the OOD problem on graphs. All the random variables are denoted bold letters while the corresponding realizations are denoted thin letters.
2.1 OUT-OF-DISTRIBUTTON PROBLEM FOR GRAPH- SRAAPHSSTRUCTURD DATA
An input graph G (4, X) contains two-fold information an adjacency matrix A = {avull |V V} and node features X = {2rll E }} where V denotes node set. Apart from these, each node in the graph has label, which random variable of input graphs and Y as random variable of node label vectors. Such a definition takes global view and treat the input graph a whole. Based on this, one can adapt the definition of general OOD problem Eq. I via instantiating the input as G and the target as Y, and then the data generation can be characterized as p(G, Y = p( () G, e) where is random variable of environments that is a latent variable and impacts data distribution.
be represented as a vector Y {y-|o V). We define G as
However, the above definition makes little sense in node-level problems where in most cases there is a single input graph that contains massive number of nodes. To make the problem-solving reasonable, we instead take local view and investigate each node's s ego-graph that has influence on the centered node. Assume as random variable of nodes. We define node v's L-hop neighbors N. (where is an arbitrary integer) and the nodes in N₂ form an ego-graph G, which consists of a (local) node feature matrix X, {Iu//u E N₂) and (local) adjacency matrix A, {aww (u, w No). Use Gy as a random variable of ego-graphs whose realization is G, = (A,,X,) Besides, we define y as a random variable of node labels. In this way, can fragment whole graph as set of instances {G.., yo Jrvv where G, denotes an input and ye is a target. Notice that the ego-graph can be seen as a Markov blanket for the centered node, the conditional distribution p( Y Y e) can be decomposed as product of [V] independent and identical marginal distributions ply G.. e).
Therefore, the data generation of {GG,, yo Wo))ev from distribution p(G. Yle) can be considered as a two-step procedure: 1) the entire input graph is generated via G ~ p( G|e) which can then be fragmented into set of ego-graphs vvv) 2) each node's ' label is generated via y ~ p(y|G, G.,, c). Then the OOD node-level prediction problem can be formulated as: given training data {G., Yo Joev from p(G, G, Yle = e), the model needs to handle lesting data {G Jov from a new distribution p( G. Yle = e'). Denote & as the support of environments, J as a predictor model with ÿ = fG.) and I(.,)) :) as a loss function. More formally, the OOD problem can be written as:
min max BGag(G)emm) EEE
Cy G. IV
Σ
We remark that the first-step sampling G ~ p(G = e) can be ignored since in most cases one only has a single input graph in the context of node-level prediction tasks.
"Our formulation and method can he trivially extended to cover edge features which we omit here for brevity. We use subscript v here remind that it is ego-graph from the view of target node.
3

---

Published as a conference paper at ICLR 2022
2.2 INVARIANT FEATURES FOR NOVE-LEVEL PREDICTION ON GRAPHS
To solve the OOD problem Eq. 2 is impossible without any prior domain knowledge or structural assumptions since one only has access to data from limited environments in the training set. Recent studies Moojal-Carulla et al., 2018; Arjovsky et al., 2019) propose to learn invariant predictor models which resorts to an assumption for data-gente suta-gennrating process: the input instance contains a portion of features (i.e., invariant features) that 1) contributes to sufficient predictive information for the target and 2) gives rise to equally (optimal) performance of the downstream classifier across environments.
With our definition in Section 2.1, for node-level prediction on graphs, each input instance is an ego-graph G, with target label ye. It seems not straightforward for how to define invariant features on graphs given two observations: 1) the ego-graph possesses hierarchical structure for associated nodes (i.e., G, induces a BFS tree rooted at u where the I-th layer contains the l-order neighbored nodes N(L)) and 2) the nodes in each layer are permutation-invaiian and variable-length. Inspired by WL test Weisfeiler & Lehman (1968), we extend the invariance assumption (Rojas-Came Carulla et al., 2018; Gong al., 2016; Arjovsky et al., 2019) to accommodate structural information in graph data: Assumption 1. (Invariance Property) Assume input feature dimension as dg. There exists a sequence of (non-linear) functions {hi H where hij IR - ER and permustation-invariee
function
T: Rdd + IRd, which gives a node-level readout To = Te (1.) that is calculated in a recursive way:
(0) - ( NO U { for I= = =1,,... L and ru hū (ar)) if u N Denote as a random variable of ru and it satisfies 1) (Invariance condition): p(y) (r, e) = =pyy'r, and 2) (Sufficiency condition): y ex (r) + where c* is non non-linear function, is independent noise.
more intuitive illustration for the above computation presented in Fig. 1(b). The node-level readout т, aggregates the information from neighbored nodes recursively along the structures of BFS tree given by G,. Essentially, the above definition assumes that in each layer the neighbored nodes contain portion of causal features that contribute stable prediction for y across different e. Such a definition possesses two merits: 1) the (non-linear) transformation hi can be different across layers, and 2) for arbitrary node u in the original graph G, its causal effect on distinct centered nodes v could be different dependent on its relative position in the ego-graph G.. Therefore, this formulation gives rise to enough flexibility and capacity for modeling on graph data.
METHODOLOGY
We next present our solution for the challenging OOD problem. Before going into the formal method, we first introduce a motivating example based on Assumption to provide some high-level intuition.
3.1 MOTIVATING EXAMPLE
We consider a linear toy example and assume I-layer graph convolution for illustration. Namely, the ego-graph Ge (and N₂)) only contains the centered node and its I-hop neighbors. We simplify the h and c* in Assumption as identity mappings and instantiate I as a mean pooling function. Then we assume 2-dim node features F2 = [x x and
1
Σ +
2
Σ uEN.
yu
+ n +
(3)
[N.]
M.
where n. and n? are independent standard normal noise and e is a random variable with zero mean and non-zero variance dependent environment In Fig. 1(c) we show the dependency among these random variables in a graphical representation and instantiate them in an example of citation networks. where a paper's published avenue is an invariant feature for predicting the paper's 's sub-area while its citation index (a spurious feature) is affected by both the label and the environment.
Based on this, we consider vanilla GCN as the predictor model 1. To- EMEN, 0,47 + 02
Then the ideal solution for the predictor model is [0,, 02] = [1, 0]. This indicates that the GCN identifies the invariant feature, i.e., x insensitive to environment changes. However, here we show negative result when using standard empirical risk minimization.
Proposition 1. Let the risk under environment be R(e) Evev Ey, I1bo Vo vo112.. The
unique optimal solution for objective ming E. [(()] would be [01,0z] = 1 1 where de > 0 denotes the standard deviation of across environments.
4

---

Published as a conference paper at ICLR 2022
This indicates that directly minimizing the expectation of risks across environments would inevitably lead the model to rely on spurious correlation (a) depends on environments). Also, such a reliance would be strengthened with smaller de i.c., when there is less uncertainty for the effect from environments. To mitigate the issue, fortunately, we can prove another result that implies a new objective sufficient condition for the ideal solution.
Proposition 2. The objective ming V [((e) reaches the optinum if and only if [0,, 02] [1. 0).
The new objective tackles the variance across environments and guarantees the desirable solution. The enlightenment is that if the model yields equal performance on different e's, it would manage to leverage the invariant features, which motivates us to devise a new objective for solving Eq. 2.
3.2 STABLE LEARNING WITH EXPLORE- TO- TOA-OOO--ETTLTTTTO
RISK MINIMIZATION
We now return to the general case where we have {(Ge. ye)} for training and leverage a GNN model as the predictor: De (o.). The intuition in Section 3.1 implies a new learning objective:
min Vo[L(G", ;=; + [ 0);
(4)
where LIG Y=; = VV. EvEv. (f)( v.) and is a trading erper-parametr. we have training graphs from sufficient number of environments &,r {e} and the correspondence of each graph to a specific e, i.e., {G*, Y JeEE,, which induces ((G vev. : e E E we can use the empirical estimation with risks from different environments to handle Eq. 4 in practice, is done by the Risk Extrapolation (REx) approach (Krueger et al., 2021). Unfortunately, as mentioned before, for node-level tasks on graphs, the training data is often single graph (without any correspondence of nodes to environments), and hence, one only has training data from a single environment. Exceptions are some multi-graph scenarios where one can assume each graph is from an environment, but there are still a very limited number of training graphs (e.g., less than five). The objective Eq. 4 would require data from diverse environments to enable the model for desirable extrapolation. To detour such a dilemma, we introduce K auxiliary context generators Iw, (G) (A- = 1. ... K) that aim to generate K K-fold graph data {G* [G*)_= (which induces { WEV S k < K)) based on the input one G and mimics training data from different environments. The generators are trained to maximize the variance loss so as to explore the environments and facilitate stable learning of the GNN:
K
min Var(fL(gung (G), (:)) 11 k K() +
Σ Loon 1 (G),Y;)).
K k=1
(5)
[wi,-. w arg
max wi," .KK
Var(fL(Sw,, (G),Y;0) 15 KT),
where Lgwn YG),Y:0) = L(G Y:0) = + ((fo(G))...).
One remaining problem is how specify Iwn (G). Following recent advances in adversarial ro- bustness on graphs (Xu et al., 2019; Jin et al., 2020), we consider editing graph structures by adding/deleting edges. Assume Boolean matrix 8* {0, 1 (k- 1, .K) and denote the A, where / is identity matrix. Then the modified graph
supplement graph of A A 11 for view A: is 4 = A B* o (Ā- A) where o denotes element- wise product. The optimization for B* difficult due to its condiifferentiabiiity and one also needs to constrain the modification within a threshold. To handle this, we use policy gradient method REINFORCE, treating graph generation as decision process and edge editing as actions (see details in Appendix A). We call our approach in Eq. 5 Explore-to taatte-to-xxxtpttte Extrapolate Risk Minimization (EERM) and present our training algorithm in Alg. 1.
4 THEORETICAL DISCUSSIONS
We next present theoretical analysis to shed insights on the objective and its relationship with our formulated OOD problem in Section 2. To begin with, we introduce some building blocks. The GNN model can be decomposed into encoder h for representation and a classifier for prediction, i.e., f= c o h and we have 2, = h(G,), f. = c(2u). ). Besides, we assume [xx:y) stands for the mutual information between and y and (xxyle denotes the conditional mutual information given z. To keep notations simple, we define p.(.) = p(-le = e) and I,(-) = I(-le = e).
Another tricky point is that in computation of the KI. divergence and mutual information, we require
5

---

Published as a conference paper at ICLR 2022
the samples from the joint distribution Pe (G. Y), which also results in difficulty for handling data generation of interconnected nodes. Therefore, we again adopt our perspective in Section 2.1 and consider a two-step sampling procedure. Concretely, for any probability function fi, f2 associated with ego-graphs Gv and node labels y, we define computation for KI. divergence as
Dxa.Uh(Grv.))llbb(G... = BG))(G)
Σ I
(pemp(y(G..G.)
log
fi = G., y= vv)
fa(Gv Gv,y y - _c]_
(6)
4.1 RELATIONSHIP BETWEEN INVARIANCE PRINCIPLE AND OOD PROBLEM
We will show that the objective Eq. 4 can guarantee valid solution for OOD problem Eq. 2. To this end, we rely on another assumption for data data- generating distribution.
Assumption 2. (Environment Heterogeneity): For (Gv. r) that satisfies Assumption 1, there exists random variable F such that Gv m(r,F) where m is functional mapping. We assume that p(y r, = e) would arbitrarily change across environments E E.
Assumptions and 2 essentially distill two portions of features in input data: one is domain-invariant invariant for prediction and the other contributes to sensitive prediction that depends on environments. The GNN model f = c o induces two model distributions (z) (by the encoder) and g(ylz) (z) (by the classifier). Based this, we can dissect the effects of Eq. which indeed forces the representation to satisfy the invariance and sufficiency conditions illustrated in Assumption 1.
Theorem 1. If q(y 3) is treated as a variational distribution, then 1) minimizing the expectation term in Eq. 4 contributes to maxg(z(G.) ([y; i.e., enforcing the sufficiency condition on z for prediction, and 2) minimizing the variance term in Eq. 4 would play a role for ming(z)G..) ely:e i.e., enforcing the invariance condition p(y z, e) ply (z).
Based on these results, can bridge the gap between the invariance principle and OOD problem.
Theorem 2. Under Assumption I and 2, if the GNN encoder ((z(G.) satisfies that 1) I(y: e/z) = O (invariance condition) and 2) Iy;;z) is maximized (sufficiency condition), then the model f given by [y|z) is the solution to OOD problem in Eq. 2.
The above results imply that the objective Eq. 4 can guarantee a valid solution for the formulated OOD problem on graph-structured data, which serves as theoretical justification for our approach.
4.2 INFORMATION- THEORETIC ERROR FOR OOD GENERALIZATION
We proceed to analyze the OOD generalization error given by our learning approach. Recall that we assume training data from p(G. Y/e e) and testing data from p( G, Y = ='). Following similar spirits of Federici et al. 1), the training error and OOD generalization error can be respectively measured by DKi based on our definition in Eq. 6. Based on Theorem 1, we can arrive at the following theorem which reveals the effect of Eq. that contributes to tightening the bound for the OOD error.
(p. (y Gv) (l)) and D (p. (y (v)llg(y GGv) which can be calculated
Theorem 3. Optimizing Eq. with training data can minimize the upper bound for D (pe (y(Gv))la(y((G.) on condition that I (G) = Ia IGG.:
The condition can be satisfied once z is a sufficient representation across environments. Therefore, we have proven that the new objective could help to reduce the generalization error on -istrf-disttibution data and indeed enhance GNN model's 's power for in-the-wild wild extrapolation.
EXPERIMENTS
In this section, we aim to verify the effectiveness and robustness of our approach in a wide variety of tasks reflecting real situations, using different GNN backbones. Table I summarizes the information of experimental datasets and evaluation protocols, and we provide more dataset information in Appendix E. We compare Implementation details are presented in Appendix In the following subsections, we will investigate three scenarios that require the model to handle distribution shifts stemming from different causes.
approach EERM with standard empirical risk minimization (ERM).

---

Published as a conference paper at ICLR 2022
Table I: Summary of the experimental datasets that entail diverse distribution shifts ("Artificial Transformation" means that we add synthetic spurious features, Dooos--Dmmain Transfers" means that each graph in the dataset corresponds to distinct domains, "Temporal Evolution" means that the dataset is a dynamic one with evolving nature), different train/val/test splits ("Domain-Leved means splitting by graphs and "Time-Awar means splitting by time) and the evaluation metries, In Appendix E we provide more detailed information and discussions on the evaluation protocols.
Dataset
Distribution Shift
#Nodes
+Eiges
#Classes
Tran/Valeess Sylit
Metric
Adapted frrm
Amaron Photo
Cluza
Antifciall Trandformaionn
7,650
2.703
[19.08]
5,27%
10
10
Dounsin-Level
Domain-Level
Accurccy
Accuney
Shohur (2018)
Yang al. (2016)
Teinchexspici
Hagebook 100
Cross Domain Transfers
1.912 99,96
411,36
16,656
11,290-
1,390655
153,/38
Domain Level
Domain-Leww evel
ROC-ALIC
Accuracy
Rovmmbrerki (3021)
Traud (2011)
OGBB-Ardiv
Ellaptic
Temupocal Evolution
169,343
1,166,243
234,355
Time-Awue
Time Aware
Accunac
Pureja (2020y'
Hu (2020)
The original dosaset is provided at pt //www. kaggle con 1 wttppptooppooooceoooooooooooooot http://ooo....ppppetttt-------
100
80
ERM
ERM
EERM
Figure 2: Results on Cora with artificial distribution shifts. We run each experiment with 20 trials. (a) The (distribution of) test accuracy of vanilla GCN using our approach for training and using ERM. (b) The (averaged) accuracy on the training set (achieved by the epoch where the highest validation accuracy is achieved) when using all the input node features and removing the spurious ones for inference. (c) The (averaged) test accuracy with different GNNs for data generation.
ERM
E-M
CERM
1el sparts...
60
EDRM
GCN
GAT
(8)
(b)
(c)
Figure 3: Experiment results on Amazon-Phote with artificial distribution shifts.
5.1 HANDLING DISTRIBUTION SHIFTS WITH ARTIFICIAL TRANSFORMATION
We first consider artificial distribution shifts based on two public node classification benchmarks Cora and
For each dataset, we adopt two randomly initialized GNNs 1) generate node labels based on the original node features and 2) generate spurious features based on the node labels and environment id, respectively (See Appendix E. for details). We generate 1 10-fold graph data with distinct environment id's and use 1/1/8 of them for training/validationnessigg
We use a 2-layer vanilla GCN (Kipf & Welling, 2017) as the GNN model. We report results on 8 testing graphs (TI~ T8) of the two datasets in Fig, 2(a) and 3(a), respectively, where we also adopt 2-layer GCNs for data generation. The results show that our approach EERM consistently outperforms ERM on Cora and Photo, which suggests the effectiveness of our approach for handling distribution shifts. We also observe that in Photo, the performance variances within one graph and across different test graphs are both much lower compared with those in Cora. We conjecture the reasons are two-fold. First, there is evidence that in Cora the (original) features from adjacent nodes are indeed informative for prediction while in Photo o this information contributes to negligible gain over merely using centered node's ' features. Based on this, once the node features are mixed up with invariant and spurious ones, would be harder for distinguishing them in the former case that relies more on graph convolution.
In Fig. 2(b) and Fig. 3(b), we compare the averaged training accuracy (achieved by the epoch with the highest validation accuracy) given by two approaches when using all the imput features and removing the spurious ones for inference (we still use all the features for training in the latter case). As we can see, the performance of ERM drops much more significantly than EERM when we remove the spurious input features, which indicates that the GCN trained with standard ERM indeed exploits spurious features to increase training accuracy while our approach can help to alleviate such an issue and guide the model to focus on invariant features. Furthermore, in Fig. 2(c) and Fig. 3(c), we compare the test accuracy averaged eight graphs when using different GNNs e.g. GCN, SGC (Wu et al., 2019) and GAT (Velickovic et al., 2018), for data generation (See Appendix G for more results). The results verify that approach achieves consistently superior performance in different cases.
7

---

Published as a conference paper at ICLR 2022
NOC- BISCANN
GGN
GAT
31GGMII
Figure 4: Test ROC-AUC on Twitch where we compare different GNN backbones.
Table 2: Test accuracy on FB 100 where we compare different configurations of training graphs.
Training graph combination
Penn
Brown
Texas
ERM
EERM
ERM
EERM
ERM
EERM
John Hopkins + Caltech + Amherst
50.48 1.09
50.64
0.25
54,53
3.93
56.73 1: 0.23
53.23 4: 4.49
55.57 0.75
Bingham Dake 1 Princeton
50.17 0.65
50.67 + 0.79
50.43 + 4.58
52.76 + 3.40
50.19 4 5.81
53.82 4.88
WishU Brandeis+ Camegie
$4.61
3:22
ETV
Table 3: Test accuracy on OGB-Arxiv with pa- pers in different time intervals for evaluation.
F1800
1150m
Method
2014-2016
2016-2018
2018-2020
(a) Grast
T1
1b) GPRGNN
ERS- SAGE
42.09 4: 1.39
39.92 4: 2.53
36.72 d: 2.47
EERM- SAGE
11.55 0.68
10.35 1.29
38,95 1.57
Figure 5: Test F1 score El Elliptic where group graph snapshots into 9 test sets (T1~ T9).
BRM- GPR
47.25 4 0.35
45.07 4 0.57
41,53 :: 0.56
BERM- GPR
49.88
4 0.49
48.59 4: 0.52
44,88 2: 0.62
5.2 GENERALIZING TO UNSEEN DOMAINS
We proceed to consider another scenario where there are multiple observed graphs in one dataset and model trained with one graph limited number of graphs is expected to generalize to new unseen graphs. The graphs of a dataset share the input feature space and output space and may have different sizes and data distributions since they are collected from different domains. We adopt two public social network datasets Twitch-Exp.l.
and Facebook-10 -10 collected by Lim et al. (2021).
Training with a Single Graph. In Twitch, adopt a single graph DE for training, ENGB for validation and the remaining five networks (ES, FR, PTBR, RU, TW) for testing. We follow Lim al. (2021) and use test ROC-AUC for evaluation. We specify the GNN model as GCN, GAT and recently proposed model GCNII (Chen et al., 2020a) that can address the over-smoothing of GCN and enable stacking of deep layers. The layer numbers are
for GCN and GAT and 10 for GCNIL. Fig. 4 compares the results on five test graphs, where EERM significantly outperforms ERM in most cases with up to 7.0% improvement on ROC-AUC. The results verify the effectiveness of EERM for generalizing to new graphs from unseen domains.
Training with Multiple Graphs. In FB-100, 00, we adopt three graphs for training, two graphs for validation and the remaining three for testing. We also follow Lim et al. (2021) and use test accuracy for evaluation. We use GCN as the backbone and compare using different configurations of training graphs, shown in Table 2. We can that EERM outperforms ERM average on all the test graphs with up to 7.2% improvement. Furthermore, EERM maintains the superiority with different training graphs, which also verifies the robustness of our approach w.r.t. training data.
5.3 EXTRAPOLATING OVER DYNAMIC DATA
We consider the third scenario where the input data are temporal dynamic graphs and the model is trained with dataset collected at one time and needs to handle newly arrived data in the future. Here also sub-cases that correspond to distinct real-world scenarios, as discussed below.
Handling Dynamic Graph Snapshots. We adopt a dynamic financial network dataset E11 ptic (Pareja et al., 2020) that contains dozens of graph snapshots where each node is a Bitcoin transaction and the goal is to detect illicit transactions. We use 5/5/33 snapshots for train/valid/tes. Following Pareja et al. (2020) we use F1 score for evaluation. We consider two GNN architectures as the backbone: GraphSAGE (Hamilton et al., 2017) and GPRGNN (Chien et al., 2021) that can adaptively combine information from node features and graph topology. The results are shown in Fig. where we group the test graph snapshots into 9 folds in chronological order. Our approach yields much higher Fl scores than ERM in most cases with averagely 9. 9.6% 3.6%/10.9%% 1100% improvements using GraphSAGE/GPR GNN backbones. Furthermore, there is an interesting phenomenon that both methods suffer a performance drop after T7. The reason is that this is the time when the dark market shutdown occurred (Pareja et al., 2020). Such an emerging event causes considerable variation to data
8

---

Published as a conference paper at ICLR 2022
distributions that leads performance degrade for both methods, with ERM suffering more. In fact, the emerging event acts as an external factor which is unpredictable given the limited training data. The results also suggest that how neural models generalize to OOD data depends on the learning approach but its performance limit is dominated by observed data. Nonetheless, our approach contributes to better F1 scores than ERM even in such an extreme case.
Handling New Nodes in Temporally Augmented Graph. Citation networks often go through temporal augmentation with new papers published. We adopt OGB-Arxiv (Hu et al., 2020) for experiments and enlarge the time difference between training and testing data to introduce distribution shifts: we select papers published before 2011 for training, in-between 2011 and 2014 for validation, and within 2014-201 (00006/2016-10 20--20018118--- 8-20 for testing, Also different from the original (transduc- tive) setting in Hu et al. (2020), we use the inductive learning setting, i.e., test nodes are strictly unseen during training. which is more akin to practical situations. Table 3 presents the test accuracy and shows that EERM outperforms ERM in five cases out of six. Notably, when using GPRGNN as the backbone. EERM manages to achieve up to 8.1% relative improvement, which shows that EERM is capable improving GNN model's s learning for extrapolating to future data.
DISCUSSIONS WITH EXISTING WORKS
We compare with some closely related works and highlight our differences. Due to space limit, we defer more discussions on literature review to Appendix B.
annerralization/Extaaoootto on Graphs. Recent endeavors (Scarselli et al., 2018; Garg et al., 2020; Verma & Zhang, 2019) derive generalization error bounds for GNNs, yet they focus on in- distribution generalization and put little emphasis on distribution shifts, which are the main focus of our work. Furthermore, some up-to-date works explore GNN's extrapolation ability for OOD data, e.g. unseen features/structuree (Xu et al., 2021) and varying graph sizes (Yehudai et al., 2021; Bevilacqua et al., 2021). However, they mostly concentrate on graph-level tasks rather than node-level ones (see detailed comparison below). Moreover, some recent works probe into extrapolating features' embeddings (Wu et al., 2021a) or user representations (Wu et al., 2021b) for open-world learning in tabular data or real systems for recommendation and advertisement. These works consider distribution shifts stemming from augmented input space or unseen entities, and the proposed models leverage GNNs as an explicit model that extrapolates compute representations for new entities based on existing ones. In contrast, our work studies (implicit) distribution shifts behind observed data, and the proposed approach resorts to an implicit mechanism through the lens of invariance principle.
Node-Level v. s. Graph-Level OOD Generalization. The two classes of graph-related problems often treated differently in the literature: node-level tasks target prediction on individual nodes that are non-i.i.d. generated due to the interconnection of graph structure; graph-level tasks treat graph as an instance for prediction and tacitly assume that all the graph instances are sampled in an i..dd. manner. The distinct nature of them suggests that they need to be tackled in different ways for OOD generalization purpose. Graph-level problems have straightforward relationship to the general setting (in Eq. 1) since one can treat input graphs as x and graph labels as y. Based on this, the data from one environment becomes a set of i.i.d. generated pairs (x, y) and existing approaches for handling general OOD settings could be naturally generalized. Differently, node-level problems, where nodes inter-connected one graph (e.g., social network) are instances, cannot be handled in this way due to the non-i.i.d. data generation. Our work introduces new perspective for formulating OOD problems involving prediction for individual nodes, backed up with a concrete approach for problem solving and theoretical guarantees. While our experiments mainly focus on node-level prediction datasets, the proposed method can be applied to graph-level prediction and also extended beyond graph data (like images/texts) for generalization from limited observed environments.
CONCLUSION
This work targets out-of-distribution generalization for graph-structured data with the focus on node-level problems where the inter-connection of data points hinders trivial extension from existing formulation and methods. To this end, we take a fresh perspective to formulate the problem in a principled way and further develop new approach for extrapolation from a single environment, backed up with theoretical guarantees. We also design comprehensive experiments to show the practical power of our approach on various real-world datasets with diverse distribution shifts.

---

Published as a conference paper at ICLR 2022
8 ACKNOWLEDGEMENT
This work was in part supported by National Key Research and Development Program of China (2000AAA0107600), Shanghai Municipal Science and Technology Major Project (2021SHZDZX01122)
REFERENCES
Faruk Ahmed, Yoshua Bengio, Harm van Seijen, and Aaron C. Courville, Systematic generalisation with group invariant predictions. In International Conference on Learning Representations (ICLR), 2021.
Kartik Ahuja, Karthikeyan Shanmugam, Kush R. Varshney, and Amit Dhurandhar. Invariant risk minimization games. In International Conference on Machine Learning (ICML), pp. 145-155, 2020.
Ehab A AlBadawy, Ashirbani Saha, and Maciej A Mazurowski. Deep learning for segmentation of brain tumors: Impact of cross-institutional training and testing. In Medical physics, 2018.
Martín Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization.
CoRR, abs/1907.0220 .00993...239.... 2019.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved linear separability and out-of-distribution generalization. In International Conference on Machine Learning (ICML), pp. 684-693, 2021.
Sara Beery, Grant Van Horn, and Pietro Perona. Recognition in terra incognita. In European Conference on Computer Vision (ECCV), pp. 472-489, 2018.
R. Berk, H. Heidari, S. Jabbari, M. Kearns, and A Roth. Faimess in criminal justice risk assessments: The state the art. In Sociological Methods & Research, 2018.
Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size- Size-invariant graph representations for graph classification extrapolations. In International Conference on Machine Learning (ICMI.), pp. 837-851, 2021.
Gilles Blanchard, Gyemin Lee, and Clayton Scott. Generalizing from several related classification tasks to new unlabeled sample. Advances Neural Information Processing Systems (NeurIPS), pp. 2178-2188 186, 2011.
Peter Bühlmann. Invariance, causality and robustness. CoRR, rationalization. International
2018.
Shiyu Chang, Yang Zhang, Mo Yu, and Tommi Jaakkola. Invariant Conference on Machine Learning (ICML), pp. 1448-1458, 2020.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning (ICML), pp. 1725-1735, 2020a.
Tianlong Chen. Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. In International Conference on Machine Learning (ICML), pp. 1695-1706. 2021.
Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. In Advances in Neural Information Processing Systems (NeurIPS), 2020b.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. International Conference on Learning Representations (ICLR), 2021.
Elliot Creager, Jömn Hen-Henrik Jacobsen, and Richard S. Zemel. Environment inference for invariant learning. In International Conference Machine Learning (ICMI.), pp. 2189-2200, 2021.
10

---

Published as a conference paper at ICLR 2022
Dengxin Dai and Luc Van Gool. Dark model adaptation: Semantic image segmentation from daytime to nighttime. In International Conference on Intelligent Transportation Systems (ITSC), pp. 3819-3824, 2018.
A. J. DeGrave, J. D. Janizek, and Lee. Ai for radiographic covid-19 detection selects shortcuts over signal. Nature Machine Intelligence, 2021.
Shobeir Fakhraci, James R. Foulds, Madhusudana V. S. Shashanka, and Lise Getoor. Collective spammer detection in evolving multi-relational social networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 1769-1778, 2015.
Marco Federici, Ryota Tomioka, and Patrick Forré. An information-theorrt approach to distribution shifts. CoRR, 02e/2106.037880 2021.
Vikas K. Garg, Stefanie Jegelka, and Tommi S. Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning (ICML), pp. 3419-3430, 2020.
Mingming Gong, Kun Zhang, Tongliang Liu, Dacheng Tao, Clark Glymour, and Bernhard Schölkopf. Domain adaptation with conditional transferable components. International Conference on Machine Learning (ICML), pp. 2839-2848, 2016.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1024-1034, 2017.
Arman Hasanzadeh, Ehsan Hajiramezanali. Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sampling. In International Conference on Machine Learning (ICML), pp. 4004-4104, 2020.
Weihua Hu, Matthias Fey, Marinka Zitmik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pp. 66-74, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Masanori Koyama and Shoichiro Yamaguchi. When is invariance useful in out-of-distribation generalization problem? ? CoRR, abs/2008.01 0100008..888888 883, 2021.
David Krueger, Ethan Caballero, Jörn-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Rémi Le Priol, and Aaron C. Courville. Out-of-distribution generalization via risk extrapolation (rex). In International Conference on Machine Learning (ICML), 2021.
Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non- homophilous graphs. In The Web Conference (WWW) workshop, 2021.
Jiashuo Liu, Zheyuan Hu, Peng Cui, Bo Li, and Zheyan Shen. Heterogeneous risk minimization. In International Conference on Machine Learning (ICML), pp. 6804-6814, 2021.
Jiaqi Ma. Junwei Deng, and Qiaozhu Mei. Subgroup generalization and fairness of graph neural networks. In Advances in Neural Information Processing Systems, 2021.
Divyat Mahajan, Shruti Tople, and Amit Sharma. Domain generalization using causal matching. In International Conference on Machine Learning (ICML), pp. 7313-7324, 2021.
Massimiliano Mancini, Zeynep Akata, Elisa Ricci, and Barbara Caputo. Towards recognizing unseen categories in unseen domains. In European Conference on Computer Vision (ECCV), pp. 466-483, 2020.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In Conference Learning Theory (COLT), 2009.
11

---

Published as a conference paper at ICLR 2022
Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In International Conference on Machine Learning (ICML), pp. 10-18, 2013.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma. Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao B. Schardl, and Charles E. Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. In AAAI Conference on Artificial Intelligence (AAAI), pp. 5363-5370, 2020.
J. Peters, P. B" "uhlmann, and N Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society, Series (Statistical Methodology), pp. 947 - 1012, 2016.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? In International Conference on Machine Learning (ICML), pp. 5389-5400, 2019.
Mateo Rojas-Carulla, Bernhard Schölkopf, Richard E. Turner, and Jonas Peters. Invariant models for causal transfer learning. Journal of Machine Learning Research, 19:36:1-36:34, 2018.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2), 2021.
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. CoRR, abs/ 1.08731 2019.
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapnik-chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248-253 259,, 2018.
Bernhard Schölkopf, Dominík Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris M. Mooij. On causal and anticausal learning. In International Conference on Machine Learning (ICML), 2012.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. CoRR,
2018
Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai. One pixel attack for fooling deep neural networks. IEEE Transactions on Evolutionary Computation, 23(5):828-88) 841, 2019.
Amanda L. Traud, Peter J. Mucha, and Mason A. Porter. Social structure of facebook networks. CoRR, abs/ 102.2166, 1.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018
Saurabh Verma and Zhi-Li Zhang. Stability and generalization graph convolutional neural networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 1539-1548, 2019.
Boris Weisfeiler and AA Lehman. A reduction a graph to a canonical form and an algebra arising during this reduction. Neuchno-Techhichessken Informatsia, 2(9):12-16, 1968.
Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In International Conference on Machine Learning (ICML), pp. 6861-6871, 2019.
Qitian Wu, Chenxiao Yang, and Junchi Yan. Towards open-world feature extrapolation: An inductive graph learning approach. In Advances in Neural Information Processing Systems (NeurIPS), 202 la.
Qitian Wu, Hengrui Zhang, Xiaofeng Gao, Junchi Yan, and Hongyuan Zha. Towards open-world recommendation: An inductive model-based collaborative filtering approach. In International Conference Machine Learning (ICML), 2021b.
12

---

Published as a conference paper at ICLR 2022
Chuanlong Xie, Fei Chen, Yue Liu, and Zhenguo Li. Risk variance penalization: From distributional robustness to causality. CoRR, abx/2066.07544, 2020.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin. Topol- ogy attack and defense for graph neural networks: An optimization perspective. In International Joint Conference on Artificial Intelligence (IJCAI), pp. 3961-3967, 2019.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward graph neural networks. In International Conference Learning Representations (ICLR), 2021.
Zhilin Yang. William W. Cohen, and Ruslan Salakhutdinov. Revisiting sumi-super learning with graph embeddings. In International Conference on Machine Learning (ICML), pp. 40-48, 2016.
Gilad Yehudai, Ethan Fetaya, Eli A. Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization graph neural networks. In International Conference Machine Learning (ICML), pp. 11975-11986, 2021.
Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Ustebay. Bayesian graph convolutional neural networks for semi-supervised classification. AAAI Conference on Artificial Intelligence (AAAI), pp. 1829958366 2019.
Cheng Zheng, Bo Zong, Wei Cheng. Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In International Conference Machine Learning (ICML), pp. 11458-11468, 2020.
Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi. Shift-robust gnns: Overcoming the limitations of localized graph training data. In Advances in Neural Information Processing Systems, 2021.
13

---

Published as a conference paper at ICLR 2022
A OPTIMIZATION AND ALGORITHM
We illustrate the details of using policy gradient for optimizing the graph editers in Eq. S. Concretely, for view k, we consider parameterized matrix Ps- = {mhmm) )- For the n-th node, the probability for exp(m
editing the edge between it and the m-th node would be p(afim) E... (xpp)""...)) We then sample
s actions {bum, Ti from multinomial distribution MMp(ath)... p((aaa)): which give the non- zero entries in the 12-h row of B The reward function R(G can be defined as the inverse loss. We use REINFORCE algorithm to optimize the generator with the gradient V Ww log Pws. (A* (4*) R(G*) where w²k- = Pk and Pwr. (A*) II, IT; iP()).,) ). We present the training algorithm in Alg. 1.
Algorithm 1: Stable Learning for OOD Generalization in Node-Level Prediction on Graphs.
INPUT: training graph data = (A, X) and Y, initialized parameters of GNN 0, initialized {wu}. learning rates Cg. O'
parameters of graph editers while not converged or maximum epochs not reached do for t = 1, , do
Obtain modified graphs G = (A*. X) from graph editer Iw,, k = 1, K; Compute loss J1 (w) = Var( Y; 1 K));
Update wik- <- wk + 0g V w. Pog (A Ji =1, 1,.., K;
if == T then
Compute loss ( = Var( Y:0): 1 Kt) + k Σ L(G*,Y:0); Update 0 t 0 - ay {
10 OUTPUT: trained parameters of GNN 0*,
B FURTHER RELATED WORKS
B. OUT-OF-DISTRIBUTION GENERALIZATION AND INVARIANT MODELS
Duttof-distribution generalization has drawn extensive attention in the machine learning community. To endow the learning systems with the ability for handling unseen data from new environments, is natural to learn invariant features under the setting of the causal factorization of physical mechanisms (Schölkopf al., 2012; Peters et al., 2016). recent work (Arjovsky et al., 2019) proposes Invariant Risk Minimization (IRM) as a practical solution for OOD problem via invariance principle. Based on this, follow-up works make solid progress in this direction, e-g., with group distributional robust optimization (Sagawa et al., 2019), invariant rationalization (Chang et al., 2020), game theory (Ahuja et al., 2020), etc. Several works attempt to resolve extended settings. For instance, Ahmed et al. (2021) proposes to match the output distribution spaces from different domains via some divergence, while a recent work (Mahajan et al., 2021) also leverages a matching-base based algorithm that resorts to shared representations of cross-domain inputs from the same object. Also, Creager al. (2021) and Liu et al. (2021) point out that in most real situations, one has no access to the correspondence of each data point in the dataset with a specific environment, based on which they propose estimate the environments as a latent variable.
Krueger al. (2021) devises Risk Extrapolation (REX) which aims at minimizing the weighted combination of the variance and the mean of risks from multiple environments. Xie et al. (2020) contributes similar objective from different theoretical perspective. Also, Koyama & Yamaguchi (2021) extends the spirit of MAML algorithm and arrives at a similar objective form. In our model, we also consider minimization of the combination of variance and mean terms (in Eq. 4) and on top of that we further propose to optimize through bilevel framework in Eq. 5. Compared to existing works, the differences EERM are two-folds. First, we do not assume input data from multiple environments and the correspondence between each data point and a specific environment. Instead, our formulation enables learning and extrapolation from a single observed environment. Second, methodology side, we introduce multiple context generators that aim to generate data of virtual environments in an adversarial manner. Besides, our formulation in this paper focus on prediction tasks for nodes on graphs, where the essential difference, mentioned before, lies in the
14

---

Published as a conference paper at ICLR 2022
inter-connection of data points in graph (that corresponds to an environment), which hinders trivial adaption from existing works in the general setting.
B.2 GRAPH NEURAL NETWORKS AND GENERALIZATION
Another line of research related to us attempts to enhance the generalization ability of graph neural networks via modifying the graph structures. One category of recent works is to learn new graph structures based
the input graph and node features. To improve the generalization power, common practice is to enforce a certain regularization for the learned graph structures. For example, Jin et al. (2020) proposes constrain the sparsity and smoothness of graphs via matrix norms and further adopts proximal gradient methods for handling the non-differentiable issue. Chen et al. (2020b); Zhang al. (2019) also aim to regularize the sparsity and smoothness but differently harness energy function to enforce the constraints. From a different perspective, Xu et al. (2019) attempts attack the graph topology for improving the model's robustness and proposes to leverage projected gradient descent to make it tractable for the optimization of discrete graph structures. Alternatively, several works focus on pruning the graph networks (Chen al., 2021) or adaptively sparsifying the structures (Zheng et al., 2020; Hasanzadeh et al., 2020). In this paper, we focus on diittii-iitiitttioon generalization and target handling distribution shifts over graphs, which is more difficult than the setting of previous methods that concentrate in-distribution generalization. On methodology side, with a different training scheme, our context generators aim to generate data of multiple virtual environments and are learned from maximizing the variance of risks of multiple (virtual) environments. Also, one can specify our context generators with other existing graph cenerratoon/ediiinnaaataiiiii frameworks mentioned above, which we leave future works.
There are some very recent works that endeavor to study the out-of-distribution generalization ability of GNNs for node classification. (Baranwal et al., 2021) introduces contextual stochastic block model that is a mix-up of standard stochastic block model and a Gaussian mixture model with each component, based which the authors show some cases where linear
node class corresponding separability can be achieved. (Ma et al., 2021) focuses on subgroup generalization and presents a PAC- Bayesian theoretic framework, while (Zhu et al., 2021) targets distribution shifts between selecting training and testing nodes and proposes new GNN model called Shift-Robust GNNs. By contrast, our work possesses the following distinct technical contributions. First, we formulate OOD problem for node-level tasks in general manner without any assumption on specific distribution forms or the way for generation of graph structures (our Assumption 1 and 2 mainly focus on the existence of causal features and spurious features in data generation across different environments), Second, our proposed model and algorithm are rooted on invariant models, providing a new perspective and methodology for OOD learning graphs. Third, design and conduct comprehensive experiments on diverse real-world datasets that can reflect in-the-wild nature in real situations (e.g., cross- graph transfers and dynamic evolution) and demonstrate the power of our approach in three scenarios.
C PROOFS FOR SECTION 3.
C.1 PROOF FOR PROPOSITION
We define the aggregated node feature a, N.. EVEN, Zu. According to the definition and setup in Section 3.1, we derive the risk under specific environment R(e):
Eylg.=G. [l1i. 10
DEV
Eni,n na |1102a! - -22a, - -vol13
V
NEV
E En n² [I[(0] + 82 1)a + 62 n +c) 3c) m
V
WEV
15

---

Published as a conference paper at ICLR 2022
Denote the objective for empirical risk minimization L1 Ee(R(e)] and we have its first-order derivative w.r.t. 01 as
0h1
Ee
En . [2[(0] + 02 1)ay + 02(n) + n +() [nn]-nl at!
001
eEV
(8)
Ee
Ent.n n² [2[(0] 02 1).1)) -a. a!!
where the second step is given by independence among ay n ny and e. Let aL1 86,
= 0, and we will
obtain 01 + 82 = 1.
Also, the first-order derivative w.r.t. Bg is
0L1
Fe
Σ Em nn [2[(0] + 02 - 1)a} + 02(n) + n +e) -n!] (a, + ny + n c)
002
Ee
En
[2[(0] + 02 - 1) a. a. + 02(m m. + n n. + +e e) m med
VEV
Ee
En .na [2[[0] + 02 1) a, a + 02 +1 1
(9)
where the last step according to Ex[x²) unique solution
E22 [2|
V [x]. We further let 00,
8L, O. and will get the
1 1 o²
01
02 2 o?
(10)
2 + o2
C.2 PROOF FOR PROPOSITION
Let L2 (e]R(e)] Eg (R (c)) - E² [e)] and ((e) (0, 02 1)a, 02(n) + nł + n..
We derive the first-order derivation of Le w.r.t 01 and 0g. Firstly,
aL2
Ee
En.... n² [48
E
En n² [2(())at]
(11)
001
VV
V
NEV
VEV
0L
E.
En n2 (4) (a. + n + n + c
002
V
DEV
(12)
+ E2
En n² [2((e) (a + n + n + +c]
"EV
0L2 By letting 86;
0, we obtain the equation 0 + 02 = 1. Plugging it into OL* 8e,
we have
0L
E.
En n² [4(02(m) n E) 3 (a + n n + e)
00,
(13)
1 V
+
E2
Σ En n² (n + n + c) m.)) (a + n + n + c)]
FEV
aL. which is function of unless [0,, 0z] = 0] that gives rise to 862
= 0 for arbitrary distributions
of environments. We thus conclude the proof.
D PROOFS FOR SECTION 4
D.1 PROOF FOR THEOREM 1
We first present a useful lemma that interprets the invariance and sufficiency conditions with the terminology of information theory.
16

---

Published as a conference paper at ICLR 2022
Lemma 1. The two conditions in Assumption can be equivalently expressed 1) (Invariance): [(y:e/r) = and 2) (Sufficiency): I(y;r) is maximized.
Proof. For the invariance, we can easily arrive the equivalence given the fact 1xxe
(14)
For the sufficiency, we first prove that for ry satisfying that y c* (r) + n would also satisfy that r = arg max, ry; We prove it by contradiction. Suppose that r * arg max, r(;:)) and arg max, ry:r) where r' # r. Then there exists random variable such that r' (((rF)) where m is a mapping function. We thus have /(y:r') = T(y; r(y;r) which leads to contradiction.
(r);,,, = (r)
We next prove that for (Gv, r, satisfying that r arg max, [(; would also satisfy that y == c* (r) + n. Suppose that y o (r(r) + n and y c²(r') + n where r' o We then have the relationship [(e" (r');)) s I(c (r'):') which yields that r' = arg max, (y; and leads to contradiction.
Given the dependency relationship Gy y, have the fact that m I(y,z) 2) is equivalent to (z/G() Ily, Gv/z). Also, have (treating q(y (z) as variational distribution)
I(y; Gv = (xy Gv. e) e)
(Rl(p(y Gv. e) [|(()//)) Dr (ply,, 2))
(15)
S DKu(ply [q((2z))
Based on this, we have the inequality
T(y, GvIz) S min Drz(p(y/Gv, e)llayyz)).
(16)
g(ylz)
Also, we have (according to our definition in Eq. 6)
Dxi(p(y/Gr, e)(lg()|z)
((( log Pely = yo Gv Go)
= -EeBarpp
v
g(y yn 2v))
(17)
VEV
Pe = yu Gy = G,)
(G
(y log EE (e VEV
yolz iz Zz
where the second step is according Jensen Inequality and the equality holds ((z[Gr) is a delta distribution (induced by the GNN encoder h). Then the problem min DKI(Ply|G, G., e)]lg(y|z)) can be equivalently converted into
min EE
1
Σ (F(G)) VeV.
min | f)].
(18)
V
We thus have proven that minimizing the expectation term in Eq. 4 to minimize the upper bound of [y, Gv|z) and contributes to maxp(x/G.) z).
Second, we have
ely:
=Dkz(p(ylz, clppy/zzz)
=Dxz(p(ylz,e) | ((y(z,e))
(19)
(D - - (B. e) ee)l(ll((())))))
(
Besides, we have (according to the definition Eq. 6)
q(y yol z 2,)
(20)
(o
Byoopely
log
E,(g(y = y, lz = 2,
17

---

Published as a conference paper at ICLR 2022
Using Jensen Inequality, will obtain that
z)]) is upper bounded by
Ee Ee f) - EE fi]l] = [",
(21)
Hence we have proven that minimizing the variance term in Eq. 4 plays role for solving (x) elye)
D.2 PROOFS FOR THEOREM
With Lemma 1, we know that 1) the representation z (given by GNN encoder z = h(Gv) satisfies the invariant condition, i.e., p(y|z) - (2) and only if 7(y: e|z) and 2) the representation 2 satisfies the sufficiency condition, i.e., = (²()) + n if and only if z arg max, zy;
We denote the GNN encoder that satisfies the invariance and sufficiency conditions as h and the corresponding predictor model (Gv Ey (ylh"(Gv) with f = c* o ht. Since we assume the GNN encoder g(l[Gv) satisfies the conditions in Assumption I, then according to Assumption we know that there exists random variable such that G, m(z, Z) and p(y Z, e) would change arbitrarily across environments. Based on this, for any environment e that gives the distribution Pe Z), construct environment e' with the distribution per (y, 2, Z) that satisfies
Per (y, Z. = (),
222)
Then follow the reasoning line of Theorem 2.1 Liu et al. (2021) finish the proof by showing that for arbitrary function f = o h and environment e, there exists an environment e' such that
Ea-py(G)
Σ DEV
E n. p. (V yo)l
[V|
(23)
2 (G)
[V]
vEV
Concretely we have
(G)).,(G)
E Mww.s.aaaeeeeeas........... Zo), yoll
NEV
=EG'=p((G)
.p (GG
E Bao. 2.),
IV'
V'EV'
NEV
(B
Σ
E By Mo (20,
|V'
VV
WeV'
1 |
1
=EG(=p(())
V
v'ev'
=EG=p.(G)
M
VEV
=GG
E My... Ja
M
BEV
(24)
where the first equality given by Eq. 22 and the second/third steps are due to the sufficiency condition of h².
18

---

Published as a conference paper at ICLR 2022
D.3 PROOF FOR THEOREM: 3
Recall that according to our definition in Eq. 6, the KL divergence DEL D would be
P.ly = yo G, = G.)
DRL(Pely/Gw)loovr/ == (C)
Ey (x(C. log "EV
[
q(y yo Gv G.)
(25)
Based on this newly defined KI. divergence, can extend the information-theoreti framework (Federici et al., 2021) for analysis on graph data. First, we can decompose the training error (resp. OOD error) into representation error and latent predictive error.
Lemma 2. For any GNN encoder q( Gv) and classifier g(y) z)) we have
D Gv)) < (GG + DKL (xl(pe(yll)laayyl)) (y & L (Gv;ylz) - (y
(26)
(27)
Proof. Firstly, we have
(y (la(y//G.))
Poly = yo G. = G,))
-EGmp.(G)
log
[
gly = yo Gv G.)
Pely y/ Gv Gz)
-EG-p.(G)
Byo (x)G.
log E Gz. g(y = Vr = 2v.)
(28)
[V]
vEV
Pely = Vo Gr = Gw)
<EG-pa(G)
yo Sor G.
log
qly yolz 1z zwx)
NEV
-D DDrr. (l))y))))))
where the third step again due to Jensen Inequality and the equality holds once q(z (vv is delta distribution.
Besides, we have
DKL(pe (y (v
1
log Pely = Gy = Go)
(BG
E B.
M VEV
q(y Vo iz 2x)
(y = yu G., = G.)pely = Volz Zu)
-BGxp.(G)
E Ba
log
M
Poly = yo 2,)g(y = Vo 12 = 2v)
=[(Gv:y|z) (yLll((yye)ll((xzz)))
(29)
The result for D (pw (yl (y) can be obtained in a similar way.
Lemma 3. For any q(z(Gr) and q(ylz)) (z), the following inequality holds for any satisfying p(z
z/e = e) > E
I(y: [(y: (1 + D
2
(
<
(30)
2a
Proof. The proof can be adapted from the Proposition 3 in Federici et al. (2021) by replacing in our case with t.
19

---

Published as a conference paper at ICLR 2022
Table Statistic information for MeatthhExxppiee datasets.
Dataset
#Nodes
#Edges
#Density
Avg Degree
Max Degree
DE
9498
153138
0.0033
16
3475
ENGB
7126
35324
0.0013
4
463
ES
4648
59382
0.0054
809
FR
6549
112666
0.0052
17
1517
PTBR
1912
31299
0.0171
16
455
RU
4385
37304
0.0038
8
575
TW
2772
63462
0.0165
1171
The results of Lemma 2 and indicate that we aim to reduce the OOD error mea- sured by (yy((yG Gv), one need control three terms: 1) Te (Gv; ylz), 2) DKL (P<(y/z)laa z) and 3) (y;elzz) The next lemma unifies minimization for the first two terms.
Lemma 4. For any g(z) Gv) and q(y 2), we have
min (xl(pe (z)( + min Le (Gv min D <(yl2)
((2[G.)
(31)
Recall that ((ylz) is variational distribution. We have Proof.
(G ylz)
(P G))l))((yl))
(y Gv)ll((yz))) - DKr DK..6e(x12)lll(xss))))
(32)
I (P ())l)(())))
Therefore, we can see that flzz) is upper bounded by (yy and the equality holds if and only if D (y ((())))) O. We thus conclude the proof.
Recall that according to Lemma have the fact that our objective in Eq. essentially has the similar effect as
min g(x(G)))()))))
ely:)
(33)
Based on the Lemma 2. and 4, we know that optimization for the objective Eq. 4 can reduce the upper bound of OOD error given by DKL (pe (y (Gy)ll(( G,) on condition that (G yl)) = Ie (Gv:
We conclude our proof for Theorem 3.
E DATASETS AND EVALUATION PROTOCOLS
In this section, we introduce the detailed information for experimental datasets and also provide the details for our evaluation protocols including data preprocessing, dataset splits and the ways for calculating evaluation metrics. In the following subsections, we present the information for the three scenarios, respectively.
E. ARTIFICIAL DISTRIBUTION SHIFTS ON CORA AND AMAZON-PHOT
Cora and -aaazon-Phote are two commonly used node classification benchmarks and widely adopted for evaluating the performance of GNN designs. These datasets are of medium size with thousands of nodes. See Table for more statistic information. Cora is citation network where nodes represent papers and edges represent their citation relationship. Amazon-Phott is a purchasing network where nodes represent goods and edges indicate that two goods are frequently bought together. In the original dataset, the available node features have strong correlation with node labels. To evaluate model's 's ability for aut-of-distributin generalization, we need to introduce distribution shifts into the training and testing data.
For each dataset, we use the provided node features to construct node labels and spurious environment- sensitive features. Specifically, assume the provided node features X,. Then adopt randomly
20

---

Published as a conference paper at ICLR 2022
70
70
70
NOCAIC
05
05
ROCAUC
63
60
60
OOD
0OD
000
GEN
(b) GAT
[c] GENI
Figure 6: Comparison of different leave-out data on SeatthhExppiiee We consider three GNN backbones trained with ERM. The "OOD" means that train the model on graph DE and report the metric on another graph ENGB. The "IID" means that we train the model on 90% nodes of DE and report the metric the remaining nodes. The results clearly show that the model performance suffers significantly drop from the case "IID" to the case "OOD". This indicates that the graph-level splits used in Section 5.2 indeed introduces distribution shifts
splitting for and would require the model to deal with out-of disttiibbbttttionnn data during test.
initialized GNN (with input of X₁ and adjacency matrix) to generate node labels Y (via taking an argmax in the output layer obtain one-hot vectors), and another randomly initialized GNN (with input of the concatenation of Y and an environment id) to generate spurious node features X2. After that, we concatenate two portions of features X [X X2] as input node features for training and evaluation. In this way, we construct ten graphs with different environment id's for each dataset. We use one graph for training, one for validation and report the classification accuracy on the remaining graphs. One may realize that this data generation is generalized version of our motivating example in Section 3.1 and we replace the linear aggregation as randomly initialized graph neural network to introduce non-linearity.
In fact, with our data generation, the original node features X1 can be seen as features that sufficiently predictive for node labels and insensitive to different environments, while the generated features X2 are camaainvvarian features that are conditioned on environments. Therefore, in principle, the ideal case for the model is identify and leverage the invariant features for prediction. In practice there exist multiple factors that may affect model's learning, including the local optimum and noise in data. Therefore, one may not expect the model to exactly achieve the ideal case since there also exists useful predictive information in X2 that may help the model to increase the training accuracy. Yet, through our experiments in Fig. 2(b) and 3(b), we show that the reliance of EERM spurious features is much less than ERM, which we believe could serve as concrete evidence that our approach is capable for guiding the GNN model to alleviate reliance on domain-variant features.
E.2 DOSSIN TRANSFERS ON MULTI-GRAPHE DATA
A typical scenario for distribution shifts graphs is the problem of cross-domain transfers. There are quite a few real-world situations where one has access to multiple observed graphs each of which from a specific domain. For example, in social networks, the domains can be instantiated as where or when the networks are collected. In protein networks, there may exist observed graph data (protein-protein interactions) from distinct species which can be seen distinct domains. In short, since most of graph data records the relational structures among a specific group of entities and the interactions//elationshhpp among entities from different groups often have distinct characteristies, the data-genen data-generating distributions would vary across groups, which bring up domain shifts.
Yet, to enable transfer learning across graphs, the graphs in one dataset need to share the same input feature space and output space. We adopt two public datasets Twi tch-Exp) i ci and Facebook-100 that satisfy this requirement
Twitch-Exp) iicit contains seven networks where nodes represent Twitch users and edges rep- resent their mutual friendships. Each network collected from a particular region, including DE, ENGB, ES, FR, PTBR, RU and TW. These seven networks have similar sizes and different densities and maximum node degrees, as shown in Table 4. Also, in Fig. 6, we compare the ROC-AUC results on different leave-out data. We consider GCN, GAT and GCNII as the GNN backbones and train the model with standard empirical risk minimization (ERM). We further consider two ways for data splits. In the first case, which call "OOD", we train the model the nodes of graph DE and
21

---

Published as a conference paper at ICLR 2022
40300
20000
10000
(a) Node Number
0.050
Density
4000
2000
10 11
(c) Degree
Figure 7: Comparison of node numbers, densities and maximum node degrees of fourteen graphs used in our experiments on Facebook-100. The index 0-13 stand for John Hopkins, Caltech, Amherst, Bingham, Duke, Princcton, WashU, Brandeis, Carnegie, Cornell, Yale, Penn, Brown and Texas, respectively. As we can see, these graphs have very distinct statistics, which indicates that there exist distribution shifts w.r.t. graph structures.
report the highest ROC-AUC on the nodes of another graph ENGB. In the second case, which we call "IID", we train the model on 90% nodes of DE and evaluate the performance on the lcave-out 10% data. The results in Fig. 6 show that the model performance exhibits clear drop from "IID" to "OOD", which indicates that there indeed exist distribution shifts among different input graphs. This also serves a justification for our evaluation protocol in Section 5.2 where we adopt the graph-level splitting to construct raaining/vllddatioonessing sets.
Another dataset is Facebook -100 which consists of 100 Facebook friendship network snapshots from the year 2005, and each network contains nodes as Facebook users from a specific American university. We adopt fourteen networks in experiments: John Hopkins, Caltech, Amherst, Bingham, Duke, Princeton, WashU, Brandeis, Carnegie, Cornell, Yale, Penn, Brown and Texas. Recall that in Section 5.2 use Penn, Brown and Texas for testing, Comnel and Yale for validation, and use three different combinations from the remaining graphs for training. These graphs have significantly diverse sizes, densities and degree distributions. In Fig. which indicates that the distributions of graph structures among these graphs are different. Concretely, the testing graphs Penn and Texas are much larger (with 41554 and 31560 nodes, respectively) than training/validation graphs (most with thousands of nodes). Also, the training graphs Caltech and Amherst are much denser than other graphs the dataset, while some graphs like Penn have nodes with very large degrees. These statistics suggest that our evaluation protocol requires the model to handle different graph structures from training/validation to testing data.
present comparison
E.3 TEMPORAL EVOLUTION ON DYNAMIC GRAPH DATA
Another common scenario is for temporal graphs that dynamically evolve as time goes by. The types of evolution can be generally divided into two categories. In the first case, there are multiple graph snapshots and each snapshot is taken at one time. As time goes by, there exists sequence of graph snapshots which may contain different node sets and data distributions. Typical examples include financial networks that record the payment flows among transactions within different time intervals. In the second case, there is one graph that evolves with node/edge adding or deleting. Typical examples include some acage-scale real real-world graphs like social networks and citation networks where the distribution for node features, edges and labels would have strong correlation with time (in different scales). We adopt two public real-worle datasets Ellipt elliptic ic and classification experiments.
iv for node
22

---

Published as a conference paper at ICLR 2022
positive label rate
0.20
0.19
0.00
T1
V31 71 72 13 74 75
Figure 8: The label rates and positive label rates of training/validationeessig data splits of Elliptic. The positive class (illicit transaction) and negative class (licit transaction) are very imbalanced. Also, in different splits, the distributions for labels exhibit clear differences.
Elliptic contains sequence of 49 graph snapshots. Each graph snapshot is network of Bitcoin transactions where each node represents one transaction and each edge indicates a payment flow. Approximately 20% of the transactions to identify illicit transaction in the future observed network. Since in the original dataset, the first six snapshots have extremely imbalanced classes (where the illicit transactions are less than 10 among thousands of nodes), we remove them and use the 7th-1 1 1tth/1thhh1 1hth 77th-49th snapshots for crining/validaiionnesttngg Also, due the fact that each graph snapshot has very low positive label rate, we group the 33 testing graph snapshots into test sets according to the chronological order. In Fig. 8 we present the label rate and positive label rate for rraiiing/aliiationneee can see, the positive label rates are quite different in different data sets. Indeed, the model needs to handle distinct label distributions from training to lesting data.
marked with licit illicit ones and the goal is
sets. As we
OGB-Arxiv v is composed of 169.343 Arxiv CS papers from 40 subject areas and their citation relationship. The goal is to predict paper's subject area. In (Hu et al., 2020), the papers published Also, the authors adopt
before 2017, on 2018 and since 2019 used for the transductive learning setting, i.c., the nodes in validation and test sets also exist the graph for training. In case, instead adopt inductive learning setting where the nodes in validation and test sets are unseen during training. which more akin to the real-world situation. Besides, for better evaluation on generalization, especially extrapolating new data, consider dataset splits with larger year gap: we use papers published before 201 for training, from 2011 to 2014 for validation, and after 2014 for test. Such dataset splitting way would introduce distribution shift between training and testing data, since several latent influential factors (e.g., the popularity of research topics) for data generation would change over time. Fig. we visualize the T-SNE embeddings of the nodes and mark the we can see that testing nodes non-overlapped with the training/validation ones exhibit an increase, which suggests that the distribution shifts enlarge as time difference goes large. This phenomenon echoes the results we achieve Table 3 where we observe that as the time difference between testing and training data goes larger, model performance suffers clear drop, with ERM suffering more than EERM.
nodes with different colors. From Fig. 9(a) to Fig. 9c)),
F IMPLEMENTATION DETAILS
In this section, we present the details for our implementation in Section incluuiig the model architectures, hyper-parametee settings and training details in order for reproducibility. Most of experiments are run on GeForce RTX 2080Ti with 1 IIB except some experiments requiring large GPU memory for which we adopt RTX 8000 with 48GB, The configurations of our environments and packages are listed below:
Ubuntu 16.04
CUDA 10.2
PYTHON 3.7
Numpy 1.20.3
PyTorc 1,9.0
23

---

Published as a conference paper at ICLR 2022
(a) (colored yellow)
(b) Test nodes within 2016 2018 (colared yellow)
(c) Test nodes within 2018 2020 (colored yellow)
Figure 9: T-SNE visualization of training/validationnessing nodes OGB-Arxiv We mark training nodes (within 1950-2011) and validation nodes (within 201 2011-2014) as red and blue, respectively. In (a)-c), the test nodes within different time intervals are visualized as yellow points. We can see that the time difference of testing data and training/validation data goes large from (a) to (c), the testing nodes non- non-overlapped with training/validationn ones become more, which suggests that the distribution shifts become more significant and require the model extrapolate to more difficult future data.
Py'Torch Geometric 1.7.2
F.1 MODEL ARCUITECTURES
In our experiments Section we adopt different GNN architectures as the backbone. Here we introduce the details for them.
GCN. We use the GCNConv available Pytorch Geometric for implementation. The detailed architecture description as below:
A sequence of L-layer GCNConv.
Add self-loop and use batch normalization for graph convolution each layer.
Use ReLU as the activation.
GAT. We use the GATConv available in Pytorch Geometric for implementation. The detailed architecture description is as below:
24

---

Published as a conference paper at ICLR 2022
A sequence of L-layer GATConv with head number H.
Add self-loop and use batch normalization for graph convolution in each layer.
Use ELU as the activation.
GraphSAGE. We use the SAGEConv available Pytorch Geometric for implementation. The detailed architecture description is as below:
A sequence of L-layer SAGEConV.
Add self-loop and use batch normalization for graph convolution each layer.
Use ReLU as the activation.
GCNIL We the implementation" provided by the original paper (Chen et al., 2020a). The associated hyper-paramelens in GCNII model are set as: AGGNII = 0.1 and ACCNII = 1.0.
GPRGNN. We use the implementation" provided by Chien al. (2021). We adopt the PPR initial- ization and GPRprop as the propagation unit. The associated hyper-parameten in GPRGNN model set as: aGPAGNN 0.1.
F.2 HYPER PARAMETER SETTINGS
The
for model architectures set default values in different cases. Other hyper- parameters are searched with grid search on validation dataset. The searching space are as follows: learning rate for GNN backbone a (0.0001, 0.0002, 0.001, 0.005, 0.01), learning rate for graph editers Og E {0.0001, 0.001, 0.005, 0.01), weight for combination B E (0.2, 0.5, 1.0, 2.0,3.0) 3.0), number of edge editing for each node {1,5, 10), number of iterations for inner update before one-step outer update 7' E 5}.
F.2.1 SETTINGS FOR SECTION 5.1
We consider 2-layer GCN with hidden size 32. We use weight decay with coefficient set as 1e-3. Besides, we 0ig 0.005, a 0.01, 3 2.0, 5, 11
F.2.2 SETTINGS FOR SECTION 5.2
For GCN, we set the layer number L as 2. For GAT, set L = 2 and // 4. For GCNII, we set the layer number as 10. We use hidden size 32 and weight decay with coefficient set as 1e-3.
For Twitch-Expiiciie other haper-parameters
follows:
* GCN: ag = 0.001, ay = 0.01, 8 = 3.0, s 5, 1. GAT: 0g = 0.005, a = 0.01, 3 = 1.0, s 5,7
GCNII: ag 0.01, ay = 0.001, 3 = 1.0, s = =
For Facebook -000, other hyper-parameterss are as: ag 0.005, ay 0.01, 1.0, =
F.2.3 SETTINGS FOR SECTION 5.3
For GraphSAGE and GPRGNN, we set the layer number as 5 and hidden size as 32.
For Elliptic, other hyper-parameter set follows:
* GraphSAGE: Og = 0.0001, a, 0.0002, 3 = 1.0, s 5
GPRGNN: ag = 0.005, ay = 0.01, 3 = 1.0, s = 5. =
For OGB--GGB--iiee Arxivv other hyper-parameter are set as follows:
'https: thub. com www../oo/aaaannnn0oo1a 6 //GPGGNN
25

---

Published as a conference paper at ICLR 2022
GraphSAGE: 0g 0.01, ay 0.005, 3 0.5, 8 = 1, T 5.
GPRGNN: 0g = 0.001, ay 0.01, 8 = 1.0, 8 - 1, = 5.
F.3 TRAINING DETAILS
For each method, we train the model with fixed number of epochs and report the test result achieved at the epoch when the model provides the best performance validation set.
G MORE EXPERIMENT RESULTS
We provide additional experiment results in this section. In Fig. 10 and 11 present the distribution of test accuracy on Cora when using SGC and GAT, respectively, as the GNNs for data generation. In Fig. 12 and 13 we further compare with the training accuracy using all the features and removing the spurious ones for inference. These results are consistent with those presented in Section 5. which again verifies the effectiveness of our approach. Besides, the corresponding extra results on P Photo are shown in Fig. 14, 15, 16 and 17, which also back up our discussions in Section 5.1.
26

---

Published as a conference paper at ICLR 2022
90
80
Accuracy
70
60
50
ERM
EERM
T1
T2
T3
T4
T5
T6
T7
T8
Figure 10: Distribution of test accuracy results on Cora with artificial distribution shifts generated by SGC as the GNN generator.
80
Accuracy
70
50
ERM EERM
40
T1
T2
T3
T4
T5
T6
T7
T8
Figure 11: Distribution of test accuracy results on Cora with artificial distribution shifts generated by GAT as the GNN generator.
27

---

Published as a conference paper at ICLR 2022
85.0
82.5
80.0
77.5
Accuracy
75.0
72.5
70.0
w/ spurious
67.5
w/o spurious
65.0
ERM
EERM
Figure 12: Comparison of training accuracy using all the features v.s. removing the spurious features
inference on Cora with artificial distribution shifts generated by SGC as the GNN generator.
85.0
82.5
80.0
77.5
Accuracy
75.0
72.5
70.0
w/ spurious
67.5
w/o spurious
65.0
ERM
EERM
Figure 13: Comparison of training accuracy using all the features v.s. removing the spurious features for inference on Cora with artificial distribution shifts generated by GAT the GNN generator.
28

---

Published as a conference paper at ICLR 2022
85
80
Accuracy
75
ERM EERM
T1
T2
T3
T4
T5
T6
T7
T8
Figure 14: Distribution of test accuracy results Photo with artificial distribution shifts generated by SGC as the GNN generator.
85
80
Accuracy
75
70
65
ERM
EERM
60
T1
T2
T3
T4
T5
T6
T7
T8
Figure 15: Distribution of accuracy results on Photo with artificial distribution shifts generated by GAT as the GNN generator.
29

---

Published as a conference paper at ICLR 2022
85.0
82.5
80.0
77.5
Accuracy
75.0
72.5
70.0
w/ spurious
67.5
w/o spurious
65.0
ERM
EERM
Figure 16: Comparison of training accuracy using all the features v.s. removing the spurious features for inference on Photo with artificial distribution shifts generated by SGC as GNN generator.
85.0
82.5
80.0
77.5
Accuracy
75.0
72.5
70.0
w/ spurious
67.5
w/o spurious
65.0
ERM
EERM
Figure 17: Comparison of training accuracy using all the features v.s. removing the spurious features
for inference on Photo with artificial distribution shifts generated by GAT the GNN generator.
30


Reviews:
[{"review_id": "vRFW9bcs4dA", "reviewer": "Reviewer_DyjE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n- Provided a new approach to retrieve invariance information among different environments.\n- Presented the theoretical foundations and the proposed approach separately in a clear and persuading manner.\n\nWeakness:\n- The contribution of adversarial attack or resilient GNN beyond prior work is not fully discussed. Simply list a few at the bottom.\n- The OOD problem has been discussed in graph neural network adversarial robustness literature and causal inference literature. Although this paper did a fairly good job in tackling this problem from a different perspective, the novelty is not as great as claimed.\n- The experiment only considered one baseline which is ERM. Other competing methods such as structural risk minimization didn't get enough attention. The experimental design looks good otherwise.\n- The function in equation 1 doesn't look right. Should be [l(f(x), y)|e].\n- Fig 1(b) lack detailed explanation.\n- Baselines do not include \n\n\n- TDGIA: Effective Injection Attacks on Graph Neural Networks. Zou Xu, Zheng Qinkai, Dong Yuxiao, Guan Xinyu, Kharlamov Evgeny, Lu Jialiang, Tang Jie. KDD 2021.\n- Adversarial Attacks on Graph Neural Networks via Node Injections: A Hierarchical Reinforcement Learning Approach. Sun Yiwei, Wang Suhang, Tang Xianfeng, Hsieh Tsung-Yu, Honavar Vasant. WWW 2020.\n- All You Need Is Low (Rank) Defending Against Adversarial Attacks on Graphs. Entezari Negin, Al-Sayouri Saba A, Darvishzadeh Amirali, Papalexakis Evangelos E. WSDM 2020.\n- Gnnguard: Defending graph neural networks against adversarial attacks. Zhang Xiang, Zitnik Marinka. arXiv preprint arXiv:2006.08149 2020.\n- Graph Random Neural Networks for Semi-Supervised Learning on Graphs. Feng Wenzheng, Zhang Jie, Dong Yuxiao, Han Yu, Luan Huanbo, Xu Qian, Yang Qiang, Kharlamov Evgeny, Tang Jie. Advances in Neural Information Processing Systems 2020.\n", "summary_of_the_paper": "- This paper tackles the out-of-distribution problem for node-level prediction on graphs from the invariance perspective. It presents a novel approach in which the whole graph is divided into n ego-graphs where n is the number of nodes. All the ego-graphs can be treated as a set of IID. Based on this division, the model can be trained to defend the adversarial attack from multiple environments. \n- This work extends the discussion of the OOD problem to node-level tasks on graphs. A new learning approach is proposed and theoretically proven to be correct. In empirical experiments on multiple datasets, the approach (EERM) outperforms its counterpart baseline ERM.\n", "summary_of_the_review": "I recommend a reject. This paper developed a new approach to tackle a problem that has already been discussed. Although the presentation is well organized and easy to read, the limited novelty and the lack of excitement bring me to this recommendation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "sm_QIWCQexx", "reviewer": "Reviewer_Wo9P", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strength\n1. **Overall, the idea is new to me and experiments are comprehensive.**\n2. **The theorem proposed are rigorously proved in the appendix.**\n\n## Weaknesses\n1. **Missing some related work.** \nBesides OOD on graph and other domain, there are couple of work [1,2] study the generalization from non-I.I.D training data in GNNs. Some discussion on this is necessary.\n1. **Technical writing is dense and hard to follow**\nIn Figure 1, the context generator is actually not generating a new graph, which instead augment the input graph. The terminology used here is confusing. \n\n1. **Assumption 1 seems to be unrealistic.**\nIn practice, do we really have the invariance property? Any kind of study supports this. I feel this assumption is the foundation of the paper that tries to bridge OOD and invariant risk minimization. For example, after graph editing, it would be hard to obtain invariant property. If we remove several author and add authors from different domain, the paper category will probably change. \n\n[1] Ma, Jiaqi, Junwei Deng, and Qiaozhu Mei. \"Subgroup Generalization and Fairness of Graph Neural Networks.\" NeurIPS 2021.\n\n[2] Zhu, Qi, et al. \"Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training Data.\" NeurIPS 2021.", "summary_of_the_paper": "This paper studies the problem of distribution shifts as out-of-distribution generalization. Specifically, it formulates the OOD problem as invariant risk minimization under different environments. The relation between these two has been extensively discussed in the paper. Multiple environment is done by graph editing using policy gradient. Experiments on three different kind of distribution shifts are presented and the effectiveness of EERM is validated.", "summary_of_the_review": "After reading this paper several times, I start to understand the underlying connection between OOD and invariant property. I think the readability of the paper can be greatly improved by introducing the connection first then talk about their implementation. However, the creation of multiple environment while keeping the invariant property is unclear to me. I might misunderstand this part. Currently, I think it is marginally below the acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "MGVbVURaf0k", "reviewer": "Reviewer_SVEc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "< Strength >\n1. OOD generalization for graph neural networks is important, but it is a relatively unexplored research area.\nThis paper will be attractive for many graph-related machine learning researchers.\n\n2. OOD for graph dataset are not trivial because of their own unique characteristic of the graph-structured dataset (for example, there are only one graph), but the proposed approach, \"Explore-to-Extrapolate Risk Minimization\",  that adopts K context generators solve the problems in a smart way. \n\n3. The proposed method is validated empirically and theoretically. \n\n< Weakness and Questions >\n1. There are some related graph OOD works [1,2]. Additional discussion will be helpful for the audience. Especially, this paper seems similar to [1], and a detailed discussion will be needed.\n\n2. The baseline methods for experimental results are not enough. For example, Table 3 reports the quantitative results for the OGB-Arxiv dataset, but the baseline is only ERM.\n\n3. In [3], they provide the benchmark settings and some results for OGBN-Arxiv. The quantitative results for normal OGBN-Arxiv experimental settings will be interesting.\n\n[1] Bevilacqua, Beatrice, et al. \"On Single-environment Extrapolations in Graph Classification and Regression Tasks.\" (2020).\n\n[2] Bayer, Jens, David Münch, and Michael Arens. \"Image-based OoD-Detector Principles on Graph-based Input Data in Human Action Recognition.\" arXiv preprint arXiv:2003.01719 (2020).\n\n[3] Hu, Weihua, et al. \"Open graph benchmark: Datasets for machine learning on graphs.\" arXiv preprint arXiv:2005.00687 (2020).", "summary_of_the_paper": "The importance of out-of-domain (OOD) generalization has emerged, and there is much research for out-of-domain generalization [1,2,3,4].\nHowever, the related works on the graph-structured datasets are not explored well.\nOOD generalization of the graph is not trivial because the graph has the interconnection among nodes and the existence of structural information.\nTo solve the problems, this paper proposes a new method, multiple contexts explore that are adversarially trained to maximize the variance of risk.\nThe proposed model is validated on many diverse datasets, Cora, Amazon-Photo, Twitch-explicit, and so on.\n\n[1] Arjovsky, Martin, et al. \"Invariant risk minimization.\" arXiv preprint arXiv:1907.02893 (2019).\n\n[2] Sagawa, Shiori, et al. \"Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization.\" arXiv preprint arXiv:1911.08731 (2019).\n\n[3] Krueger, David, et al. \"Out-of-distribution generalization via risk extrapolation (rex).\" International Conference on Machine Learning. PMLR, 2021.\n\n[4] Creager, Elliot, Jörn-Henrik Jacobsen, and Richard Zemel. \"Environment inference for invariant learning.\" International Conference on Machine Learning. PMLR, 2021.", "summary_of_the_review": "Please see the weakness and questions section.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0Y0oYkIB1GW", "reviewer": "Reviewer_xk81", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written, polished, and easy to follow. The problem that is studied is important and relevant for the community. The proposed approach is well motivated. The theory is sound, however, the technical novelty is limited. The experiments are well executed and mostly convincing, however, an ablation/sensitivity study is missing. \n\nComments:\n- The discussion in terms of a BFS tree rooted at node v is a bit convoluted. Note, the very general and large class of recursive message-passing GNNs [1] subsumes this. Since the message-passing framework is well established in the literature rephrasing some of the discussions and the assumptions (e.g. Assumption 1) in this framework/language will significantly improve readability. At the very least the relation to message-passing GNNs should be discussed and a citation is warranted.\n- The theory is sound, however, the technical novelty is limited. Once the input graph has been decomposed into a set of ego-graphs the definitions, formulations and theory are all straightforward adaptions from the respective versions for IID data. Nonetheless, there is some value in doing this.\n- It is not clear how much of the apparent benefit is due to the new objective (i.e. the addition of the variance term) vs. the (inherent) benefit of data augmentation. An ablation study should be performed where: (i) first the auxiliary context generators are not trained to maximize the variance (e.g. instead delete/add edges randomly with different probabilities), and (ii) the variance term in the Eq. 5 is removed training only on the K augmented graphs (e.g. again using random context generators). In any case, a comparison with existing data augmentation techniques for graphs (e.g. [2, 3]) is prudent. Similarly, different \"ground-truth\" environments can be used to train the generators (see question below). \n- Relatedly, the sensitivity w.r.t. the hyperparameters should be studied, at least for key hyperparameters such as L, K, and \\beta.\n- The are only few details provided about the graph generators even though they are an important component of the proposed approach. For example, as far as I can tell there are no constraints on the generated graphs, which can lead to highly unrealistic graphs. Is this the case in practice? Moreover, for the generator the parametrized matrix P_k requires O(N^2) memory which severely limits scalability, how is this issue handled, e.g. for OGB-Arxiv? In addition, using the REINFORCE algorithm to optimize the generator might be suboptimal since the gradients can suffer from high variance. How sensitive are the generators to hyperparameters?\n- It is not clear which results are statically significant (especially in Table 2 and 3).\n\nQuestions:\n- What is the accuracy of EERM when there is no distribution shift? For example if we train a GCN with ERM vs. EERM on Cora using random train/val/test split without introducing an artificial distribution shift how big is the gap in accuracy? In other words, is there a price for using EERM? Relatedly, how well does EERM perform on the standard OGB-Arxiv split and how do these results compared to the OGB leaderboard (using the original transductive setting)? \n- Why is the performance on GAT significantly lower compared to GCN and SGC on Figure 2c? Is GAT more sensitive to distributions shift? If yes, can you provide some insight why? If not, is it an orthogonal issue such as not properly tuning the hyperparameters?\n- When training with multiple graphs is the assumption that we have a single environment? What happens if we treat the nodes in each graph as belonging to a separate \"ground-truth\" environment? This would remove the need for context generators and can directly show the benefits of using the variance term in the objective. Similarly, on OGB-Arxiv each year (or set of years) can be considered a separate environment, using multiple for training and one or two for testing.\n\nReferences:\n1. Gilmer et al. \"Neural message passing from quantum chemistry\"\n2. Wang et al. \"NodeAug: Semi-Supervised Node Classification with Data Augmentation\"\n3. Rong et al. \"DropEdge: Towards Deep Graph Convolutional Networks on Node Classification\"\n", "summary_of_the_paper": "The paper adapts a recently proposed invariant risk minimization approach for tackling distribution shift on node-level predictions on graphs. The main idea is to decompose the graph into a set of ego-graphs rooted at each node, thus incorporating structural information. Since the learning objective requires data from different environments they authors introduce auxiliary context generators trained to maximize the variance loss. ", "summary_of_the_review": "The paper is well written, polished, and easy to follow. The problem that is studied is important and relevant for the community. The proposed approach is well motivated. The theory is sound, however, the technical novelty is limited. The experiments are well executed and mostly convincing, however, an ablation/sensitivity study is missing.  I am willing to increase my score if the authors address the issues with the experimental evaluation that I raised in the main review. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers have improved their scores after the rebuttal, and I agree that the work has value. It proposes a model-driven data augmentation approach to environment-invariant graph representation. Just like most data augmentation works in graph representation learning, the approach relies on graph proposal generator. The work has an implicit mechanism hidden in the graph generator (the authors' reply to a reviewer that "we target the extrapolation via a new invariant learning approach that is agnostic to specific GNN models" is a misunderstanding of why & how these types of methods work). The submission could significantly improve the introduction by properly describing the work w.r.t. other OOD efforts in graph representation learning. While the tasks of different works may be different (e.g., graph classification vs node classification), it is important to emphasize what each different approach brings to the table (rather than just state that the tasks are different). I hope the authors take this opportunity to improve the introduction. This work is more similar to the former OOD graph representation works than IRM & REX, since (without modeling assumptions) both IRM and REX require the support of the environments in test to be a subset of the ones in training. The present work does not need this support assumption since it uses an implicit mechanism in the graph generator.

The toy example in Section 3.1 is informative, thank you. The theory looks solid and easy to understand. The technical novelty is limited, since once the input graph has been decomposed into a set of ego-graphs the definitions, formulations, and theory are all straightforward adaptations from the respective versions for IID data. 

Minor:
- In Assumption 2, m() should be defined inside the assumption.
Decision: Accept (Poster)