EQUIVARIANT GRAPH NEURAL NETWORKS
Year: 2021

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.

heading: 1 INTRODUCTION
text: Graph Neural Networks (GNN) are designed to deal with graph structured data. Since a graph is not changed by permutation of its nodes, GNNs should be either invariant if they return a result that must not depend on the representation of the input (typically when building a graph embedding) or equivariant 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 a 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 (kFGNN) first introduced by Maron et 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 k which make them of little practical use for k ≥ 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 k ≥ 2, k-WL(G) are invariants based on the Weisfeiler-Lehman tests (described in Section 4.1). For each k ≥ 2, (k + 1)-WL has strictly more separating power than k-WL (in the sense that there is a 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 be as powerful as 2-WL. In Maron et al. (2019a), Geerts (2020b) and Geerts (2020a), k-LGNN are shown to be as powerful as k-WL and 2-FGNN is shown to be as powerful as 3-WL. In this paper, we extend this last result about k-FGNN to general values of k. So in term of separating power, when restricted to tensors of order k, k-FGNN is the
most powerful architecture among the ones considered in this work. This means that for a given pair of graphs G and G′, if (k + 1)-WL(G) 6= (k + 1)-WL(G′), then there exists a k-FGNN, say GNNG,G′ such that GNNG,G′(G) 6= GNNG,G′(G′). Approximation results for GNNs. Results on the separating power of GNNs only deal with pairwise comparison of graphs: we need a priori a different GNN for each pair of graphs in order to distinguish them. Such results are of little help in a practical learning scenario. Our main contribution in 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 a 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 k tends to infinity with n the number of nodes. Since we 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 Maehara & Hoang (2019) shows the universality of a new class of networks they introduced. Here, we consider a natural equivariant extension of k-WL and prove that equivariant (k + 1)-LGNNs and k-FGNN can approximate any equivariant function less powerful than this equivariant (k + 1)-WL for k ≥ 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 contributions, 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 a node embedding which beats by a 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 3 : 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 WeisfeilerLehman 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-grained Stone-Weierstrass approximation theorem for vector-valued functions with symmetries. Our theorem handles both invariant and equivariant cases and is inspired by recent works in approximation theory. In Section 6, we illustrate our theoretical results on a practical application: the graph alignment problem, a well-known NP-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://github.com/mlelarge/graph_neural_net

heading: 2 RELATED WORK
text: 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),
for example polynomials (Defferrard et al., 2016). 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.
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-passing GNNs. They showed that such networks can approximate, in a weak sense, all functions whose discriminatory power is weaker than 1-WL. Yarotsky (2018) 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 a 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 to 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 as it yields approximation guarantees even at fixed order of tensor.
CPNGNN in Sato et al. (2019) and DimeNet in Klicpera et al. (2020) are message passing GNN incorporating more information than those studied here. Partial results about their separating power follows from Garg et al. (2020) which provides impossibility results to 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 can be applied to characterize their approximation power (see Section 5).
Note that for neural networks on sets, the situation is a 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 et 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.

heading: 2.1 NOTATIONS: GRAPHS AS TENSORS
text: We denote by F,F0,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 Rp always refer to component-wise product. There are two ways to see graphs with features. First, graphs can be seen as tensors of order k: G ∈ Fnk . The classical representation of a graph by its (weighted) adjacency matrix for k = 2 is a tensor of order 2 in Rn2 . This case allows for features on edges by replacing Rn2 with Fn2 where F is some Rp. Second, graphs can also be represented by their discrete structure with an additional feature vector. More exactly, denote by Gn the set of discrete graphs G = (V,E) with n nodes V = [n] and edges E ⊆ V 2 (with no weights on edges). Such a G ∈ Gn with a vector h0 ∈ Fn represents a graphs with features on the vertices.

heading: 2.2 DEFINITIONS: INVARIANT AND EQUIVARIANT OPERATORS
text: Let [n] = {1, . . . , n}. The set of permutations on [n] is denoted by Sn. For G ∈ Fn k
and σ ∈ Sn, we define: (σ ? G)σ(i1),...,σ(ik) = Gi1,...,ik . Note that the ? operation is valid between a permutation in Sn and a graph G as soon as the number of nodes of G is n, i.e. it is valid for any order k tensor
representation of the graph. Two graphs G1, G2 are said isomorphic if they have the same number of nodes and there exists a permutation σ such that G1 = σ ? G2.
Definition 1. A function f : Fnk0 → F1 is said to be invariant if f(σ ? G) = f(G) for every permutation σ ∈ Sn and every G ∈ Fn k 0 . A function f : Fn k 0 → Fn `
1 is said to be equivariant if f(σ ? G) = σ ? f(G) for every permutation σ ∈ Sn and every G ∈ Fn k 0 .
Note that composing an equivariant function with an invariant function gives an invariant function. For k ≥ 1, we define the invariant summation layer Sk : Fnk → F by Sk(G) = ∑ i∈[n]k Gi for G ∈ Fnk . We also define the equivariant reduction layer Sk1 : Fn k → Fn as follows: Sk1 (G)i =∑
1≤i2...ik≤nGi,i2,...ik . For message passing GNN, we will use the equivariant layer Id +λS 1 : Fn → Fn defined by, (Id +λS1)(G)i = Gi + λS1(G), where λ ∈ R is a learnable parameter. In the sequel, we will need a mapping Ik lifting the input graph to a higher order tensor. We denote by Ik : Fn20 → Fn k
1 the initialization function mapping for a 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 I2 is given by, for G ∈ Fn2 , I(G)i,j = (Gi,j , δi,j) where δi,j is 0 if i 6= j and 1 otherwise. Indeed for a pair of nodes i, j in a graph (without features), there are only three isomorphism types: i = j; i 6= j and (i, j) is an edge; i 6= j but (i, j) is not an edge.

heading: 3 GNN DEFINITIONS
text: In this section, we define the various GNN architectures studied in this paper. In all architectures, there is a main building block or layer mapping Fnkt to Fn k t+1 where Fn k
t 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 a 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: mI : FT+1 → F for the invariant case and mE : FnT+1 → Fn 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 ∈ Fn20 , produces in the invariant case a graph embedding in FT+1 and in the equivaraint case a node embedding in FnT+1, then these embeddings are passed through the function mI or mE respectively to get a feature in F or Fn for the learning task.

heading: 3.1 MESSAGE PASSING GNN
text: 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) ∈ Gn and features on the nodes h0 ∈ Fn. MGNN are then defined inductively as follows: let h`i ∈ F` denote the feature at layer ` associated with node i, the updated features h`+1i are obtained as: h `+1 i = f ( h`i , {{ h`j }} j∼i ) , where j ∼ i means that nodes j and i are neighbors in the graphG, i.e. (i, j) ∈ E, and the function f is a learnable function taking as input the feature vector of the center vertex h`i and the multiset of features of the neighboring vertices {{ h`j }} j∼i. Indeed, it follows from Lem. 33 in Appendix, that any such function f can be approximated by a layer of the form,
h`+1i = f0 h`i ,∑ j∼i f1 ( h`i , h ` j ) , (1) where f0 : F` × F`+1/2 → F`+1 and f1 : F` × F` → F`+1/2, so that F` is the field for the features at the `-th layer. We call such a function a message passing layer and denote it by F : Fn` → Fn`+1 (note that F depends implicitly from the graph). Then an equivariant message passing GNN is simply obtained by the composition of message passing layers: FT ◦ . . . F2 ◦F1, where each Fi is a message passing layer. Clearly since each Fi is equivariant, this message passing GNN is also equivariant and produces features on each node in the space FT . In order to obtain an invariant GNN, we apply
an invariant function from FnT → FT+1 on the output of an 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 ∑ i(FT ◦ . . . F2 ◦ F1(G))i is taken as an invariant feature for the graph G. With our notation, S1 ◦ FT ◦ . . . F2 ◦ F1 (where S1 was defined in Section2.2) defines an invariant message passing GNN.
Hence, we define the sets of message passing GNNs as follows: MGNNI = {mI ◦ S1 ◦ FT ◦ . . . F2 ◦ F1,∀T} MGNNE = {mE ◦ (Id +λS1) ◦ FT ◦ . . . F2 ◦ F1,∀T} where Ft : Fnt → Fnt+1 are message passing layers.

