Is uniform expressivity too restrictive? Towards efficient expressivity of GNNs
Authors: Sammy Khalife
Josué Tonelli-Cueto
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Neural Networks
Expressivity
Efficiency
Activation Function
Queries
Logic
Primary area: learning on graphs and other geometries & topologies

Abstract: Uniform expressivity  guarantees that a Graph Neural Network (GNN) can express a query without the parameters depending on the size of the input graphs. This property is desirable in applications in order to  have number of trainable parameters  that is independent of the size of the input graphs. Uniform expressivity of the two variable guarded fragment (GC2) of first order logic is a well-celebrated result for Rectified Linear Unit (ReLU) GNNs [Barcelo &. Al, 2020]. In this article, we prove that uniform expressivity of GC2 queries is not possible for GNNs with a wide class of Pfaffian activation functions (including the sigmoid and $\tanh$), answering a question formulated by [Grohe, 2021]. We also show that despite these limitations, many of those GNNs can still efficiently express GC2 queries in a way that the number of parameters remains logarithmic on the maximal degree of the input graphs. Furthermore, we demonstrate that a log-log dependency on the degree is achievable for a certain choice of activation function. This shows that uniform expressivity can be successfully relaxed by covering large graphs appearing in practical applications. Our experiments illustrates that our theoretical estimates hold in practice.

