The logic of rational graph neural networks

## Abstract

Abstract. The expressivity of Graph Neural Networks (GNNs) can be described via appropriate fragments of the first order logic. Any query of the two variable fragment of graded modal logic (GC2) interpreted over labeled graphs can be expressed using a Rectified Linear Unit (ReLU) GNN whose size does not grow with graph input sizes [ BKM + 20 ] . Conversely, a GNN expresses at most a query of GC2, for any choice of activation function. In this article, we prove that some GC2 queries of depth 3 3 3 3 cannot be expressed by GNNs with any rational activation function. This shows that not all non-polynomial activation functions confer GNNs maximal expressivity,
answering a open question formulated by [ Gro21 ] . This result is also in contrast with the efficient universal approximation properties of rational feedforward neural networks investigated by [ BNT20 ] . We also present a rational subfragment of the first order logic (RGC2), and prove that rational GNNs can express RGC2 queries uniformly over all graphs.

## 1. Introduction

Graph Neural Networks (GNNs) are deep learning architectures for input data that incorporates some relational structure represented as a graph, and have proven to be very performant and efficient for various types of learning problems ranging from chemistry [], social network analysis [], bioinformatics and protein-ligand interation [, ], autonomous driving [, , ], and techniques
to enhance optimization algorithms [, ] to name a few. Understanding the ability of GNNs to compute, approximate or *express* functions over graphs, and the dependence of their capacity on the activation function is beneficial for every aspect of learning: from the understanding of the target class, the design of a GNN for a given task, to the algorithmic training. For example, certain activation functions may yield more expressive GNNs, or require less parameters to express the same functions.

In this context, several approaches have been conducted in order to describe and characterize the expressive power of GNNs. The first approach consists in
comparing GNNs to other standard computation models on graphs such as the color refinement or the Wesfeiler-Leman algorithms. These comparisons stand to reason, because the computational models of GNNs, Weisfeiler-Leman, and color refinement algorithms are closely related. They all operate under the paradigm of inferring global graph structure from local neighborhood computations. In that regard, it has been proven [, ] that the color refinement algorithm precisely captures the expressivity of GNNs. More precisely, there is a GNN distinguishing two nodes of a graph if and only if color refinement assigns different colors to these nodes. This results holds if one supposes that the size of the underlying neural networks are allowed to grow with the size of the input graph. Hence, in his survey, [] emphasizes the fact that this equivalence has been established only for unbounded GNN, and asks: *Can GNNs with bounded size simulate color refinement?* In [], the authors answer by the negative if the underlying neural network are supposed to have Rectified Linear Unit (ReLU) activation functions. In [] the authors provide a generalization of this result, for GNNs with piecewise polynomial activation functions. Furthermore, explicit lower bounds on the neural network size to simulate the color refinement can be derived for piecewise-polynomial activation functions given upper bounds on the number of regions of a neural network with piecewise-polynomial activation.

The second line of research to study the expressive power of GNNs is to characterize the types of boolean queries that a GNN can simulate. Given a boolean query $Q$ interpreted over labeled graphs, is there a GNN whose output characterizes the output of $Q$? For example, can a GNN express if a vertex of a graph is part of a clique of given size? Furthermore, can we characterize the set of queries that can be simulated by GNNs? If the number of parameters of the GNN does not depend on the size of the input graph, the GNN is said to express the query *uniformly*. Beyond theoretical considerations, uniform expressivity is also relevant from a practical standpoint as it captures the expressivity of GNNs with a fixed number of parameters with respect to the number of vertices in the input graphs. The suitable logic over labelled graphs for GNNs is a two variable fragment of graded model logic, referred to as GC2. Any GNN expresses a query of this logic, and conversely, any query of this logic can be expressed by a GNN whose size and iterations only depends on the depth of the query [, ]. For specific activation functions such as ReLUs, the size of a GNN required to express a given query of GC2 does not depend on the size of the input graph, but only on the number of subformulas (or depth) of the query. Proofs of this result [, ] provide an explicit construction of a GNN with ReLU activations that expresses a given query. In recent results [], the author provides a non-uniform description of the logic expressible by GNNs with rational piecewise-linear activations (or equivalently, rational ReLUs). The non-uniform result is presented for GNNs with general arbitrary real weights and activation functions. The author also presents new results about the expressivity of GNNs if random initialisation is allowed on the features of the vertices. In [], the authors compare the impact of the aggregation function on the expressivity of GNNs, showing that GNNs with Max or Mean aggregation functions have distinct expressivity from the Sum aggregation GNNs. In this article, we focus on uniform expressivity and consider the following question: *What is the impact of the activation on the logic uniformly expressed by GNNs?*

A natural start for such investigation are polynomial activations. They have demonstrated clear limitations for feedforward Neural Networks (NNs) as exposed with the celebrated theorem of approximation [], stating that polynomial activations are the *only ones* leading to NNs being unable to approximate any continuous function on a compact set. For example, in the case of NNs, rational activations do not share this limitation and allow to approximate continuous functions on a compact set. Beyond this ability, rational activations yield efficient approximation power of continous functions [], if one is allowed to consider different rational activation functions (of bounded degree) in the neural networks. In the same spirit, this article exposes a comparison of the power of the activation function in the case of GNNs. In particular, we will compare rational activations, with those of piecewise linear activations whose expressive power is known.

Main contributions. In this work we present an additional step towards a complete understanding of the impact of the activation function on the logical expressivity of GNNs. We show that the class of GNNs with *rational activations* (i.e. all activation functions that are fractions of polynomials) have weaker expressivity than piecewise polynomial activations (including ReLUs). For theoretical and practical considerations, we limit our study to fractions having *no real pole*. We prove that GNNs with rational activations cannot express all GC2 queries uniformly over all graphs, while they can with ReLU GNNs. Our approach also shows this result holds even if: i) the weights of the rational GNNs are arbitrary real numbers with infinite precision, and ii) the weights of the ReLU GNNs are restricted to integers (also, the underlying neural networks are supposed to have finitely many linear pieces). This result holds for sum-aggregation function, but can be extended to any aggregation function that is rational with bounded degree. This shows how the power of graph neural networks can change immensely if one changes the activation function of the neural networks. These results also seem to suggest that ReLU GNNs possess special ability for uniform expressivity over rational GNNs, a property in contrast with the efficient approximation power of rational NNs []. In addition, we describe a fragment of GC2, called RGC2, that rational GNNs can express. Our proof shows that polynomial GNNs can express this fragment as well, and we conjecture that it is only very close to the one that rational GNNs express at best. We would like to point out that this work focusses solely on the ability of classes of GNNs to express given queries (i.e. can we even find a GNN in the class that does the job?). In particular, we do not address in this work the question of *learning queries*, and the impact of the activation function on learning, namely from a sample complexity standpoint.

The rest of this article is organized as follows. Section 2 presents the definitions of GNNs and the background logic. In Section 3, we state our main result and compare it to the existing ones. Section 4 presents an overview of the proof of our main result, as well as proofs of the technical lemmata are presented. We conclude with some remarks and open questions in Section 6.

## 2. Preliminaries

### 2.1. Graph Neural Networks (GNNs)

We assume the input graphs of GNNs to be finite, undirected, simple, and vertex-labeled:
a graph is a tuple $G=(V(G),E(G),P_{1}(G),\allowbreak\cdots,P_{\ell}(G))$ consisting of a finite vertex set $V(G)$, a binary edge relation $E(G)\subset V(G)^{2}$ that is symmetric and irreflexive, and unary relations $P_{1}(G),\cdots,P_{\ell}(G)\subset V(G)$ representing $\ell>0$ vertex labels. In the following, we suppose that the $P_{i}(G)$’s form a partition of the set of vertices of $G$, i.e. each vertex has a unique label. Also, the number $\ell$ of labels, which we will also call colors, is supposed to be fixed and does not grow with the size of the input graphs. This allows to model the presence of features of the vertices of input graphs. In order to describe the logic of GNNs, we also take into account access to the color of the vertices into the definition of the logic considered, as we shall see in Section 2.2. For a graph $G$ and a vertex $v\in V(G)$, $N_{G}(v):=\{y\in V(G):\{x,y\}\in E\}$ is the set of neigbhors of $v$. If there is no ambiguity about which graph $G$ is being considered, we simply use $N(v)$. $\lvert G\rvert$ will denote the number of vertices of $G$. We use simple curly brackets for a set $X=\{x\in X\}$ and double curly brackets for a multiset $Y=\{\{y\in Y\}\}$. For a set $X$, $\lvert X\rvert$ is the cardinal of $X$. When $m$ is a positive integer, $\mathfrak{S}_{m}$ is the set of permutations of $\{1,\cdots,m\}$. $\lVert.\rVert$ is the Euclidean norm, i.e., for a vector $x\in\mathbb{R}^{m}$, $\lVert x\rVert:=\left(\sum_{i=1}^{m}x_{i}^{2}\right)^{1/2}$. Finally, if $E$ is a real vector space, $I$ a subset of $E$, $\mathsf{span}\{I\}$ refers to the set of all finite linear combinations of vectors of $I$, i.e. $\mathsf{span}\{I\}:=\{\sum_{i=1}^{m}\lambda_{i}x_{i}:\lambda\in\mathbb{R}^{m},
x_{1},\cdots,x_{m}\in I,m\in\mathbb{N}-\{0\}\}$.

[(Symmetric) rational fractions/functions]
For a positive integer $m$, $\mathbb{R}(X_{1},\cdots,X_{m})$ refers to the field of rational fractions over the field $\mathbb{K}=\mathbb{R}$. For any positive integer $m$, a rational fraction is a pair $(P,Q)$ (represented as $\frac{P}{Q}$),where $P,Q\in\mathbb{R}[X_{1},\cdots,X_{m}]$ are multivariate polynomials. The *degree* of $R$ is the pair $(\mathsf{deg}(P),\mathsf{deg}(Q))$. A rational fraction $R\in\mathbb{R}(X_{1},\cdots,X_{m})$ is said to be symmetric if for any permutation $\pi\in\mathfrak{S}_{m}$ of $\{1,\cdots,m\}$ and any $v_{1},\ldots,v_{m}\in\mathbb{R}$, $R(v_{\pi(1)},\cdots,v_{\pi(m)})=R(v_{1},\cdots,v_{m})$. In following, we make no formal distinction between rational fractions and rational functions, defined as functions taking values as the ratio between two polynomial functions. We also restrict our GNN study to fractions having no real pole, i.e. the polynomial $Q$ has no root in $\mathbb{R}^{m}$.
{defi}[Neural Network (NN)] Fix an activation function $\sigma:\mathbb{R}\to\mathbb{R}$. For any number of hidden layers $k\in\mathbb{N}$, input and output dimensions $w_{0}$, $w_{k+1}\in\mathbb{N}$, a $\mathbb{R}^{w_{0}}\rightarrow\mathbb{R}^{w_{k+1}}$, a Neural Network (NN) with activation function $\sigma$ is given by specifying a sequence of $k$ natural numbers $w_{1},w_{2},\cdots,w_{k}$ representing widths of the hidden layers and a set of $k+1$ affine transformations $T_{i}:\mathbb{R}^{w_{i-1}}\rightarrow\mathbb{R}^{w_{i}}$, $i=1,\ldots,k+1$. Such a NN is called a $(k+1)$-layer NN, and has $k$ hidden layers. The function $f:\mathbb{R}^{w_{0}}\rightarrow\mathbb{R}^{w_{k+1}}$ computed or represented by this NN is:

$$ $f=T_{k+1}\circ\sigma\circ T_{k}\circ\cdots T_{2}\circ\sigma\circ T_{1}.$ $$

In the following, the Rectified Linear Unit activation function $\operatorname{ReLU}:\mathbb{R}\rightarrow\mathbb{R}_{\geq 0}$ is defined as $\operatorname{ReLU}(x)=\max(0,x)$. The Sigmoid activation function $\operatorname{Sigmoid}:\mathbb{R}\rightarrow(0,1)$ is defined as $\operatorname{Sigmoid}(x)=\frac{1}{1+e^{-x}}.$

