# HANDLING DISTRIBUTION SHIFTS ON GRAPHS: AN INVARIANCE PERSPECTIVE


**Qitian Wu[∗]**
Shanghai Jiao Tong University
echo740@sjtu.edu.cn

**Junchi Yan[†]**
Shanghai Jiao Tong University
yanjunchi@sjtu.edu.cn


**Hengrui Zhang[∗]**
University of Illinois at Chicago
hzhan55@uic.edu

**David Wipf**
Amazon
daviwipf@amazon.com


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[1].

1 INTRODUCTION

As the demand for handling in-the-wild unseen instances draws increasing concerns, out-ofdistribution (OOD) generalization (Mansour et al., 2009; Blanchard et al., 2011; Muandet et al., 2013;
Gong et al., 2016) occupies a 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 et al. (2019); Mancini
et al. (2020). A more concerning example is that a model for COVID-19 detection exploits undesired
‘shortcuts’ from data sources (e.g., hospitals) to boost training accuracy (DeGrave et al., 2021).

Recent studies of the OOD generalization problem like Rojas-Carulla et al. (2018); Bühlmann (2018);
Gong et al. (2016); Arjovsky et al. (2019) treat the cause of distribution shifts between training and
testing data as a potential unknown environmental variable e. 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) = p(x|e)p(y|x, e). With E as the support of environments, f (·) as
a prediction model and l(·, ·) as a loss function, the OOD problem could be formally represented as

min max (1)
_f_ _e∈E_ [E][(][x][,y][)][∼][p][(][x][,][y][|][e][=][e][)][[][l][(][f] [(][x][)][, y][)][|][e][]][.]

_∗This work was done during authors’ internship at AWS Shanghai AI Lab._
_†Corresponding author is Junchi Yan. The SJTU authors are also with MoE Key Lab of Artificial Intelligence,_
Shanghai Jiao Tong University.
[1The implementation is public available at https://github.com/qitianwu/GraphOOD-EERM.](https://github.com/qitianwu/GraphOOD-EERM)


-----

Such a problem is hard to solve since the observations in training data cannot cover all the environments in practice. Namely, the actual demand is to generalize a model trained with data from
_p(x, y_ **e = e1) to new data from p(x, y** **e = e2). Recent research opens a new possibility via**
_|_ _|_
learning domain-invariant models (Arjovsky et al., 2019) under a cornerstone data-generating assumption: there exists a 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 to equal conditional distribution p(y|h(x), e = e) for ∀e ∈E. The implication is that such
a 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).

While the OOD problem is 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 in 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 as 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-implement tools for modeling relational structures in broad AI areas (vision, texts, audio,
etc.), enhancing its robustness to distribution shifts is a pain point for building general AI systems,
especially applied to high-stake applications like autonomous driving (Dai & Gool, 2018), 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 to show its practical efficacy. Concretely:

**1. To accommodate the non-IID nature of nodes in a graph, we fragment a graph into a set of**
ego-graphs for centered nodes and decompose the data-generating process into: 1) sampling a whole
input graph and 2) sampling each node’s label conditioned on ego-graph. Based on this, we can inherit
the spirit of Eq. 1 to formulate the OOD problem for node-level 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-Extrapolate 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, we 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-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).


-----

|Col1|Col2|Context Generator 1|GNN Model +|
|---|---|---|---|
|Input Data||Context Generator 2||


Context

Generator 1

GNN Model

Input Data Generator 2Context… + : publish avenue: citation index

Context : paper's sub-area

Generator : time of publication

_Explore_ _Extrapolate_

_Forward Data Flow_ _REINFORCE Update_ _Gradient Update_

(a) (b) (c)


Figure 1: (a) The proposed approach Explore-to-Extrapolate Risk Minimization which entails K
context generators that generate graph data of different (virtual) environments based on input data
from a single (real) environment. The GNN model is updated via gradient descent to minimize a
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 as bold letters while the corresponding realizations are denoted as thin letters.

2.1 OUT-OF-DISTRIBUTION PROBLEM FOR GRAPH-STRUCTURED DATA

An input graph G = (A, X) contains two-fold information[2]: an adjacency matrix A = _avu_ _v, u_
_{_ _|_ _∈_
_V_ and node features X = _xv_ _v_ _V_ where V denotes node set. Apart from these, each node
_}_ _{_ _|_ _∈_ _}_
in the graph has a label, which can be represented as a vector Y = _yv_ _v_ _V_ . We define G as a
_{_ _|_ _∈_ _}_
random variable of input graphs and Y as a random variable of node label vectors. Such a definition
takes a global view and treat the input graph as a whole. Based on this, one can adapt the definition
of general OOD problem Eq. 1 via instantiating the input as G and the target as Y, and then the data
generation can be characterized as p(G, Y|e) = p(G|e)p(Y|G, e) where e is a random variable of
environments that is a latent variable and impacts data distribution.

However, the above definition makes little sense in node-level problems where in most cases there is a
single input graph that contains a massive number of nodes. To make the problem-solving reasonable,
we instead take a local view and investigate each node’s ego-graph that has influence on the centered
node. Assume v as a random variable of nodes. We define node v’s L-hop neighbors as Nv (where
_L is an arbitrary integer) and the nodes in Nv form an ego-graph Gv which consists of a (local)_
node feature matrix Xv = {xu|u ∈ _Nv} and a (local) adjacency matrix Av = {auw|u, w ∈_ _Nv}._
Use Gv as a random variable of ego-graphs[3] whose realization is Gv = (Av, Xv). Besides, we
define y as a random variable of node labels. In this way, we can fragment a whole graph as a set of
instances (Gv, yv) _v_ _V where Gv denotes an input and yv is a target. Notice that the ego-graph can_
_{_ _}_ _∈_
be seen as a Markov blanket for the centered node, so the conditional distribution p(Y|G, e) can be
decomposed as a product of _V_ independent and identical marginal distributions p(y **Gv, e).**
_|_ _|_ _|_

Therefore, the data generation of (Gv, yv) _v_ _V from a distribution p(G, Y_ **e) 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 a set of ego-graphs _Gv_ _v_ _V ; 2) each node’s label is generated via y_ _p(y_ **Gv =**
_{_ _}_ _∈_ _∼_ _|_
_Gv, e). Then the OOD node-level prediction problem can be formulated as: given training data_
_{Gv, yv}v∈V from p(G, Y|e = e), the model needs to handle testing data {Gv, yv}v∈V ′ from a new_
distribution p(G, Y|e = e[′]). Denote E as the support of environments, f as a predictor model with
_yˆ = f_ (Gv) and l( _,_ ) as a loss function. More formally, the OOD problem can be written as:

_·_ _·_


min max
_f_ _e∈E_ [E][G][∼][p][(][G][|][e][=][e][)]


Ey _p(y_ **Gv=Gv,e=e)[l(f** (Gv), y)]
_∼_ _|_
_vX∈V_


(2)


_|V |_


We remark that the first-step sampling G ∼ _p(G|e = e) can be ignored since in most cases one only_
has a single input graph in the context of node-level prediction tasks.

2Our formulation and method can be trivially extended to cover edge features which we omit here for brevity.
3We use a subscript v here to remind that it is an ego-graph from the view of a target node.


-----

2.2 INVARIANT FEATURES FOR NODE-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 (Rojas-Carulla et al., 2018; Arjovsky et al., 2019) propose to learn invariant predictor models
which resorts to an assumption for data-generating 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 Gv with target label yv. It seems not straightforward for how to define invariant features
_on graphs given two observations: 1) the ego-graph possesses a hierarchical structure for associated_
nodes (i.e., Gv induces a BFS tree rooted at v where the l-th layer contains the l-order neighbored
nodes Nv[(][l][)][) and 2) the nodes in each layer are permutation-invariant and variable-length. Inspired]
by WL test Weisfeiler & Lehman (1968), we extend the invariance assumption (Rojas-Carulla et al.,
2018; Gong et al., 2016; Arjovsky et al., 2019) to accommodate structural information in graph data:
**Assumption 1. (Invariance Property) Assume input feature dimension as d0. There exists a sequence**
_of (non-linear) functions {h[∗]l_ _[}]l[L]=0_ _[where][ h]l[∗]_ [:][ R][d][0][ →] [R][d][ and a permutation-invariant function]
Γ : R[d][m] _→_ R[d], which gives a node-level readout rv = rv[(][L][)] _that is calculated in a recursive way:_
_ru[(][l][)]_ = Γ{rw[(][l][−][1)]|w ∈ _Nu[(1)]_ _∪{u}} for l = 1, · · ·, L and ru[(0)]_ = h[∗]l [(][x][u][)][ if][ u][ ∈] _[N][ (]v[l][)][. Denote][ r]_
_as a random variable of rv and it satisfies 1) (Invariance condition): p(y|r, e) = p(y|r), and 2)_
_(Sufficiency condition): y = c[∗](r) + n, where c[∗]_ _is a non-linear function, n is an independent noise._