Published as a conference paper at ICLR 2025
Is UNIFORM EXPRESSIVITY TOO RESTRICTIVE? TOWARDS EFFICIENT EXPRESSIVITY OF GNNS *
Sammy Khalifel
khalife.samny@comm @cornell.edu
Josué Tonelli-Cueto*
josue.tonelli. cueto @ bizkaia.eu
ABSTRACT
Uniform expressivity guarantees that Graph Neural Network (GNN) can express query without the parameters depending the size of the input graphs. This property is desirable in applications in order to have a number of trainable param- eters that is independent of the size of the input graphs. Uniform expressivity of the two variable guarded fragment (GC2) of first order logic is a well-celebrated result for Rectified Linear Unit (ReLU) GNNs Barceló al. (222)). In this article, we prove that uniform expressivity of GC2 queries is not possible for GNNs with wide class of Pfaffian activation functions (including the sigmoid and tanh), answering question formulated by Grohe (202I). We also show that despite these limitations, many of those GNNs can still efficiently express GC2 queries in a way that the number of parameters remains logarithmic on the maximal degree of the input graphs. Furthermore, we demonstrate that a log-log dependency on the degree is achievable for a certain choice of activation function. This shows that uniform expressivity can successfully relaxed by covering large graphs appearing in practical applications. Our experiments illustrates that our theoretical estimates hold in practice.
INTRODUCTION
Graph Neural Networks (GNNs) form powerful computational framework for machine learning on graphs, and have proven to be very performant methods for various applications ranging from analysis of social networks, structure and functionality of molecules in chemistry and biological
applications Duvenaud et al. (2015;; Zitnik et al. 2018); Stokes et al. (2020); Khalite et al. (2021). computer vision Defferrard al. (2016), simulations of physical systems Battaglia al. (0016);
Sanchez- Gonzalezz et al. (2020), and techniques to enhance optimization algorithms Khalil et al.
(2017): Cappart et al. (2021) to name a few. Significant progress has been made in recent years to understand their computational capabilities, in particular regarding functions one can compute or express via GNNs. This question is of fundamental importance as it precedes any learning aspect, by asking description the class of functions one can hope to learn via GNN. A better understanding of the dependency of the expressivity on the architecture functions, number of layers, inner dimensions, ...) can also help to select the most appropriate one, given some basic knowledge on the structure of the problem at hand. One common approach in this line of research is compare standard algorithms on graphs a given algorithm is able to distinguish two graph structures, is there a GNN able to distinguish them (and conversely)? The canonical algorithm that serve as a basis of comparison the color refinement algorithm (closely related to Weisfeler-Lehman algorithm). a heuristic that almost solve graph isomorphism Cai et al. 1992). is for example well-known that the color refinement algorithm refine the standard GNNs, and that the activation function has an impact on the the ability of a GNN to refine color refinement Morris al. (2019): Grohe (202T): Khalife Basu 2023).
[aapart
the GNN (activation and aggregation
GNNs. For example, if
'Both authors contributed equally. Order alphabetical.
School of Operations Research and Information Engineering, Cornell Tech, Cornell University, NY, USA 1 DDpartment of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, USA

---

Published as a conference paper at ICLR 2025
The expressivity of GNNs also be compared to queries of an appropriate logic. A first form of comparison relies on uniform expressivity, where the size of the GNN is not allowed to grow with the imput graphs. Given this assumption, first basic question is to determine the fragment of logic that can be expressed via GNNs, in order to describe queries that one can possibly learn via GNNs. For instance with first-order-loicc, one express the query that vertex of graph is part of a triangle. It turns out standard aggregation-combin GNNs cannot express that query, and more generally, a significant portion of the first order logic is removed. The seminal result of GNNs with sum aggregations (E-AC-GNNs) allow express best a fragment of the first order logic (called graded model logic, or GC2), and can be achieved with Rectified Linear Unit (ReLU) activations. Conversely, ReLU E-AC-GNNs can express uniformly queries of GC2. Grohe (203), the author presents more general results about expressivity in the uniform setting, introducing new logical guarded fragment (GFO+C) of the first order with counting (FO+C), in order to describe the expressivity of the general message passing GNNs, when no assumption is made on the activation aggregation function. The author shows that GC2 C GNN S GFO+C, where both inclusions are strict. See Figure | for a representation of the known result for uniform expressivity.
Barceló et al. (2020) states that eegregationncombinn
FO+C
GFO+C
GNNs
X-AC-GNNs = GC2
Figure I: Main logical classes to describe the uniform expressivity GNNs. no restriction is made on the activation and aggregation functions, standard message passing GNNs can express slightly more than GC2 queries, but less than GFO+C queries. The sum-aggregation aggregation combine GNNs (E-AC-GNNs) exactly express GC2 queries.
Evidently, the logic GNNs depends on the choice of architecture. Recent work include the impact of the activation function aggregation function on uniform expressivity Khalife (2023); Rosenbluth al. (003). Grohe & Rosenbluth (2024), the authors also study the expressivity depending on the type of messages that is propagated (message that depends only on the source vs. dependency on source and target vertex). They show that in a non-uniform setting, the two types of GNNs have the same expressivity, but the second variant is more expressive uniformly. Additionally, it was also showed that GNNs with rational activations and aggregations do not allow express such queries uniformly, even trees of depth two Khalife (2023). More generally, complete characterization of the activation function that enables GC2 remains clusive.
By allowing the size of the GNN to grow with the input graphs, it is possible relax the uniform notion of expressivity and ask analogous questions to the uniform case. For instance, what is the portion of first-order logic can express over graphs of bounded order with GNN? What is the required size of a GNN with given activation to do so? In this setup, it becomes now possible that general GNNs express broader class than the uniform one (GFO+C), and that E-AC-GNNs express a broader class than GC2. Such question has been explored in the work Grohe 2023), that describes the new corresponding fragments of FO+C. In particular, the author proves an equivalence between a superclass of GFO+C, called GFO+C mu and general GNNs with rational piecewise linear (rpl)- approximable functions. More precisely, query can be expressed by family of rpl-approximable GNNs whose number of parameters grow polynomially with respect to the input graphs, if and only the query belongs to GFO+Cmu. a more expressive fragment than GFO+C. The GNNs used to prove this equivalence only requires linearized sigmoid activations (r + min(1, max(0, x))) and Σ E-aggregation. Similarly to the uniform case, the set of activation functions that allows maximal expressivity still needs to be better understood. If one restricts to E-AC-GNNs and the well-known GC2 fragment, one can ask for example, given a family of activation functions, how well E-AC-GNNs with those activation functions can express GC2 queries. For example, given activation function,
2

---

Published as a conference paper at ICLR 2025
and integer n, what is the number of parameters of E-AC-GNNs needed to express GC2 queries of depth over graphs of order at most n?
Main contributions. Our first contribution goes towards more complete understanding of both uniform and non-uniform expressivity of GNNs, with a focus on E-ACC-GNNs. We first show that similarly to rational GNNs, there exist a large family of GC2 that cannot be expressed with E-AC- GNNs with bounded Pfaffian activations including the sigmoidal activation x + I+exp[-aj function
that was so far conjectured to be as expressive the ReLU I ~ max(0, æ) units in this setup Grohe 202T]. More precisely, we prove that GNNs within that class cannot express all GC2 queries uniformly, in contrast with the same ones replaced with ReLU activations. Our second contribution adds on descriptive complexity results Grohe (2023) by providing new complexity upper-bounds in the non-uniform case for class of functions containing the Pffafian ones. Our constructive approach takes advantage of the composition power, provideding some simple assumptions on the activation functions, endowing deep neural networks to approximate the step function x: + 1 (x>0) efficiently. Our experiments confirm our theoretical statements on synthetic datasets.
The rest of this article is organized as follows. Section 2 presents the basic definitions of GNNs, Pfaffian functions and the background logic. In Section 3 we state our main theoretical results, in comparison with the existing ones. Section 4 presents an overview of the proof of our negative result that builds on these properties. Section presents the core ideas to obtain our non-uniform expressivity upper-bounds. Technical details including additional definitions and lemmas are left in the appendix. In Section 6 We conclude with some remarks, present the limitations of our work in Section
we present the numerical experiments supporting theoretical results.
2 PRELIMINARIES
Notations. In the following, for any positive integer n. [n] refers to the set {1,... .n). We assume the input graphs of GNNs to be finite, undirected, simple, and vertex-colored with / 2 1 colors: graph is a tuple
= (V) E, A) consisting of a finite vertex set VGG), a binary edge relation E C (G)2 that is symmetric and irreflexive, representing the edges; and map À V(G) [e] representing the colors (or labels). The number of colors is fixed and does not depend on n. In G, (N)(v) will denote the set of vertices adjacent to e in G (not including v). Given function a: R - R. o' will denote the derivative and Λt a o ...... o a (i.e., o² and のN = o og)
the N-th iterated composition of The function log refers the logarithm in base 2.
Definition 2.1 (Neural network). A (k + 1)-layer neural network (NN) with activation function o: R + R with input dimension wy and output dimension Wk+1 is formed by a sequence of + affine transformations
R T
(i (O,..,,,,k)
where wo. w are positive integers. The function that the NN computes is the function
f: RR wi + Ro++1 given by
f = T3 00 1 Tooo
where is applied pointwise for every coordinate of each inner layer's output. The size of the neural network is wo + wi + + W) + Wk+11
Definition 2.2 (Graph Neural Network (GNN)). A GNN is a recursive embedding vertices of graph. At each iteration, the GNN combines the information at the current vertex as well as the aggregated information on the vertex's neighborhood using a neural network. More precisely, a GNN with T iterations, activation function IR IR and input size e is sequence of T combination functions
comb,
d.d x Rd. + Rd+1
(t E (O....,,-11))
that are NNs with activation function a, and where do l. Given a graph G with colors I,..., ......,, the GNN builds T + 1 vertex embeddings (1(v, G) E Rdd (t E (O. T - 1}, E V(G)) as follows:
'The notion of depth will be defined more precisely in Section For the time being, one can think of the depth as measure of complexity measure on the space of queries.
"This definition coincides with sum aggragggeattion- combine GNNs (N-NA-GNNNs) in the literature. In the following, for simplicity, unless state otherwise, we refer to E-AC-GNNs simply GNNs. Some of our results generalize slightly more general class of aggregation functions, Remark B. the appendix.
3

---

Published as a conference paper at ICLR 2025
The initial embedding (e, G) is given by (v, G) ex(n) where e, R is the ith canonical vector and A(u) E [C] the label of v.
iteration i, < ex+1 (v, G) is computed from (", G) via the update rule
(u G) comb; (), wENG(w)
E
S'(w, G)
(1)
The size of the GNN is the maximum size of the NNs given by the combination functions.
In the context of this paper, we will focus on the following activation functions:
ReLU: The Rectified Linear Unit ReLU R Rg is defined (eLU(() max(0,
CReLU: The Clipped Rectified Linear Unit CReLU TR [0 defined by CReLU(x)) min(max(0,,
tanh: The Hyperbolic Tangent tanh (-1.1) given by tanh(x) c--e--
e=
Sigmoid: The Sigmoid Sigmoid R + (0, 1) defined by Sigmoid(z) Ite
Definition 2.3 (GC2 (Barceló et al. 2020 Grohe 2021)). ) A GC2 query is formula with one free
variable obtained from the always true empty formula T and atomic formulas Col(x) (returning I or
for one of the palette colors) through one the following operations
<)(x, ((x) A ((x) and 2Nt y (F((x, v) A d(v))
where is the logical negation, A the logical conjunction, E2M, with N positive integer, means "there exist at least N", and Exx, y) means "rr and are adjacent in the considered graph". The depth, D(-) is a complexity measure of GC2 queries defined recursively
follows: for the always true empty formula T, D(T) = 0; for any atomic formula, (Coll()) = and for the non-atomic formulas, D(-6) = (()) + 1, D( A v) = D(6) + D(v) + and D D(32N y(E(x, y) A o(y)) = D(Ø) + Remark 2.1. GC2 queries are formulas from the so-called guarded model logic (GC), but restricted with two variables. In general, GC formulas are free formulas constructed using Boolean connec- tives, such as and A, and quantifiers that range over the neighbors of the current node, such as 32 yEEy(( y) h(y)).
Remark 2.2. Given our definition, the depth of query depends its writing. For example, if o is GC2 query, @ and á A á express the same GC2 query, but the latter has larger depth.
Definition 2.4. Given graph G. a vertex v and a unary query Q, Q G) = 1 Q(u) is true G and Qu, G) 0 if (v) is false in G.
Example 2.1 (Barceló et al. 2020)). All GC2 formulas define unary queries. Suppose = 2 (number of colors), and for illustration purposes Col, Red, Col, Blue. Then
(x) Blue(x)) By (E(x, v) 322, (E(y, 2) A Red(x)))
queries if z is blue and it has least neighbor with two red neighbors. Then y is in GC2. Now,
8(x) Blue(x) By (-E(a, 3) 3² (E(y, Red(z)))
not in GC2 because the of the guard ( (1, y) is not allowed. However,
rTx) == - (3y (E(x, v) 3 (E(y. x)) Blue(z))))
in GC2 because the negation is applied formula in GC2.
Definition 2.5. [Khovanskii] 1991) Let U C T be an open set. A Pfaffian function a U -> R is an analytic function for which there a 2 and chain of analytic real functions f1, " R such that f, = and that satisfies the following differential equations
fr
0f. 0//0a; = Pi ((())...,,(((
where Pı, E [RI,,,.... Tn, V1, ...... yil are polynomials on (n + i) variables of degree at most Proposition 2.1. tanh and Sigmoid bounded Pfaffian functions.
4

---

Published as a conference paper at ICLR 2025
3 STATEMENT OF THE CONTRIBUTIONS
Our contributions focus on the expressivity of GC2 queries by GNNs.
Definition 3.1. Given a unary query Q and a GNN computing vertex embedding &. we say that the GNN expresses Q over a set of graphs X if there is real < 1/2 such that for all graphs G' X and vertices VG),,
{(v, G) 2 211 1 if (U, = 1 and
E(v, G) S if Qu, G) =
We say that the GNN expresses uniformly Q if X is the set of all graphs.
The following result states the best known upper-bound on the number of iterations and size of GNNs with activation function CRcLU to express GC2 uniformly.
Theorem 3.1. (Barceló al. 2020 Grohe 2027) For every GC2 query Q of depth there is GNN with activation function CReLU, d iterations and size at most 4d that express Q over all graphs. Conversely, any GNN with activation function CReLU expresses GC2 query.
Remark 3.1. We can further restrict the GNN in Theorem 3.1 by requiring its combination functions to be the form comb, (z, y) = CReLU((Az + By + C)) with A E {-1,0, 11,,0,11xx4 1]dxd, B E (-1, 0, 1, ddxd and C z independent of t. Remark 3.2. Theorem admits the partial converse for beyond AC-GNNs Barceló al. (2020): a unary query is expressible by GNN and also expressible in first-order logic, then it is expressible in GC2.
Until now, the question about uniform expressivity has been mainly open for other activation functions such tanh and Sigmoid. Our contributions is two-fold. On the one hand, show that uniform expressivity is not possible. On the other hand, we show that, despite this impossibility, a form of almost-uniform expressivity is achievable.
We briefly overview these two contributions below, giving more details in Sections and
3.1 IMPOSSIBILITY OF UNIFORM EXPRESSIVITY
Definition 3.2 (Superpolynomial), Let f R E be function having a finite limit 8 IR in +00. We say that f converges superpolynomially to iff for every polynomial P E R[X], lim,-++oc (fx) E)
We say that Pfaffian function is superpolynomial if it is non-constant and verifies this condition.
Our first result extends the negative result rational GNNs to the class of bounded superpolynomial Pfaffian GNNs.
Theorem 3.2. Let a
: R R be a bounded superpolynomial Pfaffian activation function. Let & be the output of a GNN with activation function a. Then there a GC2 query Q, such that for any e there exist pair of rooted trees (T.T") of depth 2 with roots (8,8) 8') such that
i) Qs, T) = and Q(*,T')==)))))))
ii) ((S',T')- ((s)) <e
Corollary 3.3. Let a E {Sigmoid, tanh). There exists a GC2 query Q such that no GNN with activation a can express Q uniformly over all graphs.
We want to emphasize that the above query does not depend on the choice of the GNN provided it has this type of activation function.
3.2 ALMOST-UNIFORY EXPRESSIVITY
Our second contribution shows that for large class of activation functionss, which call step-like -ike activation function (see Definition 5.1 in Section SectiionBbllla below) we have almost-uniform expressivity of GC2 queries.
5

---

Published as a conference paper at ICLR 2025
Theorem 3.4. Let be step-like activation function. Then, for every GC2 query Q of depth d and every positive integer A. there is a GNN with activation function o, iterations and size O(d log A) that express Q over all graphs with degree A. Moreover, there exists family step-like activation functions such that the size of the GNN can be further reduced to O log log A).
Corollary 3.5. Let a {Sigmoid, Lanh). Then, for every GC2 query Q of depth and every positive integer A, there is a GNN with activation function a, d iterations and size O(d log log A) that express Q over all graphs with degree < A.
We want to emphasize that the function log log A grows slowly that for almost all theoretical and practical purposes we can consider it to be a constant function, hence our usage of the expression "almost-uniform expressivity".
4 SUPERPOLYNOMIAL BOUNDED PFAFFIAN GNNS: IMPOSSIBILITY
Let us overview why Theorem 3.2 holds, expanding all details in Appendix B Our first result makes use of specific families of input trees that allow us saturate the output signal of GNN by increasing appropriately their number of vertices in certain regions. The input trees, pictured in Figure 2 are carefully chosen in order to return distinct outputs query of GC2. The gist of our proof consists in showing that by increasing the order of the trees in a suitable manner, the output signals of the GNNs of the considered class can be made arbitrarily close. This is achieved by proving a stronger property on all vertices on the trees stated below. To do we first need the intermediate definition:
S, t (++(r-1) R VP TR [X], Vx IR lim PP y -B--1) 0)
where for vectors 2 E Rd, and functions F Rd + R. -llm,-++e F(z) = means that for every
0 there exists 3 2 0, such that min(21." zd) 2 3 implies [F(2) <
2m
leaves
k leaves
k: leaves
Figure 2: Tree T(x, k m] with root
For non-negative integers & and let T(x, k, m]] be the rooted tree of Figure 2 root has m descendants z;, having x; x descendants for = and descendants for 2 For ease of notation, whenever context allows, will refer T(x. k. m) simply T and any of the descendants of z; as 1, For any non non-negative integer t and E V let ('(,,T) be the embedding returned for node by a GNN with bounded superpolynomial Pfaffian activation function after iterations. Let M > 0 be an integer. We will prove by induction on / that for any L (1,...,MM) MM]
In this tree, the
(s(,)T) = + m (2, k. m)
T go(k) + e k)
(1 ge(k) + cx k. m)
(1, () (k) et (x, k m)
(1122, h,(k) kxr
with the following properties:
i) E Rd is constant with respect v. & and m.
ii) Each coordinate 9, and h, are bounded Pfaffian functions of & that depend only on the combination and aggregation functions and the iteration f.

---

Published as a conference paper at ICLR 2025
iii) Each coordinate of the functions Vt. Th, Et. Gl vi are in Sg-
few comments are in order. Recall that S3 is the set of functions R + R such that, for any fixed first argument. the function of the second and third argument tend (collectively) superpolynomially to 0 with respect to the third argument. This asymptotic behavior will arise from our assumptions made on the Pfaffian activation functions, and will be used in our inductive argument. One immediate corollary is that we can decompose the signal at the root vertex into main component and an error term that tends to O when the order of the trees to +00. The main signal v will depend only on the number of iterations, not 2, k. In the other vertices, the main component will only be a function of k. This will prove for instance, that the the two outputs of the GNN on the pair (T(0, k. ml, T[1, ml) m))( (M.m)ena converge the same limit, when i and tend +oo. However, for every k. >> 0, T(0, k. m] and T[1, k, m] have distinct output at the root for the following query:
Q(u) 2 (Ely, 0) (333
A T))))) vy (E(y, v) 3 =²²,E(z,)))
expressing that the vertex v's neighbors have degree at least 2. Note that GC2 can emulate other Boolean connectives (here -) combining the ones has, although it cannot use them directly. Clearly, Q is GC2 query of fixed depth 4. We can easily generalize to any GC2 query for which the root vertex of both trees have different output. In conclusion, the uniform expressivity of GNNs with superpolynomial bounded activation functions is weaker than those of the ReLUs.
TOWARDS EFFICIENT NON-UNIFORM EXPRESSIVITY
Our second result focuses non-uniform expressivity, where the size of the GNN is allowed to grow with the size the input graphs. The result that we obtain holds for the wide class of activation functions defined below, and to any other activation function that express them through neural network. This class (See Lemma C.I Appendix is characterized by a fast convergence to the linear threshold activation function
0
if < 1/2
0- (x) = 1/2
if 1/2.
1 if 1/2
Recall that denotes the derivative of a and N = a .... its N-th iterated composition.
Definition 5.1 LSkep-Like Activation Function), A step-like activation function is C2-map o R I satisfying for E [0, 1), E e (0, 1/2), N E N and H 0 the following:
(a) (0) = 0 and (11) 1.
(b) o (0)), (o)) <
(c) for all & (e, 1 - e), |oo (x) -
a. ox(x) mints, (1 n)/HH
(d) for all N (R. (c,1-E)), (o"()) H.
Remark 5.1. Seeing Ø R + R as discrete dynamical system, (a) and (b) translate into and 1 being attractive fixed points; (c) says that, after N iterations, every point in R \ (-e,e) F), the complement of (-s,e), is in the attractive region of either 0 or 1; and (d) provides a bound on constant related to the size these attractive regions.
Our main contribution presented Theorem 3.4 4 can be deduced from its technical version stated the theorem below. All proof details are relegated Appendix C
Theorem 5.1. Let be step-like activation function. Then, for every GC2 query Q of depth d and every positive integer & there a GNN with activation function o, d iterations and size
2 log( A + +2) log + 11)
3
that express Q over all graphs with degree < A. Moreover, if 1 the size of the CNN can be further reduced to
(3+ N log(2 + log(A 2))) d.
7