[Graph Neural Network (GNN)]
A GNN is characterized by:

- $\circ$
A positive integer $T$ called the number of iterations, positive integers $(d_{t})_{t\in\{1,\cdots,T\}}$ and $(d^{\prime}_{t})_{t\in\{0,\cdots,T\}}$ for inner dimensions. $d_{0}=d^{\prime}_{0}=\ell$ is the input dimension of the GNN (number of colors) and $d_{T}$ is the output dimension.
- $\circ$
a sequence of combination and aggregation functions $(\mathsf{comb}_{t},\allowbreak\mathsf{agg}_{t})_{t\in\{1,\cdots,T\}}$. Each aggregation function $\mathsf{agg}_{t}$ maps each finite multiset of vectors of $\mathbb{R}^{d_{t-1}}$ to a vector in $\mathbb{R}^{d^{\prime}_{t}}$. For any $t\in\{1,\cdots,T\}$, each combination function $\mathsf{comb}_{t}:\mathbb{R}^{d_{t-1}+d^{\prime}_{t}}\longrightarrow\mathbb{R}
^{d_{t}}$ is a neural network with given activation function $\sigma:\mathbb{R}\longrightarrow\mathbb{R}$.

The update rule of the GNN at iteration $t\in\{0,\cdots,T-1\}$ for any labeled graph $G$ and vertex $v\in V(G)$, is given by:

$$ $\xi^{t+1}(v)=\mathsf{comb}_{t}(\xi^{t}(v),\mathsf{agg}_{t}\{\{\xi^{t}(w)\,:\,w \in\mathcal{N}_{G}(v)\}\})$ $$

Each vertex $v$ is initially attributed an indicator vector $\xi^{0}(v)$ of size $\ell$, encoding the color of the node $v$: the colors being indexed by the palette $\{1,\cdots,\ell\}$, $\xi^{0}(v)=e_{i}$ (the $i$-th canonical vector) if the color of the vertex $v$ is $i$.
We say that a GNN has rational activations provided the underlying neural network $\mathsf{comb}$ has rational activation functions.

###### Remark 1 .

The type of GNN exposed in Definition 2.1 is sometimes referred to as *aggregation-combine* GNNs *without global readout*. Here are a few variants that can be found in the litterature:

- •
*Recurrent* GNNs, where $\mathsf{comb}_{t}$ and $\mathsf{agg}_{t}$ functions do not depend on the iteration $t$. The results presented in this article extends to recurrent GNNs as any aggregation-combine GNN without global readout can be reduced polynomially to a recurrent one.
- •
GNNs *with global readout*, for which aggregation functions also take as input the embeddings of all the vertices of the graph. See Remark 6 for known results from a logic standpoint.
- •
General *Message-passing* GNNs that allow operations before the aggregation on the neigbhors as well as the current vertex (*targeted* messages). We refer to [] for a some elements of comparison of expressivity of targeted vs standard ones.

###### Remark 1 .

### 2.2. Logical background: GC2 and queries

In this subsection we present the logical foundations for queries in graph theory. We refer the interested reader to Appendix B containing details for the general construction. Let $\ell>0$ be a fixed number of colors, and let $G=(V(G),E(G),\allowbreak P^{1}(G),...,P^{\ell}(G))$ be a colored graph. The first-order language of graph theory we consider is built up in the usual way from a *alphabet* containing:

- •
the logical connectives $\land,\lor,\lnot,\rightarrow$
- •
the quantifiers $\forall$ and $\exists$
- •
equality symbol $=$
- •
the *universe* $A$ of the logic is given by $A:=V$
- •
variables $x_{0},x_{1},\cdots$ (countably many)
- •
the *vocabulary* $S$ is composed of:
$\circ$
a binary edge relation symbol $E$: $(x,y)\in A^{2}$ are related if and only if $(x,y)\in E$.
$\circ$
unary relation symbols $\mathsf{Col}_{1},\cdots,\mathsf{Col}_{\ell}$ indicating if a vertex has a given color

The set of *formulas* in the logic is a set of strings over the
alphabet. To interpret these formulas and the logic over every graph, we need for each graph a map $I$ defined on the relations:

- •
for every $i\in[\ell]$, $I(\mathsf{Col}_{i}):A\rightarrow\{0,1\}$
- •
$I(E):A\times A\rightarrow\{0,1\}$

The pair $(A,I)$ is called an *$S$-structure* for the first order logic FO(S). Provided this $S$-structure, one can safely construct simple examples of formulas at the *graph level* (we will see in the next paragraph that we need something more to interpret them at the *vertex level*). Namely, the following formula interpreted over a graph $G=(V,E)$ expresses that no vertex $v\in V$ is isolated: $\forall x\exists yE(x,y).$ Similarly, the formula $\forall x\neg E(x,x)$ expresses the fact that we do not want any self loops. A more interesting example is given by

$$ $\psi:=\forall x\forall y[E(x,y)\rightarrow E(y,x)\land x\neq y]$ (1) $$

expressing that $G$ is undirected and loop-free. Similarly

$$ $\displaystyle\begin{split}\phi:=\forall x\exists y\exists z(\neg(y=z)\wedge E( x,y)\wedge E(x,z))\wedge\forall w(E(x,w)\rightarrow((w=y)\vee(w=z)))\end{split}$ (2) $$

expresses that every node $x$ of the considered graph has exactly two out-neigbhors.

Free variables and assignments. Since GNNs can output values for every vertex of a graph, the formulas we are interested in order to describe them from a logical standpoint must also take as “input” some vertex variable. Therefore, we need to add some component to the $S$-structure described as above, resulting in what we call an *interpretation*.

First we need the concept of *bound* and *free* variable of a formula. A bound variable of a formula is a variable for which the scope of a quantifier applies. In comparison, a free variable is not bound to a quantifier in that formula. Previous Formulas 1 and 2 contain no free variable. In contrast, the formula $\phi(x):=\exists y\exists z(\neg(y=z)\wedge E(x,y)\wedge E(x,z))$, which expresses that vertex $v$ has two out-neighbors, has a single free variable $x$. To interpret formulas with one (resp. $k$) free variable, we need an *assignment* that maps the set of free variables in the logic, to the universe $A$ (resp. $A^{k}$).

Now, an *interpretation* of FO(S) is a pair $(\mathcal{U},\beta)$ where $\mathcal{U}$ is an $S$-structure and $\beta$ is an assignment. To interpret a formula with free variables, every graph is associated to an $S$-structure and an assignment; both are usually implicit in practice. Any formula in FO(S) (with and without free variables) can now be thought of as a $0/1$ function on the class of all interpretations of FO(S):

- (1)
If $\phi$ is a formula without a free variable (in this case, the formula is said to be a *sentence*), then any graph $G$ is an $S$-structure and is mapped to 0 0 or $1$, depending on whether $G$ satisfies $\phi$ or not.
- (2)
If $\phi(x)$ is a formula with a single free variable $x$, then any pair $(G,v)$, where $G=(V,E)$ is a graph and $v\in V$, is an interpretation with $G$ as the $S$-structure and the assignment $\beta$ maps $x$ to $v$. Thus, every pair $(G,v)$ is mapped to 0 0 or $1$, depending on whether $(G,\beta)$ satisfies $\phi$ or not. This example can be extended to handle formulas with multiple free variables, where we may want to model $0/1$ functions on subsets of vertices.

(Queries as Boolean functions)
Let $G$ be a graph and let $v\in V(G)$ be a vertex of $G$. If $Q$ has a free variable query (of type (2) above), $Q(G,v)\in\{0,1\}$ refers to the query interpreted and evaluated using the pair $(G,v)$.

The depth of a formula $\phi$ is defined recursively as follows. If $\phi$ is of the form $\mathsf{Col}_{i}$ for $i\in[\ell]$,
then its depth is $1$. If $\phi=\neg\phi^{\prime}$ or $\phi=\forall x\phi^{\prime}$ or $\phi=\exists x\phi^{\prime}$, then the depth of $\phi$ is the depth of $\phi^{\prime}$ plus 1. If $\phi=\phi_{1}\star\phi_{2}$ with $\star\in\{\vee,\wedge,\rightarrow,\leftrightarrow\}$, then the depth of $\phi$ is $1+\max(\mathsf{depth}(\phi_{1}),\mathsf{depth}(\phi_{2}))$.
In order to characterize the logic of GNNs, we are interested in a fragment of the first order logic, defined as follows.
{defi}[Graded (or guarded) model logic with counting (GC) and GC2 []]
The alphabet of GC2 is composed of

- •
the logical connectives $\land,\lor,\lnot,\rightarrow$
- •
the quantifiers $\forall$, and for every positive integer $N$, $\exists^{\geq N}$
- •
the *universe* $A=V$
- •
variables $x_{0},x_{1},\cdots$ (countably many)
- •
the *vocabulary* $S$:
$\circ$
a binary edge relation symbol $E$: $(x,y)\in A^{2}$ are related if and only if $(x,y)\in E$.
$\circ$
unary relation symbols $\mathsf{Col}_{1},\cdots,\mathsf{Col}_{\ell}$ indicating if a vertex has a given color

In contrast with the first order logic, we do not have access to equality (=). $\exists$ is simply $\exists^{\geq 1}$. For a given unary relation $R$, the quantifier $\exists^{\geq N}xR(x)$ means that there exists at least $N$ elements $x$ verifying relation $R$. Similarly, $\exists^{\geq N}xE(x,y)$ means that at least $N$ vertices adjacent to $y$ in the considered graph.
GC-formulas are formed from the atomic formulas
by the Boolean connectives and quantification restricted to
formulas of the form $\exists^{\geq p}y(E(x,y)\land\psi))$, where x and y are
distinct variables and $x$ appears in $\psi$ as a free variable. Note
that every formula of GC has at least one free variable. For example, $\phi(x):=\lnot(\exists^{\geq 2}y(E(x,y)\land\mathsf{Col}_{1}(y))\land\exists^{
\geq 3}z(E(x,z)\land\mathsf{Col}_{2}(z)))$ is a GC formula.

We refer to the 2-variable fragment of GC as GC2 (i.e. formulas with only two variables). Equivalently, a GC2 formula $F$ is either $\mathsf{Col}_{i}(x)$ (returning 1 or 0 for one of the palette colors) or one of the following:

$$ $\lnot\phi(x),\quad\phi(x)\land\psi(x),or\quad\exists^{\geq N}y(E(x,y)\land\phi (y))$ $$

where $N$ is a positive integer and $\phi$ and $\psi$ are GC2 formulas of lower depth than $F$.

[[]]
All graded modal logic formulas naturally define unary queries.
Suppose $\ell=2$ (number of colors), and $\mathsf{Col}_{1}=\text{Red}$, $\mathsf{Col}_{2}=\text{Blue}$. Let:

$$ $\gamma(x):=\text{Blue}(x)\land\exists y(E(x,y)\land\exists^{\geq 2}x(Edge(y,x) \land\text{Red}(x))$ $$

$\gamma$ queries if $x$ has blue color, and has at least one neigbhor which has at least two red neighbors. Then $\gamma$ is in GC2.
Now,

$$ $\delta(x):=\text{Blue}(x)\land\exists y(\lnot E(x,y)\land\exists^{\geq 2}xE(y, x)\land\text{Red}(x))$ $$

is not in GC2 because the use of the guard $\lnot E(x,y)$ is not allowed. However,

$$ $\eta(x):=\lnot(\exists y(E(x,y)\land\exists^{\geq 2}xE(y,x)\land\text{Blue}(x))$ $$

is in GC2 because the negation $\lnot$ is applied to a formula in GC2.

### 2.3. GNNs and color refinement

Finally, our proofs require two additional definitions about color refinement that we include for completeness.

[Embeddings and refinement]
Given a set $X$, an embedding $\xi$ is a function taking as input a graph $G$ and a vertex $v\in V(G)$, and returns an element $\xi(G,v)\in X$. We say that an embedding $\xi$ refines an embedding $\xi^{\prime}$ if and only if for any graph $G$ and any $v\in V(G),\xi(G,v)=\xi(G,v^{\prime})\implies\xi^{\prime}(G,v)=\xi^{\prime}(G,v
^{\prime})$.
When the graph $G$ is clear from context, we use $\xi(v)$ as shorthand for $\xi(G,v)$.

[Color refinement] Given a graph $G$, and $v\in V(G)$, let $(G,v)\mapsto\mathsf{col(G,v)}$ be the function which returns the color of the node $v$. The color refinement refers to a procedure that returns a sequence of embeddings $cr^{t}$, computed recursively as follows:

- $cr^{0}(G,v)=\mathsf{col}(G,v)$

- For $t\geq 0$, $\mathsf{cr}^{t+1}(G,v):=(\mathsf{cr}^{t}(G,v),\{\{\mathsf{cr}^{t}(G,w):w\in N(
v)\}\})$

In each round, the algorithm computes a coloring that is finer than the one computed in the previous round, that is, $\mathsf{cr}^{t+1}$ refines $\mathsf{cr}^{t}$.
For some $t\leq n:=\lvert G\rvert$, this procedure stabilises: the coloring does not become strictly finer anymore.

The following connection between color refinement and GNNs will be useful to prove our main result. Notably, the theorem holds regardless of the choice of the aggregation function $\mathsf{agg}$ and the combination function $\mathsf{comb}$.

###### Theorem 2 ( [ MRF + 19 , XHLJ18 ] ) .

Let $d$ be a positive integer, and let $\xi$ be the output of a GNN after $d$ iterations. Then $\mathsf{cr}^{d}$ refines $\xi$, that is, for all graphs $G,G^{\prime}$ and vertices $v\in V(G)$, $v^{\prime}\in V(G^{\prime})$,
$\mathsf{cr}^{(d)}(G,v)=\mathsf{cr}^{d}(G^{\prime},v^{\prime})\implies\xi(G,v)=
\xi(G^{\prime},v^{\prime})$.

###### Theorem 2 ( [ MRF + 19 , XHLJ18 ] ) .

## 3. Uniform expressivity of GNNs

[[]]
Suppose that $\xi$ is the vertex embedding computed by a GNN. We say that a GNN expresses uniformly a unary query $Q$ there is a real $\epsilon<\frac{1}{2}$ such that for all graphs G and vertices $v\in V(G)$.

$$ $\begin{cases}\xi(G,v)\geq 1-\epsilon&\text{if $v\in Q(G)$}\\ \xi(G,v)\leq\epsilon&\text{if $v\notin Q(G)$}\end{cases}$ $$

We are now equipped to state the known previous results regarding the expressivity of GNNs:

###### Theorem 3 .

[, ]
Let Q be a unary query expressible in graded modal logic GC2. Then there is a GNN whose size depends only on the depth of the query, that expresses Q uniformly.

###### Remark 4 .

Let $\ell$ be the number of colors of the vertices in the input graphs, the family of GNNs with $\mathsf{agg}=\mathsf{sum}$, and $\mathsf{comb}(x,y)=\operatorname{ReLU}(Ax+By+C)$ (where $A\in\mathbb{N}^{\ell\times\ell}$, $B\in\mathbb{N}^{\ell\times\ell}$ and $C\in\mathbb{N}^{\ell}$) is sufficient to express all queries of GC2 uniformly. This result follows from the constructive proof of Theorem 3 in Appendix A. Furthermore, for each query $Q$ of depth $q$, there is a GNN of this type with at most $q$ iterations that expresses $Q$ uniformly.

Let $Q$ be the following GC2 query:

$$ $Q(x):=\text{Red}(x)\land\left(\exists yE(x,y)\,\land\,\text{Blue}(y)\right)$ $$

asking if the vertex $x$ has red color, and if it has a neighbor with blue color. Writing the subformulas of $Q$: $\text{sub}(Q)=(Q1,Q2,Q3,Q4)$
with $Q_{1}=\text{Red}$, $Q_{2}=\text{Blue}$, $Q_{3}=\exists(E(x,y)\land Q_{2}(y)$, and $Q_{4}=Q=Q_{1}\land Q_{3}$, let

$$ $A=\begin{pmatrix}1&0&0&0\\ 0&1&0&0\\ 0&0&0&0\\ 1&0&1&0\end{pmatrix},B=\begin{pmatrix}0&0&0&0\\ 0&0&0&0\\ 0&1&0&0\\ 0&0&0&0\end{pmatrix},c=\begin{pmatrix}0\\ 0\\ 0\\ -1\end{pmatrix}$ $$

and let $\sigma$ be the clipped ReLU function, i.e. $\sigma(\cdot):=\min(1,\max(0,\cdot))$ (the clipped ReLU can be computed by a neural network with ReLU activations). Then, it can be verified that $Q$ can be computed in $4$ iterations with the update rule:

$$ $\xi^{0}(G,v)=1,\quad\xi^{t+1}(G,v):=\sigma(A\xi^{t}(G,v)+B(\sum_{w\in N_{G}(v) }\xi^{t}(w)))$ $$

i.e. $Q_{i}(G,v)=\xi^{4}(G,v)_{i}$. In particular, $Q_{i}(G,v)=1\iff\xi^{4}(G,v)_{i}=1$.
The ability of GNNs to compute exactly GC2 queries is used in the proof of Theorem 3. We emphasize here that one cannot mimic the proof for sigmoid activations, even by replacing exact *computation* by uniform expressivity.

In general, the logic of GNNs and their different variants beyond first-order queries remains elusive. However, for aggregation-combine GNNs without global readout (cf. Remark 1), Theorem 3 has the following partial converse:

###### Theorem 5 .

[]
Let Q be a unary query expressible by a GNN and also expressible in first-order logic. Then Q is expressible in GC2. Furthermore, a logical classifier is captured by an aggregation-combine GNN without global readout if and only if it can be expressed in GC2 logic.

###### Remark 6 .

The logic that fits GNNs *with global readout* is not GC2. If $C2$ is the fragment of the first order logic with counting quantifiers $(\exists^{\geq p})$ and with at most 2 variables; then we have the following result []: *Let Q be a Boolean or unary query expressible in C2. Then there is a GNN with global readout that expresses Q.*

In contrast with Theorem 3, we prove:

###### Theorem 7 .

There are GC2 queries that no GNN with rational activations can uniformly express.

Equivalently, if $\mathcal{L}_{R}$ (resp. $\mathcal{L}_{ReLU}$) is the set of first order logical queries uniformly expressible by GNNs with rational activations (resp. ReLU activations), then $\mathcal{L}_{R}\subsetneq(\mathcal{L}_{ReLU}=\text{GC2})$. The query used in our proof uses logical negation:

$$ $Q_{p}(s):=\lnot\left(\exists^{\geq 1}x(E(s,x)\land\exists^{\leq(p-1)}sE(x,s))\right)$ $$

and can be extended to a large family of queries (cf. Remark 13). We can obtain the following corollary by immediate contradiction, as GNNs with rational activations and aggregations can simulate logical negation:

###### Corollary 8 .

There are queries of GC2 using only the guarded existential quantifiers with counting $\exists^{\geq K}$E, the logical and $\land$ and the atomic formulas Col(.), that GNNs with rational activations cannot uniformly express.

In Section 5, we build towards a description of the logic expressible via rational GNNs.

###### Theorem 3 .

###### Remark 4 .

###### Theorem 5 .

###### Remark 6 .

###### Theorem 7 .

###### Corollary 8 .

## 4. Rational GNNs have limited expressivity

Overview. To prove our result we construct a GC2 query $Q$ that no GNN with rational activation can express over all graphs. We prove this statement by contradiction: on the one hand we interpret the embedding returned by a rational GNN on a set of given input graphs, as a rational function of some parameters of the graph structure. On the other hand, we interpret $Q$ on the same set of input graphs. We show that if GNN were to uniformly express $Q$, then the rational function obtained by the first evaluation cannot verify the constraints imposed by $Q$. Our approach and can easily extend to a large family of GC2 queries.

Similarly to those considered in [], our set of inputs are formed using rooted unicolored trees of the form shown in Figure 1 which is a tree of depth two whose depth one vertices have prescribed degrees $k_{1},\cdots,k_{m}$, with $k_{1},\cdots,k_{m}\geq 0$. We first collect three elementary Lemmas, one that will be useful to extract monomials of largest degree in a multivariate polynomial (Lemma 9) then used for rational fractions (Lemma 10). Since the trees are parameterized by $m$-tuples of integers $k_{1},\ldots,k_{m}$, the embedding of the root node computed by the GNN at any iteration is a function of these $m$ integers. Since the activations are rational, these embeddings of the root node are multivariate symmetric rational functions of $k_{1},\ldots,k_{m}$ (Lemma 11). Furthermore, the degree of these rational functions is bounded by a constant independent of $m$. Our proof of Theorem 7 builds on these results combined with fundamental properties of symmetric polynomials and rational functions.

Figure: Figure 1. $T[k_{1},\cdots,k_{m}]$

###### Lemma 9 .

Let $p$ be a positive integer and let $S\subset\mathbb{N}^{p}$ be a finite subset of integral vectors of the nonnegative orthant, such that $S$ contains a non zero vector. Then there exist $x^{*}\in S$ and $u\in\mathbb{N}^{p}$ such that

i) if $\lvert S\rvert=1$ then $\langle x^{*},u\rangle>0$

ii) if $\lvert S\rvert\geq 2$ then for any $x\in S-\{x^{*}\}$, $\langle x^{*},u\rangle>\langle x,u\rangle$.

###### Proof 4.1 .

If $\lvert S\rvert=1$ the existence of $x^{*}$ and $u$ such that i) holds is clear as $S$ is the singleton of a vector that is non zero.
To deal with ii) in the case $\lvert S\rvert\geq 2$, consider one vector $x^{*}$ maximizing the Euclidean norm over $S$, i.e. $\lVert x^{*}\rVert^{2}=\mathsf{max}_{x\in S}\lVert x\rVert^{2}$ then let $x\in S-\{x^{*}\}$. Such $x^{*}$ and $x$ exist because $S$ is finite and $\lvert S\rvert\geq 2$.

- Case 1: $x$ is not colinear to $x^{*}$. It follows from the Cauchy-Schwarz inequality, that $\langle x^{*},x\rangle<\lVert x^{*}\rVert\lVert x\rVert$. Hence

$$ $\langle x^{*},x^{*}-x\rangle=\lVert x^{*}\rVert^{2}-\langle x^{*},x\rangle> \lVert x^{*}\rVert(\lVert x^{*}\rVert-\lVert x\rVert)>0$ $$

- Case 2: $x\in S-\{x^{*}\}$ is colinear to $x^{*}$, i.e. $x=\lambda x^{*}$ with $\lambda\in\mathbb{R}$. Since $x^{*}$ is maximizing the $2$-norm on S, then $0\leq\lambda<1$. Then

$$ $\langle x^{*},x^{*}-x\rangle=\lVert x^{*}\rVert(1-\lambda)>0$ $$

In both cases, $\langle x^{*},x^{*}-x\rangle>0$. Hence, we can set $u:=x^{*}\in S\subset\mathbb{N}^{p}$, and the Lemma is proved.

The following Lemma simply states that the vector $u\in\mathbb{N}^{p}$ can be chosen the same if one is given a pair of sets $S$ and $S^{\prime}$.

###### Lemma 10 .

Let $p$ be a positive integer, and let $S,S^{\prime}$ be two finite subsets of $\mathbb{N}^{p}$, such that $\lvert S\rvert\geq 2$ and $\lvert S^{\prime}\rvert\geq 2$. Then there exist $u\in\mathbb{N}^{p}$, $x^{*}\in S$ and $y^{*}\in S$ such that

