Some Might Say All You Need Is Sum

1 Introduction

Message passing graph neural networks (GNNs) are a fundamental deep learning architecture for machine learning on graphs. Most state-of-the-art machine learning techniques for graphs are based on GNNs. It is therefore worthwhile to understand their theoretical properties. Expressivity is one important aspect: which functions on graphs or their vertices can be computed by GNN models? To start with, functions computed by GNNs are always isomorphism invariant, or equivariant for node-level functions. A second important feature of GNNs is that a GNN can operate on input graphs of every size, since it is defined as a series of node-level computations with an optional graph-aggregating readout computation. These are desirable features that motivated the introduction of GNNs in the first place and may be seen as a crucial factor for their success. Research on the expressivity of GNNs has had a considerable impact in the field.

∗ Funded by the German Research Council (DFG), RTG 2236 (UnRAVeL)

† Funded by the German Research Council (DFG), grants GR 1492/16-1; KI 2348/1-1 "Quantitative Reasoning About Database Queries"

A GNN computation transforms a graph with an initial feature map (a.k.a. graph signal or node embedding) into a new feature map. The new map can represent a node-level function or can be "read out" as a function of the whole graph. The computation is carried out by a finite sequence of separate layers. On each layer, each node sends a real-valued message vector which depends on its current feature vector, to all its neighbours. Then each node aggregates the messages it receives, using an order-invariant multiset function, typically being entrywise summation (Sum), mean (Mean), or maximum (Max). Finally, the node features are updated using a neural network which receives as arguments the aggregation value and the node's current feature. In the eyes of a GNN all vertices are euqal: the message, aggregation and update functions of every layer are identical for every node, making GNNs auto-scalable and isomorphism-invariant.

By now, numerous works have researched the expressiv-

ity of GNNs considering various variants of them. However, many of the theoretical results have the following caveats: 1. The expressivity considered is non-uniform: for a function that is defined on graphs of all sizes, it is asked if for every n there exists a GNN that expresses the function on graphs of size n. The expressing GNN may depend on n, and it may even be exponentially large in n. For some proofs, this exponential blow-up is necessary [Abboud et al., 2021; Xu et al., 2019]. This notion of expressivity is in contrast to uniform expressivity: for a function that is defined on graphs of all sizes, asking whether there exists one GNN that expresses the function on graphs of all sizes. In addition to being a significantly weaker theoretical notion, non-uniform expressivity leaves much to be desired also from a practical standpoint: It implies that a GNN may be no good for graphs of sizes larger than the sizes well-represented in the training data. This means that training may have to be done on very large graphs, and may have to be often repeated.

2. The expressivity considered is the power to distinguish non-isomorphic graphs. A key theoretical result is the characterisation of the power of GNNs in terms of the WeisfeilerLeman (WL) isomorphism test [Morris et al., 2019; Xu et al., 2019], and subsequent works have used WL as a yardstick (see 'Related Work'). In applications of GNNs though, the goal is not to distinguish graphs but to regress or classify them or their nodes. There seem to be a hidden assumption that higher distinguishing power implies better ability to express general functions. While this is indeed the case in some settings [Chen et al., 2019], it is not the case with uniform expressivity notion.

Our goal is to better understand the role that the aggregation function plays in the expressivity of GNNs. Specifically, we ask: Do Sum aggregation GNNs subsume Mean and Max GNNs, in terms of uniform expressivity of general functions? A common perception is that an answer is already found in [Xu et al., 2019]: Sum-GNNs strictly subsume all other aggregations GNNs. Examining the details though, what is actually proven there is: in the non-uniform notion, considering a finite input domain, the distinguishing power of Sum-GNNs subsume the distinguishing power of all other aggregations GNNs. Furthermore, in practice it has been observed that for certain tasks there is a clear advantage to using Mean and Max aggregations [Cappart et al., 2021; Hamilton et al., 2017; T¨onshoff et al., 2022], with one of the most common models in practice using a variation of Mean aggregation [Kipf and Welling, 2017]. While the difference between theoretical belief and practical evidence may be attributed to learnability rather than expressivity, it calls for better theoretical understanding of expressivity.

1.1 Our Contribution