---

Published as a conference paper at ICLR 2025
Remark 5.2. The logarithmic dependence of the GNN's size the degree A of the considered class of graphs guarantees that the GNN has a reasonable size for applications. Moreover, if = 0. then we have log-log dependency, which for whichever practical setting is an almost constant function. Remark 5.3. Our proof further shows that only the width of the combination function depends on the depth d of the query, and that the number of layers remains independent of d.
Now, to give meaning to the above result, we will prove the following proposition giving us a way of constructing step-like activation functions out of tanh and Sigmoid.
Proposition 5.2. There is a step-like activation function ō arctan with r 0.64, 0.1, NN 0 and H 1.52 that can be expressed with a 3-layer NN with activation function arctan of size 3.
Proposition 5.3. There is step-like activation function tanh with nj H 2.2 that can be expressed with 4-layer NN with activation function tanh of size 6.
0.2, N and
Proposition 5.4. There is a step-like activation function Sigmooi with lj = 0, E = 0.2, N = 0 and H 2.2 that can be expressed with 4-layer NN with activation function Sigmoid of size 6.
Using these propositions, we get the following two important corollaries of Theorem 5.1 to get the almost-uniform expressivity of GC2 queries for tanh and Sigmoid, for which uniform expressivity is not possible due to Theorem 3.2
Corollary 5.5. For every GC2 query Q of depth d and every positive integer A, there is a GNN with activation function arctan, d iterations and size most (10 + 3.5 log( A 2)) d that expresses Q over all graphs with degree S A.
Corollary 5.6. For every GC2 query Q of depth d and every positive integer A, there a GNN with funattion Q over all graphs with degree S A.
activation function tanh, d iterations and size at most (9 + 4 l2 + log( A + 2))) d that expresses
Corollary 5.7. For every GC2 query Q of depth d and every positive integer A, there is GNN with activation function Sigmoid, d iterations and size at most (9 + 4log2 + log(A + 2))) d that expresses Q over all graphs with degree I A.
NUMERICAL EXPERIMENTS
In this section, we demonstrate how the size of the neural networks impacts the GNN's ability to express GC2 queries via two experiments.
6.1 QUERIES
In our experiments, we consider the following two queries:
Q1(0) (32) y (E(y, v) A (- (E(u,)) A AT)))) by by (E(y,u) + +3222E(2 v)) and
Q2(v) Red(t)) (E(z, v) (3 (E(v, x) Blue(r))) A (32) (E(v, A Red(v)))
One can see that Q1 (v) expresses that all neighbors of v have degree at least two, and Q2(v) that is red and has a neighbor that has a red neighbor and a blue neighbor. Moreover, Q1 has depth 4 and Q2 has depth 7. Note that Qi applies even to graphs with any number of colors, while Q2 applies to graph having at least two colors.
6.2 EXPERIMENTAL. SETUP
Computing and approximating queries. For the first experiment, our set of input graphs is composed of pairs of trees (T kt m),T(L, , k m)) ml) presented in Section 4 These are unicolored for Q and colored follows for Q2: the root and the r, are red, and the leaves are blue. We compare for i E [2], the two following GNNs:
(a) The ReLU GNN that exactly computes the query Qi-
We use the construction of (Barceló et al., 2020). specified in the proof of Theorem [5.] where each of the GNNs has the same combination function in each iteration. For Q1, the ReI.U GNN has 4
8