for any $x\in S-\{x^{*}\}$ and any $y\in S^{\prime}-\{y^{*}\}$, $\langle x^{*},u\rangle>\langle x,u\rangle$ and $\langle y^{*},u\rangle>\langle y,u\rangle$.

###### Proof 4.2 .

Lemma 9 insures that there exists $u^{\prime}\in\mathbb{N}^{p}$, $u^{\prime\prime}\in\mathbb{N}^{p}$, $x^{*}\in S$ and $y^{*}\in S^{\prime}$ such that for any $x\in S-\{x^{*}\}$ and any $y\in S^{\prime}-\{y^{*}\}$, $\langle x^{*},u^{\prime}\rangle>\langle x,u^{\prime}\rangle$ and $\langle y^{*},u^{\prime\prime}\rangle>\langle y,u^{\prime\prime}\rangle$. Simply set $u:=u^{\prime}+u^{\prime\prime}$ to obtain $\langle x^{*},u\rangle=\langle x^{*},u^{\prime}\rangle+\langle x^{*},u^{\prime
\prime}\rangle\geq\langle x^{*},u^{\prime}\rangle>\langle x,u^{\prime}\rangle$ for every $x\in S-\{x^{*}\}$ (the second equality follows from $\langle x^{*},u^{\prime\prime}\rangle\geq 0$ as the coordinates of both vectors are non-negative). Similarly, $\langle y^{*},u\rangle>\langle y,u\rangle$ for every $y\in S^{\prime}-\{y^{*}\}$.

###### Lemma 11 .

Let $\xi^{t}(T[k_{1},\ldots,k_{m}],s)\in\mathbb{R}^{d}$ be the embedding of the tree displayed in Figure 1 obtained via a GNN with rational activations after $t$ iterations, where $\xi^{0}(v)=1$ for all vertices $v\in V(T[k_{1},\ldots,k_{m}])$. Then, for any iteration $t$, and for every coordinate $\xi^{t}_{i}(T[k_{1},\ldots,k_{m}],s)$, there exists a symmetric rational function $F_{i}$ such that $\xi^{t}_{i}(T[k_{1},\ldots,k_{m}],s)=F_{i}(k_{1},\cdots,k_{m})$.
Furthermore, the degrees of the numerator and denominator of each $F_{i}$ do not depend on $m$, but only on the underlying neural network and $t$.

###### Proof 4.3 .

For clarity, we will perform three separate inductions, one for the existence of the rational function, one for the symmetry (using as a surrogate the color refinement algorithm), and the third one for the degree boundedness.

Rational function. We first prove by induction on $t$ that, for any vertex $v\in V(T[k_{1},\allowbreak\cdots,k_{m}])$, all the coordinates of $\xi^{t}(T[k_{1},\ldots,\allowbreak k_{m}],v)$ are rational functions of the $k_{i}$’s.

Base case: for $t=0$ this is trivial since all vertices are initialised with the constant rational function 1, whose degree does not depend on $m$.

Induction step: Suppose the property is true at iteration $t$, i.e for each node $w$, $\xi^{t}(T[k_{1},\ldots,k_{m}],w)$ is (coordinate-wise) a rational functions of the $k_{i}$’s. Since

$$ $\displaystyle\xi^{t+1}(T[k_{1},\ldots,k_{m}],v)=\mathsf{comb}_{t}(\xi^{t}(T[k_ {1},$ $\displaystyle\ldots,k_{m}],v),$ $\displaystyle\mathsf{agg}_{t}(\{\{\xi^{t}(T[k_{1},\cdots,k_{m}],w):w\in N(v)\} \}))$ $$

where $\mathsf{comb}_{t}$ is a neural network with rational activations, hence a rational function. Also, $\mathsf{agg}_{t}$ is supposed rational in the entries of its multiset argument. Then
by composition, each coordinate of $\xi^{t+1}(T[k_{1},\allowbreak\ldots,k_{m}],v)$ is a rational function of $k_{1},\cdots,k_{m}$.

Symmetry. need the intermediary claim:

*Claim: Let $T[k_{1},\cdots,k_{m}]$ be two rooted trees given by Figure 1, and let $s$ be its source vertex. Then for any iteration $t$, the color refinement embedding $\mathsf{cr}^{t}(s)$ is invariant by permutation of the $k_{i}$’s.*

###### Proof 4.4 (Proof of claim) .

By induction of $t\geq 0$, we prove the following claim: for any integer $t\geq 0$, $\mathsf{cr}^{t}(s)$ and the multiset $\{\{\mathsf{cr}^{t}(x_{1}),\allowbreak\cdots,\mathsf{cr}^{t}(x_{m})\}\}$ are invariant by permutation of the $k_{i}$’s.

*Base case:* $(t=0)$ is obvious since $\mathsf{cr}^{0}(v)=1$ for any vertex $v\in T[k_{1},\cdots,k_{m}]$.

*Induction step:* Suppose that for some iteration $t$, $\mathsf{cr}^{t}(s)$ and $\{\{\mathsf{cr}^{t}{x_{1}},\cdots,\mathsf{cr}^{t}(x_{m})\}\}$ are invariant by permutation of the $k_{i}$’s. $\mathsf{cr}^{t+1}(s)$ being invariant by permutation of the $k_{i}$’s is a consequence of:
$\mathsf{cr}^{t+1}(s)=(\mathsf{cr}^{t}(s),\{\{\mathsf{cr}^{t}(x_{1}),\cdots,
\mathsf{cr}^{t}(x_{m})\}\})$

We know from Theorem 2 that the color refinement algorithm refines any GNN at any iteration. Since the tuple obtained by color refinement for the vertex $s$ is invariant with respect to permutations of the $k_{i}$’s, $\xi^{t}(T[k_{1},\ldots,k_{m}],s)$ is also invariant with respect to permutations of the $k_{i}$’s.

Degree boundedness. Finally, the degree boundedness also follows by induction. We will prove that the degree of the numerators and denominators of $\xi^{t}(T[k_{1},\cdots,k_{m}],s)$ are both respectively bounded by $q_{t}$ and $r_{t}$.

*Base case:* At the first iteration ($t=0$), $P_{m}$ is constant equal to $1$ ($q_{1}=1$ and $r_{1}=0$) for any $m$.

*Induction step:* Suppose that for any iteration $t\leq T$ , there exists $q_{t}\in\mathbb{N}$ (that does not depend on $m$ nor the vertex $v\in V(T[k_{1},\cdots,k_{m}])$), such that for every positive integer $m$, every vertex $v\in T[k_{1},\cdots,k_{m}]$, and for every iteration $t$, $\mathsf{deg}(F_{i})\leq(q_{t},r_{t})$. Then, using again the update rule:

$$ $\displaystyle\underbrace{\xi^{t+1}(T[k_{1},\cdots,k_{m}],v)}_{Q_{m}}=$ $\displaystyle\mathsf{comb}_{t}(\underbrace{\xi^{t}(T[k_{1},\cdots,k_{m}],v)}_{ R_{m}},$ $\displaystyle\qquad\qquad\underbrace{\mathsf{agg}_{t}(\{\{\xi^{t}(T[k_{1}, \cdots,k_{m}],w):w\in N(v)\}\})}_{S_{m}})$ $$

$R_{m}$ and $S_{m}$ are rational fractions. By the induction hypothesis, for any $m$,
$\mathsf{deg}(R_{m})\leq(q_{t},r_{t})$ and $\mathsf{deg}(S_{m})\leq(q_{t},r_{t})$.

Each coordinate of the function $\mathsf{comb}_{t}$ is a rational fraction of degree independent of $m$ (neural network with a rational activation). Let $(a_{i},b_{i})$ be the degree of its $i$-th coordinate for $i\in[d]$. Hence, the degree of the $i$-th coordinate $Q_{m}$ is at most $(a_{i}\times q_{t}r_{t},b_{i}\times q_{t}r_{t})$. Hence the property remains true at $t+1$ for each coordinate $i$, setting $q_{t+1}:=(\max_{i\in[d]}a_{i})\times q_{t}r_{t}$ and $r_{t+1}:=(\max_{i\in[d]}b_{i})\times q_{t}r_{t}$.

We can now build towards the:

###### Proof 4.5 (Proof of Theorem 7 ) .

Recall that the fractions we consider have no real pole. Consider the following query of GC2:

$$ $Q(s)=\lnot\left(\exists^{\geq 1}x(E(s,x)\land\exists^{\leq 1}sE(x,s))\right)= \forall xE(s,x)\exists^{\geq 2}sE(x,s)$ $$

$Q$ is true if and only if all the neigbhors of the node $s$ have degree at least $2$. Namely $Q(T[0,k_{2},\cdots,k_{m}],s)$ is false and $Q(T[k_{1},\cdots,k_{m}],s)$ is true for every positive integers $k_{1},\cdots,k_{m}$. We will prove by contradiction that any bounded GNN with rational activations cannot uniformly express the query $Q$.
Let $R_{m}:=\xi^{t}(T[k_{1},\cdots,k_{m}],s)$ be the embedding of the source node of $T[k_{1},\cdots,k_{m}]$ returned by a GNN with rational activations, after a fixed number of iterations $t$. Suppose that it can uniformly express the query $Q$, then;

$$ $\begin{cases}R_{m}(k_{1},\cdots,k_{m})\geq 1-\epsilon&\text{if $s\in Q(T[k_{1} ,\cdots,k_{m}],s)$}\\ R_{m}(k_{1},\cdots,k_{m})\leq\epsilon&\text{if $s\notin Q(T[k_{1},\cdots,k_{m} ],s)$}\end{cases}$ $$

Let $\tilde{R}_{m}:=R_{m}-\frac{1}{2}$ and $\epsilon^{\prime}:=\frac{1}{2}-\epsilon$. Interpreting the query $Q$ over $T[k_{1},\cdots,k_{m}]$ implies the following constraints on the sequence of rational functions $\tilde{R}_{m}$:

$$ $\exists\epsilon^{\prime}>0\;\text{such that}\;\forall k\in\mathbb{N}^{m}\; \begin{cases}\exists i\in\{1,\cdots,m\},k_{i}=0\implies\tilde{R}_{m}(k)\leq- \epsilon^{\prime}&\\ \forall i\in\{1,\cdots,m\},k_{i}>0\implies\tilde{R}_{m}(k)\geq\epsilon^{\prime }&\end{cases}$ (3) $$

Let $\tilde{R}_{m}=\frac{\tilde{P}_{m}}{\tilde{Q}_{m}}$ be the irreducible representation of $\tilde{R}_{m}$,and let $S$ (resp. $S^{\prime}$) be the set of exponents of the monomials of $\tilde{P}_{m}$ (resp. $\tilde{Q}_{m}$), i.e.

$$ $\displaystyle S:=\{(\alpha_{1},\cdots,\alpha_{m})\in\mathbb{N}^{m}:\alpha_{1}+ \cdots+\alpha_{m}\leq q$ and $k_{1}^{\alpha_{1}}\cdots k_{m}^{\alpha_{m}}$ $\displaystyle\text{is a monomial of $\tilde{P}_{m}$}\}$ $$

$$ $\displaystyle S^{\prime}:=\{(\alpha_{1},\cdots,\alpha_{m})\in\mathbb{N}^{m}: \alpha_{1}+\cdots+\alpha_{m}\leq q$ and $k_{1}^{\alpha_{1}}\cdots k_{m}^{\alpha_{m}}$ $\displaystyle\text{is a monomial of $\tilde{Q}_{m}$}\}$ $$

First $\lvert S\rvert=0$ is impossible as $\tilde{R}_{m}$ would have no zeroes and Conditions 3 cannot be met. Henceforth we suppose that $\lvert S\rvert\geq 2$ and $\lvert S^{\prime}\rvert\geq 2$ (the other cases are discussed hereafter).

Lemma 10 (with $p=m$) tells us there exists $\alpha^{*}\in S$, $\beta^{*}\in S^{\prime}$ and $u=(u_{1},\cdots,u_{m})\in\mathbb{N}^{m}$ such that for any $\alpha\in S-\{\alpha^{*}\}$ and for any $\beta\in S^{\prime}-\{\alpha^{*}\}$

