On Single-environment Extrapolations in Graph Classification and Regression Tasks
Authors: Beatrice Bevilacqua
Yangze Zhou
Ryan L Murphy
Bruno Ribeiro
Venue:  (2021)
Keywords: Extrapolation
Graphs
GNNs
SCM
Causality
Counterfactual Inference

Abstract: Extrapolation in graph classification/regression remains an underexplored area of an otherwise rapidly developing field. Our work contributes to a growing literature by providing the first systematic counterfactual modeling framework for extrapolations in graph classification/regression tasks. To show that extrapolation from a single training environment is possible, we develop a connection between certain extrapolation tasks on graph sizes and Lovasz's characterization of graph limits. For these extrapolations, standard graph neural networks (GNNs) will fail, while classifiers using induced homomorphism densities succeed, but mostly on unattributed graphs. Generalizing these density features through a GNN subgraph decomposition allows them to also succeed in more complex attributed graph extrapolation tasks. Finally, our experiments validate our theoretical results and showcase some shortcomings of common (interpolation) methods in the literature.

Under review as a conference paper at ICLR 2021
ON SINGLE-ENVIROMMENT EXTRAPOLATIONS IN GRAPH CLASSIFICATION AND REGRESSION TASKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Extrapolation in graph classificatonnregressoon remains an underexplored area of an otherwise rapidly developing field. Our work contributes to a growing lit- erature by providing the first systematic counterfactual modeling framework for extrapolations in graph classification/rerrssiion tasks. To show that extrapolation from a single training environment is possible, we develop connection between certain extrapolation tasks on graph sizes and Lovász's characterization of graph limits. For these extrapolations, standard graph neural networks (GNNs) will fail, while classifiers using induced homomorphism densities succeed, but mostly on unattributed graphs. Generalizing these density features through GNN subgraph decomposition allows them to also succeed in more complex attributed graph ex- trapolation tasks. Finally, our experiments validate our theoretical results and showcase some shortcomings of common (interpolation) methods in the literature.
INTRODUCTION
In some graph classification and regression applications, the graphs themselves are representations of a natural process rather than the true state of the process. Molecular graphs are built from pairwise atom distance matrix by keeping edges whose distance is below a certain threshold and the choice impacts distinguishability between molecules (Klicpera al.. 2020). Functional brain connectomes are derived from time series but researchers must choose frequency range for the signals, which affects resulting graph structure (De Domenico et al., 2016). Recent work (e.g. Knyazev et al. 2019);; Bouritsas et al. (2020); Xu et al. (2020)) explore extrapolations in real-world tasks, showeasing a growing interest the underexplored topic of graph extrapolation tasks.
In this work, we refer to graph-processing environment (or just environment) the collection of heuristics and other data curation processes that gave us the observed graph from the true state of the process under consideration. The true state alone defines the target variable. Our work is in- terested in what we refer as the graph extrapolation task: predict a target variable from a graph regardless of its environment. In this context, even graph sizes can be determined by the environ- ment. Unsurprisingly, graph extrapolation tasks-a type of out-of-distribution prediction-are are only feasible when we make assumptions about these environments.
We define the graph extrapolation task as a counterfactual inference task that requires learning inniromment-invariantt (E-invariant) representations. Unfortunately, graph datasets largely contain a single environment, while common E-invariant representation methods require training data from multiple environments, including Independence of causal mechanism (ICM) methods (Bengio al.
2019
Besserve et al. Johansson et al.) 2016 Louizos et al. 2017 Raj et al. [020 Schölkopf
2019
Arjovsky al.) 2019), Causal Discovery from Change (CDC) methods (Tian & Pear 2001))
and representation disentunglement methods (Bengio et al. 2019 Goudet et al. 2017 Locatello
al. 2019).
Contributions. Our work contributes to growing literature by providing, to the best of our knowl- edge, the first systematic counterfactual modeling framework for extrapolations in graph classifica- tion/regression tasks. Existing work, e.g., the parallel work Xu et al. (2020), define extrapolations geometrically and, thus, have a different scope. Our work connects Lovasz' 's graph limit theory with graph-size extrapolation in family of graph classification and regression tasks. Moreover, periments show that in these tasks, traditional graph glassffcationn/eeressson methods including graph neural networks and graph kernels- are unable extrapolate.

---

Under review as a conference paper at ICLR 2021
Torget
ADondee with suslaet
erie PTPSRWY
Zy
W
]esepdaatee) soddd Porppiii
eefect catmpitniilo medil PQraeit
Gerplee parmutston
Ossevved gaan
Figure 1: (a) The DAG of the structural causal model (SCM) of our graph extrapolation tasks where hashed (resp. white) vertices represent observed (resp. hidden) variables; (b) Illustrates the relation- ship between expressive model families and most-expressive extrapolation families.
2 A FAMILY OF GRAPH EXTRAPOLATION TASKS
Geometrically, extrapolation be thought reasoning beyond convex hull of set of training points (Hastie et al] 2012] Haffner [2022] King & Zeng 2006) Xu et al. (020). However, for neural networks- and their arbitrary representation mappings -his geometric interpretation is insufficient to describe a truly broad range of tasks, Rather, extrapolations are better described through coun-
terfactual reasoning (Neyman 1923 Rubin 1974 Pearl 2009 Schölkopf 2019). Specifically we want to ask: After seeing training data from environment A, how to extrapolate and predict what would have been the model predictions of a test example from an unknown environment B, had the training data also been from
B? For instance, what would have been the model predictions for large test example graph if our training data had also been large graphs rather than small ones?
A structural causal model (SCM) for graph classification and regression tasks. In many ap- plications, graphs are simply representations of a natural process rather than the true state of the process. In what follows we assume all graphs are simple, meaning all pairs of vertices have at most one edge and no self-loops are present. Our work defines an n-vertex attributed graph as a sample of a random variable Gn := (x ( X()h))) where X( E 22(+) encodes edges and edge attributes and X((obs) 200h encodes vertex attributes; we will assume Ω Q = -2()) for simplicity. Consider supervised task over a graph input Gn, n 2 2, and its corresponding output Y. We describe the graph and target generation process with the help of structural causal model (SCM) (Pearl 2009 Definition 7.1.1).
We first consider hidden random variable E with support in Z that describes the graph-processing environment (see Introduction). We also consider an independent hidden random variable W e Dw that defines the true state of the data, which is independent of the environment variable E, with an appropriately defined space Dw. In the SCM, these two variables are inputs to a deterministic graph--geneaatin function Zt x that outputs
Dw x Dz + Qnxx, for some appropriately defined space Dz,
Apnde == (X X (hid) Aplobs), 3plobs)_ppiona)) )pronn) = LE W, Ex), with /ylobs) == =n(E,, W).
(I)
where Zx is another independent random variable that defines external noise (like measurement noise of a device). Equation (1) gives edge and vertex attributes of the graph g _ in some arbitrary canonical form (Immerman & Lander 1990), where 7) is a function of both E' and W that gives the number of vertices in the graph. To understand our definitions, consider the following simple example (divided into two parts).
Erdös- Rényi example (part 1): For single environment e, let n(e) be the (fixed) number of vertices of the graphs in our training data, and p W be the probability that any two vertices of the graph have an edge. Finally, the variable Zx can be thought the seed of a random number generator that is drawn m(n-1) times to determine if two distinct vertices are connected by an edge. The above defines our training data as a set of Erdös-Rényi random graphs of size with p W.
2
The data generation process in Equation T could leak information about W through the vertex ids (the order of the vertices). Rather than restricting how W acts on (x (hid),
(hid) 1,1 ...., Micta \itta_NWaba), N we
remedy this by modeling a random permutation to the vertex indices:
globa)
(x((0))))
X (obs) Noota Nitta) (X-(lidd) ((1).=1)) ................................
(lid) af ((Noba)) ). (Niran))))
(2)
2

---