---

Published as a conference paper at ICLR 2025
iterations (depth of Q1); and for Q2, the ReLU GNN has 7 iterations (depth of Q2). The combination functions are of the form
comb, (x, v) = (e + By + C):
where x, E R., t E C' are specified in Appendix D
d 1) and = for Q1 and d = 7 for Q2. The parameters A, B and
(b) The Pfaffian GNN with activation function: a + 1/2 (2/m) arclan (ar - 1/2) that expresses
Qi non uniformly.
We use the construction in the proof of Theorem 5.1 where as the GNNs above, the combination functions are all the same. In this case, the combination functions are of the form
comb, (x, v) of (Ar + By+ + +
where x, y E Rd, E the same the ones of the ReLU counterparts, given in Appendix [D] Note that this is NN with & +2 2 layers, where l of the layers have width d and one has width 2d.
1). =4 for Q1 and = 7 for Q2. and the parameters A, B and
We report for different values of and number of vertices of the graphs inputs (which function of k and m)) how close the two outputs of the Pfaffian GNNs, on the tree inputs T k; ml and T[1, k; ml. Since the root of these trees have respectively and 1 as output of the query Q, the ReLU GNN constructed will have a constant gap of 1. Theorem 3.2 states that these outputs will tend to be arbitrarily close when the order of the graph increases, for fixed L. addition, Theorem 3.4 tells us that the number of iterations should impact exponentially well how large graphs can be handled to be given level of precision of a gap 1.
Civi=All neighhors have dogree least
Ofvi-v neighbor
neighbor
Scparal betwren a4tte-
AeLL
PetUi
Platier
Ptafton 1-4
Plaffinn
ieuttin
Plaffian
iaaffan Im:3
Plaffon I-12
1200
2002
2002
2000
500
1000
1520
2000
2500
3000
3500
4000
Number
(a) Q1
(b) Q2
Figure 3: Separation power of CReLU GNN vs. Pfaffian GNN above as function of the graph size
Learning queries. For the second experiment, we compare the GNN's ability learn GC2 queries, depending on the activation considered (ReLU vs. Pfaffian). We consider the same two queries as above and train two distinct GNNs: (a) A first GNN with Sigmoid activation function, and (b) A second GNN with CReLU activation functions. Both GNNs have 4 and 7 iterations when trained to learn the first and second query respectively. Each iteration attributed his own combine function, feedforward neural network with one hidden layer. This choice is justified by our theoretical results that one can either compute exactly GC2 query (with the ReLU one), or approximate it efficiently (with the Pfaffian one) with only one hidden layer for the combine function. Our training dataset is composed of 3750 graphs of varying size (between 50 and 2000 nodes) of average degree 5, and generated randomly. Similarly, testing dataset is composed of 1250 graphs with varying size between 50 and 2000 vertices, of average degree 5.
The experiments conducted Mac-OS laptop with Apple MI Pro chip. The neural networks were implemented using PyTorch 2.3.0 and Pytorch geometric 2.2.0. The details of the implementation provided in the supplementary material.

---

Published as a conference paper at ICLR 2025
6.3 EMPIRICAL RESULTS
Figure 3 reports our results for the first experiment. As our theory predicts, the CReLU GNN designed with the appropriate architecture and weights is able to distinguish the source vertices of both trees with constant precision I, regardless of the number of vertices. On the other end, the Pfaffian GNNs struggle to do separation for values of < 8 (recall that is the number of compositions, i.c. the number of layers in the combinations functions) for graphs of than 1500 vertices. As the value of 'nncreasss slightly to 10 for the first query and 12 for the second, the capacity of these GNNs dramatically increases to reach a plateau close to for graphs up to 4000 vertices. This also illustrates our second theoretical result prediciting that the step-like activation functions endow GNNs efficient approximation power of GC2 queries.
Figure Tigure@reports reports the mean square error on our test set for learning the same two queries. We observe that the error is similar for both GNNs, with slight advantage for Pfaffian GNNs. This suggests that better uniform capacities does not imply that learning the queries is getting casier, given the same architecture and learning method. One potential reason is numerical: the combination functions using step-like activation functions used in our approximation of GC2 queries have likely to have large gradients. We suspect this adds the difficulty to efficiently train these networks to optimality, despite their ability to approximate queries to an arbitrary level of precision.
Qlv)=All neigbhors of have degree at least
Qtv)-v red and has a naightor that has blue and red neighbor Rautten
irattion
Clipped
0.25
clpped PaL
Hoen erter by grgh
0.30
0.20
0.25
0.33
0.30
Viau
0.30
0.05
0.00
250
800
750
1000
1350
1500
1750
2000
250
300
150
1:00
3250
1500
1730
2000
Rumber of vertices
N.mbar
Q1
(b) Q2
Figure 4: Learning queries with Pfaffian GNN vs ReLU GNN.
The mean square error per graph on the test set is displayed as a function of the order of the graph.
DISCUSSION AND OPEN QUESTIONS
Uniform expressivity is desirable property when some information on the function query to learn available. Structural information may allow to design the GNN appropriately in a hope to express the query by selecting the correct weights, for example after learning from samples. In this study, we showed that many activation functions are not as powerful as CReLU GNNs from a uniform standpoint. This limitation is counterbalanced by the efficiency of many activations (including the Pfaffian ones that are weaker than CReLU) for non-uniform expressivity, where one allows the number of parameters to constantt with respect to the input graphs. Therefore, we argue that despite being desirable, uniform expressivity has to be complemented by at different measures for thorough study on the expressivity of GNNs.
Moreover, it is frequent that one does not know in advance the structure of the query to be learned. Even when knowing the appropriate architecture for which approximate expressivity is guaranteed, learning the appropriate coefficients can be challenging illustrated in our numerical experiments. However, these experiments are only preliminary and constitute by no means an exhaustive exploration of all the architectures and hyperparameters to learn those queries. As such, hope this study will constitute a first step towards provably efficient and expressive GNNs, and suggest new directions to bridge the gap between learning and expressivity.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
Sammy Khalife gratefully acknowledges support from Air Force Office of Scientific Research (AFOSR) grant FA95502010341, and from the Office of Naval Research (ONR) grant N00014-24-1 2645. Josué Tonelli-Cueto is thankful for the generous generous support of the Acheson J. Duncan Fund for the Advancement of Research Statistics, grant 25-28. Josué Tonelli-Cueto thanks Jazz G.
Suchen for useful discussions during the write-up of this paper, particularly regarding Proposition C.3 and Brittany Shannahan and Lowie-Napolcon for emotional support.
REFERENCES
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan-Pablo Silva. The logical expressiveness of graph neural networks. In 8th International Conference on Learning Representations (ICLR 2020), 2020.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. Advances in neural information processing systems, 29, 2016.
Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound the number of variables for graph identifications. Combinatorica, 12(4):389 410, 1992.
Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. arXiv preprint 2042::2002.09544,, 2021.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
Martin Grohe. The logic of graph neural networks. In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1-17. IEEE, 2021.
Martin Grohe. The descriptive complexity 2023.
complext of graph neural networks. arXiv preprint arX1v:2303.04613,
arXiv preprint Martin Grohe and Eran Rosenbluth. Are targeted messages more effective? arXiv:2403.06817 2024.
Sammy Khalife. The logic of rational graph neural networks. arXiv preprint arXiv:2310.13132 2023.
Sammy Khalife and Amitabh Basu. On the power of graph neural networks and the role of the activation function. arXiv preprint urXiv:2307.04661 2023.
Sammy Khalife, Thérèse Malliavin, and Leo Liberti. Secondary structure assignment of proteins in the absence of sequence information. Bioinformatics Advances, 1(1):vbab038, 2021.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Askold G Khovanskiï. Fewnomials, volume 88. American Mathematical Soc., 1991.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 4602-4609, 2019.

---