$$ $\langle\alpha^{*},u\rangle>\langle\alpha,u\rangle\qquad\text{and}\qquad\langle \beta^{*},u\rangle>\langle\beta,u\rangle$ $$

*Claim 1: The (univariate) monomial $t^{\langle\alpha^{*},u\rangle}$ is the monomial of $\tilde{P}_{m}(t^{u_{1}},\cdots,t^{u_{m}})$ *of largest degree.**

###### Proof 4.6 .

$$ $\tilde{P}_{m}=\sum_{\alpha\in S}\gamma_{\alpha}k_{1}^{\alpha_{1}}\cdots k_{m}^ {\alpha_{m}}\implies\tilde{P}_{m}(t^{u_{1}},\cdots,t^{u_{m-1}},t^{u_{m}})=\sum _{\alpha\in S}\gamma_{\alpha}t^{\langle\alpha,u\rangle}$ $$

Hence, the monomial of largest degree of $\tilde{P}_{m}(t^{u_{1}},\cdots,t^{u_{m}})$ is the one such that $\langle\alpha,u\rangle$ is (strictly) maximized when $\alpha\in S$. By construction, it is $\alpha^{*}$.

Now, suppose that $\tilde{P}_{m}$ has bounded degree (i.e. there is a uniform bound on the degree of the polynomials $\tilde{P}_{m}$ that is independent of $m$). Then, any monomial of largest degree of $\tilde{P}_{m}$ does not contain all the variables. Without loss of generality (by symmetry of $\tilde{P}_{m}$), we can suppose that the monomial $k_{1}^{\alpha^{*}_{1}}\cdots k_{m}^{\alpha^{*}_{m}}$ does not contain $k_{m}$, i.e. $\alpha^{*}_{m}=0$.

*Claim 2: In these conditions, the (univariate) monomial $t^{\langle\alpha^{*},u\rangle}$ is also *the* monomial of *of largest degree of $\tilde{P}_{m}(t^{u_{1}},\allowbreak\cdots,t^{u_{m-1}},0)$. * *

###### Proof 4.7 .

Evaluating $\tilde{P}_{m}$ in $(t^{u_{1}},\cdots,t^{u_{m-1}},0)$ removes the contribution of each monomial of $P_{m}$ containing the last variable, and keeps only the contribution of the monomials containing it:

$$ $\displaystyle\tilde{P}_{m}=\sum_{\alpha\in S}\gamma_{\alpha}k_{1}^{\alpha_{1}} \cdots k_{m}^{\alpha_{m}}\implies\tilde{P}_{m}(t^{u_{1}},\cdots,t^{u_{m-1}},0) =\sum_{\begin{subarray}{c}\alpha\in S\alpha=(\alpha_{1},\cdots,\alpha_{m-1},0) \end{subarray}}\gamma_{\alpha}t^{\langle\alpha,u\rangle}$ $$

Therefore, the monomial of largest degree of $\tilde{P}_{m}(t^{u_{1}},\cdots,\allowbreak t^{u_{m-1}},0)$ is the one such that $\langle\alpha,u\rangle$ is (strictly) maximized when $\alpha\in S$ and $\alpha_{m}=0$. By construction, such $\alpha$ is $\alpha^{*}$.

Similarly, we obtain:

*Claim 3: The (univariate) monomial $t^{\langle\beta^{*},u\rangle}$ is the monomial of $\tilde{Q}_{m}(t^{u_{1}},\cdots,t^{u_{m}})$ *of largest degree.**

*Claim 4: the (univariate) monomial $t^{\langle\beta^{*},u\rangle}$ is also *the* monomial of *of largest degree of $\tilde{Q}_{m}(t^{u_{1}},\allowbreak\cdots,t^{u_{m-1}},0)$. **

Let $(\eta_{\beta})_{\beta\in S^{\prime}}$ be the coefficients of $\tilde{Q}_{m}$. The four claims combined imply that

$$ $\tilde{R}_{m}(t^{u_{1}},\cdots,t^{u_{m-1}},t^{u_{m}})\underset{t\rightarrow+ \infty}{\sim}\tilde{R}_{m}(t^{u_{1}},\cdots,t^{u_{m-1}},0)\underset{t \rightarrow+\infty}{\sim}\frac{\gamma_{\alpha^{*}}t^{\langle\alpha^{*},u \rangle}}{\eta_{\beta^{*}}t^{\langle\beta^{*},u\rangle}}$ $$

In particular $\lim_{t\rightarrow+\infty}\tilde{R}_{m}(t^{u_{1}},\allowbreak\cdots,t^{u_{m}})
=\lim_{t\rightarrow+\infty}\tilde{R}_{m}(t^{u_{1}},\allowbreak\cdots,t^{u_{m-1
}},0)$. This is a contradiction with Conditions 3.

Finally, if $\lvert S^{\prime}\rvert=0$ then $\tilde{R}_{m}$ is a polynomial. In this case we do not need Claims 3 and 4, and the reasoning still applies. If $\lvert S\rvert=1$ or $\lvert S^{\prime}\rvert=1$ then we can apply Lemma 9 (case i)) to the polynomials having only one monomial, and the same argument still goes through.

###### Remark 12 .

Note that the proof of Theorem 3 can be extended to a larger family of queries. Namely, for any integer $p\geq 2$, let

$$ $Q_{p}(s):=\lnot\left(\exists^{\geq 1}x(E(s,x)\land\exists^{\leq(p-1)}sE(x,s)) \right)=\forall xE(s,x)\exists^{\geq p}sE(x,s)$ $$

$Q_{p}$ queries if vertex $s$ has neighbors whose degree are all at least $p$. Then any $(Q_{p})_{p\in\mathbb{N}}$ cannot be expressed by any GNN with rational activations.

###### Remark 13 .

The proof of Theorem 7 was initially attempted using queries of the form:

$$ $\tilde{Q}_{p}(s)=\lnot\left(\exists^{\geq 1}x(E(s,x)\land\exists^{\geq(p+1)}sE (x,s))\right)=\forall xE(s,x)\exists^{\leq p}sE(x,s)$ $$

Which expresses that all the neighbors of $s$ have degree at most $p$. Note the similarity between $Q_{p}$ from Remark 13 and $\tilde{Q}_{p}$. Although $\tilde{Q}_{p}$ also seems a good candidate that cannot be expressed uniformly by a GNN with polynomial activations and aggregations, we could not conclude with the same approach as in the proof of Theorem 7, due to the following interesting fact:

There exists $\epsilon>0$ and a sequence of symmetric polynomial $(p_{m})_{m\in\mathbb{N}}\in\mathbb{R}[x_{1},\cdots,x_{m}]$ of bounded degree (i.e. there exists an integer $q$ such that for any $m$, $\mathsf{deg}(p_{m})\leq q$) and for any $m,p_{m}$ is greater than $\epsilon$ on the vertices of the unit hypercube $\{0,1\}^{m}$, and less than $-\epsilon$ on all the other points of $\mathbb{N}^{m}$.
$p_{m}=1-\sum_{i=1}^{m}x_{i}^{2}+\sum_{i=1}^{m}x_{i}^{4}$ is an example of such sequence of symmetric polynomials.

###### Lemma 9 .

###### Proof 4.1 .

###### Lemma 10 .

###### Proof 4.2 .

###### Lemma 11 .

###### Proof 4.3 .

###### Proof 4.4 (Proof of claim) .

###### Proof 4.5 (Proof of Theorem 7 ) .

###### Proof 4.6 .

###### Proof 4.7 .

###### Remark 12 .

###### Remark 13 .

## 5. Towards a rational fragment of GC2

We now turn our attention towards the fragment of GC2 expressed by rational GNNs. We present of fragment of GC2 that use of existential quantifiers aligned in the “same direction”, at the exception of the very last quantifier, as negation will only be allowed for the last subformula. In particular, this removes logical conjunctions and negations inside nested subformulas. Informally, such limitation arises from the aggregation phase when the messages in the neighborhood of a node, one obtains a signal that can become unbounded. We lose track of the number of neighbors that verify a given query, except at the very first iteration (captured by the set $\Omega_{0}$ in the Definition below). Our counterexamples (see Remark 13) confirm this is indeed happening. However, it is unclear if such limitation carries over for other aggregation functions such as max. However, our proof does not show that negation is *never* allowed in subformulas. We conjecture it is not the case and that RGC2 is close to the logic expressed by rational GNNs.

###### Definition 5.8 (Fragment RGC2 $\subseteq$ GC2) .

The fragment RGC2 is composed of logical queries of $\Omega$ constructed as follows:

- •
$\Omega_{0}$ contains $\mathsf{Col}_{i}$, $\lnot\mathsf{Col}_{i}$, and $\exists^{\geq K}yE(x,y)Col_{i}(y)$ for some $i\in[\ell]$ and for some $K\in\mathbb{N}$.
- •
$\Omega+:=\{\mathcal{H}^{(m)}(\phi):m\in\mathbb{N},\phi\in\Omega_{0})\}$, where $\mathcal{H}:\phi\mapsto\tilde{\phi}$ extends queries to $1$-hop neighborhoods, i.e. $\tilde{\phi}(x):=\exists^{\geq 1}y(E(x,y)\land\phi(y))$.
- •
$\Omega:=\{\lnot\psi$ with $\psi\in\Omega\}\cup\Omega$.

A few comments about RGC2 queries are in order. Note that the counting quantifier $\exists^{\geq K}$ with $K>1$ is not allowed on top of other guarded fragments, so

$$ $\phi_{1}(x):=\exists^{\geq 3}yE(x,y)(\exists^{\geq 1}xE(x,y)\land Red(x))$ $$

is not in RGC2, but $\phi_{2}$ is:

$$ $\phi_{2}(x):=\exists^{\geq 1}yE(x,y)(\exists^{\geq 1}xE(x,y)\land Red(x))$ $$

Similarly,

$$ $\phi_{1}(x)=\lnot(\exists^{\geq 1}yE(x,y)(\exists^{\geq 1}xE(y,x)(\exists^{ \geq 1}yE(x,y)\land Red(x))))$ $$

belongs to RGC2,

$$ $\phi_{2}(x)=\lnot(\exists^{\geq 1}yE(x,y)(\exists^{\geq 1}xE(y,x)(\exists^{ \leq 1}yE(x,y)\land Red(x))))$ $$

does not (alternates between existential and non existential quantifiers). Neither does

$$ $\phi_{3}(x)=\lnot(\exists^{\geq 1}yE(x,y)(\lnot\exists^{\geq 1}xE(y,x)(\exists ^{\geq 1}yE(x,y)\land Red(x))))$ $$

as it alternates between $\exists^{\geq 1}$ and $\lnot\exists^{\geq 1}$ in the nested formulas.

Finally, unlike the query $Q_{1}$ in Remark 13

