Expressiveness and Approximation Properties of Graph Neural Networks
Authors: Floris Geerts
Juan L Reutter
Venue: ICLR 2022 Oral (2022)
Keywords: Graph Neural Networks
Colour Refinement
Weisfeiler-Leman
Separation Power
Universality

Abstract: Characterizing the separation power of graph neural networks (GNNs) provides an understanding of their limitations for graph learning tasks. Results regarding separation power are, however, usually geared at specific GNNs architectures, and tools for understanding arbitrary GNN architectures are generally lacking. We provide an elegant way to easily obtain bounds on the separation power of GNNs in terms of the Weisfeiler-Leman (WL) tests, which have become the yardstick to measure the separation power of GNNs. The crux is to view GNNs as expressions in a procedural tensor language describing the computations in the layers of the GNNs. Then, by a simple analysis of the obtained expressions, in terms of the number of indexes used and the nesting depth of summations, bounds on the separation power in terms of the WL-tests readily follow. We use tensor language to define Higher-Order Message-Passing Neural Networks (or k-MPNNs), a natural extension of MPNNs. Furthermore, the tensor language point of view allows for the derivation of universality results for classes of GNNs in a natural way. Our approach provides a toolbox with which GNN architecture designers can analyze the separation power of their GNNs, without needing to know the intricacies of the WL-tests. We also provide insights in what is needed to boost the separation power of GNNs.

Published as a conference paper at ICLR 2022
EXPRESSIVENESS AND APPROXIMATION PROPERTIES OF GRAPH NEURAL NETWORKS
Floris Geerts
Department of Computer Science, University of Antwerp, Belgium floris. geerts be
Juan L. Reutter
School of Engineering, Pontificia Universidad Católica de Chile, Chile & IMFD, Chile jreuttere ing. puc......................
ABSTRACT
Characterizing the separation power of graph neural networks (GNNs) provides an understanding of their limitations for graph learning tasks. Results regarding separation power are, however, usually geared at specific GNN architectures, and tools for understanding arbitrary GNN architectures are generally lacking. We provide an elegant way to easily obtain bounds on the separation power of GNNs in terms of the Weisfeiler-Leman (WL) tests, which have become the yardstick to measure the separation power of GNNs. The crux view GNNs as expressions in procedural tensor language describing the computations in the layers of the GNNs. Then, by simple analysis of the obtained expressions, terms of the number of indexes and the nesting depth of summations, bounds on the separa- tion power terms of the WL-tests readily follow. We use tensor language define Higher-Order Message-Passing Neural Networks (or k-MPNNs), natural extension of MPNNs. Furthermore, the tensor language point view allows for the derivation of universality results for classes of GNNs in natural way. Our approach provides a toolbox with which GNN architecture designers can analyze the separation power of their GNNs, without needing know the intricacies of the WL-tests. We also provide insights in what is needed to boost the separation power of GNNs.
INTRODUCTION
Graph Neural Networks (GNNs) (Merkwirth & Lengauer, 2005; Scarselli et al., 2009) cover many popular deep learning methods for graph learning tasks (see Hamilton (2020) for a recent overview). These methods typically compute vector embeddings of vertices graphs by relying the underly- ing adjacency information. Invariance (for graph embeddings) and equivariance (for vertex embed- dings) of GNNs ensure that these methods oblivious to the precise representation of the graphs.
Separation power. Our primary focus is the separation power of GNN architectures, i.c., their ability to separate vertices or graphs by means of the computed embeddings. It has become standard to characterize GNN architectures in terms of the separation power of graph algorithms such as color refinement (CR) and k-dimensional Weisfeiler-Leman tests (k-WL), as initiated in Xu al. (2019) and Morris al. (2019). Unfortunately, understanding the separation power of any given GNN architecture requires complex proofs, geared at the specifics of the architecture. We provide a tensor language-bane based technique to analyze the separation power of general GNNs.
Tensor languages. Matrix query languages (Brijder et al., 2019; Geerts et al., 2021b) are defined to assess the expressive power of linear algebra. Balcilar et al. (2021a) observe that, by casting various GNNs into the MATLANG (Brijder et al., 2019) matrix query language, one separation results (Geerts, 2021) to obtain upper bounds on the separation power of GNNs in terms of 1-WL and 2-WL. In this paper, we considerably extend this approach by defining, and studying, new general- purpose tensor language specifically designed for modeling GNNs. As in Balcilar et al. (2021a) a)), focus on tensor languages allows obtain insights about GNN architectures.
existing

---