heading: 3.2 LINEAR GNN
text: We define the linear graph layer of order k as F : Fnk` → Fn k `+1, where for all G ∈ Fn k
` , F (G) = f (L[G]) where L : Fnk` → Fn k
` is a linear equivariant function, and f : F` → F`+1 is a learnable function applied on each of the nk features and F` is the field for the features at the `-th layer.
We then define the sets of linear GNNs as follows: k-LGNNI = {mI ◦ Sk ◦ FT ◦ . . . F2 ◦ F1 ◦ Ik,∀T} k-LGNNE = {mE ◦ Sk1 ◦ FT ◦ . . . F2 ◦ F1 ◦ Ik,∀T} where Ik : Fn20 → Fn k 1 is defined in §2.2 and for t ≥ 1, Ft : Fn k t → Fn k
t+1 are linear equivariant layers.

heading: 3.3 FOLKLORE GNN
text: The main building block of Folklore GNN (FGNN) is what we call the folklore graph layer (FGL) of order k defined as follows: for k ≥ 1, F : Fnk` → Fn k `+1 where for all G ∈ Fn k ` and all i ∈ [n]k,
F (G)i = f0 Gi, n∑ j=1 k∏ w=1 fw ( Gi1,...,iw−1,j,iw+1,...,ik ) , (2) where f0 : F`×F`+1/2 → F`+1 and fk : F` → F`+1/2 are learnable functions. As shown in Lem. 33 in Appendix, FGL is an equivariant function which is indeed very expressive.
For classical graphs G ∈ Fn20 , we can now define 2-FGNN by composing folklore graph layers Ft : Fn 2 t → Fn 2 t+1, so that FT ◦ . . . F1 ◦ F0 is an equivariant GNN producing a graph in Fn 2
T+1. To obtain an invariant feature of the graph, we use the summation layer S2 defined in Section 2.2 so that S2 ◦ FT ◦ . . . F1 ◦ F0 is now an invariant 2-FGNN. In order to define general k-FGNN, we first need to lift the classical graph to a tensor in Fnk , then we apply folklore graph layers of order k and finally we need to project the tensor in Fnk to a tensor in Fn for the equivariant version and to a tensor in F for the invariant version. The first step is done with the linear equivariant function Ik : Fn20 → Fn k 1 defined in Section 2.2. The last step is done with the reduction layer Sk1 for the equivariant case and the summation layer Sk for the invariant case, both defined in Section 2.2.
We define the sets of folklore GNNs as follows: k-FGNNI = {mI ◦ Sk ◦ FT ◦ . . . F2 ◦ F1 ◦ Ik,∀T} k-FGNNE = {mE ◦ Sk1 ◦ FT ◦ . . . F2 ◦ F1 ◦ Ik,∀T} where Ft : Fn k t → Fn k t+1 are FGLs.

heading: 4 THEORETICAL RESULTS FOR GNNS

heading: 4.1 WEISFEILER-LEHMAN INVARIANT AND EQUIVARIANT VERSIONS
text: We introduce a family of functions on graphs parametrized by integers k ≥ 2 developed for the graph isomorphism problem and working with tuples of k vertices. Each k-tuple i ∈ V k = [n]k is given
a color c0(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 ∈ [k], and i = (i1, . . . , ik) ∈ V k, Nw(i) = {(i1, . . . , iw−1, j, iw+1, . . . , ik) : j ∈ V }. Then, the colors of the k-tuples are refined as follows, ct+1(i) = Lex (ct(i), (Ct1(i), . . . , C t k(i))) where, for w ∈ [k], Ctw(i) = {{ ct(̃i) : ĩ ∈ Nw(i) }} and the function Lex means that all occuring colors are lexicographically ordered and replaced by an initial segment of the natural numbers.
For a graphG, let k-WLTI (G) denote the multiset of colors of the k-WL algorithm at the T th iteration. After a 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-WLI(G) the multiset of colors in the stable coloring. This is a graph invariant that is usually used to test if graphs are isomorphic. The power of this invariant increases with k Cai et al. (1989).
We now define an equivariant version of k-WL test to 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-WLTE : Fn 2
0 → Fn by, for i ∈ V : k-WLTE(G)i ={{ cT (i) : i ∈ V k, i1 = i }} . Similarly, define k-WLE(G) = {{ c(i) : i ∈ V k, i1 = i }} where c(i) is the stable coloring obtained by the algorithm.

heading: 4.2 SEPARATING POWER OF GNNS
text: We formulate our results using the equivalence relation introduced by Timofte (2005), which characterizes the separating power of a set of functions.
Definition 2. Let F be a set of functions f defined on a set X , where each f takes its values in some Yf . The equivalence relation ρ (F) defined by F on X is: for any x, x′ ∈ X ,
(x, x′) ∈ ρ (F) ⇐⇒ ∀f ∈ F , f(x) = f(x′) .
Given two sets of functions F and E , we say that F is more separating (resp. strictly more separating) than E if ρ (F) ⊆ ρ (E) (resp. ρ (F) ( ρ (E)). Note that all the functions in F and E 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 (k + 1)-WLI distinguishes strictly more than k-WLI , which can be rewritten simply as (for a function f , we write ρ (f) for ρ ({f}))
ρ ((k + 1)-WLI) ( ρ (k-WLI) . (3)
This notion of separating power enables us to concisely summarize the current knowledge about the discriminatory power of classes of GNN.
Proposition 3. We have, for k ≥ 2,
ρ (MGNNI) = ρ (2-WLI) ρ (MGNNE) = ρ (2-WLE) (4) ρ (k-LGNNI) = ρ (k-WLI) ρ (k-LGNNE) ⊆ ρ (k-WLE) (5) ρ (k-FGNNI) = ρ ((k + 1)-WLI) ρ (k-FGNNE) = ρ ((k + 1)-WLE) (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 k ≥ 2 is proved in Section C. Note that for k = 2, all GNNs are dealing with tensors of order 2 i.e. 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 Rn2 → Rn2 for all values of n (Maron et al., 2018); the folklore layer involves a (dense) matrix multiplication of shape n× n. If 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.

heading: 4.3 APPROXIMATION RESULTS FOR GNNS
text: For X,Y finite-dimensional spaces, let us denote by CI(X,Y ), CE(X,Y ), , the set of invariant, respectively equivariant, continuous functions from X to Y . The closure of a 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 Kdiscr ⊆ Gn × Fn0 , K ⊆ Fn 2 0 be compact sets. For the invariant case, we have:
MGNNI = {f ∈ CI(Kdiscr,F) : ρ (2-WLI) ⊆ ρ (f)} k-LGNNI = {f ∈ CI(K,F) : ρ (k-WLI) ⊆ ρ (f)} k-FGNNI = {f ∈ CI(K,F) : ρ ((k + 1)-WLI) ⊆ ρ (f)}
For the equivariant case, we have: MGNNE = {f ∈ CE(Kdiscr,Fn) : ρ (2-WLE) ⊆ ρ (f)} k-LGNNE = {f ∈ CE(K,Fn) : ρ (k-LGNNE) ⊆ ρ (f)} ⊃ {f ∈ CE(K,Fn) : ρ (k-WLE) ⊆ ρ (f)} k-FGNNE = {f ∈ CE(K,Fn) : ρ ((k + 1)-WLE) ⊆ ρ (f)}
In the invariant case for k = 2,we have MGNNI = 2-LGNNI ( 2-FGNNI where the strictness of the last inclusion comes from (3). In other words, 2-FGNNI has a better power of approximation than the other architectures working with tensors of order 2. We already knew by Proposition 3 that 2-FGNNI 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 “⊆” are actually straightforward. For concreteness, we focus on k-FGNNI ⊆ {f ∈ CI(K,F) : ρ ((k + 1)-WLI) ⊆ ρ (f)}. Take h ∈ k-FGNNI , this means that there is a sequence GNNj ∈ k-FGNNI such that, supG∈K ‖h(G)−GNNj(G)‖ goes to zero when j goes to infinity. Therefore, h is continuous and constant on each ρ (k-FGNNI)-class. Indeed, for any (G,G′) ∈ ρ (k-FGNNI), GNNj(G) = GNNj(G′) so that h(G) = limiGNNj(G) = limjGNNj(G′) = h(G′). Hence we have ρ (k-FGNNI) ⊆ ρ (h) and by Prop. 3, ρ (k-FGNNI) = ρ ((k + 1)-WLI), allowing us to get the inclusion above.
On the contrary, the reverse inclusions “⊃” are much more intricate but they are also the most valuable. For instance, consider the inclusion k-FGNNI ⊃ {f ∈ CI(K,F) : ρ ((k + 1)-WLI) ⊆ ρ (f)}. If one wishes to learn a function h ∈ CI(K,F) with k-FGNNI , this function must at least be approximable by the class of k-FGNNI . Our theorem precisely guarantees that if h is less separating that k-WLI , it can be approximated by k-FGNNI :
∀ > 0, ∃GNN ∈ k-FGNNI , sup G∈K ‖h(G)−GNN(G)‖ ≤ .
For this, we show a much more general version of the famous Stone-Weierstrass theorem (see Section D) which relates the separating power with the approximation power. Following the elegant idea of Maehara & 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 5, 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 CI(K,F) (or CE(K,Fn)). In particular, Thm. 4 implies that n-LGNN 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( √ n)-WL can distinguish non-isomoprhic instances. Therefore, O( √ n)-LGNN or O( √ n)-FGNN achieve universality in the particular, yet common, case of planar graphs. On a 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.

heading: 5 EXPRESSIVENESS OF GNNS
text: We now state the general theorems which are our main tools in proving our approximation guarantees for GNNs. Theirs proofs are deferred to Section D.9 which contains our generalization of the StoneWeierstrass theorem with symmetries. We need to first introduce more general definitions: If G is a finite group acting on some topological space X , we say that G acts continuously on X if, for all g ∈ G, x 7→ g · x 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,
CE(X,Y ) = {f ∈ C(X,Y ) : ∀x ∈ X, ∀g ∈ G, f(g · x) = g · f(x)} CI(X,Y ) = {f ∈ C(X,Y ) : ∀x ∈ X, ∀g ∈ G, f(g · x) = f(x)}
Note that these definitions extend Definition 1 to a general group. Theorem 5. Let X be a compact space, F = Rp be some finite-dimensional vector space, G be a finite group acting (continuously) on X .
Let F0 ⊆ ⋃∞ h=1 CI(X,Rh) be a non-empty set of invariant functions, stable by concatenation, and consider,
F = {m ◦ f : f ∈ F0 ∩ C(X,Rh), m : Rh → F MLP, h ≥ 1} ⊆ C(X,F) .

heading: Then the closure of F is,
text: F = {f ∈ CI(X,F) : ρ (F0) ⊆ ρ (f)} .
We can apply Theorem 5 to the class of k-ary relational pooling GNN introduced in Murphy et al. (2019a). As a result, we get that this class of invariant k-RP GNN can approximate any continuous function f with ρ(k − RPGNN) ⊆ ρ(f) but to the best of our knowledge, ρ(k − RPGNN) is not known and only ρ(k − RPGNN) ⊂ ρ(2−WLI) is proved in Murphy et al. (2019a). We now state our general theorem for the equivariant case: Theorem 6. Let X be a compact space, F = Rp and G = Sn the permutation group, acting (continuously) on X and acting on Fn by, for σ ∈ Sn, x ∈ Fn,
∀i ∈ {1, . . . , p}, (σ · x)i = xσ−1(i) ,
Let F0 ⊆ ⋃∞ h=1 CE ( X, (Rh)n ) be a non-empty set of equivariant functions, stable by concatenation, and consider,
F = {x 7→ (m(f(x)1), . . . ,m(f(x)n)) : f ∈ F0 ∩ C ( X, (Rh)n ) , m : Rh → F MLP, h ≥ 1}
Assume, that, if f ∈ F0, then,
x 7→ ( n∑ i=1 f(x)i, n∑ i=1 f(x)i, . . . , n∑ i=1 f(x)i ) ∈ F0 .

heading: Then the closure of F is,
text: F = {f ∈ CE(X,Fn) : ρ (F0) ⊆ ρ (f)} .
Applications of these theorems fo the case of Pointnet Qi et al. (2017) are provided in Section D.9

heading: 6 QUADRATIC ASSIGNMENT PROBLEM
text: To empirically evaluate our results, we study the Quadratic Assignment Problem (QAP), a classical problem in combinatorial optimization. For A,B n× n symmetric matrices, it consists in solving
maximize trace(AXBX>), subject to X ∈ Π,
where Π is the set of n× 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
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.t. 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, a class of graph considered as particularly hard for isomorphism testing.
To remedy this weakness, we consider 2-FGNNE . We then follow the siamese method of (Nowak et al., 2018): given two graphs, our system produces an embedding in Fn for each graph, where n is the number of nodes, which are then multiplied together to obtain a n× 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 Erdős–Rényi 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.1.
Erdős–Rényi graph model
Regular graph model

heading: 7 CONCLUSION
text: 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 are able to 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.e. 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 to 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 2. From a practical perspective, we demonstrate their improved performance on the QAP with a significant gap in performances compared to other approaches.

heading: ACKNOWLEDGMENTS
text: This work was supported in part by the French government under management of Agence Nationale de la Recherche as part of the “Investissements d’avenir” program, reference ANR19-P3IA-0001 (PRAIRIE 3IA Institute). M.L. thanks Google for Google Cloud Platform research credits and NVIDIA for a NVIDIA GPU Grant.

heading: A Experimental results 14
text: A.1 Details on the experimental setup . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
A.2 Experimental results on graphs of varying size . . . . . . . . . . . . . . . . . . . . 14
A.3 Generalization for regular graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

heading: B Weisfeiler-Lehman tests 16
text: B.1 Weisfeiler-Lehman test on vertices . . . . . . . . . . . . . . . . . . . . . . . . . . 16
B.2 Isomorphism type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
B.3 Weisfeiler-Lehman and Folklore Weisfeiler-Lehman tests of order k ≥ 2 . . . . . . 17

heading: C Separating power of GNN 18
text: C.1 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
C.5 Bounding the separating power of k-FGNN . . . . . . . . . . . . . . . . . . . . . 20
C.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

heading: D Stone-Weierstrass theorem with symmetries 21
text: D.1 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 of Rp . . . . . . . . . . . . . . . . . . . . . . . . . 27
D.7 Proof of the main equivariant approximation theorem . . . . . . . . . . . . . . . . 29
D.8 Practical reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
D.9 Reductions for GNNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

heading: E Proofs for expressiveness of GNNs 34
text: E.1 Expressivity of GNN layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
E.2 Approximation theorems for GNNs . . . . . . . . . . . . . . . . . . . . . . . . . 35

heading: F Extension to graphs of varying sizes 37
text: F.1 Extension to disconnected input spaces . . . . . . . . . . . . . . . . . . . . . . . . 37
F.2 Approximation theorem with varying graph size . . . . . . . . . . . . . . . . . . . 39

heading: A EXPERIMENTAL RESULTS

heading: A.1 DETAILS ON THE EXPERIMENTAL SETUP
text: We consider a 2-FGNNE 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-FGNNE encoder producing embeddings E1, E2 ∈ Rn×k. Those embeddings are used to predict a matching as follows: we first compute the outer product E1ET2 , then we take a softmax along each row and use standard cross-entropy loss to predict the corresponding permutation index. We used 2-FGNNE 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 1e-4 and Adam optimizer. The PyTorch code is 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 Erdős–Rényi random graphs, we consider G1 to be a random Erdős–Rényi graph with edge density pe = 0.2 and n = 50 vertices. The graph G2 is a small perturbation of G1 according to the following error model considered in Feizi et al. (2016):
G2 = G1 (1−Q) + (1−G1) Q′, (7)
where Q and Q′ are Erdős–Rényi random graphs with edge density p1 and p2 = p1pe/(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 is 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.

heading: A.2 EXPERIMENTAL RESULTS ON GRAPHS OF VARYING SIZE
text: Regular graph model
We tested our models on dataset of graphs of varying size, as this setting is also encompassed by our theory.
However, contrary to message-passing GNN, GNN based on tensors do not work well with batches of graphs of varying size. Previous implementations, such as the one of Maron et al. (2019a), group the graphs in the dataset by size, enabling the GNN to only deal with batches of graphs on the same size.
Instead, we use masking, which is a standard practice in recurrent neural networks. A batch of b tensors of sizes n1 × n1, n2 × n2, . . . , nb × nb is represented as a tensor b× nmax × nmax where nmax = maxi=1,...,b ni. A mask is created at initialization and is used to ensure that the operations on the full tensor translates to valid operations on each of the individual tensor.
We implemented this functionnality as a class MaskedTensors. Thanks to the newest improvements of PyTorch (Paszke et al., 2019), MaskedTensors act as a 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://github.com/mlelarge/graph_neural_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 now random. The number of vertices of a graph is indeed chosen randomly according to binomial distribution of parameters n = 50 and pn = 0.9.

heading: A.3 GENERALIZATION FOR REGULAR GRAPHS
text: We made the following experiment with the same general setting as in Section A.1 with regular graphs. We trained different models for all noise levels between 0 and 0.22 but in Figure 3, we plot the accuracy of each model across all noise levels. We observe that a majority of the models actually generalize to settings with noise level on which they were not trained. Indeed, the model trained with noise level ≈ 0.1 is performing best among all models across all noise levels!

heading: B WEISFEILER-LEHMAN TESTS
text: Here we describe more precisely this hierarchy of 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.

heading: B.1 WEISFEILER-LEHMAN TEST ON VERTICES
text: We now present the initial vertex coloring algorithm.
Input. This algorithm takes as input a discrete graph structure G = (V,E) ∈ Gn with V = [n], E ⊆ V 2 and h ∈ Fn0 features on the vertices.
Initialization. Each vertex s ∈ V is given a color c0WL(G, h)s = hs corresponding to its features vector.
Refining the coloring. The colors of the vertices are updated as follows, ct+1WL (G, h)s = Lex ( ctWL(G, h)s, {{ ctWL(G, h)(s̃) : s̃ ∼ s }}) ,
and the function Lex means that all occuring colors are lexicographically ordered.
For each graph G ∈ Gn and each vector of features h ∈ Fn0 , there exists a time T (G, h) from which the sequence of colorings (ctWL(G, h))t≥0 is stationary. More exactly, the colorings are not refined anymore: for any t ≥ T (G, h), s, s′ ∈ V ,
ctWL(G, h)s = c t WL(G, h)s′ ⇐⇒ c T (G,h) WL (G, h)s = c T (G,h) WL (G, h)s′ .
Denote the resulting coloring cT (G,h)WL (G, h) by simply cWL(G, h). cWL is now a mapping from Gn × Fn0 → Zn for some space of colors Z.
Invariant tests The proper Weisfeiler-Lehman test is invariant and is defined by, for t ≥ 0 and (G, h) ∈ Gn × Fn0 a graph,
WLtI(G) = {{ ctWL(G)s : s ∈ V }} WLI(G) = {{cWL(G)s : s ∈ V }}
Equivariant tests For the vertex coloring algorithm, cWL is already an equiavriant mapping so we define, for t ≥ 0 and (G, h) ∈ Gn × Fn0 a graph,
WLtE = c t WL WLE = cWL
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 a k-tuple w.r.t. a graph described by a tensor Fn20 .
A k-tuple (i1, . . . , ik) ∈ [n]k in a graph G ∈ Fn 2 0 and a k-tuple (j1, . . . , jk) ∈ [n]k in a graph H ∈ Fn20 are said to have the same isomoprhism type if the mapping iw 7→ jw is a well-defined partial isormophism. Explicitly, this means that,
• ∀w,w′ ∈ [k], iw = iw′ ⇐⇒ jw = jw′ . • ∀w,w′ ∈ [k], Giw,iw′ = Hjw,jw′ .
Denote by iso(G)i1,...,ik the isomorphism type of the k-tuple (i1, . . . , ik) ∈ [n]k in a graph G ∈ Fn 2 0 .
B.3 WEISFEILER-LEHMAN AND FOLKLORE WEISFEILER-LEHMAN TESTS OF ORDER k ≥ 2
We now present the folklore version of the Weisfeiler-Lehman test of order k (k-FWL), for k ≥ 2, along with k-WL for clarity. For both, we follow the presentation of Maron et al. (2019a) (except for the equivariant tests).
Input. These algorithms take as input a graph G ∈ Fn20 which can be seen as a coloring on the pair of nodes.
Initialization. Each k-tuple s ∈ V k is given a color c0k-WL(G)s = c0k-FWL(G)s corresponding to its isomorphism type.
k-WL. The k-WL test relies on the following notion of neighborhood, defined by, for any w ∈ [k], and s = (i1, . . . , ik) ∈ V k,
Nw(s) = {(i1, . . . , iw−1, j, iw+1, . . . , ik) : j ∈ V } . (WL)
Then, the colors of the k-tuples s ∈ V k are refined as follows, ct+1WL (G)s = Lex ( ctk-WL(G)s, (C t 1(s), . . . , C t k(s)) ) .
where, for w ∈ [k], Ctw(s) = {{ ctk-WL(G)s̃ : s̃ ∈ Nw(s) }} .
For each graph G ∈ Fn0 , there exists a time T (G) from which the sequence of colorings (ctk-WL(G))t≥0 is stationary. More exactly, the colorings are not refined anymore: for any t ≥ T (G), s, s′ ∈ V k,
ctk-WL(G)s = c t k-WL(G)s′ ⇐⇒ c T (G) k-WL (G)s = c T (G) k-WL (G)s′ .
Denote the resulting coloring cT (G)k-WL (G) by simply ck-WL(G).
k-FWL. For k-FWL, the corresponding notion of neighborhood is defined by, for any j ∈ V , and s = (i1, . . . , ik) ∈ V k,
NFj (s) = {(j, i2, . . . , ik), (i1, j, i3, . . . , ik), . . . , (i1, i2, . . . , ik−1, j)} (FWL)
Then, the colors of the k-tuples s ∈ V k are refined as follows, ct+1k-WL(G)s = Lex ( ctk-FWL(G)s, {{ Ctj(s) : j ∈ V }}) ,
where, for j ∈ V ,
Ctj(s) = ( ctk-FWL(G)s̃ : s̃ ∈ NFj (s) ) .
Like k-WL, for each graph G ∈ Fn0 , there exists a time T (G) from which the sequence of colorings (ctk-WL(G))t≥0 is stationary. Similarly, denote the resulting coloring c T (G) k-WL (G) by simply ck-WL(G).
The colors ctk-FWL and c t k-FWL at iteration t define a mapping from Fn
2
0 to space of colorings of k-tuples, Zn k for some space Z.
Invariant tests The standard versions of the Weisfeiler-Lehman tests are invariant and can be defined by, for t ≥ 0 and G ∈ Fn20 a graph,
k-WLtI(G) = {{ ctk-WL(G)s : s ∈ V k }} k-WLI(G) = {{ ck-WL(G)s : s ∈ V k
}} k-FWLtI(G) = {{ ctk-FWL(G)s : s ∈ V k
}} k-FWLI(G) = {{ ck-FWL(G)s : s ∈ V k }} .
Equivariant tests We now introduce the equivariant version of these tests. Many extensions are possible, we chose this one for its simplicity. For t ≥ 0, G ∈ Fn20 a graph, i ∈ V ,
k-WLtE(G)i = {{ ctk-WL(G)s : s ∈ V k, s1 = i }} k-WLE(G)i = {{ ck-WL(G)s : s ∈ V k, s1 = i
}} k-FWLtE(G)i = {{ ctk-FWL(G)s : s ∈ V k, s1 = i
}} k-FWLE(G)i = {{ ck-FWL(G)s : s ∈ V k, s1 = i }} .

heading: C SEPARATING POWER OF GNN
text: The goal of this section is to prove, Proposition 3. We have, for k ≥ 2,
ρ (MGNNI) = ρ (2-WLI) ρ (MGNNE) = ρ (2-WLE) (4) ρ (k-LGNNI) = ρ (k-WLI) ρ (k-LGNNE) ⊆ ρ (k-WLE) (5) ρ (k-FGNNI) = ρ ((k + 1)-WLI) ρ (k-FGNNE) = ρ ((k + 1)-WLE) (6)

heading: C.1 MUTLI-LINEAR PERCEPTRONS
text: 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 finite-dimensional feature spaces F0 and F1, we only assume we are given a class of (continuous) MLP from F0 to F1 which is large enough to be dense in C(F0,F1). See for instance Hornik et al. (1989); Cybenko (1989) for precise conditions for MLP to be universal.

heading: C.2 AUGMENTED SEPARATING POWER
text: To factor the proof, we introduce another notion of separating power. Definition 7. For n,m ≥ 1 fixed, let X be a set, F be a some space and F be a set of functions from X to Y = Fn×m. Then, the augmented separating power of F is,
ρaugmn,m (F) = ρ ({(x, i, j) ∈ X × {1, . . . , n} × {1, . . . ,m} 7→ f(x)i,j : f ∈ F}) .
Explicitly, for x, y ∈ X , i, j ∈ {1, . . . , n}, (x, i, j, y, k, l) ∈ ρaugmn,m (F) ⇐⇒ ∀f ∈ F , f(x)i,j = f(y)k,l .
Note that when n = m = 1, the augmented separating power is exactly the same as the original separating power, so we identify ρ (.) with ρaugm1,1 (.). We also identify ρ augm n,1 (.) with ρ augm 1,n (.), that we denote by ρaugmn (.).
First, it is easy to see that this notion is more precise than the separating power. Lemma 8. If F and G are set of functions from X to Fn×m,
ρaugmn,m (F) ⊆ ρaugmn,m (G) =⇒ ρ (F) ⊆ ρ (G) , and, in particular,
ρaugmn,m (F) = ρaugmn,m (G) =⇒ ρ (F) = ρ (G) ,
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 ≥ 1 fixed, let X be a compact topological space, Y = Fn×m, F some finitedimensional space, F ⊆ C(X,Y ), and τ : X → Zn×m a function for some space Z. Define F̃ ⊆ C(X,Fn) by,
F̃ = x ∈ X 7−→  m∑ j=1 h(f(x)1,j), m∑ j=1 h(f(x)2,j), . . . , m∑ i=1 h(f(x)n,j)  : h : F→ F MLP, f ∈ F  .
and τ̃ : X → Z̃n by, for x ∈ X , ∀i ∈ {1, . . . , n}, τ̃(x)i = {{τ(x)i,j : 1 ≤ j ≤ m}} .
Then,
ρaugmn,m (F) ⊆ ρaugmn,m (τ) =⇒ ρaugmn,m ( F̃ ) ⊆ ρaugmn,m (τ̃)
ρaugmn,m (F) ⊃ ρaugmn,m (τ) =⇒ ρaugmn,m ( F̃ ) ⊃ ρaugmn,m (τ̃) .
Note that, in the statement, we implicitly see F̃ as a set of functions from X to Fn×1 to fit the definition of augmented separating power.
Proof. We show the two inclusions independently.
(⊆) We first show that, ρaugmn,m (F) ⊆ ρaugmn,m (τ) =⇒ ρaugmn,m ( F̃ ) ⊆ ρaugmn,m (τ̃)
Take (x, i, y, k) ∈ ρaugmn,m ( F̃ )
. This means that, for any h : F→ F, f ∈ F , m∑ j=1 h(f(x)i,j) = m∑ j=1 h(f(y)k,j) .
By Lem. 31 and the universality of MLP, there exists a permutation σ ∈ Sm such that (f(x)i,σ(1), . . . , f(x)i,σ(m)) = (f(y)k,1, . . . , f(y)k,m). By definition of the augmented separating power, this means that, for any j ∈ {1, . . . ,m}, (x, i, σ(j), y, k, j) ∈ ρaugmn,m (F). Hence, by assumption, for any j ∈ {1, . . . ,m}, (x, i, σ(j), y, k, j) ∈ ρaugmn,m (τ), i.e. τ(x)i,σ(j) = τ(y)k,j . But this exactly means that τ̃(x)i = τ̃(y)k so that (x, i, y, k) ∈ ρaugmn,m (τ̃) as required.
(⊃) We now show the other inclusion, ρaugmn,m (F) ⊃ ρaugmn,m (τ) =⇒ ρaugmn,m ( F̃ ) ⊃ ρaugmn,m (τ̃) .
Take (x, i, y, k) ∈ ρaugmn,m (τ̃). By definition of τ̃ , this means that there exists σ ∈ Sm such that τ(x)i,σ(j) = τ(y)k,j so that (x, i, σ(j), y, k, j) ∈ ρaugmn,m (τ) ⊆ ρaugmn,m (F). Hence, for any f ∈ F , (f(x)i,σ(1), . . . , f(x)i,σ(m)) = (f(y)k,1, . . . , f(y)k,m), and so, for any h : F→ F,
m∑ j=1 h(f(x)i,j) = m∑ j=1 h(f(y)k,j) .
Therefore, (x, i, y, k) ∈ ρaugmn,m ( F̃ ) , which concludes the proof.
C.3 INITIALIZATION LAYER
We use the same initialization layer as Maron et al. (2019a); Chen et al. (2020) and recall it below. The initial graph is a tensor of the form G ∈ Fn20 with F0 = Re+2; the last channel of G:,:,e+1 encodes the adjacency matrix of the graph and the first e channels G:,:,1:e are zero outside the diagonal and Gi,i,1:e ∈ Re is the color of vertex vi ∈ V . We then define Ik : Fn 2 0 → Fn k 1 with F1 = Rk 2×(e+2) as follows:
Ik(G)i,r,s,w = Gir,is,w, w ∈ [e+ 1], Ik(G)i,r,s,e+2 = 1(ir = is),
for i ∈ [n]k and r, s ∈ [k]. This linear equivariant layer has the same separating power as the isormorphism type, which is defined in Section B.2.
Lemma 10 ((Maron et al., 2019a, C.1)). For k ≥ 2, p0 ≥ 1, F0 = Rp0 , F1 = Rk 2×(p0+1), there exists Ik : Fn20 → Fn k 1 such that,
ρaugm n,nk−1
( Ik )
= ρaugm n,nk−1 (iso) .

heading: C.4 KNOWN RESULTS ABOUT THE SEPARATING POWER OF SOME GNN CLASSES
text: 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.
MGNNemb = {FT ◦ . . . F2 ◦ F1 : Ft : Fnt → Fnt+1 message passing layer, t = 1, . . . , T, T ≥ 1} k-LGNNemb = {FT ◦ . . . F2 ◦ F1 ◦ Ik : Fnt → Fnt+1 linear equivariant layer, t = 1, . . . , T, T ≥ 1} k-FGNNemb = {FT ◦ . . . F2 ◦ F1 ◦ Ik : Fnt → Fnt+1 FGL, t = 1, . . . , T, T ≥ 1} .
Then, the precise results from the literature can be rephrased as,
Lemma 11 (Xu et al. (2018),Maron et al. (2018),Maron et al. (2019a)). For k ≥ 2,
ρaugmn (MGNNemb) = ρ augm n (cWL) (8)
ρaugm n,nk−1 (k-LGNNemb) ⊆ ρaugmn,nk−1 (ck-WL) (9) ρaugm n,nk−1 (k-FGNNemb) ⊆ ρaugmn,nk−1 (ck-FWL) (10)
(8) comes from Xu et 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 k = 2 is already proven in Geerts (2020a).
Lemma 12. For any k ≥ 2,
ρaugm n,nk−1 (k-FGNNemb) ⊃ ρaugmn,nk−1 (ck-FWL) ,
so that ρaugm n,nk−1 (k-FGNNemb) = ρ augm n,nk−1 (ck-FWL) .
Proof. Define,
k-FGNNTemb = {FT ◦ . . . F2 ◦ F1 ◦ Ik : Fnt → Fnt+1 FGL, t = 1, . . . , T} ,
the set of functions defined by exactly T FGL layers. We show by induction that, for any T ≥ 0,
ρaugm n,nk−1 ( k-FGNNTemb ) ⊃ ρaugm n,nk−1 ( cTk-FWL ) .
For T = 0, this is immediate by the definition of Ik in Section C.3.
Assume now that this inclusion holds at T−1 ≥ 0. We show that it also holds at T . TakeG,G′ ∈ Fnk0 and s, s′ ∈ [n]k such that,
cTk-FWL(G)s = c T k-FWL(G ′)s′ .
We need to show that, for any f ∈ k-FGNNTemb,
f(G)s = f(G ′)s′ .
But, by definition of the update rule k-FWL, the equality of the colors of s and s′ above implies that,
cT−1k-FWL(G)s = c T−1 k-FWL(G ′)s′ , (11)
and that there exists σ ∈ Sn such that, for any j ∈ [n],( cT−1k-FWL(G)s̃ : s̃ ∈ N F j (s) ) = ( cT−1k-FWL(G ′)s̃ : s̃ ∈ NFσ(j)(s ′) ) .
Let s = (i1, . . . , ik) and s′ = (j1, . . . , jk). Then this implies that, for any w ∈ [k], j ∈ [n],
cT−1k-FWL(G)i1,...,iw−1,j,iw+1,...,ik = c T−1 k-FWL(G ′)j1,...,jw−1,σ(j),jw+1,...,jk . (12)
We now use the induction hypothesis, i.e. that,
ρaugm n,nk−1 ( k-FGNNT−1emb ) ⊃ ρaugm n,nk−1 ( cT−1k-FWL ) .
Take any fT−1 ∈ k-FGNNT−1emb . By (11),
fT−1(G)s = fT−1(G ′)s′ .
By (12), for any w ∈ [k], j ∈ [n],
fT−1(G)i1,...,iw−1,j,iw+1,...,ik = f T−1(G′)j1,...,jw−1,σ(j),jw+1,...,jk .
By the definition of FGL Section 3.3, for any FT : Fn k T → Fn k T+1 FGL, FT ◦ fT−1(G)s = FT ◦ fT−1(G ′)s′ . Therefore, for any f ∈ k-FGNNTemb,
f(G)s = f(G ′)s′ ,
which concludes the proof.

heading: C.6 CONCLUSION
text: Proposition 13. We have, for k ≥ 2,
ρ (MGNNI) = ρ (2-WLI) ρ (MGNNE) = ρ (2-WLE) (13) ρ (2-LGNNI) = ρ (2-WLI) (14) ρ (k-LGNNI) ⊆ ρ (k-WLI) ρ (k-LGNNE) ⊆ ρ (k-WLE) (15) ρ (k-FGNNI) = ρ (k-FWLI) ρ (k-FGNNE) = ρ (k-FWLE) (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 case comes from Lem. 11, Lem. 8, the fact that the layers mE ◦ (Id +λS1) does not change the separating power and recalling that simply WLE = 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. 8 and the fact that the layer mE does not change the separating power.
• Proof of (16). The direct inclusion of the invariant case corresponds to Maron et al. (2019a, Thm. 2). The other cases are a consequence of Lem. 11, Lem. 9, Lem. 8 and the fact that the layers mI and mE does not change the separating power.

heading: D STONE-WEIERSTRASS THEOREM WITH SYMMETRIES
text: This section presents our extension of the Stone-Weierstrass theorem dealing with functions with symmetries. The scope of this section is not restricted to graphs or even tensors and we 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

heading: D.1 GENERAL NOTATIONS
text: As explained above, we are dealing in this section with a much larger scope than graphs and permutations. We first need to extend the notations introduced above. The notations introduced below will make this section self-contained.
If X is some topological space, and F ⊆ X , denote by F its closure. If X is a topological space and Y = Rp some finite-dimensional space, denote by C(X,Y ) the set of continuous functions from X to Y .
Moreover, if X is compact, we endow C(X,Y ) with the topology of uniform convergence, which is defined by the norm, f 7→ supx∈X ‖f(x)‖ for some norm ‖.‖ on Y . If G is a finite group acting on some topological space X , we say that G acts continuously on X if, for all g ∈ G, x 7→ g · x 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,
CE(X,Y ) = {f ∈ C(X,Y ) : ∀x ∈ X, ∀g ∈ G, f(g · x) = g · f(x)} CI(X,Y ) = {f ∈ C(X,Y ) : ∀x ∈ X, ∀g ∈ G, f(g · x) = f(x)}
Note that these definitions extend Definition 1 to a general group.
If Y = Rp, we denote the coordinate-wise multiplication, or Hadamard product of y, y′ ∈ Y simply by yy′ = (y1y′1, . . . , ypy ′ p) ∈ Y . We say that a subset A ⊆ Rp is a subalgebra of Rp if it is both a linear space and stable by multiplication.
This product in turn defines a product on C(X,Y ) with Y = Rp by, for f, g ∈ C(X,Y ), fg : x 7→ f(x)g(x).
In addition, we also extend the scalar-vector product of Y = Rp to functions: if g ∈ C(X,R) and f ∈ C(X,Y ), their product gf is the function gf : x 7→ g(x)f(x). Given a set of scalar functions S ⊆ C(X,R) and a set of vector-valued functions F ⊆ C(X,Y ), the set of products of functions of these two sets will be denoted by,
S · F = {gf : g ∈ S, f ∈ F} .
Moreover, we denote by 1 the continuous function from some X to Rp defined by x 7→ (1, . . . , 1). In particular, if f is a function from X to R, f1 denotes the function x 7→ (f(x), . . . , f(x)) which goes from X to Y = Rp. Finally, we say that F ⊆ C(X,Y ) with Y being some Rp is a subalgebra if it is a linear space which is also stable by multiplication.

heading: D.2 SEPARATING POWER
text: We recall the definition of separating power that we introduced above: Definition 14. Let F be a set of functions f defined on a set X , where each f takes its values in some Yf . The equivalence relation ρ (F) defined by F on X is: for any x, x′ ∈ X ,
(x, x′) ∈ ρ (F) ⇐⇒ ∀f ∈ F , f(x) = f(x′) .
For a function f , we write ρ (f) for ρ ({f}). Separating power is stable by closure: Lemma 15. Let X be a compact topological space, Y be some finite-dimensional and F ⊆ C(X,Y ). Then,
ρ (F) = ρ ( F )
Proof. As F ⊆ F , F is more separating than F , i.e. ρ ( F ) ⊆ ρ (F).
Conversely, take (x, y) /∈ ρ ( F ) . By definition, there exists h ∈ F such that h(x) 6= h(y) so that if
= ‖h(x) − h(y)‖, > 0 (for some norm ‖.‖ on Y ). As h ∈ F , there is some f ∈ F such that
supX ‖h− f‖ ≤ 3 . Therefore, by the triangular inequality,
= ‖h(x)− h(y)‖ ≤ ‖f(x)− h(x)‖+ ‖f(x)− f(y)‖+ ‖f(y)− h(y)‖ ≤ 2 3 + ‖f(x)− f(y)‖ .
It follows that ‖f(x)− f(y)‖ ≥ 3 > 0 so that f(x) 6= f(y) and (x, y) /∈ ρ (F).

heading: D.3 APPROXIMATION THEOREMS FOR REAL-VALUED FUNCTIONS
text: We start by recalling Stone-Weierstrass theorem, see Rudin (1991, Thm. 5.7).
Theorem 16 (Stone-Weierstrass). Let X be a compact space, and F be a subalgebra of C(X,R) the space of real-valued continuous functions of X , which contains the constant function 1. If F separates points, i.e. ρ (F) = {(x, x) : x ∈ X}, then F is dense in C(X,R).
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. LetX be a compact space, andF be a subalgebra of C(X,R) the space of real-valued continuous functions of X , which contains the constant function 1. Then,
F = {f ∈ C(X,R) : ρ (F) ⊆ ρ (f)} .
Note that if F separates points, we get back the classical result as every function satisfies {(x, x) : x ∈ X} ⊆ ρ (f). Example 18. The invariant version of PointNet is able to learn functions of the form ∑ i f(xi) for f ∈ C(Rp,R). We can apply Corollary 17 to this setting. Consider the case where X is a compact subset of Rp and F = {x 7→ g ( ∑n i=1 f(xi)) , f ∈ C(X,Rh), g ∈ C(Rh,R)}. F is a subalgebra of C(X,R) (indeed of CI(X,R)) which contains the constant function 1. Then, it easy to see that ρ (F) = {(x, σ ? x), σ ∈ Sn}, where σ ? x is defined by (σ ? x)σ(i) = xi for all i (see Lem. 31 for a formal statement).
Now note that for a function f ∈ C(X,R), the condition {(x, σ ? x), σ ∈ Sn} ⊆ ρ (f) is equivalent to f ∈ CI(X,R). So that Corollary 17 implies that F = CI(X,R) 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 F ⊆ {f ∈ C(X,R) : ρ (F) ⊆ ρ (f)} follows from the same argument as the one given below Theorem 4 so we focus on the other one.
For every x ∈ X , let xF denote its ρ (F)-class. The quotient set and the canonical surjection are: XF = X/ρ (F) = {xF , x ∈ X} and πF : X → XF , πF (x) = xF . A function g : X → R factorizes as g = ĝ ◦ πF for some ĝ : XF → R if and only if ρ (F) ⊆ ρ (g). In this case ĝ is unique, since πF is a surjection. In particular. every f ∈ F factorizes uniquely as f = f̂ ◦ πF , f̂ : XF → R, and F̂ = {f̂ , f ∈ F} clearly separates points on XF . We refer to Munkres (2000, §22) for the properties of the quotient topology. In particular, by the properties of the quotient topology on XF , F̂ is a subalgebra of C(XF ,R) and XF is compact. Hence, we can apply Theorem 16 to F̂ and F̂ is dense in C(XF ,R).
Now take f ∈ C(X,R) with ρ (F) ⊆ ρ (f) and we show that f ∈ F . Again, ρ (F) ⊆ ρ (f) implies that f = f̂ ◦ πF . Let > 0. By density of F̂ , there is some ĥ ∈ F̂ such that supxF |ĥ(xF )) − f̂(xF )| ≤ . But, by construction of F̂ , there exits h ∈ F such that ĥ ◦ πF = h. Thus,
sup x∈X |h(x)− f(x)| = sup x∈X |ĥ(πF (x))− f̂(πF (x))| = sup xF∈XF |ĥ(xF ))− f̂(xF )| ≤ .
As this holds for any > 0, we have proven that f ∈ F .

heading: D.4 THE EQUIVARIANT APPROXIMATION THEOREM
text: We first need to extend Corollary 17 to vector-valued functions. For this, we need to have a vectorvalued version of the Stone-Weierstrass theorem and as shown by the example below additional assumptions have to be made. Example 19. We consider now the equivariant version of PointNet corresponding to the particular case where X is a compact subset of (Rp)n, Y = Rn and F = {x 7→ (f(x1), . . . , f(xn)), f ∈ C(R,R)}. Then clearly F is a subalgebra of CE(X,Y ) containing the constant function 1 and ρ (F) = {(x, x), x ∈ 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 ⊆ CE(X,Y ) which is clearly not dense in C(X,Y ).
We now present an extension of Corollary 17 also due to Timofte (2005): Proposition 20. Let X be a compact space, Y = Rp for some p ≥ 1. Let F ⊆ C(X,Y ). If there exists a nonempty subset S ⊆ C(X,R) such that:
S · F ⊆ F and, ρ (S) ⊆ ρ (F) . (17)
Then we have
F = { f ∈ C(X,Y ), ρ (F) ⊆ ρ (f) , f(x) ∈ F(x) } , (18)
where F(x) = {f(x), f ∈ F}. Moreover in (18), we can replace ρ (F) by ρ (S).
Note that in the particular case Y = R and if F is a subalgebra of C(X,R), then we can take S = F in (17) and if the constant function 1 is in F , then F(x) = R, so that we recover Corollary 17. Now consider the case where F is a subalgebra of C(X,Rp). We need to find a set S ∈ C(X,R) satisfying (17) i.e. with a better separating power than F but containing real-valued functions such that sf ∈ F for all s ∈ S and f ∈ F . In the sequel, we will consider the set Fscal = {f ∈ C(X,R) : f1 ∈ F}. We clearly have Fscal · F ⊆ F since F is a subalgebra. Hence, in this setting, Prop. 20 can be rewritten as follows: Corollary 21. Let X be a compact space, Y = Rp for some p, G be a finite group acting (continuously) on X and F ⊆ CI(X,Y ) a (non-empty) set of invariant functions associated to G.

heading: Consider the following assumptions,
text: 1. F is a sub-algebra of C(X,Y ) and the constant function 1 is in F .
2. The set of functions Fscal ⊆ C(X,R) defined by,
Fscal = {f ∈ C(X,R) : f1 ∈ F}
satisfy, ρ (Fscal) ⊆ ρ (F) .
3. For any x ∈ X , there exists f ∈ F such that f(x) has pairwise distinct coordinates, i.e., for any indices i, j ∈ {1, . . . , p} with i 6= j, f(x)i 6= f(x)j .
Then the closure of F (for the topology of uniform convergence) is,
F = {f ∈ CI(X,Y ) : ρ (F) ⊆ ρ (f)} .
Note that Assumptions 1 and 2 ensures that (17) is valid, while Assumption 3 ensures thatF(x) = Rp. Unfortunately, in the equivariant case, the condition ρ (Fscal) ⊆ ρ (F) is too strong and we now explain how we will relax it.
For the sake of simplicity, we consider here the particular setting adapted to graphs: let n ≥ 1 be a fixed number (corresponding to the number of nodes), X be a compact set of graphs in Rn2 and Y = Fn with F = Rp for some p ≥ 1. We define the action of the symmetric group Sn on X by (σ ? x)σ(i),σ(j) = xi.j and on Y by (σ ? y)σ(i) = yi ∈ Rp. Hence the set of continuous equivariant functions CE(X,Y ) agrees with Definition 1.
Now consider the case where F ⊆ CE(X,Y ) is a subalgebra of equivariant functions. Then, f ∈ Fscal needs to be invariant in order for f1 to be equivariant and hence in F . As a result, we see that Fscal will not separate points of X in the same orbit, i.e. x and σ ? x. But these points will typically be separated by F , since for any f ∈ F , we have f(σ ? x) = σ ? f(x) which is not equal to f(x) unless f 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) = {σ ? x, σ ∈ Sn} and Orb(y) = {σ ? y, σ ∈ Sn}. For any equivariant function f ∈ CE(X,Y ), for any z ∈ Orb(x), we have f(z) ∈ Orb(f(x)). Then let π : Y → Y/Sn be the canonical projection π(y) = Orb(y). We define
(x, x′) ∈ ρ (π ◦ F) ⇔ ∀f ∈ F , Orb(f(x)) = Orb(f(x′)) ⇔ ∀f ∈ F ,∃σ ∈ Sn, f(σ ? x) = f(x′).
In particular, we see that if x′ ∈ Orb(x) then (x, x′) ∈ ρ (π ◦ F) for any F ∈ CE(X,Y ). Moreover, two graphs x and x′ are ρ (π ◦ F)-distinct if there exists a function f ∈ F such that ∀σ, f(σ ? x) 6= f(x′), i.e. the function f discriminates Orb(x) from Orb(x′) in the sense that for any z ∈ Orb(x) and z′ ∈ Orb(x′), we have f(z) 6= f(z′). To obtain an equivalent of Proposition 20 with CE(X,Y ) replacing C(X,Y ), we are able to relax assumption (17) to ρ (Fscal) ⊆ ρ (π ◦ 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 for some p, G be a finite group acting (continuously) on X and Y and F ⊆ CE(X,Y ) a (non-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 a sub-algebra of C(X,Y ) and the constant function 1 is in F .
2. The set of functions Fscal ⊆ C(X,R) defined by,
Fscal = {f ∈ C(X,R) : f1 ∈ F}
satisfy, ρ (Fscal) ⊆ ρ (π ◦ F) .
Then the closure of F (for the topology of uniform convergence) is,
F = {f ∈ CE(X,Y ) : ρ (F) ⊆ ρ (f) , ∀x ∈ X, f(x) ∈ F(x)} ,
where F(x) = {f(x), f ∈ F}. Moreover, if I(x) = {(i, j) ∈ [p]2 : ∀y ∈ F(x), yi = yj}, then we have:
F(x) = {y ∈ Rp : ∀(i, j) ∈ I(x), yi = yj} .
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 = Rn and the group being the symmetric group Sn. 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 x ∈ Rn 7→ (f(x1) . . . f(xn)), which are not universal in the class of equivariant functions, as shown by Segol & Lipman (2020, Lem. 3). Now, their transmission layer is a map of the form x ∈ Rn 7→ (1Tx)1. Therefore, in PointNetST, adding such a layer precisely adds a large class of functions to F = {(f(x1, ∑ i g(xi)), . . . , f(xn, ∑ i g(xi))), f ∈ C(R× Rh,R), g ∈ C(R,Rh), h ≥ 1}. F is still an algebra and as shown in Example 19, we have ρ (F) = {(x, x), x ∈ X}. Moreover, we have Fscal = CI(X,R) by Lem. 33 in particular, we get ρ (Fscal) = {(x, σ ? x), x ∈ X}, so that we obviously have ρ (Fscal) ⊆ ρ (π ◦ F). In summary, Theorem 22 implies the universality of PointNetST in CE(X,Y ).

heading: D.5 A PRELIMINARY VERSION OF THE EQUIVARIANT APPROXIMATION THEOREM
text: We start by proving a version of Theorem 22 with a slightly weaker condition:
Proposition 24. Let X be a compact space, Y = Rp for some p, G be a finite group acting (continuously) on X and Y and F ⊆ CE(X,Y ) a (non-empty) set of equivariant functions.

heading: Consider the following assumptions,
text: 1. F is a subalgebra CE(X,Y ).
2. The set of real-valued functions Fscal ⊆ C(X,R) defined by,
Fscal = {f ∈ C(X,R) : f1 ∈ F}
satisfies,
ρ (Fscal) ⊆ {(x, x′) ∈ X ×X : ∃g ∈ G, (g · x, x′) ∈ ρ (F)} .
Then the closure of F (for the topology of uniform convergence) is, F = { f ∈ CE(X,Y ) : ρ (F) ⊆ ρ (f) , ∀x ∈ X, f(x) ∈ F(x) } , (19)
where F(x) = {f(x), f ∈ F}.
The proof of this theorem relies on two main ingredients. First, following the elegant idea of Maehara & Hoang (2019), we augment the input space to transform the vector-valued equivariant functions into scalar maps. Second, we apply the fine-grained approximation result Cor. 17.
Proof. As uniform convergence implies point-wise convergence, the first inclusion is immediate, F ⊆ { f ∈ CE(X,Y ) : ρ (F) ⊆ ρ (f) , ∀x ∈ X, f(x) ∈ F(x) } .
The rest of the proof is devoted to the other direction.
For convenience, denote by Φ the family of linear forms associated to the canonical basis of Rp, i.e.,
Φ = {y 7→ yi : 1 ≤ i ≤ p} ⊆ C(Y,R) .
Define our augmented input space as X̃ = X × Φ. As Φ is finite and X is compact, X̃ is still a compact space. We now transform F , a class of equivariant functions from X to Y , into F̃ a class of maps from X̃ to R. Define
F̃ = {(x, ϕ) 7→ ϕ(f(x)) : f ∈ F} .
We check that F̃ is indeed a subset of C(X̃,R). Indeed, as Φ is finite, it is equipped with the discrete topology. Hence, each singleton {ϕ} for ϕ ∈ Φ is open in Φ and it suffices to check the continuity in the first variable with ϕ fixed. But, if f ∈ F , x 7→ ϕ(f(x)) is continuous as a composition of continuous maps.
We can now apply Cor. 17 to F̃ ⊆ C(X̃,R). Therefore, the closure of F̃ in C(X̃,R) is, F̃ = { v ∈ C(X̃,R) : ρ ( F̃ ) ⊆ ρ (v) , ∀(x, ϕ) ∈ X̃, v(x, ϕ) ∈ F̃(x, ϕ) } .
We now show the equality of (19). Take h in the right-hand side of (19), i.e. h ∈ CE(X,Y ) such that ρ (F) ⊆ ρ (h) and h(x) ∈ F(x) for all x ∈ X . We show that h̃, defined by h̃ : (x, ϕ) 7→ ϕ(h(x)), belongs to F̃ using the result above.
• As h is continuous, by the same argument as above, (x, ϕ) 7→ ϕ(h(x)) is continuous on X̃ .
• We check that ρ ( F̃ ) ⊆ ρ ( h̃ ) .
Take (x, ϕ), (y, ψ) ∈ X̃ such that, for all f ∈ F ,
ϕ(f(x)) = ψ(f(y)) , (20)
and we aim at showing that ϕ(h(x)) = ψ(h(y)).
To gain more information from (20), we apply it to functions of the form f1 with f ∈ Fscal. By definition of Φ, this translates to f(x) = f(y), for any f ∈ Fscal. Therefore (x, y) ∈ ρ (Fscal) and so there exists g ∈ G such that (g · x, y) ∈ ρ (F). Plugging this into (20) and using the equivariance of f ,
∀f ∈ F , ϕ(f(x)) = ψ(g · f(x)) .
As G acts continuously on Y , both ϕ and z 7→ ψ(g ·z) are continuous and, as a consequence of the equality above, coincide on F(x). But we assumed that h(x) ∈ F(x) and therefore the equality also holds for h, i.e. ϕ(h(x)) = ψ(g · h(x)). Finally, recalls that, by assumption, ρ (F) ⊆ ρ (h). Therefore (g · x, y) ∈ ρ (F) implies that h(g · x) = h(y) and, combined with the result above, ϕ(h(x)) = ψ(h(y)).
• We verify that, for x ∈ X , ϕ ∈ Φ, ϕ(h(x)) belongs to F̃(x). Indeed, recall that h(x) ∈ F(x). Therefore, as ϕ is continuous, ϕ(h(x)) is in ϕ(F(x)) which is included in F̃(x).
This shows that h̃ : (x, ϕ) 7→ ϕ(h(x)) is in F̃ . Consequently, for any > 0, there exists f ∈ F such that, ∀x ∈ X, ∀ϕ ∈ Φ, |ϕ(h(x))− ϕ(f(x))| ≤ . If Y = Rp is endowed with the infinity norms on coordinates, by definition of Φ, this means that,
∀x ∈ X, ‖h(x)− f(x)‖ ≤ .
Remark 25. In the particular case of G ⊆ Sn being a group of permutations acting on Rp by, for g ∈ G, x ∈ Rp,
∀i ∈ {1, . . . , p}, (g · x)i = xg−1(i) ,
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, ϕ ∈ Φ,
∀x ∈ Rp, (g · ϕ)(x) = ϕ(g−1 · x) .
In other words, the action of g on the linear form associated to the ith coordinate yields the linear form associated to the g(i)th coordinate. One can now check that the functions F̃ 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 Rp. For this, we will use the following simple lemma.
In the following lemma, R[X1, . . . , Xp] denotes the set of multivariate polynomials with p indeterminates (and real coefficients).
Lemma 26. Let C ⊆ Rp be a finite subset of Rp. There exists P ∈ R[X1, . . . , Xp] such that P|C , the restriction of P to C, is an injective map.
Proof. Let x1, . . . , xm ∈ Rp be distinct vectors such that {x1, . . . , xm} = C. Similarly to Lagrange polynomials, define,
P (X1, . . . , Xp) = m∑ i=1 i ∏ j 6=i ∑p l=1(Xl − x j l ) 2 ‖xi − xj‖22 , (21)
which is a well-defined multivariate polynomial. Note that, seeing X = (X1, . . . , Xp) as a vector in Rp, it can also be written as,
P (X1, . . . , Xp) = m∑ i=1 i ∏ j 6=i ‖X − xj‖22 ‖xi − xj‖22 . (22)
By construction, P (xi) = i and therefore P is an injective map on C
Lemma 27. For a subalgebra A of Rp, we define: J = {j ∈ {1, . . . , p} : ∀x ∈ A, xj = 0} I = {(i, j) ∈ (JC)2 : ∀x ∈ A, xi = xj} .
Then, we have : A = {x ∈ Rp : ∀(i, j) ∈ I, xi = xj , ∀j ∈ J, xj = 0} .
Proof. Before proving the general case, we focus on the situation where A will turn out to be the whole Rp.
Assume that the two following conditions holds,
∀i 6= j, ∃x ∈ A, xi 6= xj (23) ∀i, ∃x ∈ A, xi 6= 0 (24)
Our goal is to show that, under these additional assumptions, A = Rp. We divide the proof in three parts, first we show that 1 ∈ A using (24), giving us that A is closed under polynomials, then that there is x ∈ 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 ∈ A.
– First, we construct by induction x ∈ A such that xi 6= 0 for any index i. More precisely, our induction hypothesis at step j ∈ {1, . . . , p} is,
∃x ∈ A, ∀1 ≤ i ≤ j, xi 6= 0 . (25) By (24), this holds for j = 1. Now, assume that it holds at j−1 for some p ≥ j ≥ 2 and take x ∈ A such that xi 6= 0 for any 1 ≤ i ≤ j − 1 and y ∈ A such that jj 6= 0 by (24). By definition of x, the set,
{λ ∈ R : ∃1 ≤ i ≤ j − 1, λxi + yi = 0} , is finite. Thus, there exists λ ∈ R such that λxi + yi 6= 0 for any 1 ≤ i ≤ j− 1 and for i = j too as xj = 0 and yj 6= 0. As A is a subalgebra, λx+ y ∈ A and this concludes the induction step.
– Let x ∈ A be the vector constructed, i.e. such that xi 6= 0 for every index i. We prove that 1 ∈ A by constructing 1 from x. Indeed, using Lagrange interpolation, take P ∈ R[X] such that P (xi) = 1xi for every i. (Note that this noes not matter if some xi are equal, as the 1xi would also be the same.) Finally, as A is a subalgebra, xP (x), which is to be understood coordinate-wise, is in A and so is 1 = xP (x).
• We show that the previous point and (23) imply that there exists a vector in A with pairwise distinct coordinates, i.e. that there exists x ∈ A such that, for any i 6= j, xi 6= xj . Using (23), for any i < j, there exists xij ∈ A such that xiji 6= x ij j . We wish to combine the family
(xij)i<j into a single vector.
For this we use Lem. 26. Seeing each collection (xijk )i<j as vector of Rp(p−1)/2, we define C = {(xijk )i<j : 1 ≤ k ≤ p}, which is a finite subset (of cardinal p) of Rp(p−1)/2. By Lem. 26, there exists P ∈ R[X1, . . . , Xp(p−1)/2] such that P is an injective map on C.
As A is a subalgebra and 1 ∈ A, the vector,
P ( (xij)i<j ) =  P ( (xij1 )i<j ) ...
P ( (xijp )i<j
)  ,
is in A too. We now check that this vector has pairwise distinct coordinates. Let l < k, then xlkl 6= xlkk and therefore (xijl )i<j 6= (x ij k )i<j . By construction of P , P ( (xijl )i<j ) 6= P ( (xijk )i<j ) ,
i.e. P ( (xij)i<j ) l 6= P ( (xij)i<j ) k . Thus, P ( (xij)i<j ) ∈ A has pairwise distinct coordinates as required.
• Finally, we show that A = Rp. This is a direct consequence of the point above and of Lagrange interpolation. Indeed, take any y ∈ Rp and denote by x ∈ A the vector that we just constructed with pairwise distinct coordinates. Therefore, by Lagrange interpolation, there exists P ∈ R[X] such that P (xi) = yi for every i ∈ {1, . . . , p}. As A is a sublagebra and 1 ∈ A, P (x) ∈ A and hence y ∈ A.
Finally, we 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 ∈ {1, . . . , p} : ∀x ∈ A, xj = 0} I = {(i, j) ∈ (JC)2 : ∀x ∈ A, xi = xj} .
and denote by A′ = {x ∈ Rp : ∀(i, j) ∈ I, xi = xj , ∀j ∈ J, xj = 0}, which is also a subalgebra. By definition, it holds that A ⊆ A′. By construction, I is an equivalence relation on JC and denote by JC/I its equivalence classes. Let p′ = |JC/I| and choose i1, . . . , ip′ representatives of the equivalence classes. Consider the map,
ϕ :
{ Rp −→ Rp ′
x 7−→ (xi1 , . . . , xip′ ) .
ϕ is an algebra homomoprhism so that ϕ(A) is a subalgebra of Rp′ . But, by construction of I and J , ϕ(A) satisfies (23) and (24). Whence, by our result in this particular case, ϕ(A) = Rp′ .
However, A ⊆ A′ implies that ϕ(A) ⊆ ϕ(A′) ⊆ Rp′ . Therefore, Rp′ = ϕ(A) = ϕ(A′). But, by construction of ϕ, ϕ is actually an injective map on A′. Therefore, we deduce from ϕ(A) = ϕ(A′) that A = A′, concluding the proof.

heading: D.7 PROOF OF THE MAIN EQUIVARIANT APPROXIMATION THEOREM
text: We can now fully exploit the structure of subalgebra of F 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 ⊆ G subgroup, for any x, y ∈ X ,
∀f ∈ F , ∃g ∈ H, f(g · x) = f(y) ⇐⇒ ∃g ∈ H, ∀f ∈ F , f(g · x) = f(y) .

heading: In particular,
text: (x, y) ∈ ρ (π ◦ F) ⇐⇒ ∃g ∈ G, (g · x, y) ∈ ρ (F) .
Proof. The reverse implication is immediate so we focus on the direct one and prove its contraposition, i.e., ∀g ∈ H, ∃f ∈ F , f(g · x) 6= f(y) =⇒ ∃f ∈ F , ∀g ∈ H, f(g · x) 6= f(y) . To prove this, we take advantage of F being a subalgebra and H being finite. Let H = {g1, . . . , gh} and define,
A = {(f(g1 · x), . . . , f(gh · x), f(y)) : f ∈ F} .
As F is a subalgebra of C(X,Rp), A is a subalgebra of Rp′ with p′ = p(h+ 1). By Lem. 27,
A = {z ∈ Rp ′
: ∀(i, j) ∈ I, zi = zj , ∀j ∈ J, zj = 0} . where I and J can be chosen to be,1
J = {j ∈ {1, . . . , p} : ∀z ∈ A, zj = 0} I = {(i, j) ∈ {1, . . . , p}2 : ∀z ∈ A, zi = zj} .
As I is an equivalence relation, an element of A is uniquely defined by its coordinates on equivalence classes of I . Therefore, one can choose z ∈ A such that zi = zj ⇐⇒ (i, j) ∈ I . By definition of A, there exists f∗ ∈ F such that (f∗(g1 · x), . . . , f∗(gh · x), f∗(y)) = z. We now check that f∗ is indeed appropriate. Take l ∈ {1, . . . , h}, we want to show that f∗(gl · x) 6= f∗(y). By assumption, there exists f ∈ F such that f(gl · x) 6= f(y), i.e. there exists i ∈ {1, . . . , p} such that f(gl · x)i 6= f(y)i. Therefore, ((l − 1)p+ i, hp+ i) cannot be in I so that z(l−1)p+i 6= zhp+1, i.e. f∗(gl · x)i 6= f∗(y)i.
We now prove our main abstract theorem. Theorem 22. Let X be a compact space, Y = Rp for some p, G be a finite group acting (continuously) on X and Y and F ⊆ CE(X,Y ) a (non-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 a sub-algebra of C(X,Y ) and the constant function 1 is in F .
2. The set of functions Fscal ⊆ C(X,R) defined by, Fscal = {f ∈ C(X,R) : f1 ∈ F}
satisfy, ρ (Fscal) ⊆ ρ (π ◦ F) .
Then the closure of F (for the topology of uniform convergence) is, F = {f ∈ CE(X,Y ) : ρ (F) ⊆ ρ (f) , ∀x ∈ X, f(x) ∈ F(x)} ,
where F(x) = {f(x), f ∈ F}. Moreover, if I(x) = {(i, j) ∈ [p]2 : ∀y ∈ F(x), yi = yj}, then we have:
F(x) = {y ∈ Rp : ∀(i, j) ∈ I(x), yi = yj} .
Proof of Thm. 22. By Lem. 28, the second assumption of Prop. 24 is also satisfied. To get the conclusion of Thm. 22, note that F(x) is now a linear subspace of a finite-dimensional vector space and therefore it is closed. Thus, F(x) = F(x) which is a subalgebra. Applying Lem. 27 to F(x) and noting that, necessarily J = ∅ as 1 ∈ F(x) by assumption, gives the result of Thm. 22.

heading: D.8 PRACTICAL REDUCTIONS
text: Though the results we proved above were formulated using classic hypotheses, such as requiring F to be a subalgebra, we can give much more compact versions for our setting. We also reduce the assumption that ρ (Fscal) ⊆ ρ (π ◦ F) to a more practical one. We start with the invariant case. Corollary 29. Let X be a compact space, Y = F = Rp be some finite-dimensional vector space, G be a finite group acting (continuously) on X and F ⊆ CI(X,Y ) a (non-empty) set of invariant functions.
Assume that, for any h ∈ C(F2,F) and f, g ∈ F , x 7→ h(f(x), g(x)) ∈ F .

heading: Then the closure of F is,
text: F = {f ∈ CI(X,Y ) : ρ (F) ⊆ ρ (f)} .
1We slightly change the definition of I compared to the statement of the lemma to add J2, which does not change the result.
Proof. We wish to apply Thm. 22 but for this we need G to act on Y . Define a (trivial) action of G on Y by, ∀g ∈ G, ∀y ∈ Y, g · y = y . With this action on Y , CE(X,Y ) = CI(X,Y ). Moreover, Y/G = Y , π : Y → Y/G is the identity so that ρ (π ◦ F) = ρ (F). Our assumption clearly ensure that F is indeed a subalgebra and contains the constant function 1. All that is left to show to apply Thm. 22 is that the set of functions Fscal ⊆ C(X,R) defined by,
Fscal = {f ∈ C(X,R) : f1 ∈ F}
satisfies, ρ (Fscal) ⊆ ρ (F) .
Take (x, y) /∈ ρ (F) and we show that (x, y) /∈ ρ (Fscal). Indeed, by definition there exists f ∈ F , i ∈ {1, . . . , p} such that f(x)i 6= f(y)i. Let l ∈ C(F,R) defined by l(z) = zi and h ∈ C(F,F) defined by, for z ∈ F, h(z) = (l(z), . . . , l(z)) = l(z)1. Then, by assumption h ◦ f ∈ F . But h ◦ f is (l ◦ f)1 with l ◦ f ∈ C(X,R), so that, by definition, l ◦ f ∈ Fscal. Moreover, l ◦ f(x) 6= l ◦ f(y). Therefore, (x, y) /∈ ρ (Fscal). Therefore, we can apply Thm. 22. We get that,
F = {f ∈ CE(X,Y ) : ρ (F) ⊆ ρ (f) , ∀x ∈ X, f(x) ∈ F(x)} ,
and F(x) = {y ∈ Fp : ∀(i, j) ∈ I(x), yi = yj} ,
with I(x) given by,
I(x) = {(i, j) ∈ {1, . . . , p}2 : ∀y ∈ F(x), yi = yj} .
To conclude the proof, we now show that I(x) = {(i, i) : i ∈ {1, . . . , p}}, which will imply that F(x) = Rp = Y . Indeed, the constant function z 7→ (1, 2, . . . , p) is in F by assumption. Therefore, I(x) is reduced to {(i, i) : i ∈ {1, . . . , p}}.
In our previous version of our approximation result for node embedding, we did not allow features in the output as it would have made the statement and the proof a bit convoluted. With this new assumption, this is much easier.
Corollary 30. Let X be a compact space, Y = Fn, with F = Rp and G = Sn the permutation group, acting (continuously) on X and acting on Fn by, for σ ∈ Sn, x ∈ Fn,
∀i ∈ {1, . . . , p}, (σ · x)i = xσ−1(i) ,
Let F ⊆ CE(X,Fn) be a (non-empty) set of equivariant functions.

heading: Consider the following assumptions,
text: 1. For any h ∈ C(F2,F), f, g ∈ F ,
x 7→ (h(f(x)1, g(x)1), . . . , h(f(x)n, g(x)n)) ∈ F .
2. If f ∈ F ,
x 7→ ( n∑ i=1 f(x)i, n∑ i=1 f(x)i . . . , n∑ i=1 f(x)i ) ∈ F .
Then the closure of F (for the topology of uniform convergence) is,
F = {f ∈ CE(X,Fn) : ρ (F) ⊆ ρ (f)} .
For this we need a handy lemma, whose proof relies on a result about multi-symmetric polynomials from Maron et al. (2019a).
Lemma 31. Let F = Rp be some finite-dimensional space. Take x1, . . . , xn, y1, . . . , yn ∈ F such that, for any σ ∈ Sn, (x1, . . . , xn) 6= (yσ(1), . . . , yσ(n)). Then, there exists h ∈ C(F,R) such that,
n∑ i=1 h(xi) 6= n∑ i=1 h(yi) .
Moreover, h can be written as h(x) = h1(x1)h2(x2) . . . hp(xp) for any x ∈ F with h1, . . . , hp ∈ C(R,R).
Proof. By Maron et al. (2019a, Prop. 1), there exists α1, . . . , αp non-negative integers such that∑n i=1 x α1 i1 x α2 i2 . . . x αp ip 6= ∑n i=1 y α1 i1 y α2 i2 . . . y αp ip . Taking h : x 7→ x α1 i1 x α2 i2 . . . x αp ip 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 Fscal ⊆ C(X,R) by, Fscal = {f ∈ C(X,R) : f1 ∈ F} .
We have to show that ρ (Fscal) ⊆ ρ (π ◦ F). For this, take x, y /∈ ρ (π ◦ F). There exists f ∈ F such that for any σ ∈ Sn, σ · f(x) 6= f(y). We have to find l ∈ Fscal such that l(x) 6= l(y). In other words, from a function in Fn which discriminates between x and y we have to build a function in R.
First, we exhibit a function which discriminates between x and y. Apply Lem. 31 to the vectors f(x) and f(y): there exists h0 ∈ C(F,R) such that ∑n i=1 h0(f(xi)) 6= ∑n i=1 h0(f(yi)).
To fit the assumptions, we build h ∈ C(F,F) from h0 by h : x ∈ F 7→ (h0(x), . . . , h0(x)) ∈ F. Take g ∈ C(F,F) such that g(z) = (z1, . . . , z1) for any z ∈ F and l ∈ C(X,R) defined by, for w ∈ X , l(w) = ∑n i=1 h0(f(wi)). Then, l(x) 6= l(y). All we have to do is show that l ∈ Fscal, i.e., l1 ∈ F . This is where the two assumptions we made come into play. Indeed, the first one implies that h ◦ f ∈ F and the second gives
z 7→ ( n∑ i=1 h(f(zi)), . . . , n∑ i=1 h(f(zi)) ) ∈ F .
Finally, the first assumption ensure that,
z 7→ ( g ( n∑ i=1 h(f(zi)) ) , . . . , g ( n∑ i=1 h(f(zi)) )) ∈ F .
But this last function is none other than l1, which shows that l ∈ Fscal as required. We have successfully verified the hypothesis of Thm. 22. Therefore, the closure of F is,
F = {f ∈ CE(X,Fn) : ρ (F) ⊆ ρ (f) , ∀x ∈ X, f(x) ∈ F(x)} , with F(x) = {y ∈ Fn : ∀(i, i′, j, j′) ∈ I(x), yi,i′ = yj,j′} , and
I(x) = {(i, i′, j, j′) ∈ ({1, . . . , n} × {1, . . . , p})2 : ∀y ∈ F(x), yi,i′ = yj,j′} .
To get the desired result, we need to get rid of the condition “f(x) ∈ F(x)” in the description of F . Fix x ∈ X . First, we show that F(x) = {y ∈ Fn : ∀(i, j) ∈ J(x), yi = yj} , with J(x) = {(i, j) ∈ {1, . . . , n}2 : yi = yj} , (note that the equalities here are not in R anymore but in F). The direct inclusion “⊆” is immediate by construction of J(x) so we focus on the reverse direction. For this, we show that the 4-tuples (i, i′, j, j′) of I(x) necessarily satisfy i′ = j′ and (i, j) ∈ J(x).
First note that, by the first assumption, the vector y0 ∈ Fn such that y0i = (1, 2, . . . , p) for i ∈ {1, . . . , n} is in F(x). Indeed, take the constant function always equal to (1, 2, . . . , p) as h. Now, consider a 4-tuple (i, i′, j, j′) of I(x) and we show that, actually, (i, j) ∈ J(x) and i′ = j′. As y0 in F(x), and y0i,i′ = i′, y0j,j′ = j′, (i, i′, j, j′) ∈ I(x) implies that j′ = i′. Consider, k ∈ {1, . . . , p}. We show that, for any y ∈ F(x), yi,k = yj,k. But such a y can be written as y = f(x) for some f ∈ F . Consider, the function h ∈ C(F,F) associated to the permutation (i′ k), defined by,
z 7→ (z(i′ k)(1), . . . , z(i′ k)(n)) = (z1, . . . , zi′−1, zk, zi′+1, . . . , zk−1, zi′ , zk+1, . . . , zp) . By our first assumption, z 7→ (h(f(z)1), . . . , h(f(z)n)) ∈ F so that (h(y1), . . . , h(yn)) ∈ F(x). In particular, as (i, i′, j, i′) ∈ I(x), h(yi)i′ = h(yj)i′ , i.e. yi,k = yj,k. Therefore, (i, j) ∈ J(x). Finally, we can conclude that F(x) ⊃ {y ∈ Fn : ∀(i, j) ∈ J(x), yi = yj}. Indeed, take y ∈ Fn : ∀(i, j) ∈ J(x), yi = yj . We show that all the constraints of I(x) are satisfied. Indeed, take (i, i′, j, j′) ∈ I(x). We have shown that (i, j) ∈ J(x) and i′ = j′ so that yi = yj and in particular yi,i′ = yj,j′ . Therefore, this finishes the proof of F(x) ⊃ {y ∈ Fn : ∀(i, j) ∈ J(x), yi = yj}. Thus, F(x) = {y ∈ Fn : ∀(i, j) ∈ J(x), yi = yj} , with
J(x) = {(i, j) ∈ {1, . . . , n}2 : yi = yj} .
We have proven so far, that,
F = {f ∈ CE(X,Fn) : ρ (F) ⊆ ρ (f) , ∀x ∈ X, f(x) ∈ F(x)} ⊆ {f ∈ CE(X,Fn) : ρ (F) ⊆ ρ (f)} .
Take h ∈ CE(X,Fn) such that ρ (F) ⊆ ρ (h) and fix x ∈ X . Our goal is to show that, for any (i, j) ∈ J(x), h(x)i = h(x)j so that h(x) ∈ F(x). But, if (i, j) ∈ J(x), then for any f ∈ F , f(x)i = f(x)j so that (i j) · f(x) = f(x), where (i j) denotes the permutation which exchanges i and j. Moreover, as (i j) ∈ Sn, by equivariance, this means that f((i j) · x) = f(x) for every f ∈ F and therefore that ((i j) · x, x) ∈ ρ (F). By assumption, we infer that ((i j) · x, x) ∈ ρ (h) too, i.e. that h((i j) · x) = h(x) and so that h(x)i = h(x)j by equivariance, which concludes our proof.

heading: D.9 REDUCTIONS FOR GNNS
text: 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 ≥ 1 and F a finite-dimensional feature space. Let F0 ⊆ ⋃∞ h=1 C(X,Rh) be stable by concatenation and consider,
F = {x 7→ (m(f(x)1), . . . ,m(f(x)n)) : f ∈ F0∩C(X,Rh), m : Rh → F MLP, h ≥ 1} ⊆ C(X,F) . Then, if E(F) ⊆ C(X,F) is the set of functions obtained by replacing the MLP m in the definition of F by an arbitrary continuous function, E(F) satisfies,
1. F = E(F)
2. ρ (F) = ρ (E(F))
3. For any h ∈ C(F2,F), f, g ∈ E(F), x 7→ (h(f(x)1, g(x)1), . . . , h(f(x)n, g(x)n)) ∈ E(F) .
4. If, for any f ∈ F ,
x 7→ ( n∑ i=1 f(x)i, n∑ i=1 f(x)i . . . , n∑ i=1 f(x)i ) ∈ F ,
then, for any f ∈ E(F),
x 7→ ( n∑ i=1 f(x)i, n∑ i=1 f(x)i . . . , n∑ i=1 f(x)i ) ∈ E(F) .
5. If F is equivariant w.r.t. the action described in Cor. 30, so is E(F).
Proof. Define,
E(F) = {x 7→ (m(f(x)1), . . . ,m(f(x)n)) : f ∈ F0 ∩ C(X,Rh), m ∈ C(Rh,F), h ≥ 1} .
As MLP are continuous and by the universality of MLP on a compact set (see Section C.1),
F ⊆ E(F) ⊆ F . This already implies 1. and that ρ ( F ) ⊆ ρ (E(F)) ⊆ ρ (F). Using Lem. 15 yields 2.
We now show 3. Take h ∈ C(F2,F), f, g ∈ F0, f ∈ C(X,Rhf ), g ∈ C(X,Rhg ) and m ∈ C(Rhf ,F), l ∈ C(Rhg ,F). All we have to show is that,
x 7→ (h(m(f(x)1), l(g(x)1)), . . . , h(m(f(x)n), l(g(x)n))) ∈ E(F) .
But as F0 is stable by concatenation, x 7→ (f(x), g(x)) ∈ Rhf+hg is still in F0. Moreover, y ∈ Rhf+hg 7→ h(m(y1, . . . , yhf ), l(yhf+1, . . . , yhf+hg ) is also in C(Rhf+hg ,F) which shows that the map above is indeed in E(F). The last two points are immediate consequences of the definition of E(F).
Thm. 5 and Thm. 6 are now obtained by combining Lem. 32 with Cor. 29 and Cor. 30.

heading: E PROOFS FOR EXPRESSIVENESS OF GNNS
text: 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 = {f ∈ CE(X,Fn) : ρ (F0) ⊆ ρ (f)} ,
then one can show, that, if f ∈ F , then
f̃ : x 7→ ( n∑ i=1 f(x)i, n∑ i=1 f(x)i . . . , n∑ i=1 f(x)i ) ∈ F .
Indeed, f ∈ F so that it has a weaker discriminating power than F , so that ρ (F) = ρ (F0) ⊆ ρ (f). But, by construction of f̃ , ρ (f) ⊆ ρ ( f̃ ) so that ρ (F0) ⊆ ρ ( f̃ ) . As f̃ is also in CE(X,Fn), f̃ ∈ F .

heading: E.1 EXPRESSIVITY OF GNN LAYERS
text: Lemma 33. Fix F0,F1 (non-trivial) finite dimensionnal vector spaces. Consider the action of G = Sn on F0 × Fn×k0 defined by,
∀σ ∈ Sn, ∀x0 ∈ F0, ∀x ∈ Fn×k, σ · (x0, x) = (x0, xσ−1(1), . . . , xσ−1(n))
Let K ⊆ F0 × Fn×k0 be a compact set. Then, the set of functions from K ⊆ F0 × F n×k 0 to F1 of the form,
(x0, x) 7−→ f0 x0, n∑ j=1 k∏ w=1 fw(xj,w)  where f0 : F0 × Rh → F1, fj : F0 → Rh, j = 1, . . . , k are multi-linear perceptrons and h ≥ 1, is dense in CI(K,F1).
Proof. Denote by F ⊆ CI(K,F1) the set of such functions. To prove that F = CI(K,F1), we first apply Thm. 5.
We get, that, F = { f ∈ CI(F0 × Fn×k0 ,F1) : ρ (F) ⊆ ρ (f) } .
We now characterize ρ (F). Actually, it is equal to ρ (inv) = {((x0, x), (y0, y)) ∈ ( F0 × Fn×k0 )2 : ∃σ ∈ Sn, (x0, x) = σ · (y0, y)}. As the functions of F are invariant, ρ (inv) ⊆ ρ (F). We now show the reverse. Take (x0, x), (y0, y) ∈ F0 × Fn×k0 such that there does not exist σ ∈ Sn such that (x0, x) = σ · (y0, y). If x0 6= y0, there exists f0 : F0 → F1 MLP such that f(x0) 6= f(y0) so that ((x0, x), (y0, y)) /∈ ρ (F). Otherwise, there does not exists σ ∈ Sn such that (xσ−1(1), . . . , xσ−1(n)) = (y1, . . . , yn) by definition of the action of G = Sn. Now, apply Lem. 31 with F ← Fk0 , the universality of MLP and use the decomposition given to get fj : F0 → Rh, j = 1, . . . , k such that∑n j=1 ∏k w=1 fw(xj,w) 6= ∑n j=1 ∏k w=1 fw(yj,w). Choosing an appropriate MLP f0 : Rh → F1 yields that ((x0, x), (y0, y)) /∈ ρ (F). Hence, we have shown that,
F = { f ∈ CI(F0 × Fn×k0 ,F1) : ρ (inv) ⊆ ρ (f) } = CI(F0 × Fn×k0 ,F1) .

heading: E.2 APPROXIMATION THEOREMS FOR GNNS
text: We now have all the tools to finally prove our main result.
Theorem 34. Let Kdiscr ⊆ Gn × Fn0 , K ⊆ Fn 2 0 be compact sets. For the invariant case, we have:
MGNNI = {f ∈ CI(Kdiscr,F) : ρ (2-WLI) ⊆ ρ (f)} 2-LGNNI = {f ∈ CI(K,F) : ρ (2-WLI) ⊆ ρ (f)} k-LGNNI = {f ∈ CI(K,F) : ρ (k-LGNNI) ⊆ ρ (f)} ⊃ {f ∈ CI(K,F) : ρ (k-WLI) ⊆ ρ (f)} k-FGNNI = {f ∈ CI(K,F) : ρ (k-FWLI) ⊆ ρ (f)}
For the equivariant case, we have:
MGNNE = {f ∈ CE(Kdiscr,Fn) : ρ (2-WLE) ⊆ ρ (f)} k-LGNNE = {f ∈ CE(K,Fn) : ρ (k-LGNNE) ⊆ ρ (f)} ⊃ {f ∈ CE(K,Fn) : ρ (k-WLE) ⊆ ρ (f)} k-FGNNE = {f ∈ CE(K,Fn) : ρ (k-FWLE) ⊆ ρ (f)}
We decompose the proof with an additional lemma.
Lemma 35. Let Kdiscr ⊆ Gn × Fn0 , K ⊆ Fn 2
0 be compact sets. For the invariant case, and any k ≥ 2, we have,
MGNNI = {f ∈ CI(Kdiscr,F) : ρ (MGNNI) ⊆ ρ (f)} k-LGNNI = {f ∈ CI(K,F) : ρ (k-LGNNI) ⊆ ρ (f)} k-FGNNI = {f ∈ CI(K,F) : ρ (k-FGNNI) ⊆ ρ (f)}
For the equivariant case, and any k ≥ 2, we have:
MGNNE = {f ∈ CE(Kdiscr,F) : ρ (MGNNE) ⊆ ρ (f)} k-LGNNE = {f ∈ CE(K,F) : ρ (k-LGNNE) ⊆ ρ (f)} k-FGNNE = {f ∈ CE(K,F) : ρ (k-FGNNE) ⊆ ρ (f)}
Proof of Thm. 34. The theorem is now a 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 MGNNI , k-LGNNI or k-FGNNI and X be either Kdiscr or K so that X is compact and F ⊆ CI(X,F). Applying Thm. 5 directly gives,
F = {f ∈ CI(X,F) : ρ (F) ⊆ ρ (f)} ,
which is the desired result.
We now move to the equivariant case. First, let us replace MGNNE by another class, which is slightly simpler to analyze. Define,
MGNNE′ = {mE ◦ ((1− λ) Id +λS1) ◦ FT ◦ . . . F2 ◦ F1 : Ft : Fnt → Fnt+1 message passing layer, t = 1, . . . , T, T ≥ 1, λ ∈ {0, 1}} .
It holds that ρ (MGNNE′) = ρ (MGNNE) and,
MGNNE′ ⊆ MGNNE ⊆ {f ∈ CE(Kdiscr,Fn) : ρ (MGNNE) ⊆ ρ (f)} = {f ∈ CE(Kdiscr,Fn) : ρ (MGNNE′) ⊆ ρ (f)}
Therefore, if we show that,
MGNNE′ = {f ∈ CE(Kdiscr,Fn) : ρ (MGNNE′) ⊆ ρ (f)} ,
we will have the desired result.
Let F denote MGNNE′ , k-LGNNE or k-FGNNE and X be either Kdiscr or K so that X is compact and F ⊆ CE(X,Fn). We now wish to apply Thm. 6, but we need to verify the stability assumption first. Thus, we show that, for any f ∈ F ,
x 7→ ( n∑ i=1 f(x)i, n∑ i=1 f(x)i . . . , n∑ i=1 f(x)i ) ∈ F ,
• If F = MGNNE′ .Take f ∈ MGNNE′ . f is of the form,
mE ◦ ((1− λ) Id +λS1) ◦ FT ◦ . . . F2 ◦ F1 ,
where Ft : Fnt → Fnt+1 are message passing layers, FT+1 = F and λ ∈ {0, 1}. We need to show that there is a MGNNE′ which implements,
x 7→ ( n∑ i=1 f(x)i, n∑ i=1 f(x)i . . . , n∑ i=1 f(x)i ) . (26)
If λ = 1, f is exactly the function of (26). Otherwise, if λ = 0, we build another MGNNE′ implementing this function. Denote by FT+1 : Fn → Fn the (simple) message passing layer defined by FT+1(h)i = mE(hi) for i ∈ [n] and any h ∈ Fn. Then, the MGNNE′ (1− λ′) Id +λ′S1) ◦ FT+1 ◦ FT ◦ . . . F2 ◦ F1 with λ′ = 1 exactly implements (26).
• If F = k-LGNNE . A function f of this class is of the form,
mE ◦ Sk1 ◦ FT ◦ . . . F2 ◦ F1 ◦ Ik,
where Ft : Fn k t → Fn k
t+1 are linear graph layers and FT+1 = F. Our goal is to show that there is a GNN of k-LGNNE which implements,
x 7→ ( n∑ i=1 f(x)i, n∑ i=1 f(x)i . . . , n∑ i=1 f(x)i ) , (27)
By definition of linear graph layers, the map FT+1 : Fn k → Fnk defined by, for G ∈ Fnk ,
∀(i1, . . . , ik) ∈ [n]k, FT+1(G)i1,...,ik = mE(Sk1 (G)i) ,
is a linear graph layer as defined in Section 3. Now, consider, the linear graph layer, FT+2 : Fn k → Fnk defined by, for G ∈ Fnk ,
∀(i1, . . . , ik) ∈ [n]k, FT+1(G)i1,...,ik = n∑ i=1 Gi,i2,...,ik .
Then, the k-LGNN FT+2 ◦ FT+1 ◦ FT ◦ . . . F2 ◦ F1 ◦ Ik exactly implements (27).
• If F = k-FGNNE . A function f of this class is of the form,
mE ◦ Sk1 ◦ FT ◦ . . . F2 ◦ F1 ◦ Ik,
where Ft : Fn k t → Fn k
t+1 are FGL (see Section 3) and FT+1 = F. We build a GNN of k-MGNNE which implements,
x 7→ ( n∑ i=1 f(x)i, n∑ i=1 f(x)i . . . , n∑ i=1 f(x)i ) , (28)
For w ∈ [k], define the FGL Hw : Fn k → Fnk by,
∀G ∈ Fn k , ∀(i1, . . . , ik) ∈ [n]k, Hw(G)i1,...,ik = n∑ j=1 Gi1,...,iw−1,j,iw+1,...,ik .
Then H2 ◦ · · · ◦Hk : Fn k → Fnk computes the sum of the elements of the input tensor over the last k − 1 dimensions like to Sk1 : Fn k → Fn and H1 ◦H2 ◦ · · · ◦Hk : Fn k → Fnk computes the full sum of the elements of the input tensor like to Sk : Fnk → F. Finally, consider the FGL FT+1 : Fn k → Fnk associated to mE , i.e. such that, for any G ∈ Fn k ,
∀(i1, . . . , ik) ∈ [n]k, FT+1(G)i1,...,ik = mE(Gi1,...,ik) .
Now, the k-FGNN
H1 ◦H2 ◦ · · · ◦Hk ◦ FT+1 ◦H2 ◦ · · · ◦Hk ◦ FT+1 ◦ FT ◦ . . . F2 ◦ F1 ◦ Ik
exactly implements (28).

heading: F EXTENSION TO GRAPHS OF VARYING SIZES

heading: F.1 EXTENSION TO DISCONNECTED INPUT SPACES
text: Here we show that our results can be extended to graphs of varying sizes similarly to 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 a 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 a compact input space X , assume that there is some finite set A, and Xα, α ∈ A a family of pairwise disjoints compact sets such that X = ⊔ α∈AXα. Crucially, we will assume that the Xα are in distinct connected components. Intuitively, they do not "touch" each other. Similarly, assume that the output space Y can be written as Y = ⊔ α∈A 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 we will consider do not change the number of nodes of their inputs. Formally, we say that f : X −→ Y is adapted if f(Xα) ⊆ Yα for each α ∈ A, and denote by Cad(X,Y ) the of continuous and adapted functions from X to 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 a family of pairwise disjoints compact sets such that X = ⊔ α∈AXα and the Xα’s are in distinct connected components. Also assume that there is Yα, α ∈ A a family of (pairwise disjoints) real vector spaces such that Y = ⊔ α∈A Yα. Consider F ⊆ Cad(X,Y ) a (non-empty) set of adapted functions and, for each α ∈ A, define F|Xα = {f|Xα : f ∈ F} ⊆ C(Xα, Yα) the restriction of the functions of F to Xα. Assume that the following holds,

heading: 1. Each F|Xα is a sub-algebra of C(Xα, Yα) which contains the constant function 1Yα .
text: 2. There is a set of functions Fscal ⊆ C(X,R) such that Fscal.F ⊆ F and it discriminates between the Xα’s, i.e. ρ (Fscal) ⊆ ⊔ α∈AX 2 α.

heading: Then the closure of F is,
text: F = { f ∈ Cad(X,Y ) : ∀α ∈ A, f|Xα ∈ F|Xα } ,
for the distance on Cad(X,Y ) defined by, for f, g ∈ Cad(X,Y ),
d(f, g) = max α∈A sup Xα ‖f − g‖Yα .
Proof. Define the set of functions S ⊆ C(X,R) by,
S = {f ∈ C(X,R) : f.F ⊆ F} .
By definition, Fscal ⊆ S. Moreover, as each F|Xα is a subalgebra, S is also a subalgebra of C(X,R).
As X is compact, we can apply Cor. 17 to S to get that, in C(X,R),
S = {f ∈ C(X,R) : ρ (S) ⊆ ρ (f)} .
In the first part of the proof, we check that, for each α, the function fα : X −→ [0, 1] defined by
fα|Xα = 1
∀β 6= α, fα|Xβ = 0 .
is continuous and satisfy ρ (S) ⊆ ρ (fα). This will means that such functions belong to Fscal. As the Xβ’s are in different connected components, it is enough to check its continuity on each Xβ . Indeed, each fα|Xβ is constant so continuous. The second fact comes from the second assumption. Indeed, take (x, y) ∈ X such that (x, y) ∈ ρ (S). As Fscal ⊆ S, in particular (x, y) ∈ ρ (Fscal). But, by assumption, ρ (Fscal) ⊆ ⊔ β∈AX 2 β . Thus, necessarily x and y belong to the same Xβ so that fα(x) = fα(y).
Therefore, we conclude that fα ∈ S. We now prove the announced equality. By the definition of the distance, the first inclusion, F ⊆{ f ∈ Cad(X,Y ) : f|Xα ∈ Fα } is immediate. We focus on the other way. Take h ∈ Cad(X,Y ) such that h|Xα ∈ Fα for every α ∈ A and > 0. By definition of h, there exists, for each α ∈ A, gα ∈ F such that,
sup Xα ‖h− gα‖Yα ≤ ,
As the Xα’s are compact and the gα’s are continuous, maxα∈A supXα ‖gα‖ < +∞ and denote by M > 0 a bound on this quantity. We have shown above that each fα is in S so there exists, for each α ∈ A, lα ∈ S such that,
sup X |fα − lα| ≤ M .
By definition of S and, as F is a subalgebra, ∑ α∈A lαgα ∈ F and, for each β ∈ A,
sup Xβ ∥∥∥∥∥h−∑ α∈A lαgα ∈ F ∥∥∥∥∥ ≤ supXβ ‖h− gβ‖+ ‖gβ − lβgβ‖+ ∥∥∥∥∥∥ ∑ α6=β lαgα ∥∥∥∥∥∥ ≤ +M ×
M + (|A| − 1)M × M = (|A|+ 1) ,
which concludes the proof.

heading: F.2 APPROXIMATION THEOREM WITH VARYING GRAPH SIZE
text: We now state our theorem in the case of varying graph size like Keriven & Peyré (2019). With Lem. 36, it is indeed straightforward to extend any approximation result initially proven for a class of graphs of fixed size. However, as the complete proof would require new notations again, we only give a sketch of proof.
Fix N ≥ 1 and consider the space of graphs (described by tensors) of size less than N , F≤N 2 0 =⋃N n=1 Fn 2
0 . 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 G≤N×F≤N0 = ⋃N n=1 Gn×Fn0 , with a similar topology or the graph edit distance.
Corollary 37. Let Kdiscr ⊆ G≤N × F≤N0 , K ⊆ F ≤N2 0 be compact sets. For the invariant case, we have:
MGNNI = {f ∈ CI(Kdiscr,F) : ρ (2-WLI) ⊆ ρ (f)} 2-LGNNI = {f ∈ CI(K,F) : ρ (2-WLI) ⊆ ρ (f)} k-LGNNI = {f ∈ CI(K,F) : ρ (k-LGNNI) ⊆ ρ (f)} ⊃ {f ∈ CI(K,F) : ρ (k-WLI) ⊆ ρ (f)} k-FGNNI = {f ∈ CI(K,F) : ρ (k-FWLI) ⊆ ρ (f)}
For the equivariant case, we have: MGNNE = { f ∈ CE(Kdiscr,F≤N ) : ρ (2-WLE) ⊆ ρ (f) } k-LGNNE = { f ∈ CE(K,F≤N ) : ρ (k-LGNNE) ⊆ ρ (f) } ⊃ { f ∈ CE(K,F≤N ) : ρ (k-WLE) ⊆ ρ (f)
} k-FGNNE = { f ∈ CE(K,F≤N ) : ρ (k-FWLE) ⊆ ρ (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.

Review summaries:
The 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.