All our results are in the uniform expressivity notion. Mainly, we prove that Sum-GNNs do not subsume Mean-GNNs nor Max-GNNs (and vice versa), in terms of vertices-embedding expressivity as well as graph-embedding expressivity. The statements in this paper consider additive approximation, yet the no-subsumption ones hold true also for multiplicative approximation.

• Advantage Sum. For the sake of completeness, in Section 3 we prove that even with single-value input features, the neighbors-sum function which can be trivially exactly computed by a Sum-GNN cannot be approximated by any Mean-GNN or Max-GNN.
• Sum subsumes. In Section 4 we prove that if the input features are bounded, Sum-GNNs can approximate all Mean-GNNs or Max-GNNs, though not without an increase in size which depends polynomially on the required accuracy, and exponentially on the depth of the approximated Mean-GNNs or Max-GNNs.
• Advantage Mean and Max. In Section 5.1 we show that if we allow unbounded input features then functions that are exactly computable by Mean-GNNs ; Max-GNNs; and others, cannot be approximated by Sum-GNNs.
• Essential also with finite input-features domain. In Section 5.2 we prove that even with just single-value in-

put features, there are functions that can be exactly computed by a (Sum, Mean)-GNN (a GNN that use both Sum-aggregation and Mean-aggregation) or by a (Sum, Max)-GNN, but cannot be approximated by SumGNNs.

• The world is not enough. In Section 6, we examine GNNs with any finite combination of Sum; Mean; Max and other aggregations, and prove upper bounds on their expressivity already in the single-value input features setting.

Lastly, in Section 7 we experiment with synthetic data and observe that what we proved to be expressible is to an extent also learnable, and that in practice inexpressivity is manifested in a significantly higher error than implied in theory.

All proofs, some of the lemmas, and extended illustration and analysis of the experimentation, are found in the full version 1 .

1.2 RelatedWork

The term Graph Neural Network, along with one of the basic models of GNNs, was introduced in [Scarselli et al., 2008]. Since then, more than a few works have explored aspects of expressivity of GNNs. Some have explored the distinguishing power of different models of GNNs [Abboud et al., 2021; Barcel´o et al., 2021; Geerts and Reutter, 2022; Maron et al., 2019; Morris et al., 2019; Morris et al., 2020; Sato et al., 2021], and some have examined the expressivity of GNNs depending on the aggregations they use [Corso et al., 2020; Xu et al., 2019]. In [Chen et al., 2019], a connection between distinguishing power and function approximation is described. In all of the above, the non-uniform notion was considered. In the uniform notion, it was proven that SumGNNs can express every logical formula in Guarded Countable Logic with 2 variables (GC2) [Barcel´o et al., 2020b; Barcel´o et al., 2020a]. A theoretical survey of the expressivity of GNNs is found in [Grohe, 2021], and a practical survey of different models of GNNs is found in [Wu et al., 2020].

2 Preliminaries

By N , N >0, Q , R we denote the sets of nonnegative integers, positive integers, rational numbers, an d real numbers, respectively. For a, b∈N: a≤b we denote the set {n∈N: a≤n≤b} by [a..b]. For b∈N >0 we denote the set [1..b] by [b]. For a, b∈R : a≤b, we denote the set {r ∈R : a≤r ≤b} by [a, b] . We may use the terms "average" and "mean" interchangeably to denote the arithmetic mean. We use "{}" as notation for a multiset. Let x∈R , b∈N >0, we define � {x} b � �{x, . . . , x} the multiset consisting of b instances of x. Let d ∈N >0 and let a vector v∈R d , we define |v|�max(|vi|i∈[d]). Let two vectors u, v ∈R d , we define ′ ≤′ : u≤v⇔∀i ∈ [d]ui ≤vi.

2.1 Graphs

An undirected graph G=⟨V(G), E(G)⟩ is a pair, V(G) being a set of vertices and E(G) ⊆ {{u, v} | u, v ∈ V(G)} being a set of undirected edges. For a vertex v ∈ V(G) we denote by N(v) �

1 see https://arxiv.org/abs/2302.11603

{w∈V(G) | {w, v} ∈E(G)} the neighbourhood of v in G, and we denote the size of it by nv � |N(v)|.