Published as a conference paper at ICLR 2022
First, since tensor languages can only define invariant and equivariant graph functions, any GNN that can be cast in our tensor language inherits these desired properties. More importantly the separation power of our tensor language is as closely related to CR and k-WL as GNNs are. Loosely speaking, if tensor language expressions use k- 1 indices, then their separation power is bounded by k-WL. Furthermore, if the maximum nesting of summations in the expression is t, then t rounds of k-WL are needed to obtain an upper bound on the separation power. A similar connection is obtained for CR and a fragment of tensor language that we call "guarded" tensor language.
We thus reduce problem of assessing the separation power of any specific GNN architecture to the problem of specifying it in our tensor language, analyzing the number of indices used and counting their summation depth. This is usually much easier than dealing with intricacies of CR and k-WL, as casting GNNs in our tensor language is often as simple as writing down their layer-based definition. We believe that this provides a nice toolbox for GNN designers to assess the separation power of their architecture. We use this toolbox to recover known results about the separation power of specific GNN architectures such as GINs (Xu et al., 2019). GCNs (Kipf & Welling, 2017), Folklore GNNs (Maron et al., 201 2019b), k-GNNs (Morris et al., 2019), and several others. We also derive new results: we answer open problem posed by Maron et al. (2019a) by showing that the separation power of Invariant Graph Networks (k-IGNs). introduced by Maron et al. (2019b), is bounded by (k 1--WL. In addition, we revisit the analysis by Balcilar et al. (2021b) of ChebNet (Defferrard et al., 2016), and show that CayleyNet (Levie et al., 2019) is bounded by 2-WL.
When writing down GNNs in our tensor language, the less indices needed, the stronger the bounds in terms of k-WL we obtain. After all, (k 1)-WL is known to be strictly less separating than k-WL (Otto, 2017). Thus, is important minimize the number of indices used in tensor language expressions. We connect this number to the notion of treewidth: expressions of treewidth k can be translated into expressions using k 1 indices. This corresponds to optimizing expressions, as done in many areas in machine learning, by reordering the summations (a.k.a. variable elimination).
Approximation and universality. We also consider the ability of GNNs to approximate general invariant or equivariant graph functions. Once more, instead of focusing on specific architectures, we use our tensor languages to obtain general approximation results, which naturally translate to universality results for GNNs. We show: (k + 1)-index tensor language expressions suffice to ap- proximate any (Invarian/equivaaiian) graph function whose separating power is bounded by k-WL, and we can further refine this by comparing the number of rounds in k-WL with the summation depth of the expressions. These results provide a finer picture than the one obtained by Azizian & Lelarge (2021). Furthermore, focusing on "guarded"" tensor expressions yields similar universality result for CR, a result that, to our knowledge, was not known before. We also provide the link between approximation results for tensor expressions and GNNs, enabling universality properties of GNNs As an example, we show that k-IGNs can approximate any graph function that is less separating than (k-1)-WLL This case was left open in Azizian & Lelarge (2021). I).
transfer our insights into
In summary, we draw new and interesting connections between tensor languages, GNN architectures and classic graph algorithms. We provide general recipe bound the separation power of GNNs, optimize them, and understand their approximation power. We show the usefulness of our method by recovering several recent results, as well as new results, some of them left open in previous work.
Related work. Separation power has been studied for specific classes of GNNs (Morris et al., 2019; Xu et al., 2019; Maron et al., 2019b; Chen et al., 2019; Morris et al., 2020; Azizian & Lelarge, 2021). A first general result concerns the bounds in terms of CR and 1-WL of Message-Passing Neural Networks (Gilmer et al., 2017: Morris et al., 2019; Xu al., 2019). Balcilar et al. (2021a) use the MATLANG matrix query language to obtain upper bounds on the separation power of various GNNs. MATLANG can only be used to obtain bounds up to 2-WL and is limited to matrices. Our tensor language is more general and flexible and allows for reasoning over the number of indices, treewidth, and summation depth of expressions. These are all crucial for our main results. The tensor language introduced resembles Sum-MATLANG (Geerts et al., 2021b), but with the added ability to represent tensors. Neither separation power nor guarded fragments were considered in Geerts et al. (2021b). See Section A in the supplementary material for more details. For universality, Azizian & Lelarge (2021) is closest in spirit. Our approach provides an elegant way to recover and extend their results. Azizian & Lelarge (2021) describe how their work (and hence also ours) encompasses previous works (Keriven& & Peyré, 2019; Maron et al., 2019c; Chen et al., 2019). Our results use connections between k-WL and logics (Immerman & Lander, 1990; Cai et al., 1992), and CR and
2

---

Published as a conference paper at ICLR 2022
guarded logies (Barceló et al., 2020). The optimization of algebraic computations and the use of treewidth relates to the approaches by Aji & McEliece (2000) and Abo Khamis et al. (2016).
2 BACKGROUND
We denote sets by O and multisets by {0). For E N, 0, [x] == .2). Vectors are denoted by v, w..... matrices by A, B B.... and tensors by S.T..... Furthermore, v, is the i-th entry of vector v, Ac is the (i, entry of matrix A and S; denotes the i = (i,,.... i&) is entry of a tensor S. If certain dimensions are unspecified, then this is denoted by a ":"" For example, A, and A.j denote the i-th row and j-th column of matrix A, respectively. Similarly for slices of tensors.
We consider undirected simple graphs G = (Va, Eg, colc) equipped with a vertex- labellln colg : Ve - RR. We assume that graphs have size n, Va consists of vertices and we often identify VG with [n]. For a vertex v E Va. (v(v) == {u E Va ou E Ea). We let G be the set of all graphs of size n and let 9s be the set of pairs (G, 1) with G E 9 and E Vg. Note that
Go-
The color refinement algorithm (CR) (Morgan, 1965) iteratively computes vertex labellings based on neighboring vertices, as follows. For a graph G and vertex E VG, cr"h v) = cola(v). Then, for 2 O, cr(++ v) := (G, v). (G, u Na(v)))) We collect all vertex labels to obtain a label for the entire graph by defining gcrl := [fer" (G, | | V&]). The algorithm (k-WL) (Cai et al., 1992) iteratively computes labellings of k-tuples of vertices. For a k-tuple v, its atomic type in G, denoted by atp, v), a vector in R (1)+ The first (*) entries are 0/1- v-lvulues encoding the equality type of v. i... whether v oy for 1 S < j S. k. The second (5) entries are 0/1- 0/1-values encoding adjacency information, i.e. whether uu4y E Eg for 1 Si Si<js J.J.h. kt The last &e real-valued entries correspond to cola(u; E R for 1 < i < k. Initially, for a graph G and v E Vg. k-WL assigns the label wi| (G, == (G. For t 0, k-WL revises the label according to wil WI v) == (wl v), (G, M) with M ((tpp (G, vu), w/l (G, vft,e///), ..... wIf (G, olu/k)) u VV)). where vfu/d] (11, (U1...., U- 2111, , Uk). We use k-WL to assign labels to vertices and graphs by defining: wwl. (G, := (G, (u,..., u)), for vertex- labellinn,, and gwi == H( (G, u v(l),, for graph- suph-labelllinss. We use cr ger vwlf and gwif to denote the stable labellings pro- duced by the corresponding algorithm over arbitrary number of rounds. Our version of 1-WL differs from CR in that 1-WL also uses information from non-adjacent vertices; this distinction only matters for vertex embeddings (Grohe, 2021). We the "folklore" k-WL of Cai al. (1992), except Cai et al. use 1-WL to refer to CR. While equivalent to "oblivious" (k + 1)-WL (Grohe, 2021), used in some other works on GNNs, care is needed when comparing our work.
k- k-dimensional Weisfeiler-
Let G be a graph with Va [n] and let be a permutation of [n]] We denote by a * G the isomorphic copy of G obtained by applying the permutation σ. Similarly, for v V o is the permuted version of v. Let F be some feature space. A function f Go + F is called invariant if /(G) = f(a * G') for any permutation æ. More generally, f 9, - F is equivariant fa * G, a x = f(G, v) for any permutation a. The functions cr :n - F and wwl. : 9n + are equivariant, whereas ger" Go + F and gwit Go - F are invariant, for any 2 0 and k 2 1.
3 SPECIFYING GNNS
Many GNNs use linear algebra computations on vectors. matrices or tensors, interleaved with the application of activation functions or MLPs. To understand the separation power of GNNs, we introduce specification language, TL, for tensor language, that allows us to specify any algebraic computation in procedural way by explicitly stating how each entry is to be computed. We gauge the separation power of GNNs by specifying them as TL expressions, and syntactically analyzing the components of such TL expressions. This technique gives rise to Higher- Order Paassage-Passingg Neural Networks (or k-MPNNs), a natural extension of MPNNs (Gilmer et al., 2017). For simplicity, we present TL using summation aggregation only but arbitrary aggregation functions on multisets of real values can be used well (Section C.5 in the supplementary material).
3

---

Published as a conference paper at ICLR 2022
To introduce TL, consider typical layer in GNN of the form F¹ = =o.FF..W) where A R is an adjacency matrix, F E IF** are vertex features such that F.: E IR' is the feature vector of vertex i, a is non-linear activation function, and W E R is weight matrix. By exposing the indices in the matrices and vectors we can equivalently write: for i E [n] and 8 E [f]:
Fi2- = (Csetni Auj (Ere(g) Wts -F+))
In TL, we do not work with specific matrices or indices ranging over [n]] but focus instead on expressions applicable to any matrix. We use index variables 2 and 22 instead of i and j. replace Ay with placeholder E x2) and Fjt with placeholders (((2)) for E [4]. We then represent the above computation in TL by l expressions (a(x1), one for each feature column, as follows:
(=())) = (I,, E(81, (ErE(a)
Wi (iss)((
These are pure syntactical expressions. To give them semantics, we assign to E matrix A E Rnxx, to P. column vectors F, E [R=x1 for E [4], and to I an index i E [n]. By letting the variable 22 under the summation range over 1, , n, the TL expression 4/s evaluates to Fig- As such, F" """=oA aAAAA F W) can be represented as a specific instance of the above TL expressions. Throughout the paper we reason about expressions in TL rather than specific instances thereof. Importantly, by showing that certain properties hold for expressions in TL, these properties are inherited by all of its instances. We use TL to enable a theoretical analysis of the separating power of GNNs; It is not intended practical programming language for GNNs.
Syntax. We first give the syntax of TL expressions. We have a binary predicate E, to represent adjacency matrices, and unary vertex predicates P.. s E [t]. to represent column vectors encoding the É-dimensional vertex labels. In addition, we have (possibly infinite) set Ω of functions. such as activation functions or MLPs. Then, TL((2) expressions are defined by the following grammar:
P = 1po E(x,y) v) Pa(x) I 9 y 1p +p | a. [(p.....
.p) 4
where op E (=. x, y are index variables that specify entries in tensors, s E [e]. a E R. and E Ω. Summation aggregation is captured by Σg sp. We sometimes make explicit which functions are used expressions in TL( by writing [L, for f2, in Ω. For example, the expressions (x1) described earlier are in TL(o).
The set of free index variables of an expression s., denoted by free(s)), determines the order of the tensor represented by s. It is defined inductively: free(1. free( P. (x)) (x). free( ( = free(() 922) [ free (f Pp)) == Use(p fre((p)) and free(E, P1) == free((p1) \ {z}. We sometimes explic-
free (E(r, = (r,y).
free(a- == free((p1)
itly write the free indices. In our example expressions vhs (21), 21 is the free index variable.
An important class of expressions are those that only use index variables {x1,..., We denote by (12) the k-index variable fragment of ([2). The expressions (1ri are in TL2(g).
Semantics. We next define the semantics of expressions in TL()2). Let G = (Vo, EG, colG) be a vertex-labelled graph. We start by defining the interpretation [[. #la of the predicates E, P. and the (dis)equality predicates, relative to G and a valuation v assigning a vertex to each index variable:
[E(x, v), v|c == if (()))()) E EG then 1 else 0 [Pa()), = cola(v(z)) E [Lropur u|a =- if (( (yy then 1 else 0.
In other words, E is interpreted the adjacency matrix of G and the P.'s interpret the vertex- labelling colg. Furthermore, we lift interpretations to arbitrary expressions in TL(?), as follows:
[1 P2, (2, v/a = [1,, vla I12, vlc 181, IΣ vilv = Le.
[ v/a = 14,, + p/2. [a 91, vl == a 1lc
ollo
(p)) = [[P1,,la..... I., ula)
where, v/x + u) the valuation but which now maps the index x to the vertex v E VG. For simplicity, we identify valuations with their images. For example, [p(x), vle denotes [ş]xr), u|.. To illustrate the semantics, for each v E Vg. our example expressions satisfy [t>,, u|a = Fy, for F = (AA F. W) when A is the adjacency matrix of G and F represents the vertex labels.
We can replace E. t0 by more general aggregation construct aggr," (4p) for arbitrary functions F that assign a real value multisets of real values. We refer the supplementary material (Section C.5) for details.
4

---

Published as a conference paper at ICLR 2022
K-MPNNs. Consider function f G. R v) H f(G.v) E R' for some E N. We say that the function f can be represented in TL(2) if there exists expressions (p (2))....., (p((. ................................ 23) in TL(S2) such that for each graph G and each s-tuple Va.
f(G, (I12, vla. ................................ [pe, vla).
Of particular interest are kth-order MPNNs (or k-MPNNs) which refers to the class of functions that can be represented in 1 We can regard GNNs as functions Gr - R. Hence, GNN is a k-MPNN if its corresponding functions are k-MPNNs. For example, we can interpret F' (A. F W) ) as function
91 - IR such that f(G, == F' We have seen that for each 8 E [e] [t,,, dI F' with V. E (o). Hence, f(G. v) (IV11, vl,,..,,,,, [,,,, ul), and thus belongs to I-MPNNs and our example GNN a 1-MPNN.
TL represents equivariant invariant functions. We make simple observation which follows from the type of operators allowed in expressions in TL(2). Proposition 3.1. Any function f G. - IR represented TL(S2) is equivariant (invariant s 0). An immediate consequence is that when GNN a k-MPNN, it is automatically invariant or equiv- ariant, depending on whether graph vertex tuple embeddings are considered.
SEPARATION POWER OF TENSOR LANGUAGES
Our first main results concern the characterization of the separation power of tensor languages in terms of the color refinement and k-dimensional Weisfeiler- grained characterization by taking the number of rounds of these algorithms into account. This will allow for measuring the separation power of classes of GNNs in terms of their number of layers.
algorithms. We provide a fine-
4.1 SEPARATION POWER
We define the separation power of graph functions in terms of an equivalence relation, based on the definition from Azizian & Lelarge (2021), hereby first focusing on their ability to separate vertices."
Definition 1. Let F be a set of functions f 91 + Rd, The equivalence relation pr (F) is defined by F on G1 as follows:
w)) E pi (F) = F, v) = =S(H, w).
In other words, when (IG, v), (H, w)) E (T no function F can separate v G from w in H. For example, we can view tr and wwl. as functions from G1 to some Re. As such pi (cr and p1 (vwll)) measure the separation power of these algorithms. The following strict inclusions are known: for all k 2 1, Pı (vwl 1) C P1 (vwll)) and #1 (vwl(") C p1 (cr")) (Otto, 2017; Grohe, 2021). is also known that more rounds (f) increase the separation power of these algorithms (Fürer, 2001).
For a fragment L of LS2)) expressions, we define Pi (C) as the equivalence relation associated with By definition, we here thus consider
all functions f G1 + RC, that can be represented expressions in TL(22) with one free index variable resulting in vertex embeddings.
4.2 MAIN RESULTS
We first provide link between k-WL and tensor language expressions using + index variables: Theorem 4.1. For each k > 1 and any collection of functions, Pi (vwl - (TLx+1
This theorem gives us new insights: if we wish to understand how new GNN architecture compares against the k-WL algorithms, all we need do is to show that such an architecture can be represented in TL (1)). i.e., is MMNNN, an arguably much easier endeavor. As example of how to use this result, is well known that triangles can be detected by 2-WL but not by 1-WL. Thus, in order to design GNNs that can detect triangles, layer definitions in TL3 rather than TL2 should be used.
We can do much more, relating the rounds k-WL to the notion of summation depth of TL((2) expressions. We also present present similar results for functions computing graph embeddings.
We differ slightly from Azizian & Lelarge (2021) in that they only define equivalence relations graphs.
5

---

Published as a conference paper at ICLR 2022
The summation depth sd of TL()) expression yp measures the nesting depth of the summations
exprevely:
sd sd . (22) sd(;p + (22) := max(sd((p1) sd (d()))) }. sd(a . (p)) := sd((1),, (f (p)) . =
Eg in the expression. It is defined inductively: sd(1 opy) = (((, 8)) = (z)( := 0,
T summation depth one. We write TL (52) for the class of expressions in T (9) of summation
( i E [p]}. and sd(E P1) == sd())) + 1. For example, expressions 44, above h have
depth at most I, and use k-MPNN for the corresponding class of k-MPNNs. We can now refine Theorem 4. taking into account the number of rounds used in k-WL.
Theorem 4.2. For all t 2 O. k 2 1 and any collection Qi functions, pI (=(Wl)) = P1 (TL 241 (2))
Guarded TL and color refinement. As noted by Barceló et al. (2020), the separation power of vertex emheddings of simple GNNs, which propagate information only through neighboring ver- tices, is usually weaker than that of 1- 1-WL. For these types of architectures, Barceló et al. (2020) provide a relation with the weaker color refinement algorithm, but only in the special case of first- order classifiers. We can recover and extend this result in our general setting, with a guarded version of TL which, as we will show, has the same separation power as color refinement.
The guarded fragment GTL( of (Ly( is inspired by the use of adjacency matrices in simple GNNs. GTL( only equality predicates 12, =x, (constant 1) and fr, (constant 0) are allowed, addition and multiplication require the component expressions to have the same (single) free index, somm
and summation must occur in a guarded form Ex, (F(m,, 3ry) (((z)), for i,j E [2]. Guardedness
means that summation only happens over neighbors. In GTL, all expressions have a single free variable and thus only functions from G1 can be represented. Our example expressions 45 (21) are guarded. The fragment (TL) consists of expressions in GTL(S2) of summation depth at most We denote by MPNNs and MPNNs the corresponding "guarded" classes of 1-MPNNs."
Theorem 4.3. For all t 2 0 and any collection 52 of functions: pI (cr")) = p1 (GTL
As an application of this theorem, to detect the existence of paths of length f, the number of guarded layers in GNNs should account for representation in GTL( of summation depth of at least t. We recall that p (vwl)) C (cr(")) which, combined with our previous results, implies that (L) (resp.. 1-MPNNs) is strictly more separating than GTL (resp., MPNNs).
Graph embeddings. We next establish connections between the graph versions of k-WL and CR, and TL expressions without free index variables. To this aim, we use (F) for a set F of functions f: 9:9- R as the equivalence relation over G defined in analogy to P1: (G, H) E Po(F) = e
F,G() F. can consider ")( and ?) for any t 2 0 and k 2 1. Also here, Po(gwl C po(gwl()) but different from vertex embeddings, po (ggr""))) po (gw (Grohe, 2021). We define po(C) for a fragment L of TL())) by considering expressions without free index variables.
= f(H). We thus consider separation power on the graph level. For example, we
eeeeedieeeeeeeee considering expressiooeeeeee
The connection between the number of index variables in expressions and k-WL remains to hold. Apart from h- = 1, no clean relationship exists between summation depth and rounds, however." 4 Theorem 4.4. For all L 2 O, k Z 1 and any collection Q of functions, we have that:
(I) Po (gcr")) = Po (lL+*(())) = po (gwW((
(2) Po(gw( = Po (TL)+1
Intuitively, in (1) the increase in summation depth by one is incurred by the additional aggregation needed collect all vertex labels computed by gw!f".
Optimality of number of indices. Our results so far tell that graph functions represented in TL 1
(L2 are at most as separating as k-WWL What is left unaddressed is whether all k + 1 in- dex variables are needed for the graph functions under consideration. It may well be, for example, that there exists an equivalent expression using less index variables. This would imply a stronger upper bound on the separation power by (-WL for E < k. We next identify a large class of TL())) expressions, those of treewidth k, for which the number of index variables can be reduced k+ 1. e
'For the connection to classical MPNNs (Gilmer et al., 2017), see Section H in the supplementary material. 'Indeed, the best one can obtain for general tensor logic expressions is po (TL##1 (L)+((()) S po(wl("") C Pol (TL (LL=P(()) This follows from Cai al. (1992) and connections finite variable logics.

---

Published as a conference paper at ICLR 2022
Proposition 4.5. Expressions in TL( of treewidth i are equivalent to expressions in TL).
Treewidth is defined in the supplementary material (Section G) and treewidth of k implies that the computation of tensor language expressions can be decomposed, by reordering summations, such that each local computation requires most + indices (see also Aji & McEliece (2000)). As a simple example, consider ((x1) Exn Eng E( #2) (x 233 in TL.) such that [0, vlc counts the number of paths of length two starting from v. This expression has a treewidth of one. And indeed, it is equivalent to the expression ((11)= - Eaz E( x2) (E 21 (1)) in TL2 (and in fact in ) As a consequence, no more vertices can be separated by (z1)) than by cr rather than vwl. as the original expression in TL2 suggests.
On the impact of functions. All separation results for TL((2) and fragments thereof hold irre- gardless of the chosen functions in S2, including when no functions are present at all. Function applications hence do not add expressive power. While this may seem counter-intuitive, it is due to the presence of summation and multiplication in TL that are enough to separate graphs or vertices.
5 CONSEQUENCES FOR GNNS
We next interpret the general results on the separation power from Section in the context of GNNs.
1. The separation power of any vertex embedding GNN architecture which is an MPNN is bounded by the power of rounds of color refinement.
We consider the Graph Isomorphism Networks (GINs) (Xu et al., 2019) and show that these are MPNNs. To do so, we represent them in GTL(S2). Let gin be such a network; updates vertex embeddings as follows. Initially, gin (0) : 91 + R (G, v) + F == cola(u) E R For layer t O, gin 91 + R is given by: (G, v) + F = mlp") [F! ,E FM--"), with FI E Raxt and mip" = (mlpf",..... mlp?!) 26 -> R& an MLP. We denote by GIN the class of GINs consisting / layers. Clearly, gin can be represented in GTL by considering the expressions sp 00 (x1) = (1) for each i E [fo]. To represent gin" assume that we have 4-11 expressions of ((11) in GTL" representing gin"-"), That is, we have [ip"""",, = Fd-11) for each vertex and i [.--]]. Then gin")) is represented by E, expressions (f((((1) defined as:
mlp.") (t) (pt (at)....,,, (x1), Eoy E(21, 40t (42))())...... Eze E(11, Pe,_ (
Pe_
which are now expressions in GTL where Ω consists of MLPs. We have [0 alc = F.l for each e E Va and i E [Lr]. as desired. Hence, Theorem 4.3 tells that t-layered GINs cannot be more separating than rounds of color refinement, in accordance with known results (Xu et al., 2019; Mor- ris et al., 2019). We thus simply cast GINs in GTL(1)) to obtain an upper bound on their separation power. In the supplementary material (Section D) we give similar analyses for GraphSage GNNs with various aggregation functions (Hamilton et al., 2017), GCNs (Kipf & Welling, 2017), simpli- fied GCNs (SGCs) (Wu et al., 2019), Principled Neighborbood Aggregation (PNAs) (Corso et al., 2020), and revisit the analysis of ChebNet (Defferrard et al., 2016) given in Balcilar al. (2021a).
2. The separation power of any vertex embedding GNN architecture which is an k-MPNN is bounded by the power of rounds of k-WL.
For A = 1, we consider extended Graph Isomorphism Networks (eGINs) (Barceló et al., 2020). For an egin E eGIN, egin
(h G1 - 18 is defined as for GINs but for layer O. egin" 91 + R is defined by (G, v) + F == mip ( EueNa(t) F 1) >neva Fit -1), where mlp") is now an MLP from 3.3 1 + F The difference with GINs is the use of Eneve Fit-1) which corresponds to the unguarded summation Ez, (x1)) This implies that TL rather than GTL needs to be used. In similar way for GINs we can represent eGIN layers in TL That is, each (GIN is 1-MPNN Theorem 4.2 tells that t rounds of 1-WL bound the separation power of t-layered extended GINs conform to Barceló et al. (2020). More generally, any GNN looking to go beyond CR must use non- -uarded aggregations.
For & 2 2, it is straightforward to show that t-layered "folklore" GNNs (G-FGNNs) (Maron et al., 2019b) are * and thus, by Theorem 4.2, rounds of k-WW bound their separation power.
7

---

Published as a conference paper at ICLR 2022
One merely needs to cast the layer definitions in TL(S2) and observe that k++ indices and summation depth é are needed. We thus refine and recover the k-WL bound for k-FGNNs by Azizian & Lelarge (2021). We also show that the separation power of (l: IIInaraiat Graph Networks ((k + 1)-IGNs) (Maron et al., 2019b) are bounded by k-WL, albeit with an increase the required rounds.
Theorem 5.1. For any k Z 1, the separation power of a L-layered (k + 1)-IGNs is bounded by the separation power of Ik rounds of k-WL.
We hereby answer open problem in Maron et al. (2019a). The case k = 1 was solved in Chen al. (2020) by analyzing properties of 1-WL. By contrast, Theorem 4.2 shows that one can focus on expressing (k+1)- (k+1)-IGNs in TL++1(52)
and analyzing the summation depth of expressions. The proof of Theorem 5.1 requires non-trivial manipulations of tensor language expressions:
a simplified proof of Geerts (2020). The additional rounds (Ik) are needed because (k + 1)-IGNs aggregate information in one layer that becomes accessible to k-WL in l rounds. We defer detail to Section in the supplementary material, where we also identify simple class of t-layered (A + 1)-IGNs that are as powerful as (k + 1)-IGNs but whose separation power is bounded by t rounds of k-WL.
We also consider "augmented" GNNs, which are combined with preprocessing step in which higher-order graph information is computed. In the supplementary material (Section D.3) we show how TL encodes the preprocessing step, and how this leads to separation bounds in terms of k-WL, where k depends on the treewidth of the graph information used. Finally, our approach can also be used show that the spectral CayleyNets (Levie al., 2019) are bounded in separation power by 2-WL. This result complements the spectral analysis of CayleyNets given in Balcilar et al. (2021b).
3. The separation power of any graph embedding GNN architecture which k-MPNN is bounded by the power of k-WL.
Graph embedding methods are commonly obtained from vertex (tuple) embeddings methods by including a readout layer in which all vertex (tuple) embeddings are aggregated. For example, mlp(E.ev ((n (G, u)) is a typical readout layer for eGINs. Since egin" can be represented in (2)), the readout layer can be represented in TL TL ((2). using an extra summation. So they are 1MMPNNs. Hence, their separation power is bounded by gwlf", in accordance with Theorem 4.4. This holds more generally. If vertex embedding methods are k-MPNNs, then so are their graph versions, which are then bounded by gwlg by our Theorem 4.4.
To go beyond the separation power of k-WL, necessary to use GNNs whose layers are represented by expressions of treewidth > k.
Hence, design expressive GNNs one needs to define the layers such that treewidth of the resulting TL expressions is large enough. For example, to go beyond 1-WL. TL3 representable linear algebra operations should be used. Treewidth also sheds light the open problem from Maron et al. (2019a) where it was asked whether polynomial layers (in A) increase the separation power. Indeed, consider a layer of the form o 3A3.F F.F.F.W... W)) which raises the adjacency matrix to the power three. Translated in TL?)), layer expressions resemble Mx, Enng Ex, ((I)) E(x2, 43) E(23, 2.4), of treewidth one. Proposition 4.5 tells that the layer is bounded by w/ (and in fact by cr in separation power. If instead, the layer is of the form (C F- W) where Cij holds the number of cliques containing the edge ij. Then, in (L2) we get expressions containing Eg, Ers E(x1,
E( xz)) E(x2, Tz). The variables form 3-clique resulting in expressions of treewidth two. As a consequence, the separation power will be bounded by wil?" These examples show that it is not the number of multi- plications (in both cases two) that gives power, it is how variables are connected to each other.
FUNCTION APPROXIMATION
We next provide characterizations of functions that can be approximated by TL expressions, when interpreted as functions. We recover and extend results from Azizian & Lelarge (2021) by taking the number of layers of GNNs into account. We also provide new results related to color refinement.
6.1 GENERAL TL APPROXIMATION RESULTS
We assume that G. is a compact space by requiring that vertex labels come from a compact set K S Re0 Let F be set of functions f G, - R and define its closure F as all functions h. from G, for
8

---

Published as a conference paper at ICLR 2022
which there exists sequence f1, f2.... E F such that lim;-+oo supc, fi(G, (( -(G, =0 for some norm ||.I|- We assume F satisfy two properties. First, F is concatenatiionclloeed. if
fi : Go + _º and f2 9, + 18 are in F. then g == (2) : g3 + 1 : (G,u) H (fi(G, v). [2(G, u)) is also in FF. Second, F is function-closed, for fixed & E N: for any E F such that f 9, + Rp, also g o f G. - R in F for any continuous function g R - RR' For such F, we let Fr be the subset of functions in F from G, to R Our next result is based generalized Stone-Weiee Weierstrass Theorem (Timofte, 2005), also used in Azizian & Lelarge (2021).
Theorem 6.1. For any L, and any set F of functions, concatenation and function closed for e, we have: Fe = {f g. + R I
(F(F) S (o(ff).
This result gives us insight on which functions can be approximated by. for example, set F of functions originating from a class of GNNs. In this case, F, represent all functions approximated by instances of such a class and Theorem 6. tells us that this set corresponds precisely to the set of all functions that are equally less separating than the GNNs in this class. If. in addition, Fe is more separating that CR or k-WL, then we can say more. Let alg E {crl)) ger"), .wwl gwl( }.
Corollary 6.2. Under the assumptions of Theorem 6.1 and if p(Ft) = p(alg), then Fi (s 9 R p(alg) C p(f))
The properties of being concatenation and function-closed are satisfied for sets of functions repre- sentable in our tensor languages, if 52 contains all continuous functions g R" + IR', for any p. or alternatively, all MLPs (by Lemma 32 in Azizian & Lelarge (2021)). Together with our results in Section 4, the corollary implies that "P 1-MPNNs k-MPNNs or k-MPNNs can approx- imate all functions with equal or less separation power than cr gcr!") vwl gwl(") respectively.
Prop. 3.1 also tells that the closure consists of invariant (s = 0) and equivariant ( > 0) functions.
6.2 CONSEQUENCES FOR GNNs
All our results combined provide a recipe guarantee that a given function can be approxi- mated by GNN architectures. Indeed, suppose that your class of GNNs is an MPNN (respectively, 1-MPNN k-MPNN" or k-MPNN, for some & 2 1). Then, since most classes of GNNs are concatenatioon-olseed and allow the application of arbitrary MLPs, this implies that your GNNs can only approximate functions f that are no more separating than cr (respectively, gcr"), vwl. or gwlg (20)). ). To guarantee that that these functions can indeed be approximated, one additionally has to show that your class of GNNs matches the corresponding labeling algorithm in separation power.
For example, GNNs in GIN are MPNNs and thus GIN contains any function f : 9 + R
satisfying Pi (crlti) S P1 (f). Similarly, eGIN are 1-MPNNs so eGIN contains any function satisfying P1 (w S pi (f); and when extended with readout layer, their closures consist of Po(vwl(t) S Po(l)) Finally, k-FGNN are k- (P so k- K-FGNN consist of functions f such that pı (vwl?") S. (J)). We thus recover and extend results by Azizian & Lelarge (2021) by including layer information (f) and by treating color refinement separately from 1-WL for vertex embeddings. Furthermore, Theorem 5.1 implies that (k 1)-IGN consists of functions f satisfying P1 (vwl S P1(f) and po(gwl) S Po(.f) a case left open in Azizian & Lelarge (2021).
functions f 9o + T satisfying Po(ger"))
These results follow from Corollary 6.2, that the respective classes of GNNs can simulate CR or k-WL on either graphs with discrete (Xu et al., 2019; Barceló et al., 2020) or continuous labels (Maron et al., 2019b), and that they are k-MPNNs of the appropriate form.
7 CONCLUSION
Connecting GNNs and tensor languages allows us to use our analysis of tensor languages to un- derstand the separation and approximation power of GNNs. The number of indices and summation depth needed to represent the layers in GNNs determine their separation power in terms of color refinement and Weisfeiler-Leman tests. The framework of k-MPNNs provides handy toolbox to understand existing and new GNN architectures, and we demonstrate this by recovering several results about the power of GNNs presented recently in the literature, well proving new results.

---

Published as a conference paper at ICLR 2022
8 AKNOWLEDGEMENTS & DISCLOSURE FUNDING
This work is partially funded by ANID-Millennium Science Initiative Program-Code ICN17 1.0,, Chile.
ETHICS STATEMENT
The results in this paper do not include misleading claims; their correctness is theoretically verified. Related work accurately represented.
REFERENCES
Mahmoud Abo Khamis, Hung Q. Ngo, and Atri Rudra. FAQ: Questions Asked Frequently. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGE Symposium Principles of Database Systems, PODS, pp. 13-28. ACM, 2016. URL https:///doat http://///....ogg1.11111//////// 29C2280, 3, 39, 40, 41
Srinivas M. Aji and Robert J. McEliece. The generalized distributive law. IEEE Transactions on In- formation Theory, 4662):35333,,, 2000. URL httpt:/ss//bii.or/1111111111 0121//11.888.1..../1/1 3,7
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural net- works. In Proceedings of the 9th International Conference on Learning Representations, ICLR, 2021. URL https:/ /pwp//peeeeeeeeee/ee/eee net/ forum? 1ereiiddxxlho00 XXggXXXA 2, 5, 8, 9, 28, 37, 38
Muhammet Balcilar, Pierre Héroux. Benoit Gaüzère, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In Proceedings of the 38th International Conference on Machine Learning, volume 139 Proceedings of Ma- chine Learning Research, pp. 599-608. PMLR, 2021a. URL httett://proceeeiiii mmr. press /vassvvll /v13/v1...// balcilar22aa html. 1, 2, 14, 30, 31
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in a spectral perspective. In Proceedings of the 9th International Conference on Learning Representations, ICLR, 2021b.
URL https: oppnreview. net/ forum? id= qh CMMXMMMyX 2, 30, 31
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In Proceedings of the 8th International Conference on Learning Representations, ICLR, 2020. URL httph: htttps::/ppeereviiii Forum?id=r11m 1277AKEV. 3, 6, 7, 18, 38
n
Pablo Barceló, Floris Geerts, Juan L. Reutter, and Maksimilian Ryschkov. Graph neural net- works with local graph parameters. In Advances Neural Information Processing Systems, volume 34, 2021. URL https: http:////roce///eee/eeeeee neurips cc hwtppaapp////////e///eee Sapper2000 2021 1//ash//////// wtt.:ccppppprrape
(0t.0e00057776666022bbbbbb-b.ab. Abattaaaddbbbbbbbtttt....... html. 28, 29
Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F. Montúfar, Pietro Lió, and Michael M. Bronstein. Weisfeiler and Lehman go topological: Message passing simpli- cial networks. In Proceedings of the 38th International Conference on Machine Learning, vol- ume 139 of Proceedings of Machine Learning Research, pp. 1026-1037. PMLR, 2021. URL http:/ http://pocceeiingg. mmlr.press / vv33 139, /bwbonnnr22eeec html. 29,
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. In Graph Representation Learn- ing and Beyond (GRL+) Workshop at the 37 th International Conference on Machine Learning, 2020. URL htt.h:tp///// aawiv.iviiv..//ivo org/ abs 02006 09252. 29
Robert Brijder, Floris Geerts, Jan Van den Bussche, and Timmy Weerwag. On the expressive power of query languages for matrices. ACM TODS, 44:4).15:1-15:31, 2019. URL https: : //oo.. org/ 113.111113331440 14,30
10

---

Published as a conference paper at ICLR 2022
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and lo- cally connected networks on graphs. In Proceedings of the 2nd International Conference on Learning Representations, ICLR, 2014. URL https:/ /wwp//ppppeeeeeee//e//p/ee .et.eewwweeeeee...eee ftrefformmmcc DoNaQf-Usoii 30
Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identifications. Comb,, ((4))389-410, 1992. URL htLhsts::// http://0...rr11..1111.. BF BF01305232. 3,
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. the equivalence between graph isomorphism testing and function approximation with GNNs. In Advances in Neural Informa- tion Processing Systems, volume 32, 2019, URL https //proceed ngs wwwurerrss.o cc/ paper/2019/ filefflllle/eeeeee http///eeeeeeeelddaalaaa (eeeee00222999114310 628.cc111311111111101111... Paaaa..appppp.... 2, 28
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In Advances in Neural Information Processing Systems, vol- ume 33, 2020. URL https:
http::://proceedingge wtw.:/ceeeeinnnn..u.......ee neurips..p... wtt.cc/pppppeee htc//aape//222///10
Paper pdf. 8,
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pictro Liō, and Petar Veličković. Princi- pal neighbourhood aggregation for graph nets. In Advances in Neural Information Processing Systems, volume 33, 2020. URL https: http://eooeeeeeeeeeeeeeeeeeeeeee www.iieup..... CC/ ppppp///ppp////////ppp pdf. 7,26, 27
file/9 Matee99caaee dec.99cc55520 65a1 1 78
L. Csanky, Fast parallel matrix inversion algorithms. SIAM Comput., 5(4):618-623, 1976. URL
https:/ /tpp:://doii /10.
31
Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms good basis for counting small subgraphs. In Proceedings of the 49th Symposium on Theory of Computing, STOC, pp- 210- 223, 2017. uttpt //tp///xxx/ doi www.dd........eeeeeeooooooeoee.e 1ttp//0.111//35553330 011144/2055599955550000 3055502. 29
Clemens Damke, Vitalik Melnikov, and Eyke Hüllermeier. novel higher-order weisfeiler-lehman graph convolution. In Proceedings of The 12th Asian Conference on Machine Learning, ACML, volume 129 of Proceedings of Machine Learning Research, pp. 49-64 64. PMLR, 2020. URL
www..rr.....m.m......m... poress/v123 damke22a html. 28
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, volume 30, 2016. URL httttts:::pooceeeeeeeeee
neurips cc/ http/apppe/21/////////// pdf. 7,
Martin Fürer. Weisfeiler-Lehman refinement requires least a linear number of iterations. In
Proceedings of the 28th International Colloqium on Automata, Languages and Programming, ICALP, volume 2076 Lecture Notes Computer Science, pp. 322-333. Springer, 2001. URL
https: /tl:://doo. /ow.i org / 100 1007 540 4800--44224----- 5_27.
Floris Geerts. The expressive power of kth-order invariant graph networks. CoRR, abs/2007..003555 2020. URL https: http//axvvvvvo//o///.oa abs 2007.000100 12035. 8
Floris Geerts. On the expressive power of linear algebra on graphs. Theory Comput, Syst., 65(1): 179-239, 2021. URL httttt:p////olt http//oooooooo/////////oooooo 10. 1007/1007000 /000220---2222 00000000-000 0000009990999 9. 1, 14
Floris Geerts, Filip Mazowiecki, and Guillermo A. Pérez. Let's agree to degree: Comparing graph convolutional networks in the message- paasagg framework. In Proceedings of the 38th Interna- tional Conference Machine Learning, volume 139 of Proceedings of Machine Learning Re- search, pp. 3640-3649, PMLR, 2021a. URL http:/ /pooeediings mlr. www.s//ves/... geerts21a html. 26
Floris Geerts, Thomas Muñoz, Cristian Riveros, and Domagoj Vrgoe. Expressive power of linear Symposium
algebra query languages. In Proceedings of the 40th ACM on Principles of Database Systems, PODS, pp. 342-354, ACM, 2021b. URL https: //doi. org/10..145/345500 345831

---

Published as a conference paper at ICLR 2022
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley. Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 1263-1272, 2017. URL http: http::/tttcceeeeeeeeeeeee http://eccceeeegeeeeeeeee/c mlr.
press/v70 mmmeee7aa/// 7 1 Te 7 pdf. 2, 3, 6, 42, 43
Martin Grohe. The logic of graph neural networks. In Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, pp. 1-17. IEEE, 2021. URL https://doi.
.20.66.2222111 9470677 5, 6,
William L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelli- gence and Machine Learning, 14(3):1-159, 2020. URL https: http:://doo.oooo ott.:/...0//0///////// S01 251004EDIVOO Y200009A
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learn- ing on large graphs. In Advances in Neural Information Processing Systems, vol- ume 30, 2017. URL https: httpss:/pproceddngs..o neur ps wwwpp//.ccppppppppc.pppppppp..p. wtt.scccppppp//a/eeee ppapr//217/filee 5dd9db5e033da 9cw.bboaa337777aeeeeeeoaa 2eeeaaeee77aeeeea--aa pdf. 7,25
David K. Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spec- tral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-150, 2011. ISSN 1063-5203. doi: httpt///cc...........///////////
URL https:////ee //ww:.
sciencedirect. com/ wtt....w.........ee..teeeeesecce
30
Neil Immerman and Eric Lander. Describing graphs: A first-order approach to graph canon- ization. In Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, pp. 59-81. Springer, 1990. URL https: org/10.1077
978-1-4612-44788
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems, volume 32, pp- 7092-7101, 2019. URL https: Pawp:sfrsspaaapp.ppdpp Paper.
neurips.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In Proceedings of the 5th International Conference Learning Representations, ICLR, 2017. URL https:/ /ttp::///opeeeeeeeeeeeeee net httpp/ateedd/eeaaaaaaeaaaaaa
7,22
Ron Levie, Federico Monti, Xavier Bresson, and Michael M. Bronstein. Cayleynets: Graph convo- lutional neural networks with complex rational spectral filters. IEEE Trans. Signal Process. 67 (1):97-109, 2019. URL https: :/tp:s///do/ doi. org. 10. 1109/1133 2018 2879624, 2, 8, 30, 31
Haggai Maron, Heli Ben-Hamu, and Yaron Lipman. Open problems: Approximation power of invariant graph networks. In NeurlPS 2019 Graph Representation Learning Workshop, 2019a. URL wwthhhtss//ggleeeeee
www.g..iiti githubutubb.ug. weto.io/ppppae wttpppppe///111 ppt.fff.....f......... 2, 8.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably pow- erful graph networks. Advances in Neural Information Processing Systems, vol- ume 32, 2019b. URL https: bb04af0f7e (ee.ee//ceeeee222033771771111110 -app pdf. 2, 8, 27, 28, 32, 35, 36, 37,38, 38,38,33 39
wwt.cccpppppec11110 /ilee//
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In Proceedings of the 7th International Conference on Learning Representationss, ICLR, 2019c. URL https: wwwpppeeeeeeeeee/// net wtwee///ooommmdddy//eeee /ttpp//eeeeeeeeeeeoooooooaaaaaaa
2, 32, 35
Christian Merkwirth and Thomas Lengauer. Automatic generation of complementary descriptors with molecular graph networks. J. Chem. Inf. Model., 15(5): 2005. URL https:
//doi.
H. L. Morgan. The generation of unique machine description for chemical structures-a technique developed at chemical abstracts service. Journal of Chemical Documentation, 5(2):107-113, 1965. URL https:// http:/:///oooooo////////o/o orgg/00 0011110.....0/1.... 6001770118
12

---

Published as a conference paper at ICLR 2022
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In Proceedings of the 33rd AAAI Conference Artificial Intelligence, pp. 4602 1602-4609, 2019. URL hwtps:tpp/..... / .rgg
609/aaa1..... 033101..... 3301 602. 1, 2, 7, 25, 28
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and Leman sparse: Towards scalable higher-order graph embeddings. In Advances in Neural Information Processing Systems, volume 33, 2020, URL https: /attps::/procee /ttp://cccceeencceeeeeeeecc neurips cc/ /pppppp/t22///ieee f81 4ee 228 81 4de1 99b2 (eb22e877775c-Paee
pdf. 2828
Martin Otto. Bounded Vuriable Logics and Counting: A Study Finite Models, volume 9 of Lecture Notes in Logic. Cambridge University Press, 2017. URL
778131671681 2,
Martin Otto. Graded modal logic and counting bisimulation. ArXiv, 2019. URL https://
arxiv. arxiv.org/aae wrw.ooggg//b....... /1910 00039. 18
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.
The graph neural network model. IEEE Trans. Neural Networks, 20(1):61-8)) 80, 2009. URL
2005605.
Vlad Timofte. Stone-Weierstrass theorems revisited. Journal of Approximation Theory, 136(1): 45 45-59, 2005. http:t:: .or.oo..rr///oo 1tt.:/......1111111111
10.66/16--- j.t...a..000 05 004. 9, 36
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liö, and Yoshua Bengio. Graph attention networks. In Proceedings of the 6th International Conference on Learning Representations, ICLR, 2018. URL https:/ http::///ppeeeviewww/e wwwp:nrunfoooooooooooooo rJXMpikCZ. 27
Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Confer- ence Machine Learning, ICML, volume 97 of Proceedings of Machine Learning Research, pp. 6861-6871. PMLR, 2019. URL http://proceedingg mlr. pre.spessssee...... wwlr.press/v9.. /twpss////////////////// html. 7.26
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful are graph neural networks? In Proceedings of the 7th International Conference on Learning Representations, ICLR, 2019. URL htthhttt///// /tt///peevvvvveeeeeeeeeeeee nwtp:/eeeeeeeeeeeeeeeeeeeee wttp://ooommmmndreeeeeeeeeee 61.5km.....mmmmmmm 1, 2, 23, 25, 38
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in Neural Information Processing Systems, volume 30, 2017. URL https: httpps//prooeeeingg neurips. httpps.ccpppppee cc/paperr201///1lee #22e4747dalaa22 2222
23
13

---

Published as a conference paper at ICLR 2022
SUPPLEMENTARY MATERIAL
A RELATED WORK CNT'D
We provide additional details on how the tensor language TL(S2) considered in this paper relates recent work other matrix query languages. Closest to TL((2) is the matrix query language Sum-MATLANG (Geerts et al., 2021b) whose syntax is close to that of TL()). There are, however, key differences. First, although Sum-MATLANG uses index variables (called vector variables), they all must occur under a summation. In other words, the concept of free index variables is missing, which implies that no general tensors can be represented. sors and the presence of free index variables is crucial define vertex, or more generally, k-tuple embeddings in the context of GNNs. Furthermore, no notion of summation depth was introduced for Sum-MATLANG In TL())), the summation depth is crucial assess the separation power in terms of the number of rounds of color refinement and k-WL. And in fact, the separation power of sum- MATLANG was not considered before, and neither finite variable fragments of sum- Mum-MATLANG and connections to color refinement and k-WL studied before. Finally, no other aggregation func- tions were considered for Sum-MATLANG. We detail in Section C.5 that TL(Ω2) can be gracefully extended to (L θ) for some arbitrary set θ of aggregation functions.
TL()), we can represent arbitrary ten-
Connections 1-WL and 2-WL and the separation power of another matrix query language, MATLANG (Brijder et al., 2019) were established in Geerts (2021). Yet, the design of MATLANG is completely different in spirit than that of TL()). Indeed, MATLANG does not have index variables or explicit summation aggregation. Instead, it only supports matrix multiplication, matrix transpo- sition, function applications, and turning a vector into a diagonal matrix. As such, MATLANG can be shown to be included in (L2). Similarly as for Sum-MATLANG, MATLANG cannot represent general tensors, has no (free) index variables and summation depth is not considered (in view of the absence of explicit summation).
We also emphasize that neither for MATLANG nor for Sum-MATLANG guarded fragment was considered. The guarded fragment is crucial to make connections color refinement (Theorem 4.3). Furthermore, the analysis in terms of the number of index variables, summation depth and treewidth (Theorems 4.1,4. and Proposition 4.5), were not considered before in the matrix query language literature. For none of these matrix query languages, approximation results were considered (Sec- tion 6.1).
Matrix query languages are used to assess the expressive power of linear algebra. Balcilar et al. (2021a) use MATLANG and the above mentioned connections 1-WL and 2-WL, to assess the separation power of GNNs. More specifically, similar to our work, they show that several GNN architectures can be represented in MATLANG, or fragments thereof. As consequence, bounds on their separation power easily follow. Furthermore, Balcilar et al. (2021a) propose new architectures inspired by special operators in MATLANG. The use of (1)) can thus been seen as a continuation of their approach. We note, however, that TL( is more general than MATLANG (which is included in (L2),, allows to represent more complex linear algebra computations by means summation (or other) aggregation, and finally, provides insights in the number of iterations needed for color refinement and k-WL. The connection between the number of variables (or treewidth) and k-WL is not present in the work by Balcilar et al. (202 la), neither is the notion of guarded fragment, needed to connect to color refinement. We believe that is precisely these latter two insights that make the tensor language approach valuable for any GNN designer who wishes to upper bound their GNN architecture.
B DETAILS OF SECTION 3
B. PROOF OF PROPOSITION 3.1
Let G = (V, E, col) be graph and let be permutation of V. As usual, we define
a + = (V", E" col") as the graph with vertex set V := V. edge set ow E E" if and only if o (v)o ((w) E E, and col" (v) = col(o-'(()) (v)). We need to show that for any expression y(x)) in (L))) either [4, o+ * VInaG = [p, vla. or when has no free index variables, [yplo = Iplo- We verify this by simple induction the structure of expressions in TL(Ω).
14

---

Published as a conference paper at ICLR 2022
If 2z) 1æ; opays then for valuation mapping 2; to and 2, oj in V:
[1,, opæy, p|a = op op op((s) = [1z, 0x * lo
where we used that is permutation.
((;;) = Pc(x;;, then for a valuation μ mapping x; to 2 in V:
[Pr, plc (col():))) (col" [
where we used the definition of col".
Similarly, if (();, E(z;, then for valuation assigning 2; is and zj ey: u| = 1 EuyeR ((())(())))= =
where we used the definition of E
((x)) = 4i (2)) ) (22)) then for a valuation v from æ to V: lp,ujc |,,, v/a [122, [,i, * ulower * [ vlonG:
where we used the induction hypothesis for yo and ø2. The cases ((x) = (2(())) + (2((2)) and (p()) (x) are dealt with in a similar way.
If (xx) = f())(x))) (x))) (x),)) then
pp. "(1s,.vl....... ((.. vlp)
f(1f1, o vIo....... 18p 0 x
[p, * v.o.GG
where we used again the induction hypothesis for Finally, if (pxx)
App
Ey PI( y) then for valuation of a to V:
14,, ula
Eler. - u|]c Σ x u|lonr
VEV
eEV
Σ 1
v| ollo.o = [4p, vll..G.
veVe
where we used the induction hypothesis for P1 and that V because permutation.
We remark that when does not contain free index variables, then vol [plc for any valu- ation v, from which invariance follows from the previous arguments. This concludes the proof of Proposition 3.1.
C DETAILS OF SECTION 4
In the following sections we prove Theorem 4.1, 4.2, 4.3 and 4.4. More specifically, we start by showing these results in the setting that TL(2) only supports summation aggregation (2., e) and in which the labelx-labellings in graphs take values in (0. 1)r In this context, we introduce classical logics in Section C. and recall and extend connections between the separation power of these logics and the separation power of color refinement and k-WL in Section C.2. We connect TL(22) and logics in Section C.3, to finally obtain the desired proofs in Section C.4. We then show how these results can be generalized in the presence of general aggregation operators in Section C.5, and the setting where labbex-labellings take values in g in Section C.6.
C.1 CLASSICAL LOGICS
In what follows, we consider graphs G = (Va, FGG, colG) with colg : Vo - (0, We start by defining the k-variable fragment Ck of first-order logic with counting quantifiers, followed by the definition of the guarded fragment GC of C2, Formulae in C* are defined over the set { xx} of variables and are formed by the following grammar:
6 := (x+ 2z)
E( 2.)) Ps (x(2)) | up ( 32m 4p:
15

---

Published as a conference paper at ICLR 2022
where i.j [k], E is binary predicate, P. for [d] are unary predicates for some N, and m E N. The semantics formulae C* defined in terms of interpretations relative to a given graph G' and (partial) valuation μ : { 2& Va. Such interpretation maps formulac, graphs and valuations to Boolean values B == (1, T), in similar way as we did for tensor language expressions.
More precisely, given a graph G = -VV. Eg, cola) and partial valuation pu { m& - Va. define [2, IB for valuations defined on the free variables in sp. That is, we define:
[xi = T == if p(x;) = (læ;)) then T else Li 18) = if u(z;))(a;; E Ea then T else 1; (Pa( if cola (o(r()( 1 then T else 1;
[-9, m lle
P p2; 11 | = [4 mIe A 102,
[ 2m 2; P1 G = ke e Va [p, + vll8 = TH 2 m then else 1.
In the last expression, μlz; + si denotes the valuation l modified such that maps x; to vertex u.
We will also need the guarded fragment GC of C² in which we only allow equality conditions of the form 2, = 24, component expressions of conjunction and disjunction should have the same single free variable, and counting quantifiers can only occur in guarded form: 32th (z x2) A up( (zg) or -2mm, (F(22, .1) ()(1)) The semantics of formulae GC is inherited from formulae C².
Finally, we will also consider C* Gow- that is, the logic C* extended with infinitary disjunctions and conjunctions. More precisely, add to the grammar of formulae the following constructs:
V Pa and A Pa aεA
aEd
where the index set A can be arbitrary, even containing uncountably many indices, We define GCoow in the same way by relaxing the finite variable conditions. The semantics is, as expected:
IV We Paa plc T if for at least one A. [&a. plg = T, and [lae Pa. plee = T if for all
A. [Po: pl T.
We define the free variables of formulae just as for TL, and similarly, quantifier rank is defined as summation depth (only existential quantifications increase the quantifier rank). For any of the above logics L we define ( as the set of formulae in L of quantifier rank at most t.
To capture the separation power of logics, we define pi ((())) the equivalence relation on defined by
(G,, E PI = Vip(z) E L 11, Mer
where Mh is any valuation such that p(z) a similar way, except that now the relation is only over pairs of graphs, and the characterization over all formulae with free variables (also called sentences). Finally, also use, and define, the relation P.. which relates pairs from Gg: consisting of a graph and an s-tuple of vertices. The relation is defined
and likewise for The relation po is defined in
((G, v), (H, w)) pC(C =
Vi(a)) _ Ip, = Ii, pw 1e.
where x consist free variables and Ho is a valuation assigning the i-th variable of x to the i-th value of v, for any [s).
C.2 CHARACTERIZATION OF SEPARATION POWER OF LOGICS
We first connect the separation power of the color refinement and k-dimensional Weisfeiler-Leman algorithms the separation power of the logics we just introduced. Although most of these con- nections are known, we present them in a bit of more fine-graing ine-grained way. That is, we connect the number of rounds used in the algorithms to the quantifier rank of formulae in the above logics.
Proposition C.I. For any 2 have the following identities:
16

---

Published as a conference paper at ICLR 2022
(1) pi (cr")) p1 (GC and pu pu(gcr")) = Pu(Bwl(") pa (C2:((+))) (2) For k 2 1, (vwll) p (C++1 and
po po(cht2((ett)) - po((wlk))) S po po(((+1(((t)))
As a consequence, pa (B(Bwl = po(ckt1).
Proof. For (1), the identity P1 (crl)) = p1 (GC is known and can be found, for example, in Theorem V.10 in Grohe (2021). The identity po(gcr pa (gwwl")) can be found in Proposition V.4 in Grohe (2021). The identity po (o(gl)))) po((2.((t1)) is a consequence of the inclusion shown in (2) for k =
For (2), we use that p=(W) = Pk (C)+1,00), see e.g., Theorem V.8 in Grohe (2021). We ar- gue that this identity holds for pi (vwll)) pi (Ck+I,0)) Indeed, suppose that (G, v) and (H, w) not in pr (C&+I.10). Let (((1)) be formula in Ck+1 such that [ vlē * [ w Con- sider the formula sot ox1,...,,. = ((x1) A A [ = z4). Then, [pt jw,,,,.... "oo....,w)ll w)ll and hence (G,,.....,,)) and (H, (W,...,,,w)) w)) are not in Pa (C*+100) ei- ther. This implies that wil (e,...,))) # wil (H, (w....,,)) w)), and thus, by definition, u) A vwlk (H, w). In other words, v) and (H, w) are not in pi (vwl)). from which the inclusion pI (wwl)) E (I(C++latt follows. Conversely, if (G,e) and (H,w) are not in PI( (Vw!)")) then wll (v,...,)) # w/ (H, (w,...,,u ,w). As a consequence, (G, (e...., u)) and (H, (w..... w)) are not in pa (C either. Let (( xxx) be formula in Ck+1,00 such that lip, (w...., e * Ip, (w..... w)]B. Then it readily shown that into a formula yp (21) in Ck+ such that "ul # Ip_ ww H. not in A1 (C*+1.0). Hence, we also have the inclusion p1 (vwll)) 2 p first identity in (2) follows.
convert (ozr),.... ..I and thus (G, and (H, w) are p (C++110), form which the
remains to show Po (C++I)(++)) S. Po (gwllt))) S. Po (C Clearly, if (G, H) not in Po (gwl(() then the multisets of labels wi ( v) and (H, w) differ. It is known that with each label c one can associate a formula fo in C++0 such that "ipp,,l3 T if and only if ( v)
(G, c. So, if the multisets are different, there must be a e that occurs more often in one multiset than in the other one. This can be detected by fomulae of the form 3=m (11,((x1...................... 3rk )xx))² (2i,....... ..k) which is satisfied there are m tuples a with label c. It is now easily verified that the latter formula can be converted into a formula in ((++), Hence, the inclusion Po (C**+1.(0+4))) S po (gwl()) follows.
For Po (gwl(!) S. Po (C) we show that if (G, H) is in (oggl("), then this implics that Tp,,1l = Ml for all formulae in Ck+11((++) and any valuation (notice that f is superfluous in this definition when formulas have no free variables). Assume that (G. H) is in po po(gwlg). Since any formula of quantifier rank t+ 1 is a Boolean combination of formulas of less rank or formula of the form & 32"',;; x; & where & is of quantifier rank f, without loss of generality consider formula of the latter form, and assume for the sake of contradiction that [1 = T but [ al I. Since [|p n = T, there must be at least m elements satisfying vb. More precisely, let uI.... Up in G be all vertices in G such that for each valuation yaæx + 0z] holds that [V. M[x + v/18 = T. As mentioned, it must be that p is at least m. Using again the fact that pa (wl = pa (C++1.ll), we
infer that the color wi(e-1) (G, (U....., (U.....,;;)) U.)) is the same, for each such v,.
Now since gwl gwi(-") (G) = gwi (t-1) 1) (H), it is not difficult to see that there must be exactly ver- tices Wi,... , Wp in H such that w/ (t (G, (v..... v4)) = w/ wi(t-1)( (H, (w, w:)). Otherwise, would simply not be the case that the aggregation step of the colors, assigned by k-WL is the same
in G and H. By the connection to logic, we again know that for valuation ju[z + wy] it holds that
[W plz + w. 2 T. It then follows that [p, 1 T for any valuation μ4, which was to be shown.
Finally, we remark that po (gw)(oo) po (C++1) follows from the preceding inclusions in (2). 1
17

---

Published as a conference paper at ICLR 2022
Before moving to tensor languages, where we will use infinitary logies to simulate expressions in (22 and (TL, we recall that, when considering the separation power of logics, we can freely move between the logics and their infinitary counterparts:
Theorem C.2. The following identities hold for any t 2 0, k 2 2 and 2 0:
(1) pi (GC p1 (GC
(2) Pa (Chal)) = =p (C...t))).
Proof. For identity (1), notice that only need to prove that p1 (GC S P1 (GC ( the other direction follows directly from the definition. We point out the well-known fact that two tuples vG,v) and (H, w) belong to #i (GC if and only if the unravelling of G rooted at up depth / is isomorphic to the unravelling of H rooted at to up to root I. Here the unravelling is the infinite tree whose root the root node, and whose children are the neighbors of the root node (see e.g. Barceló et al. (2020); Otto (2019). Now for the connection with infinitary logic. Assume that the unravellings of G rooted u and of H rooted at w up to level are isomorphic. but assume for the sake of contradiction that there is a formula (ox)) in GC such that Melg * [p,, Hwll where Me and Me are any valuation mapping variable x to and w. respectively. Now since G and H are finite graphs, one can construct, from formula d, formula ø' in GC such that [v>, nu.1e & [t), Pno I Notice that this is in contradiction with our assumption that unravellings where isomorphic and therefore indistinguishable by formulae in GC To construct th, consider an infinitary disjunction VacA Og. Since G and H have a finite number of vertices, and the formulac have a finite number of variables, the number of different valuations from the variables to the vertices in G or H is also finite. Thus, one can replace any extra copy of at. Oge' such that their value is the same in G and H. The final result is finite disjunction, and the truth value over G and H/ is equivalent the original infinitary disjunction.
HH-
For identity (2) we refer Corollary 2.4 in Otto (2017).
C.3 FROM (L) TO C.e AND GCoow
We are now finally ready to make the connection between expressions in TL(S2) and the infinitary logics introduced earlier.
Proposition C.3. For any expression (px)) in TL (Q) and e E E. there exists an expression (x) in C such that [p, vla = e if and only [ 2 TT for any graph G [VG.Ec. colG) in G and v E Vb. Furthermore, if ((x) E (T2( then 5 GCoow Finally, if o has summation depth t then & has quantifier rank t.
Proof. We define 6 inductively on the structure of expressions in TL2(2).
p(x;, = 1g, op-, Assume first that op is "_", We distinguish between (a) i / j and (b) i = j. For case (a), if = 1, then we define & (2,, == (z, = =2)). if c = 0, then we define 6 (z;, xr)) = -(x; = xÿ), ), and if o 0, 1, then we define ( ..)) = x, * di- For case (b), if
then we define (xi, 2z) == (x; xz), and for any e + 1, we
define 6d (x, 2z) == -(x; = I.).. The case when op is "*" is treated analogously.
p(xx) Pe(x)). If c = 1, then we define @ (ax) == Pr( if = O. then we define $ (xx) = -P,(.)) For all other c, we define (x1, == - (1; = xz).
x,), = E(x,, m.). If = 1, then we define s (s,, xz) := E(s,, xz), c = 0, then we define 60 (z,, 21) == -E(,, 2,). For all other e, we define 47' (Z, == -(x; 2.).
= 91 + 42. We observe that [lp, v|c = if and only if there are ci C2 E RR such that [11, u ci and [| U/c C2 and C1 c2. Hence, it suffices to define
$ A 35
CLR 6= tCa
18

---

Published as a conference paper at ICLR 2022
where pi and 622 are the expressions such that [p1, vlc c1 if and only if lPf : T and [f2, e|e 02 if and only if [ v T, which exist by induction.
Indeed, Ip. vla if and only if there are c1, C2 E such that [41, = c1 and [,2, vIc = 02 and c = c1 C2. Hence, it suffices to define
+p := (0 P2- This is case is analogous to the previous
V C1.62ER em01102
F AAA
yp == a 9I.
P1. This is case is again dealt with similar way. Indeed, [|p, = if and only if there is a IR such that [&,, vla and cr. Hence, it suffices define
41
C1 ER
p = f(P,,... Pp) with f R2 + R. We observe that v/c if and only if there are Ci...., Cp E R such that f(c....., cp) and [P ele c; for i [p]. Hence, it suffices to define
V
67 A. 5r
p Ex, 91. We observe that pp. implies that we can partition Va into parts Vi...,, Ve, of sizes mi, mi....; me, respectively, such that (pl, - e|]G = c for each U E V,, and such that all c s are pairwise distinct and Ein G my, It now suffices to consider the following formula
th x. 89
Vr,
M. G1 PE c= myds
where 3 x, vp is shorthand notation for 32 xz -2 2, s. and Vx; denotes -321 24 mab.
This concludes the construction of G We observe that we only introduce quantifiers when ip Σx, iP1 and hence if we assume by induction that summation depth and quantifier rank are in sync, then if i has summation depth - 1 and thus eी has quantifier rank for any then oo has summation depth f, and as can be seen from the definition of 6o, this formula has quantifier rank t, as desired.
It remains to verify the claim about guarded expressions. This is again verified by induction. The only case requiring some attention sp(x1) := -.n, E(11, A yi (222) for which we can define
3 2(0 A 3
(
MNEN
my
which is a formula in GC again only adding one to the quantifier rank of the formulac की for e E. So also here, we have the one-to-one correspondence between summation depth and quantifier rank.
C.4 PROOF OF THEOREM 4.1, 4.2, 4.3 AND 4.4
Proposition C.4. We have the following inclusions: For any 2 0 and any collection of functions:
(cr(o) C 01 (GTL
19

---

Published as a conference paper at ICLR 2022
(vwwl S p1 (TL++1 and
po(l S po (TL k+1 (S)).
(H+1)
Proof. We first show the second bullet by contraposition. That is, we show that (G, u) and (H, w) are not in P1 (TL k+1 (22),, then neither are they in P1 (vwl))) Indeed, suppose that there exists an expression (((1)) in + (52) such that [[p, vlc c + c' [p, w|# From Proposition C.3 and [8 w| L. Hence, (G, v) and (H, w) do no belong to P1 ((tt) Theorem C.2 implies that (G, v) and (H, w) also do not belong to p1 (C* Finally, Proposition C.I implies that (G, v) and (H, w) do not belong to P1 (v as desired. The third bullet is shown in precisely the same, but using the identities for Pu rather than Pl, and gwl." rather than vw
know that there exists a formula & in Ck+ such that [ _el:
Also the first bullet is shown in the same way, using the connection between GTL GC GC and cr"), given by Proposition C.1, Theorem C.2, and Proposition C.3.
oow>
We next show that our tensor languages are also more separating than the color refinement and k-dimensional Weisfeiler-Leman algorithms.
Proposition C.5. We have the following inclusions: For any 2 0 and any collection St of functions:
pi (GTL (GTL)(())) C pi(c""));
(TL k+1 (1)) S pı (vwll and
Po (t+ (1)) Po (gwl
Proof. For any of these inclusions to hold, for any Ω need to show the inclusion without the use of any functions. We again use the connections between the color refinement and k-dimensional Weisfeiler-Leman algorithms and finite variable logies stated in Proposition C.I. More precisely,
we show for any formula ()x) E Ck.lt) there exists an expression (0xx) E TL (b) such that for any
graph G in G. [v, v = T implies 18, v]c = 1 and I,, v] = 1 implies [ vlc = 0. By appropriately selecting and and by observing that when (z()) GC then (xx) GTL, the inclusions follow.
The construction of ((x) is by induction on the structure of formulae in C*
x = (x; = =.)) Then, we define + := 1 1x
p == (z(.). Then, we define + = P=(x)).
P E(x,, r.). Then, we define 3 = E(xi, 25).
x P1. Then, we define > == 1u,=0; 61
x 1 422 Then, we define +p = Φ 122
: := 32m (21. Consider polynomial p(x)= = E, ajod such that p(x) for x 1, m - 1} and p(x) = for x E (m, m + I,....n) Such a polynomial exists by interpolation. Then, we define : = E, a (Ex, 21)"
We remark that we here crucially rely on the assumption that G contains graphs of fixed size n and that TL; is closed under linear combinations and product. Clearly, if &p E GC, then the above translations results in an expression E GTL( Furthermore, the quantifier rank of to is in one- to-one correspondence to the summation depth of G.
We can now apply Proposition C.I. That is, if (G, v) and (H, w) are not in Pi (cr then by Proposi- tion C.I, there exists formula (zx) in GC such that [4, v/8 T # [ip B L. We have just shown when consider G, in GTL also [ rle # [ w| holds. Hence, (G, u) and (H,
20

---

Published as a conference paper at ICLR 2022
not in P1 (S)) either, for any Ω. Hence. P1 (GTL S P1 (crl)) holds. The other bullets are shown in the same way, again by relying on Proposition C.I and using that we can move from vwlf and gwlg logical formulae, and to expressions in TL and TL TL respectively, to separate v) from (H, w) or G from H, respectively.
((+k)
Theorems 4.1, 4.2, 4.3 and 4.4 now follow directly from Propositions C.4 and C.3.
C.5 OTHER AGGREGATION FUNCTIONS
As is mentioned in the main paper, our upper bound results on the separation power of tensor lan- guages (and hence also of GNNs represented in those languages) generalize easily when other ag- gregation functions than summation are used in TL expressions.
To clarify what we understand by an aggregation function, let us first recall the semantics of summation aggregation. Let o Ex, (f1. where Σx, represents summation aggregation, let
G (Va, Eg, colg) graph, and let be a valuation assigning index variables vertices Vg- The semantics is then given by: 1Σ,, Pr, == Eveva IPI. v/2; + vllo.
explained in Section 3. Semantically, can alternatively view Ex, 91 function which takes the sum of the elements in the following multiset of real values:
1I1,, e|la VGl).
One can now consider, more generally, an aggregation function as a function which assigns to any multiset of values in R single real value. For example, F could be max, min, mean, ... Let be such a collection of aggregation functions. We next incorporate general aggregation function in tensor language.
First, we extend the syntax of expressions in TL(22) by generalizing the construct Σx, in the grammar of TL(22) expression. More precisely, we define TL(2, θ) as the class of expressions, formed just like tensor language expressions, but in which two additional constructs, unconditional and conditional aggregation, are allowed. For an aggregation function F we define:
aggr 2, (v) and aggr.,, (x(x;) ((x,,,;))
where in the latter construct (conditional aggregation) the expression pızz) represents a TL(2, θ) expression whose only free variable is 2y. The intuition behind these constructs is that uncondi- tional aggregation aggr," (i) allows for aggregating, using aggregate function F, over the values of where æi ranges unconditionally over all vertices in the graph. In contrast, for conditional aggre- gation aggr F m; (P((;) F(I;,,))) aggregation by F of the values of ()(r)) is conditioned on the neighbors of the vertex assigned to 2;. That is, the vertices for x, range only among the neighbors of the vertex assigned 2..
More specifically, the semantics of the aggregation constructs is defined as follows:
[aggrr (4) vlc == (flle, v/a, + vila u E V&ll) R. [aggr,, (v(0;) ((1,, v]a F (tile, v(a, + v|la v E Vo, (M(Zz),u) E Eal)) IR.
We remark that we can also consider aggregations functions F over multisets of values in RR' for some l E N. This requires extending the syntax with aggri, n, (P1....,, for unconditional ag- gregation and with aggr,, F 2, (2.))...,ee()()) mantics is as expected: F(H(([p),,(z) + olla.... I.e. + vilc) | Voll) E R and F(H((Ie),,(z, + vllG..... 1/z, - vlle)
E(x;, for conditional aggregation. The se-
Vo. (v(z)), Eoll)
The need for considering conditional and unconditional aggregation separately is due to the use of arbitrary aggregation functions. Indeed, suppose that one uses an aggregation function F for which 0 E IR is neutral value. That is, for any multiset X of real values, the equality F(X)= = F(X)(()) holds. For example, the summation aggregation function satisfies this property. We then observe:
JaggrE, (y((7)) F((1, v/a F(lll,, + e]] o Vo, (u(x)), v) E Fall)
21

---

Published as a conference paper at ICLR 2022
FHIl E(r,, p/ay oll a Val)) laggr xj (p(zy) E 23) )) vlc..
In other words, unconditional aggregation can simulate conditional aggregation. In contrast, when is not neutral value of the aggregation function F, conditional and unconditional aggregation behave differently. Indeed, in such cases aggrz, F 2 (f(xz) E xz))) and aggr,, (f(xz)) E( 4,))
may evaluate to different values, as illustrated in the following example.
지 Ezex x for multisets X of real values. We remark that 0's in X contribute to the size of X and hence 0 not a neutral element of avg. Now, let us consider the expressions
As aggregation function we take the average (vg
(x;) aggr,, avE (Iz (((r, and (2(())) aggra, (1=z= (()))
2
Let y be such that (z;;) ) = Then, [f la results in applying the average to the multiset ff] f[-w= E(u, w) w E Vo]) which includes the value for every w (V(v) and a for every non- neighbor é Na(v). In other words, [[1 o/e results in [No(e))/VVal In contrast, [122 v|a results in applying the average to the multiset [[1==w | w E VG, (v, w) E Ec]]. In other words, this multiset only contains the value 1 for each w E Nv(v), ignoring any information about the non-neighbors of v. In other words, [[22, v]G results in and unconditional aggregation behave differently for the average aggregation function.
= 1. Hence, conditional
This said, one could alternative use a more general variant of conditional aggregation of the form aggr,, (pl()) with semantics Jaggr,, =; (fl1),, P/lG := F (fI[e, p/z; + e|]l v E Va, [t), v/zr eIa + 0}} where one creates a multiset only for those valuations v/2z - u) for which the condition evaluates a non-zero value. This general form of aggregation includes conditional aggregation, by replacing 1i with E(xs, 25) and restricting and unconditional aggregation, by replacing & with the constant function e.g.. 1zz=e;- In order not to overload the syntax of TL expressions, we will not discuss this general form of aggregation further.
The notion of free index variables for expressions in TL(2, Q) is defined as before, where now free((p) \\  {x,}, and where free(aggr", (f((2)) E(z;, zy)) {a;} (recall } conditional aggregation). Moreover, summation depth is replaced by the notion of aggregation depth, agd(pp), defined in the same way as summation depth except that Similarly, the fragments (S2 θ) and its aggregation depth restricted fragment TL Q) are defined as before, using aggregation depth rather than summation depth.
free(aggr") 23 (4))
that free(
(p(z)) free((p(z)))
F agd(aggr x, (4)) = agd(p) + 1 and agd(grgr (y((z)) ) ((I,,,,)) = agd((p)
For the guarded fragment, GTL(2,, θ), expressions are now restricted such that aggregations must occur only in the form aggrž, (I((z;) E(x,, 2;)), for i, E [2]. In other words, aggregation only happens on multisets of values obtained from neighboring vertices.
We now argue that our upper bound results on the separation power remain valid for the extension TL θ) of (S2) with arbitrary aggregation functions O
Proposition C.6. We have the following inclusions: For any 2 0, any collection Ω of functions and any collection @ of aggregation functions:
funcctiionnnnn
(i(cro)) Em (GTL (9,
(i(wll"") ( k+1 (2, 0)); and (++1) po(aw((") S Po (TL k+1 (2, 0))
Proof. It suffices to show that Proposition C.3 also holds for expressions in the fragments of TL(Ω2 θ) considered. In particular, we only need to revise the case of summation aggregation (that is, y = Σx, (Pi) in the proof of Proposition C.3. Indeed, let us consider the more general case when of the two aggregating functions are used.
22

---

Published as a conference paper at ICLR 2022
p aggrz, (191).
We then define
60 V
V
I2 Pi A
Va; or,
CEN (m.....,y))N (1) (m me. a=1
s=1
where C(m me, F) now consists of all (c, ......,,. ct) E RR+1
such that
F (He......
Ct..... ..................... C....,......
mi
me
Pp: aggr xz)). We then define
80 = V V
3 E(z
BEN (mi...E))EN (c. (m FR.
24 (Zz (x,)
where C(m), me, F`) again consists of all (c, C1 (,,...,, Ct) E Re+1 such that
F ((c1.....
Ce. Cl:-....e)) and m m,-
times
me
It is readily verified that [aggr (0), vla
iff 109000 1 = T. and [aggr F. (v((x;) E(z,, a|g iff 1 0/8 = T. desired.
For the guarded case, we note that the expression 6 above yields a guarded expression as long conditional aggregation is used of the form aggr. F (ggxt.( Ex),, with i, [2]. we reuse the argument in the proof of Proposition C.3 for the guarded case.
We will illustrate later on (Section D) that this generalization allows for assessing the separation power of GNNs that use a variety of aggregation functions.
The choice of supported aggregation functions has, of course, an impact on the ability of TL(2, θ) match color refinement or the k-WL procedures in separation power. The same holds for GNNs, as shown by Xu et al. (2019). And indeed, the proof of Proposition C.5 relies on the presence of summation aggregation. We note that most lower bounds on the separation power of GNNs in terms of color refinement or the k-WL procedures assume summation aggregation since summation suffices to construct injective sum-decomposable functions on multisets (Xu al., 2019: Zaheer et al., 2017), which are used to simulate color refinement and k-WL. A more in-depth analysis of lower bounding GNNs with less expressive aggregation functions, possibly using weaker versions of color refinement and k-WL is left as future work.
C.6 GENERALIZATION TO GRAPHS WITH REAL-VALUER VERTEX LABELS
We next consider the more general setting in which cole Vo + Re for some & E N. That is, vertices in graph can carry real-valued vectors. We remark that no changes to neither the syntax nor the semantics of TL expressions are needed, note that [P)(),, u/G == cola(v), is now an element R rather than or 1, for each s [f].
A first observation is that the color refinement and k-WL procedures treat each real value as separate label. That is, two values that differ only by any small e 0, are considered different. The proofs of Theorem 4.1, 4.2, 4.3 and 4.4 rely connections between color refinement and k-WL and the finite variable logics GC and C++1 respectively. In the discrete context, the unary predicates P. (z) used in the logical formulas indicate which label vertices have. That is, [P, T iff cola (v), = To accommodate for real values in the context of separation power, these logics now need be able to differentiate between different labels, that is, different real numbers. We therefore
23

---

Published as a conference paper at ICLR 2022
extend the unary predicates allowed in formulas. More precisely, for each dimension [e], now have uncountably many predicates of the form Pe.r, one for each r E R. In any formula in GC or C only finite number of such predicates may occur. The Boolean semantics of these new predicates is expected:
(a.r((),,IE3 == if colo(1();)); = then else 1.
In other words, in our logics, we can now detect which real-valued labels vertices have. Although, in general, the introduction of infinite predicates may cause problems, we here consider a specific setting in which the vertices in graph have unique label. This is commonly assumed in graph learning. Given this, easily verified that all results Section C.2 carry over, where all logics involved now use the unary predicates Pa,r with E [C] and E R.
The connection between TL and logics also carries over. First, for Proposition C.3 we now need to connect TL expressions, that use finite number of predicates P.. for [e], with the extended logics having uncountably many predicates Ps.r. for & [f] and r IR, at their disposal. It suffices to reconsider the case p(z,) (a,
3 in the proof of Proposition C.3. More precisely, [P, (x;), can now be an arbitrary value c E R. We now simply define (x,,) = (z,(( By definition [P.()),, v]a = if and only [P=,. vla = T, as desired.
The proof for the extended version of proposition C.5 now needs slightly different strategy, where we build the relevant TL formula after we construct the contrapositive of the Proposition. Let us first show how construct a TL formula that is equivalent logical formula any graph using only labels in a specific (finite) set R of real numbers.
In other words, given a set R of real values, we show that for any formula (xx) E Ck.(t) using unary predicates Par such that E R. we construct the desired @. As mentioned, we only need to reconsider the case (p(x;) = (Tz)) We define
+ =
II
(P.(2:) - r' ((12==)))
II E M'Rrrt
Then, [8, vla evaluates to
(r I =
[Pr. ul = T
0 [P / = =
Indeed, if [Pa,,, w/] = T, then cola(u), r and hence [Ps, u = r. resulting in the same nomi- nator and denominator in the above fraction. If [P 1, then cola(v), r for some value r' E R with * r'. In this case, the nominator in the above fraction becomes zero. We remark that this revised construction still results in a guarded TL expression, when the input logical formula is guarded as well.
Coming back to the proof of the extended version of Proposition C.5, let us show the proof for the the fact that P1 (GTL"(()) S Pı (cr'"), the other two items being analogous. Assume that there is a pair (G, v) and (H, w) which is not in Pi (cr().. Then, by Proposition C. applied on graphs with real-valued labels, there exists formula pz(x) in GC such that [4,, v] T [ia w J. We remark that (p()) uses finitely many Par predicates. Let R be the set of real values used in both G and /! (and (zx)). We note that
finite. We invoke the construction sketched above, and obtain formula e in GTL such that [ vlo [ w/ w. Hence, (G,v) and (H, w) is not in Pa (GTL (Q)) either, for any Ω which to be shown.
D DETAILS OF SECTION 5
We here provide some additional details on the encoding of layers of GNNs in our tensor languages, and how, consequence of our results from Section 4, one obtains bound their separation power. This section showcases that it is relatively straightforward to represent GNNs in our tensor languages. Indeed, often, direct translation of the layers, defined in the literature, suffices.
D.1 COLOR REFINEMENT
We start with GNN architectures related to color refinement, or in other words, architectures which can be represented in our guarded tensor language.
24

---

Published as a conference paper at ICLR 2022
GraphSage. We first consider "basic" GNN, that is, instance of GraphSage (Hamilton al., 2017) in which sum aggregation is used. The initial features are given by F (f1 ..... (ol where ft E Rnxi hot-one encoding of the vertex label in G. We can represent the ini- tial embedding easily in GTL without the use of any summation. Indeed, it suffices to define pp t (x1) := (x1) for E [do]. We have Futh [43 elc for j E [do]. and thus the initial features can be represented by simple expressions in GTL
Assume now, by induction, that we can also represent the features computed by basic GNN in layer - That is, let F(l1) E R_xde-1 be those features and for each i [dx-1] let u (211 be expressions GTL GTL"="(()) representing them. We assume that, for each E [dc-1]. Fi! F(t-1) [o ,Vla. We remark that we assume that summation depth of L 1 is needed for layer - 1.
Then, in layer i, basic GNN computes the next features
F :- a (Fit-1) v + A F W + B')),
where A E T is the adjacency matrix of G, V and W are weight matrices in Rdc-1xd, B E Raxdd is a (constant) bias matrix consist of n copies of h Rd,, and is some activation function. We can simply use the following expressions k) (z1). for [d]]:
Σ
of (x1) + Σg
E(01,12)
- (12)) + b9g 1.
Here, With with if and b/ are real values corresponding the weight matrices and bias vector in layer t. These are expressions in (r) since the additional summation is guarded, and combined with the summation depth of t - of oft-") this results in a summation depth of t for layer t. Furthermore, F = - ula, desired. If we denote by bGNN the class of t-layered basic GNNs, then our results imply
e (cr")) S Pi((GTL" S p (bGNN")),
and thus the separation power of basic GNNs is bounded by the separation power of color refinement. We thus recover known results by Xu et al. (2019) and Morris et al. (2019).
Furthermore, if one uses a readout layer in basic GNNs to obtain a graph embedding, one typically applies function
Rdd - Rd in the form of ro ro F.P), in which aggregation takes places over all vertices of the graph. This corresponds to an expression in TL ro): 93 :=
ro, (E., (21)). where roj is the projection of the readout function on the jthe coordinate. We note that this is indeed not a guarded expression anymore, and thus our results tell that
Po (gcr!") Po Po (TTLL++(()) (2)) C po (bGNN readout).
More generally. GraphSage allows for the use general aggregation functions F on the multiset of features of neighboring vertices. To cast the corresponding layers in TL(S2), we need to consider the extension TL2,2 θ) with an appropriate set @ of aggregation functions, as described in Section C.5. In this way, we can represent layer by means of the following expressions (/((x)) (x1), for j E [de]-
d=
de
vi
a p.
(x1))
Σ
aggr F. (
(v: ((I1, + 6 1 1m
which is now expression in GTL ((a), +) and hence the bound in terms of t iterations of color refinement carries over by Proposition C.6. Here, O simply consists of the aggregation functions used in the layers in GraphSage.
GCNs. Graph Convolution Networks (GCNs) (Kipf & Welling, 2017) operate alike basic GNNs except that a normalized Laplacian D 1-1/2(1 + D-D-1/2 used to aggregate features, instead of the adjacency matrix A. Here, D 1/2 is the diagonal matrix consisting of reciprocal of the square root of the vertex degrees in G plus 1. The initial embedding F is just before. We
25

---

Published as a conference paper at ICLR 2022
again de to denote the number of features in layer t. In layer t 0. GCN computes F a (D-1/22(1 D- F + BO)). If, in addition to the activation function o we add + va+1 to Q, we can represent the GCN layer, as follows. For v=+1 expressions
the function Vz+1 R
j E [de], we define the GTL
(x1) = ( (AIVETT (211
Σ W up
(x1))
f1/ f1/va41
Σ ((11122))
+ +11/==11 E(11, 22))
Σ
E(r1, f1/
E(12,
Wilh :p (12))
322
22
where we omitted the bias vector for simplicity. We again observe that only guarded summations are needed. However, we remark that in every layer now add two the overall summation depth, since we need an extra summation to compute the degrees. In other words, a t-layered GCN correspond to expressions in GTL22 (a, Vx+1/ ). we denote by GCN the class of L-layered GCNs, then our results imply
P1 Pi (cr(22) S pz (IGTL S P1 (GCN")).
We remark that another representation can be provided, in which the degree computation is factored out (Geerts et al., 2021a), resulting in better upper bound p1 (cr(t+)) S pi (GCN'"). In a similar way as for basic GNNs, also have po (gcr(t+)) S (GCGC readout).
SGCs. As an other example, we consider a variation of Simple Graph Convolutions (SGCs) (Wu al., 2019), which use powers the adjacency matrix and only apply a non-linear activation function at the end. That is, F := oAA". F W) for some p E N and W E xdd, We remark that SGCs actually use powers of the normalized Laplacian, that is, F := o ((D 1/2 (I + AG) 1-/3)) F W) but this only incurs an additional summation depth as for GCNs. We focus here on our simpler version. It should be clear that we can represent the architecture in TLP) T (12) by means of the expressions:
(x1)
Σ
Σ Zpti
II ((EL)
Wis pp (eptt))
for j [d1]. A naive application of our results would imply upper bound their separation power by p-WL. We can, however, use Proposition 4.5. Indeed, it is readily verified that these expressions have treewidth of one, because the variables form path. And indeed, when for example, = 3, we can equivalently write 50 (x1)
as
do
Σ E(11,22) 22)
21) ) (E E((r,,
W.y
1 (122))
by reordering the summations and reusing index variables. This holds for arbitrary p. We thus obtain guarded expressions in (a) and our results tell that t-layered SGCs are bounded by cr for vertex embeddings, and by gcr(") for SGCs + readout.
Principal Neighbourhood Aggregation. Our next example is GNN in which different aggrega- tion functions are used: Principal Neighborhood Aggregation (PNA) is an architecture proposed by Corso et al. (2020) in which aggregation over neighboring vertices is done by means of mean, stdv, max and min, and this in parallel. In addition, after aggregation, three different scalers are applied. Scalers diagonal matrices whose diagonal entries are function of the vertex degrees. Given the features for each vertex V computed in layer - 1, that is, F E gxxe a PNA computes v's new features in layer t in the following way (see layer definition (8) in (Corso et al., 2020)). First, vectors G E R X48 are computed such that
mean (fmlp, (FX-1))
w E No(u)B)
for Sisl for f fff+1jj222
stdv (Hmmp, (Fit- -)
w e No(e)B)
max (((mlp, (FFt-1)) 1)) w No(c)
for 2 i
min (ffmlp (F (Fut-D)
w e No(x)B)
for 3 +1 46,
26

---

Published as a conference paper at ICLR 2022
where mlp, RR' R is the projection of an MLP mlp R' R' the jth coordinate. Then, three different scalers are applied. The first scaler is simply the identity, the second two scalers $1 and 82 depend on the vertex degrees. As such, vectors a R 12c are constructed follows:
for 1 S 48
$1 (i (v))
H Hit
for 4 S 88 for 8e + J I 126,
82 $2(dega
where 81 and 82 functions from R IR (see (Corso al., 2020) for details). Finally, the new vertex embedding is obtained as
F m (H
for some MLP mlp': : RIZ + R The above layer definition translates naturally into expressions in TL( +), the extension of (L()) with aggregate functions (Section C.S). Indeed, suppose that for each [4] we have TL(22, Q) expressions o0) (x)" such that [pp)",, .ll 1oj for any vertex v. Then, Gi simply corresponds to the guarded expressions
(9 (x1) =- aggr.. (marr
(mlp, ( (22)..... (122) E(I1,
for S S and similarly for the other components of G using the respective aggregation functions, stdv, max and min. Then, H corresponds to
( $1 (aggrr sum $2(aggr
for S 48
clt 9 (x1)
(1 P
E(a1, (m1) 1my= ((21,
for 4/ + + S 88
sum
1 (ai)
for Sf S S 122,
m2
where we use summation aggregation to compute the degree information used in the functions in the scalers $1 and $2. And finally,
:= = (51
Ste (x1))
represents prth We see that all expressions only use two index variables and aggregation is applied in guarded way. Furthermore, in each layer, the aggregation depth increases with one. As such, a t-layered PNA can be represented in CTL (2, θ), where consists of the MLPs and functions used in scalers, and @ consists of sum (for computing vertex degrees), and mean, stdv, max and min. Proposition C.6 then implies a bound on the separation power by cr!")
Other example. In the same way, show that these can be represented in GTL(S?) as well, and thus bounds by color refinement can be obtained.
also easily analyze GATs (Velickovic al., 2018) and
D.2 À-DIMENSIONAL WEISFEILER-LEEME TESTS
We next discuss architectures related to the k-dimensional Weisfeiler-Leman algorithms. For t = 1, we discussed the extended GINs in the main paper. We here focus on arbitrary 2.
We first consider the "Folklore" GNNs or k-FGNNs for short (Maron et al., 2019b). For & 2, k-FGNNs computes a tensors. particular, the initial tensor F encodes atp, (G, v) for each v Vt. We can represent this tensor by the following 2 2) expressions in T
Folklore GNNs.
for j E [6] 1,,=,, (p)))) E(Ir,
p (#1...., Ix) (+x== =
for j = f 1,
for j = f f+ 2 for r, [k] and j E + 2]. We note: I (U1,..., Ua FO) [x]2 [e+ 2]. as desired. We let To = [A]2 [e and set dg 22 (l (1+
1z,=x,
v.....u..r. for all (r,s.)
Then, in layer f, k-FGNN computes a tensor
P1 mlp ( U2....
Σ
II
mlp
((1-1)
we s=1
27

---

Published as a conference paper at ICLR 2022
where mlp!' R + Rd, for E [k], and and mlp? R + Rd are MLPs. We here use to denote combinations of indices in Ta for FO and in Td-1 for F(t11)
Let F(-1) E R=*xxe- be the tensor computed by an k-FGNN in layer L 1. Assume
that for each tuple of elements j in Td,-1 we have an expression sy 10-"((a (#1, (.1.....:. .......... .*k satisfying [p (ag....,,4)ee.
F(-))) " and such that it is an expression in T That is,
need k + 1 index variables and a summation depth of - 1 to represent layer t- 1.
Then, for layer for each j E Td, suffices to consider the expression
1 , 2R) = mlpo' ((v) ft-
(2), (ZI, 1E.,..,; xx4) SETA,_."
Σ 2k+1
th (10) (fr,,..., Ts- 1.. 2.41, ml
Ix)) SEre, )),
where mlp%. and mip?? are the projections of the MLPs on the j-coordinates. We remark that we need & + index variables, and one extra summation needed. We thus obtain expressions in TL 1 (St) for the ith layer, desired. We remark that the expressions are simple translations of the defining layer definitions. Also, in this case, Ω consists of all MLPs. When a k-FGNN is used for vertex embeddings, we now simply add to each expression factor I lam=a, As an immediate consequence of our results, if denote by k-FGNN the class of t-layered k-FGNNs, then for vertex embeddings:
Pi (vwlk) S pi (TL2 E P (K-FGNN
in accordance with the known results from Azizian & Lelarge (2021). When used for graph embed- dings, an aggregation layer over all k-tuples of vertices is added, followed by the application of an MLP. This results in expressions with no free index variables, and of summation depth / + k; where the increase with l stems from the aggregation process over k-mples. In view of our results, for graph embeddings:
Po (gwl! S (0(TLR+1(2)) S (o(kFFGNN)
in accordance again with Azizian & Lelarge (2021). We here emphasize that the upper bounds in terms of k-WL are obtained without the need to know how k-WL works. Indeed, one can really just focus on casting layers in the right tensor language!
We remark that Azizian & Lelarge (2021) define vertex embedding k-FGNNs in different way. Indeed, for a vertex v, its embedding is obtained by aggregating of all (A: (k- tuples in the remaining coordinates of the tensors. They define vwl, accordingly. From the tensor language point of view, the summation depth. Our results indicate that we loose
this corresponds the addition of k: the connection between rounds and layers, as in Azizian & Lelarge (2021). This is the reason why we defined vertex embedding k-FGNNs in a different way and can ensure correspondence between rounds and layers for vertex embeddings.
Other higher-order examples. It is readily verified that t-layered k-GNNs (Morris et al., 2019) be represented in TL (S2), recovering the known upper bound by vw (Morris al., 2019). is an equally easy exercise to show that 2-WL-convolutions (Damke et al., 2020) and Ring-GNNs (Chen al., 2019) are bounded by 2-WL, by simply writing their layers in TL2( The invariant graph networks (k-IGNs) (Maron et al., 2019b) will be treated in Section E, as their representation TL++1(2)) requires some work.
D.3 AUGMENTED GNNS
Higher-order GNN architectures such as k-GNNs, k-FGNNs and k-IGNs, incur substantial cost in terms of memory and computation (Morris et al., 2020). Some recent proposals infuse more efficient GNNs with higher-order information by means of some pre-processing step. We next show that the tensor language approach also enables to obtain upper bounds on the separation power of such "augmented" GNNs.
We first F-MPNNs (Barceló et al., 2021) in which the initial vertex features are augmented with homomorphism counts of rooted graph patterns. More precisely, let pr be connected rooted
28

---

Published as a conference paper at ICLR 2022
graph (with root vertex r), and consider graph G = (Vc, Eg, colg) and vertex E VG. Then, hom ,G)) denotes the number of homomorphism from P to G. mapping r to V. We recall that homomorphism is tnge-rreeerving mapping between vertex sets. Given collection F . of rooted patterns, an F-MPNN runs an MPNN on the augmented initial vertex features:
M Now, take any GNN architecture that can be cast in GTL( or TL2(2) and assume, for simplicity of exposition, that a t-layer GNN corresponds to expressions in GTL(((S) or (1). In order to analyze the impact of the augmented features, one only needs to revise the expressions 4) (z1) that represent the initial features. In the absence of graph patterns, (x1) == P3( we have seen before. By contrast, to represent ( we need to cast the computation of hom(??, C G*) in TL. Assume that the graph pattern P. consists of p vertices and let us identify the vertex set with [p]. Furthermore, without of loss generality, we assume that vertex "1" is the root vertex P.. To obtain hom( PT, G*) we need to create an indicator function for the graph pattern P: and then count how many times this indicator value is equal to one in G. The indicator function for P. is simply given by the expression LuveEE, El Zo). Then, counting just pours down to summation over all index variables except the one for the root vertex. More precisely, if we define
F = (F es hom(P", ("),
(1)) = -. II
By WEEEn
then "Ie hom(P; PT G.). This encoding results in expression in TLp. However, it is well-known that we can equivalently write şp, (21) as an expression Gp, (21) in TLx+1 where is the treewidth of the graph P. As such, our results imply that F-MPNNs are bounded in separation power by k-WL where k is the maximal treewidth of graphs in F. We thus recover the known upper bound as given in Barceló et al. (2021) using our tensor language approach.
Another example of augmented GNN architectures are the Graph Substructure Networks (GSNs) (Bouritsas et al., 2020). By contrast J-MPNNs, subgraph isomorphism counts rather than ho- momorphism counts are used to augment the initial features. At the core of a GSN thus lies the computation of sub P",, G)),, the number of subgraphs H in G isomorphic to P (and such that the isomorphisms map to v). In a similar way as for homomorphisms counts, we can either directly cast the computation of sub(P", G") in TL resulting again in the use p index variables. A possible reduction in terms of index variables, however, can be obtained by relying on the result (Theorem 1.1.) by Curticapean et al. (2017) in which shown that sub(P" (PP G") can be computed in terms of homomorphism counts of graph patterns derived from pr. More precisely, Curticapean et al. (2017) define spasm(P") as the set of graphs consisting of all possible homomorphic images of Pr. It is then readily verified that if the maximal treewidth of the graphs in spasm (P)) is k. then sub(P", ,G) can be cast as an expression in TL Hence, GSNs using a pattern collection F can be represented in TL where k is the maximal treewidth of graphs in any of the spams of patterns in F, and thus are bounded in separation power k-WL in accordance to the results by Barceló et al. (2021).
As a final example, we consider the recently introduced Message Passing Simplicial Networks (MPSNs) (Bodnar al., 2021). In a nutshell, MPSNs are run on simplicial complexes of graphs instead of on the original graphs. We sketch how our tensor language approach can be used to assess the separation power of MPSNs on clique complexes. We use the simplified version of MPSNs which have the same expressive power as the full version of MPSNs (Theorem 6 in Bodnar et al. (2021)).
We recall some definitions. Let (Giques(G)) denote the set of all cliques in G. Given two cliques e and c' in Cliques(G), define < c' if e C e' and there exists no c" in Cliques(G). such that C d' cd. We define Boundary(c, G) == {e' E Cliques(G) d' < c) and Upper(c, G) {c' e
Cliques(G)) 3e" E Cliques(G), < c" and e X c").
For each e in Cliques(G) we have an initial feature vector F E Rixt_ Bodnar et al. (2021) initialize all initial features with the same value. Then, in layer i, for each e E (G) features
are updated as follows:
G Fa(((mpp (1 Fu-")) | c' Boundary(C,c))))
29

---

Published as a conference paper at ICLR 2022
H (f(plp (F Fur" Falet) | E Upper(G. c)
F mlp(F F G
where FB and Fy are aggregation functions and mlpg. mlpy and mlp are MLPs. With some effort, one can represent these computations by expressions in (L, θ) where is largest clique in G. As such, the separation power of clique-complex MPSNs on graphs of clique size at most p is bounded by p - 1-WL. And indeed, Bodnar et al. (2021) consider Rook's 4 x 4 graph, which contains a 4-clique, and the Shirkhande graph, which does not contain 4-clique. As such, the analysis above implies that clique-complex MPSNs are bounded by 2-WL on the Shrikhande graph, and by 3-WL on Rook's 's graph, consistent with the observation in Bodnar al. (2021). A more detailed analysis of MPSNs in terms of summation depth and for other simplicial complexes is left as future work.
This illustrates again that our approach can be used assess the separation power of variety of GNN architectures in terms of k-WL, by simply writing them as tensor language expressions. Furthermore, bounds in terms of k-WL can be used for augmented GNNs which form more efficient way of incorporating higher-order graph structural information than higher-order GNNs.
D.4 SPECTRAL GNNS
In general, spectral GNNs are defined in terms of eigenvectors and eigenvalues of the (normal- ized) graph Laplacian (Bruna al., 2014; Defferrard et al., 2016; Levie al., 2019; Balcilar al., 2021b)). The diagonalization of the graph Laplacian is. however, avoided in practice, due to its excessive cost. Instead, by relying on approximation results in spectral graph analysis (Hammond et al., 2011), the layers of practical spectral GNNs are defined in term propagation matrices consist- ing of functions, which operate directly on the graph Laplacian. This viewpoint allows for a spectral analysis of spectral and "spatial" GNNs in uniform way, as shown by Balcilar et al. (2021b). In this section, we consider two specific instances of spectral GNNs: ChebNet (Defferrard et al., 2016) and CayleyNet (Levie et al., 2019), and assess their separation power in terms of tensor logic. Our general results then provide bounds on their separation power in terms color refinement and 2-WL, respectively.
Chebnet. The separation power of ChebNet (Defferrard et al., 2016) was already analyzed in Balcilar et al. (2021a) by representing them in the MATLANG matrix query language (Brijder al., 2019). It was shown (Theorem 2 (Balcilar et al., 2021a)) that it is only the maximal eigenvalue Amax of the graph Laplacian used in the layers of ChebNet that may result in the separation power of ChebNet to go beyond 1-WL. We here revisit and refine this result by showing that, when ignoring the use of Amax. the separation power of Chebnet is bounded already by color refinement (which, as mentioned in Section 2, is weaker than 1-WL for vertex embeddings). In a nutshell, the layers of a ChebNet are defined in terms of Chebyshev polynomials of the normalized Laplacian L = D-1/2.
D 1122 and these polynomials can be easily represented in GTL( One can alternatively use the graph Laplacian L D A in ChebNet, which allows for a similar analysis. The distinction between the choice of Lnom and L only shows in the needed summation depth (in as in similar way as for the GCNs described earlier). We only consider the normalized Laplacian here.
More precisely, following Balcilar et al. (2021a;b), in layer t, vertex embeddings are updated in a ChebNet according to:
p Σ
c()) F(t-1), wil-
F(t)
with
2 L I, 1.((0) 2((2) c(s-1) c(8-2), for 8 2 3,
(1)1) : C,
Amax
and where Amax denotes the maximum eigenvalue Lnoem- We next use a similar analysis as in Balcilar et al. (2021a). That is, we ignore for the moment the maximal eigenvalue Amax and redefine (2) as c. - I for some constant We thus see that each (+(s) is polynomial of the form (c, Lnom) Ei= a; (c) (Lnomm) with scalar functions af R + R and where we interpret (Lmom)) I. To upper bound the separation power using our tensor language approach,
30

---

Published as a conference paper at ICLR 2022
thus shift our attention entirely to representing (Luom) F(t-1). ((-11,9) for powers i N. Furthermore, since nonom)) is again polynomial of the form q: ( 1/2 A.D 1D21)
L big (D-1/2, A. D 0-1/2/0, we can further narrow down the problem to represent
D 1/2 A. D 1/2 F ((-11,>)
in GTL( for powers j E N. And indeed, combining our analysis for GCNs and SGCs results in expressions in GTL( As example let us consider (D-1/2. A D-1/2)2. F(t-1), W((+1) that is we use a power of two. It then suffices to define, for each output dimension j, the expressions:
03((1) -ii/va 2()1, Exs 2(21, f1/2
(E(a) (,,
En, (E(x,,01) Luv (2)1 (EiT W (t- (x (mi)))
where the - (((-1)(x)) (x1) are expressions representing layer t - 1. It is then readily verified that we can use 4/ (x11 to cast layer of a ChebNet in GTL((2) with l consisting of f1/V= IR + R z + V
fi/z : R - : x + I. and the used activation function a. We thus recover (and slightly refine) Theorem 2 in Balcilar et al. (2021a):
Corollary D.1. On graphs sharing the same Xmax values, the separation power of ChebNet is bounded by color refinement, both for graph and vertex embeddings.
A more fine- the-grained analysis of the expressions is needed when interested in bounding the sum- mation depth and thus of the number of rounds needed for color refinement. Moreover, as shown by Balcilar et al. (2021a), when graphs have non-regular components with different Amax values, ChebNet can distinguish them, whilst 1-WL cannot. To our knowledge, Amax cannot be computed in (S2) for any k. This implies that it not clear whether an upper bound on the separation power can be obtained for ChebNet taking Amax into account. It is an interesting open question whether there are two graphs G and H which cannot be distinguished by k-WL but can be distinguished based on Amax A positive answer would imply that the computation of Amax is beyond reach for (S2) and other techniques are needed.
CayleyNet. We next show how the separation power of CayleyNet (Levie al.. 2019) can be analyzed. To our knowledge, this analysis is new. We show that the separation power of CayleyNet is bounded by 2-WL. Following Levie al. (2019) and Balcilar al. (2021b), in each layer t, CayleyNet updates features as follows:
P Σ c(o). p(t-1
FO0
with
(())= ;- 11 = Re
hL + (
((2e+1) ;= Re
hL +
where constant, is the imaginary unit, and Re : C - C maps a complex number to its real part. We immediately observe that CayleyNet requires the of complex numbers and matrix inversion. So far, we considered real numbers only, but when our separation results are concerned, the choice between real complex numbers is insignificant. In fact, only the proof of Proposition C.3 requires a minor modification when working on complex numbers: the infinite disjunctions used in the proof now need to range over complex numbers. For matrix inversion, when dealing with separation power, one can use different expressions in TL(2) for computing the matrix inverse, depending on the input size. And indeed, it is well-known (see e.g., Csanky (1976) that based on the characteristic polynomial of A, A for any matrix A E p can be computed as polynomial -1 Σ An-1i if en + 0 and where each coefficient is polynomial in tr( (r(A),, Cn for various j. Here, tr(-) is the trace of matrix. As consequence, layers in CayleyNet can be viewed as polynomials in hL - aI with coefficients polynomials in tr((hL =I)"). One now needs three index variables to represent the trace computations tr( -II'). Indeed, let (o((1,, 222) be
31

---

Published as a conference paper at ICLR 2022
the TL2 expression representing h. .I. Then, for example, (hL =f)² can be computed in TL3 using
Py (z 22) = Σ (o((x1 x3) (jj (23.
and hence expressions in TLy. The polynomials in h. aI can be represented in TLy just for ChebNet. This implies that each layer in CayleyNet can be represented, on graphs of fixed size, by TLa( expressions, where 52 includes the activation function and the function Re. This suffices our general results and conclude that CayleyNets are bounded in separation power by 2-WL. An interesting question is find graphs that can be separated by CayleyNet but not by 1-WL. We leave this as an open problem.
is represented by Σ Ex, My (01: x22) (
=z,= In other words, we obtain
E PROOF OF THEOREM 5.1
We here consider another higher-order GNN proposal: the invariant graph networks or k-IGNs of Maron et al. (2019b). By contrast to k-FGNNs, k-IGNs are linear architectures. we denote by k-IGN( the class of layered k-IGNs, then following inclusions are known (Maron et al., 2019b)
Pi (K-IGN"*) S pi (vw((2)) and Po (k-IGN) S (o(gl
The reverse inclusions were posed as open problems Maron et al. (2019a) and were shown to hold by Chen et al. (2020) for k = 2. by means of an extensive case analysis and by relying properties of 1-WL. In this section, we show that the separation power of k-IGNs is bounded by that of (A: 1)-WL. for arbitrary & 2. Theorem 4.2 tells that we entirely shift attention to showing that the layers of k--GNNs can be represented in TLx (2). In other words, we only need to show that & index variables needed for the layers. As will below, this requires bit of work since a naive representation of the layers of k-IGNs use 2k index variables. Nevertheless, we show that this can be reduced index variables only.
By inspecting the expressions needed to represent the layers of k-IGNs in TL (22), we obtain that t layer (*) require expressions of summation depth of th. In other words, the correspondence between layers and summation depth is precisely in sync. This implies, by Theorem 4.2:
pi (k-IGN) pi (vw)l=1)::
where we ignore the number of layers. We similarly obtain that Po (K-IGN) = Pu (gwlloe)) hereby (2019a). Finally, we observe that the k-IGNs used
answering the open problem posed in Maron in Maron et al. (2019h) to show the inclusion pi (K-IGN"*) S pi (vwl are of very simple form. By defining a simple class k-IGNs, denoted by k-GINs, we obtain
pi (k-GIN")) #1 (vwlg-))
hereby recovering the layer/round connections.
We start with the following lemma:
Lemma E.1. For any k 2 2, t layer k-IGNs can be represented in TL*
Before proving this lemma, we recall k-IGNs. These are architectures that consist of linear equiv- ariant layers. Such linear layers allow for an explicit description. Indeed, following Maron et al. (2019c), let reg be the equality pattern equivalence relation on [n] such that for a, b [m]', a ~e if and only if a, a + b by for all j E [t]. We denote by in]/>>> the equivalence classes induced by ~e. Let us denote by F E IR" xd, the tensor computed by an k-IGN in layer t 1. Then, in layer 1, new tensor in Ran xd. is computed, follows. For [d:] and v1..... E [m]]:
F BE.... =
Σ
1 ((r,w) En
Σ Cyiig Fi) wi..
1 Ieeubpes
(1)
/ejn)////ag we[n]*
kE(d--1]
/E|D)/m
for activation function constants C and bus in R and where (w,w)er and 1ven are indicator functions for the 2k-tuple (v, w)) be in the equivalence class ? [m] [n] and the k-tuple to
32

---

Published as a conference paper at ICLR 2022
be in class μ [n) As initial tensor F one defines F ci.... atp;(G, (G, R. with do 2()) + ke where É is the number of initial vertex labels, as for k-FGNNs.
We remark that the need for having summation depth of th in the expressions in TL,(9)), or equivalently for requiring th rounds of (k 1)-WL, can intuitively be explained that each layer of k-IGN aggregates more information from "neighbouring" k-tuples than - 1)-W does, Indeed, in each layer. an k-IGN can use previous tuple embeddings of all possible k-tuples. In single round of (k: 1) only previous tuple embeddings from specific sets of k-tuples are used. only after additional k - rounds, that k-WL gets to the information about arbitrary k-tuples, whereas this information is available a k-IGN in one layer directly.
Proof of Lemma E.I. We have seen how F can be represented in TL2 when dealing with k-FGNNs. We assume now that also the 1th layer F(-1) can be represented by d expres sions in TL4 (L(t-1))o(()) and show that the same holds for the /th layer.
We first represent F in TL2x(S),, based on the explicit description given earlier. The expressions index variables 21;--., and /1,... Uk- More specifically, for j [de] we consider the expressions:
( (1I..... Ik) =
Cr.i
vE(N)a /wokk
1=1
Σ ... 91
Σ
( (1
The V1. ....... ...))..))))))............ v 10-1) "Vn..... ......,,kk))
Σ bus Sial
(2)
pEin]*/~E
where th (Z1...... my,) is product of expressions of the form 1r, op encoding the equality pattern μ., and similarly, b,,, (Z1...... Tk. ....... Mt:) a product of expressions of the form 1r, op 1y op y and 1z, op encoding the equality pattern These expressions are indicator functions for the their corresponding equality patterns. That is,
Ttbys w)) = -11 if (v,w) otherwise
if v E μ {1 0 otherwise
We remark that in the expressions o we have kinds of summations: those ranging over fixed number of elements (over equality patterns, feature dimension), and those ranging over the index variables y1. .kk The latter are the only ones contributing the summation depth. The former are just concise representations of a long summation over fixed number of expressions.
We now only need to show that we can equivalently write v (.i,..., kkk) as expressions TLx that is, using only indices Ii....,Iy As such, we can already ignore the term Ene(n)/ b (x Ixk) since this is already in (L) Furthermore, this expressions does not affect the summation depth.
Furthermore, as just mentioned, simpler expressions. As such, it suffices to show that k index variables suffice for each expression of the form:
expand expression 10 into linear combinations of other
> (, Tbs .i.....y.!! yk) (y.. yk),
M1
obtained by fixing j and in expression (2). To reduce the number of variables, as first step we eliminate any disequality using the inclusion-exclusion principle. More precisely, we observe that v y) can be written as:
II 1, (l
II (i.)eT
1,
II (J)EJ
1 b
II
19
II 1, ((.)KK
II 1 (..))
(J))J
33

---

Published as a conference paper at ICLR 2022
+EE (-1)LAHHBBH AEJRCJCER
II
1 1
II 18
II 1nmyy,
(4)
((J)
(6J)JJUR
(1-j)EJUC
for some I, J and K of pairs of indices in [k]2. and where 7= [k] 1 J J [k] and K = [M:2] K. Here we use that lapta = =1-1 -1-1,,=,, z 5,y., = 1 y my and 1 u = by and use the inclusion-exclust
principle to obtain a polynomial in equality conditions only.
In view of expression (4), we can push the summations over y1...., in expression (3) to the subexpressions that actually use .I....., yk. That is, we can rewrite expression (3) into the equivalent expression:
ΣEΣ AÇI BCJ CER
Σ
II 12,=0,
(KJ)EJUA
Σ
w=w
II (K,)EKUC
12,=0, "p (......., Mk) )
(5)
(6,))JUBB
By fixing A, B and C, now suffices to argue that
II mn
Σ
II (K,)EKUC
12,-0, -/- "yn."..... (6)
(15)
Vi
Uk (i.))JJUB
be equivalently expressed in (Q))
Since our aim is to reduced the number of index variables from 2k to k, important to known which variables are the same. In expression (6), some equalities that hold between the variables may not be explicitly mentioned. For this reason, we expand U A, J JUL. B and K U C with their implied equalities. That is, 1 1,,= is added I A, if for any (v, w) such that
I
1 1x,-, (i.j)NA
III
II (LJ)JJUR
II (KJ)RKUC
I,, (v, w)lG
[1,,=2y, oIa
holds. Similar implied equalities 1 1,, and 12,=9; are added to J JUB and K K.C, respectively. let denoted by I', J' and K". It should be clear that we can add these implied equalities to expression (6) without changing its semantics. In other words, expression (6) can be equivalently represented by
II 12,=2, (U))
Σ Σ
1 w. (K,j)EJ'
II
II 1x,=y, Pi (at ( ........ yk) (KJ)EK'
There now two types of index variables among the yi,.... Uk: those that are equal to some 2;, and those that are not. Now suppose that (i.j') J', and thus yj = -yy, and that also (i,j) E K', and thus I; Øý- Since we included the implied equalities, we also have (i,j") E K", and thus x; My-- There is reason keep (j,j") E J' as it is implied by (i.j) and (i,J") K". We thus safely remove all pairs (j.j") from J' such that (i.j) K' (and thus also (i.j") E K'). We denote by J be the reduced set of pairs of indices obtained from J' in this way. We have that expression (7) can be equivalently written as
II 1 (UJ)r
Σ Dk
II (K.))K'
1z.=,,
II (K))EJ"
1 1n-,, 56 11 (31 (y1....,, ......k))
(8)
where we also switched the order of equalities in J" and K'. Our construction J" and K' ensures that none of the variables y! with belonging to a pair in J" is equal to some
By contrast, the variable Yj occurring (i,7) E K' are equal to F;. We observe, however, that also certain equalities among the variables {#I..... J hold, as represented by the pairs in l'. let (i(1) : (i' (i,7') E I') and define as unique representative element 1'(i). For example, one can take be smallest index in I(()). We use this representative index (and corresponding u-variable) simplify K". More precisely, we replace each pair (i,j) E K' with the pair (i, j). In
34

---

Published as a conference paper at ICLR 2022
terms of variables, replace 2; yj with x; Vy- Let K" be the set K" modified in that way. Expression (8) can thus be equivalently written as
II 1,,=,
Σ
II (iJ)EK"
II (A,))J"
1u 1 "x ......., vk.)
(iJ))
21
where the free index variables of the subexpression
Σ II 1=
II (i.))JJ"
1 ,, p "31 "yI....., My)
(10)
V1 3R (L,))EK"
precisely the index variables 2; for (ž,j) K" Recall that our aim is to reduce the variables from 26 to k. We are now finally ready to do this. More specifically, we consider a bijection 8 : {y1, ......... ................................
and B(yy) y8] + [II,...,,II in which ensure that for each there is a j such that (i,j) K" 24. Furthermore, among the summations Σy, .'Eg. Ey, can ignore those for which ((y)) = xi holds. After all, they only contribute for given æı; value. Let Y be those indices in such that ((y)) * Ia for some i. Then, we can equivalently write expression (9) as
II 1, (1)))P
Σ
II
1o,)(,,)) II ((w))8(()))
B( (LS)EK)
(KJ)eJ"
(11. (11)
11- 11 (vi.... vk.) denotes the expression obtained by renaming of variables yi..... in where ((x)
pi ((-1) (y......,30 yy) into z-variables according to 3. This is our desired expression TLx If we analyze the summation depth of this expression, we have by induction that the summation depth of vptt (t-1) is at most (t k) In the above expression, we are increasing the summation depth with at most [Y). The largest size of Y is k, which occurs when none of the y-variables are equal any of the variabbls As consequence, we obtained an expression of summation depth at most tk, as desired.
As consequence, when using O for vertex embeddings, using (G, F P..... one simply pads the layer expression with [ 1z,=ı, which does not affect the number of variables or summation depth. When using th of graph embeddings, an additional invariant layer is added to obtain an embedding from G + _d Such invariant layers have similar (simpler) representation as given in equation (Maron et al., 2019c), and allow for a similar analysis. One can verify that expressions in TL TL((++1)k)()) (22) are needed when such invariant layer is added to previous l layers. Based on this, Theorem 4.2, Lemma E. and Theorem in Maron et al. (2019b), imply that P1 (K-IGN) P1 (vwlk-) +1(v
and po (k-IGN) po ()) hold.
k-dimensional GINs. We can recover a layer-based characterization for k-IGNs that compute ver- embeddings by considering special subset of k-IGNs. Indeed, the k-IGNs used in Maron al. (2019b) to show P1 (wlk2 C P1 (k-IGN' are of a very special form. We extract the essence of these special k-IGNs in the form of k-dimensional GINs. That is, we define the class k-GINs to consist of layers defined as follows. The initial layers are just as for k-IGNs. Then, for t 2 1:
F0 Pp. = mlp (F(tD)
Σ mlp ( e.....
Σ WeVo
mlp
(F F.......e..)
mlp
(itt)))
P1 (F
wEV&
-d- - R4 are MLPs. is now easy exercise to show that k- k can be represented in TL (Ω) (remark that the summa- tions used increase the summation depth with one only in each layer). Combined with Theorem 4.2
where F(-1)
oee E 1R mlp Rdd -> & and mlp (4)
and by inspecting the proof of Theorem in Maron al. (2019b), obtain:
35

---

Published as a conference paper at ICLR 2022
Proposition E.2. For any k 2 2 and any t 2 0: p1 (k-- p1 (vwl
We can define the invariant version of k-IGNs by adding simple readout layer of the form mlp(Fi) Ui...,,a.:...
is used in Maron et al. (2019b). We obtain, Po (o po(gwl by simply rephrasing the readout layer in (12).
F DETAILS OF SECTION 6
Let C(G,, I() be the class of all continuous functions from G. to Rf. We always assume that G. forms a compact space. For example, when vertices are labeled with values in {0. 10, Ge is a finite set which we equip with the discrete topology. When vertices carry labels in I we assume that these labels come from a compact set K C R In this case, one can represent graphs in G, by elements in (I and the topology used is the one induced by some metric ||-|| on the reals. Similarly, we equip R with the topology induced by some metric ||-I|-
Consider F S C(G..R)) and define F as the closure of F in C(G., R') under the usual topology induced by f + supc, [f, w)ll. In other words, continuous function h : Gg + R is in F there exists a sequence of functions f1, f2.... F such that lim supa Doo....ll (l, u)- e) = O. The following theorem provides characterization of the closure of a set of functions. We state it here modified to our setting.
Theorem F.1 ((Timofte, 2005)). Let F C C(G,, such that there exists a set S S IR) satisfying S CF F and p(S) S PFF). Then,
F: (f E C(G,, R") I(F) (DG)) 9., &
where F(G,v) v) = (K(G, v) 1 E CR. We can equivalently replace p(F) by P(S) in the expression for F.
We will use this theorem show Theorem 6.1 in the setting that F consists of functions that can be represented in TL(??), and more generally, sets of functions that satisfy two conditions, stated below. We more generally allow F to consist of functions : G. + R$,, where the Ey N may depend on f. We will require F to satisfy the following two conditions:
concatenation-closed: If fi G. + Rp and fo G. + Ry are in F, then = (f1, : G. + 1att. (G)v) + (G, f2(G, v)) is also in
function-closed: For a fixed E N, for any f E F such that f G. - RP, also ho f. G. Rº is in F for any continuous function h E C(PP, TIIP,,'' R.).
We denote by Fe be the subset of of functions from 9, to R..
Theorem 6.1. For any l, and any set F of functions, concatenation and function closed for f, we have: Fe = {f G. + Re P.(F) S (o()))
Proof. The proof consist of (i) verifying the existence of set S as mentioned Theorem F.1; and of (ii) eliminating the pointwise convergence condition "V(G, v) Go, f.G, E Fe v) in the closure characterization in Theorem F.1.
For showing (ii) we argue that Fe v) Re such that the conditions f(, Fe
automatically satisfied for any f E C(G., RR). Indeed, take an arbitrary f E G. - R' and consider the constant functions b; T Rd x + with b, E T the ith basis vector. Since F is function- closed for f, so is Fe. Hence, b; == gi o E Ft as well. Furthermore, if if. . + R :z + a X ær, for a R, then 8, f E Fe and thus F, is closed under scalar multiplication. Finally, consider + 2f + Re (x,z) + v + y. For f and g in Fe, h (f. F since F is concatenation- closed. As a consequence, the function + o : G. + R is in Fe, showing that F& is also closed under addition. All combined, this shows that Fg is closed under taking linear combinations and since the basis vectors of Re can be attained, Fe v) = TRC desired.
36

---

Published as a conference paper at ICLR 2022
For (i), show the existence of set S C C(Gs, R) such that S F. S Fe and Pa(S) S (F(e)
hold. Similarly as in Azizian & Lelarge (2021), we define
S = {f E C(S,, R)
f)
Etimes
We remark that for & E S and ʃ E 8. + -R (G,v) + s(G v) o S(G, v), with @ being pointwise multiplication, is also in Fe. Indeed, 8. S- oo (8, f) with (s, f) the concatenation of and f and @ : 2 + Re (x. y) + x O y being pointwise multiplication.
It remains to verify (S) (Fe). Assume that v)) and (HI,)) are not in (F(F. By definition, this implies the existence of function f E Fe such that f(G, v) a + b f(H, w) with a, b E R.. We argue that (G, v) and (H, w) are also not in P. (S)) either. Indeed, Proposition in Maron et al. (2019b) implies that there exists natural numbers a (a1,...,a0) E N such that the mapping ha : RR'' R : a - I x.e satisfies (a = + b = ha with a, b E R. Since F (and thus also Fr) is function-closed, ha of E Fg for any E Fe. In particular, 9 == ha f E Fe and concatenation-coe -oloouu implies that (g.....9) g, + R is in Fe too. Hence, g E S. by definition. It now suffices to observe that g(G, = ha (f. v)) = a a x
ha (f w)) = HH,, w), and thus (G, v) and (H, w) are not in (S)) as desired.
When we know more about (FFF we can say a bit more. In the following, we let alg {cr()) ger"t, wwlh gwl( and only consider the setting where is either (invariant graph func- tions) or s = (equivariant graph/vertex functions).
Corollary 6.2. Under the assumptions of Theorem 6.1 and if p(Fi) p(alg), then Fi = { 9 R p(alg) C p(f)).
Proof. This is just a mere restatement of Theorem 6.1 in which (FFFF) in the condition (F(F) C P&(f) is replaced by pz(alg), where s = 1 for alg E {crl") wwll and = - for alg E {ger") gwlge) J.
To relate all this functions representable by tensor languages, we make the following observations. First, if consider F to be the of all functions that can be represented in GTL Tl)+*( T (Q) or TL(22). then F will be automatically concatenation and Ω consists of all functions in Up C(RP, R Hence, Theorem 6.1 applies. Furthermore, our results from Section 4 tell us that for all t 2 0, and 2 1, p (cr
TL
provided that
pi (G)), po pg(rr()) po (TTT++ = po (o(gl("") pI (ewl!") = Pi (TL)) (Ω)). and po ( (TL (22) = po (gwll As consequence, Corollary 6.2 applies as well. We thus easily obtain the following characterizations:
Proposition F22 For any t and k 2 1:
F F consists of all functions representable GTL) then Fe = { 91 + R (I(ctl)) S (f));
If F consists of all functions representable in (L)), then Fr {s 91 + Re (v(wilt)) S p1(f);
F consists of all functions representable in TL** then Fr = { : Go + R Po(gwl(")) S po())); and finally,
If F consists of all functions representable in TL++1(9), then F {f Go + g Po(gwlloo)) S (o())),
provided that Q consists of all functions in U, C(RP, RR).
In fact, Lemma 32 in Azizian & Lelarge (2021) implies that equivalently populate Ω with all MLPs instead of all continuous functions. We can thus use MLPs and continuous functions interchangeably when considering the closure of functions.
37

---

Published as a conference paper at ICLR 2022
At this point, want make comparison with the results and techniques in Azizian & Lelarge (2021). Our proof strategy is very similar and is also based on Theorem F.I. The key distinguishing feature is that consider functions f G. - RR instead of functions from graphs alone. This has as great advantage that no separate proofs are needed to deal with invariant or equivariant functions. Equivariance incurs quite some complexity in the setting considered in Azizian & Lelarge (2021). A second major difference is that, by considering functions representable in tensor languages, and based on our results from Section 4, we obtain more fine-grained characterization. Indeed, we obtain characterizations in terms of the number of rounds used in CR and k-WL. In Azizian & Lelarge (2021), is always set to oc, that is, an unbounded number of rounds is considered. Further- more, when it concerns functions/ f 9i + R we recall that CR is different from 1-WL. Only 1-WL is considered in Azizian& & Lelarge (2021). Finally, another difference is that we define the equivariant version vwl, in different way than is done in Azizian & Lelarge (2021), because in this way, a tighter connection to logics and tensor languages can be made. In fact, if we were to use the equivariant version of k-WL from Azizian & Lelarge (2021), then we necessarily have to consider an unbounded number of rounds (similarly as in our gwl, case).
We conclude this section by providing little more details about the consequences of the above results for GNNs. As we already mentioned in Section 6.2, many common GNN architectures are concatenation and function-closed (using MLPs instead of continuous functions). This holds, for example, for the classes G eGIN k-FGNN and k-GINg and K-IGN as described in Sec- tion 5 and further detailed in Section and D. Here, the subscript l refers to the dimension of the embedding space.
We now consider a function f that is not more separating than cr (respectively, ger"), vwl. or gwlg for some k 2 1), and want to know whether f can be approximated by a class of GNNs. Proposition F.2 tells that such f can be approximated by a class of GNNs as long as these are at least as separating as GTL (respectively, TL TLE 1 or TL ). This, in turn, amounts showing that the GNNs can be represented in the corresponding tensor language fragment, and that they can match the corresponding labeling algorithm in separation power. We illustrate this for the GNN architectures mentioned above.
In Section 5 we showed that GIN can be represented in GTL) Theorem 4.3 then implies that yi (cr()) S pi (GIN Furthermore, Xu et al. (2019) showed that pi (GIN)") S Pi (cr"t). As consequence, م (GIN = pi (cr()). We note that the lower bound for GINs only holds when graphs carry discrete labels. The same restriction is imposed in Azizian & Lelarge (2021).
In Section 5 we showed that eGIN can be represented in (L). Theorem 4.2 then implies that p1 (1(wl(()) S. Pi (eGIN(") Furthermore, Barceló et al. (2020) showed that pi (eGIN( S pi (vwl)"). As a consequence, /i (eGIN()) = pi (vwl"").. Again, the lower bound is only valid when graphs carry discrete labels.
In Section 5 we mentioned (see details in Section D) that K-FGNN can be represented in K++ (9). Theorem 4.2 then implies that pi (v S pi ) Further- more, Maron et al. (2019b) showed that Pi (A-FGNN;)) S p1 (vwll()) As consequence, Pi (K=FFGN) C pi (vwl?"). Similarly, pi ((k: 1)-GIN!") pi (vwlk)) for the special class of (k + 1)-IGNs described in Section E. No restrictions are in place for the lower bounds and hence real-valued labeel- graphs can be considered.
When GIN or eGIN are extended with readout layer, we showed in Section that these can be represented in TLL+ Theorem 4.4 and the results by Xu et al. (2019) and Barceló et al. (2020) then imply that (vwl("") and po(ger(t)) coincide with the separation power of these architectures with readout layer. Here again, discrete labels need to be considered.
Similarly, when K-FGNN or (k + 1)-IGNs are used for graph embeddings, we can represent these in TL (I2) resulting again that their separation power coincides with that of gwl(") No restrictions are again in place on the vertex labels.
38

---

Published as a conference paper at ICLR 2022
So for all these architectures, Corollary 6.2 applies and characterize the closures of these architectures in terms of functions that not more separating than their corresponding versions cr or l--WL, described in the main paper. In summary,
Proposition F.3. For any t 2 0:
{f 91 + R I pp((f) GTL eGIN (J: - TRC (I Em(()) (1)
2
and when extended with a readout layer:
GIN eGIN²" {f : 9u + R Po(EwI)) & po(f)) Furthermore, for any k 21
(9)+
1s- k-FGNN GIN {f :6 + +R
(vwll (pi(f)} I
TL (90)
(k + 1)-IGN, = (J - RR pI ( [p((O)) = TLx+1(52)e
and when converted into graph embeddings:
k-FGNN; = K-GIN, = (k + 1)-IGN, = {f 9 - R$
[ - T(++
where the closures of the tensor languages interpreted as the closure the graph or graph/vertex functions that they can represent. For results involving GINs or eGINs, the graphs considered should have discretely labeled vertices.
As side note, remark that in order to simulate CR on graphs with real-valued labels, one can use GNN architecture the form Fdb (Fat-), " (e(N) mlp( mlp(F(t-1)) which translates in (T) expressions of the form
(Z1) F211, mlp, (xp (x1-"((1)
1 1 S d:-1 d-1 <j S.
of (x))
(x))
Pd. (x1))
The upper bound in terms of CR follows from our main results. To show that CR can be simulated, it suffices to observe that one approximate the function used in Proposition I in Maron et al. (2019b) to injectively encode multisets of real vectors by means of MLPs. As such, a continuous version of the first bullet in the previous proposition be obtained.
G DETAILS ON TREEWIDTH AND PROPOSITION 4.5
As extension of our main results in Section 4, enrich the class of tensor language expressions for which connections to k-WL exist. More precisely, instead of requiring expressions to belong to TL++1 (12), that is only use h + index variables, semantically equivalent to an expression using k + variables. Proposition 4.5 identifies a large class of such expressions, those of treewidth k. As consequence, even when representing GNN architectures may require more than k + index variables, sometimes this number can be reduced. As consequence of our results, this implies that their separation power fact upper bounded by {-WL for a smaller é < k. Stated otherwise, to boost the separation power of GNNs, the treewidth of the expressions representing the layers of the GNNs must have large treewidth.
investigate when expressions in TL(22)
We next introduce some concepts related to treewidth. We here closely follow the exposition given in Abo Khamis al. (2016) for introducing treewidth by means variable elimination sequences of hypergraphs.
In this section, we restrict ourselves summation aggregation.
G. ELIMINATION SEQUENCES
We first define elimination sequences for hypergraphs. Later on, show how associate such hypergraphs to expressions in tensor languages, allowing us to define elimination sequences for tensor language expressions.
39

---

Published as a conference paper at ICLR 2022
With multi-hypergrapp H (V.E) we simply mean multiset & of subsets of vertices V. An elimination hypergraph sequences is a vertex ordering o = Ui,..., Un of the vertices of H. With such sequence o, we associate for H. 1n-1--... Ht as follows. We define
...... 1 sequence of n multi hulti-hypergraphs 1, n 1 ................................
Hn = (Vn. En) = H
A(v,) = (F E En Un E F}
U, U F.
FED(Un)
and for j = 1, 2, 1:
V, = ful....,,s) fi}
E = (E ((05t1)) (0++i))
0(v)) = ( E)
U = U
FEO(NS)
The induced width on H. by a is defined as max UU| - We further consider the setting in which H. has some distinguished vertices. As we will see shortly, these distinguished vertices correspond to the free index variables of tensor language expressions. Without loss of generality, we assume that the distinguished vertices are #1, v2,.... When such distinguished vertices are present, an elimination sequence is just as before, except that the distinguished vertices come first in the sequence. If Ui, Vy are the distinguished vertices, then we define the induced width of the sequence f maxx/+ssisn IU; \ {vi,.... Uy }| - 1. In other words, we count the number of dis- tinguished vertices, and then augment it with the induced width of the sequence, starting from 4 to to U,, hereby ignoring the distinguished variables in the U, ss One could, more generally, also try to reduce the number free index variables but we assume that this number is fixed, similarly as how GNNs operate.
G.2 CONJUNCTIVE TL EXPRESSIONS AND TREEWIDTH
We start by considering a special form of TL expressions, which we refer to as conjunctive TL expressions, in analogy conjunctive queries in database research and logic. A conjunctive TL expression is of the form
( Σ (w.
where denote the free index variables, contains all index variables under the scope of sum- mation, and finally, (x y) is product of base predicates in TL. That is, va y) a product of E(z, 2;) and Pz(z,) with 2;, Zj variables in æ y. With such conjunctive TL expression, one can associate a haprr-hh a canonical way (Abo Khamis et al., 2016). More precisely, given a conjunctive TL expression (p(x) we define H.p
V& consist of index variables and y;
Ex:: for each atomic base predicate in 1b have edge F, containing the indices occurring in the predicate; and
the vertices corresponding to the free index variables form the distinguishing set of ver-
tices.
We now define an elimination sequence for ip an climination sequence for H.p taking the dis- tinguished vertices into account. The following observation ties elimination sequences of yp to the number of variables needed to express yp.
Proposition G.1. Let (p(x)) be conjunctive TL expression for which an elimination sequence of induced with k exists. Then sp(x) is equivalent to an expression ((x)) TL..
Proof. We show this by induction the number of vertices in H.p which are not distinguished. For the base case, all vertices are distinguished and hence (p(x) does not contain any summation and expression in TL; itself.
40

---

Published as a conference paper at ICLR 2022
Suppose that in Hip there are p undistinguished vertices. That is,
Σ ... Σ (a,
21
Up
By assumption, we have an climination sequence of the undistinguished vertices. Assume that Up is first in this ordering. Let write
((())
Σ
Σ
(b, y)
y1
Up
Σ
Σ
vi (x, y Bo) Σ U2 y)
where 11 is the product of predicates corresponding to the edges F E Ep (Up)) that is, those not containing Up, and t is the product of all predicates corresponding to the edges F E ((p)). that is, those containing the predicate yp- Note that, because of the induced width of A - 1. Ey, V2 y) contains all indices in Up which is of size S k. We now replace the previous expression with another expression
((xx) = Σ Σ (2, Up) Ra(
xxx)=
Where R2 is regarded as an |Up1 1-ary predicate over the indices in Up Mp. It is now easily verified that Hpp is the hypergraph H corresponding to the variable ordering We note that this is hypergraph over p undistinguished vertices. We can apply the induction hypothesis and replace ('(x) with its equivalent expression G (xx) ) in TL.. To obtain the expression ((xx) of (ax), now remains to replace the new predicate R2 with its defining expression. We note again that Rp contains at most k -1 indices, so it will occur in & (xx in the form (a 2) where |z| < k 1. In other words, one the variables in z is not used, say 2g. and we can simply replace Rp x) by E,, (x 2.2.)
As consequence, way of showing that conjunctive expression ((x:) in TL equivalently expressible in TLk, is to find an climination sequence of induced width k -- 1. This in turn is equivalent to H.g having treewidth of k 1, as shown, c.g., in Abo Khamis et al. (2016). As usual, we define the treewidth of conjunctive expression ()(r) in TL as the treewidth of its associated hypergraph H.p.
We recall the definition of treewidth (modified to our setting): A tree decomposition T (Vr, Er, {T) of Hyp with Er VT + 2 is such that
* For any F E E, there is a E Vi such that F Cr and
For any E V corresponding to a non-distinguished index variable, the set {t tE V {(t)} is not empty and forms a connected sub-tree of T.
The width of a tree decomposition T is given by max,ev, (tr(t)) Now the treewidth of Hop- tw(H) is the minimum width of any its tree decompositions. We denote by tw(pp) the treewidth of H.g. Again, similar modifications are used when distinguished vertices are in place. Referring again to Abo Khamis et al. (2016), tw(yp) = k is equivalent to having a variable elimination sequence for yo of an induced width of k 1. Hence, combining this observation with Proposition G. results in:
Corollary G.2. Let (xx) be a conjunctive TL expression of treewidth k Then (p(x) is equivalent to an expression (xx) in TL..
That is, we have established Proposition 4.5 for conjunctive TL expressions. We next lift this to arbitrary TL(S2) expressions.
G.3 ARBITRARY TL(2) EXPRESSIONS
First, we observe that any expression in TL can be written as a linear combination of conjunctive expressions. This readily follows from the linearity of the operations in TL and that equality and
41

---

the following, v Published as a conference paper at ICLR 2022
inequality predicates can be eliminated. More specifically, we may assume that (o(x) in TL is of the form
Σ aa (z. y);
aEd
with A finite of indices and da IR, and 4o (2 y) conjunctive TL expressions. We now define
tw(() == max(tw((s)) (va) a E A}
for expressions in TL. To deal with expressions in TL(22) that may contain function application, we define tw((p) as the maximum treewidth of the expressions: (i) PProfun (2) E TL obtained by replacing each top-level function application f(P)..... (Pp) by new predicate RG with free indices (ree( J. .... U free((pp); and (ii) all expressions .1.....: (pp occurring in top-level function ap- plication ( Pp)
) in sp. We note that these expression either have no function applications (as in (i)) have function applications of lower nesting depth (in yo, as in (i)). In other words, applying this definition recursively, we end up with expressions with no function applications, for which treewidth was already defined. With this notion of treewidth hand, Proposition 4.5 now readily follows.
H HIGHER HORDER MPNNS
We conclude the supplementary material by elaborating on k-MPNNs and by relating them to clas- sical MPNNs (Gilmer et al., 2017). As underlying tensor language we use (S2, 9) which includes arbitrary functions (I)) and aggregation functions (6), defined in Section C.5.
We recall from Section that k- 4-MPNNs refer to the class of embeddings f 9. + IR' for some l E N that can be represented in (L2, +). When considering embedding f G. + R the notion of being represented is defined in terms of the existence of l expressions in TL θ), which together provide each of the components of the embedding in IR We remark, however, that we can alternatively include concatenation in tensor language. As such, we can concatenate é separate expressions into a single expression. As positive side effect, for f G. + R to be represented in tensor language, we can then simply define it by requiring the existence of a single expression, rather than l separate ones. This results in a slightly more succinct way of reasoning about k-MPNNs
In order to reason about MMMPNN class of embeddings, we can obtain an equivalent definition for the class of k-MPNNs by inductively stating how new embeddings are computed out of old embeddings. Let X = ( # } be a set of k + distinct variables. denotes a tuple of vertices that have at least many components used in expressions. Intuitively, variable zj refers to the jth component in v. We also denote the image of a graph G and tuple by expression (p, i.e., the semantics of &e given G and v, as (G,G v) rather than by [4p vIc. We further simply refer to embeddings rather than expressions.
the highest index of variables
We first define "atomic" MMMM embeddings which extract basic information from the graph G and the given tuple v of vertices.
Label embeddings of the form (pxx,) = : (xx)), with 0, e X, and defined by ((G v) := (cola(v:)) are MPNNN
Edge embeddings of the form ((),, = E(xi5ayy) with vi, X, and defined by
(G, v) = (1 if uyuy E Fgg otherwise,
are MMMNN and
(Dis-) Jqqualiyy embeddings of the form p(2;,,;) = 1,, with 24 E X, and defined by
1 if U/ up
(G, = 10 otherwise,
are MMNNS..
42

---

Published as a conference paper at ICLR 2022
We next inductively define new k-MPNN from "old" k-MPNNs. That is, given k-MPNNs pi (a1),.... (e(....,,pp))))).. the following are also k-MPNNs:
Function applications of the form ((()) = f((p((1)))........ (e((z) are k-MPNNs, where x 21 U... U Dt, and defined by
(( = (pp (fI vlai),..... Ge(G,
Here, if (: vle.) Rd, then Rd x... x Rd + Hd for some d N. That is, & generates an embedding in R.d. We remark that our function applications include concatenation.
vle,)
Unconditional aggregations of the form (px)) == agg,, (2r (z)) are k-MPNNs, where Ij E X and žj & æ, and defined by
(G v) : F (H Uj-1, 11 0
Vali).
Here, if 4p generates an embedding in Rd,, then an aggregation function assigning to multisets of vectors in Rd a vector in Rd, for some d E N. So, generates an embedding in Rd
Conditional aggregations of the form p(x;) agg., MPNNs, with Ty X, and defined by
are k- (G v) == F(lvi v, w) w No(v:))))
As before, if (p generates an embedding in Rd,, then F is an aggregation function assigning to multisets vectors in Rddi vector in Rd, for some E N. So again, & generates an embedding in R
As defined in the main paper, we also consider the subelass k-MPNN by only considering k- MPNNs defined terms of expressions of aggregation depth most Our main results, phrased in terms of k k-MPNNs are:
Pi (vwll)) = Pr (K-MPNNs and Po(gwl,)) = Pa (M-Nss.
Hence, if the embeddings computed by GNNs are k-MPNNs, one obtains an upper bound on the separation power in terms of k-WL.
The classical MPNNs (Gilmer et al., 2017) are subclass of 1-MPNNs in which no unconditional aggregation can be used and furthermore, function applications require input embeddings with the same single variable (æ1 or T2), and only 1,,=æ; and 1æ, are allowed. correspond to guarded tensor language expressions (Section 4.2). We denote this class of 1-MPNNs by MPNNs and by (PNNs when restrictions on aggregation depth are in place. And indeed, the classical way of describing MPNNs
other words, they
6 (x1) = (P. Pe(z1))
6 (z)) = r ( ( "(I1), p(o) (xr),,
(xx1), tht "xx2) (x2) E(s,, 25)))
correspond to 1-MPNNs that satisfy the above mentioned restrictions. Without readouts, MPNNs compute vertex embeddings and hence, our results imply
pi (cr = Pi P (MPNNs
Furthermore, MPNNs with readout function fall into the category of 1-MPNNs:
$ aggr readout (x)1)
where unconditional aggregation is used. Hence.
Pu(gcr !u(gw!!!) = (11MMNNN
We thus see that k-MPNNs gracefully extend MPNNs and can be used for obtaining upper bounds on the seperation power of classes of GNNs.
43


Reviews:
[{"review_id": "xZBuc9dbeNY", "reviewer": "Reviewer_tPHz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Post-rebuttal Comments (11/29/2021)\n\nI appreciate the authors for their response. I am satisfied with their answers. So, I want to keep my score and vote for acceptance.\n\n# Initial Comments\n\n【Strength】\n- [1] This paper gives a general procedure for deriving the upper bound of expressive power for any GNN as long as we can translate it into the tensor language.\n- [2] Theorem 6.1 and Corollary 6.2 allow us to give lower bounds on the expressive power of GNNs as well.\n\n【Weakness】\n- [1] Compared to the upper bound, it is more difficult to show the lower bound of expressive power because the former needs individual proof for concrete GNNs.\n- [2] Those familiar with GNNs but not with the first-order logic may be hard to follow up the discussion of the paper.\n\n【Correctness】\n- [1] As far as I checked, I could not find any inappropriate points in the proofs.\n- [2] What I am wondering is that in Theorem 4.1, the equivalence relation $\\rho_1(\\mathsf{TL}_{k+1}(\\Omega))$ is independent of the choice of $\\Omega$. Considering the case of $\\Omega=\\emptyset$, does this result imply that the separation power of the tensor language does not increase even if we add expressive functions such as non-linear activation functions or MLPs?\n\n【Technical Novelty And Significance】\n- [1] As mentioned in this paper, several studies such as [Barcelo et al., 2020 ] have studied the expressive power of GNNs via first-order logic. However, while [Barcelo et al., 2020] related GNNs to the existing first-order logic (namely, $\\mathrm{FOC}_2$), this paper defined a new grammar, the tensor language $\\mathsf{TL}$, and related GNNs to the first-order logic via this language. In this sense, the approach of this paper is novel.\n- [2] This approach allows us to analyze expressive power independently of particular GNNs. In addition, it is relatively easy to derive the expressive power of a GNN because it is sufficient to translate the GNN into the tensor language. Therefore, I think this approach is significant.\n- [3] There is no easy and general way to obtain the guarantees for the lower bound of the expressive power compared with the upper bound. We have to check the sufficient condition of Corollary 6.2 for each GNN, which needs proof tailored to the GNN. If we can find a general approach to obtain the guarantees, it would increase the paper's significance. (However, it is also notable that this paper obtained lower bounds systematically to some extent, as mentioned in Proposition E.3.)\n- [4] The paper gives positive answers to the unresolved issues raised by existing studies. In this sense, this paper is significant.\n\n【Empirical Novelty And Significance】\n- [1] This paper does not have numerical experiments.\n\n【Detailed Comments】\n- [1] P.3: I think it is better to write the definition of irreflexivity as it is not well-known.\n- [2] P.3: Initially, for a graph $G$ and $\\mathbfit{v}\\in V^k_G$, ... → I am afraid this sentence is hard to understand, especially the part \"where, atp_k(G, v) is the atomic type...\". Could you reconsider the sentence?\n- [3] P.4: I think $S$ is undefined.\n- [4] P.6: The definition of $\\mathsf{C}_{k+1}$ does not appear in the main text (only available in Appendix).\n- [5] P.13: $\\pi_{\\sigma\\star G}\\textlbrackdbl \\varphi_1, \\sigma \\star \\nu \\textrbrackdbl \\cdot \\pi_{\\star G}\\textlbrackdbl \\varphi_2, \\sigma \\star \\nu \\textrbrackdbl$ → $\\star G$ should be $\\sigma\\star G$.\n- [6] P.15: e..g., → e.g., \n- [7] P.16: Here the unravelling is the (infinite tree ... → remove the parenthesis\n- [8] P.17: $\\pi_{H}\\textlbrackdbl \\varphi_1, \\mu[x_i \\to v] \\textrbrackdbl$ → $\\pi_{G}\\textlbrackdbl \\varphi_1, \\mu[x_i \\to v] \\textrbrackdbl$", "summary_of_the_paper": "This paper defined formal languages for describing tensor expressions. It showed that their expressive power is identical to (suitably parameterized) color refinement algorithms or (vertex/graph) WL algorithms. Then, by translating existing GNNs into the tensor languages, this paper provided upper bounds for the expressive power of GNNs, which recovered several existing results. In addition, this paper characterized the closure of a function class by functions whose expressive power is equal to or less than the functions (Theorem 6.1). As an application, this paper characterized the expressive power of several GNNs via the tensor language (Corollary 6.2, Proposition E.3).", "summary_of_the_review": "As far as I checked, I could not find any incorrect points in the proofs. I think this paper is technically novel and significant as it gave a model-agnostic approach for analyzing the expressive power of GNNs and solved several conjectures.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "fDtiNO8OlR", "reviewer": "Reviewer_KRNm", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strong Points\n\n1. Evaluation of the expressive power of GNN is indeed not straightforward and needs a lot of architecture specific proofs. Indeed, we need model agnostic way to evaluate expressive power of any GNN.  Thus the main motivation of the paper is appropriate and might have a significant effect on the literature.\n\n2. Paper was written well, quite clear and understandable. It includes enough theoretical proofs and examples on how to find the expressive power of some well-known GNNs.\n\n## Clarifying the used WL test order\n\nClarifying the used WL test order would be great. In GNN papers, generally we call CR as 1-WL, then original 1-WL as 2-WL and so on and so forth. It seems that this paper follows (Cai et al 1992) notations. It means the GNN in (Maron et al.,2019b) , known to have 3-WL power in the original paper, has 2-WL power according to this paper. It would be better if this point is clearly mentioned.\n\n## Weak Points\n\n1. The way of evaluating expressive power by tensor language is not new at all. According to my knowledge, this kind of evaluation was recently proposed in [1]. They introduced Geerts' matrix query language (MATLANG) for GNN world and showed how to use it in order to evaluate some well known GNN's expressive power by write down given GNN's forward calculations in matrix form. Then, they figured the expressive power out by determining which language can explain GNN's forward calculations. Thus, In Separation Power sections \"We do not have any general technique allowing us to expand these results for arbitrary GNNs\" and in Related Work section \"general matrix query languages are known,albeit not in the context of GNNs\" are basically not true. Also [1] falsified the claim that \"In summary, our paper draws new and interesting connections between tensor languages, GNN architectures and classic graph algorithms\". I strongly think the connection between the tensor language and WL-test order of GNN models is interesting and valuable, but not novel. Definitely the differences between similar recent works should be discussed.  \n\n2. Showing how many iterations of the WL-test equivalent of the given GNN is trivial. It is well-known that an additional layer in GNN is equivalent to WL-test's additional iteration (coloring rounds). So in expressive power analysis, we can assume that we always have enough layers as we assume the WL test continues till the stabilization of colors. Introducing that depth parameter as a contribution seems a little exaggerated. In my mind, just WL test order equivalence is enough. \n\n3. Even though the main claim is that by this paper, anyone can determine the GNN's expressive power easily, is not that straight forward. One needs to write down the GNN layer in tensor form. It seems possible while using summation and/or weighted summation for neighborhood aggregation. How about other aggregations? Can PNA ( GNN that uses different aggregation such as max, min, std) be evaluated by this framework? I have seen that in Appendix, there is an example for GraphSage's version which uses sum aggregation. But the main version of GraphSage uses max.  There is no analysis for max aggregator of GraphSage. Is it possible to do it? Also some GNN such as Chebnet can be more powerful than 1-WL in some certain cases. But in general it is not less powerful than 1-WL. Can the proposed method determine this special case? Can Chebnet expressive power analysis be at least on the appendix?\n\n4. By Geerts' matrix query language MATLANG, we can determine the expressive power up to 3-WL (or 2-WL in Cai et al 1992 notation). This paper extends this matrix language in order to determine the expressive power of GNN which goes beyond the 3-WL. However, due to the memory and cpu complexity it is not that practical and I have never seen any GNN in practice whose expressive power is more than 3-WL. So the main contribution of the paper beside what MATLANG provides, seems not necessary in practice at least for now. I am suspicious if we really need more powerful than 3-WL GNN. Thus maybe these theoretical analyses will never be used.\n\n5. One of the main practical advantages of this theoretical work would be to give us some insight on how to increase the expressive power of GNN. Even though it is mentioned in the abstract, I am not sure these insights are clear enough. Can we create a new GNN architecture to use these insights? I see that experimental work such that proposing a new GNN is not the main idea of the authors. But at least some clear examples on how to increase expressive power would be very valuable.  \n\n\n### Reference\n[1] Muhammet Balcilar, Pierre Heroux, Benoit Gauzere, Pascal Vasseur, Sebastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021\n", "summary_of_the_paper": "The paper proposed a novel way of evaluating the expressive power of any arbitrary GNNs in terms of WL test order using tensor language. The main motivation of this paper is that there is no straight forward expressive power evaluation tool so far. All existing methods need architecture specific proofs. Main challenge is the translating given GNN into tensor language. Later, they easily parametrize given GNN by two numbers which are the number of indices of tensor language ($k$ ) and number of summation depth ($t$). Then, they claimed that given GNN's expressive power is equal to $k-1$-WL test when it applies $t$ coloring rounds.", "summary_of_the_review": "I think theoretical sounds of the paper is quite strong and the main motivation is valid.\nI am slightly to lean to recommend acceptance for this paper. But  above 5 points should be addressed.\n\nAfter rebuttal,the authors pointed out all my concerns very well. Therefore I would recommend clear acceptance for this work.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "fD4Jm071vJ_", "reviewer": "Reviewer_2fbv", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: the paper is very clearly written and makes a clear new connection between programming language and deep learning. Formalizing GNN as a TL is a new toolbox that allows the authors to get an unified theoretical analysis of the separating power of GNNs. In particular, they are able to get new results characterizing the expressive power of GNNs as a function of the number of layers. This alone is a very nice contribution.\n\nWeakness: I think Section 6 on function approximation is less relevant. The main reason is that the authors consider the discrete topology on the set of graphs so that any function is continuous. But GNN are more restricted functions and are continuous as mapping acting on tensors. As a consequence, I think:\n1- the results presented in section 6 are correct but could probably be proved with simpler arguments similar to the ones used in Appendix A of 'On the equivalence between graph isomorphism testing and function approximation with GNNs' by Zhengdao Chen, Soledad Villar, Lei Chen, Joan Bruna.\n2- the consequences of Theorem 6.1 and Corollary 6.2 are not clear for GNNs as GNNs cannot model any function taking a graph as argument. Indeed the importance of continuity is highlighted in section 3 of 'On the Limitations of Representing Functions on Sets' by Edward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, Michael Osborne.\nI think the authors should address this issue in Section 6.2 by explaining the possible limitation of their approach. Note that Azizian and Lelarge probably consider continuous functions of tensor representation of the graph for this reason.", "summary_of_the_paper": "This paper introduces a new approach to study the separation power and approximation properties of graph neural networks (GNN). The authors introduce the Tensor Languages (TL) and show the representation of GNN as TL expressions. In Section 4, they show the separation power of TL and relate it to color refinement algorithms like k-WL. In particular, they are able to characterize the separation power of such algorithms after a given number of iterations. These results allows them to compute in Section 5 the separation power of GNNs. They are able to recover all results in the literature in an unified way and prove some new results. In Section 6, they give consequences of their results in term of approximation of GNNs, recovering known results and proving new ones.\nThis is a theoretical paper without any experimental results.", "summary_of_the_review": "Very nice contribution making a new connection between programming language and GNN to study their expressive power.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "984h6pu_cnf", "reviewer": "Reviewer_QRwU", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The unified framework provided by TL is interesting, and allows a more uniform study of GNN models, and a simpler means to derive expressiveness bounds for new GNN models. The study of TL is also very well-grounded in the literature, as it includes most of the key works on GNN expressive power, and additionally confirms their findings. Furthermore, TL establishes a new set of results, thereby addressing some open questions in the field. In particular, it produces interesting insights about the effect of more layers, connecting this explicitly to treewidth and thus adding a nice nuance to this discussion. The results also appear intuitive and sound, though I did not check these thoroughly. Hence, the paper seems to be a valuable addition to the literature on GNNs.\n\nNonetheless, I find that the novelty of the approach is limited, particular relative to other frameworks characterizing GNNs. In particular, I cannot see the novelty proposed by TL relative to the matrix query languages mentioned in the paper. Therefore, I strongly suggest a more through comparison with related work. Furthermore, it is not clear how much simpler writing a TL expression for GNNs is, particularly with respect to non-standard GNNs involving, e.g, sub-structure counting. Hence, a more detailed presentation of specific model TL expressions, including some from the supplementary material, should be added into the paper to more clearly present the TL translation process. On a more minor note, the current writing style and notation are hard to follow. I refer specifically to Page 3, and the explanation of cr, gwl,vwl, etc. This section required multiple reads to be properly understood, and is quite dense. This is also true of other parts in the paper, e.g., Page 7. Therefore, a more simplified presentation, supported by examples, would be beneficial. Finally, the authors can also consider studying their framework with respect to classes of functions (or universality), as in Barcelo et al. [1], rather than just function approximation relative to separating power, to provide a more holistic overview of the GNN landscape. Alternatively, illustrations of functions with separation power limits can also benefit the presentation in this part of the paper. \n\n[1] Barcelo et al. The logical expressiveness of graph neural networks. ICLR 2020.", "summary_of_the_paper": "The paper proposes Tensor Language (TL), a language with which popular GNN models can be uniformly studied, so as to yield insights about their expressiveness and separation power. More specifically, the paper shows how TL corresponds to the WL hierarchy, and shows that summation depth in TL, as well as the number of index variables, correspond directly to iterations and tuple size for k-WL, respectively. Moreover, the paper establishes a direct correspondence between GNN update equations and expressions in TL, thus offering a simpler means to understand the expressive and separation power of GNNs, even considering their number of layers, by mapping their architectures to expressions in TL. TL , as well as its guarded fragment GTL, are then used to re-establish a set of known GNN results from the literature. \n\nBeyond expressive power, TL is also used to quantify the function approximation power of GNNs, and also shows that GNNs, characterized by a TL fragment, can learn functions with separation power upper-bounded by a refinement algorithm corresponding to this fragment. Finally, the TL framework is used to establish new results. In particular, it shows that k-IGN cannot achieve expressiveness beyond (k-1)-WL, as this model corresponds to tk iterations of (k-1)-WL, and also offers insights as to the expressiveness of k-IGN with a polynomial number of layers: Indeed, model power does not increase with more standard layers, e.g., those relying on the adjacency matrix, but rather, any increase in layers can only improve expressiveness by deriving GNN functions with e.g., increased treewidth.", "summary_of_the_review": "The paper's main proposal, TL, offers a novel and simple means to characterize the power of GNNs irrespective of specific design choices, and helps derive some new results for GNNs. All in all, the paper makes good contributions, but some of its claims, namely the simplicity of TL translation, as well as its novelty, should be better explained.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper gives a new theoretical framework to characterize the expressive power of graph neural networks that describes GNN by tensor language (TL) and then makes it possible to analyze its expressive power through the lens of TL. The authors connect the expressive ability of TL to the color refinement algorithms and (vertex/graph) k-WL algorithms. By doing so, the several existing results can be recovered in a unifying manner. In addition to that, the function approximation ability is also investigated. 

The paper gives a novel theoretical framework that gives a clear perspective to the problem of expressive power of GNN, which would be quite beneficial to the community and open up a new research direction. The reviewers have raised several questions on the paper, but the authors addressed all the concerns properly. Therefore, I recommend acceptance to ICLR2022.
Decision: Accept (Oral)