Published as a conference paper at ICLR 2025
Eran Rosenbluth, Jan Toenshoff, and Martin Grohe. Some might say all you need is sum. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pp. 4172-4179, 2023.
Alvaro
Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovec, and Peter Battaglia. Learning to simulate complex physics with graph networks. In International conference on machine learning, pp. 8459-8468. PMLR, 2020.
Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae Zohar Bloom-Ackermann, et al. A deep learning approach to antibiotic discovery. Cell, 180(4):688-708 7028888--22220 2020.
A. J. Wilkie. A theorem the complement and some new o-minimal structures. Selecta Mathematica, New Series, 5:397-421, 1999. doi: 10.1007//00029900500552 URL https://doi.org//O0 10. 1007/ s000290050052
Marinka Zitnik, Monica Agrawal, and Jure Leskovec. Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics, 34((3):1457i4466
2018. 2018.
A FACTS ABOUT PFAFFIAN FUNCTIONS
The following three results are folklore the theory of Pfaffian functions. We finish with proof of Proposition 2.1
The first proposition is just a direct consequence the so-called o-minimality of Pfaffian func- tions Wilkie (1999). which guarantees that Pfaffian systems share with polynomial systems their finiteness properties amaong which we have the finiteness of sero-dimensional zero sets. The first lemma is easy consequence of the chain rule and the definition of Pfaffian functions. The second and third lemmas follow from the proposition, but we include a proof for completeness.
Proposition A.1. Let f R > be Pfaffian function. Then f either constant or has finitely many zeroes in R.
n
Lemma A.2. The addition, multiplication, composition and derivatives of Pfaffian functions are Pfaffian.
I
Lemma A.3. Let J + IR be Pfusfian and bounded function. Then f has a finite limit in +00.
Proof. By Lemma A.2 since f is Pfaffian, so is f'. Hence, by Proposition A.1 either f' is constant, and f = 0, f has finitely many zeros. In the first case, f is constant and it trivially has limit. In the second case, let R > 0 be such that (R, oo) does not contain any zero of f". Then either I' is strictly positive strictly negative on (R, oo). and either f is strictly increasing or strictly decreasing on (R, oo). Hence, by the supremum axiom of the real numbers, we have that
lim f(x) = sup v E (R, o0) 2-000
ff is strictly increasing on (R, oo), or
lim f(x) (n) 1 (R,
if f is strictly decreasing on (R, oo). Since f is bounded, the right-hand side is finite in both cases. Thus f has a finite limit in +oc.
Lemma A.4. A bounded Pfaffian function f IR R has a bounded derivative.
Proof. By Lemma A.2 f and f" are Pfaffian, because f is Thus, by Proposition A.1 f and f" have a finite number of zeros-if any them are constant, then f cannot bounded. Hence there is R > 0 such that all the zeros of f. f and f" are inside (-R, R). In this way, since f' is bounded on any bounded interval, we only need to prove that f is bounded on [R oo) and on (-o0, - R]. Without loss of generality, we will focus on the former case.
Assume, without loss of generality, after multiplying f and the variable X by -1 if necessary, that f(R) and f' (((R)= 0. Now, either have that f" is positive negative the whole [R, oc),
12

---

Published as a conference paper at ICLR 2025
and for all [R. f()) (R) 0f f' positive, 0 f'(x) - f(R), if f negative. In the first case, for x 2 R.
S d' f(R) (a (x-)))
f(z) f(R)
goes infinity oc, which contradicts assumption f. Thus, are in the second case, in which f is bounded as desired.
L
Now, we end with proof of Proposition 2.1
Proof of Proposition 2.7 is easily shown.
The only part requiring proof is that they are Pfaffian, that they are bounded
We have that tanh'
tz)) and that Sigmoid' (x) - - Sigmoid(z)² In this way,
tanh' (x) = P(z, tanh(x))
with P(z,8) = 1 - y², and
Sigmoid' (x)) = P(x, e" Sigmoid(#)), e =
with P(x, y1: U2) = - v1v2 and Q(x, y) = y, show that tanh and Sigmoid are Pfaffian.
Alternatively, since
tanh(x) = (igmoid(2z) and Sigmoid(z) (a/h)(222)//)
it would have been enough to show that either tanh or Sigmoid is Pfaffian to conclude that the other so, by Lemma A.2
B PROOF OF THEOREM 3.2 AND COROLLARY 3.3
Proof of Theorem 3.2 We consider the set of activation functions
fo
R + R: : a is Pfaffian, bounded and superpolynomial)
where the notions above where given in Definitions 2.5 and 3.2 functions of fast decay in the last variable:
Let S, be the set of IR" + IR
S, = {o ( R VP E R
[X),
Vr E R
P())-1)(( "1. .Br-1) =0} ++0
lim
where for functions F; IRd R. lim F(2) = 0 means that for every e there exists / 2 such that min(21,." 22) implies [F(2)] <
For non-negative integers l and m, let T(x, k. m] be the rooted tree of Figure 2 in which the root has descendants r;, having 2; descendants if of notation, we will refer to T(x, k, m] simply as T and to any of the descendants of æ; as 4,- For any non-negative integer and V(T), let (u, T) be the embedding returned for node v by GNN with activation function E E after iterations. Let M > 0 be an integer. We will prove by induction on & that for any E (1..... M):
1 and descendants if i > 2. For ease
{s,,, T) Ut + n. (2, k. k)
( T) 9)(k) + e e k m)
('4422, T) h₂(k) + vı(a, k, k)
(((2), = (.(k)) + < ki m)
g (l,,,T) = (.( + ot (z, k, m)
with the following properties: a) v R4 is constant with respect to and b) each coordinate of Se and h, are bounded Pfaffian functions of & that depend only on the combination and aggregation functions and the iteration i, and each coordinate of 14, Mes 6t, e, of are in S3.
13

---

Published as a conference paper at ICLR 2025
In the remaining of the proof we explicitly treat the case of one- die-dimensional embeddings (i.e. dN 1 for every E [T) for ease of notation. Our proof extends to multi-dimensional embeddings with the three additional ingredients:
i) considering only one input variable and the rest fixed, each coordinate of a combine function given by neural network with activation function = is bounded Pfaffian function that is constant or superpolynomial (see Lemma A.2)). Therefore, one can also use in that case Corollary A.1 on the zeroes of these functions, as we do in the one-dimensional case.
ii) the error terms of each signal can be controlled using norms of the Jacobian matrix instead of the gradient, as we shall next.
iii) Given a bounded multivariate Pfaffian function f. for any fixed reals \ Ay- f(Am,, Agm,.... A,)) has a limit when m + +00. This follows from the fact that the univariate function I + f(Ai2, λ2T, ... A,.)) is Pfaffian bounded.
Base case: Obvious all embeddings are initialized 1.
Induction hypothesis: Suppose that for some integer / 2 O, for every S t:
The above system of equation is verified.
ii) Jur ha are Pfaffian and bounded functions.
iii) Mus Bus Eur c and v Sz.
Induction step: For the remaining of the proof, for convenience we drop the dependency on of comb, and simply write comb. which is neural network with some activation E E. First note that comb has bounded derivatives as the derivative
bounded Pfaffian function also bounded, see Lemma A.4 Let Kcomb supzeR2 [00,, comb(x)) az,, comb(z)]l2.
The update rule for the leaves writes
gt- (4:2, T = comb comb("((4,,)) (4, (x;,
comb(h, + (1 m), g (k) (x(,k,m)) comb(h.(k) gr (k)) + (1, k))
h(-1(k) + + m)
where
|p (I, m)] = ( + vi m), (k) + er k, m)) co))(
K comb (,,, (u k, m), (1, m))
< K Koomb 22 (x, k m), c(x h m))lla
similarly, g++l (1, T) comb (h, (k)) 9 (k)) t m) where ue4a (Jr, k m) ccomb(h, (A: + o/ (xc, k, m)) g: (k) (a, k; m)) co For the intermediary vertices, we have
g g++ (1222, 7) comb(g' (N,, T), 5" (s. 7) + k: 7))
comb(g (k) + (2r, k, m), vr n (1 ki m) + k(ha(k)) + v4(x,, kx),
comb(g (k), 1/2 + (k)) + (2,1
9 (k) ct+1 kr.
Let A == (2, k. m) + ku, (a, k. m))
let11m (k)) = comb (k) + (x, k, m), + A + kha((k)) - comb(g((k), v2 + kk)()))
Kcomb (E, A: m), All
Similar inequalities can be derived for (1 T). Finally, for the root we have
gl+2 (8, T) = comb(s' T), Σ St (xi, ((n,T) T))
comb(u; (1 + ne(a, k, m) gr (x) + (m (k)( + ct kt m) + (m 1)e((r, (,))k))))) comb()t, (m (k)) 1211 k. k)
14

---