A (vertex) featured graph G = ⟨V(G), E(G), S d , Z(G)⟩ is a 4-tuple being a graph with a feature map Z(G) : V(G)→S d , mapping each vertex to a d-tuple over a set S . We denote the set of graphs featured over S d by GS d , we define GS � � d∈N GS d , and we denote the set of all featured graphs by G∗. The special set of graphs featured over {1} is denoted G1. We denote the set of all feature maps that map to S d by ZS d , we denote � d∈N ZS d by ZS , and we denote the set of all feature maps by Z∗. Let a featured-graph domain D⊆G∗, a mapping f :GD→Z∗ to new feature maps is called a feature transformation.

For a featured graph G and a vertex v∈V(G) we define sum(v)�Σw∈N(v)Z(G)(w), avg(v)� 1 nv sum(v), and max(v)� max(Z(G)(w) : w∈N(v)). In this paper, we consider the size of a graphG to be its number of vertices, that is, |G|�|V(G)|.

2.2 Feedforward Neural Networks

A feedforward neural network (FNN) F is directed acyclic graph where each edge e carries a weight w F e ∈R, each node v of positive in-degree carries a bias b F v ∈R, and each node v has an associated continuous activation function a F v : R→R. The nodes of in-degree 0, usually X1, . . . , Xp, are the input nodes and the nodes of out-degree 0, usually Y1, . . . , Yq, are the output nodes. We denote the underlying directed graph of an FNN F by (V(F), E(F)), and we call � V(F), E(F), (a F v )v∈V(F) � the architecture of F, notated A(F). We drop the indices F at the weights and the activation function if F is clear from the context.

The input dimension of an FNN is the number of input nodes, and the output dimension is the number of output nodes. The depth depth(F) of an FNN F is the maximum length of a path from an input node to an output node.

To define the semantics, let F be an FNN of input dimension p and output dimension q. For each node v∈V(F), we define a function fF,v : R p →Rby fF,Xi (x1, . . . , xp)�xi for the ith input node Xi and

for every node v with incoming edges ej =(uj, v). Then F computes the function fF : R p →R q defined by

Let F an FNN, we consider the size of F to be the size of its underlying graph. That is, |F| = |V(F)|.

A common activation function is the ReLU activation, defined as ReLU(x)�max(0, x). In this paper, we assume all FNNs to be ReLU activated. ReLU activated FNNs subsume every finitely-many-pieces piecewise-linear activated FNN, thus the results of this paper hold true for every such FNNs. Every ReLU activated FNN F is Lipschitz-Continuous. That is, there exists a minimal aF ∈R≥0 such that for every input and output coordinates (i, j), for every specific input arguments x1, . . . , xn, and for every δ>0, it holds that

2.3 Graph Neural Networks

Several GNN models are described in the literature. In this paper, we define and consider the Aggregate-Combine (ACGNN) model [Xu et al., 2019; Barcel ´o et al., 2020b]. Some of our results extend straightforwardly to the messaging scheme of MPNN [Gilmer et al., 2017], yet such extensions are out of scope of this paper.

A GNN layer, of input and output (I/O) dimensions p; q, is a pair (F, agg) such that: F is an FNN of I/O dimensions 2p; q, and agg is an order-invariant p-dimension multiset-to-one aggregation function. An m-layer GNN N = ((F1, agg1), . . . , (Fm, aggm)), of I/O dimensions p; q, is a sequence of m GNN layers of I/O dimensions p (i) ; q (i) such that: p (1) = p, q (m) =q and ∀i ∈ [m - 1] p (i+1) =q (i) . It determines a series of m feature transformations as follows: Let a graph G∈GR p and vertex v∈V(G), then N (0) (G, v)�Z(G)(v), and for i ∈ [m] we define a transformation

We notate by N(G, v)�N (m) (G, v) the final output of N for v. We define the size of N to be |N|�Σi∈[m] |Fi| the sum of its underlying FNNs' sizes. We call � (A(F1), agg1), . . . , (A(Fm), aggm) � the architecture of N, notated A(N), and say that N realizes A(N). For an aggregation function agg, we denote by agg-GNNs the class of GNNs for which ∀i ∈ [m] aggi =agg. For aggregation functions agg1, agg2, we denote by (agg1, agg2)- GNNs the class of GNNs with m=2n layers such that ∀i ∈ [n] agg2i-1 = agg1, agg2i = agg2.

2.4 Expressivity