$$ $\phi_{4}(x):=\forall yE(x,y)(\exists^{\leq 1}E(x,y))=\lnot(\exists^{\geq 1}yE( x,y)(\exists^{\geq 1}xE(x,y))$ $$

is in RGC2. To build towards Theorem 15, we first need the following Lemma.

###### Lemma 14 .

Let $\sigma$ be a univariate polynomial such that $\mathsf{deg}(\sigma)>1$ . Let $M>1$ be an integer, and let $P\in\mathbb{R}[X]$ be a univariate polynomial of degree $M$. Then there exists a feedforward neural network $f$ with activation function $\sigma$, whose size depends only on $M$, such that $f=P$.

###### Proof 5.9 .

Let $m:=\mathsf{deg}(\sigma)>1$. The set $\mathcal{A}_{\sigma}:=\mathsf{span}\{\sigma_{w,\theta}:\mathbb{R}\rightarrow
\mathbb{R},\,\sigma_{w,\theta}(x):=\sigma(wx+\theta):w\in\mathbb{R},\theta\in
\mathbb{R}\}$ is the set of polynomials of degree at most $m$. This can be deduced, for example, from the fact that the family $\mathcal{F}$ of polynomials $1,\sigma(X),\sigma(X+1),\cdots,\sigma(X+m)$ are linearly independent. This is true as the polynomials $1,(X+1)^{m},(X+2)^{m},\cdots,(X+m)^{m}$ are linearly independent (a consequence of the via the positivity of the Vandermonde determinant for $m$ distinct integers). Hence, the family $\mathcal{F}$ form a basis of the vector space of polynomials of degree at most $m$. Since $\mathcal{A}_{\sigma}$ is the set of functions computed by a $1$-hidden layer neural network with activation $\sigma$, we can perform an immediate induction on $M$ to prove the claim.

*Base case:* (M=2). Proved above.

*Induction step:* Suppose that for some integer $M$, for any integer $0<i\leq M$, for any polynomial $P_{i}$ of degree $i$, there exists a neural network $f_{M}$ of size that depends only on $i$ such that $f_{i}=P_{i}$. Suppose we are given a polynomial $P$ of degree $M+1$. By the induction hypothesis, we first reconstruct the polynomial $Q(X):=X^{M}$ as the output of one neuron. Now, $\sigma\circ Q$ has degree $M\times m>M$. Hence, $A_{\sigma\circ Q}$ is the set of polynomials of degree at most $2m$. In particular, we can compute $P$ as the output of a neural network by adding an additional hidden layer.

###### Theorem 15 .

For any query $Q$ of RGC2, there exists a rational GNN that expresses $Q$ uniformly over all graphs.

###### Proof 5.10 .

Our proof is very similar to the one presented in Appendix A, and actually shows that a *polynomial* GNN will do the job. Let $Q$ be a query of RGC2 of depth $d$, that we decompose in subformulas $(Q_{1},\cdots,Q_{d})$. By definition, $Q_{1}\in\Omega_{0}$ and all subqueries $Q_{i}$ for $i\in\{1,\cdots,d-1\}$ are in the positive fragment $\Omega_{+}$. Only $Q=Q_{d}$ is potentially in $\Omega$. We will prove by induction on $i\in\{1,\cdots,d-1\}$ that there is a polynomial GNN that outputs after $d$ iterations $\xi\in\mathbb{R}^{d}$ such that for every $i\in\{1,\cdots,d-1\}$ the coordinate $\xi_{i}$ is greater than $1$ if the query $Q_{i}$ is verified (for the considered vertex and graph) and returns exactly 0 0 if the query is not verified. The subqueries belonging to $\Omega_{0}$ constitute our “base case”, and we make standard induction on the depth when the query is in $\Omega_{+}-\Omega_{0}$.

*Base case:* We first prove that every query of $\Omega_{0}$ can be expressed. Any query of $\Omega_{0}$ is composed of the following queries:

1) $\mathsf{Col}_{i}$ or $\lnot\mathsf{Col}_{i}$ for some $i\in[\ell]$. Since the initial feature embedding $\xi^{0}(v,G)\in\{0,1\}^{\ell}$ encodes the color of the node $v$, one can construct a combine function that returns: i) in first coordinate $1$ if the $i$-th coordinate is $1$, and 0 0 when it is 0 0, and ii) zeroes in all $d-1$ coordinates. This insures that at the first iteration, the GNN expresses $Q_{1}$.

2) If the query is of the form $\exists^{\geq K}yE(x,y)Col_{i}(y)$ for some $i\in[\ell]$ and for some $K\in\mathbb{N}$. $\xi^{1}(v)$ is a $0-1$ vector constructed as in case 1) above. One can construct a polynomial function $P:\mathbb{R}\rightarrow\mathbb{R}$ (taking as input only the sum of the signals from the neigbhors) that is equal to 0 0 on every point of $\{0,\cdots,K-1\}$, and greater than $1$ on $\mathbb{N}-\{0,\cdots,K-1\}$. This can be achieved, for instance, by interpolation with the polynomial $P=X(X-1)(X-2)\cdots(X-(K-1))$, and using Lemma 14. Concretely,

$$ $\xi^{2}(G,v)=\tilde{P}(\sum_{w\in N_{G}(v)}\xi^{1}(G,w))$ $$

where $\tilde{P}$ is a vector with coordinates that are polynomials. The second coordinate of $\tilde{P}$ (corresponding to the subquery considered) is $P$. The other coordinates of $\tilde{P}$ and the others are the identity function. It is easy to see that $\xi^{2}(G,v)$ has the desired property.

*Induction step:* For $i\geq 2$, Suppose we are given a subformula of $\Omega_{+}$, then $Q_{i}(x)=\exists^{\geq 1}y(E(x,y)\land Q_{i-1}(y))$ with $Q_{i-1}\in\Omega_{+}$. By the induction hypothesis, we can construct a GNN, whose output $\xi\in\mathbb{R}^{d}$ verifies: for every $j\in\{1,\cdots,i-1\}$, $\xi_{j}$ is at least $1$ if $Q_{j}$ is verified and equal to 0 0 otherwise. Suppose we are given such GNN. At the update phase, when summing over the neighbors, one gets a signal equal to 0 0 if there is no neighbor verifying $Q_{i-1}$, and a signal of value at least $1$ if one of them does. Simply using the combine function that returns the same signal for all the coordinates the $i$-th coordinate gives $\xi_{i}$ expressing $Q_{i}$. More precisely, we have

$$ $\xi^{i}(G,v)=A_{i}\xi^{i-1}(G,v)+B_{i}\sum_{w\in N_{G}(G,v)}\xi^{i-1}(G,w)$ $$

where the combine function is the identity map $\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$, $A_{i}\in\mathbb{R}^{d\times d}$ has same first $i-1$ rows as $A_{i-1}$ and other rows are set to zero. $B_{i}\in\mathbb{R}^{d\times d}$ has the same $i-1$ rows as $B_{i-1}$ and $i-$th row verifies $B_{i,i-1}=1$. All first $i-1$ coordinates of $\xi^{i}$ remains the same, and the new $i$-th coordinate expresses the desired query.

Finally, if $Q=Q_{d}=\lnot Q_{d-1}$ with $Q_{d-1}\in\Omega$. By the result obtained above, we are in possession of a polynomial GNN that is at least $1$ when $Q_{d-1}$ is verified, and exactly 0 0 when not. Simply consider the update:

$$ $\xi^{d}(v,G)=A_{d}\xi^{i-1}(G,v)$ $$

Where the first $d-1$ rows of $A_{d}$ are the same as $A_{d-1}$ and the last row verifies $A_{d,d-1}=-1$. This insures that final query can be expressed by the GNN.

###### Definition 5.8 (Fragment RGC2 ⊆ \subseteq ⊆ GC2) .

###### Lemma 14 .

###### Proof 5.9 .

###### Theorem 15 .

###### Proof 5.10 .

## 6. Discussion and open problems

The activation functions of GNNs have an impact on the logic they can express. Analyzing rigorously how this expressivity is altered is valuable as it can help in selecting an appropriate architecture for a given problem. In this regard, the efficient universal approximation properties of rational neural networks [] may lead to believe that rational GNNs have maximal expressivity from a formal logical standpoint. Our results show that it is not the case as rational GNNs have strictly weaker expressivity than ReLU GNNs. Therefore, non polynomial activations do not confer GNNs superior uniform expressivity, although they do provide feedforward neural networks universal approximation power.
An interesting path for future research is to understand whether this desirable property of ReLU GNNs confer them a significant advantage over rational GNNs on graphs of bounded order, which may be relevant for practical applications.

It is also essential to note that expressivity is just one facet of practical use of GNNs and the related machine learning algorithms. This article does not delve into other crucial aspects such as the GNN’s ability to generalize from provided data, and the computational efficiency of learning and inference. In particular, we have not investigated the ability of a GNN to learn a logical query from examples – namely from a sample complexity standpoint. We also believe that theoretical investigations on the expressivity of GNNs and logical expressivity can suggest potential avenues to integrate logic-based and statistical reasoning in machine learning methods, and in particular in GNN architectures. These investigations also include questions of independent mathematical interest, some of which remain open. We list some below that are closely related to the results presented in this article.

Question 1: Can GNNs with sigmoidal activations and $\mathsf{agg}=\mathsf{sum}$ uniformly express GC2 queries?

Question 2: Do polynomial GNNs and rational GNNs have the same uniform expressivity?

Question 3: What is the impact of the aggregation function beyond those considered in this article (sums, of polynomials with bounded degree)?

Question 3: What is the exact fragment of GC2 uniformly expressible by GNNs with rational activations ?

Acknowledgements: The author would like to thank Amitabh Basu (Johns Hopkins University), Pablo Barceló (Universidad Católica de Chile) and Edinah Gnang (Johns Hopkins University) for valuable discussions about this work.

## Appendix A Proof that piecewise linear GNNs (and AGG=SUM) are as expressive as GC2

###### Proof A.11 .

We will prove the following claim from which the Theorem 3 will be an immediate corollary.

*Claim. Let $Q$ be a query in GC2, and let $\text{sub}(Q)=(Q_{1},Q_{2},\cdots,Q_{d})$ be an enumeration
of the subformulas of $Q$. Then, there exists a ReLU GNN returning $\xi^{t}$ such that for graph $G$ and any vertex $v\in V(G)$, $\xi^{t}(G,v)\in\{0,1\}^{d}$, and for any $i\in\{1,\cdots,d\}$, $\xi^{t+1}_{i}(G,v)=1\iff Q_{i}(G,v)=1$. *

The overall GNN will take as input the graph $G$ as well as for each node of $v$, $\xi^{0}(G,v)\in\{0,1\}^{\ell}$ encoding the colors of each node of $G$; and after $d$ iterations, outputs for each node a vector $\xi^{d}(G,v)\in\{0,1\}^{d}$. Furthemore, at each intermediate iteration $t\in\{1,\cdots,d-1\}$, the constructed GNN will verify $\xi^{t}(G,v)\in\{0,1\}^{d}$. This property will be crucial for the inductive argument to go through.

In order to prove the claim, we simply need to find appropriate $(\mathsf{comb}_{t})_{1\leq t\leq d}$ and $(\mathsf{agg}_{t})_{1\leq t\leq d}$ functions such that if $\xi^{t}$ verifying the update rule:

$$ $\xi^{t+1}(G,v)=\mathsf{comb}_{t}(\xi^{t}(G,v),\mathsf{agg}_{t}(\{\{\xi^{t}(G,v )):v\in\mathcal{N}_{G}(v)\}\}))$ $$

then $\xi^{t}$ computes the given query $Q$. We will prove that we can find such $\mathsf{comb}_{t}$ and $\mathsf{agg}_{t}$ functions by induction on the depth of $Q$.

*Base case*. If $Q$ has depth $1$, $Q$ is one of $\ell$ color queries, and this can be computed via a GNN in one iteration, whose underlying neural network is the projection onto the $i-$th coordinate, i.e.

- $\mathsf{comb}_{0}(x,y)=\text{proj}_{i}(x)$

- $\mathsf{agg}_{0}$ can be chosen as any aggregation function.

*Induction step.* Let suppose $Q$ be a query of depth $d>1$. By the induction hypothesis, we here suppose that we have access to some $(\mathsf{comb}_{t})_{1\leq t\leq d-1}$ and $(\mathsf{comb}_{t})_{1\leq t\leq d-1}$ such that for any $j\in\{1,\cdots,d-1\}$ and for any $1\leq i\leq j$, $Q_{j}(v)=1\iff\xi_{j}^{i}(v)=1$. Recall that $\text{sub}(Q)=(Q_{1},Q_{2},\cdots,Q_{d})$, i.e. the $Q_{i}$s form an enumeration
of the subformulas of $Q$. In particular, $Q_{d}=Q$. In the following construction, $\xi^{i}$ keeps “in memory” the output of the subformulas $Q_{j}$, for $j\leq i$.
For each case described below, we show that we are able to construct $\mathsf{comb}_{d}$ and $\mathsf{agg}_{d}$ in the following form:

- $\mathsf{comb}_{d}:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}^{d},
(x,y)\mapsto\sigma(A_{d}X+B_{d}Y+c_{d})$, where $\sigma(\cdot)=\min(1,\max(0,\cdot))$ is the clipped ReLU. Note that a clipped ReLU can be computed by a Neural Network with ReLU activations.

- $\mathsf{agg}_{d}$ is the sum function.

Due to the inductive nature of GC2, one of the following holds:

- •
Case 1: there exist subformulas $Q_{j}$ and $Q_{k}$ of $Q$, such that $\ell(Q_{j})+\ell(Q_{k})=d$ and $Q=Q_{j}\land Q_{k}$
- •
Case 2: $Q(x)=\lnot Q_{j}(x)$ where $Q_{j}$ is a query of depth $d-1$
- •
Case 3: there exists a subformula $Q_{j}$ of $Q$ such that $\ell(Q_{j})=d-1$ and $Q(x)=\exists^{\geq N}y(E(x,y)\land Q_{j}(y))$

We will first give general conditions on the update of the combinations and aggregate functions, and then conclude that these conditions are actually be met by constant $\mathsf{comb}$ and $\mathsf{agg}$ functions:

- $A_{d}$ gets the same first $d-1$ rows as $A_{d-1}$.

- $B_{d}$ gets the same first $d-1$ rows as $B_{d-1}$

- $c_{d}$ get the same first $d-1$ coordinates as $c_{d-1}$,

- •
Case 1: The $d$-th row of $A_{d}$ gets all zeros except: $(A_{d})_{jd}=1$, $(A_{d})_{kd}=1$. The $d$-th row of $B_{t}$ is set to 0 0. Set $(c_{d})_{d}=-1$.
- •
Case 2: The $d$-th row of $A_{d}$ gets all zeros except: $(A_{d})_{jd}=-1$. The $d$-th row of $B_{d}$ is set to 0 0. Set $(c_{d})_{d}=1$.
- •
Case 3: The $d$-th row of $A_{d}$ is set to 0 0. The $d$-th row of $B_{d}$ is set to 0 0 except $(B_{d})_{jd}=1$. Set $(c_{d})_{d}=-N+1$.

What remains to prove is the following:

$$ $\text{For any $i\in\{1,\cdots,d\}$},\quad\xi_{i}^{d}(G,v)=1\iff Q_{i}(G,v)=1$ $$

Due to the update rule, the first $d-1$ coordinates of $\xi^{d}(G,v)$ are the same as $\xi^{d-1}(G,v)$. Hence, the property is true for $i\leq d-1$ by immediate induction. We are left to show that $\quad\xi_{d}^{d}(G,v)=1\iff Q(G,v)=Q_{d}(G,v)=1$. Here, we use the fact that:

- •
for every node $v$, every coordinate of $\xi^{d-1}(v)$ is in $\{0,1\}$.
- •
$\sigma$ is the clipped ReLU activation function: $\sigma(\cdot)=\min(1,\max(0,\cdot))$.

Since $\xi^{d}(G,v)=\sigma(A_{d-1}\xi^{d-1}(G,v)+B_{d-1}\sum_{w\in N(v)}\xi^{d-1}(G,w
)+c_{d-1})$
This follows from an immediate discussion on the three cases described previously, and ends the induction on $d$.

An important feature of the update described above is that $(A_{d},B_{d},c_{d})$ verifies all the conditions imposed for every $(A_{t},B_{t},c_{t})_{1\leq t\leq d}$ to compute all subformulas $Q_{t}$. The updates of $A_{t}$, $B_{t}$ and $c_{t}$ are only made for the $t$-th row and $t$-th entry, and do not depend on the previous columns but only on the query $Q$. Hence, we may as well start from the beginning by setting $(A_{t},B_{t},c_{t})$ to $(A_{d},B_{d},c_{d})$, instead of changing these matrices at every iteration $t$. In these conditions, the combination function $\mathsf{comb}_{t}$, parametrized by $A_{t}$, $B_{t}$ and $c_{t}$ can be defined independently of $t$. The same holds for $\mathsf{agg}_{t}$ as it can be chosen as the sum for any iteration.

###### Remark A.12 .

The proof of [] presents an approach where the ReLU GNN is non-recurrent (each $\mathsf{comb}_{t}$ in that case depends on $t$).
The fact that $\xi^{t}$ is a $\{0,1\}$-vector is also crucial so that the argument goes through.
In particular, both proofs do not extend to other activations (such as sigmoid), as there is no function $f:\mathbb{R}\rightarrow\mathbb{R}$ such that
for some $0<\epsilon<\frac{1}{2}$, and for any
$x_{1},\cdots,x_{N}\in[0,\frac{1}{2}-\epsilon]\cup[\frac{1}{2}+\epsilon,1]$,