Published as a conference paper at ICLR 2025
Using Corollary A.1. for every {1..... t 1}, 9u is either constant equal to on R or has zeroes after some rank. Therefore, there exists an integer le such that for every k; 2 k* and every {1.... + 1.. one of the following cases holds:
Case a) (k.) 0.
Case b) (k.) < 0.
Case c) 9u 0 on R.
We remind the reader that a similar case discussion here extends to the multidimensional case, i.c. when the function 9u take vectorial values, and when the combine function has multi-dimensional co-domain, see for example comment ii) Note that we can select a common B = k- for each iteration. Now, suppose that |A] 2 3.
By continuity of comb and 9i having limit in -00.
Ve 0, AM, Vk 2 3, Vm 2 M, |comb(u:, (z) + (m ():)) - 11 S
where / limy comb(u,, y) case a) and limy-+-o comb(ut, (z, y) if case b), and ( comb(e', 0) otherwise (case c). Hence
g! (s. T) = comb(ur. Ur (x) + (m 1)g. (k)) + (2; k, m)
[lim xo comb Uz, v) + 7 (z) m) limy-++o comb (v,, y) + 7 k m) comb(u,, 0) + M (Ix, k, m)
if gk(t) < 0 if go gk
otherwise
where Mh+1 met1 + n- In the third case the induction step goes through immediately. In the following, we suppose without loss of generality that ge (k*) >> 0, with
(2, k m)] == |comb(uz U2 + (x k m.) ge (x) + (m ())) + c k. m)
+ (m - (z, k m)) comb(u: Uz (z) + (m - (A))
and
(2) M141 (ar, k m)) combbor....oooooooooo.o. + (m - (k)) - lim comb(v,, v) +o+
First, it is clear that ni: (xx, k. m) can be made less than for some m, due to the existence of the limit limy-++ox comb(w,, v) and that ge (k)) chosen
non zero (for every after rank k* chosen above). Furthermore, 1h41 is still in S3 as for every fixed æ,K > k* the function m + comb(u, Ue. ge (z) + (m (m- 11): tends superpolynomially fast to its limit, due to the assumption made on the activation function and again from the fact that ge (k) F 0 for every & 2 k*. Second,
(2)
| (2x, k m)l s Koomb v2ll k, m), & (2, k, m) + (m 1)e k, ml)
We see that for this part the error terms of and get multiplied by We know by the induction hypothesis that for every polynomial P.
VE > 0, 33, Vm 2 3,
3 S |k|
=
[P(m)es(Z, S.
In these conditions ( k. m)] S The property is still verified at rank t+ 1 as (m(m((m- [)e, k. m)l < (m(m)(m (x, k, m) where Q(X) = (X - P(X) is polynomial.
((m)
By the triangle inequality, 1m (k)) S |/ 1.m (A)) + 1m+1..m (k)). and so the desired property follows (after splitting the in half) and ends the induction.
Remark B. The above proof can be generalized for more general GNNs that use aggregation functions more general than sums. In particular, the proof above can be adapted to any aggregation function agg, that admits limit in {-o0, +00) when the size of the multiset with repeated entry grows to +o0.
Proof of Comollar 3 This follows from Theorem 3.2 and Proposition 2.1
15

---

Published as a conference paper at ICLR 2025
C PROOFS FOR SECTION 5
C. PROOF OF THEOREM 5.1
Let overview the proof of Theorem 5.1 First, will show that the constructive proof of (Barceló
ct al. 2020 Proposition 4.2) for CReLU holds for the linear threshold activation function o, defined in equation After this, we will exploit that for fast convergence of step-like function (see
Definition 5.1 of converges fast to as the following lemma shows.
Lemma C.1. Let a be a step-like activation function. Then for all & (e, - E) and all 2 N,
11+1
8-N
(4)
2
Moreover, further 0, then for all x & (-,1-6) E) and all f N.
(x) oz. 22
(5)
Proof of TTheorem 5.7 Let Q be a query of GC2 of depth d, and let (Qi,..., Qa) an enumeration of its subformulas, being each Qi an atomic formula or formula build from the previous ones. Without loss of generality, assume that Q uses all & S d colors and that the first subformulas Q1..... Qe are the atomic formulas
corresponding these & colors. If this is not the case, then Q involves E' S. E colors, say AI...., dg, and so in the sequence (Q....., Qa). we will only have the atomic formulas Colx, appearing. Thus to make the construction below work, we only need to reorder the subformulas and to perform the constructions below changing the color X; to the color i in the formulas and change the and the first combination function combo from A and B to AP and BP where the coordinate projection mapping ex; to ej.
Colx, (x)
First, we extend the constructive proof of (Barceló et al., 2020 Proposition 4.2) to GNNs with linear threshold activations σ.. In this extension, we have to make sure we can control the error made efficiently The GNN that we will build has iterations, being each combination functions of the form
comb; (x. v) + (Ax + C) (t E fo.....d-11 1})
where A and B are d x d matrices and C d-dimensional vector C. The jth row of A, B and C will correspond to the corresponding subformula Q2 and they will be filled as follows:
1) Q is the atomic formula corresponding the color Aj. then AJ,,, otherwise, Bj = 0 for all & E [d]. and C₁ = O. Note that by our assumption, the first l rows of A those of the identity matrix, and so the first é components of the embeddings give the color of the vertex.
for k X, and AJ, 0
2) If (x) =>k (F(r, y) A (v)) for some j, then AJ,a - for all & [d]. Bj,; 1 and B₁ = 0 for # i, and C -(K -1
3) (x) =
(E(x, v) A T), then Ay,* = 0 for all & E [d], By = 1 for & e [(] and B =
for k & [f], and
and C- -(K 1)
4) = -Q((x) with j. then AJ.a = -1 and Aj,x = 0 for h: + i, By, = 0 for all k E [d]
and C;=11
Q)(() = -T then A₁. = BB,+ = 0 for all E [d] and C = 0.
6) (x(x)) Qx, (x) ^ Q1, for some i, i2 j. then Ay,i Aj,z2 1 and Ay,: 0 for k * 11,22 B,, = 0 for all j E [d] and Cj- = =-1. -1
7) If 1f)) (x(x) AT (z( T Q((x)) for some j. then AJ, 1 and AJ,x 0 for
k # B, for all j E ld] and C = O.
'The original proof to exactly compute the query can actually be extended for any function g: R + R verifying: there exists real < b such that i) for every real a, g(z) = O. ii) for every real x 2 g,)(z) = and fii) g is non-decreasing on (a, b).
16

---

Published as a conference paper at ICLR 2025
8) (z) TA then AJ,t By, for all j E [d] and C =
For any integer E {o....,e d - 1} and for every graph G and each vertex v V(G) of G. consider
(v, G) comb; (g((,C))
E q'(w, ((m..C)) wENa(1)
(6)
Observe that for each [d], (1 G) E 10.1)" With the exact same inductive argument as in (Barceló al. 2020. Proposition 4.2), we have that for E [d] and all
[4].
df(v, G) (v G),
ie., the first & components of the embedding q (t, G) are equal to the first subformulas QI,..., Qt of Q.
Now, we will now consider the GNN where we have substituted o, by its approximation of. The new GNN will have combination functions of the form
comb (z, 8) + (Ax + By +) C)
(t (o....,
with A, B and C' as above, and it will construct the vertex embedding (v, G) given by the update rule
+ G) comb,
(v,
E (w G)
wEN((()
Observe that comb, a neural network with input size 2d, output size d, + layers and widths 2d, d, ... d, and so size (e + 2)d.
Let be a positive integer and fix graph G with maximal degree bounded by A. For E (0,...,d}. we define
:=:=
max 11 G) 4' (v. Go vEV(G)
We shall prove that, under the assumptions of the theorem, the following claim:
Claim. For any & (O....,d
1+m L-N
if > 0 if 0
2(4 + 2)4 < 1, then c+1 I
Under this claim, using induction, we can easily show that if either
2 log( A + 2)
7 > and 2 N +
1 log(1 + 7)
7 = 0 and l 2 N log(22 log(A 2)),
then Ea S. 1/3 < 1/2. Effectively, under any of the above assumptions, have that
2(A + 2)a
2(A 2) <1
by the claim and the fact that s < 1/2. Since eo = 0, we conclude, by induction, that
if 1/3 < 1/2.
Ed <
if =
22
providing the expressivity. Note that the size of the above GNN is + m, and so the statement of the theorem follows.
17

---

Published as a conference paper at ICLR 2025
Now, we prove the claim. For t {0, ...., d 1} we have, by the triangle inequality, that
1 (u, G) - (w, G)
c++1
max vEV(G)
max ve vVV(G)
comb
(),
Σ
("( G)
comb,
d'(u,)), E
Le G)
in mENo(v)
wENo(U)
100
< max vEV(G)
comb
(),
Σ
5'(,, G)
comb,
()(,,)) Σ
{w, G)
w wENo(v)
wENo(u)
+ max vEV(G)
comb,
(),
E wENG(o)
<'(w; G) comb, (), Σ
d',, G)
wENo(V)
The first maximum of the last inequality is bounded above by
sup {|| c/mmb/// (I, y) comb; (z, v) for all i, 24 $ (Et, 1 - Et), & (De, 1 1 DEi)].
since each component of (", G) at distance at most e, from 0 by definition of Et. Now, comb, (x, y) = of (Ax+ Bx++C) and comb, (z, y) = a. (Ar+ BB++ with A, B E ((-1,,0 1] and C' _ Moreover, the matrix A has at most two non-zero entries per row, and B most one non-zero entry. Since the 1-norm each row of is at most 2, and the one of at most 1, we can improve the upper-bound with
dxd
sup {lo (z)- - a. (=) = & ((A + 2) (A + 2)
By assumption, this quantity is bounded from above by the claimed by Lemma
For the second maximum, define
x = (, G) and y =
Σ
(ww, G)
wENc(v)
and
d' = ( G) and o' = Σ
d'm G)
wENo(e)
to simplify notation. By definition of es, we have
|| -rr=xlles 2' S and lyy 3'1oo I Ae..
Now, arguing as above regarding A, and Br, have that
- B(y- 5 112+Ap1 A)E. In this way, Ar + By + C' is real vector with no-norm < 1/2 to the integer vector Ar' + By +C and so we conclude that
[|(rr By + C* (Az' + By' + Cl ||A( x +
comb(I, y) = comb(x', yz)),
because a, takes the same value on an integer and on a real number at distance less than 1/2 from Hence the value of the difference under the second maximum is zero, proving the claim.
To prove Lemma C.I we will need the following well-known lemma.
Lemma C.2. Let f IR R be C2 C2-function, To E R fixed point of f (ie., f(Fo) zo) and r r> iff = y < 1, supre (aoo (ooelloo-ree +2)++]] 1 (t) = > 0 and
Hr < 1-11)
then for every integer 2 0 and x E [10
r, T0 + rr).
1 11 "
1 11+1)
n
1f zal S
xx - xol 5
2
Moreover, in = O, then for all n and x E
[Do
r, 2y + r]
2"
(x) - 3ol <
H
1r
2 <
r
2
22 -
18

---

Published as a conference paper at ICLR 2025
Proof of Lemma C.1
Fix & (e. E) and let (1- By (c), have that
lo (r) (x) r with Hr I 1 Hence, since (x))) is a fixed point of a, by (a), we have, by
Lemma C.2 (b) and (e), that
a- (x))
converges to zero with the desired speed.
Proof of Lemma Let H suPre (mo- z- (t)) Then we have that S 7 and so for I E [o0 r, 20 + r). we will have, by Taylor's s theorem, for some s between x and zo.
f(x) zu + n(x ma) + 1 fs) xp)²,
2
where we write To since Tn = f(xo). Rearranging the expression and taking absolute values,
If(x) zol S n/| zol + H xul - (1 n 2
Hr
l zul.
2
since [s)(s)] H and | zol S r. Now, by assumption, Hr/2 /2 S 1-
and so
11
[fx)) - vol
|x: zol-
2
For the case 0, we have instead
H
[f(z) zo
S
1
vol2
2
Hence in both cases, induction on ends the proof.
C.2 PROOFS OF PROPOSITIONS 5.2
5.3
AND 5.4
We now focus on Proposition 5.2
5.3 and 5.4
First, we prove Proposition 5.2 Second, we show that
2 follows from Proposition more precise Proposition C.3
5.3
Third and last, we prove Proposition 5.3 by proving the
We just need to consider arrttan (x)) 2 + 2 Arctan((x 1). Then simple computation shows that the given claim true.
Proof of Proposition 5.2
we can express tanh as a NN with activation function Sigmoid. Hence, we can transfor Tanh into diigmoid by substituting each x (anh(x) by & 2 2igmoii((2x) - 1. A Simple counting finishes the proof.
Proof of Proposition 5.4 By equation 3
Observe that Proposition 5.3 follows from the following precise proposition that we will prove instead.
Proposition C.3. Let
taanh (x) tanh(x d 1/2)
ttanh1/2)
and
Lannh(2ax a) - a tanhh4aa 2a)) + tanh(6ar - 3a) 2(tanh(a) - a tanh(2a) + tanh(3a))
Ttank (z) == Granh
+ 2
where a E (0.45, 0.46) and (3.14,3.15) are such that
sech (w) sech ( (3xx)
sech?(a) sech sech? a.
min
I R
soch? (2x)
sech ((a))
Then o Oranh and taanh are step-like activation functions functionn with, respectively, 17 = 0.86, E = 0.16, N = and H 0.84, and y 0, 0.2, N 0 and H 2.2.
19

---

Published as a conference paper at ICLR 2025
Proof. The claim about Granh (2) follows after simple numerical computation. For the claim about Taan (I) observe that
taanh (x) Ttanh (Tanh(((3)))
where, by the choices above, we have that:
(0) ((0) = 0, 7(1) = 1.
(1) T is strictly increasing.
(2) 7 (z) = 0 if and only i E 10,
Hence Taanh is fixes 0 and 1, is strictly increasing and, by the chain rule, satisfies 1) 0. The rest of the constants are found by numerical computation.
C.3 PROOFS OF COROLLARIES 5.5 5.6 AND 5.7 AND COMPOSITE NN
Proof of Corollary 5.5
This is a combination of Theorem 5.1
with Proposition
5.2 using Proposi-
tion below.
Proof of Corollary tion below.
5.6
This is a combination of Theorem 5.1 with Proposition 5.3 using Proposi-
Proof of Corollary
5.7
This is combination of Theorem 5.1 with Proposition 5.4 below.
Proposition C.4. Let R. + R and ō I. + R be functions. If can be written in terms of a NN with activation function a with + 2 layers of widths I,T1,..., Te, 1, then every NN with activation function ō with k + layers of widths Wa...., Wk+1 be transformed into a NN with activation function a with 2 + {k 1) layers of widths
Wo, w1 ri, Witt, W2T1, W2T', Wgr',..... WK'T', Wk+1-
In particular, ō can be written in terms of NN with activation function of size T, then every NN with activation function ē of size can be transformed into a NN with activation function a of size at most (r- 2)s.
Proof. Let the NN with activation function have affine transformations T, R 204 R wi+t
E (O.....k) and the NN with activation function o that expresses have affine transformations S, RT g (i ( + 1}), where to T++2 1. Then, IR R map have
ō S S. .... S So.
but, as pointwise R + R map, we can write ă as
2 now o 0
St
where 5@e is the map R R RC++0 w given by
(((1))
R
(R
E (RR"41)" R"
Se(www)
Fw
In this way, considering the NN with activation function with affine transformation
To. SQ coous
Spon
Ti
g80m S+1
S
S
S
cow2 To a S8+1
S
S
T
80wk-1 S S441
S@un Th S
transform the NN with activation function ē into NN with activation function with the desired characteristics. The claim about the size is immediate. Note that if r = 2, then is an affine map and the claim is still true.
20

---

Published as a conference paper at ICLR 2025
D NUMERICAL EXPERIMENTS
Computing and approximating queries. For Q1, the ReLU GNN has 4 iterations with A, and c
given by
0 0
0
0
0
0
0
0
0
0
0
1
A =
B
C
0 0
0
0
0
1
0
0
Note that since are in the unicoloring setting, all vectors are initialized e1.
For Q2, the ReLU GNN has iterations and A, B and c: are given as:
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
B
0
0
0
0
.C
1
0
0
0
0
0
0
0
0
0
Note that vertices are initialized to ej or e2 depending on whether they are colored red or blue.
21


Reviews:
[{"review_id": "mBHdmT86qr", "reviewer": "Reviewer_ir8P", "summary": "This is a theoretical work about the connection between GC2 and GNNs with various activation functions. Its first contribution is to prove that uniform expressivity is not possible for GNNs with bounded Pfaffian activations. The second contribution is to build non-uniform expressivity for GNNs with Pfaffian activations via a constructive approach. Some synthetic experiments are provided to verify the theoretical arguments.", "questions": "Please see the above concerns.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The motivation is good: rigorously understanding the expressive power of GNNs is a significant direction, especially it requires carefully quantify expressive capacities with sizes and depths. This work follows this motivation.\n2. A rich family of activation functions is considered (such as arctan, tanh, sigmoid), as an extension of previous works about positive and negative results with simpler activation functions. And the general definition of Pfaffian functions makes it possible to generalize to other activations in the future.\n3. The presented theory in the main text looks good.\n\nNote that I didn't check all the proof in the appendix.", "weaknesses": "1. The presentation seems incomplete in some places, so thorough proofread and revision are necessary. For example:\n    * in theorem 3.1, the last sentence is confusing in grammar.\n    * in line 197, ''two blue neighbors'' should be ''red''.\n    * in line 195, 199, 202, please check whether the parentheses are complete or not.\n    * in line 279, the last sentence is not complete.\n    * in Figure 2, $l_i$'s are missing. I suppose they are the leaf nodes.\n    * around line 318, notations are not consistent, where line 685 uses $\\nu_{t,m}(k)$ instead of $\\nu_{t}(k,m)$\n    * in line 363, what is the meaning of $\\\\sigma^N(R\\\\setminus (\\\\epsilon, 1-\\\\epsilon))$?\n    * in Corollary 5.5, tanh -> arctan\n    * in Figure 3, please use different linestyles for easiness of reading, instead of only using different colors\n    * in line 495, a ''second'' shall be removed\n2. around 335, the mentioned $T[0,k,m]$ and $T[1,k,m]$ seem to assume the tree in Figure 2 is rooted tree from $s$ without backtracking, which means $s$ is not in the leaf nodes. If so, please clarify this when defining the tree.\n3. in line 495, please clarify how this layer argument is connected with theoretical results. Does it mean the different layers for activation functions in Prop 5.2-5.4?\n4. in line 500, the conjecture about SGD is too sudden without evidence", "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": "", "extra_scores": {}}, {"review_id": "GfRkW86pFs", "reviewer": "Reviewer_ikke", "summary": "The paper aims to more closely characterize the uniform approximation capabilities of graph neural networks as a function of the activation functions applied to each aggregation of messages. There are primary theoretical contributions:\n1. While previous results suggest that bounded-size guarded model logic (GC2) queries can be expressed by fixed-size GNNs with CReLU activations, Section 3.1 proves that certain GC2 circuits cannot be expressed by GNNs with sigmoid and tanh activations (or more generally, for superpolynomial Pfaffian activations). This limits the universality properties of GNNs. The proof involves constructing pairs of tree graphs whose outputs will be identical as a result of their activations.\n2. However, Section 3.2 shows that all bounded-size GC2 queries can be expressed by a GNN whose size grows slowly as a function of the graph degree for sigmoid and tanh activations (and more generally, for \"step-like activations\").\n\nThey validate their theoretical results by training GNNs to learn two synthetic GC2 queries on different graph sizes. These experiments reveal sharp thresholds between the abilities of different activations to distinguish between similar graph instances.", "questions": "In general, (approximate) linear threshold activations are not practical in neural networks because of lack of bounded derivatives. Are the authors concerned about the learnability of their constructions in Section 5 that simulate threshold activations?\n\nWhat is the significance of the parameters $H$ and $\\epsilon$ on the construction in Theorem 5.1? The other parameters seem to have influence on size complexity, but not those.\n\nLikewise, do know whether the network weights for Theorem 5.1 can be bounded?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The results of the paper are well-motivated theoretically---it is interesting to understand the trade-offs of different activations and the limitations of universal approximation. In particular, such fine-grained separations between constant-size and near-constant-size architectures are interesting, seeing as most graphs are small enough for the $\\log\\log\\Delta$ scaling to be surmountable. \n\nAs far as I can tell, the mathematical results are correct. The proof ideas of distinguishing similar tree graphs and constructing separations with step-wise activations are intuitive.", "weaknesses": "In general, the presentation of the results would be improved by more context for Pfaffian and step-like activations. A more close linkage between tanh and sigmoid and the parameters of Pfaffian chain of order would appreciated, along with more examples of step-like activations and an intuitive discussion of their parameters.\n\nWhile individually unimportant, there are several areas with ambiguous notation or minor mistakes that I would appreciate the authors clarifying:\n* Definition 2.3 and Example 2.1 have some inconsistent notation, e.g. $E$ and $Edge$ are used interchangeably, and $\\exists^{\\geq p}$ is not defined (although it is fairly intuitive). The formula in Example 2.1 appears to indicate that at least one neighbor has at least two neighbors that are _red_, not blue.\n* Definition 2.4 introduces a Pfaffian chain of order, but not Pfaffian functions. The relationship between the two should be made explicit.\n* In Theorem 3.1, \"Conversely, any (aggregation-combine) GNN expresses with activation function CReLU expressed a\nGC2 query\" does not parse.\n* Grammar nit on line 250: \"superpolynomial if it non constant\".\n* On line 291, what is the $y$ limit over? $y$ appears to be vector-valued.\n* If Definition 5.1, does the $\\sigma^N$ notation reference exponentiation or composition?", "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": "", "extra_scores": {}}, {"review_id": "daOmYHeb0X", "reviewer": "Reviewer_Mu1a", "summary": "In the study of GNN expressivity, it is crucial for practical usage to take the number of parameters needed into consideration. To this end, uniform expressivity has been proposed to test whether GNNs can express a query with the number of parameters independent on the size of the input graphs. However, in this paper the authors found that uniform expressivity tends to be too restricted for a wide class of GNN models. This paper then relaxes the concept of uniform expressivity into almost-uniform expressivity and further show that most GNNs can be still quite expressive when restricting the number of parameters to be logarithmic on the maximal degree, satisfying most practical needs. The results in this paper are justified by both theoretical analysis and numerical experiments.", "questions": "Please refer to Weakness. There are some concerns that limit the impacts of the theory in this paper. I am willing to change the score if the concerns / problems are properly discussed / solved.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- Compared with general expressivity measurement of GNNs, uniform expressivity sometimes tends to be too strict, thus provides negative results for GNNs: as shown in this paper, MPNNs with sigmoid activations cannot uniform express GC2 queries. To this end, it is nice to find a balance between general expressivity (which does not consider the number of parameters) and uniform expressivity (where the number of parameters is independ w.r.t. input graphs) for practical needs. The log complexity of parameters described in this paper is realizable for most practical situations.\n- This paper considers a wide class of activations, defined as step-like activation functions. The authors show that their results are applicable for many practical activation functions including sigmoid and tanh.", "weaknesses": "- The study in this paper relies on the definition of step-like activation functions. The properties of step-like activation function still requires more discussion. Specially, I have some concerns regarding the definition of step-like activation functions:\n  - The Relu function ReLU(x)=max{0,x} clearly is not a step-like activation function since it disobeys (a): $\\sigma(1)=1$. A question naturally arises: is the set of all possible step-like activation functions large enough to cover up most situations (or further, is it possible to find the maximal set of activation functions that satisfies Theorem 3.4)?\n  - In Definition 5.1, I assume in (b), $\\sigma'$ is the derivative of $\\sigma$. What does $\\sigma^N$ in (c) mean? I searched over the paper but couldn't find an explanation.\n  - To derive Corollary 3.5 from Theorem 3.4 it is necessary to show that sigmoid and tanh are special cases of step-like activation functions with $\\eta=0$. However, Proposition 5.3 and Proposition 5.4 states that only a 3-layer NN with tanh and a 5-layer NN with sigmoid can be step-like activations. If this is the case, it largely restricts the structure of GNNs: the results in this paper are only applicable to MPNNs whose activations are again multi-layer NNs. This setting should be mentioned in the former parts of the paper when defining GNNs.\n  - Continuing from the above concern. In Proposition 5.3 (and similarly in Proposition 5.4), a 3-layer NN is needed to express step-like activation function. Note that an activation function is a **point-wise** function that applies independently to each element of the input vector. How does the 3-layer NN behave like a poin-wise function to the input vectors in the whole GNN computation procedure? For example, let $X=[x]$ be the input and $W=[w_1,w_2]^T$ be the parameter at first layer. The output is $[w_1 x,w_2 x]^T$. If the dimension input is changed to be $X=[x_1,x_2]$, how does this reflect to $W$? To me this can be done by setting $W=[[w_1,w_2,0,0]^T,[0,0,w_1,w_2]^T]$ but this makes the number of parameters in each layer linerly grows w.r.t. the input dimension ( and thus makes the total number of parameters $O(d^2)$). Please correct me if I am wrong.\n\n## Minor Issues:\n- Corollary 5.5, 5.6, 5.7 all considers tanh activation. Should this be changed to arctan, tanh and sigmoid respectively?\n\n## Suggestions:\n- This paper can be further strengthened by discussing more complex GNN variants, e.g. higher-order GNNs. I suspect the number of parameters is logarithmic w.r.t. $N^{k-2}$ for $k$-order MPNNs, with $N$ being the number of nodes.", "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": "", "extra_scores": {}}, {"review_id": "0sutyEARbX", "reviewer": "Reviewer_6aa7", "summary": "This papers studies the following fundamental question. Any node binary classification task can be defined as a logic formula. The paper tries to understand whether common GNN architectures can learn a given logic formulas **uniformly** (over all graphs with unbounded size). This is in stark contrast with prior research, which typically allows the model size to grow with input graph size. The authors gave both negative and positive results, showing that GNNs with sigmoid/tanh activations cannot uniformly approximate GC2 logic formulas, but they can almost-uniformly approximate them. The authors gave both counterexamples and constructions in their proof. Finally, they conduct experiments to verify their results.", "questions": "I am curious about the insights behind the theoretical results. I suspect this may be due to the sigmoid/tanh function is bounded, so it can not  express a quantity that grows with input size. On the other hand, ReLU/CReLU is not bounded. I wonder whether any unbounded non-linear activation is sufficient for uniform expressivity?\n\n\nMiscellaneous：\n1. Definition 2.4: U should be $U$.\n2. Page 7, line 350: the word \"the\" is redundant.\n3. What is the difference between Corollaries 5.6 and 5.7? I suspect there is a typo here.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "I would like to say this is a quite interesting paper and I like it a lot. First, this paper studies GNN expressivity from a novel perspective. Unlike prior work which largely focuses on graph isomorphism (which is mainly TCS/graph theory perspectives), this paper is clearly more relevant to real neural network architectures instead of abstract color refinement algorithms, making it especially relevant to the community. On the other hand, this paper differs from traditional function approximate theory, as these theories often let the model size to grow in order to approximate better with a larger input domain. Instead, this paper gives both positive and negative results on whether a *fixed* model can deal with graph learning tasks for all inputs. This ability is unique for graph learning tasks.\n\nSecondly, the paper provides a rigorous theoretical foundation. All definitions and statements are well-defined and accessible, which enhances clarity. I find the results nontrivial and impactful, and it enhances our understanding in the community.", "weaknesses": "One potential weakness of these results is that almost-uniform expressivity is perhaps already sufficient. Therefore, the limitations of sigmoid/tanh networks is not that severe in practice. So this paper may have a limited impact in guiding practical design of GNNs.\n\nUpdate: I should acknowledge that I am not very familiar with first-order logics beyond the paper of Barcelo (2020). I am not sure if similar ideas have been raised in prior work (possibly under a different community).", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)