Let p, q∈N, and a set S . Let F ={ f :GS p →ZR q} a set of feature transformations, and let a feature transformation h : GS p →ZR q . We say F uniformly additively approximates h, notated F ≈h, if and only if

The essence of uniformity is that one function "works" for graphs of all sizes, unlike non-uniformity where it is enough to have a specific function for each specific size of input graphs. The proximity measure is additive - as opposed to multiplicative where it is required that � � � � f (G)(v)-h(G)(v) h(G)(v) � � � � ≤ ε. In this paper, approximation always means uniform additive approximation and we use the term "approximates" synonymously with expresses. Although our no-approximation statements consider additive approximation, they hold true also for multiplicative approximation, and the respective proofs (in the full version) require not much additional argumentation to show that.

Let F, H be sets of feature transformations f :GS p →ZR q , we say F subsumes H, notated F ≥H if and only if for every h :GS p →ZR q it holds that H≈h⇒F ≈h. If the subsumption holds only for graphs featured with a subset T p ⊂ S p we notate it as F ≥T H.

Let p, q∈N. We call an order-invariant mapping f :ZR p →R q , from feature maps to q-tuples, a readout function. Both sum and avg are commonly used to aggregate feature maps, possibly followed by an FNN that maps the aggregation value to a final output. We call a mapping f :GS p →R q , from featured graphs to q-tuples, a graph embedding. Let w∈N, let a set of feature transformations F ={ f :GS p →ZR q}, and let a readout r :ZR q →R w , we notate the set of embeddings {r ◦ f : f ∈F} by r ◦ F. We use the expressivity terms and notations defined for feature transformations, for graph embeddings as well.

3 Mean andMax Do Not Subsume

It has already been stated that Sum-GNNs can express functions that Mean-GNNs and Max-GNNs cannot [Xu et al., 2019]. For the sake of completeness we provide formal proofs that Mean-GNNs and Max-GNNs subsume neither Sum-GNNs nor each other.

3.1 Mean andMax Do Not Subsume Sum

Neither Mean-GNNs nor Max-GNNs subsume Sum-GNNs, even when the input-feature domain is a single value.

We define a featured star graph with (a parameter) k leaves, Gk (see Figure 1): For every k ∈N >0:

• V(Gk)={u} ∪ {v1, . . . , vk}
• E(Gk)= � i∈[k]{{u, vi}}
• Z(Gk)={(u, 1)} � i∈[k]{(vi, 1)}

Let N be an m-layer GNN. We define u (t) k �N (t) (Gk, u), the feature of u∈V(Gk) after operating the first t layers of N. Note that u (m) k = N(Gk , u).

Lemma 3.1. Assume N is a Mean-GNN or a Max-GNN . Let the maximum input dimension of any layer be d, and let the maximum Lipschitz-Constant of any FNN of N be a. Then, for every k it holds that � � �u (m) k � � � ≤ (da) m .

Theorem 3.2. Let f :G1→ZR a feature transformation such that for every k it holds that f (Gk)(u)=k. Then, Mean-GNNs � f and Max-GNNs � f .

Note that by Theorem 3.2, a function such as neighborscount is inexpressible by Mean-GNNs and Max-GNNs .

Corollary 3.3. We have that Mean-GNNs ≱ {1} Sum-GNNs, Max-GNNs ≱ {1} Sum-GNNs.

3.2 Mean andMax Do Not Subsume Each Other

Mean-GNNs and Max-GNNs do not subsume each other, even in a finite input-feature domain setting. We define a parameterized graph in which, depending on the parameters' arguments, the average of the center's neighbors is in [0, 1 2 ] while their max can be either 0 or 1. For every k ∈N and b ∈ {0, 1}:

• V(Gk,b) = {u} ∪ {v1, . . . , vk} ∪ {w}
• E(Gk,b) = � i∈[k]{{u, vi}} ∪ {{u, w}}
• Z(Gk,b)={(u, 0)} � i∈[k]{(vi, 0)} ∪ {(w, b)}

Theorem 3.4. Let f :G{0,1} →ZR a feature transformation such that for every k it holds that f (Gk,b)(u)= b k+1 . Then, Max-GNNs � f .