$$ $f(\sum_{i=1}^{N}x_{i})\geq\frac{1}{2}+\epsilon\iff\text{there are at least $p$ $x_{i}$'s such that $x_{i}\geq\frac{1}{2}+\epsilon$}$ $$

On the one hand, it is necessary that $f(x)\geq\frac{1}{2}+\epsilon$ for any $x\geq p$. Furthermore, it is possible to pick $x_{1},\cdots,x_{N}$ such that for any $i$, $x_{i}\in[0,\frac{1}{2}-\epsilon]$ but $x_{1}+\cdots x_{N}\geq p$. This in turn would imply $f(\sum_{i=1}^{N}x_{i})\geq\frac{1}{2}+\epsilon$ but all $x_{i}$’s are smaller than $\frac{1}{2}$.
The previous property becomes verified if one restricts to $\{0\}\cup\{1\}$ and $f_{p}(.)=\text{cReLU}(\cdot-p+1)$ where cReLU is the clipped ReLU.

###### Proof A.11 .

###### Remark A.12 .

## Appendix B Logic background: general definitions

###### Definition B.13 .

A first order logic is given by a countable set of symbols, called the alphabet of the logic:

- (1)
Boolean connectives: $\neg,\vee,\wedge,\rightarrow,\leftrightarrow$
- (2)
Quantifiers: $\forall,\exists$
- (3)
Equivalence/equality symbol: $\equiv$
- (4)
Variables: $x_{0},x_{1},\ldots$ (finite or countably infinite set)
- (5)
Punctuation: $($, $)$ and ,.
- (6)
(a)
A (possibly empty) set of constant symbols.
(b)
For every natural number $n\geq 1$, a (possibly empty) set of $n$-ary function symbols.
(c)
For every natural number $n\geq 1$, a (possibly empty) set of $n$-ary relation symbols.

###### Remark B.14 .

Items 1-5 are common to any first order logic. Item 6 changes from one system of logic to another. Example: In Graph theory, the first order logic has:

- •
no constant symbols
- •
no function symbol
- •
a single $2$-ary relation symbol $E$ (which is interpreted as the edge relation between vertices). When graphs are supposed labeled with $\ell$ colors: $\ell$ function symbols $\mathsf{col}_{1},\cdots,\mathsf{col}_{\ell}$. $\mathsf{col}_{i}(v\in G)$.

The set of symbols from Item 6 is called the vocabulary of the logic. It will be denoted by $S$ and the first order logic based on $S$ will be denoted by $FO(S)$.

###### Definition B.15 .

The set of terms in a given first order logic $FO(S)$ is a set of strings over the alphabet defined inductively as follows:

- (1)
Every variable and constant symbol is a term.
- (2)
If $f$ is an $n$-ary function symbol, and $t_{1},\ldots,t_{n}$ are terms, then $f(t_{1},\ldots,t_{n})$ is a term.

###### Definition B.16 .

The set of formulas in a given first order logic is a set of strings over the alphabet defined inductively as follows:

- (1)
If $t_{1},t_{2}$ are terms, then $t_{1}\equiv t_{2}$ is a formula.
- (2)
If $R$ is an $n$-ary relation symbol, and $t_{1},\ldots,t_{n}$ are terms, then $R(t_{1},\ldots,t_{n})$ is a formula.
- (3)
If $\phi$ is a formula, then $\neg\phi$ is a formula.
- (4)
If $\phi_{1},\phi_{2}$ are formulas, then $(\phi_{1}\vee\phi_{2})$, $\phi_{1}\wedge\phi_{2}$, $\phi_{1}\rightarrow\phi_{2}$ and $\phi_{1}\leftrightarrow\phi_{2}$ are formulas.
- (5)
If $\phi$ is a formula and $x$ is a variable, then $\forall x\phi$ and $\exists x\phi$ are formulas.

The set of all variable symbols that appear in a term $t$ will be denoted by $\operatorname{var}(t)$. The set of free variables in a formula is defined using the inductive nature of formulas:

- (1)
$\operatorname{free}(t_{1}\equiv t_{2})=\operatorname{var}(t_{1})\cup
\operatorname{var}(t_{2})$
- (2)
$\operatorname{free}(R(t_{1},\ldots,t_{n}))=\operatorname{var}(t_{1})\cup\ldots
\cup\operatorname{var}(t_{n})$
- (3)
$\operatorname{free}(\neg\phi)=\operatorname{free}(\phi)$
- (4)
$\operatorname{free}(\phi_{1}\star\phi_{2})=\operatorname{var}(\phi_{1})\cup
\operatorname{var}(\phi_{2})$, where $\star\in\{\vee,\wedge,\rightarrow,\leftrightarrow\}$
- (5)
$\operatorname{free}(\forall x\phi)=\operatorname{free}(\phi)\setminus\{x\}$
- (6)
$\operatorname{free}(\exists x\phi)=\operatorname{free}(\phi)\setminus\{x\}$

###### Remark B.17 .

The same variable symbol may be a free symbol in $\phi$, but appear bound to a quantifier in a subformula of $\phi$.

###### Definition B.18 .

The set of sentences in a first order logic are all the formulas with no free variables, i.e., $\{\phi:\operatorname{free}(\phi)=\emptyset\}$.

###### Definition B.19 .

Given a first order logic $FO(S)$, an $S$-structure is a pair $\mathcal{U}=(A,I)$ where $A$ is a nonempty set, called the domain/universe of the structure, and $I$ is a map defined on $S$ such that

- (1)
$I(c)$ is an element of $A$ for every constant symbol $c$.
- (2)
$I(f)$ is a function from $A^{n}$ to $A$ for every $n$-ary function symbol $f$.
- (3)
$I(R)$ is a function from $A^{n}$ to $\{0,1\}$ (or equivalently, a subset of $A^{n}$) for every $n$-ary relation symbol $R$.

Given an $S$-structure $\mathcal{U}=(A,I)$ for $FO(S)$, an assignment is a map from the set of variables in the logic to the domain $A$. An interpretation of $FO(S)$ is a pair $(\mathcal{U},\beta)$, where $\mathcal{U}$ is an $S$-structure and $\beta$ is an assignment.

We say that an interpretation $(\mathcal{U},\beta)$ satisfies a formula $\phi$, if this assignment restricted to the free variables in $\phi$ evaluates to 1, using the standard Boolean interpretations of the symbols of the first order logic in Items 1-5 of Definition B.13.

###### Definition B.20 .

The depth of a formula $\phi$ is defined recursively as follows. If $\phi$ is of the form in points 1. or 2. in Definition B.16 , then its depth is $1$. If $\phi=\neg\phi^{\prime}$ or $\phi=\forall x\phi^{\prime}$ or $\phi=\exists x\phi^{\prime}$, then the depth of $\phi$ is the depth of $\phi^{\prime}$ plus $1$. If $\phi=\phi_{1}\star\phi_{2}$ with $\star\in\{\vee,\wedge,\rightarrow,\leftrightarrow\}$, then the depth of $\phi$ is one plus the maximum of the depths of $\phi_{1}$ and $\phi_{2}$.

This is equivalent to the depth of the tree representing the formula, based on the inductive definition. The length/size of the formula is the total number nodes in this tree. Up to constants, this is the number of leaves in the tree, which are called the atoms of the formula.

###### Definition B.13 .

###### Remark B.14 .

###### Definition B.15 .

###### Definition B.16 .

###### Remark B.17 .

###### Definition B.18 .

###### Definition B.19 .

###### Definition B.20 .

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 4
questions: - Could you please briefly explain, and maybe point to the parts of proof, that make capturing anything larger than RGC2 hard? 
- Or otherwise, what motivates you to conjecture " We conjecture it is not the case and that RGC2 is close to the logic expressed by rational GNNs"?
soundness: 4
strengths: - Clarity. The paper is clearly written. I have not checked the proofs provided in the appendix. But the paper draws very clear and well-motivated connections to Barcelo et al. and does an excellent job at presenting the results.
summary: The authors investigate logical expressivity of GNNs, i.e., the first order logic classifiers that can be captured by a GNN, in the uniform setting, i.e., the graph sizes can vary but the parameter size of the GNN remains fixed. This has been completely answered for GNNs without a global readout by Barcelo et al. (2020) --- showing that all such classifiers are exactly the once expressible in the graded fragment of first order logic with two variables, and counting quantifiers (GC2).
In this paper, the authors look at the expressivity of a restricted setting, i.e., the activations functions are represented by a rational function. 
- The authors show that not all classifiers  in GC2 can be captured by a rational GNN. 
- They introduce a restricted fragment of GC2, called RGC2, that can be captured by the GNNs.
weaknesses: - Novelty and relevance. My main concern is the novelty and the relevance of the results. NNs with rational activations seems really a niche, and I am unable to understand the motivation to investigate this fragment. 
- I maybe mistaken, but it also seems that RGC2 is an arbitrary restriction picked up by authors to show some positive results. I think a better attempt towards providing positive results for a larger fragment, or even completely capturing Rational GNNs could have been attempted. 
- I would have been more inclined towards acceptance, if a clear picture of why RGC2 is the best fragment they can capture would have been presented.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: Please refer to Weakness. Among them, the first one is the most important.
soundness: 3
strengths: - This paper extends the results of [Barcelo &. Al., 2020] to MPNNs equipped with rational activations. Many previous works on GNN expressivity do not consider the specific design of aggregation / combination functions and assume they can be arbitrary function. It is therefore necessary and practical to study what GNNs, equipped with different activation functions, can uniformly express.
- For MPNNs with rational activations, this paper adequately shows:
  - Rational MPNNs cannot uniformly express GC2 formulas (which are uniformly expressed by MPNNs if we don't restrict the activation functions)
  - There's a subset of GC2 which is uniformly expressed by rational MPNNs.
summary: This paper studies the expressivity of graph neural networks from the perspective of logic. Concretely, the paper focus on investigating the uniform expressivity of the specific variant of GNNs namely Message Passing Neural Networks. Existing results in [Barcelo &. Al., 2020] have shown that GC2 can be expressed uniformly by MPNNs equipped with ReLU activations, however, uniform expressivity of MPNNs with some other activations, such as rational activations, still remains uninvestigated. This paper investigates the uniform expressivity of MPNNs equipped with rational activations, and proposes the fragment of GC2 uniformly captured by them. The results are justifies by both theoretical analysis and numerical experiments.
weaknesses: - The main contribution of this work is to point out RGC2 as a subset of GC2 which discribes the uniform logical expressivity of rational MPNNs. However, there is only one theorem (Theorem 4) that states all RGC2 formulas are expressed by rational MPNNs, and for a more complete study of GNN expressivity, it is still necessary to:
  - Show RGC2 completely captures the logical expressivity of rational MPNNs (if this was the case). This can be done by either:
    - Proving that RGC2 is equivalent to rational MPNNs in terms of distinguishability, i.e. for arbitrary graphs $G,H$, rational MPNNs distinguish $G$ and $H\iff$ there is a RGC2 formula that distinguish $G,H$ (which I believe is not the case)
    - Proving that RGC2 is the largest logic set captured by rational MPNNs, i.e. for arbitrary logic formula $Q\notin$RGC2, $Q$ is not uniformly captured by rational MPNNs.
  - If the above statements do not hold for RGC2, discuss why it is not feasible to find the subset of logic formulas that satisfies the above statements, and explain why RGC2 is large enough to cover up important properties of rational MPNNs.

## Suggestions:
- This paper focus on a very specific setting of GNNs: MPNNs with rational activations. This paper can be further strengthened by:
  - Discussing why it is important to study rational activations.
  - Extending to more complex GNN variants (i.e., consider higher-order MPNNs, which are direct extensions of MPNNs and are expressed by $\mathrm{FOC}_k$).
  - Extending to different activation functions.

- Other suggestions:
  - The discussion of RGC2 as the main contribution of the paper is short. For example, the authors can discuss the general difference between GC2 and RGC2 (i.e. what kinds of logic formulas are discarded, what patterns GC2 can capture but RGC2 cannot).
  - Theorem 4 is the main theorem of this paper and Section 5 introduces the main constribution. Maybe consider putting Theorem 4 in Section 5?

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: **Universe $A$ Notation:**

 In graph theory, the symbol $A $ typically denotes the adjacency matrix representing the structure of a graph. However, throughout the paper, $ A $ appears to represent the universe and is set to $ V $ in each definition. Could you clarify whether the choice of $ A $ here is tied to a general logic definition? Additionally, in Example 2 of Section 3, $ A $ is introduced as a matrix. To avoid confusion, would it be preferable to use a different letter for this matrix?

**Clarification in Example 2 of Section 3:**

 I would appreciate additional clarification on Example 2 in Section 3. Specifically:
   - **Usage of Vector $ c $**: The vector $ c $ is defined, but it appears to go unused. Could you elaborate on its intended purpose?
   - **Indices in $ \xi^4(G, v)_i $**: The notation $ \xi^4(G, v)_i $ introduces an index $ i $ whose meaning is unclear. As this may pertain to logical constructs that not all readers are familiar with (like me), additional explanation here would improve clarity.

**Typographical Error in Proof Overview (Line 444):** 

In the proof overview, line 444, there appears to be a typographical error. The text suggests that rational GNNs can uniformly express GC2, which is contradictory to Theorem 3. Could you confirm if this is an error or provide clarification?

**Loss Curve Analysis:**

Have you analyzed the training loss curves for both CReLU and rational GNNs on the training set? Examining these curves could provide insight into your theoretical claim. For instance, if rational GNNs indeed struggle to express certain GC2 queries, we might observe a higher or stagnant training loss. Such empirical observations could help substantiate your theoretical findings.

**General typographical error:**

 - **line 181**: for **a** some elements of comparison of expressivity of targeted vs standard ones. **a** should be removed.
 - **line 309** :  $(Q_1,Q_2,Q_3,Q_4)$ instead of $(Q1,Q2,Q3,Q4)$. 
 - **line 360** : Our approach **and** can easily extend to a large family of GC2 queries. **and** should be removed.
 - **line 450** : **Then**, we **then**. One **then** should be removed.
soundness: 2
strengths: **Novelty and Idea:**

Given the demonstrated advantages of rational activation functions over ReLUs in traditional neural network architectures, the authors propose the compelling idea of extending this approach to Graph Neural Networks (GNNs).

**Theoretical Contribution:** 

The authors demonstrate that, in the context of GC2, GNNs with rational activation functions exhibit lower expressivity compared to those using ReLU activations.

**Pedagogical Clarity:**

The authors have made effort to clarify the logical foundations required to understand GC2 and related fragments. Section 2, in particular, is highly accessible and does an excellent job of providing readers with the necessary background in logic. This careful exposition allows the paper to be more approachable to readers who may not have a strong background in formal logic.
summary: This paper explores the impact of rational activation functions in specific classes of Graph Neural Networks (GNNs) on their capacity to uniformly approximate queries from the two-variable guarded fragment with counting (GC2). In this context, uniformly indicates that the number of GNN parameters is dependent solely on the query depth rather than the graph size. While prior studies show that GNNs with ReLU activations can uniformly express GC2, the authors demonstrate that certain GC2 queries cannot be captured by GNNs with rational activations. They further introduce RGC2, a fragment of GC2 expressible by GNNs employing rational activations. The authors conduct experiments demonstrating that approximations for specific queries remain stable as the number of nodes increases.
weaknesses: **Lack of Literature Examples for GNN Types:**

 In Remark 1, the authors discuss three types of Graph Neural Networks (GNNs); It would be helpful if you could provide specific examples from the literature for each GNN type mentioned. This would give readers a better understanding of how these different GNN architectures have been applied in practice and studied theoretically.

**Clarity Issues in Example 2 of Section 3:**

 Example 2 in Section 3 presents some ambiguities, potentially due to complex logical reasoning. For readers who may not be experts in logic, further clarification or simplification would enhance comprehension. Presenting the example in more accessible terms could improve the paper’s accessibility and impact.

**Figure 1 Caption:**

To improve Figure 1, consider expanding the caption to provide more context about what the figure represents and how it relates to the main concepts discussed in the paper. This would allow readers to understand the figure's significance without needing to refer back to the main text.

**Limited Scope of Experiments:**

 The experimental evaluation in this paper is restricted to two queries, and the results do not fully corroborate the theoretical assumptions made by the authors. Additionally, the authors claim that a ReLU GNN can approximate CReLU GNN, but no direct comparison is provided in the experiments. Including a comparison with a ReLU GNN would strengthen the experimental results and help substantiate the authors’ claims.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 1
questions: 1. Why should we care about GNNs with rational activations?

2. What does L484 - L485 mean by "as the mean square error stabilizes around a value for large graphs"?
soundness: 3
strengths: 1. The problem statement and corresponding objectives are clear
2. There is good reference to existing work and how this paper fits into it
3. The paper builds upon an interesting body of work that is relevant to the ICLR community - the expressivity of GNNs
summary: This paper analyses the expressivity of GNNs with rational activation functions, building on previous work that characterises the expressivity of GNNs using a fragment of first-order logic (GC2). They provide two main results: 1) they show that there are GC2 expressions that cannot be uniformly (i.e. GNN size does not depend on input graph size) captured by GNNs with rational activations, and 2) they define a fragment of GC2 (RGC2) which GNNs with rational activations can capture. Finally, they run experiments on two artificial datasets (corresponding to two different queries) to test the abilities of Rational vs ReLU GNNs.
weaknesses: 1. The significance of the contribution is small. It is not clear, either from references or experiments, why we should care about GNNs with rational activation functions - could such references or experiments perhaps be provided?. Thus, these (already minor) theoretical results about what fragments of logic they can and cannot express do not seem substantial.

2. The presentation is lacking.

2.1. The background takes up far too much space, with novel contributions of the paper first appearing on page 7. The background is also too verbose, since anyone who is interested in this work will either already be familiar with much of the background, or can go read some of the literature. I suggest rather summarising the background knowledge and referring the reader to the appendix / related work for a more in-depth explanation. For example, L185 - L205 uses a lot of space to define FOL on graphs. It can be condensed both by cutting whitespace, and by being less verbose.

2.2 The structure makes it difficult to follow: all theoretical results are presented in L335 - 352, with the proof sketches and explanations appearing far below. RGC2 is only defined in L416 but references in a theorem in L351. All technical terms should be defined before they are used and proof sketches / intuitions should appear near one another. Remark 5 is not useful, since it is referencing things that are only in the appendix, and cannot be made sense of without first reading the appendix. If it could be presented more intuitively, or in a way that makes it clearer why it is relevant to the proof, that would help.

2.3 In general, the space is used poorly, and the paper did not need the full 10 pages. Parts of the paper are lacking intuition and explanation (e.g. section 3) whilst others are far too verbose. For example, L250 - L269 ends up repeating much of what was said above.

3. The experiments are small in scope and the results that were obtained seem to undercut the significance of the theoretical contribution, since the theoretical advantage of CReLU GNNs does not transfer to a practical advantage. To better support the work, more substantial experiments should be performed across both artificial datasets (i.e. on more queries) as well as on some standard benchmarks.