A more intuitive illustration for the above computation is presented in Fig. 1(b). The node-level
readout rv aggregates the information from neighbored nodes recursively along the structures of BFS
tree given by Gv. Essentially, the above definition assumes that in each layer the neighbored nodes
contain a portion of causal features that contribute to stable prediction for y across different e. Such
a definition possesses two merits: 1) the (non-linear) transformation h[∗]l [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 Gv. Therefore, this formulation gives
rise to enough flexibility and capacity for modeling on graph data.

3 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 1 to provide some high-level intuition.

3.1 MOTIVATING EXAMPLE
We consider a linear toy example and assume 1-layer graph convolution for illustration. Namely, the
ego-graph Gv (and Nv) only contains the centered node and its 1-hop neighbors. We simplify the h[∗]
and c[∗] in Assumption 1 as identity mappings and instantiate Γ as a mean pooling function. Then we
assume 2-dim node features xv = [x[1]v[, x][2]v[]][ and]

1 1
_yv =_ _x[1]u_ [+][ n]v[1][,] _x[2]v_ [=] _yu + n[2]v_ [+][ ϵ,] (3)

_Nv_ _Nv_
_|_ _|_ _uX∈Nv_ _|_ _|_ _uX∈Nv_

where n[1]v [and][ n]v[2] [are independent standard normal noise and][ ϵ][ is a random variable with zero mean]
and non-zero variance dependent on environment e. 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 sub-area
while its citation index (a spurious feature) is affected by both the label and the environment.

Based on this, we consider a vanilla GCN as the predictor model ˆyv = _N1v_ _u_ _Nv_ _[θ][1][x]u[1]_ [+][ θ][2][x]u[2] [.]

_|_ _|_ _∈_

Then the ideal solution for the predictor model is [θ1, θ2] = [1, 0]. This indicates that the GCN

P

identifies the invariant feature, i.e., x[1]v [insensitive to environment changes. However, here we show a]
negative result when using standard empirical risk minimization.
**Proposition 1. Let the risk under environment e be R(e) =** _|V1 |_ _v∈V_ [E][y][|][G]v[=][G]v [[][∥]y[ˆ]v − _yv∥2[2][]][. The]_

_e_ 1
_unique optimal solution for objective minθ Ee[R(e)] would be [θ1P, θ2] = [_ 2+[1+]σ[σ]e[2][2] _[,]_ 2+σe[2] []][ where][ σ][e][ >][ 0]

_denotes the standard deviation of ϵ across environments._


-----

This indicates that directly minimizing the expectation of risks across environments would inevitably
lead the model to rely on spurious correlation (x[2]v [depends on environments). Also, such a reliance]
would be strengthened with smaller σe, i.e., 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 as a sufficient condition for the ideal solution.
**Proposition 2. The objective minθ Ve[R(e)] reaches the optimum if and only if [θ1, θ2] = [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-EXTRAPOLATE RISK MINIMIZATION
We now return to the general case where we have (Gv, yv) for training and leverage a GNN model
_{_ _}_
as the predictor: ˆyv = fθ(Gv). The intuition in Section 3.1 implies a new learning objective:

min Ve[L(G[e], Y _[e]; θ)] + βEe[L(G[e], Y_ _[e]; θ)],_ (4)
_θ_

where L(G[e], Y _[e]; θ) =_ _V1e_ _v_ _Ve_ _[l][(][f][θ][(][G]v[e][)][, y]v[e][)][ and][ β][ is a trading hyper-parameter. If we have]_

_|_ _|_ _∈_

training graphs from a sufficient number of environments _tr =_ _e_ and the correspondence of each

P _E_ _{_ _}_

graph to a specific e, i.e., {G[e], Y _[e]}e∈Etr which induces {{G[e]v[, y]v[e][}][v][∈][V]e_ [:][ e][ ∈E][tr][}][, we can use the]
empirical estimation with risks from different environments to handle Eq. 4 in practice, as 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 a 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 gwk (G) (k = 1, _, K) that aim to_
_· · ·_
generate K-fold graph data {G[k]}k[K]=1 [(which induces][ {{][G]v[k][}][v][∈][V] [: 1][ ≤] _[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( _L(gwk[∗]_ [(][G][)][, Y][ ;][ θ][) : 1][ ≤] _[k][ ≤]_ _[K][}][) +][ β]_ _L(gwk[∗]_ [(][G][)][, Y][ ;][ θ][)][,]
_θ_ _{_ _K_

_k=1_ (5)

X

s. t. [w1[∗][,][ · · ·][, w]K[∗] [] = arg] max
_w1,···,wK_ [Var][(][{][L][(][g][w][k] [(][G][)][, Y][ ;][ θ][) : 1][ ≤] _[k][ ≤]_ _[K][}][)][,]_


where L(gwk (G), Y ; θ) = L(G[k], Y ; θ) = _V1_ _v_ _V_ _[l][(][f][θ][(][G]v[k][)][, y][v][)][.]_

_|_ _|_ _∈_

One remaining problem is how to specifybustness on graphs (Xu et al., 2019; Jin et al. gwPk (,G 2020). Following recent advances in adversarial ro-), we consider editing graph structures by
adding/deleting edges. Assume a Boolean matrix B[k] = {0, 1}[N] _[×][N]_ (k = 1, · · ·, K) and denote the
supplement graph of A as A = 11[⊤] _−_ _I −_ _A, where I is an identity matrix. Then the modified graph_
for view k is A[k] = A + B[k] _◦_ (A − _A) where ◦_ denotes element-wise product. The optimization for
_B[k]_ is difficult due to its non-differentiability and one also needs to constrain the modification within
a threshold. To handle this, we use policy gradient method REINFORCE, treating graph generation
as a decision process and edge editing as actions (see details in Appendix A). We call our approach in
Eq. 5 Explore-to-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.1. To begin with, we introduce some building blocks.
The GNN model f can be decomposed into an encoder h for representation and a classifier c for
prediction, i.e., f = c ◦ _h and we have zv = h(Gv), ˆyv = c(zv). Besides, we assume I(x; y)_
stands for the mutual information between x and y and I(x; y|z) denotes the conditional mutual
information given z. To keep notations simple, we define pe( ) = p( **e = e) and Ie(** ) = I( **e = e).**

_·_ _·|_ _·_ _·|_
Another tricky point is that in computation of the KL divergence and mutual information, we require


-----

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 f1, f2 associated
with ego-graphs Gv and node labels y, we define computation for KL divergence as


[#]


log _[f][1][(][G][v][ =][ G][v][,][ y][ =][ y][v][)]_

_f2(Gv = Gv, y = yv)_


_DKL(f1(Gv, y)_ _f2(Gv, y)) := EG_ _p(G)_
_∥_ _∼_


Eyv _p(y_ **Gv** =Gv )
_∼_ _|_
_vX∈V_


_|V |_


(6)


4.1 RELATIONSHIP BETWEEN INVARIANCE PRINCIPLE AND OOD PROBLEM

We will show that the objective Eq. 4 can guarantee a valid solution for OOD problem Eq. 2. To this
end, we rely on another assumption for data-generating distribution.

**Assumption 2. (Environment Heterogeneity): For (Gv, r) that satisfies Assumption 1, there exists**
_a random variable r such that Gv = m(r, r) where m is a functional mapping.We assume that_
_p(y|r, e = e) would arbitrarily change across environments e ∈E._

Assumptions 1 and 2 essentially distill two portions of features in input data: one is domain-invariant
for prediction and the other contributes to sensitive prediction that depends on environments. The
GNN model f = c _h induces two model distributions q(z_ **Gv) (by the encoder) and q(y** **z) (by the**
_◦_ _|_ _|_
classifier). Based on this, we can dissect the effects of Eq. 4 which indeed forces the representation z
to satisfy the invariance and sufficiency conditions illustrated in Assumption 1.

**Theorem 1. If q(y|z) is treated as a variational distribution, then 1) minimizing the expectation**
_term in Eq. 4 contributes to maxq(z_ **Gv) I(y; z), i.e., enforcing the sufficiency condition on z for**
_|_
_prediction, and 2) minimizing the variance term in Eq. 4 would play a role for minq(z_ **Gv) I(y; e** **z),**
_|_ _|_
_i.e., enforcing the invariance condition p(y|z, e) = p(y|z)._

Based on these results, we can bridge the gap between the invariance principle and OOD problem.

**Theorem 2. Under Assumption 1 and 2, if the GNN encoder q(z|Gv) satisfies that 1) I(y; e|z) = 0**
_(invariance condition) and 2) I(y; z) is maximized (sufficiency condition), then the model f_ _[∗]_ _given_
_by Ey[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 a 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|e = e[′]). Following similar
spirits of Federici et al. (2021), the training error and OOD generalization error can be respectively
measured by DKL(pe(y **Gv)** _q(y_ **Gv)) and DKL(pe′** (y **Gv)** _q(y_ **Gv)) which can be calculated**
_|_ _∥_ _|_ _|_ _∥_ _|_
based on our definition in Eq. 6. Based on Theorem 1, we can arrive at the following theorem which
reveals the effect of Eq. 4 that contributes to tightening the bound for the OOD error.

**Theorem 3.** _Optimizing Eq. 4 with training data can minimize the upper bound for_
_DKL(pe′_ (y **Gv)** _q(y_ **Gv) on condition that Ie′** (Gv; y **z) = Ie(Gv; y** **z).**
_|_ _∥_ _|_ _|_ _|_

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 out-of-distribution
data and indeed enhance GNN model’s power for in-the-wild extrapolation.

5 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 1 summarizes the information
of experimental datasets and evaluation protocols, and we provide more dataset information in
Appendix E. We compare our approach EERM with standard empirical risk minimization (ERM).
Implementation details are presented in Appendix F. In the following subsections, we will investigate
three scenarios that require the model to handle distribution shifts stemming from different causes.


-----

Table 1: Summary of the experimental datasets that entail diverse distribution shifts ("Artificial
Transformation" means that we add synthetic spurious features, "Cross-Domain 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-Level"
means splitting by graphs and "Time-Aware" means splitting by time) and the evaluation metrics. In
Appendix E we provide more detailed information and discussions on the evaluation protocols.

Dataset Distribution Shift #Nodes #Edges #Classes Train/Val/Test Split Metric Adapted From

Cora 2,703 5,278 10 Domain-Level Accuracy Yang et al. (2016)

Artificial Transformation
Amazon-Photo 7,650 119,081 10 Domain-Level Accuracy Shchur et al. (2018)

Twitch-explicit 1,912 - 9,498 31,299 - 153,138 2 Domain-Level ROC-AUC Rozemberczki et al. (2021)

Cross-Domain Transfers
Facebook-100 769 - 41,536 16,656 - 1,590,655 2 Domain-Level Accuracy Traud et al. (2011)

Elliptic 203,769 234,355 2 Time-Aware F1 Score Pareja et al. (2020)[1]

Temporal Evolution
OGB-Arxiv 169,343 1,166,243 40 Time-Aware Accuracy Hu et al. (2020)

[1 The original dataset is provided at https://www.kaggle.com/ellipticco/elliptic-data-set.](https://www.kaggle.com/ellipticco/elliptic-data-set)

Figure 2: Results on Cora with artificial distribution shifts. We run each experiment with 20 trials.

|ER We|w/ spuri w/o spu M run|ous riou (b) e|s EE ach|RM exp|
|---|---|---|---|---|


100

80

80 70

Accuracy60 ERM Accuracy 60 w/ spurious Accuracy ERM

EERM w/o spurious 60 EERM

40 40

T1 T2 T3 T4 T5 T6 T7 T8 ERM EERM GCN SGC GAT

(a) (b) (c)

(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.

Figure 3: Experiment results on Amazon-Photo with artificial distribution shifts.

95

90 90

90

Accuracy85 ERM Accuracy85 w/ spurious Accuracy80 ERM

EERM w/o spurious EERM

80 80 70

T1 T2 T3 T4 T5 T6 T7 T8 ERM EERM GCN GAT SGC

(a) (b) (c)


5.1 HANDLING DISTRIBUTION SHIFTS WITH ARTIFICIAL TRANSFORMATION

We first consider artificial distribution shifts based on two public node classification benchmarks
Cora and Amazon-Photo. For each dataset, we adopt two randomly initialized GNNs to 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.1 for details). We generate 10-fold
graph data with distinct environment id’s and use 1/1/8 of them for training/validation/testing.

|G en g hig sp n.|E E CN t an he uri|RM ERM S ( with d u st ous|GC c) 2 sin val o|0 g i n|G tr E da es|AT ial R tio f|M o|
|---|---|---|---|---|---|---|---|
|GC on N ti iz fe e g|ER EE N s on ed atu en|M RM G (c hift be GN res era|AT SG ) s. nchm Ns t based te 10-|||C ark o 1 o fol||


We use a 2-layer vanilla GCN (Kipf & Welling, 2017) as the GNN model. We report results on
8 testing graphs (T1∼ 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

|E ith L T pub two 2) ix E em he and tha the, the r c at i|w/ spurious w/o spuriou RM (b) artifi RAN lic no rand gener .1 fo for tr GNN 3(a) t our effec perf ompa n Co|s EE cial SFO de om ate r de aini mo, re ap tive orm red ra t|RM dist RM clas ly i spur tails ng/v del. spec proa nes anc wit he (|
|---|---|---|---|

adjacent nodes are indeed informative for prediction while in Photo 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, it 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 input 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 on 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 our approach achieves consistently superior performance in different cases.


-----

60


65


65


ERM
EERM


ERM
EERM


ERM
EERM




70

60

50


(a) GraphSAGE


(b) GPRGNN

|55 U|Col2|Col3|Col4|Col5|Col6|Col7|Col8|Col9|Col10|Col11|Col12|EERM|M 60 U|Col15|Col16|Col17|Col18|Col19|Col20|Col21|Col22|Col23|Col24|Col25|E|Col27|Col28|EERM|U|Col31|Col32|Col33|Col34|Col35|Col36|Col37|Col38|Col39|Col40|E|Col42|Col43|EERM|Col45|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|55 ROC-AU 50 Fi le 2: Tr John Bin Wa|||||||||||||60 ROC-AU 55 50 on T 00 wh||||||||||||||||60 ROC-AU 55 re dif t con|||||||||||||||aphs 75 88 2 with on.|
||||||||||||||||||||||||||||||||||||||||||||||
||||E gu Te|S re st|F 4: ac|R T cu|PT (a) est ra|BR GCN R cy|R OC on|U - F|T AU B-|W C 1||||w e|ES it re|F ch we||R w c|PT (b) G her om|BR AT e pa|r|R we e|U c di|o f|T m fe|W pa ren|||E fe fi|S re gur|F nt ati|R G o|( N n|PT c) G N s|BR CN b of|II a t|R ck ra|U b in|o i|T ne ng|W s. gr||
||||aini|ng|grap|h co|mb|inat|ion|||||||Pe|nn||||||||||B|row|n||||||||T|e|xas||||||
||||||||||||||ERM|||||EER||M||||E|RM||||EER||M||||E|RM|||||E|ER|M||
||||Hop gha shU|kins m +|+ + D Bran|Calt uke dei|ech + P s+ C|+ A rinc arn|mhe eton egie|rst|5 5 5|0.4 0.1 0.8|8 ± 1.09 7 ± 0.65 3 ± 0.17||||50 50 51|.64 .67 .52||± 0 ± 0 ± 0|.25 .79 .87|5 5 5|4 0 4|.53 .43 .61|± ± ±|3 4 4|.93 .58 .75||56.73 ± 52.76 ± 55.15 ±||0. 3. 3.|23 40 22|5 5 5|3.2 0.1 6.2|3 9 5|± ± ±|4.4 5.8 0.1|9 1 3||55 53 56.|.5 .8 1|7 ± 2 ± 2 ±|0. 4. 0.4||
||||||||||||||||||||||||||||||||u im|rac e|y int|on er|v|O al|GB s|f|-A or|r ev|x a|i lu|v ati||
|||||||||ERM EERM|||||||||||ERM EERM||||||||||||||||||||||||||
||||||||||||||||||||||||||||||||014|-20|16|||201|6-||18|||20|18-||


Figure 5: Test F1 score on Elliptic where we
group graph snapshots into 9 test sets (T1∼ T9).

5.2 GENERALIZING TO UNSEEN DOMAINS


EEERMRM- SAGE- SAGE 41.5542.09 ± ± 0.68 1.39 39.9240.36 ± ± 2.53 1.29 36.7238.95 ± ± 2.47 1.57

EEERMRM- GPR- GPR 47.2549.88 ± ± 0.55 0.49 45.0748.59 ± ± 0.57 0.52 41.5344.88 ± ± 0.56 0.62


We proceed to consider another scenario where there are multiple observed graphs in one dataset and
a model trained with one graph or a 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-Explicit and Facebook-100 collected by Lim et al. (2021).

**Training with a Single Graph. In Twitch, we 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
et al. (2021) and use test ROC-AUC for evaluation. We specify the GNN model as GCN, GAT and a
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 set as 2 for GCN and GAT and 10 for
GCNII. 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, 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, as shown in Table 2. We can see that EERM outperforms ERM on 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
are also two sub-cases that correspond to distinct real-world scenarios, as discussed below.

**Handling Dynamic Graph Snapshots. We adopt a dynamic financial network dataset Elliptic**
(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/test. 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. 5
where we group the test graph snapshots into 9 folds in chronological order. Our approach yields
much higher F1 scores than ERM in most cases with averagely 9.6%/10.0% improvements using
GraphSAGE/GPR-GNN as 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


-----

distributions that leads to 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-2016/2016-2018/2018-2020 for testing. Also different from the original (transductive) 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 of improving GNN model’s learning for extrapolating to future data.

6 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.

**Generalization/Extrapolation 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 indistribution 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/structures (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 to 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**
are 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 a
graph as an instance for prediction and tacitly assume that all the graph instances are sampled in an
i.i.d. 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 in 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 a 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.

7 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 a 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.


-----

8 ACKNOWLEDGEMENT

This work was in part supported by National Key Research and Development Program
of China (2020AAA0107600), Shanghai Municipal Science and Technology Major Project
(2021SHZDZX0102).

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.02893, 2019._

Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semisupervised 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. Fairness in criminal justice risk assessments:
The state of the art. In Sociological Methods & Research, 2018.

Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invariant graph representations for
graph classification extrapolations. In International Conference on Machine Learning (ICML), pp.
837–851, 2021.

Gilles Blanchard, Gyemin Lee, and Clayton Scott. Generalizing from several related classification
tasks to a new unlabeled sample. In Advances in Neural Information Processing Systems (NeurIPS),
pp. 2178–2186, 2011.

Peter Bühlmann. Invariance, causality and robustness. CoRR, abs/1812.08233, 2018.

Shiyu Chang, Yang Zhang, Mo Yu, and Tommi S. Jaakkola. Invariant rationalization. In International
_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 J. 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. In International Conference on Learning Representations (ICLR), 2021.

Elliot Creager, Jörn-Henrik Jacobsen, and Richard S. Zemel. Environment inference for invariant
learning. In International Conference on Machine Learning (ICML), pp. 2189–2200, 2021.


-----

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 S.-I Lee. Ai for radiographic covid-19 detection selects shortcuts
over signal. Nature Machine Intelligence, 2021.

Shobeir Fakhraei, 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-theoretic approach to distribution
shifts. CoRR, abs/2106.03783, 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. In International Conference on
_Machine Learning (ICML), pp. 2839–2848, 2016._

William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on 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. 4094–4104, 2020.

Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta,
and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. 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 an out-of-distribution
generalization problem ? CoRR, abs/2008.01883, 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 nonhomophilous 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 on Learning Theory (COLT), 2009.


-----

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. Evolvegcn: 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. In Journal of the Royal Statistical Society. Series B
_(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 Rozemberczki, 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/1911.08731, 2019._

Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapnik-chervonenkis dimension
of graph and recursive neural networks. Neural Networks, 108:248–259, 2018.

Bernhard Schölkopf, Dominik 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, abs/1811.05868, 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–841, 2019.

Amanda L. Traud, Peter J. Mucha, and Mason A. Porter. Social structure of facebook networks.
_CoRR, abs/1102.2166, 2011._

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 of 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 of a graph to a canonical form and an algebra arising
during this reduction. Nauchno-Technicheskaya 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), 2021a.

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 on Machine Learning (ICML), 2021b._


-----

Chuanlong Xie, Fei Chen, Yue Liu, and Zhenguo Li. Risk variance penalization: From distributional
robustness to causality. CoRR, abs/2006.07544, 2020.

Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin. Topology 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 to graph neural networks. In International
_Conference on Learning Representations (ICLR), 2021._

Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised 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 in graph neural networks. In International Conference on Machine Learning
_(ICML), pp. 11975–11986, 2021._

Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Üstebay. Bayesian graph convolutional
neural networks for semi-supervised classification. In AAAI Conference on Artificial Intelligence
_(AAAI), pp. 5829–5836, 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 on 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.


-----

A OPTIMIZATION AND ALGORITHM

We illustrate the details of using policy gradient for optimizing the graph editers in Eq. 5. Concretely,
for viewediting the edge between it and the k, we consider a parameterized matrix m-th node would be Pk = {π pnm[k](a[}][k]nm[. For the][) =] _[ n]exp([-th node, the probability for]πnm[k]_ [)]

_m[′][ exp(][π]nm[k]_ _[′]_ [)] [. We then sample]

_s actions {b[k]nmt_ _[}]t[s]=1_ [from a multinomial distribution][ M][(][p][(][a]n[k]1[)][,][ · · ·]P[, p][(][a]nn[k] [))][, which give the non-]
zero entries in the n-th row of B[k]. The reward function R(G[k]) can be defined as the inverse loss. We
can use REINFORCE algorithm to optimize the generator with the gradient ∇wk log pwk (A[k])R(G[k])
where wk = Pk and pwk (A[k]) = ΠnΠ[s]t=1[p][(][b]nm[k] _t_ [)][. We present the training algorithm in Alg.][ 1][.]


**Algorithm 1: Stable Learning for OOD Generalization in Node-Level Prediction on Graphs.**

**1 INPUT: training graph data G = (A, X) and Y, initialized parameters of GNN θ, initialized**
parameters of graph editers w = _wk_, learning rates αg, αf .
_{_ _}_

**2 while not converged or maximum epochs not reached do**

**3** **for t = 1, · · ·, T do**

**4** Obtain modified graphs G[k] = (A[k], X) from graph editer gwk, k = 1, _, K;_
_· · ·_

**5** Compute loss J1(w) = Var( _L(G[k], Y ; θ) : 1_ _k_ _K_ ) ;
_{_ _≤_ _≤_ _}_

**76** **ifUpdate t == w Tk then ←** _wk + αg∇wk log pwk_ (A[k])J1(w), k = 1, · · ·, K ;

**8** Compute loss J2(θ) = Var({L(G[k], Y ; θ) : 1 ≤ _k ≤_ _K}) +_ _K[β]_ _Kk=1_ _[L][(][G][k][, Y][ ;][ θ][)][ ;]_

**9** Update θ _θ_ _αf_ _θJ2(θ) ;_
_←_ _−_ _∇_ P


**10 OUTPUT: trained parameters of GNN θ[∗].**

B FURTHER RELATED WORKS

B.1 OUT-OF-DISTRIBUTION GENERALIZATION AND INVARIANT MODELS

Out-of-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, it is
natural to learn invariant features under the setting of the causal factorization of physical mechanisms
(Schölkopf et al., 2012; Peters et al., 2016). A 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-based algorithm that resorts to
shared representations of cross-domain inputs from the same object. Also, Creager et 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 to estimate
the environments as a latent variable.

Krueger et 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 to a 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 a bilevel framework in Eq. 5. Compared to
existing works, the differences of 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, on 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, as mentioned before, lies in the


-----

inter-connection of data points in one 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 on the input graph and node features. To improve the generalization power, a
common practice is to enforce a certain regularization for the learned graph structures. For example,
Jin et al. (2020) proposes to 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 et 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 to 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 et al., 2021) or adaptively
sparsifying the structures (Zheng et al., 2020; Hasanzadeh et al., 2020). In this paper, we focus on
out-of-distribution generalization and target handling distribution shifts over graphs, which is more
difficult than the setting of previous methods that concentrate on 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
generation/editing/attacking frameworks as mentioned above, which we leave as 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
node class corresponding to a component, based on which the authors show some cases where linear
separability can be achieved. (Ma et al., 2021) focuses on subgroup generalization and presents a PACBayesian 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 a 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 on graphs. Third, we 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.1

C.1 PROOF FOR PROPOSITION 1

We define the aggregated node feature av = _N1v_ _u_ _Nv_ _[x][u][. According to the definition and setup]_

_|_ _|_ _∈_
in Section 3.1, we derive the risk under a specific environment R(e):
P


_vX∈V_ Ey|Gv=Gv ∥yˆv − _yv∥2[2]_

_vvXX∈∈VV_ EEnn11,,nn22 [][]∥∥θ(θ11a +[1]v [+] θ[ θ]2 −[2][a]v[2]1)[−]a[1]v[y][v][+][∥][ θ]2[2][2][(][n]v[1] [+][ n]v[2] [+][ ϵ][)][ −] _[n]v[1][∥][2]2_


_|V |_

= [1]

_|V |_

= [1]

_|V |_


(7)


-----

Denote the objective for empirical risk minimization as L1 = Ee[R(e)] and we have its first-order
derivative w.r.t. θ1 as

_∂L1_ 1

= Ee En1,n2 2[(θ1 + θ2 1)a[1]v [+][ θ][2][(][n]v[1] [+][ n]v[2] [+][ ϵ][)][ −] _[n]v[1][]][ ·][ a][1]v_
_∂θ1_ " _|V1 |_ _vX∈V_ [] _−_ # (8)

= Ee " _|V |_ _vX∈V_ En1,n2 2[(θ1 + θ2 − 1) · a[1]v _[·][ a]v[1]#_ _,_

where the second step is given by independence among[] _a[1]v[,][ n][1]v[,][ n][2]v_ [and][ ϵ][. Let][ ∂L]∂θ1[1] [= 0][, and we will]

obtain θ1 + θ2 = 1.

Also, the first-order derivative w.r.t. θ2 is


_∂L1_ 1

= Ee En1,n2 2[(θ1 + θ2 1)a[1]v [+][ θ][2][(][n]v[1] [+][ n]v[2] [+][ ϵ][)][ −] _[n]v[1][]][ ·][ (][a][1]v_ [+][ n]v[1] [+][ n]v[2] [+][ ϵ][)]
_∂θ2_ " _|V1 |_ _vX∈V_ [] _−_ #

= Ee En1,n2 2[(θ1 + θ2 1) _a[1]v_ _v_ [+][ θ][2][(][n]v[1] _v_ [+][ n]v[2] _v_ [+][ ϵ][ ·][ ϵ][)][ −] _[n]v[1]_ _v_

" _|V1 |_ _vX∈V_ [] _−_ _·_ _[·][ a][1]_ _[·][ n][1]_ _[·][ n][2]_ _[·][ n][1]#_

= Ee En1,n2 2[(θ1 + θ2 1) _a[1]v_ _v_ [+][ θ][2][(1 + 1 +][ σ]e[2][)][ −] [1] _,_

" _|V |_ _vX∈V_ _−_ _·_ _[·][ a][1]_ #

(9)

[]

where the last step is according to Ex[x[2]] = E[2]x[[][x][] +][ V][x][[][x][]][. We further let][ ∂L]∂θ2[1] [= 0][, and will get the]

unique solution

_θ1 = [1 +][ σ]e[2]_ _,_ _θ2 =_ 1 _._ (10)

2 + σe[2] 2 + σe[2]

C.2 PROOF FOR PROPOSITION 2

We derive the first-order derivation ofLet L2 = Ve[R(e)] = Ee[R[2](e)] − E L[2]e[[][R]2 w.r.t.[(][e][)]][ and] θ1 and[ l][(][e][) = (] θ2. Firstly,[θ][1] [+][ θ][2] _[−]_ [1)][a]v[1] [+][ θ][2][(][n]v[1] [+][ n]v[2] [+][ ϵ][)][ −] _[n]v[1][.]_


_∂L2_ 1 1

_∂θ1_ = E∂Le "2 _|V |_ _vX∈V_ E1n1,n2 []4l[3](e)a[1]v# + E[2]e " _|V |_ _vX∈V_ En1,n2 []2l(e)a[1]v

= Ee En1,n2 4l[3](e) (a[1]v [+][ n]v[1] [+][ n]v[2] [+][ ϵ][)]
_∂θ2_ " _|V1 |_ _vX∈V_ [] _·_ #

+ E[2]e En1,n2 2l(e) (a[1]v [+][ n]v[1] [+][ n]v[2] [+][ ϵ][)] _._

" _|V |_ _vX∈V_ _·_ #

By letting _[∂L]∂θ1[2]_ [= 0][, we obtain the equation][ θ][1][ +][][ θ][2][ = 1][. Plugging it into][ ∂L]∂θ2[2] [we have]


(11)

(12)

(13)


_∂L2_ 1

= Ee En1,n2 4(θ2(n[1]v [+][ n]v[2] [+][ ϵ][)][ −] _[n]v[1][)][3][ ·][ (][a][1]v_ [+][ n]v[1] [+][ n]v[2] [+][ ϵ][)]
_∂θ2_ " _|V1 |_ _vX∈V_ [] # (13)

+ E[2]e En1,n2 2(θ2(n[1]v [+][ n]v[2] [+][ ϵ][)][ −] _[n]v[1][)][ ·][ (][a][1]v_ [+][ n]v[1] [+][ n]v[2] [+][ ϵ][)] _,_

_V_

" _|_ _|_ _vX∈V_ #

which is a function of e unless [θ1, θ2] = [1[] _, 0] that gives rise to_ _[∂L]∂θ2[2]_ [= 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.


-----

**Lemma 1. The two conditions in Assumption 1 can be equivalently expressed as 1) (Invariance):**
_I(y; e|r) = 0 and 2) (Sufficiency): I(y; r) is maximized._

_Proof. For the invariance, we can easily arrive at the equivalence given the fact_

_I(y; e_ **r) = DKL(p(y** **e, r)** _p(y_ **r)).** (14)
_|_ _|_ _∥_ _|_

For the sufficiency, we first prove that for (Gv, r, y) satisfying that y = c[∗](r) + n would also satisfy
that r = arg maxr I(y; r). We prove it by contradiction. Suppose that r ̸= arg maxr I(y; r) and
**r[′]** = arg maxr I(y; r) where r[′] ≠ _r. Then there exists a random variable r such that r[′]_ = m(r, r)
where m is a mapping function. We thus have I(y; r[′]) = I(y; r, r) = I(c[∗](r); r, r) = I(c[∗](r); r) =
_I(y; r) which leads to contradiction._

We next prove that for (Gv, r, y) satisfying that r = arg maxr I(y; r) would also satisfy that
**y = c[∗](r) + n. Suppose that y ̸= c[∗](r) + n and y = c[∗](r[′]) + n where r[′]** ≠ **r. We then have**
the relationship I(c[∗](r[′]); r) ≤ _I(c[∗](r[′]); r[′]) which yields that r[′]_ = arg maxr I(y; r) and leads to
contradiction.

Given the dependency relationship z **Gv** **y, we have the fact that maxq(z** **Gv) I(y, z) is**
_←_ _→_ _|_
equivalent to minq(z **Gv) I(y, Gv** **z). Also, we have (treating q(y** **z) as a variational distribution)**
_|_ _|_ _|_

_I(y, Gv_ **z) = DKL(p(y** **Gv, e)** _p(y_ **z, e))**
_|_ _|_ _∥_ _|_
= DKL(p(y **Gv, e)** _q(y_ **z))** _DKL(p(y_ **z, e)** _q(y_ **z))** (15)
_|_ _∥_ _|_ _−_ _|_ _∥_ _|_
_DKL(p(y_ **Gv, e)** _q(y_ **z)).**
_≤_ _|_ _∥_ _|_

Based on this, we have the inequality

_I(y, Gv_ **z)** min (16)
_|_ _≤_ _q(y_ **z)** _[D][KL][(][p][(][y][|][G][v][,][ e][)][∥][q][(][y][|][z][))][.]_
_|_

Also, we have (according to our definition in Eq. 6)

_DKL(p(y_ **Gv, e)** _q(y_ **z))**
_|_ _∥_ _|_

1

=EeEG _pe(G)_ Eyv _pe(y_ **Gv=Gv)Ezv** _q(z_ **Gv=Gv)** log _[p][e][(][y][ =][ y][v][|][G][v][ =][ G][v][)]_
_∼_ " _V_ _vX∈V_ _∼_ _|_ _∼_ _|_  _q(y = yv|z = zv)_ [#] (17)

1 _pe(y = yv_ **Gv = Gv)**

EeEG _pe(G)_ Eyv _pe(y_ **Gv=Gv)** log _|_ _,_
_≤_ _∼_ " _V_ _vX∈V_ _∼_ _|_  Ezv∼q(z|Gv=Gv)[q(y = yv|z = zv)] [#]

where the second step is according to Jensen Inequality and the equality holds if
_q(z_ **Gv) is a delta distribution (induced by the GNN encoder h).** Then the problem
_|_
minq(z **Gv),q(y** **z) DKL(p(y** **Gv, e)** _q(y_ **z)) can be equivalently converted into**
_|_ _|_ _|_ _∥_ _|_

1

min Ee _l(f_ (G[e]v[)][, y]v[e][)] = min Ee[L(G[e], Y _[e]; f_ )]. (18)
_f_ " _|Ve|_ _vX∈Ve_ # _f_

We thus have proven that minimizing the expectation term in Eq. 4 is to minimize the upper bound of
_I(y, Gv_ **z) and contributes to maxq(z** **Gv) I(y, z).**
_|_ _|_

Second, we have
_I(y; e|z)_
=DKL(p(y **z, e)** _p(y_ **z))**
_|_ _∥_ _|_
=DKL(p(y|z, e)∥Ee[p(y|z, e)]) (19)
=DKL(q(y|z)∥Ee[q(y|z)]) − _DKL(q(y|z)∥p(y|z, e)) −_ _DKL(Ee[p(y|z, e)]∥Ee[q(y|z)])_
_≤DKL(q(y|z)∥Ee[q(y|z)])._

Besides, we have (according to the definition in Eq. 6)

_DKL(q(y|z)∥Ee[q(y|z)])_

1 _q(y = yv_ **z = zv)**

=EeEG _pe(G)_ Eyv _pe(y_ **Gv=Gv)Ezv** _q(z_ **Gv=Gv)** log _|_ _._ [(20)]
_∼_ " _|V |_ _vX∈V_ _∼_ _|_ _∼_ _|_  Ee[q(y = yv|z = zv)] [#]


_DKL(p(y_ **Gv, e)** _q(y_ **z))**
_|_ _∥_ _|_


min Ee


-----

Using Jensen Inequality, we will obtain that DKL(q(y|z)∥Ee[q(y|z)]) is upper bounded by

Ee[|L(G[e], Y _[e]; f_ ) − Ee[L(G[e], Y _[e]; f_ )]|] = Ve[L(G[e], Y _[e]; f_ )]. (21)

Hence we have proven that minimizing the variance term in Eq. 4 plays a role for solving
minq(z **Gv) I(y; e** **z).**
_|_ _|_

D.2 PROOFS FOR THEOREM 2

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) = p(y|z, e) if and only if I(y; e|z) = 0 and 2) the representation
**z satisfies the sufficiency condition, i.e., y = c[∗](z) + n if and only if z = arg maxz I(y; z).**

We denote the GNN encoder that satisfies the invariance and sufficiency conditions as h[∗] and the
corresponding predictor model f _[∗](Gv) = Ey[y|h[∗](Gv)] with f_ _[∗]_ = c[∗] _◦_ _h[∗]. Since we assume the_
GNN encoder q(z **Gv) satisfies the conditions in Assumption 1, then according to Assumption 2,**
_|_
we know that there exists random variable z such that Gv = 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(y, z, z), we can construct environment e[′]_ with the distribution pe[′] (y, z, z) that satisfies

_pe′_ (y, z, z) = pe(y, z)pe′ (z). (22)

Then we follow the reasoning line of Theorem 2.1 in Liu et al. (2021) to finish the proof by showing
that for arbitrary function f = c ◦ _h and environment e, there exists an environment e[′]_ such that


EG∼pe′ (G)

EG _pe(G)_
_≥_ _∼_


1

_V_ Eyv∼pe′ (y|Gv=Gv)[l(f (Gv), yv)]
_|_ _|_ _vX∈V_

1

_V_ Ey∼pe(y|Gv=Gv)[l(f _[∗](Gv), yv)]_
_|_ _|_ _vX∈V_ #


(23)


Concretely we have


EG∼pe′ (G)

=EG′∼pe′ (G)

_≥EG′∼pe′_ (G)

=EG′∼pe′ (G)

=EG _pe(G)_
_∼_

=EG _pe(G)_
_∼_


E(yv,zv,zv)∼pe′ (y,z,z|Gv=Gv)[l(c(zv, zv), yv)]
_vX∈V_


_|V |_


E(yv,zv)∼pe(y,z|Gv=Gv)[l(c(zv, zv′ ), yv)]
_vX∈V_ ##

E(yv,zv)∼pe(y,z|Gv=Gv)[l(c[∗](zv, zv′ ), yv)]
_vX∈V_ ##

E(yv,zv) _pe(y,z_ **Gv=Gv)[l(c[∗](zv), yv)]**
_∼_ _|_
_vX∈V_ ##


Ezv′ _∼pe′_ (z|Gv=Gv′ )EG∼pe(G)
_vX[′]∈V_ _[′]_

Ezv′ _∼pe′_ (z|Gv=Gv′ )EG∼pe(G)
_vX[′]∈V_ _[′]_

Ezv′ _∼pe′_ (z|Gv=Gv′ )EG∼pe(G)
_vX[′]∈V_ _[′]_


_|V_ _[′]|_

1

_|V_ _[′]|_

1

_|V_ _[′]|_


_|V |_

1

_|V |_

1

_|V |_


1

E(yv,zv) _pe(y,z_ **Gv=Gv)[l(c[∗](zv), yv)]**

_V_ _∼_ _|_
_|_ _|_ _vX∈V_ #

1

E(yv,zv,zv) _pe(y,z,z_ **Gv=Gv)[l(c[∗](zv), yv)]**

_V_ _∼_ _|_
_|_ _|_ _vX∈V_


(24)


where the first equality is given by Eq. 22 and the second/third steps are due to the sufficiency
condition of h[∗].


-----

D.3 PROOF FOR THEOREM 3

Recall that according to our definition in Eq. 6, the KL divergence DKL(pe(y **Gv)** _q(y_ **Gv)) would**
_|_ _∥_ _|_
be

1

_DKL(pe(y_ **Gv)** _q(y_ **Gv)) := EG** _pe(G)_ Eyv _pe(y_ **Gv=Gv)** log _[p][e][(][y][ =][ y][v][|][G][v][ =][ G][v][)]_
_|_ _∥_ _|_ _∼_ " _|V |_ _vX∈V_ _∼_ _|_  _q(y = yv|Gv = Gv)_ [#]

(25)
Based on this newly defined KL divergence, we can extend the information-theoretic framework
(Federici et al., 2021) for analysis on graph data. First, we can decompose the training error (resp.
OOD error) into a representation error and a latent predictive error.


**Lemma 2. For any GNN encoder q(z|Gv) and classifier q(y|z), we have**

_DKL(pe(y_ **Gv)** _q(y_ **Gv))** _Ie(Gv; y_ **z) + DKL(pe(y** **z)** _q(y_ **z)),** (26)
_|_ _∥_ _|_ _≤_ _|_ _|_ _∥_ _|_

_DKL(pe′_ (y **Gv)** _q(y_ **Gv))** _Ie′_ (Gv; y **z) + DKL(pe′** (y **z)** _q(y_ **z)).** (27)
_|_ _∥_ _|_ _≤_ _|_ _|_ _∥_ _|_

_Proof. Firstly, we have_


_DKL(pe(y_ **Gv)** _q(y_ **Gv))**
_|_ _∥_ _|_


[#]


log _[p][e][(][y][ =][ y][v][|][G][v][ =][ G][v][)]_

_q(y = yv|Gv = Gv)_


=EG _pe(G)_
_∼_

=EG _pe(G)_
_∼_

EG _pe(G)_
_≤_ _∼_


Eyv _pe(y_ **Gv=Gv)**
_∼_ _|_
_vX∈V_

Eyv _pe(y_ **Gv=Gv)**
_∼_ _|_
_vX∈V_


_|V |_

1

_|V |_

1

_|V |_


[#]


_pe(y = yv_ **Gv = Gv)**
log _|_

Ezv _q(z_ **Gv=Gv)q(y = yv** **z = zv)**
_∼_ _|_ _|_


(28)


[#]


log _[p][e][(][y][ =][ y][v][|][G][v][ =][ G][v][)]_

_q(y = yv_ **z = zv)**
_|_


1

EG _pe(G)_ Eyv _pe(y_ **Gv=Gv)Ezv** _q(z_ **Gv=Gv)** log _[p][e][(][y][ =][ y][v][|][G][v][ =][ G][v][)]_
_≤_ _∼_ " _|V |_ _vX∈V_ _∼_ _|_ _∼_ _|_  _q(y = yv|z = zv)_ [#]

=DKL(pe(y **Gv)** _q(y_ **z)),**
_|_ _∥_ _|_

where the third step is again due to Jensen Inequality and the equality holds once q(z **Gv) is a delta**
_|_
distribution.

Besides, we have


_DKL(pe(y_ **Gv)** _q(y_ **z))**
_|_ _∥_ _|_


log _[p][e][(][y][ =][ y][v][|][G][v][ =][ G][v][)]_

_q(y = yv_ **z = zv)**
_|_ [#]


=EG _pe(G)_
_∼_

=EG _pe(G)_
_∼_


Eyv _pe(y_ **Gv=Gv)Ezv** _q(z_ **Gv=Gv)**
_∼_ _|_ _∼_ _|_
_vX∈V_


_|V |_

1

_|V |_


[#]


log _[p][e][(][y][ =][ y][v][|][G][v][ =][ G][v][)][p][e][(][y][ =][ y][v][|][z][ =][ z][v][)]_

_pe(y = yv_ **z = zv)q(y = yv** **z = zv)**
_|_ _|_


1

=EG _pe(G)_ Eyv _pe(y_ **Gv=Gv)Ezv** _q(z_ **Gv=Gv)** log _[p][e][(][y][ =][ y][v][|][G][v][ =][ G][v][)][p][e][(][y][ =][ y][v][|][z]_
_∼_ " _|V |_ _vX∈V_ _∼_ _|_ _∼_ _|_  _pe(y = yv|z = zv)q(y = yv|z =_

=I(Gv; y **z) + DKL(pe(y** **z)** _q(y_ **z)).**
_|_ _|_ _∥_ _|_
(29)


The result for DKL(pe′ (y **Gv)** _q(y_ **Gv)) can be obtained in a similar way.**
_|_ _∥_ _|_

**Lemma 3. For any q(z|Gv) and q(y|z), the following inequality holds for any z satisfying p(z =**
_z|e = e) > 0, ∀e ∈E._

2

1 1

_DJSD(pe′_ (y **z)** _q(y_ **z))** _._ (30)
_|_ _∥_ _|_ _≤_ r 2α _[I][(][y][;][ e][|][z][) +]_ r 2 _[D][KL][(][p][e][(][y][|][z][)][∥][q][(][y][|][z][)]!_


_Proof. The proof can be adapted by from the Proposition 3 in Federici et al. (2021) by replacing e in_
our case with t.


-----

Table 4: Statistic information for Twitch-Explicit datasets.

Dataset #Nodes #Edges #Density Avg Degree Max Degree

DE 9498 153138 0.0033 16 3475
ENGB 7126 35324 0.0013 4 465
ES 4648 59382 0.0054 12 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 22 1171

The results of Lemma 2 and 3 indicate that if we aim to reduce the OOD error measured by DKL(pe[′] (y **Gv)** _q(y_ **Gv), one need to control three terms:** 1) Ie(Gv; y **z), 2)**
_|_ _∥_ _|_ _|_
_DKL(pe(y_ **z)** _q(y_ **z) and 3) I(y; e** **z). The next lemma unifies minimization for the first two**
_|_ _∥_ _|_ _|_
terms.
**Lemma 4. For any q(z|Gv) and q(y|z), we have**

min min
_q(z_ **Gv),q(y** **z)** _[D][KL][(][p][e][(][y][|][G][v][)][∥][q][(][y][|][z][))][ ⇔]_ _q(z_ **Gv)** _[I][e][(][G][v][;][ y][|][z][) + min]q(y_ **z)** _[D][KL][(][p][e][(][y][|][z][)][∥][q][(][y][|][z][))][.]_
_|_ _|_ _|_ _|_

(31)

_Proof. Recall that q(y|z) is a variational distribution. We have_

_Ie(Gv; y_ **z) = DKL(pe(y** **Gv)** _pe(y_ **z)))**
_|_ _|_ _∥_ _|_
= DKL(pe(y **Gv)** _q(y_ **z))** _DKL(pe(y_ **z)** _q(y_ **z))** (32)
_|_ _∥_ _|_ _−_ _|_ _∥_ _|_
_DKL(pe(y_ **Gv)** _q(y_ **z)).**
_≤_ _|_ _∥_ _|_

Therefore, we can see that Ie(Gv; y **z) is upper bounded by DKL(pe(y** **Gv** _q(y_ **z)) and the equality**
_|_ _|_ _∥_ _|_
holds if and only if DKL(pe(y **z)** _q(y_ **z)) = 0. We thus conclude the proof.**
_|_ _∥_ _|_

Recall that according to Lemma 1 we have the fact that our objective in Eq. 4 essentially has the
similar effect as
min (33)
_q(z_ **Gv),q(y** **z)** _[D][KL][(][p][e][(][y][|][G][v][)][∥][q][(][y][|][z][)) +][ I][(][y][;][ e][|][z][)][.]_
_|_ _|_

Based on the Lemma 2, 3 and 4, we know that optimization for the objective Eq. 4 can reduce the
upper bound of OOD error given by DKL(pe′ (y **Gv)** _q(y_ **Gv) on condition that Ie′** (Gv; y **z) =**
_|_ _∥_ _|_ _|_
_Ie(Gv; y_ **z). 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.1 ARTIFICIAL DISTRIBUTION SHIFTS ON CO R A AND AM A Z O N-PH O T O

Cora and Amazon-Photo 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 1 for more statistic information. Cora is a citation network where
nodes represent papers and edges represent their citation relationship. Amazon-Photo is a copurchasing 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 ability for out-of-distribution 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 environmentsensitive features. Specifically, assume the provided node features as X1. Then we adopt a randomly


-----

initialized GNN (with input of X1 and adjacency matrix) to generate node labels Y (via taking an

75 75 75

70 70 70

65 65 65

ROC-AUC60 ROC-AUC60 ROC-AUC60

55 IID 55 IID 55 IID

OOD OOD OOD

50 (a) GCN 50 (b) GAT 50 (c) GCNII

Figure 6: Comparison of different leave-out data on Twitch-Explicit. We consider three GNN
backbones trained with ERM. The "OOD" means that we train the model on one 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 on the remaining nodes. The results clearly show that the model performance
suffers a significantly drop from the case "IID" to the case "OOD". This indicates that the graph-level
splitting for training/validation/testing splits used in Section 5.2 indeed introduces distribution shifts
and would require the model to deal with out-of-distribution data during test.

argmax in the output layer to 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 = [X1, 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 a generalized version of our motivating example
in Section 3.1 and we replace the linear aggregation as a randomly initialized graph neural network
to introduce non-linearity.

In fact, with our data generation, the original node features X1 can be seen as domain-invariant
features that are sufficiently predictive for node labels and insensitive to different environments,
while the generated features X2 are domain-variant features that are conditioned on environments.
Therefore, in principle, the ideal case for the model is to 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 on 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 CROSS-DOMAIN TRANSFERS ON MULTI-GRAPH DATA

A typical scenario for distribution shifts on 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
is 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 as distinct domains. In short,
since most of graph data records the relational structures among a specific group of entities and the
interactions/relationships among entities from different groups often have distinct characteristics, the
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 Twitch-Explicit and
Facebook-100 that satisfy this requirement.

Twitch-Explicit contains seven networks where nodes represent Twitch users and edges represent their mutual friendships. Each network is 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 we call "OOD", we train the model on the nodes of one graph DE and


-----

40000

30000

20000

10000

0

0 1 2 3 4 5 6 7 8 9 10 11 12 13

(a) Node Number

0.100

0.075

0.050

0.025

0.000

0 1 2 3 4 5 6 7 8 9 10 11 12 13

(b) Density

4000

3000

2000

1000

0

0 1 2 3 4 5 6 7 8 9 10 11 12 13

(c) Max 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, Princeton, 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 leave-out
10% data. The results in Fig. 6 show that the model performance exhibits a clear drop from "IID" to
"OOD", which indicates that there indeed exist distribution shifts among different input graphs. This
also serves as a justification for our evaluation protocol in Section 5.2 where we adopt the graph-level
splitting to construct training/validation/testing 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 our experiments: John Hopkins, Caltech, Amherst,
Bingham, Duke, Princeton, WashU, Brandeis, Carnegie, Cornell, Yale, Penn, Brown and Texas.
Recall that in Section 5.2 we use Penn, Brown and Texas for testing, Cornell 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. 7 we present a comparison
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 in 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.

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 a 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 large-scale 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-world datasets Elliptic and OGB-Arxiv for node
classification experiments.


-----

0.30

label rate

0.25 positive label rate

0.20

0.15

0.10

0.05

0.00
Tr Val T1 T2 T3 T4 T5 T6 T7 T8 T9


Figure 8: The label rates and positive label rates of training/validation/testing 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 a sequence of 49 graph snapshots. Each graph snapshot is a network of
Bitcoin transactions where each node represents one transaction and each edge indicates a payment
flow. Approximately 20% of the transactions are marked with licit or illicit ones and the goal is
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-11th/12th-17th/17th-49th snapshots for
training/validation/testing. Also, due to the fact that each graph snapshot has very low positive label
rate, we group the 33 testing graph snapshots into 9 test sets according to the chronological order.
In Fig. 8 we present the label rate and positive label rate for training/validation/testing sets. As we
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 testing data.

OGB-Arxiv is composed of 169,343 Arxiv CS papers from 40 subject areas and their citation
relationship. The goal is to predict a paper’s subject area. In (Hu et al., 2020), the papers published
before 2017, on 2018 and since 2019 are used for training/validation/testing. Also, the authors adopt
the transductive learning setting, i.e., the nodes in validation and test sets also exist in the graph for
training. In our case, we instead adopt inductive learning setting where the nodes in validation and
test sets are unseen during training, which is more akin to the real-world situation. Besides, for better
evaluation on generalization, especially extrapolating to new data, we consider dataset splits with a
larger year gap: we use papers published before 2011 for training, from 2011 to 2014 for validation,
and after 2014 for test. Such a 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. In Fig. 9, we visualize the T-SNE embeddings of the
nodes and mark the training/validation/testing nodes with different colors. From Fig. 9(a) to Fig. 9(c),
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 in Table 3 where we observe that as the time difference between testing
and training data goes larger, model performance suffers a clear drop, with ERM suffering more than
EERM.

F IMPLEMENTATION DETAILS

In this section, we present the details for our implementation in Section 5 including the model
architectures, hyper-parameter settings and training details in order for reproducibility. Most of our
experiments are run on GeForce RTX 2080Ti with 11GB 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

-  PyTorch 1.9.0


-----

(a) Test nodes within 2014 - 2016 (colored yellow)

(b) Test nodes within 2016 - 2018 (colored yellow)

(c) Test nodes within 2018 - 2020 (colored yellow)


Figure 9: T-SNE visualization of training/validation/testing nodes in OGB-Arxiv. We mark training
nodes (within 1950-2011) and validation nodes (within 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 as the time difference of testing data and training/validation data goes large from (a) to (c), the
testing nodes non-overlapped with training/validation ones become more, which suggests that the
distribution shifts become more significant and require the model to extrapolate to more difficult
future data.

-  PyTorch Geometric 1.7.2

F.1 MODEL ARCHITECTURES

In our experiments in Section 5, we adopt different GNN architectures as the backbone. Here we
introduce the details for them.

**GCN. We use the GCNConv available in Pytorch Geometric for implementation. The detailed**
architecture description is as below:

-  A sequence of L-layer GCNConv.

-  Add self-loop and use batch normalization for graph convolution in 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:


-----

-  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 in 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 in each layer.

-  Use ReLU as the activation.

**GCNII. We use the implementation[4]** provided by the original paper (Chen et al., 2020a). The
associated hyper-parameters in GCNII model are set as: αGCNII = 0.1 and λGCNII = 1.0.

**GPRGNN. We use the implementation[5]** provided by Chien et al. (2021). We adopt the PPR initialization and GPRprop as the propagation unit. The associated hyper-parameters in GPRGNN model
are set as: αGP RGNN = 0.1.

F.2 HYPER PARAMETER SETTINGS

The hyper-parameters for model architectures are set as default values in different cases. Other hyperparameters are searched with grid search on validation dataset. The searching space are as follows:
learning rate for GNN backbone αf 0.0001, 0.0002, 0.001, 0.005, 0.01, learning rate for graph
editers αg 0.0001, 0.001, 0.005 ∈{, 0.01, weight for combination β _}_ 0.2, 0.5, 1.0, 2.0, 3.0,
number of edge editing for each node ∈{ _s ∈{}_ 1, 5, 10}, number of iterations for inner update before ∈{ _}_
one-step outer update T ∈{1, 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 set αg = 0.005, αf = 0.01, β = 2.0, s = 5, T = 1.

F.2.2 SETTINGS FOR SECTION 5.2

For GCN, we set the layer number L as 2. For GAT, we set L = 2 and H = 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-Explicit, other hyper-parameters are set as follows:

-  GCN: αg = 0.001, αf = 0.01, β = 3.0, s = 5, T = 1.

-  GAT: αg = 0.005, αf = 0.01, β = 1.0, s = 5, T = 1.

-  GCNII: αg = 0.01, αf = 0.001, β = 1.0, s = 5, T = 1.

For Facebook-100, other hyper-parameters are set as: αg = 0.005, αf = 0.01, β = 1.0, s = 5,
_T = 1._

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-parameters are set as follows:

-  GraphSAGE: αg = 0.0001, αf = 0.0002, β = 1.0, s = 5, T = 1.

-  GPRGNN: αg = 0.005, αf = 0.01, β = 1.0, s = 5, T = 1.

For OGB-Arxiv, other hyper-parameters are set as follows:

[4https://github.com/chennnM/GCNII](https://github.com/chennnM/GCNII)
[5https://github.com/jianhao2016/GPRGNN](https://github.com/jianhao2016/GPRGNN)


-----

-  GraphSAGE: αg = 0.01, αf = 0.005, β = 0.5, s = 1, T = 5.

-  GPRGNN: αg = 0.001, αf = 0.01, β = 1.0, s = 1, T = 5.

F.3 TRAINING DETAILS

For each method, we train the model with a fixed number of epochs and report the test result achieved
at the epoch when the model provides the best performance on validation set.

G MORE EXPERIMENT RESULTS

We provide additional experiment results in this section. In Fig.10 and 11 we 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.1,
which again verifies the effectiveness of our approach. Besides, the corresponding extra results on
Photo are shown in Fig. 14, 15, 16 and 17, which also back up our discussions in Section 5.1.


-----

90

80

70

60

50

40


T1 T2 T3 T4 T5 T6 T7 T8


ERM
EERM


Figure 10: Distribution of test accuracy results on Cora with artificial distribution shifts generated
by SGC as the GNN generator.


80

70

60

50

40


T1 T2 T3 T4 T5 T6 T7 T8


ERM
EERM


Figure 11: Distribution of test accuracy results on Cora with artificial distribution shifts generated
by GAT as the GNN generator.


-----

85.0

82.5

80.0

77.5

75.0

72.5

70.0

67.5

65.0
ERM EERM


w/ spurious
w/o spurious


Figure 12: Comparison of training accuracy using all the features v.s. removing the spurious features
for inference on Cora with artificial distribution shifts generated by SGC as the GNN generator.

85.0

82.5

80.0

77.5

75.0

Accuracy

72.5

70.0

67.5


65.0
ERM EERM

w/ spurious
w/o spurious


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 as the GNN generator.


-----

85

80

75

70

65


T1 T2 T3 T4 T5 T6 T7 T8

ERM
EERM


Figure 14: Distribution of test accuracy results on Photo with artificial distribution shifts generated
by SGC as the GNN generator.


85

80

75

70

65

60


T1 T2 T3 T4 T5 T6 T7 T8

ERM
EERM


Figure 15: Distribution of test accuracy results on Photo with artificial distribution shifts generated
by GAT as the GNN generator.


-----

85.0

82.5

80.0

77.5

75.0

72.5

70.0

67.5

65.0
ERM EERM


w/ spurious
w/o spurious


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 the GNN generator.

85.0

82.5

80.0

77.5

75.0

Accuracy

72.5

70.0

67.5


65.0
ERM EERM

w/ spurious
w/o spurious


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 as the GNN generator.


-----