Theorem 3.5. Let f :G{0,1} →ZR a feature transformation such that for every k it holds that f (Gk,b)(u)=b. Then, MeanGNNs � f .

Corollary 3.6. We have that Mean-GNNs ≱ {0,1} Max-GNNs , Max-GNNs ≱ {0,1} Mean-GNNs .

4 Sometimes Sum Subsumes

In a bounded input-feature domain setting, Sum-GNNs can express every function that Mean-GNNs and Max-GNNs can. The bounded input-feature domain results in a bounded range for Mean and Max, a fact which can be exploited to approximate the target GNN with a Sum-GNN. The approximating Sum-GNNs, that we describe, come at a size cost. We do not know if an asymptotically-lower-cost construction exist.

4.1 Mean by Sum

Sum-GNNs subsume Mean-GNNs in a bounded input-feature domain setting.

Lemma 4.1. For every ε>0 and d ∈N >0, there exists a SumGNN N of size O(d 1 ε ) such that for every featured graph G∈G[0,1]⊂R d it holds that ∀v∈V(G) � � �N(G, v) - avg(v) � � � ≤ε.

Theorem 4.2. Let a Mean-GNN NM consisting of m layers, let the maximum input dimension of any layer be d, and let the maximum Lipschitz-Constant of any FNN of NM be a. Then, for every ε>0 there exists a Sum-GNN NS such that:

1. ∀G∈G[0,1] d ∀v∈V(G) |NM(G, v) -NS (G, v)| ≤ε.
2. |NS | ≤O(|NM| + d·m·ad(1-(2ad) m ) ε(1-(2ad)) ).

Corollary 4.3. Sum-GNNs ≥[0,1] Mean-GNNs.

4.2 Max by Sum

Sum-GNNs subsume Max-GNNs in a bounded input-feature domain setting.

Lemma 4.4. For every ε>0 and d ∈N >0, there exists a SumGNN N of size O(d 1 ε ) such that for every featured graph G∈ G[0,1] d and vertex v ∈ V(G) it holds that |N(G, v) - max(v)| ≤ ε.

Theorem4.5. Let aMax-GNNNM consisting of m layers, let the maximum input dimension of any layer be d, and let the maximum Lipschitz-Constant of any FNN of NM be a. Then, for every ε>0 there exists a Sum-GNN NS such that:

1. ∀G∈G[0,1] d ∀v∈V(G) |NM(G, v) -NS (G, v)| ≤ε.
2. |NS | ≤O(|NM| + d·m·ad(1-(2ad) m ) ε(1-(2ad)) ).

Corollary 4.6. Sum-GNNs ≥[0,1] Max-GNNs.

5 Mean andMax Have Their Place

In two important settings, Mean and Max aggregations enable expressing functions that cannot be expressed with Sum alone. As in Section 3, we define a graph Gθ parameterized by θ over domain Θ. We define a feature transformation f on that graph and prove that it cannot be approximated by SumGNNs. The line of proofs (in the full version) is as follows:

1. We show that for every Sum-GNN N there exists a finite set FN of polynomials of θ, those polynomials obtain a certain property φ, and it holds that:

1. We show that for every finite set F of polynomials (of θ) that obtain φ, it holds that:

5.1 Unbounded, Countable, Input-Feature Domain

In an unbounded input-feature domain setting, Mean;Max and other GNNs are not subsumed by Sum-GNNs. We define a graph Gk,c (see Figure 1): For (k, c) ∈N 2 >0 ,

• V(Gk,c)={u} ∪ {v1, . . . , vk}
• E(Gk,c)= � i∈[k]{{u, vi}}
• Z(Gk,c)={(u, 0)} � i∈[k]{(vi, c)}

Theorem 5.1. Let f :GN 1 →ZR a feature transformation, such that for every k, c it holds that f (Gk,c)(u)=c. Then, Sum-GNNs � f .

Corollary 5.2. Denote by S the set of all multisets over N >0. Let g : S →R an aggregation such that ∀a, b ∈ N >0 g( � {a} b � ) = a, that is, g aggregates every homogeneous multiset to its single unique value. Then, Sum-GNNs ≱ N g-aggregation GNNs.

Corollary 5.2 implies a limitation of Sum-GNNs compared to GNNs that use Mean; Max; or many other aggregations.

Graph Embedding

