Expressive Power of Invariant and Equivariant Graph Neural Networks
Authors: Waiss Azizian
marc lelarge
Venue: ICLR 2021 Spotlight (2021)
Keywords: Graph Neural Network
Universality
Approximation

Abstract: Various classes of Graph Neural Networks (GNN) have been proposed and shown to be successful in a wide range of applications with graph structured data. In this paper, we propose a theoretical framework able to compare the expressive power of these GNN architectures. The current universality theorems only apply to intractable classes of GNNs. Here, we prove the first approximation guarantees for practical GNNs, paving the way for a better understanding of their generalization. Our theoretical results are proved for invariant GNNs computing a graph embedding (permutation of the nodes of the input graph does not affect the output) and equivariant GNNs computing an embedding of the nodes (permutation of the input permutes the output). We show that Folklore Graph Neural Networks (FGNN), which are tensor based GNNs augmented with matrix multiplication are the most expressive architectures proposed so far for a given tensor order. We illustrate our results on the Quadratic Assignment Problem (a NP-Hard combinatorial problem) by showing that FGNNs are able to learn how to solve the problem, leading to much better average performances than existing algorithms (based on spectral, SDP or other GNNs architectures). On a practical side, we also implement masked tensors to handle batches of graphs of varying sizes. 

Published as a conference paper at ICLR 2021
EXPRESSIVE POWER OF INVARIANT AND EQUIVARIANT GRAPH NEURAL NETWORKS
Waiss Azizian
Marc Lelarge
ENS, PSL University, Paris, France wa waiss wwiziazneen..n. fr
INRIA & ENS, PSL University, Paris, France marc. Lelrreeenageenss..
ABSTRACT
Various classes of Graph Neural Networks (GNN) have been proposed and shown to be successful wide range of applications with graph structured data. In this paper, propose theoretical framework able to compare the expressive power of these GNN architectures. The current universality theorems only apply to intractable classes of GNNs. Here, we prove the first approximation guarantees for practical GNNs, paving the way for better understanding of their generalization. Our theoretical results are proved for invariant GNNs computing graph embedding (permutation of the nodes of the input graph does not affect the output) and equivariant GNNs computing
embedding of the nodes (permutation of the input permutes the output). We show that Folklore Graph Neural Networks (FGNN), which are tensor based GNNs augmented with matrix multiplication are the most expressive architectures proposed so far for a given tensor order. We illustrate our results on the Quadratic Assignment Problem (a NP- combinatorial problem) by showing that FGNNs are able to learn how to solve the problem, leading to much better average performances than existing algorithms (based on spectral, SDP or other GNNs architectures). On practical side, we also implement masked tensors to handle batches graphs of varying sizes.
INTRODUCTION
Graph Neural Networks (GNN) are designed to deal with graph structured data. Since graph is not changed by permutation of its nodes, GNNs should either invariant if they return a result that must not depend on the representation of the input (typically when building a graph embedding) or cquivariant if the output must be permuted when the input is permuted (typically when building an embedding of the nodes). More fundamentally, incorporating symmetries in machine learning is fundamental problem as it allows to reduce the number of degree of freedom to be learned.
Deep learning on graphs. This paper focuses on learning deep representation of graphs with network architectures, namely GNN, designed to be invariant to permutation or equivariant by permutation. From a practical perspective, various message passing GNNs have been proposed, see Dwivedi et al. (2020) for a recent survey and benchmarking on learning tasks. In this paper, we study 3 architectures: Message passing GNN (MGNN) which is probably the most popular architecture used in practice, order-k Linear GNN (k-LGNN) proposed in Maron et al. (2018) and order-k Folklore GNN (k- FGNN) first introduced by Maron al. (2019a). MGNN layers are local thus highly parallelizable on GPUs which make them scalable for large sparse graphs. k-LGNN and k-FGNN are dealing with representations of graphs as tensors of order le which make them of little practical use for k 2 3.
In order to compare these architectures, the separating power of these networks has been compared to a hierarchy of graph invariants developed for the graph isomorphism problem. Namely, for i 2 2, k &-WL.(G) are invariants based on the Weisfeiler-Lehman tests (described in Section 4.1). For each 2 2, (k + 1) has strictly more separating power than k-WL (in the sense that there is pair of non-isomorphic graphs distinguishable by (k + 1)-WL and not by k-WL). GIN (which are invariant MGNN) introduced in Xu et al. (2018) are shown to as powerful as 2- 2LW In Maron et al. (2019a), Geerts (2020b) and Geerts (2020a), k-LGNN are shown to be as powerful as k- and 2-FGNN is shown to be as powerful as WL. In this paper, we extend this last result about k-FGNN to general values of ht So in term of separating power, when restricted tensors of order k; k-FGNN is the

---

Published as a conference paper at ICLR 2021
most powerful architecture among the ones considered in this work. This means that for given pair of graphs G and G", if (k + +1)-WL(G) + (k+ ++)-WW(("") then there exists a k-FGNN, say GNNg, such that GNN (G) & GNNG..
Approximation results for GNNs. Results on the separating power of GNNs only deal with pairwise comparison of graphs: need priori a different GNN for each pair of graphs in order distinguish them. Such results are of little help in a practical learning scenario. Our main contribution this paper overcomes this issue and we show that a single GNN can give a meaningful representation for all graphs. More precisely, we characterize the set of functions that can be approximated by MGNNs, k-LGNNs and k-FGNNs respectively. Standard Stone Weierstrass theorem shows that if an algebra A of real continuous functions separates points, then A is dense in the set of continuous function on a compact set. Here we extend such a theorem to general functions with symmetries and apply it to invariant and equivaraint functions to get our main result for GNNs. As consequence, we show that k-FGNNs have the best approximation power among architectures dealing with tensors of order k.
Universality results for GNNs. Universal approximation theorems (similar to Cybenko (1989) for multi-layers perceptron) have been proved for linear GNNs in Maron et al. (2019b); Keriven & Peyré (2019); Chen et al. (2019). They show that some classes of GNNs can approximate any function defined on graphs. To be able to approximate any invariant function, they require the use of very complex networks, namely k-LGNN where & tends to infinity with n the number of nodes. Since prove that any invariant function less powerful than (k + 1)-WL can be approximated by a k-FGNN, letting k tends to infinity directly implies universality. Universality results for k-FGNN is another contribution of our work.
Equivariant GNNs. Our second set of results extends previous analysis from invariant functions to equivariant functions. There are much less results about equivariant GNNs: Keriven & Peyré (2019) proves the universality of linear equivariant GNNs, and Machara & Hoang (2019) shows the universality of a new class of networks they introduced. Here, we consider a natural equivariant extension of k- GL and prove that equivariant (k + 1)-LGNNs and k-FGNN can approximate any equivariant function less powerful than this equivariant (k + 1) for k 2 1. At this stage, we should note that all universality results for GNNs by Maron et al. (2019b); Keriven & Peyré (2019); Chen et al. (2019) are easily recovered from our main results. Also our analysis is valid for graphs of varying sizes.
Empirical results for the Quadratic Assigment Problem (QAP). To validate our theoretical con- tributioon, we empirically show that 2-FGNN outperforms classical MGNN. Indeed, Maron et al. (2019a) already demonstrate state of the art results for the invariant version of 2-FGNNs (for graph classification or graph regression). Here we consider the graph alignment problem and show that the equivariant 2-FGNN is able to learn node embedding which beats by large margin other algorithms (based on spectral method, SDP or GNNs).
Outline and contribution. After reviewing more previous works and notations in the next section, we define the various classes of GNNs studied in this paper in Section message passing GNN, linear GNN and folklore GNN. Section 4 contains our main theoretical results for GNNs. First in Section 4.2 we describe the separating power of each GNN architecture with respect to the Weisfeiler- Lehman test. In Section 4.3, we give approximation guarantees for MGNNs, LGNNs and FGNNs at fixed order of tensor. They cover both the invariant and equivariant cases and are our main theoretical contributions. For these, we develop in Section D a fine-graine grained Stone Weierstrass approximation theorem for rector-valued functions with symmetries. Our theorem handles both invariant and cquivariant cases and inspired by recent works in approximation theory. In Section 6, we illustrate our theoretical results on a practical application: the graph alignment problem, well-known ha-hard problem. We highlight a previously overlooked implementation question: the handling of batches of graphs of varying sizes. A PyTorch implementation of the code necessary to reproduce the results is available at https: thub. commmlllee arge/ graph gawpeagaaheeeeeeeeaagg neural Lnet.
RELATED WORK
The pioneering works that applied neural networks to graphs are Gori et al. (2005) and Scarselli et al. (2009) that learn node representation with recurrent neural networks. More recent message passing architectures make use of non-linear functions of the adjacency matrix (Kipf & Welling, 2016),
2

---

Published as a conference paper at ICLR 2021
for example polynomials (Defferrard et al., 2016). For regular-grit graphs, they match classical convolutional networks which by design can only approximate canslation-invarian functions and hence have limited expressive power. In this paper, we focus instead more expressive architectures.
Following the recent surge in interest in graph neural networks, some works have tried to extend the pioneering work of Cybenko (1989); Hornik et al. (1989) for various GNN architectures. Among the first ones is Scarselli et al. (2009), which studied invariant message- passingg GNNs. They showed that such networks can approximate, in a weak sense, all functions whose discriminatory power weaker than 1-WL. Yarotsky (2018) 8) described universal architectures which are invariant or equivariant to some group action. These models rely on polynomial intermediate layers of arbitrary degrees, which would be prohibitive in practice. Maron et al. (2019b) leveraged classical results about the polynomials invariant to a group action to show that k-LGNN are universal as k tends to infinity with the number of nodes. Keriven & Peyré (2019) derived similar result, in the more complicated equivariant case by introducing a new Stone- Weierstrass theorem. Similarly to Maron et al. (2019b), they require the order of tensors to go to infinity. Another route towards universality is the one of Chen et al. (2019). In the invariant setting, they show for a class of GNN that universality is equivalent to being able to discriminate between (non-isomorphic) graphs. However, the only way achieve such discriminatory power is to use tensors of arbitrary high order, see also Ravanbakhsh (2020). Our work encompass and precise these results using high-order tensors it yields approximation guarantees even at fixed order of tensor.
CPNGNN in Sato al. (2019) and DimeNet in Klicpera al. (2020) are message passing GNN incorporating more information than those studied here. Partial results about their separating power follows from Garg al. (2020) which provides impossibility results decide graph properties including girth, circumference, diameter, radius, conjoint cycle, total number of cycles, and k-cliques. Chen et al. (2020) studies the ability of GNNs to count graph substructures. Though our theorems are much more general, note that their results are improved by the present work. Note also, that if the nodes are given distinct features, MGNNs become much more expressive Loukas (2019) but looses their invariant or equivariant properties. Averaging i.e. relational pooling (RP) has been proposed to recover these properties Murphy et al. (2019a). However, the ideal RP, leading to a universal approximation, cannot be used for large graphs due to its complexity of O(V))). Regarding the other classes of RPGNN i.e. the k-ary pooling (Murphy et al., 2019b), we will show how our general theorems in the invariant case be applied to characterize their approximation power (see Section 5).
Note that for neural networks on sets, the situation is bit simpler. Efficient architectures such as DeepSets (Zaheer et al., 2017) or PointNet (Qi et al., 2017) have been shown to be invariant universal. Similar results exist in the equivariant case (Segol & Lipman, 2020; Maron al., 2020), whose proofs rely on polynomial arguments. Though this is not our main motivation, our approximation theorems could also be applied in this context see Sections D.3 and D.4.
2.1 NOTATIONS: GRAPHS AS TENSORS
We denote by IF, Fo, F1/2, F1... arbitrary finite-dimensional spaces of the form Rp' (for various values of p) typically representing the space of features. Product of vectors in R2 always refer to component-wii wise product. There are two ways to see graphs with features. First, graphs can be seen as tensors of order k: G Fn. The classical representation of graph by its (weighted) adjacency matrix for Rn with Fm² where FF is some Rp. Second, graphs can also be represented by their discrete structure with additional feature vector. More exactly, denote by Gn the set of discrete graphs G = (V, E) with n nodes V = [n] and edges E C V2 (with no weights on edges). Such a G E Gn, with a vector ho e F" represents graphs with features on the vertices.
is a tensor of order 2 in 18=", This case allows for features on edges by replacing
2.2 DEFINITIONS: INVARIANT AND EQUIVARIANT OPERATORS
Let [n] = (1...... n). The set of permutations on [n] is denoted by Sn. For G F= and o E Sn, we define: (a * ()) = G.....i. Note that the * operation is valid between a permutation in S,, and graph G as soon the number of nodes of G is n, i.e. it is valid for any order k tensor
3

---

Published as a conference paper at ICLR 2021
representation of the graph. Two graphs G1, G2 are said isomorphic if they have the same number of nodes and there exists a permutation a such that G1 = a * G2.
Definition 1. A function f
F + 1 is said to be invariant if f( * G) f(G) for every permutation a Sn and every G E F6". A function f Fü + FT is said be equivariant f(a G = o * f(G) for every permutation a E Sn and every G E F
Note that composing an equivariant function with invariant function gives invariant function.
For k 2 1, we define the invariant summation layer S F= F by S (G) - Eienn] Gi for GE E F" We also define the equivariant reduction layer S F= + F" as follows: S (G), = Eisig..ie Gi, For message passing GNN, will the equivariant layer Id +XS* F" + FT defined by, (Id (G), = G. + (G), where E R is a learnable parameter.
In the sequel, we will need mapping 1 lifting the input graph to higher order tensor. We denote by I& F88 + +1TT the initialization function mapping for given graph each k-tuple to its isomorphism type. We refer to the appendix Section C.3 for a precise description of this linear equivariant function. Note at this stage that 1 is given by, for G E RT" T(G) = (Gtj. 55.5) where 6Ggر is 0 if + and I otherwise. Indeed for a pair of nodes i, j graph (without features), there are only three isomorphism types: j: i # and (i.j) is edge; i o j but (i,j) is not an edge.
3 GNN DEFINITIONS
In this section, we define the various GNN architectures studied in this paper. In all architectures, there is main building block or layer mapping F7" to Fy"" where F7" can be seen as the space for the representation of the graph at layer t. We will define three different types of layers for message passing GNN, linear GNN and folklore GNN.The case k- 2 is probably the most interesting case from a practical point view and corresponds to a case where a layer takes as input a graph (with features on nodes and edges) and produces as output graph (with new features on nodes and edges). For each type of GNNs, there will be an invariant and an equivaraint version. All architectures will share the last function: m, : Fr+1 - for the invariant case and mg : F7 + IF" for the equivariant case which are continuous functions. It is typically modeled by a Multi Layer Perceptron, which is applied on each component for the equivariant case. In words, each network takes as input a graph G E F produces in the invariant case a graph embedding in Fr+1 and in the equivaraint case node embedding in F7 then these embeddings passed through the function my or me respectively to get feature in F or F for the learning task.
3.1 MESSAGE PASSING GNN
Message passing GNN (MGNN) are defined for classical graphs G with features on the nodes. More exactly they take as input a discrete graph G = (V, E) E Gn and features on the nodes ht" E F". MGNN are then defined inductively as follows: let hς F, denote the feature at layer associated
(hÊ, ((1()) y...) where j ~ means that nodes and are neighbors in the graph G, ie. (i,j) E E, and the function is learnable function taking as input the feature vector of the center vertex bf and the multiset of features of the neighboring vertices {{ kt) }} jسر jm Indeed, follows from Lem. 33 Appendix, that any such function of can be approximated by layer of the form,
with node i, the updated features h5 are obtained as: h h5+1
R So
N E JI (1,10)) Jrs
where fo FF x Fe+1/2 + Fr+1 and fi F. x F3 + F241/2. so that Fr, is the field for the features at the ê-th layer. We call such function message passing layer and denote it by F: F7 F (note that F depends implicitly from the graph). Then an equivariant message passing GNN is simply obtained by the composition of message passing layers: F7 o ... F& FI. where each F, is message passing layer. Clearly since each F; is equivariant, this message passing GNN is also equivariant and produces features on each node in the space Fy. In order to obtain invariant GNN, we apply
4