Under review as a conference paper at ICLR 2021
where Uniform(Sxian is uniform permutation of the indices {1..... , Noboo and S is the permutation group. The observed graph is the outcome of this joint permutation of vertex ids.
SCM target variable. We now define our target variable Y. The true target of K is
(3) which is given by a deterministic function h that depends only on W and random noise Zy inde- pendent of W and E. Our final structural causal model is summarized in the directed acyclic graph (DAG) of (igure[a)
Y = (W: Zy),
cedōs-Rééyi example (part 2): The targets of the Erdös-Rény' graphs in our previous example can be, for instance, the value Y = W in Equation (3), which is also the edge probability p.
Graph extrapolation tasks over new environments. Equation (3) shows that our target variable Y is a function only of the true state W of the data, rather than the graph-processing environment E. Due to the reverse path between Y and E' through G in the DAG of Figure aa), Y is not independent of E given Globe These non-causal paths are called backdoor paths since they flow backwards from Y and g Nidess Hence, traditional (interpolation) methods can pick-up this corre- lation, which would prevent the learnt model from extrapolating over environments different than the ones provided in the training data (or even over different P(E) distributions) (Arjovsky et al.) 2019] (Schlkkopi) 2019; de Haan et al., 2019). To address the challenge of predicting Y in spite of backdoor paths, need a backdoor adjustment (Pearl [209) Theorem 3.3.2). Instead of explicitly conditioning on the environment for the adjustment, we eliminate the need for conditioning with a graph representation that is invariant the environment E.
Before we proceed, we note that the existing counterfactual notation in the literature (see Definition 7 of [Bareinboim et al. (2020)) could be cumbersome in our setting. Hence, we re- re-propose the powerful concept of random variable coupling from Markov chains (Pitman| 1976 Propp & Wilson, 1996) to describe our counterfactual inference problem. The coupling of two independent variables Di and D2 is a proof technique that creates a random vector (D), Dj), such that D;, DJ have the same marginal distributions, i = 1, 2, but DJ, D2 are structurally dependent. For instance, if D1, D2 are independent 6-sided die rolls, then D (D + 2) mod 6 + 1, D (D + 1) mod 6 + are coupled variables corresponding to D, and D2. respectively, where D is a 6-sided die roll.
Definition 1 (Counterfactual coupling (CFC)). A counterfactual coupling of Equations
10 is
P(Y y, Global
G. nnlon Nin
E Bw.zx Zr. E. 1 h(W, Zy)) 1|G ( Zx))}
(4)
LIG = (o(EE, W, Zx))} 1 ( n,EE, w)} (( T7(
(obs) Niw N and Glo == (X(_f) x(o) Ny.) (-) is defined be- low, and E and E are independent random variables that sample environments, potentially with different distributions and supports, and 1 is the Dirac delta function. The counterfactual cou- pled variable gh asks what would have happened to Niwi if we had used the environment random variable É in place of E in Equation o (C²) = (x-)) (x=))))())) x! ((N))))))) above.
where globa = (X (X..
In an abuse of notation we have defined
Using Definition D we now prove that a graph representation function I'(:) that is E-invariant is able to predict the targets of the counterfactual graphs.
Proposition 1. Let P( Niatii (lou) and P(Y P =
be the conditional target distri- random variables in Definition [ To simplify expo-
butions defined by the countefictually-cupleed sition, we consider the case where Y E y is discrete. The continuous case is similar but requires graph rep-
significantly more complex measure theory definitions. Consider a resentation I U U2nn + Rd,, d 2 1, and a function p(---) E (0, 1) (e.g., a feedforward network with softmax outpuss) such that, for some e, > O, the interpolation error (generalization error) is defined as
P( P((
Gfobbe) ply, ((G(ooo)) ((od))) ))l <e) 2 1 1- 8, Vy E.
3

---

Under review as a conference paper at ICLR 2021
I is said environment-invariinn (E-invariant) ifT (
Nisa)) where a.s. (almost surely) njst) } with zero probability (measure). Then, the extrapolation ervor is the same as the interpolation error, i.e.,
I(g
T(G = ((
mith ) except for a set of graphs { ( I and (G
means pioba)
P(IP(Y -lg Nith = G plu: [ xith )) ( 21-11666
Vy e...
(5)
Proposition T shows that an E-invariant representation will perform no worse on the counterfactual test data (extrapolation samples from (Y, g )) than on a test dataset having the same environment
distribution the training data (samples from (Y. g )) Other notions of E-invariant representa- tions are possible (Aroossy et al. 2019 kch 2019), but ours -through coupling- provides direct relationship with how learn graph representations from a single training environment. Our task now becomes finding an E-invariant graph representation I' that can describe well the training data distribution. Specifically, we are interested in single-environment extrapolations.
Video
extrapolation). An extrapolation lask is single-enviromment ex- trapolation task if the observed training data is generated from a mangl-envirooment e E Zt, while the test data may come from larger set of environments & zt E + {e).
Definition 2 (Single-environmen
In recent years, a crop of interesting research has analyzed the expressiveness of T.. In what follows explain why these are related interpolations rather than extrapolations.
A comment on most-expressive graph representations, interpolations, and extrapolations, The expressiveness of a graph clasification/regresiio method is a measure of model family bias (Morris) eet al. 2019 Xu et al. (2018)) Gärtner et al., 2003) Maron et al. 2019a Murphy et al. 2019). That is, given enough training data, a neural network from more expressive family can achieve smaller generalization error (interpolation error) than neural network from a less expressive family, assum- ing appropriate optimization. However, this power is just a measure of interpolation capability, not extrapolation. Figure [b) illustrates space where each point is set of neural network parameters from a most-expressive model family. The blue region (ellipsoid i) represents models that can per- fectly interpolate over the training distribution (i.e., models with the smallest generalization error). The models in the blue region are mostly fitting spurious training environment correlations with Y, that will cause poor extrapolations in environments.
The models illustrated in the red region of Figure [T)) (cllipsoid it) are E-invariant and, thus, by Proposition I can extrapolate across environments, since they cannot fit these spurious environment correlations. The intersection between the blue and red regions contains models that are optimal both for test data from the same environment distribution as training (interpolation test) and test data from a different environment distribution (extrapolation test). In our SCM in Equations ( (3). the intersection between the blue and red ellipsoids is nonempty. We can denote the models in the red ellipsoid as the eoot-exppeessive family of E-invariant (Proposition [T]. Our work focuses on a family of classifiers and regression models that reside inside the red ellipsoid.
Summary. In this section we have defined family of extrapolation tasks for graph classification and regression using counterfactual modelling, and connected to the existing literature. Next, we show how these definitions can be applied to a family of random graph models (graphons) first introduced by Diaconis Freedman (198I).
GRAPH MODELS AND EXTRAPOLATIONS
This section introduces an example of a graph representation that is invariant environment changes, that is, the representation is environment-invarian or E-invariant for short.
3.1 AN INFORMAL DESCRIPTION OF AN E-INVARIANT GRAPH REPRESENTATION APPROACH
In order to learn approximately E-invariant representation of family of N-vertex graphs GN. we leverage the stability of subgraph densities (more precisely, induced homomorphism densities) in random graph models (Lovász & Szegedy 2006]. We consider G, to be aertex-attribued graph with discrete attributes (no edge attributes). For a given k-vertex graph F5. (k < n), let ind G,,) be the number of induced homomorphisms of F3 into G,,, informally, the number of mappings from
4

---

Under review as a conference paper at ICLR 2021
((F)) V(G.) such that the corresponding subgraph induced in G, is isomorphic to Fj. The induced homomorphism density is defined as:
ind G..)
Lnd (Fk G₁))
(6)
nl/(nn kk)
Let F&& be the set of all connected vertex-attributed graphs of size k' I k. Using the subgraph densities (induced homomorphism densities) (Fir, G. FF we will construct a (feature vector) representation for Gn,, similar to Hancock & Khoshgoftaar (2020); Pinar et al. (2017).
I' h-hor (Gn)
Σ
tina (Fkr, Ga hon- Fskh
FareTig
where Lone-hor (Fer, (Fkr, } assigns a unique one-hot vector to each distinct graph Fi in Fsk. For instance, for k = 4, the one-hot vectors could be (I,0.... (0.1.... (0,O.....I.............. .)) 00=
(0.0.... etc.. In Section 3.2 we show that the (feature vector) representation in Equation is approximately E-invariant for a class of unattributed and attributed random graphs models.
An alternative form of attributed graph representations use graph neural networks (GNNs) (Kipf & Welling/ 2017 Hamilton et al., 2017, You et al. 2019) to learn representations that can capture information from vertex attributes (see our Appendix for a brief introduction to GNNs). Then, we
arrive to the following GNN-inspired representation of G,;:
[G.)
Σ PREEFR
tima (a.(F,,G,))AAAAEE MAA(FR,GG.RREEDDOTCCCGN (..RREADOU(GGN(FF)))
where READOUT is a function that maps the vertex-level outputs of a GNN to a subgraph-Ievel representation (e.g. via summation). Unfortunately, GNNs
most-expressive representations of graphs (Morris et al. 2019; Murphy et al., 2019; Xu et al., 2018a) and thus L'GNN(-) is less expressive than I 1-hor( (-) for unattributed graphs. representation with greater expressive power is
ToNN+ (Gn)
Σ FErEFER
(ima (Fr', G,, G.JRREADOUT (Fir)),
where GNN+ is most-expressive vevertex graph representation. which can be achieved by any of the methods of Vignac et al. (2020); Maron et al. (2019a); Murphy et al. 2019). Since GNN most expressive, GNN can ignore attributes and map each Fer to a one-hot vector Lone-hot F therefore, TONN+ (.) generalizes I ho) (.) of Equation 77 But note that greater expressiveness does
not imply better extrapolation as discussed in Section
More importantly, GNN and GNN+ representations allow us to increase their E-invariance by adding penalty for having different representations of two graphs Fer and FV with the same topology but different vertex attributes (say, Fu-Zaan and FG-Z)), as long as these differences do not significantly impact downstream model accuracy in the training data. The intuition is that attribute distributions may shift, but if representation of G, tries be invariant possible to vertex attributes through a regularization penalty. it will more likely be E-invariant than the representation without the regularization. Hence, for each attributed kisizee graph Fee, we consider the set H((FF)) of all k v'-vertex attributed graph having the same underlying topology as Fgz but with all possible different vertex attributes. We then define the regularization penalty
1
EN |READOUT(GNN" (Fw)) |
READOUT (He)))l2. (10)
Fesk FArEFsx
where GNN" = GNN if we choose the representation I'GNN or GNN = GNN+ if we choose the representation TaNN+ In practice, we assume Hę uniformly sampled from H(Fee) and we sample one Hg for each Fg. to perform an estimation for Equation (TO)
Practical considerations. Efficient algorithms exist to estimate induced homomorphism densities over all possible connected k-vertex subgraphs (Ahmed et al. 2016; Bressan et al. 2017]: Chen & Lui 2018, Chen et al. 2016; Rossi et al. 2019 Wang et al. 2014). For unattributed graphs and
5, we use ESCAPE (Pinar al. 2017) obtain exact induced homomorphism densities of
5

---

Under review as a conference paper at ICLR 2021
each connected subgraph of size I k. For attributed graphs unattributed graphs with A: >> 5, exact counting becomes intractable so we use R-GPM (Teixeira et al. (018) to obtain unbiased estimates of induced homomorphism counts, from which we compute density estimates. Finally, Proposi- tion 2 in the Appendix shows that certain biased estimators can be used without losing information in the representations in Equation ( if READOUT is the sum of vertex embeddings.
3.2 THEORETICAL DESCRIPTION OF THE E-INNARIANT REPRESENTATION APPROACH
In this section, we show that the graph representations seen in the previous section are approximately E-invariant under a well-known family of random graph models (graphons). We start with Theo- rem D which gives necessary and sufficient conditions for an unattributed graph to be graphon, an extension of Theorem 2.7 of Lovász & Szegedy (2006) to our setting. This is followed by defini- tion of random graphs with attributed vertices, and proof that the representations in the previous section are approximately E-invariant in Theorem
Theorem 1. [Extension of Theorem 2.7 Lovász & Szegedy 2006y] Let In W == EgGGN/W, N=
n, E] be the n-vertex unattributed graph over the true undertying state variable W. If [ satis- fies the following properlies:
Deleting a random vertex v. from W,, and the distribution of the trimmed graph is the same as the distribution of 1n, with 91 W as a trivial graph with a single vertex for all W.
2. For every 1 < < n, the subgraphs of G.,W induced by {1....,k} k3 and {k + I....,n] n) are independent random variables.
Then, the variable W is a random variable defined over the family of symmetric measurable func- tions W: [0, 1|2 - [0, 11, ie., W is random graphon function.
A note on sampling from graphons: A graphon W [0, 1)2 + [0, 1] is a powerful random graph model of variable-size unattributed graphs. A graphon defines the following sampling scheme: (i) For each vertex j in the graph, we assign an independent random value Uy Uniform(0, 1): (ii) We assign an edge between vertices i and j with probability WUU,, U,) for all pairs of vertices # j.
Now consider the following extension of the graphon model to graphs with vertex attributes.
Definition 3. Let A be a set of discrete vertex attributes. The attribute of a vertex j in the graph is given by deterministic function C Z x [0 - A, which takes as inputs the environment E and the (graphon) vertex variable U3- ~ Uniform((, 1), and output the attribute of vertex j.
Example: Stochastic Block Model (SBM) (Snijders & Nowicki 1997]: SBM can be seen as a dis- crete approximation of a graphon (Airoldi et 2013)) that is also amenable to have vertex attributes. SBMs partition the vertex set to disjoint subsets ST, S2, .e.,.... S, (known as blocks or communities) with an associated r x r symmetric matrix P. where the probability of an edge (u, v), E S to v E Sj is P.y. for i.j E .......... The mapping to graphons is as follows: Divide the interval [0, into disjoint convex sets (1), [t1, t2)..... 11 tr.. where to O and t,. 1, such that if vertex u's graphon random variable U, ~ Uniform(O, 1) is such that U, E [f,-1, f,), then vertex v belong to block S, and has attribute C(E, U.) in environment E P(E), with C as in Definition 3
Approximate E-invariance: Let / (lobs) W be the random variable that describes observed vertex- attributed graphs obtained from given an unobserved true state W, satisfying the conditions in The- orem Temmand and Definition 3 By Theorem the true state W can be thought of the graphon model. Next,
the following theorem shows the ability of I' (9 ( (W) to be an approximately E-invariant rep- resentation in training dataset with input graphs 5 IW, while also considering vertex attributes. Other examples can be constructed with meergy-based graph models (EBM) (Holland & Leinhardi, 1981. as long as the EBM can describe graphs of any size (Chatterjec et al. 2013).
Theorem 2 (Approximate E-invariant Graph Representation). Let Himiss W and G geed I be two samples of graphs of sizes Nitraini and Nfiss from the training and test distributions, respectively, both defined over the same true state W and satisfying Theorem [ The training and test distribu- tions differ in their environment variables E and E, respectively (which are allowed to have non- overlapping supports). Assume the vertex attribute function C of Definition Bis invariant to E and E (the reason for this assumption will be clear later). Let (.)) be defined as in Equation (7) replacing lin by linj (the injective homomorphism density Lováázz & Szegedy 2006)) to obtain
6

---

Under review as a conference paper at ICLR 2021
sharp bound, and || c/ denote the L-infinity norm. Note there is bijection berween induced and injective homomorphism densities (Borgs et al. 2006), and we do not lose expressiveness by such replacement. Then. for any integer l S n, and for any constant 0 <<< 1,
Pr([I J-hor (9 (rmmn WW-1"; (ees)) W2 > e) - 2|Fsul(exp( e² N(ttuinn)
c² NNiee
(9
+exp(
))s
8k2
8k2
(11)
Theorem shows how the graph representations given in Equation 7 are approximately E-invariant. Note that for unattributed graphs, we can define -(:-)) = Ø the null attribute, which is invari- ant to any environment by construction. For graphs with attributed vertices, C(s-) being invariant P(E), C(e1, = C(e2. -). The single-envirroment extrapolation deals with P(E) concentrated on only one single value as defined in Definition 2 Theorem 2 shows that for k < min (( Nusso), the representations I i-hoc (.) of two possibly different-sized graphs with the same W are nearly identical. Because of the bi- jection between induced and injective homorphism densities, I (r. is an approximately
to E and E means for any two environment 61 P(E),
E-invariant representation of IW. Theorem also exposes a trade-off, however. If the ob- served graphs tend to be relatively small, the required for nearly E-invariant representations can be small, and then the expressiveness of I (--hor()) gets compromised. That is, the ability of T (-bo
to extract information about W from G W reduces as l decreases. Finally, this guarantees that for appropriate k. passing the representation I'i-ho (W) to a downstream classifier provably approximates the classifier in Equation (3) of Proposition I We defer the choice of downstream models and respective bounds to future work.
(W)
Finally, for the GNN-based graph representations in Equations (8) and (9). the regularization in Equation (10) pushes the representation of vertex attributes to be more E-invariant, making it more likely to satisfy the conditions of E-invariance in Theorem 2 In particular, for the SBM, assume the vertex attributes are tied to blocks, and the vertex attributes are distinct for each block. To be more specific, for a given block S;, we can further divide [4-1,,4] (4) into disjoint sets such that they also assign different attributes to vertices. And the environment operates on changing the division of [t,-1.t;) t2), thus changes the distributions of attributes assigned in each block. If we are going to predict cross- cross-block edge probabilities (see Scction we need the representations to merge attributes that are assigned the same block achieve E-invariance of C. By regularizing (Equation (TO) the GNN-based graph representation (Equations (8) and (9) towards merging the representations of different vertex attributes, we can get an approximately E-invariant representation in this setting.
4 RELATED WORK
This section presents an overview of the related work. Due to space constraints, a more in-depth discussion with further references are given in the Appendix. In particular, the Appendix gives detailed description of dnvironment-nvariinn
methods that require multiple environments in train- ing, including Independence of Causal Mechanism (ICM), Causal Discovery from Change (CDC) methods, and representation düsentanngemeet methods. Also, none of these works focus on graphs.
Counterfactual mechanisms in graph claxiffcation/regresion and other extrapolation work. There are two key sources of causal relationships on graph tasks: Conterfactuals on graphs, interested in cause-effects events related to processes running on top of a graph, such as [Eclles et al. (2016a b). Conterfactuals of graphs, which is the topic of our work, where we want to ascertain a counterfactual relationship between graphs and their targets in the tasks. We are unaware of prior work in this topic. The parallel work of Xu et al. (2020) (aiready discussed) is interested in the narrower geometric definition of extrapolation. Previous works also examine empirically the ability of graph networks to extrapolate in physics (Battaglia et al. 2016) Sanchez--Gonzzlee et al. 20188). mathematical and abstract reasoning (Santoro et | 2018 Saxton et al. 2019)) and graph algorithms (Bello et al., 2017 Nowak al., 2017: Battaglia et al. 2018) Velickovic et al., 2018). These works do not provide guarantees of test extrapolation performance, or a proof that the tasks are really extrapolation tasks over different environments. We hope our work will help guide future extrapolation analysis.
Graph classfficationdregresssoo using induced homomorphism densities. A related interesting set of works look at induced bomomorphism densities as graph features for kernel (Shervashidze et al.) 2009 Yanardag & Vishwanathan 20153] Wale et al. (008). These methods focus on generalization (interpolation) error only and can perform poorly in some tasks (Kriege al. 2018).
7

---

Under review as a conference paper at ICLR 2021
Table 1: Extrapolation performance over unattributed graphs shows clear advantage of environment- invariant representations r',, with or without GNN, over standard (interpolation) methods extrapola- tion test accuracy. Interpolation and extrapolation distributions contain diffcrent-size graphs. (Left) Classifies schizophrenic individuals using brain functional networks where graphs are on average 40% smaller at extrap- olation environment. (Right) A graph classification task with Y p E (0.2, 0.5, 0.8] the edge probabilities of Frdós-Rény' graphs, whose sizes are N Nimin) (((meeep-ts)) E {20,- ... 8 in train & test interpolation and E (140...., 200) in test extrapolation. Table shows mean (standard deviation) accuracy.
pylestr test)
Accuracy in Schizophrenia Task
Accuracy in Erdós- Task
Interpl. Train
Interpl. Test
Extrapl. Test (1)
Interpl. Train
Interpl. Test
Extrapl. Test (1)
GIN RPGIN
0.68 (0.02)
0.71 (0.04)
0.41 (0.04)
0.99 (0.01)
0.99 (0.01)
(0.03)
0.74 (0.02)
0.72 (0.04)
0.44 (0.07)
0.99 (0.01)
1.00 (0.00)
0,36 (0.03)
WL Kemee
1.00 (0.00)
0.63 (0.07)
0.40 (0.00)
1,00 (0.90)
1,00 (0.00)
0,39 (0.00)
GC Kemel
0.61 (0.00)
0.61 (0.06)
0:60 (0.00)
1.00 (0.00)
1.00 (0.00)
1.00 (0.00)
T Fia
0.69 (0.01)
0.70 (0.06)
0.70 (0.05)
1.00 (0.00)
1.00 (0.00)
1.00 (0.00)
Fan (ot
0.68 (0.01)
0.71 (0.06)
0.71 (0.04)
1,00 (0.00)
1.00 (0.00)
1.00 (0.00)
T FarGN (eq. 2
0.68 (0.01)
0.71 (0.04)
0.69 (0.04)
1.00 (0.00)
1.00 (0.00)
1.00 (0.00)
Table 2: Extrapolation performance over attributed graphs shows clear advantage of environment- invariant representations with regularization in Equation (10). The goal is to classify the cross-hlocks edge
probability Y P1,2- Pa.1 E {0.1, 0.33 of Stochastic Block Model (SBM) with vertex attribute distribu- tions that change between training and test extrapolation environments, Interpolation and extrapolation distribu- tions contain different-size graphs: Train & test interpolation contains graphs with ( N (illtep-stss 20,
test extrapolation contains graphs with / seu
40. Table shows mean (standard deviation) accuracy.
Interpolation Train
Interpolation Test
Extrapolation Test (f)
GIN RPGIN
0.95 (0.02)
1.00 (0.00)
0.45 (0.04)
0,98 (0.02)
1.00 (0.00)
0.43 (0.00)
WL Kernel
1.00 (0.00)
0.95 (0.00)
0.57 (0.00)
GC Kernel
1.00 (0.00)
0.90 (0.00)
0.43 (0.00)
T
0,99 (0.00)
0.90 (0.00)
0.43 (0.00)
T Tax
1.00 (0.00)
1.00 (0.00)
0.91 (0.06)
T RRCCN
1.00 (0.00)
1.00 1.00 (0.00)
0.97 (0.03)
GNN-lype representations and subgraph methods. Common GNN methods lack the ability to distin- guish nonisomorphic graphs (Morris et al., [019 Xu et al.
2018a) and cannot count the number of subgraphs such as triangles (3-cliques) (Arvind et al. 2020 Chen et al. 2020). Proposed solutions (c.g. Dasoulas et al. (2019): [Chen al. (2020)) focus on making substructures distinguishable and rather than learning functions that extrapolate. Closer to our represen- tations, other methods based on subgraphs have been proposed. Procedures like mGCMN (Li al.) 2020). HONE (Rossi et al. 2018), and MCN (Lee et al. (2088) learn representations for vertices by extending methods defined over traditional neighborhood (edge) structures to higher-order graphs based on subgraphs; for instance, mGCMN applies GNN on the derived graph. These methods will not learn subgraph representations in a manner consistent with our extrapolation task. These and other related works (detailed in the Appendix) focus generalization (interpolation) error only.
thus expressivity/uuiversaalll
5 EMPIRICAL RESULTT
This section is dedicated to the empirical evaluation of our theoretical claims, including the ability of the representations in Equations 7 to 99) to extrapolate in the manner predicted by Proposition for tasks that abide by conditions 1 and 2 of Theorem [ and Definition 3 We also test their ability to ex- trapolate in a task with a real dataset that does not perfectly fit conditions I and 2 of Theorem [ Our results report (i) interpolation test performance
held out graphs from the same environment used for training; and (ii) extrapolation test performance on held out graphs from different environments. Our code is available and complete details are given in our Appendix.
We choose a few methods as examples of graph representation interpolations. While not an extensive list, these methods are representative of the literature. Graph Isomorphism Network (GIN) (Xu et al. 2018a); Relational Pooling GIN (RPGIN) (Murphy et al.] 2 The Weisfeiler Lehman kernel (WL Kernel) (Shervashidze et al.) 2011) uses the Weisfeiler- Leman algorithm /Weisfeiler & Lehman
Interpolation representations:
1968) to provide graph representations.
https://ancnymouus. wcw.sccieieo
8

---

Under review as a conference paper at ICLR 2021
Extrapolation representations: We experiment with the three representations Ti-hot- TONN. in Equations 7 and (8), and TRRPONN, where we use RPGIN as a method of GNN* in Equation (9). We also test Graphlet counting kernel (GC Kernel) (Shervashidze al. 2009), which is a method that uses a hox GC Kernel since wanted to add better downstream classifier than the one used in Sheevvsssiieee ett al. (2009), Per Section [3.]] we estimate induced homorphism densities of connected graphs of size exactly k, which treated as an hyperparameter.
hox representation as input to a downstream classifier. We report I ho separately from
Extrapolation performance over unattributed graphs of varying size. For these unattributed graph experiments, the task is to extrapolate over environments with different graph sizes. These tasks fulfill the conditions imposed by Theorem[] which allow us to test our theoretical results.
Schizophrenia task. We use the fMRI brain graph data on 71 schizophrenic patients and 74 controls for classifying individuals with schizophrenia (De Domenico et al., 2016). Vertices represent brain regions with edges as functional connectivity. We process the graph differently between interpola- tion and extrapolation data, where interpolation has exactly 264 vertices (a single environment) and extrapolation has average 40% fewer vertices. The graphs are dense and processing approximate the conditions imposed by Theorem 1 The value of k {4, 54 and chosen based on a separate validation error over the interpolation environment. Further details are provided in the Appendix.
Erdös- Rényi task. This is an easy interpolation task. We simulate Erdös-Rényi Rényi graphs (Gilbert 1959 Erdös & Rényi [959) which by design perfectly satisfies the conditions in Theorem []] There
two environments: we train and measure interpolation accuracy graphs of size in (20...80);
we extrapolate to graphs from an environment with size in {140 .003. The task is to classify the edge probability p E {0.2, 0.5, 0.83 of the generated graph. Further details are in the Appendix.
Unattributed graph results: Table D shows that our results perfectly follow Proposition Tand The- orem - where representations I hox (GC Kernel and our simple classifier), TNNN T RRGNN the only ones able to extrapolate. while displaying very similar -often identical- interpolation and extrapolation test accuracies in all experiments. All methods perform well in the interpolation task.
Extrapolation performance over attributed graphs over varying attributes. Next we try an at- tributed graph scenario satisfying the conditions in Theorem I and Definition where the attributed graph environments have a shift in both the observed sizes and the observed attributes (further details in Appendix). We define a Stochastic Block Model (SBM) task with N (iiteerp-tts)) 20 for the interpolation environment and N(ext-test) = 40 for the extrapolation environment. Moreover, the graphs are composed of two blocks with different vertex attribute distributions. Vertices are assigned red or blue attributes if they are in the first block, and green yellow attributes if they are in the second block. The change in environments between training and testing also induces an attribute- shift environment change: in training (and interpolation-tes test), the vertices are predominantly red and green whereas in extrapolation-test. they are mainly blue and yellow. The task is to predict the cross-block edge probability P12 P2 E 0.31.
We learn the graph representations I FIN, T RPGIN of Equations and 9 using the regularization penalty in Equation (1O). The regularization will force GNN representations avoid distinguishing reds+blue and green yyellow vertex attributes, since not distinguishing them will not reduce the accuracy of the downstream model in training data. This should allow these learnt representations to extrapolate to the extrapolation test environment.
Attributed graph results: Table 2 shows that interpolation representations and Fi (GC Kernel and the better classifier) taps into the casy correlation between Y and the density of red and green k-sized graphs, while I'GN and I' RPGIN are E-invariant, which results in extrapolation test accuracy that more closely matches the interpolation test accuracy.
6 CONCLUSIONS
Our work contributes to a growing literature by providing the first systematic counterfactual model- ing framework for extrapolations in graph classfiication/regrrsioo tasks. We connected a family of graph extrapolation tasks with Lovász theory of graph limits, and introduced (E-invariant) representations that can provably extrapolate in such scenarios. Our experiments val- idated our theoretical results and the shortcomings of common graph representation (interpolation) methods.
ietronment-invariann

---

Under review as a conference paper at ICLR 2021
REFERENCES
Ghadeer AbuOda, Gianmarco De Francisci Morales, and Ashraf Aboulnaga. Link prediction via higher-order motif features. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 412-429, Springer, 2019.
Nesreen K Ahmed, Theodore L Willke, and Ryan A Rossi. Estimation of local subgraph counts. In 2016 IEEE International Conference on Big Data (Big Data), pp. 586-595. IEEE, 2016.
Edo M Airoldi, Thiago Costa, and Stanley H Chan. Stochastic blockmodel approximation of graphon: Theory and consistent estimation. In Advances in Neural Information Processing Systems, pp. 692-700, 2013.
David J Aldous. Representations for partially exchangeable arrays of random variables. Journal of Multivariate Analysis, 11(4):511-598, 1981.
Uri Alon. Network motifs: theory and experimental approaches. Nature Reviews Genetics, 8(6): 200-4,
Anonymous. Incremental learning on growing graphs. In Submitted to International Conference on Learning Representations, 2021. under review.
Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv: 2019.
J Scott Armstrong, Fred Collopy, and Thomas Yokum. Decomposition by causal forces: pro- cedure for forecasting complex time series. International Journal of forecasting, 21(():25-36, 2005.
Vikraman Arvind, Frank Fuhlbrücc, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: subgraph counts and related graph properties. Journal of Computer and System Sci- ences, 2020.
James Atwood and Don Towsley. Diffussion-oonvllutioaaal neural networks. In Advances in Neural Information Processing Systems, pp. 1993-2001, 2016.
Elias Bareinboim, Juan Correa, Duligur lbeling, and Thomas Ieard. On Pearl's hierarchy and the foundations of causal inference. ACM special volume in honor of Judea Pearl, 2020.
Jordi Bascompte and Carlos J Melián. Simple trophic modules for complex food webs. Ecology, 86
(11):2868-283) 22733, 2005.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. In Advances in neural information processing systems, pp. 4502-4510, 2016.
Peter Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Gonzaez- Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint urXiv:1806 01261, 2018.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in neural information processing systems, pp. 585-591, 2002.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. International Conference on Learning Representa- tions, 2017.
Yoshua Bengio, Tristan Deleu, Nasim Rahaman, Rosemary Ke, Séhastien Lachapelle, Olexa Bila- niuk, Anirudh Goyal, and Christopher Pal. A meta-transfer objective for learning to disentangle causal mechanisms. arXiv preprint arXiv: /9.1 10912, 2019.
Austin R Benson, David F Gleich, and Jure Leskovec. Higher- order organization of complex net- works. Science, (53(6295) 2016.
10

---

Under review as a conference paper at ICLR 2021
Michel Besserve, Naji Shajarisales, Bernhard Schölkopf, and Dominik Janzing. Group invariance principles for causal generative models. In International Conference on Artificial Intelligence and Statistics, pp. 557-565, 2018.
Christian Borgs, Jennifer Chayes, László Lovász, Vera T Sós, and Katalin Vesztergombi. Counting graph homomorphisms. In Topics in discrete mathematics, pp. 315-371. Springer, 2006.
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path kernels on graphs. In Fifth IEEE international conference on data mining (ICDM'05), pp. 8-pp. IEEE, 2005.
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(supp__1:: i47-i56, 2005.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improv- ing graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.09 092.52, 2020.
Marco Bressan, Flavio Chicrichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi. Count- ing graphlets: Space vs time. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining (WSDM' 17), pp. 557-566. ACM, 2017.
Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. In Advances in neural information processing systems, pp. 4868 4879-4879900 2019.
Ines Chami, Sami Abu-El-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy. Machine learning on graphs: model and comprehensive taxonomy. arXiv preprint arXiv:2005.0366 2020.
Sourav Chatterjee, Persi Diaconis, al. Estimating and understanding exponential random graph models. The Annals of Statistics, 41(5):2428-2465 2013.
Lina Chen, Xiaoli Qu, Mushui Cao, Yanyan Zhou, Wan Li, Binhua Liang, Weiguo Li, Weiming He, Chenchen Feng, Xu Jia, et al. Identification of breast cancer patients based on human signaling network motifs. Scientific reports, 3:3368, 2013.
Xiaowei Chen and John CS Lui. Mining graphlet counts in online social networks. ACM Transac- tions on Knowledge Discovery from Data (TKDD), 12(4):1-38, 2018.
Xiaowei Chen, Yongkun Li, Pinghui Wang, and John Lui. A general framework for estimating graphlet statistics via random walk. arXiv preprint 1rXiv 075044 2016.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? arXiv preprint 20X1v:2002.04055, 2020.
George Dasoulas, Ludovie Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. arXiv preprint arXiv: 19/2.06088 2019.
Manlio De Domenico, Shuntaro Sasai, and Alex Arenas. Mapping multiplex hubs in human func- tional brain networks. Frontiers in neuroscience, 10:326, 2016.
Pim de Haan, Dinesh Jayaraman, and Sergey Levine. Causal confusion in imitation learning. In Advances in Neural Information Processing Systems, pp. 11698- 1709, 2019.
Asim K Dey, Yulia R Gel, and H Vincent Poor. What network motifs tell us about resilience and reliability of complex networks. Proceedings of the National Academy of Sciences, 116(39): 19368-19373, 2019.
Persi Diaconis and David Freedman. On the statisties of vision: the julesz conjecture. Journal of Mathematical Psychology, 24(2):1 12-138, 1981.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Gure Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, pp. 2224-2232, 2015.

---

Under review as a conference paper at ICLR 2021
Dean Eckles, Brian Karrer, and Johan Ugander. Design and analysis of experiments in networks: Reducing bias from interference. Journal of Causal Inference, 5(1), 2016a.
Dean Eckles, René F Kizilcec, and Eytan Bakshy, Estimating peer effects in networks with peer encouragement designs. Proceedings of the National Academy of Sciences, 113(2)):731--332, 2016b.
P Erdōs and A Rényi. On random graphs i. Publ. math. debrecen, 6(290-297):18, 1959.
Matthias Fey and Jan Lenssen. Fast graph representation learning with PyTorch Geometrie. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
V. K. Garg, S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In Proceedings of the 37th International Conference on Machine Learning, Proceed- ings of Machine Learning Research. PMLR, 2020.
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning theory and kernel machines, pp. 129-143. Springer, 2003.
Edgar N Gilbert. Random graphs. The Annals of Mahematical Statistics, 30(()) 1959.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference Learning Representations (ICLR), 2015.
Olivier Goudet, Diviyan Kalainathan, Philippe Caillou, Isabelle Guyon, David Lopez-Paz, and Michèle Sebag. Causal generative neural networks. arXiv preprint 1.Xiv:1711.089338 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proc. of
KDD, pp. 855-864. ACM, 2016.
Patrick Haffner. Escaping the convex hull with extrapolated vector machines. In Advances in Neural Information Processing Systems, pp. 753-760, 2002.
Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using networkx. In Gaël Varoquaux, Travis Vaught, and Jarrod Millman (eds.), Proceedings of the 7th Python in Science Conference, pp. 11 15, Pasadena, CA USA, 2008.
Patric Hagmann, Maciej Kurant, Xavier Gigandet, Patrick Thiran, Van Wedeen, Reto Meuli, and Jean-Philipps Thiran. Mapping human whole-brain structural networks with diffusion mri. PloS one, 2(7)x 2007.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
William L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 14(3):1-159, 2020.
John T Hancock and Taghi Khoshgoftaar. Survey on categorical data for neural networks. Journal of Big Data, 7:1-41, 2020.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning, vol- ume 1. Springer series in statistics, 2012.
Robert I. Hemminger. On reconstructing a graph. Proceedings of the American Mathematical Society, 20(1) 1969.
Alex Hernández- Gareia and Peter König. Data augmentation instead of explicit regularizationn arXiv preprint 1886:22806.038822 2018.
12

---

Under review as a conference paper at ICLR 2021
Paul W Holland and Samuel Leinhardt. An exponential family of probability distributions for di- rected graphs. Journal of the american Statistical association, 76(373):33 1981.
Douglas Hoover. Relations on probability spaces and arrays of random variables. Technical Report, Institute for Advanced Study, Princeton, NJ, 2, 1979.
Weihua Hu, Matthias Fey, Marinka Zitikk Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0068) 2020.
Maximilian Isse, Jakub M Tomczak, and Max Welling. Attention-based deep multiple instance learning. arXiv preprint arXiv:1802.04712, 2018.
Neil Immerman and Eric Lander. Describing graphs: A first-order approach to graph canonization. In Complexity theory retrospective, pp. 59-81. Springer, 1990.
Fredrik Johansson, Uri Shalit, and David Sontag. Learning representations for counterfactual infer- ence. In International conference on machine learning, pp. 0020-3029, 2016.
Olav Kallenberg. Probabilistic symmetries and invariance principles. Springer Science & Business Media, 2006.
Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of the 20th international conference machine learning (ICML-033, pp. 321- 328, 2003.
Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: A survey, Journal of Machine Learning Research, 21(70):1-73, 2020.
Paul Kelly et al. A congruence theorem for trees. Pacific Journal of Mathematics, 7(1):911-968, 1957.
Gary King and Langche Zeng. The dangers of extreme counterfactuals. Political Analysis, 14(2): 131-159, 2006.
Thomas Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. NIPS Workshop on Bayesian
Deep Learning, 2016.
Johannes Klicpera, Janek GroB, and Stephan Günnemann. Directional message passing for molec- ular graphs. arXiv preprint wrXiv:2003.03123 2020.
Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and generalization in graph neural networks. In Advances in Neural Information Processing Systems, pp. 4202-4212, 2019.
Nils M Kriege, Christopher Morris, Anja Rey, and Christian Sohler. A property testing framework for the theoretical expressivity of graph kernels. In IJCAI, pp. 2348-2354, 2018.
Nils M Kriege, Fredrik D Johansson, and Christopher Morris. A survey on graph kemels.. Applied Network Science, 5(1):1-42, 2020.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in tempo- ral interaction networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '19, pp. 1269-1278, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 978 9781450362016.
Guillaume Lample and François Charton. Deep learning for symbolic mathematics. In International Conference on Learning Representations, 2020.
John Boaz Lee, Ryan A Rossi, Xiangnan Kong, Sungchul Kim, Eunyee Koh, and Anup Rao. Higher- order graph convolutional networks. arXiv preprint arXiv: 1809.0709999 2018.
13

---

Under review as a conference paper at ICLR 2021
Xing Li, Wei Wei, Xiangnan Feng. Xue Liu, and Zhiming Zheng. Representation learning of graphs using graph convolutional multilayer networks based on motifs. arXiv preprint arXiv:2007. 2020.
Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. In Advances in Neural Information Processing Systems, pp. 8230-8241, 2019.
Francesco Locatello, Stefan Bauer, Mario Lucic, Gunnar Raetsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem. Challenging common assumptions in the unsupervised learning of disentangled representations. international conference on machine learning, pp. 41 4114-4124,
2019.
Christos Louizos, Uri Shalit, Joris M Mooij, David Sontag, Richard Zemel, and Max Welling- Causal effect inference with deep latent-variable models. In Advances in Neural Information Processing Systems, pp. 6446-6456, 2017.
László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.
László Lovász and Balázs Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96(6):933 (11)9933-957, 2006.
Shmoolik Mangan and Uri Alon. Structure and function of the forw-forward loop network motif. Proceedings of the National Academy Sciences, (00(21):11800-199 2003.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pp. 2156-2166661 2167, 2019a.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2019b.
Brendan D McKay. Small graphs reconstructible. Australasian Journal of Combinatorics, 15: 123-126, 1997.
Brendan D McKay and Adolfo Piperno. Practical graph isomorphism, ii Journal of Symbolic Computation, 60:94-112, 2014.
Changping Meng, S Chandra Mouli, Bruno Ribeiro, and Jennifer Neville. Subgraph pattern neural networks for high-order graph evolution prediction. AAAL, pp. 3778-3787, 2018
Ron Milo, Shai Shen-Or, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Net- work motifs: simple building blocks of complex networks. Science, 298(5594):824887,, 2002.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Elizabeth Munch. A user's guide topological data analysis. Journal of Learning Analytics, 4(2):
47-61, 2017.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pool- ing for graph representations. In Proceedings of the 36th International Conference on Machine Learning. 2019.
J Neyman. Sur les applications de la theoric des probabilites experiences agricoles: essai des principes (masters thesis); justification applications of the calculus of probabilities to the solu- tions of certain questions in agricultural experimentation. excerpts english translation (reprinted). Stat Sci, 5:463-477 1923.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In International conference on machine learning, pp. 2014-2023, 2016.
Alex Nowak, Soledad Villar, Afonso Bandeira, and Joan Bruna. A note learning algorithms for quadratic assignment with graph neural networks. In Proceeding of the 34th International Conference Machine Learning (ICMI), volume 1050, pp. 22, 2017.
14

---

Under review as a conference paper at ICLR 2021
Peter Orbanz and Daniel M Roy. Bayesian models of graphs, arrays and other exchangeable random structures. IEEE transactions on pattern analysis and machine intelligence, 37(2):437-46.1 2014.
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserv- ing graph embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1105-1114, 2016.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pp. 506-519, 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
Judea Pearl. Causality. Cambridge university press, 2009.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn; Machine learning in Python. Journal of Machine Learning Research, 12:2825-288 2011.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Ali Pinar, Seshadhri, and Vaidyanathan Vishal. Escape: Efficiently counting all 5-vertex sub- graphs. In Proceedings of the 26th International Conference on World Wide Web, pp. 1431-1440, 2017.
JW Pitman. On coupling of markov chains. Zeitschrift.fi Wahnsscheimiiccheisshheeiii und verwandte Gebiete, 35(4):315-322, 1976.
James Gary Propp and David Bruce Wilson. Exact sampling with coupled markov chains and applications to statistical mechanics. Random Structures & Algorithms, 91-2))223-255 -2222, 1996.
Nataša Pržulj. Biological network comparison using graphlet degree distribution. Bioinformatics, 23(2)el77-e183, 2007.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 459 467, 2018.
Anant Raj. Stefan Bauer, Ashkan Soleymani, Michel Besserve, and Bernhard Schölkopf. Causal feature selection via orthogonal search. arXiv preprint arXiv:2007.029338 2020.
Bastian Rieck, Christian Bock, and Karsten Borgwardt. A persistent weisfeiler-lehman procedure for graph classification. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5448-5458, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Ryan A Rossi, Nesreen K Ahmed, and Eunyee Koh. Higher-order network representation learning. In Companion Proceedings of the The Web Conference 2018, pp. 3-4, 2018.
Ryan A Rossi, Nesreen K Ahmed, Aldo Carranza, David Arbour, Anup Rao, Sungchul Kim, and Eunyee Koh. Heterogeneous network motifs. arXiv preprint arXiv: 190/. 2019.
Donald B Rubin. Estimating causal effects of treatments in randomized and nonrandomized studies.
Journal of educational Psychology, 66(5):688, 1974.
15

---

Under review as a conference paper at ICLR 2021
Alvaro Sanchez-Gonzalle Nicolas Heess, Jost Tobias Springenberg, Josh Merel, Martin A Ried- miller, Raia Hadsell, and Peter Battaglia. Graph networks as learnable physics engines for infer- ence and control. In International Conference Machine Learning, 2018.
Adam Santoro, Felix Hill, David Barrett, Ari Morcos, and Timothy Lillicrap. Measuring abstract reasoning in neural networks, In International Conference on Machine Learning, pp. 4477-4486, 2018.
Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04078, 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. arXiv preprini arXiv:2002.03/55, 2020.
David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical rea- soning abilities of neural models. International Conference on Learning Representations, 2019.
Bernhard Schölkopf. Causality for machine learning. arXiv preprint arXiv:1911.10500 2019.
J Scott Armstrong and Fred Collopy. Causal forces: Structuring knowledge for time-series extrapo- lation. Journal of Forecasting, 12(2):003-155, 1993.
Shai S Shen-Orr, Ron Milo, Shmoolik Mangan, and Uri Alon. Network motifs in the transcriptional regulation network of escherichia coli. Nature genetics, 31(1):64-66 68, 2002.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mchlhorn, and Karsten Borgwardt. Ef- ficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics, pp. 488 495, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mchlhorn, and Karsten M Borg- wardt. Weisfeiler-lhhman graph kernels. Journal of Machine Learning Research, 12(Sep):2539- 2011,
Chawin Sitawarin, Arjun Nitin Bhagoji, Arsalan Mosenia, Prateek Mittal, and Mung Chiang. Rogue signs: Deceiving traffic sign recognition with malicious ads and logos. CoRR, boos/1801.0280,, 2018.
Tom AB Snijders and Krzysztof Nowicki. Estimation and prediction for stochastic blockmodels for graphs with latent block structure. Journal of classification, 14(1):75-100, 1997.
Olaf Sporns and Rolf Kötter. Motifs in brain networks. PLoS biology, 2(11):;369, 2004.
Lewi Stone and Alan Roberts. Competitive exclusion, or species aggregation? Occologia, 91(3): 419-424, 1992.
Lewi Stone, Daniel Simberloff, and Yael Artzy-Randrup. Network motifs and their origins. PLoS computational biology, 1504)ee,0 2019.
Mahito Sugiyama, M. Elisabetta Ghisu, Felipe Llinares-ópezz, and Karsten Borgwardt. graphker- nels: R and python packages for graph comparison. Bioinformatics, 34(3):530-53,, 2017
Haitian Sun, Bhuwan Dhingra, Manzil Zaheer, Kathryn Mazaitis, Ruslan Salakhutdinov, and William Cohen. Open domain question answering using carly fusion of knowledge bases and text. In Proceedings of the 2018 Conference Empirical Methods in Natural Language Process- ing, pp. 4231-4242, Brussels, Belgium, Oetober-November 2018. Association for Computational Linguistics.
Carlos HC Teixcira, Leornado Cotta, Bruno Ribeiro. and Wagner Meira. Graph pattern mining and learning through user-defined relations. In 2018 IEEE International Conference on Data Mining (ICDM), pp. 1266-1271. IEEE, 2018.
Komal K. Teru, Etienne Denis, and William L. Hamilton. Inductive relation prediction by subgraph reasoning. In Proceedings of the 37th International Conference on Machine Learning, Proceed- ings of Machine Learning Research. PMLR, 2020.
16

---

Under review as a conference paper at ICLR 2021
Jin Tian and Judea Pearl. Causal discovery from changes. UAI, 2001.
Stanislaw M Ulam. A collection of mathematical problems. Wiley, New York, 29, 1960.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. ICLR, 2018.
Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural paassig--pssinng arXiv e-prints, pp. arXiv-2006, 2020.
Nikil Wale, lan A Watson, and George Karypis. Comparison of descriptor spaces for chemical com- pound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008
Li Wang, Hongying Zhao, Jing Li, Yingqi Xu, Yujia Lan, Wenkang Yin, Xiaoqin Liu, Lei Yu, Shihua Lin, Michael Yifei Du al. Identifying functions and prognostic biomarkers of network motifs marked by diverse chromatin states in human cell lines. Oncogene, 39(3):677-68)) 2020a.
Pinghui Wang, John CS Lui, Bruno Ribeiro, Don Towsley, Junzhou Zhao, and Xiaohong Guan. Effi- ciently estimating motif statistics of large networks. ACM Transactions Knowledge Discovery from Data (TKDD), 92)):127, 2014.
Yiwei Wang, Wei Wang. Yuxuan Liang, Yujun Cai, and Bryan Hooi. Graphcrop: Subgraph cropping for graph classification. arXiv preprint arXiv:2009. 10564, 2020b.
Van J Wedeen, Patric Hagmann, Wen- Yih Isaac Tseng, Timothy G Reese, and Robert Weisskoff. Mapping complex tissue architecture with diffusion spectrum magnetic resonance imaging. Mag- netic resonance in medicine, 54(6):1377-1333 2005.
Boris Weisfeiler and AA Lehman. A reduction of graph to canonical form and an algebra arising Informatsia, 1291:12-16, 1968.
during this reduction. Mouchmo-Technichesee
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1rXiv:1810.00826. 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Ste- fanie Jegelka. Representation learning on graphs with jumping knowledge networks. volume 80 of Proceedings of Machine Learning Research, pp. 5453-5462, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018b. PMLR.
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. arXiv preprint arXiv:2009.1 11848 2020.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374. ACM, 2015.
Wei Ye, Omid Askarisichani, Alex Jones, and Ambuj Singh. Deepmap: Learning deep representa- tions for graph classification. arXiv preprint arXiv:2004.0213), 2020.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. volume 97 of Proceedings of Machine Learning Research, pp. 7134-7143, Long Beach, California, USA, 09-15 Jun 2019. PMLR
Wenchao Yu, Cheng Zheng, Wei Cheng, Charu C Aggarwal, Dongjin Song, Bo Zong, Haifeng Chen. and Wei Wang. Learning deep network representations with adversarially regularized au- toencoders. In Proc. of AAAI, pp. 2663-2671. ACM, 2018.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5175, 2018.
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey. IEEE Transactions Knowledge and Data Engineering, 2020.
17

---

Under review as a conference paper at ICLR 2021
A PROOF OF PROPOSITION
Proposition 1. Let g =Grobau) Niaau (low))) and P(Y g -G be the conditional target distri- butions defined by the counterfactulllycouphl cooppeee random variables Te Definition To simplify expo- sition, consider the case where Y E y is discrete. The continuous case is similar but requires significantly more complex measure theory definitions. Consider a permulation-invariane resentation I - + RR, d 2 1, and a function p(:,-) E [0, 1] (e.g., a feedforward network with softmax outputs) such that, for some e, O, the interpolation error (generalization error) is defined as
graph rep-
P(Y = ylg
Nindo ( p(y, ((Gg)))))) Tpinaal ))1 26)21-0 Vy E E.
I is said environment-invarian (E-invariant) if (ahaa))
Bug. T(G NiGn where a.s. (almost surely) means ((Gtobad) ploda) = ((G w except for a set of graphs (Glotan) and (Glof ( with zero probability (measure). Then, the extrapolation error is the same as the interpolation error, i.e.,
P(IP(Y = -lg = -G(0) ni/d) - plu: D mo )) S 26)2--0
Vy e.
(5)
Proof. By Equation 33. is only function of W and some independent random noise, not E.
Then, replacing E by E in Definition
N ((o ) P(Y y 1 will not affect the distribution of Y. which yields P(Y
Glef (gto)) Since, by definition [(G (( = T(G (oot)) for
any two graphs Glabn and G that can be sampled by our data generation process, we have that p(y, ((G ((00)) = p(y, (GG plln )), concluding our proof.
B PROOF OF THEOREM 1
Theorem 1. [Extension of Theorem 2.7 Lovász & Szegedy 2006i] Let 9n W == EgGGN|W,N
n, E) be the n-vertex unattributed graph over the true underlying state variable W. If W satis- fies the following properlies:
Deleting random vertex n. from G,, and the distribution of the trimmed graph the same as the distribution of In-1WW, with G1 W as a trivial graph with a single vertex for all W.
For every < < n, the subgraphs of G induced by (1...., k} and {k: + 1,..., n) are independent random variables.
Then, the variable W is a random variable defined over the family of symmetric measurable func- tions W 10, 1] - [0, 11, i.e, W is random graphon function.
Proof. First, direct consequence of Equation ( is that the distribution of ((obs) IW is invariant under relabeling of the vertices (permutation invariance). We add this latter condition to conditions
I and 2 of Theorem [ Given these three conditions, Theorem 2.7 of Lovász & Szegedy (2006) states that (lobs) W's graph topology equivalent to that of the graphon mode G(n,
with
W' [0, 1 + [0, 1] symmetric function. That is, such that the composition π o Eg (WW 2x) of Equations [I] and (2) is a graphon model. Since, the topology generated by ge does not change with the environment e, the original (gg) and the new graph generation processes (g'z) would be indistinguishable for whatever distribution P(E).
redefine gg of Equation I I'
C PROOF OF THEOREM 2
Theorem (Approximate E-invariant Graph Representation). Let I glttrain) W and & Now IW be two samples of graphs of sizes Nitrain and Nfestt from the training and test distributions, respectively,
(test)
"The graphon model was described as W-random graph in Lovász & Szegedy (200)), with the notation later changing in the literature match that of Diaconis & Freedman (1981) the first paper to describe the model.
18

---

Under review as a conference paper at ICLR 2021
both defined over the same true state W and satisfying Theorem 7
The training and test distribu- tions differ in their environment variables E and E, respectively (which are allowed to have non- overlapping supports). Assume the vertex attribute function C of Definition is invariant to and
É (the reason for this assumption will be clear later). Let [i))(()) be defined as in Equation 7 replacing lind by linj (the injective homomorphism density (Lovász & SSzegdy 2006)) to obtuin
sharp bound, and || oo denote the L-infinity norm, Note there is a bijection between induced and
injective homomorphism densities (Borgs al. 2006), and we do not lose expressiveness by such
replacement. Then, for any integer k S n, and for any constant 0 <<<) <1
e² N(trui)))
e² N
Pr[[IT J-hor (9 grtoroo) W -W-rri-me T-hor (oon W> > e) S 2| 2]F5g((expp(
+exp(
)),
81.2
8k.2
(11)
Proof. (ing(Fk, Gn) is defined by
(nk G.) inj(Fe: G.) nl/(n- - k)!
(12)
where inj( Gr)) is the number of injective homomorphisms of F5 into Gn.
From Lovász & Szegedy 2006 Theorem 2.5), we know for unattributed graphs g No WW
2²
Pr(( (W) - (F,,, W) > c) S 2exp(-
N(1)
(13)
21
The definition of ((Fs; W) can be found Lovász & Szegedy (2006).
Since Iiina (FR, I [
W) t(F W)l S 8 and Mima(Frx I M (W) t(FR, W) 1 y implies
(train) Mmna (R,, 9 Nama IW) lind FR, I (lest)
[W] S
Pr[M (Fer ((train)
W) - Lind (In FF,,
(test)
Nosen WW] > E)
Pr([lind Fe, G (train)
W) Lind (R 9 N/m0
g(leat)
WW) (e)
S Pr((iind Fk, I (train)
W)- t(Fe, W S ;)
Pr Biid (Fe, I ( t(xx, W)l S 2
Neeam
2²
< 11 - (1 - 2 2exp(
N ((raain)))
- 2 2exp(=
N(wes)
8h.2
81.2
2
2²
2
2(eex((
N(tmain) expl(
N(tees)))
- -4exp(-
(Nitmin)) + A((ess))
8k
8k.2
8k
2
2
2(exp(
N(train))
+ exp((
N((est))
81.2
8k.2
(14)
Then we know
Pr[[I[T i-hor G (raan))
W) ri- ( Nrnen Willoo 5)
= Pr([tima( Fex, prmamn I linal ( Fk,, I (tess I )| S for all FEr E FsK)
2 1 Σ
Pr(1tind Fk,, poma (W) - timd (Fwr ((ees) [W) > c)
(15)
FwEFFs
N(tainn)
((ee))
2 1 - 2.
812 + exp(
86. ))
follows the Bonferroni inequality that, Pr(n A.) A)) - Pr(Ai). where A, and its com-
plement À; are any events. Therefore, Pr hoo G (llin)))
Nunis ( r Ti-nort (eees W S <) s
19

---

Under review as a conference paper at ICLR 2021
) concluding the proof for unattributed graphs where C(:-)= 0 =0 as the null attribute, which is invariant to E by construction.
N 2exx=
Sk + exp(- ( 84s
attributed graphs similarly the graphon W unattributed graphs. We can consider the graph generation procedure as first generate the under- lying structure, and then add vertex attribute accordingly to its corresponding random graphon value (0, 1). -(:-)) being invariant to E and É means for any two environment e1 P(E), e2 P(E). C(e,,)) -) C(e2,)). The single-environment extrapolation focuses on when P(E) concen- trated on only one single value as defined in Definition
For attributed graphs, since C' operates
Then similar as the proof in Lovász & Szegedy 2006), we can define for given v-vertices attributed graph Fs and given N. define as injective map [A:] - [NC),, As denotes the event is a homomorphism from L's to the W-random graph 9 | V Fm W denotes the subgraph of G W induced by vertices
Σg Pr(Ag) mm (") martingale which justified in the proof of Lovász Szegedy (2006 Theorem 2.5) for unattributed graphs. And since the C' operates on attributed graphs similarly as the graphon W on unattributed graphs, it is also a martingale here. Then we can use Azuma's ' incquality to prove the exact same bounds as in Equation (3). We omitted this part since they are shown in the proof of Lovász & Szegedy (2006) Theorem 2.5).
m). Then it is easy
Bm
D BIASES INDUCED HOMOMORPHISM DENSITIES
Let Cea and Cs denote all possible connected k' k'-vertex graphs (1 S k' < k) and all possible con- nected k-vertex graphs respectively, C& is an arbitrary k-vertex connected graph. Induced homo- morphism densities over all possible k-vertex connected graph for n-vertex graph Gn, is defined as:
ind(Ck, G,,)
w(Ck, Gm) = Σorec. ind(Ck, Gn)
The .(;,)) and Fgg are replaced by -( and Csa in Equations in our experiments.
to (9) for graph representations
Achieving unbiased estimates for induced homomorphism densities usually requires sophisticated methods and enormous amount of time. We show that a biased estimator can also work for the GNN in Equation 9 if the bias is multiplicative and the READOUT function is simply the sum of the vertex embeddings. We formalize it as followed.
Proposition Assume (CCk, G,) is a biased estimator for wCCk, G.)) for any ie and k-sized con- nected graphs Cs in n-vertex Gn such that E(w(Cr. Gn)) B(Cx) (C Gn). where B(Cx) (3(.) > 0) is the bias related to the graph Cs, and the expectation is over the sampling procedure. The expected learned representation B(Ec G(Ck,,G,)T G.))1((CNN+ (C)))) can be the same as using the true induced homomorphism densities .(:,)).
Proof. If we can learn the representation GNN+ = GNN+ ((Ck)/B(Ck) for all C E Cck. and GNN+ is the representation we will learn from the true true induced homomorphism densities w. This is possible because GNN proven to be most expressive k-vertex graph represen- tation, thus it is able learn any function the graph Cg. Then
E
Σ CHrECSn
@(C G.. (CW)) (Cw)))
Σ CUECSE
w(Cw, (GN)"" ((Ck)))
where 1 TGNN (Cxr) )) is the sum of the vertex embeddings given by the GNN if it is an equiv- ariant representation of the graph.
E REVIEW OF GRAPH NEURAL NETWORKS
20

---

Under review as a conference paper at ICLR 2021
Graph Neural Networks (GNNs) constitute a popular class of methods for learning representations
of vertices in a graph or graph-wide representations (Kipf & Welling 2017| Atwood Towsley,
2016 Hamilton et al.
Gilmer et al. 2017 Velickovic et al. 2018 Xu et al., 2018a] Morris Liu et al. 2019 Chami et al. 2019). We will explain the general case applying GNNs to connected induced subgraphs in a larger graph to learn their latent representations. That is, in our work, we have applied GNNs connected induced subgraphs in a graph, and then aggregated them to obtain the representation of the graph. We briefly summarize the idea, but more details can be found in texts such as by |Hamilton (2020) and reviews by [Wu al. (2020) and Zhang et al. (2020) and the references therein.
2017
ef al.
2019 You et al. 2019
of learning graph-wide representations but the idea applies straightforwardly
Suppose we have a graph with vertex set V (1,2..... ".....,njj n). and each vertex in our data may earry some vertex feature (also called an attrihute). For instance, in molecule, vertices may represent atoms, edges may represent bonds, and features may indicate the atomic number (Duvenaud et al.) 2015). These vertex features can be stored in n X d matrix X, where d is the dimension of the of X, holds the attribute associated with vertex v.
vertex feature vector. In particular, row
Simply speaking, graph neural networks proceed by vertices passing messages, amongst each other, passing these through a learnable function such as an MLP, and repeating T E Z>1 times. At each iteration = 21,2,... ,,,..,T),,, T, all vertices u E V are associated with a learned vector (1) Specifically, begin by initializing vector as h X, for every vertex v E V. Then, we recursively compute an update such as the following
h (1) = MLP(1) (1) (t
Σ Σm HEATC))
Yu E
(16)
where (N)) C V denotes the neighborhood set of in the graph, MLP(0 denotes multi-layer perceptron, and whose superscript / indicates that the MLP at each recursion layer may have different learnable parameters. We can replace the summation with any permutation germutation-ivvariantt invariant function of the neighborhood. We see that GNNs recursively update vertex states with states from their neighbors and their state from the previous recursion layer. Additionally, we can sample from the neighborhood set rather than aggregating over every neighbor. Generally speaking there is much research into the variations of this recursion step and we refer the reader to aforementioned references for details.
To learn graph representation, we can aggregate the vertex representations using so-called READ- OUT function defined to permutation-invariann over the labels. A graph representation f by a GNN is thus
f(G) = READOUT (n))) (9) J Ju.Iev
where the vertex features h in Equation weights.
16 READOUT may may not contain learnable
The entire function is differentiable and can be learned end-to-end These models are thus typi- cally trained with variants of Stochastic Gradient Descent. In our work, we apply this scheme over connected induced subgraphs in the graph, making them differentiable module in end-to-end representation scheme.
F RELATED WORK
This section provides a more in-depth discussion placing our work in the context of existing litera- ture. We explain why existing state-of-the-art graph learning methods will struggle to extrapolate, subgraph methods, and explore perspectives of causality and extrapolation at large as well as in the context of graph classification.
Causal reasoning Counterfactual inference and invariances. Recent efforts have brought coun-
terfactual inference to machine learning models. Independence of causal mechanism (ICM) meth-
ods (Bengio et al. [2019] Besserve et al. 2018 Johansson et al., 2016 Louizos et al. 2017 Raj et al.
2020 Schölkopt 2019), Causal Discovery from Change (CDC) methods (Tian & Pearl 2001), and
representation disentanglement methods (Bengio al.
2019 Goudet et al. 2017 Locatello al.
21

---

Under review as a conference paper at ICLR 2021
Invariant risk minimization (IRM) (Arjovsky et al., 2019) is a type of ICM (Schölkopf) 2019 Broadly, these efforts look for representations (or mechanism descriptions) that are invariant across multiple environments observed in the training data. In our work, we are interested in techniques that can work with a single training environment -a common case in graph data, Moreover, these works not specifically designed for graphs, and it unclear how they can be efficiently adapted for graph tasks. To the best of our knowledge there is no clear effort for counterfactual graph extrapolations from a single environment.
2019).
Extrapolation There are other approaches for conferring models with extrapolation abilities. These ideas have started to permeate graph literature, which we touch on here, but remain outside the scope of our systematic counterfactual modeling framework.
Incorporating domain knowledge is an intuitive approach to learn a function that predicts adequately outside of the training distribution, data collection environment, and heuristic curation. This has been used, for example, in time series forecasting (Scott Armstrong & Collopy 1993] Armstrong et al. 2005). This can come in the form of re-expressing phenomena in way that can be adequately and accurately represented by machine learning methods (Lample & Charton| 2020) or specifically augmenting existing general-purpost methods to task (Kliepera et al. 2020). In the context of graphs, it has been used to pre-process, the graph input to make learned graph neural network model a less complex function and thus extend beyond training data (Xu et al. 2020 although this does not necessarily fall into the framework consider here.
Another way of moving beyond the training data is robustness. Relevant for deep learning systems adversarial attacks (Papernot al. (017). Neural networks be highly successful classifiers on the training data but become wildly inaccurate with small perturbations of those training exam- ples (Goodfellow et al., 2015). This is important, say, in self-driving cars (Sitawarin et al. 2018), which can become confused by graffiti. This becomes particularly problematic when we deploy systems to real-world environments outside the training data. Learning defend against adversar- ial attacks is in way related to performing well outside the environment and curation heuristics encountered in training. An interesting possibility for future work is to explore the relationships between the two approaches.
Overfitting will compromise even generalization (interpolation). Regularization schemes such as explicit penalization are a well known and broadly applicable strategy (Hastie et al.) 2012)). An- other implicit approach is data augmentation (Hernández-Garche & König 2018), and the recent GraphCrop method proposes a scheme for graphs that randomly extracts subgraphs from certain graphs in a minibatch during training (Wang et al. 2020b). These directions differ from our own in that we seek a formulation for extrapolation even when overfitting is not necessarily a problem but the two approaches are both useful in the toolbox of an analyst.
We would like to point out that representation learning on dynamic graphs (Kzzem et al. 2020). including tasks like link prediction on growing graphs (Anonymous) 2021 is a separate vein of work from what consider here. In these scenarios, there is direct expectation that the process model will change and evolve. For instance, knowledge bases a form of graph encoding facts and relationships- are inevitably incomplete (Sun al. 2018)). Simply put, developments in information and society move faster than they can be curated. Another important example is recommendation systems (Kumar al., 2019) based on evolving user-item networks. These concepts are related to the counterfactuals on graphs (Eckles et al., (0166) that we discuss. This is fundamentally different from our work where we do graph-wide learning and representation of a dataset of many graphs rather than one constantly evolving graph.
Subraph methods and Graphlet Counting Kernels A foundational principle here is that exploit- ing subgraphs confers graph classifications models with both the ability to fit the training data and extrapolate to graphs generated from a different environment. As detailed in Section 3.2 this insight follows from the Aldous-Hoover Hoover representation exchangeable distributions over graphs (Hoover,
1979 Aldous 1981 Kallenberg 2006 Orbanz & Roy (014) and work on graph limits (Lovász
2012
We discuss the large literature using subgraphs in machine learning.
Counting kernels (Shervashidze et al., 2009) measure the similarity between two graphs by the dot product of their normalized counts of connected induced subgraphs (graphlet). This can be used for classification via kernelized methods like Support Vector Machines (SVM).
22

---

Under review as a conference paper at ICLR 2021
Yanardag & Vishwanathan (2015) argue that the dot product does not capture dependence between subgraphs and extend to a general bilinear form over a learned similarity matrix. These approaches related to the Reconstruction Conjecture, which posits graphs can be determined through knowl- edge of their subgraphs (Kelly et al.
1957 Ulam, 1960 Hemminger 1969 McKay 1997). It is
known that computing maximally expressive graph kernel, or one that is injective over the class of graphs, is as hard as the Graph Isomorphism problem, and thus intractable in general (Gärtner et al.) 2003 Kriege al., 2020). Kriege et al. (2018) demonstrate graph properties that subgraph count- ing kernels fail to capture and propose a method to make them more expressive, but only for graphs without vertex attributes. Most applications of graphlet counting do not exploit vertex attributes, and even those that do (e.g. (Wale et al.) 20088) are likely to fail under a distribution shift over attributes; recording count for each type of attributed subgraph (e.g. red clique, blue clique) is sensitive to distribution shift. In comparison, our use of Relational Pooling Graph Neural Networks confers our framework with the ability learn a compressed representation of different attributed subgraphs, tailored for the task, and extrapolate even under attribute shift. We demonstrate this in synthetic experiments below. Last, a recent work of Ye et al.] (2020) propose to pass the attributed subgraph counts to downstream neural network model to better compress and represent the high dimensional feature space. However, with extreme attribute shift, it may be that the downstream layers did not see certain attributed subgraph types in training enough to learn how correctly represent them. We feel that it is better to compress the attributed signal in the process of representing the graph to handle these vertex features, the approach we take here.
There are many graph kernel methods that do not leverage subgraph counts but other features to measure graph similarity, such as the count of matching walks, c.g. (Kashima et al. 2003 Borgwardi et al. 2005 Borgwardt & Kriegel 2005). The WL Kernel uses the WL algorithm to compare graphs (Shervashidze et al. [201] 1) and will inherit the limitations of WL. GNNs like inability to represent cycles. RRick et al. 2019) propose persistent WL kernel that uses ideas from Topological Data Analysis (Munch) (017) to better capture such structures when comparing graphs. Methods that do not count subgraphs will not inherit properties regarding a graph- environment change from our analysis of asymptotic graph theory - but all extrapolation tasks require an assumption and our framework under different scenarios. Those relying on attributes to build similarities are also likely to suffer from attribute shift.
be applied studying the ability of various kernel methods to extrapolate
Subgraphs are studied to understand underlying mechanisms of graphs like gene regulatory net- works, food webs, and the vulnerability of networks to attack, and sometimes used prognosti- cally. A popular example investigates motifs, subgraphs that appear more frequently than under
chance (Stone& & Roberts 1992, Shen-Orr et al. 2002 Milo et al. 2002 Mangan Alon 2003 Sporns & Kötter 2004| Bascompte & Mclián 2005 Alon 2007 Chen et al. 2013 Benson et al. 2016 [tone et al. 2019: Dey et al. [019)] Wang et al., (020a)). Although the study of motif's is along different direction and often focus on one-graph datasets, our framework learns rich latent
representations of subgraphs; interesting future work could include leveraging our learned 7 func- tions (pre-trained) and estimated counts to glean scientific understanding. Another line of work uses subgraph counts as graph similarity measures, an example being matching real-world graphs to their most similar random graph generation models (Pržulj 2007).
Other machine learning methods based on subgraphs have also been proposed. Methods like MGCMN (Li et al., 2020), HONE (Rossi et al. 2018), and MCN (Lee et al. (018)) learn representa- tions for vertices by extending classical methods over edges to new neighborhood structure based on subgraphs; for instance, mGCMN runs GNN on the new graph. These methods do not exploit all subgraphs of size i and will not learn subgraph representations in manner consistent with our extrapolation framework. Teru et al.) (2020) use subgraphs around vertices to predict missing facts in a knowledge base. Further examples include the Subgraph Prediction Neural network (Meng et al., 2018) that predicts subgraph classes in one dynamic heterogeneous graph; counting the appearance of edges in each type of subgraph for link prediction tasks (AbuOda et al. 2019): and SEAL(Zhang & Chen 2018) runs GNN over subgraphs extracted around candidate edges predict whether an edge exists. While these methods exploit small subgraphs for their effective balance between rich graph information and computational tractability, they are along an orthogonal thread of work.
Graph Neural Networks Among the many approaches for graph representation learning and clas- sification, which include methods for vertex embeddings that are subsequently read-out into graph
23

---

Under review as a conference paper at ICLR 2021
representations (Belkin & Niyogi 2002;
Perozzi et al. 20014 Niepert et al., 2016 Ou et al. 2016
Kipf & Welling 2016 Grover & Leskoved 2016 Yu et al.
2018; QQu et al. 2018 Maron et al. focused our discussion and mod- cling of f on graph neural network methods (Kipf & Welling 2017 Atwood & Towsley, 2016
2019b at Wu et al. 2020 Hamilton 2020; Chami al. (2020)
Hamilton et al., 2017; Gilmer et al., 20177 Velickovic et al., 2018: Xu et 20188| Morris et al.
2019 You et al., 2019 Liu et al. 2019 Chami et al. 2019). GNNs are trained end-to-end, can straightforwardly provide latent subgraph representations, easily handle vertex/edge attributes, are computationally efficient, and constitute a state-of-the-ar method. However, GNNs lack extrapo- lation capabilities due to their inability to learn latent representations that capture the topological structure of the graph (Xu et al., 2018a, Morris ct al., 2019) Garg et al., 2020; Sato 2020). Rele- vantly, many cannot count the number of subgraphs such as triangles (3-cliques) in graph (Arvind) cct al. 2020 Chen et al. 2020 In general, our theory of extrapolating in graph tasks requires prop- erly capturing graph structure. Moreover, if GNNs cannot exploit structure in subgraphs they may be distracted by vertex features and fail to extrapolate under attribute shift, as demonstrated in our experiments. Relational Pooling (Murphy al.) 2019) and rGIN (Sato et al.) 2020) employ random features as a straightforward way to overcome this limitation; whereas rGIN does not respect iso- morphic invariance of graphs. we compare against RP-GNN. There. we show that sfte-of-theear GIN (Xu et al. 201 and RP-GIN (Murphy et al. 2019) are expressive in-distribution but fail to extrapolate.
Teru et al. (2020) use subgraphs around vertices to predict missing facts in knowledge base. Further examples include Meng al.) (2018) that predicts subgraph classes in one dynamic heterogeneous graph; counting the appearance of edges in each type of subgraph for link prediction tasks (AbuOda al. 2019); and SEAL (Zhan Chen 2018) runs GNN over subgraphs extracted around candi- date edges to predict whether edge exists. While these methods exploit small subgraphs for their effective balance between rich graph information and computational tractability.
G EXPERIMENTS
In this appendix we present the details the experimental section, discussing the hyperparameters that have been tuned. Note that the search space has been chosen that all the biggest models have a comparable number parameters.
G.1 MODEL IMPLEMENTATION
All neural network approaches, including the models proposed in this paper, are implemented in PyTorch (Paszke et al. 2019).
Our GIN (Xu et al. 20) implementation based on the implementation available in Pytorch Geometric (Fey & Lenssen 2019). For RPGIN (Murphy et al. 2019), we implement the permutation and concatenation with ooe-hot identifiers and use GIN as before. To use GIN on unattributed graphs, we follow convention and assign '1" dummy feature every vertex. For RPGIN, we assign one-hot identifiers with dimension 10. In the attributed case, GIN simply uses the vertex attributes whereas RPGIN appends one-hot identifiers to the attributes. GIN and RPGIN serve both g as baselines and as architectural building-blocks of I GIN and reea () for learning latent vectors of connected induced subgraphs. Other than a few hyperparameters and architectural choices, we use standard choices (c.g. Hu et al. (2020).
RPGIN
We use the WL graph kernel implementations provided by the graphkernels package (Sugiyama al. 2017). All kernel methods use a Support Vector Machine on scikit-learn (Pedregosa et al.) 2011
The graphlet counting kernel, well as our own procedure, relies on being able efficiently count attributed or unattributed connected induced subgraphs. We made use of ESCAPE (Pinar et al. 2017) and R-GPM (Teixeira al. 2018) as described in the main text. The source code of ESCAPE available online and the authors of Teixeira et al. (2018) provided us their code.
Our models (I D. r 0 pfe g
1-hot GIN R were implemented using PyTorch Geometric (Fey & Lenssen 2019). As discussed in the main text, the choice subgraph size k is very important hyperparam- eter for method, trading off computation, expressive power, and in way that depends on the
24

---

Under review as a conference paper at ICLR 2021
characteristics of the graphs hand. We discuss our choice of k in each of the tasks below, and the same samplers as above to obtain exact or estimated induced subgraph densities.
These models learn graph representations I(G)), which pass to downstream layers in end-to- r g GIN and RPGIN- we use GIN and RPGIN respectively to obtain latent vectors for end fashion. For
I reeq X
each k-sized Connected Induced Subgraph (CIS) and then sum over the latent CIS representations, each weighted by its corresponding induced homomorphism density. In Appendix G.5]
we use an attention mechanism in the sum. For 1 1--oor the representation I i is a vector containing den- sities of each (possibly attributed) CIS pattern. To map this into graph representation, we compute T--oo (G) W where W is learnable weight matrix whose rows are subgraph representations. Note that this effectively learns a unique weight vector for each CIS pattern.
(2)
The methods GIN, RPGIN, r I p Pl and 1 1.hor vector for each graph. In each case, we use linear layer on the graph representation to obtain the prediction. To optimize the neural models, we use Adam optimizer. When an in-distribution valida- tion set is available (see below), we use the weights that achieve best validation-set peridtion-eepeeffrmmaacc prediction. Otherwise, we train for a fixed number epochs.
7 all produce latent graph representation
RPGIN
performance for
The specifics of hyperparameter grids and downstream architectures are discussed in each section below.
G.2 SCHIZOPHRENIA TASK: SIZE EXTRAPOLATION
These data were provided by the gracious authors of De Domenico et al. (2016), which they pre- processed from publicly available data from The Center for Biomedical Research Excellence There are 145 graphs which represent the functional connectivity brain networks of schizophrenic patients and 74 healthy controls. Each graph has 264 vertices representing spherical regions of in- terest (ROIs). Edges represent functional connectivity. Originally, edges reflected a time-series coherence between regions. If the coherence between signals from two regions was above a certain threshold, the authors created weighted edge. Otherwise, there is no edge. For simplicity, we converted these to un- un-weighted edges. A key motivation of this paper shares our own. Extensive pre-processing must be done over fMRI data to create brain graphs. This includes discarding signals from certain ROIs. As described by the authors, these choices make highly significant impacts on the resulting graph. We refer the reader to the paper (De Domenico et al., 2016). It is interesting to note that there are numerous methods for constructing a brain graph, and in ways that change the number of vertices. The measurement strategy taken by the lab can result in measuring about 500 ROIs, 1000 ROIs, or 264 as in the case of this paper (Hagmann et al. 2007 Wedeen et al.) 2005 De Domenico al. 2016).
For our purposes, we wish to create an extrapolation task where a change in environment leads to an extrapolation set that contains smaller graphs. We randomly select 20 of the 145 graphs, balanced among the healthy and schizophrenic patients, and we reduce the size of the control-group graphs by removing vertices uniformly random. Ultimately these graphs have on average 40% fewer vertices. This forms our extrapolation-test set.
We hold out the extrapolation-test. Over the remaining data, we use 5-fold cross-validation as- sess interpolation-test accuracy and for hyperparameter tuning. Each of the validation-set folds can be used as interpolation-tes sets. We averaged over the validation fold performance of the best- performing hyperparameter configuration and report the mean (standard deviation) as interpolation- test performance. Note that we use stratified sampling within the cross validation folds.
1 [-hoo and the graphlet [4, 5). Finally, in this section, all GIN modules use the Jumping Knowledge mechanism (Xu et al. 2018b).
Recall that we must obtain homomorphism densities for feg. Keg, counting kernel. We use ESCAPE, to and tune the size in
GIN
RPGIN.
For P and po RPCIN= we tune the network width (of the aggregation MLP) in {32, 64, 128, 256} and the number of layers (i.e. recursions of message-passing) in {1,2), the learning rate in {0.001, 0.0001), the batch size in {32, 64, full-train-size),
25

---

Under review as a conference paper at ICLR 2021
For I recall that we learn unique weight vector for each CIS type; tune the dimension of this vector in (32, 64, 128, 256). We tune the learning rate in {0.001, 0.0001), and the batch size in (32, 64, full-train].
For the baseline classifiers GIN and RPGIN, we tune the learning rate in {0.01, 0.001), the network width in {32, 64, 128, 256), the number of layers in 21, 3, 4), and the batch size in f32, full-train). For inference, we average over four permutations as described in (Murphy et al. 2019)).
We train all neural models for 400 epochs. Once the best hyperparameter configuration is obtained through cross-validatin on the training data with full-sized graphs, we re-train the model on the entire train split before predicting on the extrapolation set where the healthy graphs are smaller. We repeat the training with 10 different initialization seeds, and we report the mean and the standard deviation.
For the graph kernels, following Kriege et al. (020)), we tune the regularization hyperparameter C in SVM over the range from 10 to 10" with steps of 10. We tune the number of iterations for WL kernel in
G.3 ERDÖS- -ÉNYI CONNECTION PROBABILITY: SIZE EXTRAPOLATION
We simulated Frdös-Rényi graphs (Gnp model) using Network (Hagberg et al. 2008 The graphs
in training and interpolation-test varies from (20. 80), while extrapolation- test graphs vary from {140,... 200), selected uniformly at random. Here, the training, in-environment interpolation-tes! and extrapolation-test sets are fixed. They are of sizes 80, 40, and 100 respectively.
Recall that must obtain homomorphism densities for pls R GIN
(eg P
teg
and the graphlet I-hot
RPGIN
counting kernel. We use ESCAPE for fixed size k = 5.
For raN and pley RPCIN' we tune the network width of the aggregator MLP in {16, 32, 64, 128, 256 the number of layers (i.e. recursions of message passing) in {1,2), and the learning rate in {0.1, 0.01, 0.001}.
S
For I I hot recall that we learn unique weight vector for each CIS type; we tune the dimension of this vector in {16, 32, 64, 128, 256} and the learning rate {0.1, 0.01, 0.0013.
For the baseline classifiers GIN and RPGIN, we tune the network width of the MLP aggregator in {32, 64, 128, 256). the number of layers (i.e. message passing recursions) in (1,2,3), and the learning rate in {0.1, 0.01, 0.001 J. We also tune the presence or absence of the Jumping Knowledge mechanism from Xu et al. (2018b).
We train all neural models for 500 epochs. Whenever evaluate model performance, do so using the estimated weights from the epoch that attained the best performance on the interpolation- test (i.e. validation) set. We select the hyperparameter configuration that achieved the highest mean accuracy on the interpolation-tes. averaged across 10 different random weight initializations. We report the score from the best hyperparameter configuration as interpolation-tes performance; we do so for all neural methods. To report training and extrapolation-tee set performance, we train the model with best hyperparameter configuration, again using the interpolation-test (validation) set to find the epoch at which to use weights, and predict over both sets. This is also repeated for 10 random initializations.
For the graph kernels, following Kriege et al. (220). we tune the regularization hyperparameter C in SVM from 10-3 10a with steps of 10 and the number of iterations for WI. kernel in (2,3).
G.4 EXTRAPOLATION PERFORMANCE OVER SBM ATTRIBUTED GRAPHS
We simulated Stochastic Block Model graphs (SBM) using NetworkX (Hagberg et al. 2008). Each graph has two blocks, having a within-block edge probability of Pt, = P2.2 = 0.2. The cross-block edge probability is P1,2 Pt. E {0.1, 0.3). and constitutes the target. Vertex color distribution changes with environment. training, vertices in the first block are either red or blue, with a prob- ability distribution of (0.9. 0.1} respectively, while vertices in the second block are either green or yellow, with a probability distribution of (0.9, 0.1} respectively. In test, the probability are re- versed: vertices in the first block are either red or blue, with probability distribution of (..1
26

---

Under review as a conference paper at ICLR 2021
Table 3: Average (standard deviation) number of five cliques with varying colorations in graph across training, interpolation test and extrapolation test. The target is the number of 5-cliques with- any green vertices, the sum of the clique-types indicated in the first two row headings.
Train
Interpolation Test
Extrapolation Test
No green, or red No green, less than 4 red At least one green Total number of 5-cliques
8.55 (10.87)
10.35 (11.82)
3.10 (6.50)
2.02 (3.11)
1.35 (3.05)
8.56 (9.66)
6.79 (8.60)
9.05 (11.06)
7.68 (11.94)
17.36 (13.68)
20.95 (13.96)
19.35 (17.07)
respectively, and vertices in the second block are green or yellow with probability distribution of {0.1, respectively. Training, in-environment interpolation-tes. and extrapolation-tes sets are of sizes 80, 20, and 100 respectively.
To obtain the homomorphism densities for Tice Tlg
1-hot and the graphlet counting kernel, we use R-GPM for a fixed size h = 5. We compute the induced homomorphism counts (from which derive the densities) using 100 different seeds, and epochs.
T (oq
RPCIN
the different samples in different
For ten E and I deg RPGIN we tune the network width of the aggregator MLP in {16, 32, 64, 128, 256), the number of layers (i.e. recursions of message passing) in {1,2), and the learning rate in {0.01, 0.001
For I plog D tune the dimension of this vector in {8, 16, 32, 64) and the learning rate in H-oor {0.01, 0.0013.
For the baseline classifiers GIN and RPGIN, we tune the network width of the MLP aggregator in (32, 64, 128, 256), } the number of layers (i.e. message passing recursions) in {1,2. 3), and the learning in {0.01, 0.001). We also tune the presence or absence of the Jumping Knowledge mechanism from Xu et (2018b).
We train all neural models for 400 epochs. Whenever evaluate model performance, do so using the estimated weights from the epoch that attained the best performance on the interpolation- test (i.e. validation) set. We select the hyperparameter configuration that achieved the highest mean accuracy on the interpolation-test, averaged across 10 different random weight initializations. We report the score from the best hyperparameter configuration as interpolation- performance; we do so for all neural methods. To report training and extrapolation-tes test set performance, we train the model with best hyperparameter configuration, again using the interpolation-6s (validation) set to find the epoch at which to use weights, and predict over both sets. This is also repeated for 10 random initializations.
For the graph kernels, following Kriege et al. (020). tune the regularization hyperparameter C in SVM from 10-3 to 10t with steps of 10 and the number of iterations for WL kernel {1, 2,
G.5 EXTRAPOLATION PERFORMANCE OVER ATTRIBUTED GRAPHS
Next we try a significantly more challenging scenario, with conditions that clearly violate Theo- rem 7 This experiment involves vertex attributes. To simulate graphs, we first randomly create an unattributed graph (i.e. simulate a graph of some topology), and then add vertex attributes. The graph structure is sampled from a Erdós-Rényi Rényi (Gnp) model whose number of vertices is selected uniformly random from {20, 22. ... 25}. Since our task involves counting 5-cliques (those that have green vertices), we were careful to specify edge-creation probability that would cre- particular, after sampling graph size, we compute the
ate a meaningful number of 5-cliques. edge probability such that the expected proportion of 5-cliques is 0.8. For example, the expected number of 5-cliques is 16 for a graph size 20.
The vertices have a one attribute: either red, green, blue, which is one hot-encoded. We induce an attribute-shin environment change: for training and interpolation testt, the 5-cliques are predomi- nantly red whereas in extrapolation-test. the coloration of 5-cliques is more 'uniform'. The empirical distributions of 5-cliuue coloration is shown in Table 3 By 'uniform', we do not indicate that the proportion of the types of 5-cliques shown in the extrapolation-test column is uniform. We mean that
27

---

Under review as a conference paper at ICLR 2021
Extrapolation performance attributed graphs shows clear advantage of environment- invariant methods that use GNNs. We count # #{S-lliques with green vertices). Vertex color distribution changes with environment. Table shows Mean Absolute Error (MAF) over interpolation environment (train & test) and extrapolation test. Results show mean (standard deviation) MAE.
Table 4:
Interpolation Train MAE
Interpolation Test MAE
Extrapolation Test MAE (
Prodict train target meerag
8.46
9677 (0.00)
8.88 (0.00)
3,20 (0
(0.64)
RPGIN
3.00 (0.73)
2.96 (0.30)
6.90 (0.73)
W1. Komel
6.31 (0.00)
7.11 (0.00)
8.52 (0.00)
GC Kernel (attributed)
4.46 (0.00)
(0.6()
7.36 (0.00)
GC Kernel (attributed unsstributed)
3.81
5.17 (0.00)
(0.00)
Ticms
1.78 (0.60)
3,31 (0.17)
6.17 (0.87)
Tor (m
1.12
1997 (0.80)
3.92 (0.95)
TRAGS 64
1.57
(0.35)
(0.65)
the coloration is less dominated by mostly-red 5-cliques. The idea behind this task is that it is very challenging in that the target is highly correlated with 'number of mostly-red cliques'. Mostly need to avoid learning predict the number of red 5-cliques (if they can count substructures effectively, unlike the WL and GNN methods), and avoid learning some function of the number of red vertices.
Train, Interpolation Test and Extrapolation Test sets fixed and each respectively contain 80, 20, and 100 graphs.
As these attributed graphs, estimate the CIS counts with R-GPM discussed in the main text. We fixed the subgraph size to k = 5. A round of sampling is run for every epoch that we use in training to ensure unbiased estimation.
RPGIN- we use GIN with no jumping knowledge to obtain the CIS representations. Then, a graph representation is constructed by employing the attention mechanism proposed in llse al. on the CIS representations concatenated to their densities. We tune the width of the MLP in the aggregator in {16, 32, 64, 128, 256). the number of layers (i.e. message passing recursions) in (1,2), and the learning rate {0.01, 0.001}.
T For GIN and rlea g)
For (eq. 1-hot recall that we learn a unique weight vector for each CIS type; we tune the dimension of this vector in {8, 16, 32} and the number of layers in {1, To avoid overfitting due to the large number of distinct attributed CISs which translates in large number of parameters, we used an 12 regularization of 0.1.
For standard GIN and RPGIN, we tune the network width of the MLP aggregator in {32, 64, 128, 256). the number of layers (i.e. message passing recursions) in 21, the learn- ing rate in {0.01, 0.001} } and dropout in (0.0, 0.1},
The models are trained for 400 epochs. The hyperparameter tuning and evaluation scheme are similar that of Appendix G.3
For the graph kernels, following Kriege et al. 2020). we tune the regularization hyperparameter in SVM from 10-3 to 10d with steps of TO and the number of iterations for WL. kernel in (2,3).
Table shows the Mean Absolute Error (MAE) results. We include a train target average predictor to provide a reference for bad MAE. The results show that interpolation representations and TT 1-oo (GC Kernel and new classifier) get distracted by the easy relationship between Y and the density of red cliques, while I' GIN and I' RPRGIN are significantly more robust, giving similar GNN representations to red and blue cliques. TIIN and I RPGINN show a gap between interpolation and extrapolation test errors, likely reflecting the deviation in Theorem conditions.
H EDGE ATTRIBUTES
To the best of our knowledge, algorithms that estimates the densities of connected induced sub- graphs handles edge attributes due to the lack of canonical labeling algorithms that consider them. To fill the gap, we propose to modify the canonical labeling algorithms used in the sampling al- gorithms. Our idea generalizes the method proposed in McKay & Piperno 2014)., and consists of transforming graph with edge and vertex attributes into larger graph with only vertex attributes that can then be used in the canonical labeling. If the edge attributes are integers in 21,,....7 .,....,,-1)) 2d-1), the transformed graph will have d layers, each with the original number of vertices. The binary
28

---

Under review as a conference paper at ICLR 2021
pansion of each color number tells which layers contain edges with that colors. The new attribute for each vertex is an hash of its original attribute and the layer number.
29


Reviews:
[{"review_id": "ySpcK1G8eQo", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper explores the problem of extrapolation in graph classification tasks and by leveraging Lovasz’s graph limit theory, provides graph representations and related theoretical guarantees on graph size extrapolation in the context of unattributed graphs. Specifically, it is shown that the graph representations characterized by induced homomorphism densities are size-invariant under certain conditions. The theoretical claims are validated by empirical evaluation of classifiers trained on the proposed graph representations. \n\nOverall, I find the contributions of the paper solid and of interest to many researchers. \n\nPros: The paper is well written with an appropriate focus on motivating the problem at hand. The experiments seem convincing enough to establish the implications of theoretical guarantees. \n\nCons: I don't see any major issues in the paper. \n\nElaborating on a few points will help improve the readability:\n\n1. I recommend elaborating on the graphon function $W'$ defined in Theorem 1 and its relation to graph topology. \n\n2. Are the conditions of Theorem 1 violated by any large class of graph models, such as MRFs?\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "kYv-z7ZEUQ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Below constitutes the Official Review for Paper2605.\n\nSummary of the paper:\n\nThis paper explores the problem of constructing invariant representations to certain new environments. Specifically, they constrain the problem to a so-called single-environment graph classification or regression task. Authors define a notion of counterfactual coupling, and consider a notion of invariance different from (though not well-justified) the standard literature. Based on the authors' own definition, they consider a few example tasks on random graphs. Under strong assumptions, authors show a couple generalization error bounds. Their bounds appear to be algorithm agnostic and do not take into account the neural network or optimizer properties. On the modeling side, authors propose a model: the model is to simply replace a one-hot vector with a GNN. Small-scale experiments are conducted on two toy datasets to show the proposed model slightly improves four vanilla baselines, on these two toy datasets.\n\nEvaluation:\n\nWhile it is clear that papers like Paper2605 have much to offer, the official recommendation is rejection. \n\nOverall, it is unclear what contribution this paper has. The problem setting is contrived, over-complicated, and not well-defined. It is hard for one to find the theorems meaningful: they assume strong assumptions and contrived settings, and are not applicable to real problems. What conclusion one can draw from the theorems are also quite unclear. The technical proofs are unimpressive either as they appear to be maneuvering the already contrived definitions with basic inequalities. \n\nThe proposed model is unclear, unmotivated, and has logical gaps.  No clear algorithm process or code is given. Reproducibility is impossible. No motivation or theoretical guarantee is given, neither were we given evidence how it may compare to other invariant/causal models such as IRM or domain adaptation techniques.\n\nBecause the theoretical and modeling contributions were unclear, one would expect to see strong experimental results. Yet, the experiments are particularly unconvincing, in that the proposed one had only been evaluated on two toy datasets,  and compared to four baselines. State-of-the-art models such as IRM, REx, domain invariant models are are missing from the comparison. Putting aside the unconvincing execution,  the experiments do not seem to corroborate the theorems (which are ambiguous and unclear anyways) either, making the theoretical/modeling contribution even weaker and more unclear. \n\nAdditionally, one must complain about the poor writing. This paper suffers from the lack of logic and mathematical rigor; it is full of jargons that are unexplained and undefined. For example, after reading the entire paper, one still can't find a definition of GNN or GNN+, which constitute the main part of the proposed model. It is impossible to imagine the ICLR community will appreciate this paper. Based on the evaluation, a rejection is recommended. \n\n$\\textbf{Unclear contribution and contrived/trivial theorems}$ \n\nOne cannot draw any clear conclusion from the theorems. Problem setting and theorems are contrived, over-complicated and not rigorously defined. The technical proofs are unimpressive either as they appear to be maneuvering the already contrived definitions with basic inequalities. \n\n''Definition 1 (Counterfactual coupling (CFC)).'' This definition is simply confusing and contrived. How can you even evaluate over all permutations? This is NP-hard?  The independence assumption is also strong? How is this different from standard definitions? Never explained?\n\n''Proposition 1. Let P(Y |G(obs) N(obs) = G (obs) n(obs)) and P(Y |G(cf) N(cf) = G (cf) n(cf)) be the conditional target distributions ''  Proposition 1 seems to be only stating definitions (generalization error etc), how is this even a proposition? \n\n''Proposition 1. a link function ρ(·, ·) such that'' link function p is never defined. \n\n''assume Y ∈ Y is discrete'' What about regression?\n\n\n'E ∈ Z+ that describes the graph-processing environment''.  Graph-processing environment is never defined. What is that?\n\n''supervised task over a graph input Gn(n ≥ 2) and its corresponding output Y''. Problem is undefined. What is graph classification or regression?  Is the response variable over graph, edge, vertex? Is input one graph or many graphs?\n\n'' Consider a permutation-invariant graph representation Γ : ∪∞ n=1Ω n×n → R d''  How is this even possible?  Permutation-invariant graph representation is such a strong assumption?\n\n''Proposition 1 shows that an E-invariant representation will perform no worse on the counterfactual\ntest data (extrapolation samples from (Y, G (cf) N(cf))) than on a test dataset having the same environment distribution as the training data (samples from (Y, G (obs) N(obs))).''  Well, this is apparently wrong? Evidence? \n\n''Other notions of E-invariant representations are possible (Arjovsky et al., 2019; Scholkopf, 2019), but ours —through coupling— provides a direct relationship with how we learn graph representations from a single training environment.''  Not convincing? Evidence? Well, Arjovsky et al., 2019; Scholkopf, 2019 can be applied to graphs too? You are also missing a great amount of literature on invariant models and domain adaptation techniques.\n\n''Theorem 1. Assume our graph-processing heuristic'' What does graph-processing heuristic even mean?\n\n''Theorem1.   the outputs of ge1 and ge2 of Equation (1) can only differ in their attributes ∀e1, e2'' What does this even mean? Seems too contrived?\n\n''Theorem 1. Deleting a random vertex n from G (obs)n |W, and the distribution of the trimmed graph is the same as the distribution of G (obs)n−1|W, with G (obs) 1|W as a trivial graph with a single vertex for all W'' Over-complicated?\n\n''For every 1 < k < n, the subgraphs of G (obs) n |W induced by {1, . . . , k} and {k + 1, . . . , n} are independent random variables'' Why does this hold? Evidence?\n\n''Then, the variable W can be equivalently defined as W = (W0, C0E), where W0 is a random variable defined over the family of symmetric measurable functions W0\n: [0, 1]2 → [0, 1], i.e., W0 is a random graphon function, and, if the graph has attributes, C0 E is an environment-dependent random\nvariable that defines vertex and edge attributes, otherwise, C0E = Ø is defined as the constant null.'' Unclear what conclusion one can draw from Theorem. Doesn't seem to have useful implications. \n\n''It is possible to guarantee that a graph representation is E-invariant even when the training data contains just one environment.'' This reads apparently wrong? Evidence? \n\n''inj(F, G) be the number of injective homomorphisms of F into a larger unattributed graph G'' Expensive to evaluate? Justification?\n\n''1one-hot{Fk0 , F≤k} be the one-hot vector with a one at the index of Fk0 in F≤k and zeros elsewhere'' How do you construct this? Not well motivated? \n\n$\\textbf{Trivial and unmotivated modeling}$\n\nThe proposed method (Section 3.2) is not well-motivated and is ambiguous. No clear algorithm is described either, making it impossible to reproduce.\n\n''Hence, our proposal replaces the one-hot vector 1one-hot{Fk0 , F≤k} with a GNN applied to Fk0 : ''  What is this one-hot vector? What is GNN? Never defined? Replacing one hot by GNN seems trivial? \n\n''ta-inj(Fk0 , Gn)'' Not well-defined? Algorithm to compute this?\n\n''Unfortunately, GNNs are not most-expressive representations of graphs (Morris et al., 2019; Murphy et al., 2019b; Xu et al., 2018a) and thus ΓGNN(·) is less expressive than Γ1-hot(·) for unattributed graphs.'' What does this even mean? Then why do you use GNN (which is not defined anyways)?\n\n\n$\\textbf{Unconvincing experiments}$\n\nThe proposed model is only evaluated on two toy datasets.\n\nA large amount of baselines on invariant models, causal models, domain adaptation techniques are missing. Just to name a few,\n\nhttps://arxiv.org/abs/1907.02893\n\nhttps://arxiv.org/abs/2003.00688\n\nhttps://arxiv.org/abs/2002.04692\n\nhttps://arxiv.org/abs/1505.07818\n\nhttps://arxiv.org/abs/1911.00804\n\nhttps://arxiv.org/abs/2006.07500\n\nhttps://arxiv.org/abs/2010.07922v1\n\n\nThe proposed model only slightly improves upon four basic baselines on the toy datasets. \n\nThe experiments do not corroborate the theorems (which are inconclusive anyways). \n\n\n$\\textbf{Poor writing and mathematical rigor}$\n\nThe paper is full of jargons that are unexplained and undefined.  Many claims are stated without evidence.\n\n''graphs are simply representations of a natural process rather than the true state''. What does this even mean? Evidence?\n\n'E ∈ Z+ that describes the graph-processing environment''.  Graph-processing environment is never defined. What is that?\n\n''supervised task over a graph input Gn(n ≥ 2) and its corresponding output Y''. Problem is undefined. What is graph classification or regression?  Is the response variable over graph, edge, vertex? Is input one graph or many graphs?\n\n''graph generation function g : Z+ × D × D → Ω n×n'' D is never defined. What is D?\n\n''in some canonical order'' what is the canonical order?\n\n''graphs are simple, meaning all pairs of vertices have at most one edge'' This is a wrong definition of simple graphs?\n\n''Erdos-Renyi example (part 1)''  The problem setting is described by an example. A rigorous definition of problem setting is expected. \n\n''Figure 1: (a) The DAG of the structural causal model (SCM) of our graph extrapolation tasks where hashed (white) vertices'' Hashed (white) vertices do not exist in Figure 1 (a)? What is sampled permutation?\n\n''Illustrates the relationship between expressive model families and most-expressive extrapolation families'' How is this even related?\n\nSCM is never defined? While I know what a SCM is, this presents yet another example of poor writing.\n\n''Single-environment graph extrapolation task''. What does this even mean?  Can you formally define it? Isn't the paper studying invariant models?  https://en.wikipedia.org/wiki/Extrapolation  extrapolation is used in a confusing way, different from wikipedia? \n\n''the value Y = W in Equation (3), which is also the edge probability p'' Well, isn't this too contrived?\n\n''Hence, traditional (interpolation) methods can pick-up this correlation, which prevents the learnt model from extrapolating over environments different than the. ones provided in the training data (or even over different P(E) distributions).'' Well, this is not your contribution, so you need to properly add citation.\n\n''we need a backdoor adjustment'' What is backdoor adjustment? Undefined? Well, although I know what it is, it shows yet another example of lack of mathematical rigor.\n\n''Definition 1 (Counterfactual coupling (CFC)).'' This definition is simply confusing and contrived. How can you even evaluate over all permutations? This is NP-hard?  The independence assumption is also strong? How is this different from standard definitions? Never explained?  \n\n''Proposition 1. Let P(Y |G(obs)\nN(obs) = G\n(obs)\nn(obs)) and P(Y |G(cf)\nN(cf) = G\n(cf)\nn(cf)) be the conditional target distributions ''  Proposition 1 seems to be only stating definitions, how is this a proposition? What do you even mean?  \n\n''Proposition 1. a link function ρ(·, ·) such that'' link function p is never defined?\n\n''Theorem 1. Assume our graph-processing heuristic'' What does graph-processing heuristic even mean?\n\n'' the outputs of ge1 and ge2 of Equation (1) can only differ in their attributes ∀e1, e2'' What does this even mean? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "fVwoKer8rRp", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper formulates a theoretical model for testing extrapolation abilities of graph learning tasks, and suggests some practical feature maps to achieve good extrapolation properties empirically. In more detail, this paper introduces a model, a so-called structural causal model, for graphs where the graph creation process is modeled as a random variable that depends on different independent factors:  environment $E$, which is used to model the graph size $n$; graph property $W$, which is used for example to model the probability of edge existence; and random seed $Z_X$. The created graph is also scrambled by a random permutation to yield the observed graph $G^{\\text{obs}}$. The ground truth labels of the graph $Y$ are functions of two factors $W$, the graph property, and $Z_Y$ random seed. \n\nThe authors claim that a problem with learning data of the form $(G^{\\text{obs}},Y)$ is that $Y$ is not independent of $E$ given that we see $G^{\\text{obs}}$ and therefore standard learning techniques can overfit certain environments and fail to extrapolate. These dependencies are referred to as backdoor paths. Then the authors move to define counterfactual coupling of $G^{\\text{obs}}$ and $Y$. They actually mention equation 1 but i assume this is a mistake and they mean equation 2. Also, why $\\tilde{E}$ is used as regular variable inside $g$? The definition is confusing to me since the event the indicator defines does not necessarily mean $G^{\\text{obs}}=G^{\\text{cf}}$. Anyway, I could not really understand what is the object that is defined here. My best guess was that there is a new random variable $G^{\\text{cf}}$ defined with a new environment $\\tilde{E}$, and the counterfactual coupling is their joint probability function.  \nIn Proposition 1, if I understand correctly, the main point is that given a function $\\Gamma$ that is (almost everywhere) invariant to the environment parameter then good generalization error of this function would also imply good extrapolation error. This feels natural, however, if this is indeed the case, I find it hard to understand the formulation of the difference equations in Prop 1. In particular the equalities between the different $G$, and what is a link function? The definition of E-invariant should be defined properly; e.g. , what does \"can be sampled\" mean? \n\nThe authors then turn to look for $E$-invariant graph functions $\\Gamma$. Theorem 1 then introduces certain assumptions under which it is possible. I could not understand the conclusions in this theorem. The assumptions basically mean that subgraphs of $G^{\\text{obs}}$ can be seen as sampled from smaller $n$. Does that mean different $E$ is already available by just sampling subgraphs of the observed data? Using these assumptions the authors prove in Theorem 2 that a certain version of subgraph counting provides such an $E$-invariant function. Again the definitions in this Section (3.1) were unclear. They also discuss an extension to graphs with features using some common GNN architectures in Section 3.2. I found this section also hard to follow. The paper concludes with experiments using these feature maps to demonstrate extrapolation properties.\n\nI think this paper presents a potentially interesting model and some initial results as to what kind of conditions allow extrapolation. However, this paper suffers from what I find as a bad exposition. It assumes familiarity with causality theory, and lacks clear definitions, statements, claims and explanations. I really struggled understanding the different parts and cannot say I fully understand them. I needed to guess many details and I am not sure i got it right. I think that to make this paper useful for the community a rather complete rewrite should be done. \n\nA more concrete concern I had is that I was under the impression that the type of assumption required (in Theorem 1) for building $E$-invariant representations basically means that we have access to different size graphs (through the sub-graph assumptions)  and therefore extrapolation to smaller sizes is possible. I would be interested to know if we can extrapolate to larger graphs in this case. \nLastly, subgraph counting is computationally and memory demanding. Maybe empirically quantifying the cost ($k$?)-extrapolation tradeoff could be useful. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a new extrapolation problem for graph representation learning (they refer to it as ' counterfactual modeling').
While the problem set-up is intriguing and the work likely has merit,  two reviewers (R2 and R4),  found the writing highly problematic and we share their opinion.  Even though some of the concerns they raised, as followed from the rebuttal, were not correct, this confusion, in our view, is largely due to the exposition.  Both these reviewers are experts in geometric deep learning. Their lack of understanding even of relatively central points of the paper, despite clearly investing a large amount of time in reading the paper, indicates that extra work is needed.  The only positive reviewer marked his confidence as very low, provided a rather short review, and did not choose to champion the paper.

While the authors tried to address the reviewers' concerns both in rebuttal and by revising the manuscript, we still feel that much more work is needed before it can be presented at a conference. We understand that this is a challenge to present this work in a conference format; it builds on the diverse background (e.g., in graph representation learning and in causal modeling) and considers a novel setting. However, we still feel that it could have been done much more successfully. In principle, this work may benefit from being presented in a journal paper (e.g., jmlr).
Decision: Reject