Sum-GNNs are limited compared to Mean; Max; and other GNNs, not only when used to approximate vertices' feature transformations but also when used in combination with a readout function to approximate graph embeddings. Consider another variant of Gk,c: For (k, c) ∈N 2 >0 ,

• V(Gk,c)={u1, . . . , uk 2} ∪ {v1, . . . , vk}
• E(Gk,c)= � i∈[k 2 ], j∈[k]{{ui, vj}}
• Z(Gk,c)= � i∈[k 2 ]{(ui, 0)} � i∈[k]{(vi, c)}

Theorem 5.3. Let f :GN 1 →R a graph embedding such that ∀k, c f (Gk,c)= kc k+1 . Let an aggregation a∈ {sum, avg} and an FNN F, and define a readout ro� fF ◦ a. Then, ro ◦ Sum-GNNs � f .

Corollary 5.4. Denote by S the set of all multisets over N >0. Let g : S →R an aggregation such that ∀a, b ∈ N >0 g( � {a} b � ) = a. Let an aggregation a ∈ {sum, avg} and an FNN F, and define a readout ro� fF ◦a. Then, ro ◦ Sum-GNNs ≱ N avg ◦ g-GNNs.

We have shown that Sum-GNNs do not subsume Mean and Max (and many other) GNNs. The setting though, consisted of an input-feature domain N >0, that is, countable unbounded.

5.2 Finite Input-Feature Domain

Mean and Max aggregations are essential also when the input-feature domain is just a single value i.e. when the input is featureless graphs. We define a new graph Gk,c (see Figure 1): For every (k, c) ∈N 2 >0 ,

• V(Gk,c) = {u} ∪ {v1, . . . , vk} ∪ {w1, . . . , wc}
• E(Gk,c)= � i∈[k]{{u, vi}} � i∈[k], j∈[c]{{vi, wj}}
• Z(Gk,c)={(u, 1)} � i∈[k]{(vi, 1)} � i∈[c]{(wi, 1)}

Theorem 5.5. Let f :G1→ZR a feature transformation, such that for every k, c it holds that f (Gk,c)(u) = c. Then, SumGNNs � f .

Corollary 5.6. Denote by S the set of all multisets over N >0, and let g : S →R an aggregation such that ∀a, b∈ N >0 g( � {a} b � )=a. Then, Sum-GNNs ≱ {1} (Sum, g)-GNNs.

Corollary 5.6 implies a limitation of Sum-GNNs compared to stereo aggergation GNNs that combine Sum with Mean; Max; or many other aggregations. The limitation exists even when the input-feature domain consists of only a single value.

Graph Embedding

Completing the no-subsumption picture, Sum-GNNs are not subsuming, in a 2-values input-feature domain setting, also when used in combination with a readout function to approximate graph embeddings. We define Gk,c: For every (k, c) ∈ N 2 >0 ,

• V(Gk,c)={u1, . . . , uk 2} ∪ {v1, . . . , vk 3} ∪ {w1, . . . , wkc}
• E(Gk,c)= � j∈[k 2 ],i∈[k 3 ]{{uj, vi}} � i∈[k 3 ], j∈[kc]{{vi, wj}}
• Z(Gk,c)= � i∈[k 2 ]{(ui, 0)} � i∈[k 3 ]{(vi, 0)} � i∈[kc]{(wi, 1)}

Theorem 5.7. Let f :G{0,1} 1 →R a graph embedding such that ∀k, c f (Gk,c) = (k 2 +kc)kc k 3 +k 2 +kc . Let an aggregation a ∈ {sum, avg} and an FNN F, and define a readout ro� fF ◦ a. Then, ro ◦ Sum-GNNs � f .

Corollary 5.8. Denote by S the set of all multisets over N >0. Let g : S →R an aggregation such that ∀a, b ∈ N >0 g( � {a} b � )=a. Let an aggregation a∈ {sum, avg} and an FNN F, and define a readout ro� fF ◦ a. Then, ro ◦ Sum-GNNs ≱ {0,1} avg ◦ (Sum, g)-GNNs.

6 Sum andMore Are Not Enough

In previous sections we showed that Sum-GNNs do not subsume Mean-GNNsand Max-GNNs , by proving that they cannot express specific functions. In this section, rather than comparing different GNNs classes we focus on one broad GNNs class and show that it is limited in its ability to express any one of a certain range of functions.