---

Published as a conference paper at ICLR 2021
an invariant function from F7. Fr+1 the output of equivariant message passing GNN. In practice, a symmetric function is applied on the vectors of features indexed by the nodes, typically the sum of the features (F With our notation, S* o Fr .... Fi (where St was defined in Section2.2) defines invariant message passing GNN.
F2 Fi (G)); is taken an invariant feature for the graph G.
Hence, we define the sets of message passing GNNs as follows:
MGNN, = {m, S o.... F1, MGNNE {mg (Ld +AS') Fr o... F2 Fi, VT)
where Fj P2 + 1741 message passing layers.
3.2 LINEAR GNN
define linear graph layer of order k as F F." + Fe where for all G E Fy. F(G) (L[G)) where L 17y" 1Fy is linear equivariant function, and f Fg + Fe+1 is learnable function applied on each of the n features and Fe is the field for the features the L-th layer.
We then define the sets of linear GNNs as follows:
k-LGNN,
(m, Sh PT o F2 o 1 VT)
VT)
K-LGNNE (mr St Fr o...... F2 F1 1 VT}
where 7& F6 - BT is defined in $2.2 and for f 2 1, Fg F7" + Fit are linear equivariant layers.
3.3 FOLKLORE GNN
The main building block of Folklore GNN (FGNN) what we call the folklore graph layer (FGL) of order & defined as follows: for & 2 1, F
FV E+1 where for all G E FY" and all i E [m]*,
F(G); fo fo G1,
Σ
II f=1==] w=1
fw (Ga 1edta l.....bk))
(2)
where fo Fe X Fr41/2 + Fe+1 and fo F. - F 1/+1/2 are learnable functions. As shown in Lem. 33 in Appendix, FGL is equivariant function which is indeed very expressive.
For classical graphs G F8" we can
define 2-FGNN by composing folklore graph layers ....... Pi o Fo is an equivariant GNN producing graph in F7 To
Fe : IF7" - 1mn so that Fr o.... obtain an invariant feature of the graph, we use the summation layer Sa defined in Section 2.2 so that 82 Fr o... Fi Fo is
invariant 2-FGNN. In order define general k-FGNN, we first need to the classical graph to a tensor F= then we apply folklore graph layers of order and finally we need to project the tensor in R to a tensor F" for the equivariant version and to a tensor in for the invariant version. The first step is done with the linear equivariant function _ FF - FT" defined in Section 2.2. The last step is done with the reduction layer St for the equivariant case and the summation layer S for the invariant case, both defined in Section 2.2.
We define the sets of folklore GNNs as follows:
k-FGNN,
{mj 5h o Fr F 1 VT)
k-FGNN {mg St Fr..... F FFFF 1 VT}
where F. pun pu are FGL.s
THEORETICAL RESULTS FOR GNNS
4.1 WEISPEILER-LEHNE INVARIANT AND EQUIVARIANT VERSIONS
We introduce a family of functions on graphs parametrized by integers & 2 2 developed for the graph isomorphism problem and working with tuples of i vertices. Each k-tuple i 4 [n]* is given
5

---

Published as a conference paper at ICLR 2021
color (i) corresponding to its isomorphism type (see Section B.2). The k-WL test relies on the following notion of neighborhood, defined by, for any w E [k). and = (f....., ix)) E ,
{(i1... - 1- fw ....., ig.) j E V). Then, the colors of the h-tuples refined as follows, (i) = Lex (i) (CI()),..... (t))) where, for E [b]. C. (i) {{ c' ie (.) { and the function Lex means that all occuring colors are lexicographically ordered and replaced by an initial segment of the natural numbers.
For a graph G. let k- W (G) denote the multiset of colors of the k- WL algorithm at the T iteration. After finite number of steps (which depends on the number of vertices in the graph), the algorithm stops because a stable coloring is reached (no color class of k-tuples is further divided). We denote by k- (G) the multiset of colors in the stable coloring. This is graph invariant that is usually used to test if graphs are isomorphic. The power of this invariant increases with & Cai et al. (1989).
We now define an equivariant version of k-WL test express the discriminatory power of equivariant architectures For this, we construct a coloring of the vertices from the coloring of the k-tuples given by the standard k- WL algorithm. Formally, define k- k-WL F8 - F by, for i E V: k- k-WL = {(c (1) i E V* i = =}]]. Similarly, define k- e-WLg(G) = [(c(() ie V 11 +3} where c(i) is the stable coloring obtained by the algorithm.
4.2 SEPARATING POWER OF GNNS
We formulate results using the equivalence relation introduced by Timofte (2005), which charac- terizes the separating power of set of functions.
Definition 2. Let F be set of functions f defined on a set X, where each f takes its values in some Yy. The equivalence relation p (F) defined by F on X is: for any z, x' E X,
(I,x') E (FF = VFEF, f(x)=
Given two sets of functions F and E, we say that F is more separating (resp. strietly more separating) than & if p (F) C (E) (resp. (FF Ç p (E)). Note that all the functions in F and & need to be defined on the same set but can take values in different sets. For example, we can easily see that for the k- WL algorithm defined above, the equivariant version is more separating than the invariant one.
Some properties of the WL hierarchy of tests can be rephrased with the notion of separating power. In particular, Cai et al. (1989) showed that (A + 1)-WL; distinguishes strictly more than k-WL,, which can be rewritten simply as (for a function f. we write p (f) for p ((f)))
p ((k + 1)-WL,) S P (k-WL))
(3)
This notion of separating power enables us concisely summarize the current knowledge about the discriminatory power of classes of GNN.
Proposition 3. We have, for k 2 2,
P (MGNN)) (2-WLL) P (K-LGNN1) =P (K- P (K-FGNN p(( + 1)-WL,
P (MGNNE) = (2-WLL) (k- (k-LGNNE) S. (k- p (k- = ((K 1L-
(4)
(5)
(6)
Only results about the invariant cases were previously known: (4) comes from Xu et al. (2018), (5)
from Maron et al. (2018) Geerts (2020a) and one inclusion of (6) comes from Maron et al. (2019a). The equality in (6) for general & 2 2 is proved in Section C.
Note that for k all GNNs are dealing with tensors of order i.c. with the adjacency matrix of the graph. However, the complexities of the various layers are quite different: for the message passing GNN, all computations are local (scaling with the maximum degree in the graph) and can be done in parallel; for the linear layer, there are only 15 linear functions from Ra* > IR. for all values of n (Maron et al., 2018); the folklore layer involves a (dense) matrix multiplication of shape 2-FGNN is the most complex architecture, we see that it has the best separating power among all architectures proposed so far dealing with tensors of order 2.
If

---

Published as a conference paper at ICLR 2021
4.3 APPROXIMATION RESULTS FOR GNNS
For X, Y finite-dimensional spaces, let us denote by Cr(X, Cx Y),, the set of invariant, respectively equivariant, continuous functions from X to Y. The closure of class of function F for the uniform norm is denoted by F. Our result extend easily to graphs of varying sizes but this is deferred to Section F.2 for clarity.
The theorem below states in particular that the class k-FGNN can approximate any continuous
function that is less separating than (k + 1)-WL in the invariant and in the equivariant cases.
Theorem 4. Let Kdiser - In Fü. K _ F8O be compact sets. For the invariant case, we have:
MGNN, {ʃ E (Kss,,,,, B): ((2-WL,) & (f)
1-LGNN = {f E B): P (k-) S (
k-FGNN = {f (K(,K)) P ((k + 1)- [(()
For the equivariant case, we have:
MGNNE (S E CE(Kiiser, )F P (2-WLE) [
k-IGNNE (E, P (K-LGNNE) E (()) = (S F*), ((-WWL.) S [()))
K-FGNNE = {f (EC, P ((k+1)-WLE) S (f)}
In the invariant case for k = we have MGNN, = 2-LGNN, E 2-FGNN; where the strictness of the last inclusion comes from (3). In other words, 2-FGNN, has a better power of approximation than the other architectures working with tensors of order 2. We already knew by Proposition 3 that 2-FGNN, is the best separating architecture among those studied in this paper, dealing with tensor of order 2 and our theorem implies that this is also the case for the approximation power.
To clarify the meaning of these statements, we explain why the inclusions "S" are actually straightfor- ward. For concreteness, we focus on K-FGNN, S {f E F), p((k + 1)-WL,) S p (f)). Take h k-FGNN, this means that there is a sequence GNN, k-FGNN, such that, suPGEK [[h(G') GNN,(G)] goes to zero when j goes to infinity.
Therefore, h is continuous and constant on each p (4-FGNNN)-claas Indeed, for any (G.G)) (k-FGNN1), GNN,(G) = GNN, (G') so that h(G) = lim, GNN, = lim, GNN, = h(G"). Hence we have p (k-FGNN,) E (h) and by Prop. 3, p (k-FGNN1) p ((k + W)-WW)). allowing us to get the inclusion above.
On the contrary, the reverse inclusions "5" are much more intricate but they are also the most valu- able. For instance, consider the inclusion k-FGNN, > {f e F), p(k + 1)-WL,) S P (f)). If one wishes to learn a function h E C, with k-FGNN, this function must at least be approximable by the class of k-FGNN, Our theorem precisely guarantees that if h is less separating that k- W-W,,,, it can be approximated by k-FGNN,
VE 0, EGNN E K-FGNN, sup [I(G] GNN(G))I Sc.
GEK
For this, show much more general version of the famous WeiersWeisss theorem (see Section D) which relates the separating power with the approximation power. Following the elegant idea of Machara & Hoang (2019), we augment the input space to transform vector-valued equivariant functions into scalar invariant maps. Then, we apply a fine-grained approximation theorem from Timofte (2005). We also provide specialized versions of our abstract theorem in Section which can be easily used to determine the approximation capabilities of any deep learning architecture.
Our theorem has also implications for universality results like Maron et al. (2019b); Keriven & Peyré (2019), A class of GNN is said to be universal if its closure on a compact set K is the whole Cy (K, I)) (or Cx(K, F))). In particular, Thm. implies that n-LGGNN and n-FGNN are universal as n-WL distinguishes non-isomorphic graphs of size n. This recovers a result of Ravanbakhsh (2020) for LGNN. Moreover, we can leverage the extensive literature on the WL tests to give more subtle results. For instance, Cai et al. (1989, $8.2) show that, for planar graphs, O(vR)-WIL can distinguish non-isomoprhic instances. Therefore, OLVN)-LGNN or particular, yet common, case of planar graphs. On more practical side, Fürer (2010, Thm. 4.5) shows that the spectrum of a graph is less separating than 3- WL so that functions of the spectrum can actually be well approximated by 2-FGNN.
achieve universality in the
7

---

Published as a conference paper at ICLR 2021
5 EXPRESSIVENESS OF GNNS
We now state the general theorems which are our main tools in proving our approximation guarantees for GNNs. Theirs proofs deferred Section D.9 which contains generalization of the Stone- Weierstrass theorem with symmetries. We need to first introduce more general definitions: If G is finite group acting on some topological space X, we say that G continuously X if, for all G, I + is continuous. If G is a finite group acting on some compact set X and some topological space Y, we define the sets of equivariant and invariant continuous functions by,
C) (f C(X,Y) Ye e E, Vg E G, flg z) = f()) Cx (E),) Vo E X, Vy e G, fgg x) = f(x))
Note that these definitions extend Definition I to general group.
Theorem 5. Let X be compact space, FF = RRP be some finite-dimensional vector space, G be finite group acting (continuuusly) on X.
Let Fo - C Cr( be non-empty set of invariant functions, stable by concatenation, and consider,
F =m Fon m: R + F h c
Then the closure of F is,
F == (Fo) Ep(f)
We can apply Theorem 5 to the class of k-ary relational pooling GNN introduced in Murphy et al. (2019a). As result, we get that this class of invariant k-RP GNN can approximate any continuous function I with p(k- RPGNN) C p(f) but to the best of our knowledge, p(k: RPGNN) is not known and only p(k - RPGNN) C p(2 2o(2-W6 LI)) [ is proved in Murphy et (2019a). We now state general theorem for the equivariant case:
Theorem 6. Let X be compact space, F = IRP and G = Sn, the permutation group, acting (continuously) on X and acting on F" by, for Sn, F",
Vi E (1......), p), (a .., = (
Let Fo S CE (Rh)R) be non-empty set of equivariant functtoon stable by concatenation, and consider,
F= (z (m(((x))) m(((:))))))))))))))))))))))))))) Func (X, m R F FLP. h 1}
Assume, that, if f E Fo, then,
Σ f(x),, Σ f(x),
f(1); E Fu.
x +
Then the closure of F
F= = (s C=(,F"") (Foo C Ep())
Applications of these theorems case of Pointnet Qi et al. (2017) are provided Section D.9
QUADRATIC ASSIGNMENT PROBLEM
To empirically evaluate our results, we study the Quadratic Assignment Problem (QAP), a classical problem in combinatorial optimization. For A, B symmetric matrices, it consists in solving
maximize trace(AXXX"
subject to X E II,
where II is the set of n x n permutation matrices. Many optimization problems can be formulated as QAP. An example is the network alignment problem, which consists in finding the best matching
8

---

Published as a conference paper at ICLR 2021
between two graphs, represented by their adjacency matrices A and B. Though QAP is known to be NP-hard, recent works such as Nowak et al. (2018) have investigated whether it can be solved efficiently w.r.. a fixed input distribution. More precisely, Nowak et al. (2018) studied whether one can learn to solve this problem using a MGNN trained on a dataset of already solved instances. However, as shown below, both the baselines and their approach fail on regular graphs, class of graph considered as particularly hard for isomorphism testing.
To remedy this weakness, we consider 2-FGNN E. We then follow the siamese method of (Nowak et al., 2018): given two graphs, our system produces an embedding in IF" for each graph, where n is the number of nodes, which are then multiplied together obtain a n X n similarity matrix on nodes. A permutation is finally computed by solving a Linear Assignment Problem (LAP) with this resulting n n as cost matrix. We tested our architecture on two distribution: the Frdös-Rényí model and random regular graphs. The accuracy in matching the graphs is much improved compare to previous works. The experimental setup is described more precisely in Section A.
Erdōs Erdōs-Rényi graph model
Regular graph model
0.8
0.8
Accuracy
Accuracy
0.6
0.6
0.4
0.4
0.2
0.2
0
0
0.01
0.02
0.03
0.04
0.05
0.01
0.02
0.03
0.04
0.05
Noise level
Noise level
This work
SDP (Peng et al., 2010)
LowRankAlign (Feizi et al., 2016)
GNN (Nowak et al., 2018)
Figure/ Fraction of matched nodes for pairs of correlated graphs (with edge density 0.2) function of the noise, see Section A. for details.
7 CONCLUSION
We derived the expressive power of various practical GNN architectures: message passing GNN, linear GNN and folklore GNN; both for their invariant and equivariant counterparts. Our results unify and extend the recent works in this direction. In particular, we able recover all the universality results proved for GNNs so far. Similarly to existing results in the literature, we do not deal here with the sizes of the embeddings constructed at different layers, i.c. the sizes of the spaces F&, and these sizes are supposed to grow to infinity with the number of nodes n in the graph. Obtaining bounds on the scaling of the sizes of the features ensure that the results presented here are still valid is an interesting open question. We show that folklore GNNs have the best power of approximation among all GNNs studied here dealing with tensors of order From a practical perspective, we demonstrate their improved performance the QAP with significant gap in performances compared to other approaches.
ACKNOWLEDDMENNT
This work was supported in part by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d' l'avenir" program, reference ANR19-P3IA-000 (PRAIRIE 31A Institute). M.L. thanks Google for Google Cloud Platform research credits and NVIDIA for NVIDIA GPU Grant.

---

Published as a conference paper at ICLR 2021
REFERENCES
J.-Y. Cai, M. Furer, and N. Immerman. An optimal lower bound the number of variables for graph identification. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, SFCS '89, pp. 612-617, USA, 1989. IEEE Computer Society. ISBN 08 186119999 1819821. doi: (ttp:/SSSS...9..333555
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 2019.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? CoRR, abs/2002.04025, 2020.
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, 2(4):303-311 1989.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852, 2016.
Brendan L Douglas. The weisfeiler- lehman method and graph isomorphism testing. arXiv preprint arXiv: 2011.
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXi::2003.00992, 2020.
Soheil Feizi, Gerald T. Quon, Mariana Recamonde Mendoza, Muriel Médard, Manolis Kellis, and Ali Jadbabaie. Spectral alignment of networks. CoRR, abs/1602.04181, 2016.
Martin Fürer. On the combinatorial power of the weisfeiler-lehman algorithm. In International Conference on Algorithms and Complexity, pp. 260-271. Springer, 2017.
Martin Fürer. On the power of combinatorial and spectral invariants. Linear Algebra and its Applications, 432(9):2373 2380, 2010. ISSN 0024-3795. doi: https://doi.org 10.//10.1116 laa106/j.aaa.00099 07.019. Special Issue devoted to Selected Papers presented the Workshop on Spectral Graph Theory with Applications on Computer Science, Combinatorial Optimization and Chemistry (Rio de Janeiro, 2008).
Vikas K Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. arXiv preprint arXiv:2002.06157, 2020.
Floris Geerts. The expressive power of kth-order invariant graph networks. arXiv preprint arXiv:2007.12035, 2020a.
Floris Geerts. Walk message passing neural networks and second-order graph neural networks. arXiv preprint arXiv:2006.094400 2020b.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729-7344 IEEE, 2005.
Martin Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Lecture Notes in Logic. Cambridge University Press, 2017. doi: 10.1017/978 139028888....
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks universal approximators. Neural Networks, 2(5):359 366, 1989. ISSN 0893-6080. doi: https:
10

---

Published as a conference paper at ICLR 2021
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buue Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 7090-7099, 2019.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks arXiv preprint arXiv:1609.0290000 2016.
Johannes Klicpera, Janek Groß, and Stephan Günnemann. Directional message passing for molecular graphs. arXiv preprint arXiv:2003.03/22; 2020.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. arXiv preprint arXiv:/907.03199 2019.
Takanori Maehara and NT Hoang. A simple proof of the universality of invariant/equivariant graph neural networks. ArXiv, abs/1910. 0tss//990003802.. 2019.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprini arXiv: (.XXv0/8//200902.. 2018
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pp. 2153-2164, 2019a.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. arXiv preprint arXiv: 1eXXiv:901..00 190109932, 2019b.
Haggai Maron, Or Litany, Gal Chechik, and Ethan Fetaya, On learning of symmetric elements. CoRR, abs/2002.08599, 2020.
J.R. Munkres. Topology. Featured Titles for Topology. Prentice Hall, Incorporated, 2000. ISBN 9780131816299.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663 4673. PMLR, 2019a
Ryan I.. Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019b.
Alex Nowak, Soledad Villar, Afonso S. Bandcira, and Joan Bruna. Revised note on learning quadratic assignment with graph neural networks. 2018 IEEE Data Science Workshop (DSW), pp. 1-5, 2018.
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, regh-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc. E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
Jiming Peng, Hans D. Mittelmann, and Xiaoxue Li. A new relaxation framework for quadratic assignment problems based on matrix splitting. Mathematical Programming Computation, 59-77, 2010.
Charles Ruizhongtai Qi, Hao Su, Kaichun Mo, and Leonidas J. Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI. USA. July 21-26. 2017, pp. 77-85. IEEE Computer Society, 2017. doi: 10. 109/CV/R.2017..6
Siamak Ravanbakhsh. Universal equivariant multilayer perceptrons. arXiv preprint arXiv:2002.02917 2020.
11

---

Published as a conference paper at ICLR 2021
W. Rudin. Functional Analysis. International series in pure and applied mathematics. McGraw-Hill, 1991. ISBN 9780070542365.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Advances in Neural Information Processing Systems, pp. 4081- 4090, 2019.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. Computational capabilities of graph neural networks. IEEE Trans. Neural Networks, 20(1):81-102 2009. doi: 10. 1110//NN.2008.0000
Nimrod Segol and Yaron Lipman. On universal equivariant set networks. ArXiv, abs/1910.02421, 2020.
Vlad Timofte. Stone-weierstrass theorems revisited, Journal of Approximation Theory, 136(1):45 59, 2005. ISSN 0021-9045. doi: https://doi.org// 1at1
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.008: 2018.
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. CoRR, abs/1804. 10306, 2018
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J. Smola. Deep sets. Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 3391-3401 2017.
12

---

Published as a conference paper at ICLR 2021
A Experimental results
14
A.1 Details on the experimental setup
14
A.2 Experimental results graphs of varying size
14
A.3 Generalization for regular graphs
15
Weisfeiler-Lehman tests
16
B.1 Weisfeiler-Lehman test on vertices
16
B.2 Isomorphism type
16
B.3 Weismeiler-Lehman and Folklore Weisfeiler- Ceissan tests of order
17
Separating power of GNN
18
C.I Mutli-linear perceptrons
18
C,2 Augmented separating power
18
C,3
Initialization layer
19
C.4
Known results about the separating power of some GNN classes
20
Bounding the separating power of k-FGNN
20
C.6
Conclusion
theorem with symmetries
21
D.I General notations
22
D.2 Separating power
22
D.3
Approximation theorems for real-valued functions
23
D.4 The equivariant approximation theorem
24
D.5 A preliminary version of the equivariant approximation theorem
26
D.6 Characterizing the subalgebras R
27
D.7 Proof of the main equivariant approximation theorem
29
D.8 Practical reductions
30
D.9 Reductions for GNNs
33
E Proofs for expressiveness of GNNs
34
E.1 Expressivity of GNN layers
34
E.2 Approximation theorems for GNNs
35
F Extension to graphs of varying sizes
37
E1 Extension disconnected input spaces
37
F2 Approximation theorem with varying graph size
39
13

---

Published as a conference paper at ICLR 2021
A EXPERIMENTAL RESULTS
A.1 DETAILS ON THE EXPERIMENTAL SETUP
We consider 2-FGNN E and train it to solve random planted problem instances of the QAP. Given a pair of graphs G1, G2 with n nodes each, we consider the siamese 2-FGNN encoder producing embeddings E,, Eg E Raxk Those embeddings are used predict matching as follows: we first compute the outer product E, E, then we take softmax along each row and use standard cross-entropy loss to predict the corresponding permutation index. We used 2-FGNN Ø with 2 layers, each MLP having depth 3 and hidden states of size 64. We trained for 25 epochs with batches of size 32, a learning rate of le-4 and Adam optimizer. The PyTorch code available in the supplementary material.
For each experiment, the dataset was made of 20000 graphs for the train set, 1000 for the validation set and 1000 for the test set. For the experiment with Erdōs Rényi random graphs, we consider G1 to be a random Erdös Erdōs-Rényi graph with edge density Pe = 0.2 and n = 50 vertices. The graph G2 is a small perturbation of G according to the following enror model considered in Feizi et al. (2016):
G2 = 11 o (1 - Q) + -1- @ Q',
where Q and Q' are Erdōs-Rény: random graphs with edge density p1 and p2 PiPe/(1 pe) respectively, so that G2 has the same expected degree as G1. The noise level is the parameter P1. For regular graphs, we followed the same experimental setup but now G1 a random regular graph with degree d = 10. Regular graphs are interesting example as they tend to be considered harder to align due to their more symmetric structure.
A.2 EXPERIMENTAL RESULTS ON GRAPHS OF VARYING SIZE
Regular graph model
0.8
Accuracy
0.6
0.4
0.2
This work
0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2
Noise level
Figure 2: Fraction of matched nodes for pairs of correlated graphs (with edge density 0.2) function of the noise, see Section A.I for details.
We tested models on dataset of graphs of varying size, this setting is also encompassed by theory.
However, contrary message-passing GNN, GNN based on tensors do not work well with batches of graphs of varying size. Previous implementations, such as the one Maron et al. (2019a), group the graphs in the dataset by size, enabling the GNN only deal with batches of graphs the same size.
14

---

Published as a conference paper at ICLR 2021
Accutary
10
69
693
024
626
D1
022
033
034
633
636
617
039
5"
00 091 o8z
ods
ud4
8:8
08s
01 013
033
616
01r 038
021 922
ress
Figure 3: Each line corresponds to model trained at a given noise level and shows its accuracy across all noise levels.
Instead, we use masking, which standard practice recurrent neural networks. A batch of tensors of sizes n1; n2 X 72,,..., R4 is represented as tensor b x Amaz X Rmna where Amaz max;=1....b ny. mask created initialization and used to ensure that the operations on the full tensor translates to valid operations each of the individual tensor.
implemented this functionnality as class MaskedTensors. Thanks to the newest improve- ments of PyTorch (Paszke et al., 2019), MaskedTenson act subclass of fundamental Tensor class. Thus they almost seamlessly integrate into standard PyTorch code. We refer the reader to the code for more details: https: : / ///gtttttt github.. com com/mmeell /wwmmeerrrggeeeem/emmmmmmmlamell garaph_neurae
net
Results of our architecture and implementation with graphs of varying size are shown below on Figure 2. The only difference with the setting described above is that the number of nodes is random. The number of vertices of graph is indeed chosen randomly according to binomial distribution of parameters 50 and P.. 0.9.
A.3 GENERALIZATION FOR REGULAR GRAPHIS
We made the following experiment with the same general setting in Section A. with regular graphs. We trained different models for all noise levels between and 0.22 but in Figure 3, we plot the accuracy of each model across all noise levels. We observe that majority of the models actually generalize to settings with noise level on which they were not trained. Indeed, the model trained with noise level es 0.1 is performing best among all models across all noise levels!
15

---

Published as a conference paper at ICLR 2021
B WEISFEILER-LEHMAN TESTS
Here we describe more precisely this hierarchy tests, which will be used extensively to characterize the discirminatory power of classes of GNN. See Douglas (2011); Grohe (2017); Fürer (2017) for graph-theoretic introductions to these algorithms.
B.1 WEISFEILER-LEAEE TEST ON VERTICES
We now present the initial vertex coloring algorithm.
Input.
This algorithm takes input discrete graph structure G (V, 9n with V [n], B C 2 and E F features on the vertices.
Initialization.
Each vertex E V is given a color (wT h), h, corresponding to its features
vector.
Refining the coloring.
The colors of the vertices are updated as follows,
4+1 (G, h), = Lex (G, h).: {f (f (G)) x}})
and the function Lex means that all occuring colors lexicographically ordered.
For each graph G E Gn and each vector of features h E Fö. there exists a time T(G, h) from which the sequence of colorings (dwL (G, h)) is stationary. More exactly, the colorings refined anymore: for any 2 T(G, h1), 8,8' E..
dw h), dw (G, -
T(G, T(G.N) (G, (G,h), = CWI.
(G, h)
OWL
Denote the resulting coloring OWL Gn x F8 th for some space of colors Z.
T(G.A) (G, h) by simply (G, OwL. is now mapping from
Invariant tests The proper Weisfeiler-Lehmal test is invariant and is defined by, for 2 0 and (G, h) Gn x Fø graph,
WL)(G) ((dh(()) :se]). v} WL,(G) Heww :SE):
Equivariant tests For the vertex coloring algorithm, OWL is already an equiavriant mapping so we define, for / 2 0 and (G, h) E Gn x Fö a graph,
WL =CWL
WL. OWL
B.2 ISOMORPHISM TYPE
The initialization of the higher-order variants of the Weisfeiler-Lehman test is slightly more intricate. For this we need to define the isomorphism type of k-tuple w.r.t. a graph described by a tensor Fø"
A k-tuple (i1,..., i E [m]* in a graph G F and k-tuple (fi.....je) .ja)) E [m]] in graph Il 1882 are said have the same isomoprhism type if the mapping in + Ino well-defined partial isormophism. Explicitly, this means that,
Vw, w/ E [k], dw in - In = Iw. Vw, w/ E [k], Grunrhu = Hjwdir
Denote by iso (so(G)i the isomorphism type of the k-tuple (f1,..., ix) [m]] in graph G E Fg?
16