Denote by S the set of all multisets over R, and let an aggregation a : S →R. We say that a is a uniform polynomial aggregation (UPA) if and only if for every homogeneous multiset � {x} b � , x∈R , b∈N >0 it holds that a( � {x} b � ) is either a polynomial of x or a polynomial of (bx). Note that Sum; Mean; and Max are all UPAs. We say that a GNN N =(L (1) , . . . ,L (m) ) is an MUPA-GNN (Multiple UPA) if and only if the aggregation input to each of its layers is defined by a series of UPAs. That is, L (i) = (F (i) , (a (i) 1 , . . . , a (i) bi )), for some bi UPAs.

We define a parameterized graph Gk (see Figure 1): For every k ∈ N >0:

• V(Gk)={u} ∪ {v1, . . . , vk}
• E(Gk)= � i∈[k]{{u, vi}}
• Z(Gk)={(u, 1)} � i∈[k]{(vi, 1)}

Lemma 6.1. Let Aan m-layer MUPA-GNN architecture, let l be the maximum depth of any FNN in A, and let d be the maximum in-degree of any node in any FNN in A. Then, there exists r ∈N such that: for every GNN N that realizes A it holds that N(Gk, u) is piecewise-polynomial (of k) with at most ((d + 1) l ) m pieces, and each piece is of degree at most r.

Lemma 6.1 implies that the architecture bounds (from above) the number of polynomial pieces, and their degrees, that make the function computed by any particular realization of the architecture. With Lemma 6.1 at our disposal, we consider any feature transformation that does not converge to a polynomial when applied to u∈V(Gk) and viewed as a function of k. We show that such a function is inexpressible by MUPA-GNNs.

Theorem6.2. Let f :G1→ZR a feature transformation, and define g(k)� f (Gk)(u). Assume that g does not converge to any polynomial, that is, there exists ε>0 such that for every polynomial p, for every K0, there exists k≥K0 such that |g(k) - p(k)| ≥ ε. Then, MUPA-GNNs� f .

The last inexpressivity property we prove, concerns a class of functions which we call PIL (Polynomial-Intersection Limited). For n ∈N denote by Pn the set of all polynomials of degree ≤n. We say that a function f :N→R is PIL if and only if for every n ∈N there exists kn ∈N such that for every polynomial p∈Pn there exist at most kn - 1 consecutive integer points on which p and f assume the same value. Formally,

We consider every feature transformation f such that for g(k)� f (Gk)(u) it holds that g is PIL. This is a different characterization than "no polynomial-convergence" (in Theorem 6.2), and neither one implies the other. The result though, is weaker for the current characterization. We show that every MUPA-GNN architecture can approximate such a function only down to a certain ε>0. That is, every GNN that realizes the architecture - no matter the specific weights of its FNNs - is far from the function by at least ε (at least in one point). The following lemma is an adaptation of the Polynomial of Best Approximation theorem [Mayans, 2006; Golomb, 1962] which is a step in the proof of the Equioscillation theorem attributed to Chebyshev.

Lemma 6.3. For x, k ∈N define Ix,k �{x, x+1, . . . , x+k-1} the set of consecutive k integers starting at x. Let f :N→R be a PIL, let n ∈N, and define kn �

Then, for every x ∈N there exists εx,kn >0 such that: for every p ∈ Pn there exists y ∈ Ix,kn for which |p(y) - f (y)| ≥ εx,kn . That is, for every starting point x there is a bounded interval Ix,kn , and a gap εx,kn , such that no polynomial of degree ≤n can approximate f on that interval below that gap.

Lemma 6.4. For every q, n∈N there exists a point Tq,n ∈N and a gap δTq,n >0 such that: for every PIL f :N→R, and every piecewise-polynomial g with q many pieces of degree ≤n, there exists y∈N , 0≤y≤Tq,n for which |g(y) - f (y)| ≥ δTq,n . That is, the number of pieces and the max degree of a piecewise-polynomial g determine a guaranteed minimum gap by which g misses f within a guaranteed interval.

Theorem 6.5. Let f :G1→ZR a feature transformation, let g(k)� f (Gk)(u), and assume that g is PIL. Then, for every MUPA-GNN architecture A, there exists εA > 0 such that for every MUPA-GNN N that realizes A there exists k such that |N(Gk, u) - f (Gk)(u)| ≥ ε.