---

Published as a conference paper at ICLR 2021
B.3 WEISFEILER-LEHAE AND FOLKLORE WEISFEILER LEHMAAN TESTS ORDER A 2
We now present the folklore version of the Weisfeiler-Lehmal test of order (k-FWL), for k 2 2, along with k-WL for clarity, For both, follow the presentation of Maron et al. (2019a) (except for the equivariant tests).
Input. These algorithms take input graph G Fy" which can be coloring the pair of nodes.
Initialization. Each k-tuple s E V is given a color cf (G), cº. FwL. (G), corresponding to its isomorphism type.
k-WL. The k- &L test relies on the following notion of neighborhood, defined by, for any w [k]] and (f1....,444 .4) ) V².
(s) {(i1,..., 1...
(4) v}.
(WL)
Then, the colors of the k-tuples E Vk are refined as follows,
WL (G), Lex (G),, (C())
where, for E [k).
(s) (G)) (s)))))
For each graph G E Fü. there exists time T(G) from which the sequence of colorings (cf (G)) is stationary. More exactly, the colorings are not refined anymore: for any / T(G). s, Vk.
(G), = (i:ww(G): =
TG)) c WL (G), = (2 (G)s
T(G) (G) by simply (G- Denote the resulting coloring Ck-WL
F-F For k-FWL, the corresponding notion neighborhood defined by, for any j E V, and (f1,..., (x) E Vk
Nff(s) = 16. is), (11. .........)) 24. (x-
(FWL)
Then, the colors of the k-tuples E Vkk are refined as follows,
1+1 k-wL (G), Lex (ck.w..())
([C (
where, for j E V.
(s) = (ck. 8E
Like k- LL,,, for each graph G E Fü, there exists time T(G) from which the sequence of colorings (G))e( is stationary. Similarly, denote the resulting coloring T(G) (G) by simply (G)
The colors FL. and F.. at iteration t define mapping from F8 to space of colorings of k-tuples, nn" for some space Z.
Invariant tests The standard versions of the Weisfeiler- Lehman tests are invariant and can be defined by, for 2 0 and G E F graph,
k-W ((
vky (G) = (HCuWL(G) vi]]
k-FWL(( = ((chomi (G), V*]]
A-FWI,, ((cR (G) :8 y*]]
17

---

Published as a conference paper at ICLR 2021
We now introduce the equivariant version of these tests. Many extensions possible, chose this one for its simplicity. For t 0, G Fj a graph, i V.
Equivariant tests
k- B (G); ([ (G), : V* 81 i}
k- (G),, ((c..w : v* $1 i}}
k-FWI E = (LLA (G)s V*. $1 = =1}
k-FWL-g(G); ((CLFWL (G), E VL. ;1 = =1]]
C SEPARATING POWER OF GNN
The goal of this section is to prove, Proposition We have, for k 2 2, (MGNN1) p (2-WLI)
(MGNNE) = (2--WLE)
(4)
P (K-LGNN,) (k-WL1)
(K-LGNNE) S. P (k-WLE) P (K-FGNNE) - [((( + 11-WLE)
(5)
(K-FGNNTT) - ((K + 1)-WLr)
(6)
C.I MUTLI-LINEAR PERCEPTRONS
In the following we will use extensively multi-linear perceptrons (MLP) and their universality properties. Yet, for the sake of simplicity, we do not define precisely what we mean by MLP.
Given two
feature spaces Fo and F, we only assume we are given class of (continuous) MLP from Fo to F, which is large enough to be dense in C(IF, F1). See for instance Hornik al. (1989); Cybenko (1989) for precise conditions for MI.P be universal.
C.2 AUGMENTED SEPARATING POWER
To factor the proof, we introduce another notion of separating power. Definition 7. For n, m 2 1 fixed, let X be a set, IF be some space and F be set of functions from X Y paxm Then, the augmented separating power of is,
aagm P n.m
(F) = (1((2, 1, E X x (I.....m} x fl.....m) + (())s:ffFF))
Explicitly, for x. y E X, X.i,j (1....,m]. m).
(x, 1. 1) Papm
(F) Af EF, f(x) = f(y)a1
Note that when = m 1, the augmented separating power is exactly the same as the original separating power, so we identify p (-) with p augm we denote by paugm (.).
(.). We also identify Pn.1
asigm (.) with augm (.), that
First, it is easy to that this notion is more precise than the separating power.
Lemma 8. If F and G are set of functions from X to Faxm
Pn.m
(F) C
Pa.m
(g) = p(F) cg)))
and, in particular,
(F)
- p(F p())
Pr.m
The interest in this notion is justified by the following lemma, which shows that this notion behaves well under composition with "reduction layers".
Lemma 9, For n, m 2 1 fixed, let X be a compuct topological space, = Faxm some finite- dimensional space, F C(X,Y), and T X + Znxm function for some space Z. Define F FC,, by.
I TEXI +
Σ ((f(x)1))
Σ h(f(z)2.))
Σ ((f(z)))) :h + F f
18

---

Published as a conference paper at ICLR 2021
and F z" by, for X, Vi E nI...., F(x); ((((x)) : 15 m]]
Then,
Pa.m
(F) C
pagm
(r)
f
Pn.m
augm (7)
P
augm
Prem
augin
(T)
P
auggm
P
augm
Note that, in the statement, we implicitly see FF as a set of functions from X to [2X1 to fit the definition of augmented separating power.
Proof. We show the two inclusions independently.
( We first show that.
Paim
(F)
S augm
(T)
P
augmm
F
Pimm
Take (Ir, i, k) E Pn.m
F
This means that, for any F: FFF.REEFF
m
m
Σ (((())))) Σ MS(W))))
By Lem. 31 and the universality of MLP, there exists permutation o Sm such that f())
= (..())............ (()))))......)......)) f.))..m By definition the augmented separating power, this means that, for any j {1,..... ......,,,..... (at, (,,( k,j) E Pamm (F). Hence, by assumption, for any j E {1,... m). ( k. pamm (T), i.e. (()) r(y)kJ- But this exactly means that 7(x); F(v)x so that (x,i,y,k) angm (f) as required.
Pr.m
(D) We now show the other inclusion,
Pr.m (F) augmm (T)
-
P
Pr
augim
Pamm (7)
Take (Ir, (n,i,y,k) E paugm (7). By definition of F, this means that there exists E S,p such that ((z)),,(1) = T(U)k so that
U. (,), = (f()),,),... f(v)).m) and so, for any m
paaa (r) S Paaa (F). Hence,
for any f E F. h F.
Σ -((()) = Σ N((())))))
j=1
Therefore, (I, u, k) daggm
(F) which concludes the proof.
C.3 INITIALIZATION LAYER
We use the same initialization layer Maron et al. (2019a); Chen et al. (2020) and recall it below. The initial graph is a tensor of the form G J8g² with Fo R=+2, the last channel of G encodes the adjacency matrix of the graph and the first e channels G.,. are zero outside the diagonal and
G Re is the color of vertex i V. We then define I* 188" uen** with Fr Ig ((((())) as follows:
1 (G)
Giniin E 1],
1 (G)ineet2 = 1(1, = is).
for i E [n]* and r,s E [k). This linear equivariant layer has the same separating power as the isormorphism type, which is defined in Section B.2.
19

---