7 Experimentation

We experiment with vertex-level regression tasks. In previous sections we formally proved certain expressivity properties of Sum; Mean; and Max GNNs. Our goal in experimentation is to examine how these properties may affect practical learnability: searching for an approximating GNN using stochastic gradient-descend. With training data ranging over only a small subsection of the true-distribution range, does the existence of a uniformly-expressing GNN increase the chance that a well-generalizing GNN will be learned?

Specific details concerning training and architecture, as well additional illustrations and extended analysis, can be found in the full version 2,3 .

7.1 Data and Setup

For the graphs in the experiments, and with our GNN architecture consisting of two GNN layers (see full version), Mean and Max aggregations output the same value for every vertex, up to machine precision. Thus, it is enough to experiment with Mean and assume identical results for Max.

We conduct experiments with two different datasets, one corresponds to the approximation task in Section 5.1, and the other to the task in Section 5.2:

2 see https://arxiv.org/abs/2302.11603

3 code for running the experiments is found at https://github.com/ toenshoff/Uniform Graph Learning

1. Unbounded Countable Feature Domain (UC): This dataset consists of the star graphs {Gk,c} from Section 5.1, for k, c∈ [1..1000]. The center's ground truth value is c, and it is the only vertex whose value we want to predict.
2. Single-Value Feature Domain (SV): This dataset consists of the graphs {Gk,c} from Section 5.2, for k, c∈ [1..1000]. Again, the center's ground truth value is c, and we do not consider the other vertices' predicted values.

As training data, we vary k ∈ [1..100] and c ∈ [1..100]. We therefore train on 10K graphs in each experiment. Afterwards, we test each GNN model on larger graphs with k ∈ [101..1000} and c∈ [101..1000]. Here, we illustrate our results for two representing values of k: 500, 1000, for all values of c. Illustrations of the full results can be found in the full version. The increased range of k and c in testing simulates the scenario of unbounded graph sizes and unbounded feature values, allowing us to study the performance in terms of uniform expressivity with unbounded features.

7.2 Results

Our primary evaluation metric is the relative error. Formally, if ypred is the prediction of the GNN for the center vertex of an input graph G, with truth label c, we define the relative error as

A relative error greater or equal to 1 is a strong evidence for inability to approximate, as the assessed approximation is nobetter than an always-0 output. It is also reasonable that in practice, when judging the regression of a function whose range vary by a factor of 1000, relative error would be the relevant measure.

Unbounded, Countable, Feature Domain

Figure 2 provides the test results for UC. We plot the relative error against different values of c. Note that the error has a logarithmic scale. Mean-GNNs achieve very low relative errors of less than 10 -4 across all considered combinations of k and c. Their relative error falls to less than 10 -6 when c is within the range seen during training (≤100), Therefore, Mean-GNNs do show some degree of overfitting. Notably, the value of k has virtually no effect on the error of MeanGNNs . This is expected, since mean aggregation should not be affected by the degree k of a center vertex whose neighbors are identical, up to machine precision. Sum-GNNs yield a substantially higher relative error. For k=500 and c≤100 the relative error is roughly 1, but this value increases as c grows beyond the training range. Crucially, the relative error of Sum-GNNs also increases with k. For k = 1000, the relative error is above 1 even when c is within the range seen during training. Therefore, Sum-GNNs do generalize significantly worse than Mean-GNNs in both parameters k and c. '

Single-Value Feature Domain

Figure 2 provides the test results for SV. Again, we plot the relative error against different values of c. Sum-GNNs yield similar relative errors as in the UC experiment. As expected, learned (Sum,Mean)-GNNs do perform significantly better than Sum-GNNs. However, the learning of (Sum,Mean)- GNNs is not as successful as the learning of Mean-GNNs in the UC experiment: relative error is around 10 -1 for k=500, and slightly larger for k=1000, clearly worse than the UC-experiment performance. In particular, the learned (Sum,Mean)-GNN is sensitive to increases in k. Note that each (Sum,Mean)-GNN layer receives both Sum and Mean aggregations arguments and needs to choose the right one, thus it is a different learning challenge than in the first experiment.