Published as a conference paper at ICLR 2021
Lemma 10 (MMrrnn et al., 2019a, C.1)). For k 2 2, Po 2 1, Fo exists 1 188" + FT such that,
R Fr R (po+1), there
augg D
(1*)
P Pontt- (iso)
C.4 KNOWN RESULTS ABOUT THE SEPARATING POWER SOME GNN CLASSES
First, we need to define some classes of GNN from which both the invariant and equivaraint GNN we considered are built. See Section 3 for details about the different layers.
MGNN emb {Fr .............................. 0 Fr: F. + Fi+1 message passing layer, ................................ .T............. T 1]
k-LGNN emb = {Fr o...... F2
[Foo...Foof. 1s F2 + F241 linear equivariant layer, t = 1, ,.....,,,IT
k-FGNN emb = {Fr o.... F 1s F. + F FGL, = T. , 1}.
Then, the precise results from the literature can be rephrased as,
Lemma 11 (Xu et al. Maron al. (2018).Maron al. (2019a)). For k 2 2,
Pi auggmn
(MGNN emb) Pn augm (cwz)
(8)
P ougma (K-LGNNema) _ auugr (CR-WZ)
(9)
P gagmm
(k-FGNNemb) E Parat (CR-FWL)
(10)
(8) comes from eu al. (2018, $A, {B), (9) and (10) from Maron et al. (2019a, $C, $D).
C.5 BOUNDING THE SEPARATING POWER OF k-FGNN
We complete the results of the literature with a bound on the separating power of k-FGNN. Note that the particular case of h: 2 is already proven in Geerts (2020a).
Lemma 12. For any k 2 2,
augm P,n (I-FGGNeems) 3 Pr,nk- (Ck-FWZ).
so that
augm P (k-FGNNemsb)
paugin (Ck-FWL).
Proof. Define,
K-FGNN emb = (F
17 + F FGL, t = I,...,
the set of functions defined by exactly T FGL layers. We show by induction that, for any T 2 0,
(k-FGNN Tmb)) C Paugr (cf.
For T= = 0, this is immediate by the definition of 1 in Section C.3.
Assume now that this inclusion holds at 7 2 0. We show that it also holds at T', Take G, G' E EE""
and s, s' [n] such that,
FWL (G), = Ff.. FWL (G')
We need to show that, for any f E K-FGNNT emb.
f(G), = f(G').'
But, by definition of the update rule k-FWL, the equality of the colors of and s' above implies that,
T-1 ( (G), = T (G')s² k-FWI,
(11)
and that there exists a E S,, such that, for any j E [n].
C C (G)a BE Nf)) =
- ( : NE (6))
20

---

Published as a conference paper at ICLR 2021
Let (i1...., ix) and s' (fiy... Jk). Then this implies that, for any [k], E [m],
F.. C.. (G)i isht tendd = (o.
(12)
We now use the induction hypothesis, i.c. that, (K-FGNN 5 P gugm
augm Pnn
(c
Take any fr-1 E k-FGNN T emb (11),
-1-(()s=Sr-1(0
By (12), for any jb], E [m]]
(G) 1 F (.th
By the definition of FGL Section 3.3, for any Fr. F7 + E741 FGL, Fr o fr-1(G), =Fr
fT-1(G")s' Therefore, for any f E K-FGNN emb.
- ([G)==[(G))
which concludes the proof.
C.6 CONCLUSION
Proposition 13. We have, for & 2 2,
P (MGNN,) (22-WL))
(MGNNE) = p (2-WLL))
(13)
P (2-LGNN,) (2-WWL)) P (K-LGNNI1 S. ((--WL)) (K-FGNN1) (K-FFWI.)
(14)
P (K-LGNNE) S (K-WWE) (k-FGNNE) p (k--FWLL))
(15)
(16)
Proof. Most of the statements come from the literature or are direct consequences of the lemmas above.
Proof of (13). The invariant case is proven in Xu et al. (2018, Lem. 2, Thm. 3). The equivariant comes from Lem. 11, Lem. 8, the fact that the layers me (Id +XS²) does not change the separating power and recalling that simply WLg CWL.
(14) is the exact result Chen et al. (2020, Thm. 6).
Proof of (15). The invariant case is exactly Maron et al. (2019a, Thm. 1). The equivariant case comes from Lem. 11 Lem. 9, Lem. and the fact that the layer mg does not change the separating power.
Proof of (16). The direct inclusion of the invariant case corresponds to Maron et al. (201 9a, Thm. 2). The other cases are consequence of Lem. 11, Lem. 9, Lem. 8 and the fact that the layers m and me does not change the separating power.
D STONE- WEIERSTRAS THEOREM WITH SYMMETRIES
This section presents our extension of the Kkone-Weierstrr theorem dealing with functions with symmetries. The scope of this section is not restricted to graphs even tensors and will deal with general spaces and general symmetries. To illustrate it, we will present applications for the PointNet architecture Qi et al. (2017). Our approximation results for GNNs (Theorems Thm. 5 and Thm. 6) are then obtained from these theoretical results applied to tensors and the symmetric group in Section D.9
21

---

takes its values in Published as a conference paper at ICLR 2021
D.1 GENERAL NOTATIONS
As explained above, we are dealing in this section with a much larger scope than graphs and permutations. We first need extend the notations introduced above. The notations introduced below will make this section self-contained.
If X is some topological space, and S X, denote by F its closure
If X is topological space and Y = IR" some finie-diieensional space, denote by C(X, Y) the set of continuous functions from X to Y.
Moreover, X is compact, we endow C(X,Y Y) with the topology of uniform convergence, which is defined by the norm, f - suPxex (x))) for some norm ||-|| Y.
If G is finite group acting on some topological space X, we say that G acts continuously on X if, for all g G + g is continuous.
If G is a finite group acting on some compact set X and some topological space Y, we define the sets of equivariant and invariant continuous functions by,
Cr(X,Y)= (f C(X,Y) Ye EX, Vg E G, flg z) = f(x)) (, = {f e C(X,Y) Vr e X, Ag E G, f(g z) = f(z))
Note that these definitions extend Definition to general group.
Y = R", we denote the coordinate- wise multiplication, or Hadamard product of y. y E Y simply by yy (viv'..... ............. linear space and stable by multiplication.
ky ....
Y. We say that subset C IR" is subalgebra of E2 if is both
This product in turn defines a product on Y( with R by, for f.g E C(X,)), 8). fg: x (())(()).
Rp
In addition, we also extend the scalar-vector product of Y R to functions: if g E C(X, R) and
I C(X, Y), their product yf is the function gʃ + f(x) Given a set of scalar functions S SCC( I) and a set of vector-valued functions C C(X, Y), the set products of functions of these two sets will be denoted by,
S
Moreover, we denote by 1 the continuous function from some to RP defined by x + (I....,I) 1). In particular, if f is function from X to R. f1 denotes the function + (f(z).... f(x)) which goes from to Y = TRP. Finally, we say that F C C(X, Y) with Y being some Rp is subalgebra it is linear space which is also stable by multiplication.
D.2 SEPARATING POWER
We recall the definition of separating power that we introduced above: Definition 14. Let F be a set of functions f defined on set X, where each f some Yy. The equivalence relation p (F) defined by F on X is: for any x, x' X,
(I, E (
of E
For function f. we write p (f) for p ((f)).
Separating power is stable by closure:
Lemma 15. Let X be compact topological space, Y be some fiitee-dimensionl and F C C(X,Y). Then,
p(F) = (F)
Proof. As AsF is more separating than F.c.e. p (F) ((F).
Conversely, take (x, v) $ (F). By definition, there exists h E F such that h(x)) * h(y) so that if
=11h(>> h(v)],, 0 (for some norm ||-|| Y). As F, there is some F such that
22

---

Published as a conference paper at ICLR 2021
supx 1/- fll $ 3- Therefore, by the triangular inequality,
2
<= [[h(x) h(v))l - llf(()) - h())l + (lf(2) - f(y)ll + +1f((+) - h(v)) || - 3 /ec [f((x) =(((lf(())=))
f(v)l
3
It follows that [lf(z) - f())l N 3 > 0 so that f(x) * f(v) and (z.1) & P
D.3 APPROXIMATION THEOREMS FOR VVLUED FUNCTIONS
We start by recalling Weiie-Weissssssss theorem, see Rudin (1991, Thm. 5.7).
Theorem 16 (oone-WWierstrrss). Let X be a compact space, and FF be a subalgebra of C(X, R) the space of real-valued continuous functions of X, which contains the constant function 1. If separates points, i.e. p (F) {(x,x) : X}, then F is dense in C(X,B),
We now prove an extension of this classical result due to Timofte (2005) allowing us to deal with much smaller F by dropping the requirement that F separates points.
Corollary 17. Let X be a compact space, and F be subalgebra of C(X, continuous functions of X, which contains the constant function 1. Then,
((X,)) R) the space of real-valued
F {f E :
Note that if F separates points, we get back the classical result as every function satisfies {(r, .)):
x E } S (()).
Example 18. The invariant version of PointNet is able to learn functions of the form Σ, fz; for T C(RP, R). We can apply Corollary 17 this setting. Consider the case where X is compact subset of TRP F = {i + (E D= ((=)( f E ((X, E C(RAA [R)]. F is subalgebra of C(X, IR) (indeed of Cx,X, R)) which contains the constant function 1. Then, easy to see that is defined by (a * x))(() = x4 for all i (see Lem. 31 for
(F)= = {(z, a * z)) S,), where formal statement).
Now note that for function f E C(X,B)) the condition {(x, o x), E S S pf) is equivalent to f E CX, R). So that Corollary 17 implies that F = Cr RR) which means that PointNet is universal for approximating invariant functions. This was already proved in Qi et al. (2017).
We now provide a proof of Corollary 17 for completeness.
Proof. The first inclusion J C [ E B(X, the one given below Theorem 4 so we focus on the other one.
p() follows from the same argument as
For every E X, let xy denote its p (F)-class. The quotient and the canonical surjection are: X= X/p (F) = {xF, x E }} and T X + Xx,, =z(x) FFF-
A function g X + R factorizes as g 9 KFF for some 9 Xx= + R if and only p S (g). In this case I is unique, since FF is a surjection. In particular. every ʃ E F factorizes uniquely as f - FF. f: Xx= + R. and f = =f.. f = F} clearly separates points on Xy. We refer to Munkres (2000, $22) for the properties of the quotient topology. In particular, by the properties of the quotient topology on X,, f is subalgebra of C C(X,, R) and Xx is compact. Hence, we can apply Theorem 16 to f and dense in C(),,R).
Now take f E IR with p (F) C (J) and we show that f E E Again, p p(F) S pS) implies that f = f o π.. Let e > O. By density of F. there some E $ such that supay [Mxx)) [ S e. But, by construction of F, there exits h F such that h प h. Thus.
sup [((z) - f(x) = sup M(<{(x)) - f(Tx(()) sup (b(x))) f(xx)) Se. zeX
zex
azEXr
As this holds for any > 0, have proven that F.
23

---

Published as a conference paper at ICLR 2021
D.4 THE EQUIVARIANT APPROXIMATION THEOREM
We first need to extend Corollary 17 to vector-valued functions. For this, we need to have a vector- valued version of the assumptions have to be made.
theorem and as shown by the example below additional
Example 19. We consider now the equivariant version of PointNet corresponding to the particular case where X is compact subset of (R")", Y I and F = {ir + (f(z)).... fx.)). f C(R, ]. Then clearly FF is a subalgebra of Cr(X, Y) containing the constant function and p (F) = (x),,r),,
X). Hence if Corollary 17 would be true with vector-valued functions instead of real-valued functions, we would have that F is dense in C(X, Y). But this can clearly not be true as F C Cx Y) which clearly not dense in ((X,Y)
We now present extension of Corollary 17 also due to Timofte (2005); Proposition 20. Let X be compact space, Y = RR for some 2 1. Ler F S C(X,Y) If there exists a nonempty subset S C C(X,R) such that:
S FF and, p ( (
(17)
Then we have
プ= == -=(EEC(X,), (FF (F) 1(x) S(0) F(t))
(18)
where F(x)= FJ. Moreover in (18), we can replace p (F) by (S).
Note that in the particular case Y = IR and if F is subalgebra of C(X,R), R)) then can take S = F in (17) and the constant function
F. then F(x) = I2, so that we recover Corollary 17.
Now consider the case where F is subalgebra of C(X, IRP). We need to find set S E C(X, R) satisfying (17) i.e. with a better separating power than F but containing real-valued functions such that sf E FF for all
S and E F. In the sequel, we will consider the set Fsout {S E C(X, R) : fl E F). We clearly have Fs F C F since F a subalgebra. Hence, this setting, Prop. 20 can be rewritten as follows:
Corollary 21. Let X be compact space, Y Rº for p. G be finite group acting (continu- ously) on and F C C1 (X,, Y) (non-empty) set of invariant functions associated to G.
Consider the following assumptions,
1. F is sub-algebra of C(X, and the constant function 1 is in F.
2. The set of functions Fscat S C(X, R.) defined by,
Fecal = {f ((
satisfy,
p PF 5 (FF
3. For any x. E X, there exists f E F such that (xx has pairwise distinct coordinates, i.e., for any indices i,j [l....,p} with + f(x) + f(x)
Then the closure of F (for the topology of uniform convergence) is,
T= (()
Note that Assumptions and 2 ensures that (17) is valid, while Assumption 3 ensures that F(x) = RP. Unfortunately, in the equivariant case, the condition p (Fscat) S pFF) is too strong and we now explain how we will relax it.
For the sake of simplicity, a fixed number (corresponding to the number of nodes), X be a compact of graphs in pg* and == F" with FF = Rº for some 2 1. We define the action of the symmetric group S, on X by (a x (()) = Zı.j and on Y by (a y)a(1) y: E IR.. Hence the set of continuous equivariant functions Cr X) agrees with Definition 1.
consider here the particular setting adapted to graphs: let 2 be
24

---

Published as a conference paper at ICLR 2021
Now consider the case where F S Cg(X,Y) is subalgebra of equivariant functions. Then, f Fscol needs to be invariant in order for fl to be equivariant and hence in F. As a result, we that Fseat will not separate points of X in the same orbit, i.c. x and o But these points will typically be separated by F, since for any f E F, we have f(a x)) = a * (xx which is not equal to f() unless is invariant.
We see that we need somehow to require a weaker separating power for F. More formally, two isomorphic graphs will have permuted outputs through an equivariant function, but should not be considered as separated. Let Orb(x) = fo any equivariant function f f (x, YY,Y), for any 2 E Orb(z), we have f(z) E Orb(f(x)). Then let Y + Y/S, be the canonical projection m(y) = Orb(y). We define
E Sn) and Orb(y) = for + E Sn). - For
(x.z')
Vf E F, Orb(f(x)) = Orb(f(z'))
E E Sni f(o f(x').
In particular, see that a' E Orb(z) then (x,x') ( F) for any F Cx Y). Moreover, two graphs x and x' are p ( F)-distinnt if there exists a function f f F such that Yo, f(o x) of fa'), i.e. the function f discriminates Orb(æ) from Orb(x') the sense that for any 2 E Orb(z) and 2' E Orb(z'), we have fz) * f(z').
To obtain an equivalent of Proposition 20 with Cg(X. Y) replacing C(X,Y), we are able to relax assumption (17) to (Fscat) S (IT F). Our main general result in this direction is the following theorem (proved in Section D.7) which might be of independent interest:
Theorem 22. Let X be a compact space, Y =RP
Re for some p. G be a finite group acting (continu- ously) X and Y and F S C) (non-empty) set of equivariant functions.
Denote by π. : Y - Y/G the canonical projection on the quotient space Y/G. Consider the sollowing assumptions,
1. F a sub-algebra of C(X,Y) and the constant function 1 in F.
2. The set of functions Fseat C C(X, RR) defined by,
Fseat E ((X
satisfy,
(FFcatt) E p o)
Then the closure of F (for the topology of uniform convergence) is,
F= {f ( Vo E X, f(z) e F(x)),
where have:
f E F}. Moreover, if = {(t,)) E |p : Vy E F(z), = v₁ then we
(vER v(i.)) [(x), y: = =
Example 23. We now demonstrate how Theorem 22 can be used to recover the universality results in Segol & Lipman (2020). In this paper, the authors study equivariant neural network architectures working with unordered sets, corresponding in our case to X = Y = IR" and the group being the symmetric group S,- They show that the PointNet architecture cannot approximate any (continuous) equivariant function and that adding a single so-called transmission layer is enough to make this architecture universal.
Indeed, PointNet can only learn maps of the form E R + universal in the class of equivariant functions, as shown by Segol Lipman (2020, Lem. 3). Now, their transmission layer is map of the form layer precisely adds a large class of functions to F ([f(11,)) Σ, (zx.))..... f(zn. E. (xx)))))), e C(R x R R), g E C(R. R*), h 2 1). F is still an algebra and as shown in Example 19, we have (F)= = (2. E X}. Moreover, we have Fecat C, R) by Lem. 33 in particular, get P (F scat) = {(x, o * r), x e X), so that we obviously have p (Fscat) S p p(T o). In summary, Theorem 22 implies the universality of PointNetST in C5. (X, Y).
which are not
E + (1"x)1. Therefore, in PointNetST, adding such
25

---

Published as a conference paper at ICLR 2021
D.5 A PRELIMINARY VERSION OF THE EQUIVARIANT APPROXIMATION THEOREM
We start by proving a version of Theorem 22 with a slightly weaker condition:
Proposition 24. Let X be compuct space, Y Rp for some p. G be finite group acting (continuously) on X and Y and C Cc((X, ) a (non-empty) set of equivariant functions.
Consider the following assumptions,
1. FF is subalgebra Cr(X,Y).
2. The set of real-valued functions Facal C- [C(X,R) defined by,
Fecal = (f E C(X, f1
satisfies.
P (Fsaa)) E 2(2,2')
E X Bg G, (g 20 E (FF).
Then the closure of F (for the topology of uniform convergence) is,
F= (E)
Vo E E, E())
(19)
where =(x)= [ FEJ
The proof of this theorem relies two main ingredients. First, following the elegant idea of Maehara & Hoang (2019), we augment the input space to transform the vector-values equivariant functions into scalar maps. Second, we apply the fine-grained approximation result Cor. 17.
Proof. As uniform convergence implies point-wise wise convergence, the first inclusion is immediate,
c C=(X,Y) P spf), e X, f(x) E F(r))
The rest of the proof devoted to the other direction.
For convenience, denote by the family of linear forms associated to the canonical basis of RP, i.e.,
y: < i sis p) C C(Y,R.
Define our augmented input space as X = X x क. As + is finite and X is compact, X is still compact space. We now transform F, a class of equivariant functions from X to Y, into F class of maps from X to R. Define
(1) ffF
We check that f indeed subset of C(X, RR. Indeed, as finite, is equipped with the discrete topology. Hence, each singleton {5) for şo E + is open in t and it suffices to check the continuity the first variable with & fixed. But, f F. F (((()) is continuous as a composition of continuous maps.
We can now apply Cor. 17 to F C C(X, RR. Therefore, the closure of 5 in C(X, R) is.
F= f E C(X, R)
f
(v)), V(x,,) e X, v(x, F(1
We now show the equality of (19). Take f in the right-hand side of (19), i.c. h E CB(X,Y) such that p (F) C p (h) and h(xx) F(x) for all x E X. We show that h, defined by h (ar, sp) (ph())),
belongs to F using the result above.
As h is continuous, by the argument above, (I. se(h(z))) is continuous on X²
26

---

Published as a conference paper at ICLR 2021
We check that (F) S (1))
Take (z, (U, 1/ E X such that, for all f E F.
p(f(=)) (f(()),
(20)
and we aim at showing that p(h(x)) - (h(y)).
To gain information from (20), we apply it to functions of the form f'1 with E F seal- By definition of t this translates to [(x) = [w), for any E Fseat- Therefore (x. y) E p (Feeat) and so there exists G such that (g v. p (F). Plugging this into (20) and using the equivariance of f.
VFEF, v((()))) = rh f(x))
As G acts continuously on Y, both and ++ (ggg are continuous and, as a consequence of the equality above, coincide on F(z). But we assumed that h(x) E F(x) and therefore the equality also holds for h, i.e. ((((x)) <0g l(x))).
Finally, recalls that, by assumption, p (F) S (h). Therefore (g x. v) p (F) implies that lig x) = h(y) and, combined with the result above, ((h(x)) = (h(y))
We verify that, for a E X, t, ((((x)) belongs to F(r). Indeed, recall that h(z) e F(x). Therefore, as yp continuous, <(h(2)) is in (FF()) which is included in F(x).
This shows that h (x,zp + (p((x)) is in Consequently, for any e > 0, there exists f E such that,
Vx E X, Vp E Φ l=(h(z)) ((f())) c. If Y = R' endowed with the infinity norms coordinates, by definition of 4, this means that, Va E X, [1(x)) s(x) <..
Remark 25. In the particular case of G C S, being group of permutations acting TR by, for E G. R.,
Wi (l.....p). (g x); = Ig))(())
the functions of f are indeed invariant, as shown by Maehara Hoang (2019). For this, a left action on & is defined by, for g G, up E Φ
E R2, (g- (x) = -
In other words, the action of on the linear form associated to the hth coordinate yields the linear form associated to the 9 coordinate. One can now check that the functions FF are invariant.
D.6 CHARACTERIZING THE SUBALGEBRAS OF RP
Before moving to our general result, we need to study the structure of the subalgebras of RR For this, we will use the following simple lemma.
In the following lemma, R[XI....,, Xpl denotes the set of multivariate polynomials with indetermi- nates (and real coefficients).
Lemma 26. Let C 12P be a finite subset of There exists E[X,,..... Xpl such that Pic. the restriction of P to C, is an injective map.
Proof. Let 1 polynomials, define,
E IPP be distinct vectors such that {x ,..., " C. Similarly to Lagrange
(X1 x 1
P(X1. ..........
X,)=
Σ
(21)
27

---

Published as a conference paper at ICLR 2021
which is well-defined multivariate polynomial. Note that, seeing X (X1, ...,..., Xx)) as vector in R", it can also be written as,
m
X x 1
P(
x))
Σ
(22)
x
By construction, P(x') = and therefore P is an injective map on C Lemma 27. For subalgebra A of?, we define:
J = (i E fl,...,... :o E A, 2j = 0}
I = ((..)) (J9) Vo E A,, x, x₁}
Then, we have: :
A = E RP v(L.) E z = zj Vj E J, = 0}.
Proof. Before proving the general case, we focus on the situation where A will turn out to be the whole I..
Assume that the two following conditions holds,
Vi * j E A,
(23)
Vi, A
(24)
Our goal is to show that, under these additional assumptions, A= RP. We divide the proof in three parts, first show that A using (24), giving that A is closed under polynomials, then that there is x E A with pairwise distinct coordinates thanks to (23) and finally that this implies that A is the whole space.
Note that if p- = 1, (24) and the linear space property of A immediately give the result.
Here we prove that (24) implies that 1 E A.
First, construct by induction AA such that r; # 0 for any index i. More precisely, our induction hypothesis at step j E {1....,)) .P} is,
Fr E A, sisisj #
(25)
By (24), this holds jorj= 1
Now, assume that it holds at 1 for some p ツ > 2 and take A such that x; A 0 for any 1 < i < 1 and y E AA such that Jj + 0 by (24). By definition of x, the set,
E I1 sisj - Ae; + yi = 0),
is finite. Thus, there exists À E R such that Λr; + # 0 for any < i < j - and for i= too as Ij = and y # 0. As A is subalgebra, Ar + y E A and this concludes the induction step.
Let A be the vector constructed, i.c. such that x, for every index i. We prove that 1 E AA by constructing 1 from J. Indeed, using Lagrange interpolation, take P E [ such that P(x;) = for every i. (Note that this noes not matter if some are equal, as the 1 would also be the same.) Finally, as A is subalgebra, PP:)), which to be understood coordinate- wise, is in AA and so is 1 = (xx).
We show that the previous point and (23) imply that there exists vector in A with pairwise distinct coordinates, i.e. that there exists x E A such that, for any i * j. x; * xj. Using ij (23), for any i < j. there exists أ E A such that 2/ # x. We wish to combine the family (x"))ss into single vector.
For this we use Lem. 26. Sceing each collection (x )is as vector of (p((-1)/2 1)/2 we define
C. = {(xg)) Dis : 1 < & < p}. which is a finite subset (of cardinal p) of [g(p-1)// 1)/2 By Lem. 26, there exists P E R R[X,..... 1)/2-1//2 such that P is an injective map on C.
28

---

Published as a conference paper at ICLR 2021
As A is subalgebra and 1 E A, the vector,
P (x ((aP)ses)
P P(<x))ic))
P ((og))2s)
is in too.
We now check that this vector has pairwise distinct coordinates. Let 1 < ks then 2fth & x and therefore (x)) J2y # (z )es.. By construction of P, P (a)))<s) * P (E2))
i.e. P ((x )<e)), # P ((r7)))))) Thus, P ((a*))=<)) A has pairwise distinct coordi- nates as required.
Finally, we show that = R.. This a direct consequence of the point above and of Lagrange interpolation. Indeed, take any y E R2 and denote by AA the vector that just constructed with pairwise distinct coordinates. Therefore, by Lagrange interpolation, there exists P [ such that P(xx) ys for every i (1, (1,...,P) As A is sublagebra and E A, P(x) E A and hence E A.
Finally, return to the general case. We introduce the set of indexes of I and J which appear in the result and use them to reduce the situation to the previous case. Define,
J {j (l. Vo E A, Iz =0
1 1= = ((i.) (J92; Vo E A, z, = =.=z}}.
and denote by .A' fx E Rº f) E I, x, = . Vj By definition, it holds that A C A'.
J. 2j =0), which is also subalgebra.
By construction, I is equivalence relation J and denote by / its equivalence classes. Let p' = [C and choose i i1...., by representatives of the equivalence classes. Consider the map,
R.P
Re
p::
Tii
).
sp is algebra homomoprhism that (pA) is subalgebra of RP But, by construction of I and J, (PA) satisfies (23) and (24). Whence, by result in this particular case, (p(AA) R.
However, A C A' implies that (pA) S ((A') S Rº'. Therefore, RP' ((A) ((AA). But, by construction of y,, is actually an injective map on A'. Therefore, we deduce from sp(A) (pA4)) that A', concluding the proof.
D.7 PROOF OF THE MAIN EQUIVARIANT APPROXIMATION THEOREM
We can now fully exploit the structure of subalgebra of IF thanks to the results above, and in particular relax the second assumption of Prop. 24 to give our main theorem 22. We first prove the following lemma.
Lemma 28. Under the assumptions of Thm. 22, for any H C G subgroup, for any 2, E X,
VFEF, 3g H, f(g x) = f(v) -
3g E H, VFEF, flg-a1 x) f(u).
In particular,
(x,y) E ((TOF) = e G. (g x, v, E (
Proof. The reverse implication is immediate so we focus on the direct one and prove its contraposition, i.c.
Vg H. 3f E F, f(g 2) # f(y) ff F, Vg E H, f(g x) # f(y). To prove this, take advantage of F being subalgebra and H being finite. Let H [9i..... ... gn and define,
A= (((g)) x), .., s(g I())
29

---

Published as a conference paper at ICLR 2021
As FF is subalgebra of C(X, R"), A subalgebra of R2 with = p(h + 1). By Lem. 27,
A= {= E Rt V(i.j) E I, 2, = Vj E J, = 0}
where I and J can be chosen to be,
J U p) E 2j = 0}
I= ((i,)) (I,...,pp) V2 A, 2; z))
As is equivalence relation, element of A is uniquely defined by its coordinates equivalence classes of Therefore, one can choose 2 E A such that 2 = = (i.5) E I. By definition of A, there exists f F such that (f* ,),,,.,, f"
f).
We now check that
f is indeed appropriate. Take / E [I,...,h), assumption, there exists f E F such that f(g x) o f(w), i.e. there exists i {l,...,P) P] such that f(g x)s f(y). Therefore, ((I- 1)p + i, hp + i) cannot be in I so that 2(1- 1)pti # 2hp+1, ie. (" r); (y))
hJ. we want to show that f x) * f [w]). By
We now prove our main abstract theorem.
Theorem 22. Let X be compact space, Y = IP for some p. G be finite group acting (continu- ousty) on and Y and F S Cg(X,Y) a inon-empty) set of equivariant functions.
Denote by π Y - Y/G the canonical projection on the quotient space Y/G. Consider the following assumptions,
1. F is sub-algebra of C(X, Y) and the constant function 1 is in F.
2. The set functions F Fseat S C(X, R) defined by,
Fecal = {f E C(X, f f1EF)
satisfy,
(FFocat) S (T
Then the closure of F (for the topology of uniform convergence) is,
F= [ E CE((,Y): _ ( Vo X, f(x) E F(t))
where (())=((())) F}. Moreover, if ((t,j) E bp: Vy F(x), ys = 8, then we have:
F(x) (y E V(i.j) T(x), y: = =
Proof of Thm. 22. By Lem. 28, the second assumption of Prop. 24 is also satisfied. To get the
conclusion Thm. 22, note that F(x) ) is now a linear subspace of a dintee-dimsiinaal vector space
and therefore it is closed. Thus, F(x) F(x) which subalgebra. Applying Lem. 27 to F(x) and noting that, necessarily
F(x) by assumption, gives the result of Thm. 22.
D.8 PRACTICAL REDUCTIONS
Though the results we proved above were formulated using classic hypotheses, such as requiring F subalgebra, we can give much more compact versions for our setting. We also reduce the assumption that (F.cat)
( F) to more practical one.
We start with the invariant case.
Corollary 29. Let X be a compact space, Y = = F = RdP be some fnite-dimensiondl vector space, G be finite group acting (continuously) on X and J C C((,Y) a (non-empty) set of invariant functions.
Assume that, for any E C(R2, and f.g F,, I x (((()) EF.
Then the closure of F
F Ff ((F) (P)))
We slightly change the definition of compared to the statement of the lemma to add J², which does not change the result.
30

---

Published as a conference paper at ICLR 2021
Proof. We wish apply Thm. 22 but for this we need G to act Y. Define (trivial) action of G on by,
Vg E G, by E v=g.v=y. With this action Y, Cx(X (x, Moreover, Y/G = -YCC=Y;TYY. Y/G is the identity so that ( F) p
Our assumption clearly ensure that JF is indeed subalgebra and contains the constant function K.
All that is left to show to apply Thm. 22 is that the set of functions Fseat C C(X,R) defined by,
Fecal = {f E ((X, fle
satisfies,
pF [P(F).
Take (x, $ p (F) and show that (z. & p (Fscut). Indeed, by definition there exists E F. i E (1.....P) such that [(r); * f(y); Let E C(B, R) defined by 1(z) 2; and E C(R, IF) defined by, for 2 F, h(2) (1(=). ........... ,[{)) I(=)lf Then, by assumption h o F. But h (To f)1 with f EC(X, RR. so that, by definition, lo E Feeat- Moreover, t f(x) + #o f(y). (Q(XRR),
Therefore, (z,3) $ (Fseat). Therefore, we can apply Thm. 22. We get that,
F= (f
(f), Vo X, f(x) E F(z)),
and
= (v v(ij) I(x), ys = =
with [(x) given by,
[(x) = ((i.)) E fl......p p) vy E F(x), y1 = y3}
To conclude the proof, F(x) = R2 = Y.
show that [(x) ((i,t) : p)), which will imply that
Indeed, the constant function ++ (1, p) is in F by assumption. Therefore, [(x:) is reduced to ((i,)) : pp)..
In our previous version of our approximation result for node embedding, we did not allow features in the output it would have made the statement and the proof bit convoluted. With this new assumption, this is much easier.
Corollary 30. Let X be compact space, Y F", with = R and = Sn the permutation group, acting (continuously) X and acting F for Sa. F".
Vi e (L....,p,, (o z), To (())
Let F C CE(,FF"") be a (non-empty) set of equivariant functions. Consider the following assumptions,
1. For any C(F2, f.g F.,
- (((())) (MM EF.
2. EF
Maxi E (())
Es(w)s E EF.
Then the closure of F (for the topology of uniform convergence) is.
== C (F(xE
For this we need a handy lemma, whose proof relies on a result about multi-symmetrie polynomials from Maron et al. (2019a).
31

---

Published as a conference paper at ICLR 2021
Lemma 31. Let F = Rp be some that.for for any a E Sn, (#1....., Tn) ) * (Ur(I)...... Ya(n)). Then, there exists E C(F, R) such that,
space. Take 21....: Zn: .1..... Yn F such
Σ h(x)) +
h(y.).
Moreover, h can be written as h(x) h (2) he (22) kp(xp) for any If with hi...., he C(RR, R)..
Proof. By Maron et al. (2019a, Prop. 1). there exists a1..... Op non-negative integers such that
Ei aa 222 Vip + Ei=1 Vi 2o Mip Taking + Ti x22 ......... Fip yields the result.
Proof of Cor. 30. We want to apply Thm. 22. With our first assumption, the first assumption of Thm. 22 is easily verified.
We now focus on the second one. As in the statement of Thm. 22, define Fecal S R) by.
Fsent [S E
We have to show that p (Feeat)) C p( For this, take x, & ( There exists f F such that for any Sn. 0. f(x) # fly). We have to find / E Facul such that ((z) & 1yy). In other words, from function
which discriminates between æ and y we have to build function in R.
First, we exhibit function which discriminates between x and y. Apply Lem. 31 to the vectors f(x) and f(y): there exists ho C(F, R) such that Σ.= (f,() + E ho(f():)).
To fit the assumptions, build h C(F,F) from ho by h : F (h.(z)...., Take E C(F,F) such that g(z) = (Zi...., 21) for any 2 E and E C(X,R) defined by, for X, I(w) E ho:)(w;)). Then, 1(x)) * 1(y). All we have to do is show that I Fscat, i.e., 11 E F. This where the two assumptions we made come into play. Indeed, the first one implies that h o f E F and the second gives
F.
Σ (((()))
Σ (((())) EF.
Finally, the first assumption ensure that,
2 ( g Σ (EM(Ca))) ( EactEn) EF.
But this last function is none other than /1, which shows that E Fseat as required. We have successfully verified the hypothesis of Thm. 22. Therefore, the closure of F is
F= == Cx( (FF) SP()) Vo X, (()))
with
F(x) = =y=)=EEER FF V(iY,,))) M(x), yar = Ni.')
and
= ((, E (fl...., nn x {1..... ..).:)))) : E F(z), y1." = yir
To get the desired result, we need to get rid of the condition "f(x) E F(r)" in the description of F. Fix X.
First, we show that
= e F V(i.j) J(x), y1 = ;=
with
( (1)...,)): y y3
(note that the equalities here not in I anymore but in F). The direct inclusion "C" is immediate by construction of Jxx) so we focus on the reverse direction. For this, we show that the 4-tuples (i,"',i.)) of (x:) necessarily satisfy /f j" and (i, E (xx.
32

---

Published as a conference paper at ICLR 2021
First note that, by the first assumption, the vector yd F" such that y (1. for i {I....,n] n is in F()). Indeed, take the constant function always equal to (1.2..... p) as h. Now, consider 4-tuple (i, (. of (xx) and we show that, actually, (i.5) E [zz) and i' = j'. As y in F(x), and uf = i', DiS = J'. ji,'' E ((r) implies that j' = Consider, k E (1)....p) We show that, for any E F(x), Mi.k Mj.k- But such a y can be written as y = fa) for some F. Consider, the function h E C(IF, F) associated to the permutation (i' k), defined by.
2 2H (z a)(1)...... 2(x R)(m)) = (21..... -1, 2k, 20 2p-1..... 2k-1, 25,, 2k ,p))
By our first assumption, + particular, (i, ".,", E [2)). h(gb)e h(y))e, Le. vi = Yy Therefore, (i.j) (z)).
h(f(2)m)) E F so that (h(31)..... h(ya)) E F(z). In
= 31 Indeed, take y E IP" V(i. E J(x), V/: - My. We show that all the constraints of ((x) are satisfied. Indeed, take E I(x). We have shown that (i:j) E (zz) and i' = j' so that yr = yj and in particular
Finally, we can conclude that F(x) 2 {y E Fn v(i,j) E J(x),
yarr = Uja' Therefore, this finishes the proof of F(z) C f& Fm v(i.)) E J(x). y リ₃}-
Thus.
F(x)= = tu E F" ((I.) E ((x), yi = ;
with
J(z) ((i.)) {1, [l.....m]] n2² y y= =
We have proven so far, that,
(f), EX, f(t) E F(x)) S U E F = (IX
Take h E Cc((X such that p (F) S (h) and fix E X. Our goal is to show that, for any (i.j) E J(z), h(z); h(r), so that h(z) F(z). But, (i.j) [z). then for any f E F. f(z); = f(x), so that (i f(x)== f(z), where (ij) denotes the permutation which exchanges i and j. Moreover, as (i E Sn, by equivariance, this means that j(( = fxx for every f E F and therefore that ((ij) x) (F). By assumption, we infer that ((ij) xr, x)) E (() too, i.e. that ((i xx = h(z) and so that h(z); = h(x), by equivariance, which concludes our proof.
D.9 REDUCTIONS FOR GNNS
We now present a lemma which explains how to instantiate the two corollaries above in the case of GNNs by replacing continuous functions with MLPs.
Lemma 32, Fix X some compact space, n. 2 1 and FF a finite-dimensional feature space. Let Fo C U C(X, Rea) be stable by concatenation and consider,
F {
(.(()))))( f E Fonc(X,R"), m m:R: R + FF MLP, h 2 1] CC(,F).
Then, iF) C C(X,F) is the set of functions obtained by replacing the MLP m. in the definition of F by an arbilrary continuous function, {FF satisfies,
1. -(F(
2. -
3. For any h E C(F2,F), (.g
I x+ M((())) E E(F).
4. If. for any f F,
Σ f(x); Σ f(x)...., Σ ((x)s Eno)) E EF,
1=1
then, for any f E(F)
n
n
x +
Σ
f(x), Σ f(x),
Σ f(z);
E EE(F)
i=1
33

---

Consider the action of Published as a conference paper at ICLR 2021
5. F is equivariant w.r.t. the action described in Cor. 30, is {FF).
Proof. Define,
8(F far -
C(RR*, F), h 1).
As MLP are continuous and by the universality of MLP compact set (see Section C.I),
FCE(F)
This already implies 1. and that p (F) S EP(E(F)) E (FF) Using Lem. 15 yields 2.
We now show 3. Take C(F2, .F). f.g E Fo. E E(( ((X,R** and E C(R",, I E C(R" 2 F). All we have to show is that,
x + (M((((()))
But as Fo stable by concatenation, æ + (f()),g(x)) Rhyth is still Fu- Moreover, y E Bhrth, + h(m(y1..... "................. ..h,), +1... . th, is also in C( t ,)) which shows that
the map above is indeed in E(F). The last two points are immediate consequences of the definition of {(F).
Thm. 5 and Thm. are now obtained by combining Lem. 32 with Cor. 29 and Cor. 30.
E PROOFS FOR EXPRESSIVENESS OF GNNS
Note that in the Theorem 6, the additional stability assumption is "almost" necessary to obtain the result. Indeed, if the result holds, i.e.,
F E (x(C (())
then one can show, that, if f E F, then
j:zH +
E(t)) Σ f(x).... I(t)) EF.
Indeed, f F so that it has a weaker discriminating power than F, so that (FF) = = sP(f). But, by construction of J. (f) S p ( so that (Fo) S (i) As is also in Cr(XFF"), JEE.
E.1 EXPRESSIVITY OF GNN LAYERS
Lemma 33. Fix Fo, Ff (non-trivial) finite dimensionnal vector spaces. G G=S, Sn on Fo x paxk defined by.
Yo E Sn, Va E Fo. VI E gank o (2) = (x" ,
Io fo Io
Let K C Fo x Fox be compact set. Then, the set of functions from C.F Fo x F x form,
to F1 of the
(x,, x) - fo 0
fro
(I
j= w=
where fo Fn RRA. F1, Sg Fo Raa -,...,. I are multi-lined perceptrons and h > 1, is dense in (K
Proof. Denote by F C Cr(K, F1) the set of such functions. To prove that F C,(KK F1), first apply Thm. 5.
We get, that.
F= = ( EFF paxk :
34

---

Published as a conference paper at ICLR 2021
We now characterize p (F). Actually, it is equal to p (inc) = {((x", (((=),)),(0) (v),))))) E (Fo x Roxk)? Bo Sn: show the reverse, Take (x x), (y/ y) E Fg x Fo such that there does not exist o Sn such that (x0 x) = -- (y", 19). If xf # yd there exists fo Fo + F1 MLP such that f f(=") # f(y so that ((x", (v) (FF).
a- 0." .y}. As the functions of F are invariant, p (inv) S PFF). We now
Otherwise, there does exists Sn such that (Io 1(1) Fo 2(m) (y1 (y1:-..;; Un) by
definition of the action of G Sn- Now. apply Lem. 31 with F & Fh. the universality of MLP and use the decomposition given to get fy Fo + R j 1...., such that E fu((),.) + Σ E-=IT (Vs,))). Choosing an appropriate MLP fo R B1 yields that ((>", x), (...)))))))))) (F)).
Hence, have shown that,
F= E Fo paxk [F) : (ino)) ( (())
Cr x Fo Faxk ,F)).
E.2 APPROXIMATION THEOREMS FOR GNNs
We now have all the tools to finally prove our main result.
Theorem 34. Let Kdisor S Gn F.. K C FB be compact sets. For the invariant case, we have:
MGNN, ( CK F): p (2-WLI) P(T
2-L.GNN, = (K, (2-WWL.) (/)
k-IGNN, = (K)): (I--LGNNI) S 2 (
P(AWL))
K-FGNN, = = (KK,F) P (k-FWL,) (P()
For the equivariant case, we have:
MGNN E Cr(Kissrr) IF"): (2-WLL)) [
k-LGNNE (JECE(K,F")) p(K-LGNNE) S (p()) (1 F=), S
k-FGNNE (JECA(K,FF) F"): (k-FFLL)) (()
We decompose the proof with an additional lemma.
Lemma 35, Let Kdiser S On x F.. K S Fb be compact sets. For the invariant case, and any k 2 we have,
MGNN, (s E (Kdiser, BY: (MGNN,1 S CP(}}
K-LGNN (K, (K-LGNNI) (())
T-FGNN, CK, P (K-FGNNN)) (())
For the equivariant case, and any k 2 2, we have:
MGNNE [
F): p (MGNNE) S SPD}} E (IECC((KF)) p (K-LGNN)) [p(
k-LGNNE
k-FGNNE
= =(, (k-FGNNF) CP
Proof of Thm. 34. The theorem is direct consequence of Prop. 13 and Lem. 35.
We now move to the proof of Lem. 35.
Proof of Lem. 35. First, focus on the invariant case. Let F denote MGNN,, k-LGNN, or k-FGNN, and X be either Kaiser K so that X is compact and F S CX,,F).. Applying Thm. 5 directly gives,
F= (s E ((()
35

---

Published as a conference paper at ICLR 2021
which is the desired result.
We now move to the equivariant case. First, let us replace MGNNE g by another class, which is slightly simpler to analyze. Define,
MGNN F" {mE ((1 X) Id + IT o ..... c Fi Pr:
F. F+1 message passing layer, t .,...::....... T, T 2 1,X (0.
holds that p (MGNN E² (MGNN&) è) and.
MGNN g C & - {f E CE (Kd(errrrr: F²)) (MGNN k) S pf))
{f E CE Kiiser: F²): (MGNNE E
Therefore, if we show that, MGNN (f E
F (MGNNE:) (P()
we will have the desired result.
Let FF denote MGNNE, gy, &-LGNN& or K-FGNNE and X be either Keiter or K that is compact and F C CE(X,FF) We now wish to apply Thm. 6, but we need to verify the stability assumption
first. Thus, we show that, for any f E F.
Σ f()), f(x)...... ...., f(1))) EF,
x +
If F = M. MGNNE- f is of the form,
mg ((1 A) Fr F F1,
where F3 F. +
F. are message passing layers, Fr+1 = F and A E {0, 1}. We need to show that there a MGNN which implements,
Σ (0))
n
Σ (1)
Σ1())
(26)
A = f is exactly the function (26). Otherwise, if A = 0, we build another MGNN g implementing this function. Denote by Fr41 1 + F the (simple) message passing layer defined by (h)), = mg, for [n] and any E F"" Then, the MGNN g (1 X Id +X's) Frtz F1 ... F2 F1 with X' = exactly implements (26).
F K-LGNN A function f of this class is of the form.
mæ S Fr o F2 F1 o I
where Fy: FT + 1+1 are linear graph layers and Fr+1 F. Our goal is to show that there a GNN of k-LGNN which implements,
n
f(x),, Σ f(x)
Σ 1())))
(27)
By definition of linear graph layers, the map FT FI pm* defined by, for G e Fn*
Vii E [n]*, Fr+i(G) (G) ())
is a linear graph layer as defined in Section 3. Now, consider, the linear graph layer,
Fr+2 Ipn - Ru defined by, for G E In*
V(u,...., ... E [n] Fr+1(G) = Σ Giszmnnde
Then, the k-LGNN Fr+2 Fr Fr o..... Fg Fi T exactly implements (27).
36

---

Published as a conference paper at ICLR 2021
If F k-FGNN g. A function f of this class is of the form,
me o S Fr o... .o...P. F2 F1 o 1*
where Ft F. + 1++ are FGL (see Section 3) and Br+1 = F. We build a GNN of k-MGNNe which implements,
Σ f()) f()) Σ f(x))
(28)
For [k], define the FGL Hw Fnn - *p" >F""by. by,
vG E F". V(i...... is) E [n]*, Hw
G tf
Then H2 Hx F + F= computes the sum of the elements of the input tensor over the last 1 dimensions like to S Fx* + F" and H1 H2 ....o Hg. F" + F" computes the full sum of the elements of the input tensor like to S Fm" + I.. Finally, consider the FGL Fr+1 Fnc Fn* associated mg, i.e. such that, for any G E F*
Vii is) E [n]*, FG+1(G)s = -mmmg(G mg(Gii...s)))
Now, the k-FGNN
H1 H2 .... H& o Fr+1 H2 H...... Hn PT41 o Fr or... F2 Fj o exactly implements (28).
F EXTENSION TO GRAPHS OF VARYING SIZES
F.1 EXTENSION TO DISCONNECTED INPUT SPACES
Here we show that our results can be extended to graphs of varying sizes similarly Keriven Peyré (2019). There are two ways to do it. The first would be to directly adapt all the proofs but it would make them more cumbersome. Instead, we extend them with a simple argument presented below. As side benefit, this general lemma makes it possible to extend almost all the approximation results for graph neural networks from the literature.
The abstract setting is the following. Given compact input space X, assume that there is some finite set A, and Xa. a E A family of pairwise disjoints compact sets such that X = Lhe X.- Crucially, will assume that the X, are in distinct connected components. Intuitively, they do "touch" each other. Similarly, assume that the output space can be written as Y = =Luce Y., with Y., a A family of (pairwise disjoints) real vector spaces.
Before moving to the results, we need a last definition. Informally, we need that the functions f that will consider do not change the number of nodes of their inputs. Formally, we say that f: X - Y is adapted if f(Xa) C Ya for each A, and denote by Cad Y) the of continuous and adapted functions from X Y.
We can now state our lemma to adapt our results to graphs with varying node sizes.
Lemma 36. Let X be a compact space, Y be a topological space and A a finite set. Assume that there exists X..
A family of pairwise disjoints compact sets such that X == Llec A X. and the X 's's are in distinct connected components. Also assume that there is Yo.. a E A a.ffilly of (pairwise disjoints) real vector spaces such that L Yo. Consider F Coe(X, Y)) (non-empty) set of adapted functions and, for each A, define Fix_, x. of F) S C(X,, Y.) the restriction of the functions of F. to X..
Assume that the following holds,
37

---

Published as a conference paper at ICLR 2021
1. Each Fix. is sub-algebra of C(Xa, Ya) which contains the constant function 1y..
2. There a set of functions Fseat S (XX, IR) such that F S F and it discriminates between the X. 's, i.e. (FFscat) C LaeA X
Then the closure of F is,
F -- Va A, fixa E Fixa).
for the distance on Cad(X, () defined by. for f.g E Cad(X,Y),
d(s.g) = max sup ||s - gllx. aεA Xo
Proof. Define the set of functions
8 C C(X,R) by,
S = [f
By definition, Fscut S S. Moreover, each Fix. is subalgebra, S is also subalgebra of C(X, IR).
As X is compact, can apply Cor. 17 to S to get that, in C(X,
{f E C(X,)) (S) (f)).
In the first part of the proof, we check that, for each a, the function fa X - [0, 1] defined by
Sapxa = vB # a, fa|x; = O.
is continuous and satisfy (()) (Ja).. This will means that such functions belong to Fseat-
As the X 's are in different connected components, enough to check its continuity on each X3- Indeed, each falx is constant continuous. The second fact comes from the second assumption. Indeed, take (x,y) v) X such that (2r, v) (S). As Fscat C S, in particular (Ir, u) (F But, by assumption, s S Laea X3. Thus, necessarily x and belong to the same X so that fa (z) fa (v).
Therefore, we conclude that Sa E.
We now prove the announced equality. By the definition of the distance, the first inclusion, F C {s E Ca,(X,Y): fix., E F,,} is immediate. We focus on the other way. Take h E Coa(X, Y) such that f fyx., Fa for every A and 0. By definition of h, there exists, for each A, Ja F such that,
sup h Ially. <c, X.
As the X. are compact and the Ja 's are continuous, max supx.. |lgall +oo and denote by M > a bound on this quantity. We have shown above that each fa is in so there exists, for each A, l, S such that,
sup Ifa - lal S M x
By definition and, as F is a subalgebra, Ene laga E and, for each 3 E A,
sup X
h
Σ
laga F
< sup h goll + 1lgs llaee1 +
Σ
laga
X
< sct M x e + + 1)M x
(IA) + 1)c.
M
M
which concludes the proof.
38

---

Published as a conference paper at ICLR 2021
F.2 APPROXIMATION THEOREM WITH VARYING GRAPH SIZE
We now state our theorem in the case of varying graph size like Keriven & Peyré (2019). With Lem. 36, is indeed straightforward extend any approximation result initially proven for class of graphs of fixed size. However, as the complete proof would require new notations again, we only give sketch of proof.
Fix N 2 1 and consider the space of graphs (described by tensors) of size less than N, FEN UN F8 Equip this space with the final topology or, equivalently, the graph edit distance. Then, the last thing to check to apply Lem. 36 is that the classes of GNN that we consider indeed discriminate between graphs of different sizes, which is immediate.
Likewise, for message passing GNN, consider 9SN x XFO =U 9n FB, with similar topology or the graph edit distance.
FF Corollary 37. Let Kdiser 9 x IEE K C F be compact sets. For the invariant case, we have:
MGNN, = (s E CK F): ((2-WL,) SN(N}
2-LGNN, (I, ((2-WL)) (D)
k-LGNN, = (K, (
((WW))) S (P)))
k-FGNN, = (C,C), ((-FWL))
For the equivariant case, we have:
MGNNg ( BSN): (2-WLE) E
k-LGNNE (FEM p (K-LGGNE)) [ 2 (f E Co(K, p (K-WLE)
k-FGNNE { CEE, (k-FFWLE) Ep(f)
Proof. This corollary is a direct consequence of Thm. 34 and Lem. 36, using Lem. 32 to satisfy the sub-algebra assumption of Lem. 36.
39


Reviews:
[{"review_id": "PlNBGug-HLp", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe authors prove several statements about the expressiveness of different classes of graph neural nets (GNNs): conventional message passing networks, linear GNNs (LGNN) and “folklore GNNs” (FGNN). The novel theoretical contributions include analysis of expressiveness of FGNNs that use tensors of arbitrary order in terms of comparison to the Weisfeiler-Lehman tests; a characterization of the functions that these classes of networks can approximate; universality of FGNN as the tensor order goes to infinity. The results are based on a general Stone-Weierstrass-like theorem for equivariant functions. Prior universality results can be recovered as special cases. The authors have a simple experiment that show in a limited setting that a practical implementation agrees with the theory.\n\nStrengths:\n-\tThe paper and appendix are very well written and relatively well understandable for me, unfamiliar with universality proofs. Particular examples of clear writing include: the statement of Theorem 4 is clearly explained below the theorem; providing Example 16 directly after Corollary 15 aids exposition; using example 17 to motivate prop 18. \n-\tThe authors use a very general statement (Thm 20) to derive their results, making them generally applicable.\n-\tThe authors derive a substantial number of expressiveness results from the general theory.\n\nWeaknesses & suggestions for improvement:\n-\tThe main paper only sets up the problem and states the main results, while all theoretical contributions are done in the appendix. The main paper would be more self-contained if some more intuition for the proofs was given in the main paper.\n-\tThe experiments seem to not compare to LGNN. Adding this comparison would help making an empirical argument for why FGNN is best. \n\nRecommendation:\nAlthough I am not very familiar with the field of universality proofs, the paper appears to me to be a very solid contribution to the field and I recommend publication.\n \nMinor points / suggestions:\n-\tIn several instances, the authors write “a compact” without a noun. Is this conventional language?\n-\tBelow Eq 2, there is an F without subscript. Is this the same for all layers?\n-\tIn App C.3, in the second line of the equation, are there suffices missing on the left-hand side?\n-\tSec 4.3, first sentence, “the set invariant”, missing “of” \n-\tSec 4.3, typo “To clarify the meaning of theses statements”\n-\tApp D.3: typo “as every function satisfy” should be “satisfies”\n-\tExample 16, typo “is able to learn function” should be plural\n-\tApp D.3, proof of Corollary 15: define when a class separates a set around “clearly separates X_\\mathcal{F}”. Presumably means same as separates points?\n-\tEq 17, Define S \\cdot \\mathcal{F}, presumably as the scalar-vector product of the outputs of the functions? \n-\tCorollary 19, assumption 3, what does “pairwise distinct coordinates” mean?\n-\tApp D.3, typo “For an equivariant function, for any” missing $f$\n-\tExample 21, \\mathcal{C}_{eq} should be \\mathcal{C}_E? Happens later more.\n-\tLemma 24, define R{X_1, .., X_p] as polynomials\n\n### Post rebuttal\nI thank the authors for their response. My previous rating still applies.", "extra_scores": {}, "extra_text": {}}, {"review_id": "PSP6pWkYfov", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Summary:\n\nThis paper compares the expressive power of three types of invariant and equivariant GNNs against the Weisfeiler-Lehman (WL) tests, proves function approximation results for these GNNs, and demonstrates that 2-FGNN_E works well for the quadratic assignment problem.\n\n2. Clearly state the recommendation (accept or reject) with one or two key reasons for this choice:\n\nI am slightly leaning towards recommending a rejection to this paper, with the main reason being that I am not sure if the contributions are sufficiently significant, as I will elaborate below.\n\n3. Arguments for the recommendation and questions for the authors:\n\na) It is nice to establish and summarize a thorough comparison of the expressive powers of different GNN families as well as k-WL, and also to incorporate not only invariant but also equivariant GNNs into consideration. However, among the results in Section 4.2, the only novel one is the equivalence between k-FGNN and (k+1)-WL, which, one may argue, is also not surprising considering the equivalence between k-FWL and (k+1)-WL. The value of 2-FGNN has also been demonstrated by the work of [1].\n\nb) The overall framework for the comparison of expressive power as well as function approximation resembles that of [2], which characterizes the expressive power of GNNs and WL tests by the sigma algebra they induce on the space of graphs, and also establishes an equivalence between the ability to distinguish non-isomorphic graphs and the ability to approximate invariant functions. Hence, the authors may want to elaborate more on the connection between this work and [2].\n\n4. Additional comments:\n\nThe authors claim that 3-LGNN or 2-FGNN can count the number of 6-cycles, which is an improvement upon the result in [3], which implies that 6-LGNN can count 6-cycles. Technically, however, it is only known (by [4], to my knowledge) that 3-WL can count the number of times 6-cycles appear as subgraphs of a graph, but not induced subgraphs, whereas [3] is concerned with the counting of both subgraphs and induced subgraphs. Therefore, I would recommend that the authors make this statement more precise.\n\nReferences:\n\n[1] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks.\n\n[2] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with GNNs.\n\n[3] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures?\n\n[4] Martin Fu ̈rer. On the Combinatorial Power of the Weisfeiler-Lehman Algorithm.\n\n\n=== Post Rebuttal ===\n\nI appreciate the careful response provided by the authors, which reminds me of the significance of extending existing theoretical results from invariant to equivariant models. Therefore I have raised my score by 1 point.", "extra_scores": {}, "extra_text": {}}, {"review_id": "PQwpJwfudCn", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "post-discussion:\nI read the author's response and other reviews. I still think this is a very strong submission and would like to see it accepted.\nI encourage the authors to add a section discussing their generalization of SW theorem + Theorems 31,32 as the authors suggested. another small point: I couldn't easily find the definition of \"stable by concatenation\".\n\n\nSummary: \n\nThe paper studies the expressive power of several classes of recently suggested models: message passing neural networks, Linear GNNs, and Folklore GNNs. Understanding the expressivity of GNNs is a timely and important topic since unlike other neural architectures as fully connected networks, the most widely-used models today, message-passing networks, are not universal. The paper first formally defines the three model classes mentioned above. The paper then reviews previous results on the separation power of these models (can a model tell the difference between two non-isomorphic graphs) and summarizes them, as well as new results they obtain, in prop. 3. Theorem 4 then connects these separation results to the approximation power of the model classes by a novel adaptation of a recently introduced generalization of the Stone-Weierstrass theorem.  The authors conclude the paper with an experimental section showing that folklore GNNs perform significantly better than other models in solving the quadratic assignment problem, which supports the theoretical claims\n\n\nStrong points:\n\nNew strong results: the paper closes the following knowledge gaps: (1) Folklore GNNs: k Folklore GNNs are as strong as k+1 WL, (2) Equivariant separation: connecting the separation power of equivariant (rather than invariant) models to their equivariant WL counterpart (3) Link separation results to approximation results: the authors suggest a generalization of the stone Weierstrass theorem and use it to show new approximation results.    \nThe paper succinctly summarizes the current results on the separation power of various GNN classes.\nThe paper Introduces new tools from approximation theory. These tools seem important and will be useful for future papers targeting the expressive power of invariant and equivariant deep models\nInteresting experimental results. Showing for the first time that more expressive models  (2-FWL) substantially outperform previous (2-WL) models on an important task.\n\nWeak points:\n\nNone. I have several comments on the exposition. See below. \nIn addition, I would like to ask the authors to explicitly and succinctly state their generalization of the Stone-Weierstrass theorem for general symmetries and deep models so it would be easy for future work to use it. Please do so for both invariant and equivariant case, and consider stating it in the paper itself.\n\n\n\nRecommendation: \n\nThis is a high-quality paper with several strong contributions as listed above. Most importantly, the paper proves several important results on the expressive power of GNNs and introduces useful mathematical tools that I am sure will be used by the community. Hence, I strongly encourage the acceptance of this paper (and would also recommend it as a spotlight/oral presentation).\n\nMinor comments:\n\n* Can the authors comment on “Building powerful and equivariant graph neural networks with structural message-passing” (Vignac et al. 2020). Specifically, Theorem 2 shows that their models can separate any pair of non-isomorphic graphs while using only second-order tensors\n* “So in terms of separating power, when restricted to tensors of order k, k-FGNN is the most powerful architecture. ” => Among the architectures considered in this paper.\n* “For regular-grid graphs, they match classical convolutional networks which by design can only approximate translation-invariant functions and hence have limited expressive power. In this paper, we focus instead on more expressive architectures.” => I believe that mentioning the relation between GNNs and 2-WL here is a better example of the limited expressive power of GNNS.\n* “Note that 2-WL solves k-cliques for k <= 6 (Fürer (2017)) so that these networks are probably not comparable to 2-WL.” => As far as I know 2WL cannot detect triangles. Please explain.\n* k-FWL: maybe write 2 FGNN layers explicitly and discuss matrix multiplication connection?\n* Appendix D is written really nicely with good examples\n* Algebras are closed under multiplication but sets of neural networks are not (although products can be easily approximated in most cases). I believe this gap is filled in Appendix D but would like to ask the authors to explain it in the main text.\n* The paper has several typos.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EbmT1m2UmY", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### Goal\n\nThe paper describes the approximation power of certain types of graph neural networks.  It considers Message Passing GNNs (MGNNs), and two GNN-type methods proposed by Maron et al., k-FGNN and k-LGNN.\n\nThe main challenge with some of the current expressiveness analysis of neural networks is their reliance on discrete attributes. This line of work shows how these can be extended to a general setting.\n\n#### Quality\n\n- This is a great paper, well written, nice appendix, on an interesting topic. The only drawback is that the approach was narrowly applied to k-FGNN and k-LGNN, comparing them to k-WL approaches.\n\n- My main concern is being too narrowly focused on k-FGNN and k-LGNN without a proper empirical comparison with other more expressive competing methods. For instance, it does not even discuss alternative approaches using group averaging. I think the paper would significantly broaden its audience if there is a comparison with novel k-ary group averaging approaches (e.g., Chen et al., 2020, Murphy et al. 2019) in the empirical section. \n\n#### Clarity\n\nThe paper is clear and well-written. The notation follows the standard notation used in prior work.\nIn one aspect the notation could improve: \\subset should be replaced by \\subseteq to avoid confusion, and be more in line with the use of \\subsetneq. I was not sure what \\subseteq meant until I saw \\subsetneq. It is unfortunately but different branches of mathematics use \\subseteq differently and the symbol should be avoided altogether. \nThe appendix is well organized, with an index that helps the reader find proofs and definitions.\n\n#### Originality\n- The work follows from prior work of Maehara & Hoang (2019), Chen et al., 2019, Geerts (2020a), etc.\n- There is some novelty in the proof approach\n- New results related to k-FGNN and k-LGNN.\n\n#### Significance\n\nThe work is of interest to a narrow sub-community working on k-FGNN and k-LGNN. The MGNN results were known but recovered here in a different way (i.e., there is value). The k-FGNN and k-LGNN results are new but also very narrow due to the sub-community size.\n\nThe empirical results essentially do not compare with any other alternative approach. Until the community is convinced that k-FGNN and k-LGNN can empirically compete with other approaches (e.g., Morris et al. 2019, Permutation group averages like  Chen et al. 2020, Murphy et al. 2019, among others), these methods will not see broad applicability. \n\nChen, Zhengdao, Lei Chen, Soledad Villar, and Joan Bruna. \"Can graph neural networks count substructures?.\" NeurIPS (2020).\n\nMurphy, Ryan L., Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. \"Relational pooling for graph representations.\" ICLR (2019).\n\n#### Pros\n- Solid theoretical work showing the expressiveness of k-FGNN and k-LGNN\n- Interesting ports of ideas from other papers to improve proof techniques of current GNN papers\n\n#### Cons\n\n- The authors seem unfamiliar with group average approaches that increase the expressiveness of MGNNs. These can also be universal approximations. Permutation group averages like  Chen et al. 2020, Murphy et al. 2019, among others, have increased expressiveness of MGNN using the same MGNN architecture.  Since there has been a lot of recent activity related to these methods, this is a blind spot of this work. For instance, “Note also, that if the nodes are given distinct features, MGNNs become much more expressive Loukas (2019) but this is meaningless in some problems such as our graph alignment problem.” does not point to the fact that a simple group average approach would fix the issue. This way, the work feels unnecessarily narrow.\n\n#### Typos:\n- \"test to express the discriminatory power of equivariant architectures For this\" => \"test to express the discriminatory power of equivariant architectures. For this\"\n- \"Maron et al. (2018) Geerts (2020a)\" => \"Maron et al. (2018); Geerts (2020a)\"\n\n----------------------------------------\n\nAfter rebuttal:\n\nThanks for the answers. I have raised my score even though I still think the paper could have done a better job at comparing against other methods.\n\n- Regarding group-averaging methods for the equivariant case: It is a trivial extension, specially the approach of giving GNNs unique IDs and then averaging their representation, which (Loukas, 2020) shows it is universal (but (Loukas, 2020) did not consider averaging). Regarding training, it is always performed stochastically via data augmentation and Monte Carlo estimated in test. For the generalization error of the stochastic optimization, it is still unknown (some new results show promise (Chen et al. 2020) and (Lyle et al. 2020)) in the same way that the generalization performance of other universal methods is still unknown.\n\n- Chen, S., Dobriban, E., & Lee, J. H. (2020). Invariance reduces Variance: Understanding Data Augmentation in Deep Learning and Beyond.\n- Lyle, Clare, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin Bloem-Reddy. \"On the Benefits of Invariance in Neural Networks.\" arXiv preprint arXiv:2005.00178 (2020).\n- Loukas, Andreas. \"How hard is to distinguish graphs with graph neural networks?.\" Advances in Neural Information Processing Systems 33 (2020).", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is concerned with the ongoing research program of mapping the approximation power of different GNN architectures. It provides significant advances in the study of equivariant GNNs and nice extensions in the invariant case by closing existing gaps between distinct GNN families. 
All reviewers agreed that this is a strong submission with substantial new theoretical results. The AC recommends a strong acceptance. 
Decision: Accept (Spotlight)