Graph Neural Networks and Arithmetic Circuits
Authors: Timon Barlag
Vivian Holzapfel
Laura Strieker
Jonni Virtema
Heribert Vollmer
Venue: NeurIPS 2024 poster (2024)
Keywords: Machine Learning
Graph Neural Networks
Arithmetic Circuits
Computational Complexity
Primary area: graph_neural_networks
TL;DR: We obtain a characterization of the computational power/expressivity of graph neural networks in terms of arithmetic circuits over the reals.

Abstract: We characterize the computational power of neural networks that follow the graph neural network (GNN) architecture, not restricted to aggregate-combine GNNs or other particular types. We establish an exact correspondence between the expressivity of GNNs using diverse activation functions and arithmetic circuits over real numbers. In our results the activation function of the network becomes a gate type in the circuit. Our result holds for families of constant depth circuits and networks, both uniformly and non-uniformly, for all common activation functions.

Graph Neural Networks and Arithmetic Circuits
Timon Barlag
Vivian Holzapfel
Institute for Theoretical Computer Science
Institute for Theoretical Computer Science
Leibniz University Hanover
Leibniz University Hanover
Hanover, Germany
Hanover, Germany
barlagOthi, uni hannovrnn de
holzapfel@thi. uni -ainhnnnverr de
Laura Strieker
Jonni Virtema
Institute for Theoretical Computer Science
School of Computer Science University of Sheffield Sheffield, United Kingdom
Leibniz University Hanover
Hanover, Germany
strieker@thi. iaceiiiunn-hhaae wa--ahhneve..dd de
j j.t. wewirtema@shefffeeleee ac.
Heribert Vollmer
Institute for Theoretical Computer Science
Leibniz University Hanover
Hanover, Germany
vollmer@thi. uni mmi-hhnnover.
Abstract
We characterize the computational power of neural networks that follow the graph neural network (GNN) architecture, not restricted to aggregate-combine GNNs other particular types. We establish an exact correspondence between the expressivity of GNNs using diverse activation functions and arithmetic circuits over real numbers. In our results the activation function of the network becomes a gate type in the circuit. Our result holds for families of constant depth circuits and networks, both uniformly and non-uniformly, for all common activation functions.
1 Introduction
Neural networks have recently received growing attention from a theoretical point of view number of papers studying their computational properties. Relevant this paper examinations of the computational power of neural networks after training, i.c., the training process is not taken into account but instead the computational power of optimally trained network is studied. Starting already in the ninetics, the expressive power feed-forward neural networks (FNNs) has been related Boolean threshold circuits, see, e.g., [Maass al. 1991, Siegellann and Sontag 1995 Maass 1997 He and Papakonstantinou/ 2022]. Most importantly. Maass] 1997] showed that when restricting networks to Boolean inputs, language can be decided by family of (in certain sense) "polynomial-size" FNNs if and only if it belongs to the class TC" i.e., the class of all languages decidable by families of Boolean circuits of constant depth and polynomial size using negation gates and unbounded fan-in AND, OR, and threshold gates.
In the last five years attention has shifted the study of graph neural networks (GNNs) which is
model for machine learning tasks graph-structured inputs. Their expressive power can be closely related the Weisfeiler-Leman algorithm [Xu et al., 2019 Morris et al., 2019 202T]. Originally developed to solve the graph isomorphism problem, the WL algorithm is connected to fragments of first-order logic; hence the logical expressiveness of GNNs was subsequently studied. Barceló et al.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

2020 consider so- so-called logical classifiers these are unary formulas of first-order (FO) predicate logic that classify a node in a given graph according to whether the formula holds for this node. Barceló et al. proved that all classifiers definable in certain fragment GC (guarded first-order logic with counting quantifiers) are computable by GNNs. The converse direction a bit problematic; is only known to hold for unary queries definable in first-order logic. This result has been broadened recently by [Benedikt et al. 2024] using logics with Presburger quantifiers. Barceló et al. then consider extension of GNNs by so-called global readout and show that these GNNs can compute all queries from the logie FOC, (first-order restricted to two variables, but extended with counting quantifiers, superclass of GC), but the converse is open.
Our motivation. Neural networks in general and GNNs specifically have mostly been studied through the lens of Boolean functions. This does not necessarily reflect on the usage of machine learning models in real-world applications. We want to shift this focus to real-valued computations and hence, in this paper, we make real numbers first-class citizens. When networks are digitally simulated in practical applications, of course only rational numbers are used as inputs, and the real numbers that appear during their computation (e.g., via the sigmoid function) are approximated by rationals. However, we are interested in principal statements about the computational power of neural networks-henc' we study networks as devices operating with real numbers. We do not solely consider networks that are restricted to Boolean inputs or Boolean outputs (Boolean queries, logical classifiers), as done in all the papers cited above. Instead, consider GNNs as model to compute functions from (vectors of) real numbers to (vectors of) real numbers, or from labeled graphs (i.e., undirected graphs whose nodes annotated with vectors of real numbers) to labeled graphs
Instead of turning to logies, we focus on a computation model that has been used to capture the expressivity of neural networks in the past: we use circuits, but since we turn away from the Boolean computation model, we use arithmetic circuits over the reals, that is, circuits that take real numbers as inputs and have nodes that compute real functions such as addition, multiplication, projection, or a constant function. Why do we do that? It will turn out that in this way we obtain a close correspondence between GNNs and arithmetic circuits. Arithmetic circuits can in a second step be simulated by a Boolean computation model, but this does not say anything about the computational power of the networks. Going directly from neural networks to Boolean circuits mixes up two different issues and obscures statements about the power of GNNs. By separating the two aspects, we do not only obtain upper bound, or correspondence with respect to discrete classification tasks, but an equivalence between GNNs and conttant-depth arithmetic circuits over the real functions they compute. In this way, we shed more light the computational model behind GNNs. Our results show very explicitly what the computational abilities of GNNs are and what elementary operations they can perform.
We also want to make a general statement about scaling and complexity. A common narrative nowadays seems to be that by making neural networks larger and larger, they can solve more complex reasoning tasks. However, theoretical limitations as proven in this paper show that scaling is not all we need. Our results show that to improve the expressivity of GNNs, more computationally complex aggregation and combine functions are needed. More precisely, these functions need to come outside of the class FACE, which contains functions that can be computed by arithmetic circuits that are bounded in size and depth, see Definition 2.11 for a precise definition. Another approach would be to change the fixed depth framework of GNNs to one that includes recursion, for example.
Following broad line of research outlined by Merrill [022) in this paper, we aim at a general statement about the computational power of neural networks following the GNN architecture, i.c.. networks operating in layers where connections within layers and hence their communication capa- bilities correspond to the given input graph. However, contrary to most predecessor papers [Morris] et al. 2019 Barceló et al. 2020). we do not only consider so-called AC-GNNs, i.e., GNNs where the computation in each node of a layer of the network consists first of an aggregation step (collecting information from the adjacent nodes of the graph-very often simply summation), followed by a com- bine step (combining the aggregated information with the current information of the node- node-mostly a linear function followed by unary non-linear activation function such sigmoid ReLU). AC- GNNs like these are just one example of a GNN architecture. We take a more general approach. The GNN framework defines a continuous graph- based "message passing" [Gilmer et al. 2017 Morris ct al. 2019]. In our networks we keep the layout and message passing mechanisms of GNNs but equip the nodes in each layer with constant-depth arithmetic circuits (taken from a previously fixed basis of circuits), not limited to the usual eegregate-combing (AC) operations. We call these networks

---

C-GNNs, circuit graph neural networks. AC-GNNs, whose aggregation function is computable by a constant-depth circuit, can be simulated by C-GNNs (using the same activation function). The computational upper bounds we obtain thus point out general computational limitations for networks following the GNN message passing framework.
Main Results. The main contribution of our paper is an exact correspondence between C-GNNs and arithmetic circuits. A function (from labeled graphs to labeled graphs) is computable by C-GNN with constant number of layers if and only if it is computable by a constant-depth arithmetic circuit over the real numbers. The activation function of the neural network will be a gate type in the arithmetic circuit. Thus, the (set of) actual activation function(s) becomes a parameter in a general statement equating the computational power of GNNs and arithmetic circuits.
A number of remarks are in order.
Our result holds for all commonly used activation functions.
Our result is uniform. If we start with a family of GNNs whose individual networks can be generated via some algorithm, the resulting family of arithmetic circuits will be uniform in the same way, and vice versa.
Our result gives general limits for neural networks following the GNN message passing framework, including but not restricted to the currently widely used AC-GNNs. This means that in order to use GNN to compute function not computable by constant-depth arithmetic circuits, scaling GNNs up or adding computational power in the individual nodes will not help, but neural networks of completely different architecture are needed.
This paper follows a modular approach. We stick to the GNN message passing framework, but allow computations of arbitrary power in the individual nodes of the graph. Our approach is adaptable and opens possibilities for many extensions; we point out a few in our conclusion section.
We would like to stress that theoretical insights like those presented in this paper have the potential to guide practical development. We prove principal limits of networks following the GNN framework, extending the current AC-GNNs. Our results enables the use of theoretical results regarding arithmetic circuit complexity for arguing about the complexity of GNNs. For example findings for a complexity hierarchy within the real valued FAC* will lead corresponding statements about the power of GNNs. They may also be used to design GNN architectures with provable expressivity bounds.
Organization. In the next section, we introduce the relevant notions about GNNs and arithmetic circuits. Section 3 contains our results. In Subsection 3.1 we introduce Circuit-GNN Creuuit-GNNs as a general- ization of AC-GNNs. In Subsections 3.2 and 3.3 we show how to simulate C-GNNs by arithmetic circuits, and vice versa. In Section 4 we point out a number of questions for further research. Due to lack of space, we only provide proof sketches for some of the proofs and refer to the arXiv version Barlag et al. (2024) for the full proofs.
Related Work. The first model of GNNs was introduced by Scarselli et al. (2099]. Since then, their expressive power has been studied in numerous works and from various perspectives as discussed above. As mentioned already, [arceló et al. [2020] established a close connection between classifiers definable in guarded FOC₂ and computable by AC-GNNs. It is worth to point out that a connection very close to the aforementioned one can be obtained by connecting the results of (Sato al. [019). ,
that relate graph neural networks with more general models of distributed computation, to the results of Hella et al. [2015). that logically characterize expressivity of those models of distributed computation with graded modal logics (known to be equivalent with guarded FOC2). Grohe [0223 very recently extended these characterization results for GNNs, and furthermore connected GNNS to Boolean circuits. He considers an FO-fragment GFO+C (guarded fragment of FO plus a more general form of counting than used by Barceló et al.) and proves equivalence of this logic to GNNs for unary queries, that is for Boolean functions (functions with Boolean output). However, his overall result holds only in the non-uniform setting (that is, the sequence of GNNs for graphs of different sizes is non-uniform in the sense that there is not necessarily an algorithm that, given a graph size, computes that network from the sequence responsible for the given size), and the activation functions have to be "rpl approximable" (i.e.. rational piecewise linear approximable, i. e., the real functions must in a certain way be approximable by Boolean circuits or logic). This includes most of the commonly used activation functions. Since queries expressible in this logic known to be T computable, he obtains TC upper bound for the computational power of GNNs. For the converse connection, an extension of GNNs is necessary, and it is shown that a unary query computable by a
3

---

TC circuit is computable by GNN with so-called random initialization. Another line of work that focuses on real-valued computations includes [Geerts et al. 2022 where the logic MPLang operating directly on real numbers was introduced to readily express GNN computations. The main goal of that paper was to reason about GNNs using logic, extended by real-number computations. However, the converse connection, from MPLang to GNNs, is highly unclear. Other work addressing the precise characterizations of expressivity issues of GNNs outside of the restriction to the Boolean setting with GNNs using formal logic include [Cucala et al. 2023 Pfluger et al., [024]. To the best of our knowledge, there are no other works considering valled computations and circuits or arithmetic circuits. Another approach that leans more into comparing the expressivity when using different functions for aggregation in the GNN can be found in Rosenbluth et al. (2023]. where they compared the expressivity of GNNs using sum as their aggregation with mean and max GNNs.
2 Preliminaries
Throughout this paper, the graphs we consider have an ordered set of vertices and are undirected unless otherwise specified. We use overlined letters to denote tuples, write [T] to denote the length of E (i.c., the number of elements of F), and use [n]] to denote the first n nonzero natural numbers .n.....n.. For a & E N we denote all possible n-tuples for every n of IR* with (R²)) The notation ( is used for multisets. A restriction of function f to set S is written as sis.
Definition 2.1. Let & E N, and let G (V, E) be graph with an ordered set of vertices V and set of undirected edges E on V. Let gv: V - R& be a function which labels the vertices with attribute vectors. We then call 6 EV gv) a labeled graph of dimension it and denote by Braph the set of all labeled graphs and by Graph;; the set of all labeled graphs of dimension k.
For node u V, the neighborhood of is defined as (v) = {w E V {v,w) E E).
In order to compare standard graph neural networks and the circuit graph neural networks which we will introduce later on, we fix the notion of a graph neural network first. Generally, GNNs can classify either individual nodes or whole graphs. For the purpose of this paper, we will only introduce node classification graph classification works analogously. We focus on aggregate combine graph neural networks that aggregate the information of every neighbor of a node and then combine this information with the information of the node itself.
An aggregation fanction (of dimension ke) is a permutation- -ivvaiiiinnnnnniinnttt function AGG X R a combine function (of dimension k) is function COM R x R - IR* and classification function (of dimension k) is a function CLS: : IR* + {0, }} that classifies a real vector as either true or false. Finally, an activation function (of dimension k) a componentwise function σ: R + E
Definition 2.2 (AC-GNN, cf. [Barceló et al. 2020 D. An L layer aggregate combine graph neu- ral network (AC-GNN) is a tuple DD = ((AGG))) H (COM()) (o(0) CLS), where (AGG 1=1 and (COM }.=_ are sequences of aggregation and combine functions, {a 1 is a sequence of activation functions and CLS is a classification function.
Given a labeled graph 6- = gv)), the AC-GNN model computes vectors In for every v E V in every layer < i < L as follows: z(") gv gv(v) the initial feature vector of v, and for > 1
a = (6) (COM
(1 ( v)) where = AGG ( (K | (v))
The classification function CLS: R + {0, 10 is applied to the resulting feature vectors z/
In this paper we focus on the real-valued computation part of GNNs and discard the classification function. We consider the feature vectors ( after the computation of layer L as our output. While we could also integrate CLS into model, for our concerns this is not needed.
Next we define arithmetic circuits as model of computation for computing real functions. Since we will put them in the context of graph neural networks, which inherently operate on vectors of real numbers rather than individual reals, we will accordingly define arithmetic circuits relative to R rather than relative to RR, as is done more commonly (cf. e.g. [Blum et al. 1997].
Definition 2.3. Let k, n. m E N. An & -arittimmetic circuit with n inputs and m outputs a simple directed acyclic graph of labeled nodes, also called gates, such that

---

there are exactly n gates labeled imput, which each have indegree 0,
there are exactly m gates labeled oupuu, which have indegree 1 and outdegree O,
there are gates labeled constant, which have indegree O and are labeled with a tuple E TR*, there are gates labeled projections.j for 1 i S k, which have in- and outdegree 1,
there are gates labeled addition and multiplication.
Additionally, both the input and the output gates are ordered.
An R* -a-arithmettic circuit with n inputs and m outputs computes the function fc: (R+)* - )I as follows: Initially, the input to the circuit is placed in the input gates. Afterwards, in each step, each arithmetic gate whose predecessor gates all have a value, computes the respective function it is labeled with, using the values of its predecessors we refer to the respective componentwise operations and the projection computes the function proje.; R T (I1,-... T.,.... rk) (0, (O....,0, O, Ti ,0....,)). Analogously, each output position
inputs. By addition and multiplication
gate takes the value of its predecessor, once its predecessor has one. The output of fc is then the tuple of values in the m output gates of C' after the computation.
The depth of C' (written (C) is the length of the longest path from an input gate to output gate in C and the size of C (written size(C)) the number of gates in C. For gate g in C, we will write depth(g) to denote the length of the longest path from an input gate in C.
Remark 2.4. In the context of the circuits over R$ that have just defined, circuit over R is just a circuit over TR.. Note that for circuits over TR,, projection gates are just identity gates and can therefore be omitted. It should also be noted that for any fixed k N. circuits over R and circuits over R can easily simulate each other. For a detailed explanation see the arXiv version Barlag et al. 2024
Since an arithmetic circuit itself can only compute function with a fixed number of arguments, we extend this definition to families of arithmetic circuits in natural way.
Definition 2.5. An TR* -arithmetic circuit family is a sequence (Cn) (Cn)eeN of circuits, where each circuit C, has exactly input gates. Its depth and size functions mapping natural numbers n to (C.) and size(C,), respectively.
An arithmetic circuit family C (Cn)neN computes the function fe: (R+ + (I* defined as (T) =
Remark 2.6. Since a circuit family is an infinite sequence of circuits, one would be hard pressed to consider such family a (finite) algorithm. Such models of computation, where different instance is needed for any different input length. is called non-umiform. In order to deem a circuit family (Cn)en to be an algorithm, a frequent requirement the existence of algorithm which, when given n as an input, outputs the circuit C,. Circuit families, for which such an algorithm exists are called uniform circuit families. For more details on circuit uniformity, see e.g. Vollmer 11999 and for more on uniformity with respect to real computation, see Blum et al. [199].
Definition 2.7. For any k E N and any two functions s, d: N + N, PSIZE-DEPTHA (s, d) is the class of all functions (IR + (R$)* that are computable by arithmetic circuit families of size in (ss) and depth in ((d). Let A a set of functions of the form f: TR - R Then FSIZE-DEPTH (s, [[[ is the class of functions computable by arithmetic circuits with the same constraints, but with additional gate types gr. with indegree and outdegree 1 that compute f. for each f A.
We call all classes of the form FSIZE-DEPTH (s, d)[A) (and their subclasses) circuit function classes. As usual in circuit complexity, 3-circuit family, where class of functions, will denote a circuit family that computes a function in 3.
We restrict this work to versions of one specific circuit function class.
Definition 2.8. FAC2, e is the class of all functions f: (R*)* (R+ that be computed by arithmetic circuit families (Cx) of constant depth and polynomial size, i.e. FACE FSIZE-DEPTHp. (n (1),,))
By Definition 2.7 FACE [i]-cir families are FAC -irreuut families where the circuits are expanded by additional gate types for all functions in A.
5

---

A node in graph neural network aggregates the values of its neighbors in each step, irrespective of their order, and then combines them with its own previous value. In order for our circuits to mimic this behaviour, we impose symmetry condition on them. We require the functions they compute to be tailssymmetric, i.e., to only be able to single out their first argument.
Definition 2.9. A function f: (IR*)* + (R*)* is tail-symmetric, if f( Tn)
( (T (,,,,., I.,) for all permutations π.
Remark 2.10. One way to construct a tail-symmetric function ff to take a binary function g and fully symmetric function h of arbitrary arity and compose them: f = g( h(r2...., )n)). Note that this is precisely the notion required for the aggregate-combing step in AC-GNNs per Definition 2.2
An arithmetic circuit C is tail-symmettric if fc is tail- sail-mymmetric. In the sequel, will consider fami- lies of tail-symmetric functions computed by some circuit family C. In this setting, the circuit family computes one unique function f.. for each arity denote fn (T1, Tn), when ([ Jn } is a multiset of cardinality n -
N. We will then write Se (#1, = Fn B) to
Definition 2.11. Let & be a circuit function class. We denote by tš the class which contains all functions of & that are tail-symmetric.
3 Graph Neural Networks using Circuits
We now define the main computation model of interest for this paper, namely circuit graph neural networks (C-GNNs). C-GNNs work similarly to plain AC graph neural networks. Instead of using the concept of two-step aggregate and combine computation via which the new feature vector of node is computed, C-GNNs permit that this computation is done by an arithmetic circuit (with particular resource bounds). This allows us to classify GNNs based on the complexity of their internal computing functions.
3.1 Model of Computation
A basis of a C-GNN is a set of functions of specific circuit function class along with a set of activation functions. The respective networks will be based on these functions.
Definition 3.1. Let S be non-empty set of functions from (R*)* to (IR*)* and let A be non-empty set of activation functions of dimension k. Then we call the set S x A a C-GNN-basis of dimension k.
C-GNNs of particular basis essentially consist of a fixed depth and a function assigning circuit families and activation functions from its basis its different layers.
Definition 3.2. Let B = S A be C-GNN- -asis of dimension k. A circuit graph neural network (of dimension kt) of depth d E N is a function N: : [d] + B. all functions in S belong to a circuit function class
also say that A is (3 A)-GNN.
Definition 3.3. Net be C-GNN of depth d. The function fx: Graph; + Graph;; computed by N defined as follows:
Let @ = (V, g. be labeled graph. The labeled graph &' computed by fxx(8) has the same structure as G, however, its nodes have different feature vectors. That is fr( G', where 8' = (V, hv) and by is defined inductively as follows:
1 (w) = (w) n (w) = (()) (Sow (nL (w), with M M = (/-0-)0 u Ne(w))
where N(i) = (c))),(())) Finally by (w) = 1 (w).
The C-GNN model that we have just defined computes functions from labeled graphs labeled graphs (with the same graph structure).
Our results are stated for C-GNNs using functions from versions of the function class FAC as defined in Definitions 2.8 and 2.11

---

Remark 3.4. We can relate our C-GNN model to the continuous computation of traditional AC- GNNs. For any AC-GNN following Definition 2.2 with activation functions A and where the aggregation functions are computable by -iireit families, there exists () A)-GNN with a constant number of layers which computes the same function, omitting only the functionality of the classification function. This holds for the common aggregation functions like the sum, product or mean.
3.2 Simulating C-GNNs with arithmetic circuits
Definition 3.5. Let 6 (V, F., gv) be labeled graph, n [V], and M adj(G) be the adjacency matrix of (V, F), where the columns are ordered in accordance with the ordering of V. We write (M) to denote the encoding of M as the n² matrix entries written using vectors (O...., 0) and (L....: 1) in Rt ordered in row wise fashion. We denote them by myy encoding the matrix entry Maj. We write (6) to denote the encoding of 6 as a tuple of real valued vectors, such that ((M),
(0) ((M), (e) E (I84yn**,, which consists of the encoding of M followed by ve) the feature vectors of B. The feature vectors vec(G) are gv (v) for all v E V and ordered like V.
Theorem 3.6. N be (tFACg) [A], (id])) Then there exists an FACe [A]-circuit family C, such that for all labeled graphs & the following holds: fx(() = 8' iff ((()) (G'), where (8) = ((adj ()), (vec(()),
Proof. We essentially roll out the given (#FAC [A], (id))- N by using circuit to simulate each individual layer of N and concatenating these circuits to then simulate No Since the computation in each node of N can be performed by circuit of FACE. [A]- Al]ffmmlly simulating this computation can be done without an issue. Similarly, connecting the simulated nodes and layers can be done relatively simply, and thus the resulting circuit family is an FACE [A]-family. The full proof can be found in the Xiv version Barlag al. 2024
Remark 3.7. Note that this proof preserves uniformity: if the sequence of C-GNNs is uniform, so is the circuit family. Furthermore, for any set of activation functions A, (tFA CF [A], {id))-GNNs are at least as powerful as (AFAC&. {id] U A)-GNNs and (#FACg {id]) -NNNN. The latter do not have access to the functions of A at all and (#FAC {id} U A)-GNNS are more restricted in the use of the functions than (/FACH [A], {id])-
3.3 Simulating arithmetic circuits with C-GNNs
In order to simulate FAC&&-circur families using C-GNNs, we utilize the following normal form. Definition 3.8. A circuit C' is in path-length normal form if every path from an input to output gate has the same length and every non-input and non-output gate has exactly one successor.
Lemma 3.9. Let C be an FACa--circut family. Then for every circuit C E C there exists circuit C' of the same depth in path-length normal form such that for (7) = fT) for all I E (R²).
Proof. We describe a procedure that transforms to C². If a gate in C' has more than one successor, the subgraph consisting of h and all paths from input gates to h are copied in C" for each successor of h. These copies are then used as the respective input for those successors which results in every gate in C" having only one successor. This is done iteratively, where in each step only gates in one depth layer of the circuit are modified, starting with depth 1, the gates closest to the input gates. Each step in this procedure incurs a polynomial overhead in size. Since C' is of constant depth there are only constantly many iteration steps and thus C' remains polynomial in size.
Let max = depth dC")h(C")) be the length of the longest path from an input to an output node in C. For every path of length l which is shorter than Lmaz. we add to C' Lmaz - unary addition gates directly after the input. The depth of the resulting circuit C" equals the one of C, as all changes to path lengths are made with this upper bound mind. Since all changes made preserve the computed function and the produced C' is in path-length normal form, the claim follows.
Since C-GNNs get labeled graphs as their input, while arithmetic eircuits typically work on vectors over R we show next how to represent circuit an input to a C-GNN.
7

---

(1)
(1)
inn
6
Pine
9
iin 5
Pini
Vinz
Vina
nr(9+) =1
(1)
0+
nx(xx) 2
x
(1)
2
Ux
(a) Underlying circuit, to simulated by the C- GNN (nr(x) denotes the unique number of the gate).
(b) The labeled graph and initial feature vectors of the C-GNN (0g denotes the feature vector a gate at layer i).
Figure Example illustrating the proof of Theorem 3.11
Table Example illustrating the proof of Theorem 3.11 The values of the feature vectors during the
computation of the C-GNN.
LAYER
Viny
Ving
Ving
U+
Ux
6
9
5
1
2
9
6
9
6
9
5
15
x 15
75
Definition 3.10. If C' is circuit with input x: whose gates additionally numbered with unique elements of R. let &c be the labeled graph (G, gv). where G = (V, E) is the underlying graph of the circuit and the function gv is defined follows. The feature vector of graph node corresponding to an input gate is the corresponding input value. Each other node gets its own number according to the gate numbering of the circuit its feature vector.
The following theorems describe how C-GNNs able to simulate arithmetic circuits. The proofs are given for R circuits, but as mentioned in Remark [2.4] families of constant depth and polynomial size R and R circuits can simulate each other with constant increase/decrease size, they also hold for I circuits.
Theorem 3.11. Let C = (Cu))NN be GNN N. such that for all n E N and E E R", the feature vectors of the nodes of f corresponding output gates in Cn exactly the components of fc (z) in the same order. The number of layers in N is equal to the depth C.C.
family. Then there exists (EFAC) (id))-
Proof. The general idea is use the graphs of the eircuits from C as input graphs for C-GNN and then simulate the gates layerwise. The gates of C. are numbered and the numbering is represented in the feature vectors for each node. In each layer circuits of the C-GNN use a lookup table decide which operation is applied to a feature vector. An example illustrating the proof idea is given in Figure and Table For simplicity reasons an example omitting any special cases chosen. The full proof can be found in the arxiv version Barlag et al. [2024].
Since we have shown in Section 3.2 that C-GNNs can be simulated by FAC [A] [A]-circuit families we now examine the converse direction: simulating these families with C-GNNs.
Theorem 3.12. Let C (Cn)neN be an FACK A]]-ircuuit family. Then there exists (IFACR[A) [A), (id)) N, such that for all E N and x E IR"", the feature vectors of the nodes of IN (Bc..) corresponding output gates On are exactly the components of fc,, (x) in the same order. The number of layers in N is equal to the depth of
8

---

iin
(1)
6
Uin1
Vina
T ing
6 9
nr(ge) =
nr(g)) =
Uo
y/¹
0
2
nor(+) =3
3
V+
(b) The labeled graph and initial feature vectors of GNN (nr(x) denotes the unique number of the the C-GNN (eg denotes the feature vector of gate).
(a) Underlying circuit, to be simulated by the C-
gate at layer
Figure 2: Example illustrating the proof of Theorem 3.17
Table 2: Example illustrating the proof of Theorem computation of the C-GNN.
3.17 The values of the feature vectors during the
LAYER
Vin
Ujag
V
1
6
9
1
2
3
2
(66)
(9)
a (1)
(9)
a (3)) =
(3))
3
(6)
(9)
(1)
(9)
(66 (9()
Proof. The proof follows the same concept as the proof of Theorem 3.11 With the exception that the internal circuits of the C-GNN now have access the same set of functions AA in the form of gates that compute them. Those are then used to simulate gates from that compute functions of AA. The full proof can be found in the arXiv version [Barlag et al. 2024
In the previous two theorems, we have shown that C-GNNs can simulate FAC -circuit families as is and that they can simulate FAC [AA--circuii families if they have arbitrary access to the functions we consider A consist of activation functions, though, it would more natural to only permit them as such in our C-GNN model. In the following will introduce structural restriction of circuits, which will allow us to capture subset of FACE C (A] using C-GNNs that have access to A only as activation functions.
Definition 3.13. A circuit C' is said to be in function-layer form if it is in path-length normal form and for each depth d S dCpth(C') all gates of depth have the same gate type.
Definition 3.14. Let 3 be circuit function class. We denote by /3 the class which contains all functions of & that can be computed by circuit families where all circuits are in function-layer layer form.
We also need a small restriction on the functions we will permit as activation functions.
Definition 3.15. A computable function f: 1²* _* is countably injective if there a countably infinite set S C R such that fis is injective. We also say that f is countably injective on S. Remark 3.16. The commonly used activation functions ReLU(z) max(0, x). (xx) T+e and
tanh(z) 0"40
-- are countably injective.
Theorem 3.17. Let be set of countably injective activation functions and let C. (Ga) be SFACA Al-circuit family. Then there exists (IFACR, AU (id))-GNN N, such that for all n E N and F E IR", the feature vectors of the nodes of Jx (Gc,,) corresponding to output gates in Cn are exactly the components of JC.,, (x) the same order. The number of layers in N is equal to the depth oCC.
Proof. Contrary to the proof Theorem 3.12 the gates in computing function a E A are simulated in the C-GNN by using the respective function activation function applied to all

---

nodes. To distinguish between nodes where this function should and should not be applied we assign a-1 of the respective feature vectors of nodes where we do not want to change the value. This is done prior to the application of the activation function. Therefore the function needs to be injective on some countable set. An example illustrating the proof idea is given Figure and [ As in the proof of Theorem 3.17 an example omitting any special cases is chosen. The full proof can be found in the arXiv version Barlag et al. 2024].
4 Conclusion
In this paper we showed a correspondence between arithmetic circuits and a generalization of graph neural networks using circuits. However, some restrictions needed to be imposed on the particular circuits used in our constructions. In particular, the circuits used in our C-GNNs need to be tail symmetric, and in Theorem 3.17 the corresponding FAC [A]-circuit family needs to be in -aacioon-llyer form as well. An interesting avenue for further research is the question, whether those restrictions can be made "on both sides in our simulations". This means, in particular, to ask (#FAC),, {id} U A)-GNNs can be simulated by fFACR* [A] families and, (tfFACC+ {id} U A.- GNNs and fFACe lel [A] can simulate each other. Another direction of further work is to study whether by relating our C-GNNs to variants of so-called VVc-GNNs Sato al. [2019), may drop the assumption of tail-symmetry.
We already mentioned the issue of uniformity. If the sequence of GNNs, one for each graph size, is uniform in the sense that there an algorithm that, given the size of the graph as an input, outputs the GNN responsible for that size, then the sequence of arithmetic circuits will also be uniform, because our simulation proof explicitly shows how to construct the circuit; and vice versa. In future work, this should be made more precise. In the case of Boolean circuits, logtime-uniforiity (Ug.-unifon) -un-uorforimyt has become the standard requirement [Vollmer 1999]. What is the corresponding precise uniformity notion for GNNs?
In the introduction we mentioned the complexity of the problem of training neural networks. We studied the expressiveness (or computational power) of neural networks. The higher the expressive- ness of network is, the more complicated the training process will be; however, the question to decide if a trained network of given quality exists might become easier to decide. Can this be made precise? Is there a formal result connecting complexity of training and network expressiveness?
Further investigations are required to obtain practical implications of our theoretical results. Once we fix the architecture of our C-GNNs (i.e., a circuit function class for the GNN nodes), we obtain specific circuit class that characterizes the computational power of the C-GNN model which can be then rigorously studied. The question of what can be computed by arithmetic circuits using activation functions is related to the question of which functions can be computed using other functions, or in other words, which functions are "more complex" than others. We are only aware of very little work in this area. Results include PTIME upper bound (in the so-called BSS-model of computation) for the arithmetic circuit complexity class NCR that uses the sign function CmnctionCuucker (1992].
As it currently stands, there does not seem to be meaningful experiments that could be run for our model of computation. The problem that not much is known about the computational power of the circuit classes we utilize. Further research into functions computable by practically implementable arithmetic circuits of different sizes and depths would be required. This could e.g. be done by investigating the Boolean parts of different complexity classes defined by families of arithmetic circuits, i.e., the classes when restricted Boolean inputs. This research would pinpoint properties that would be provably outside of the capabilities of particular GNN models, whose learnability could be then tested in practice. We helieve that our results will motivate research for these circuit classes.
Merrill et al. 2022], Merrill and Sabharwal 2022] have studied transformer networks from a computational complexity perspective and obtained TC upper bound, similar to the result for GNNs by Grohe [2023]. We think it is worthwhile to study the computational power of transformers from the point of view of computation over the reals, similar what have done in this paper for
GNNs.
For readability purposes the mieddimeniooal vectors in the C- C-GNN are written real numbers.
10

---

Acknowledgements
The first and the fourth author were partially supported by the DFG grant VI 1045-1/1.
References
J. L. Reutter, and J. P. Silva. The Logi- cal Expressiveness of Graph Neural Networks. In 8th International Conference Learn- ing Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020. URL
Barceló, V. Kostylev, M. Monet, J. Pérez,
Barlag, V. Holzapfel, L. Strieker, J. Virtema, and H. Vollmer. Graph neural networks and arithmetic circuits. CoRR, abs/2402.17800 17805, 2024. doi: 008550/ARXII.2402.11000 URL
https:///oi.ox/ mereiiiorg//o.. www.4//0//....422......
M. Benedikt, C. Lu, B. Motik, and T. Tan. Decidability of graph neural networks via logical characterizations. In K. Bringmann, M. Grohe, G. Puppis, and O. Svensson, editors, 51st International Colloquium
Automata, Languages, and Programming. ICALP 2024, July 8- 12. 2024, Tallimn, Estonia, volume 297 LIPlcs, pages 127:1-127:20, Schloss Dagstuhl Leibniz-7entruum für Informatik, 2024. doi: 10.4230/LIPICS.IIC 202.P............2....,. URL https 1ttool.rg//1.420/LLTII 1CA.c.2............2222.22
L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer- Springer-Verlag. Berlin, Heidelberg, 1997. ISBN 0387982817.
D. Т. Cucala, B. C. Grau, B. Motik, and E. V. Kostylev. On the correspondence between monotonic max-sum gnns and datalog. In P. Marquis, T. Son, and G. Kern- Isbemmr,r,e,, editors, Proceedings of the 20th International Conference
Principles of Knowledge Representation and Reasoning. KR 2023, Rhodes, Greece, September 2-8, 2023, pages 658-667, 2023. doi: 10. 10.24966//KR.2223/66. URL https::///o....o 11. kr 2ttp:////.2022////2
Cucker. PR * NCR. Complexity, 8(3):230-235; 1992. URL https:://ao..orr/100.000 0885-064X (92) 9002446
Geerts, J. Steegmans, and J. Van den Bussche. On the Expressive Power Message-Passing Neural Networks Global Feature Map Transformers. In I. Varzinezak, editor, Foundations of Information and Knowledge Systems 12th International Symposium, FolKS 2022, Helsinki, Finland, June 20-23, 2022, Proceedings, volume 13388 of Lecture Notes in Computer Science, pages 20-34, Springer, 2022. doi: 10. 1007/9977 00007/978-3-01111 11321-5), URL 10.1007/978- 3- 031- 11321-5.2.
Gilmer, S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In International conference machine learning, pages 1263-1272. PMLR, 2017.
M. Grohe. The Descriptive Complexity of Graph Neural Networks. In LICS, pages 1- 14, 2023. doi: 10. 10.1109//ICSS3633..2222 200.C05666662222211775555 202. 10175533. URL https:://oo.orr/10.111
TL1S56666.2023.10111
He and A. Papakonstantinou. Deep Neural Networks: The Missing Complexity Parameter. Elec- Iron. Colloquium Comput. Complex., TR22-159, 2022. httttp:://ecccc..iizzmaaa report/2022/155
L. Hella, M. Järvisalo, A. Kuusisto, J. Laurinharju, T. Lempiäinen, K. Luosto, J. Suomela, and Virtema. Weak models of distributed computing, with connections to modal logic. Distributed Comput., 28(1):31-53, 2015. doi: 10. 10.1007/500444--013-0000 10.1007/60046--13-00222
URL https://doi.ons
W. Maass. Bounds for the Computational Power and Learning Complexity of Analog Neural Nets. SIAM Comput, 26(3):708 732, 1997. doi: 10. 10.133777700777777955544 URL httpss

---

W. Maass, G. Schnitger, and E. D. Sontag, On the Computational Power of Sigmoid versus Boolean Threshold Circuits. In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 767-776. IEEE Computer Society, 1991. doi:
N..109/SFCS.19911.0
W. Merrill. Transformers are Uniform Constant-Depth Threshold Circuits.
https://
www. http:o/ttbee.cc//aaaaaaaa///aaa.
2022.
W. Merrill and A. Sabharwal. Log-Precisson Transformers Constant-Depth Uniform Threshold Circuits. CoRR, abs/2207.00722) 2022. doi: D..S00AARXIV.2227.00772 URL https
W. Merrill, A. Sabharwal, and N. A. Smith. Saturated Transformers are Constant-Depth Threshold Circuits. Trans. Assoc. Comput. Linguistics, 3465
856, 2022. BRL.htttss//transccl.or
C. Morris, M. Ritzent, M. Fey, W. Hamilton, J. E. Lenssen, Rattan, and M. Grohe. Weis- feiler and Leman Go Neural: Higher-Order Graph Neural Networks. In The Thirty- AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium Educational Ad- vances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 February URL
1, 2019, pages 4602 4609, AAAI Press, 2019. doi: 10. httts:://di..orgg 10.10//9111111//0/ 2ttp:///aaa..1111111333131111110
C. Morris, M. Fey, and N. M. Kriege. The Power of the Weisteiler-Leman Algorithm for Machine Learning with Graphs In Z. Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Viriual Event / Monireal, Canada, 19-27 August 2021, pages 4543 4550. ijcai.org, 2021. doi: 10.24966/IICAA1222116616 URL https 7/doi. 10. 2ww.2/42933....... 2021//66
M. Pfluger, D. T. Cucala, and E. V. Kostylev. Recurrent graph neural networks and their connections to bisimulation and logic. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 14608-14616, 2024.
E. Rosenbluth, J. Tönshoff, and M. Grohe. Some might say all you need is sum. CoRR, abs/2302. 1103, 2023. doi: 10.48550/ARXIV 2302.11603. URL CtLhhttps:/// http:///oooorg//.1333//
R. Sato, M. Yamada, and H. Kashima. Approximation ratios of graph neural networks for combinato- rial problems. In H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-BBuc, E. B. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 4083 4092. 2019. URL http:////ppppooddggnooroo....ppp hash/ 0454444000ffffffff111444eeed121. attp://///d..--asttattt....aaaa Abstract.htm
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Trans. Neural Networks, 20(1):61 2009. doi: 10. (009/TNN.2000.0000
URL
H. T. Siegelmann and E. D. Sontag. On the Computational Power of Neural Nets. J. Comput. Syst. Sci., 131-:10::151,,,,, 1995. doi: 10. 00.0000/CSS..195..0001 URL Jcss.1995.1013
H. Vollmer. Introduction Circuit Complexity A Uniform Approchh. Texts in Theoretical Computer Science, An EATCS Series. Springer, 1999. ISBN 978-3-540-64310-4, doi: 10. 1007/79778---- 03927-4. URL htl.apppp///o...rr///00000/////3
K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How Powerful are Graph Neural Networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL URL http::///ppprrrrr....eettoor////
12

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: In the abstract and introduction, we introduce the setting of our paper, describe our main results on characterizations of GNNs in terms of arithmetic circuits and their possible implications, e.g., concerning limitations of the computational power of GNNs. In the main part of the paper, together with the appendíx, we give rigorous proofs for all of our claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The theoretical limitations for results were discussed and mentioned before the respective proof'. Experimental limitations do not apply to this theoretical paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
13

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
For each theoretical result the full set of assumptions is given by the definitions
in the preliminaries section as well as the formulation the theorems itself. Proof sketches are supplied, the full proofs can be found in the supplementary materials of the full arxiv version of the paper [Barlag et al. [024].
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
14

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc/
mublic/guides. httia//guuuees//odeeubisssssssss
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurlPS code and data submission guidelines (https http///eeummmmmsiiiieeeeeeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
15

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httppp///eaurrsscccpaaaal//tttte
Answer: [Yes]
Justification: We carefully inspected the NeurlPS Code of Ethics, and as a purely theoretical paper its requirements do not apply. In general, research conforms with general research ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The results of the paper are theoretical and give provable bounds for the expressivity of neural network computation. The results do not have direct societal impact.
Guidelines:
16

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
17

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwprssstspsssssccdeeee.. wwt.coo///aaat datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
[NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
18

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
19


Reviews:
[{"review_id": "lUOIqKC8Ik", "reviewer": "Reviewer_3Xib", "summary": "This paper provides a new lens through which the expressive power of GNNs is analyzed via arithmetic circuits and derives expressiveness limits for general GNNs.", "questions": "- Is there any numerical experiments you can run to demonstrate your theoretical findings?", "limitations": "The limitations have been sufficiently addressed in the paper.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- this paper is indeed modular, well-written, and cleanly organized\n- it introduces an interesting perspective for analyzing GNN expressiveness", "weaknesses": "- I think this paper would benefit from more detailed discussion on the relationship with WL tests.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**I think this paper would benefit from more detailed discussion on the relationship with WL tests.**\nThe Weisfeiler Lehman tests (and its variants) usually refer to the problem of graph isomorphism, and give insight to the question whether two graphs can be distinguished by some GNN model. Since we are concerned with comparing the classes of functions over the reals that can be computed (using distributed computation/message passing in the case of C-GNNs and AC-GNNs), the WL test does not precisely relate to our main focus. We of course mention WL tests as a well understood technique to compare GNN expressivity.\n\n**Is there any numerical experiments you can run to demonstrate your theoretical findings?**\nAs it currently stands, there does not seem to be any meaningful experiments that could be run for this model of computation. Essentially, the problem is that not much is known about the computational power of the circuit classes we utilize. Further research into functions computable by practically implementable arithmetic circuits of different sizes and depths would be required. \nThis could e.g. be done by investigating the Boolean parts of different complexity classes defined by families of arithmetic circuits, i.e., the classes when restricted to Boolean inputs. This research would pinpoint properties that would be provably outside of the capabilities of particular GNN models, whose learnability could be then tested in practice. We believe that our results will motivate research for these circuit classes.", "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": "GeRxu5qd7Q", "reviewer": "Reviewer_E5Mq", "summary": "In this article, the authors present new contributions on the understanding on the computational framework provided by GNNs.\nIn particular, they draw a connection between Arithmetic Circuits and GNNs. \n\nBased on a new definition of GNN using arithmetic circuits, they show that the function computed by a GNN on each node can be thought of a function that an (tail-symmetric) arithmetic circuit computes, by stacking the adjacency matrix of the graph and the features vector. In other words, by using arithmetic circuits as comb and aggregation functions inside a message passing framework, the overall procedure can still be thought of as an arithmetic circuit (and vice-versa).", "questions": "- The authors emphasize (and I think it is a good thing) that the computational equivalence they obtain with Arithmetic circuits is something that applies to the message passing framework (the essence of GNNs), regardless of the computational power on the nodes. But in their work, the authors provide an arithmetic circuit as computational power to the nodes. In other words, do the authors believe there is an arithmetic circuit that cannot be computed by an AC-GNN?\n\n- The authors define standard notations like $[n]$, notation for multisets, but not for $(\\mathbb{R}^{k})^{*}$. This probably refers to all possible n-tuples of $R^{k}$ for every n. However, it becomes confusing at several locations in the paper.\n\n- From the abstract, the authors mention that their result hold uniformly and non uniformly. This is not mentioned again nor explained in the paper (uniform vs. non uniform) (except if I missed it?)\n\n- The definition of an AC-GNN, as an C-GNN does not coincide with the standard one: a function \\sigma^{i} is applied after the combination. This does not align for instance with [2020, Barcelo & Al.]. \n\n- Definition 3.3, is unclear: The authors may want to elaborate why the proj_1 and proj_2 operations are made consecutively, why is proj_2 needed for $\\sigma^{(i)}$ ? I suppose that this is in order to have access to two different arithmetic consecutively.\n \n\n- The authors may want to consider in their introduction, in order to compare their result (in particular the independence w.r.t. the activation functions) the references:\n\n- Impact of aggregation function: \t\tEran Rosenbluth, Jan Tönshoff, Martin Grohe ``Some might say all you need is sum``\nMartin Grohe, Eran Rosenbluth               ``Are Targeted Messages More Effective?``\n\n- Impact of activation function on GNN expressivity: Sammy Khalife ``Graph Neural Networks with polynomial activations cannot express all GC2 queries``\n\t\t\t\t\t\t    \n- Sammy Khalife, Amitabh Basu\t``On the power of graph neural networks and the role of the activation function.``\n\n\n- In proof of Theorem 3.11 is used Definition A.7, and mentioned (``via the injective function'', but this definition allows several functions (as long as different depth implies different values taken by the function). Can the authors confirm and/or clarify this?\n\n- I had a look at the proof of Theorem 3.11 in details (I find this result the most interesting). Can the authors confirm: the essence of the proof is to group the input of the initial circuits (vector of reals) and the circuit as a new graph input to the C-GNN? The gates and structure of the initial circuit is then processed by the C-GNN, in order to compensate for the excess (addition and multiplication shown in Algorithm 1). The division performed in Algorithm 1 is allowed as it is the same as multiplying by the inverse of a constant (this number is indeed a constant as it relates to the structure of the circuit, not the input).", "limitations": "The authors are transparent in the conclusion of their work about the limitations of their work.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The paper reads well, in particular the introduction about related work is useful. (although the authors may want to include some additional references for completeness, as detailed below in the Questions section).\n\n- The authors propose a new way to think about GNNs, as a correspondence between a given iteration number, and two family circuits (which used to be the COMB and AGG functions).\n\n- I find the several contributions interesting.", "weaknesses": "- The main weakness that I can see, is that the definition of the C-GNNs makes the connection between AC-GNN (or close variants, which is what is implemented and used in practice) and circuits. Since the correspondence between GNNs and tail-symmetric arithmetic circuit is established in the following sense:\n\n$$ \\text{AC-GNN} \\subsetneq (\\text{ C-GNNs} = FAC^{0}_{\\mathbb{R}^{k}}[\\mathcal{A}] )$$\n\nThere is potentially a huge gap between AC-GNNs and C-GNNs, that is partially discussed in Remark 3.4. The obscure part of this correspondance seems to arise mainly because of the aggregation functions: i.e., if we have the sum, max and product as aggregation functions, what part of the C-GNNs can we simulate (with polynomial reductions)? \n\n- Also, although I personally find the results interesting, they are not very deep or insightful: if one provide arithmetic circuit power on each node, and arithmetic circuit power as aggregation, then we obtain at most arithmetic circuits.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Regarding the mentioned weaknesses:\nThe nature of the relationship between AC-GNNs and C-GNNs lies in the definitions. In Remark 3.4 we assume the aggregation functions to be computable by $\\text{FAC}^0_{R^k}$-circuit families, which the max function is not. So to be able to express an AC-GNN that uses max as the aggregation function, a different class of C-GNNs would be needed. The other way around (AC-CNNs simulating C-GNNs) this would boil down to the question which kind of circuit class the circuits used in the C-GNN are part of. For $\\text{FAC}^0_{R^k}$ (note: no extra gates) we would intuitively say the AC-GNNs could simulate C-GNNs where every circuit has a restricted depth as the sum or product over n different inputs only takes one gate to compute in a $\\text{FAC}^0_{R^k}$ circuit, assuming the circuits are minimal.\n\nWhile the results may not seem too surprising at first glance, the proofs still involve a lot of technicalities, some mainly attributed to the use of real numbers and functions over those, while others arise from the fact that this essentially shows that message passing does not increase power in this kind of setting. \n\n## Regarding the questions:\n1. In their standard definition, arithmetic circuits have access to addition and multiplication gates.\nHowever, functions which make use of arbitrary multiplication in a meaningful way cannot in general be computed by AC-GNNs of classical definition with constant depth, i.e., with sum as its aggregation and a weighted sum as its combine function.\nIf we were to use different aggregation and/or combine functions in the AC-GNN, depending on the chosen functions, we might very well be able to simulate arithmetic circuits using AC-GNNs as well.\n2. You are correct, we will address this in the revised version.\n3. From the constructive nature of our proofs, it follows that we will have some notion of uniformity. Defining that notion precisely and proving a formal statement will still require some work.\n4. Apart from (not) fixing the combination function, our definition aligns with the one mentioned, as $\\sigma^{(i)}$ corresponds to the function f that is part of the combination in Barceló et al. We changed the notation here because we refer to this function very frequently as the activation function and therefore wanted it to be written out separately from the combination function.\n5. In our current definition, $\\mathcal{N}(i)$ is a function pointing to a CGNN basis for every layer, which in turn is a tuple $(\\mathcal{S}, \\mathcal{A})$ containing a set of functions computed by a circuit family $\\mathcal{S}$ and a set of activation functions $\\mathcal{A}$.\nWe needed the projections to refer to the individual functions $\\mathcal{C}^{(i)}$ and $\\sigma^{(i)}$ for layer $i$. We will improve the somewhat poor presentation of this.\n6. Thank you, we will look into these.\n7. This is indeed a misleading formulation. Any numbering satisfying the condition of Definition A.7 would suffice, we will clarify this.\n8. Yes, this is indeed the essence of the proof. The details certainly require a bit of technical work, but this portrays the general idea well.", "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": "bMUaTgeENF", "reviewer": "Reviewer_FVmx", "summary": "The paper investigates the computational power of GNNs by demonstrating that the expressiveness of GNNs with different activation functions is equivalent to the capabilities of arithmetic circuits over real numbers. The authors introduce a new GNN variant called C-GNNs, which are equipped with constant-depth arithmetic circuits, and prove that these can compute the same functions as constant-depth arithmetic circuits. This result holds uniformly for all common activation functions and provides insights into the inherent computational limitations of GNNs, suggesting that enhancing GNN expressivity requires more complex functions or different architectures beyond mere scaling.", "questions": "1. In Line 115-116, you mention that the results are \"not only an upper bound for neural networks.\" However, existing studies often establish the *equivalence* between GNNs and classic algorithms, implying both upper and lower bounds. Moreover, the exact correspondence seems to be established only for C-GNNs and not AC-GNNs. Could you clarify this distinction?\n\n2. You state that the \"result holds for all commonly used activation functions.\" Yet, the results appear to hinge solely on the injectivity of the activation function, without more detailed results. Since commonly adopted activation functions are injective, it's challenging to discern the expressiveness of these functions. Could you provide more nuanced insights into this matter?\n\n3. The paper does not discuss applications to deep learning, which may limit its appeal to the NeurIPS audience. \n- Could you elaborate on potential practical problems that the FAC-circuit family can solve or not solve? \n- Additionally, how do FAC-circuits relate to traditional GNN expressiveness results, such as the WL test and first-order logic? Can these classic algorithms be simulated by FAC-circuits?\n\n4. An important related work is missed [1]. This study discusses the equivalence between GNNs and a family of distributed algorithms, as well as the impact on aggregation functions. Furthermore, VVc-GNN appears similar to the C-GNN proposed in your paper. A discussion on this would be beneficial.\n\n[1] Sato, Ryoma, Makoto Yamada, and Hisashi Kashima. \"Approximation ratios of graph neural networks for combinatorial problems.\" NeurIPS 2019.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper offers a novel perspective on the expressiveness of GNNs, which is a valuable addition to the existing body of research on GNN expressiveness. This could potentially inspire future work in GNN design.", "weaknesses": "1. The paper's presentation may not align well with the expectations of a NeurIPS audience. Even for readers with a background in TCS and combinatorics, the contributions of the paper could be made more apparent. An improved presentation could potentially result in a higher evaluation score. (Questions 1, 2, 3)\n\n2. The paper would benefit from a more thorough discussion and comparison with existing literature within the main body of the text. This would help to contextualize the paper's contributions within the broader field. (Questions 3, 4)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Regarding the mentioned weaknesses:**\nThank you for pointing out these issues, we will definitely keep these in mind when revising the paper. We strife to appeal to the general NeurIPS audience, and for this purpose focussed also to presenting a thorough general introduction to the paper. This is though a bit of a balancing act given the theoretic nature of the result.\n\n**Regarding the questions:**\n1. That is certainly correct. Our intention was not to imply that there aren't other precise characterisation results, instead our intent was to emphasize that our results produces a matching lower and upper bound. Furthermore, the direct correspondence we establish is indeed only achieved for C-GNNs. For AC-GNNs, we merely show an upper bound.\n2. We wanted to emphasize that our results cover all commonly used activation functions. The proof technique does rely only on the injectivity of the activation function, and therefore holds for many more functions than just the ones mentioned. The main take away from this should be that if an activation function satisfies a very easy requirement (injectivity), then we get a correspondence between circuits and C-GNNs that have access to the same activation functions.\n3. Questions about what different FAC-families can and cannot compute in practice still require further research. We believe that this work produces an application motivating the research on this topic for people working in circuit complexity. Since we are only concerned with real-valued computations, connections to classical FO do at least not seem obvious. Connections to FO over metafinite R-structures, however, seem plausible, and are worth investigating, since there is a close connection between real valued circuits and FO over R-structures.\n4. Thank you, this is indeed an important paper as it is a precursor for the logical characterisations of Barcelo et al. (ICLR 2020) and Grohe (LICS 2023). We do not think that VVc-GNNs are directly related to our C-GNNs; in our work the aggregation-combine operations are computed by a circuit from some circuit class that delineates the complexity of the aggregation-combine method. In VVc-GNNs the focus is on the format of the message passing, and does not limit complexity of the aggregation-combine method. However, it is an interesting topic of future work to study whether by relating our C-GNNs to variants of VVc-GNNs we may drop the assumption of tail-symmetry. Finally, if the results of Sato et al. are combined with logical characterisations of  \n\"Hella, Jarvisalo, Kuusisto, Laurinharju, Lempiainen, Luosto, Suomela, Virtema. Weak models of distributed computing, with connections to modal logic. PODC 2012\"  \nthe model of distributed computing that the paper by Sato et al. take inspiration from, one obtains a weaker form of the logical characterisation later proved directly to GNNs by Barcelo. We will add a comment about this to the paper.", "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": "TlJQKqxaYn", "reviewer": "Reviewer_2Yjw", "summary": "The paper establishes a series of expressiveness/expressive efficiency equivalence between graph neural networks (GNNs) whose aggregation/combine operations can be computed by arithmetic circuits, and various sub-classes of constant-depth arithmetic circuits. The main challenge consists of showing expressiveness equivalences in the case of the GNN or the aggregation/combine operations being equipped with some non-linearities. In principle, one could then leverage these expressive equivalence results to show limitations of what GNNs can compute through the language of arithmetic circuits.", "questions": "I list my questions below:\n1. It seems the paper does not show a theoretical application of the expressive equivalences shown. Do the authors have some insight about which kind of limitations of GNNs can be shown through the language of arithmetic circuits? The arithmetic circuits equipped with non-linear gates appears quite powerful. Are there already some works on showing limitations of what they can compute?\n2. The authors introduce the concept of arithmetic circuits computing tail-symmetric functions. What would be a systematic way to build tail-symmetric circuits in practice?\n3. The proof of Lemma 3.9 shows how to decompose an arithmetic circuit whose maximum out-degree of nodes is > 1 into another one whose out-degree of nodes is instead 1. Do the authors agree that the space complexity of such decomposition is polynomial in the size of the original circuit only because we are considering constant-depth circuits? If the circuits were not constant-depth, then the complexity of the decomposition would be exponential w.r.t. the depth, right? If this is true, then the authors should make this more clear in the proof.\n4. It is not clear to me at which point of the proof of Theorem 3.17 we need the activation functions to be countably injective. Would it be fine if they were simply bijective? Can you please explain why do we need this constraint?\n5. The authors mention multiple times that their results are \"uniform\", but it seems it is not properly defined anywhere. What is a formal definition of \"uniformity\" in general? Why is it important?", "limitations": "The only limitation I can think of is related to the theoretical results is that in many cases they require using arithmetic circuits equipped with non-linear gates, for which showing limitations in what they can compute sounds quite hard. See my question 1 above for details.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "I believe the paper brings a substantial theoretical contribution to the problem of understanding the expressiveness of GNNs, since it proposes using a special class of arithmetic circuits to express the computations of GNNs (and vice versa). By doing so, any limitation shown over this class of arithmetic circuits can be translated to GNNs as well.\n\nThe proofs of the theorems are briefly discussed in the main text, and then they are fully presented in the appendix. I believe the proofs in the main text do quite a good job in giving an outline about the full proof. Most of the notation and terminology is very well-explained formally, even though in just a few cases they are not (see weaknesses).", "weaknesses": "While I do not have a background about showing expressiveness results of GNNs, I have some background in doing so for arithmetic circuits. The great flexibility of arithmetic circuits when equipped with non-linearities (as the ones showed in the paper) suggests it might be very difficult showing their limitations, and therefore limitations for the GNNs in this way. Therefore, I think the class of arithmetic circuits considered might limit the impact of the contribution to being important but not exceptional. I am happy to reconsider my score if proved otherwise (see also my questions).\n\nI think there are some weaknesses regarding the presentation at multiple points in the paper (hence the 2/4 score), which I list below:\n- The introduction is too long (~3 pages) and I was often confused about which content in it was actually relevant for the paper. For example, the first paragraph (L9-16) is not relevant, as also mentioned in L17. Also, L26-50 discuss relationships with fragments of first-order logics in the literature, but this sounds far from the actual contributions of the paper. I have noticed there is no related work section in the paper. I would suggest moving some content of the introduction to a related work section just before the conclusion, if it is really something related to the paper. This would make the contributions appear sooner.\n- The contributions of the paper are listed at multiple points of the introduction, and some concepts are often repeated. For instance, L68-72, L106-109, L114-116 look all similar sentences. I think it is sufficient to list the contribution and motivate them (e.g., L129-134) only once.\n- The authors should check if all concepts are explained in the introduction before using them, such as \"existential theory of real numbers\" and the class $\\mathrm{FAC}_R^0$ (L86).\n- I was quite confused about the meaning of L253, since projection is used also as a gate in the arithmetic circuit. Here it is instead using to extract one element of the pair returned by the circuit GNN. Also, I was expecting $\\sigma^{(i)}$ to be a non-linearity (e.g., ReLU), but it is instead the projection here. I think L252-L254 can be rephrased as to make the notation more clear.\n- L202 uses the star symbol. I suppose this is the Kleene star operator, but it seems to not be defined.\n- Definition 3.15 contains an upward half arrow labelled with $S$. What is the semantic of this symbol? Is this defined somewhere? If not, it is better to define it.\n- Since there is a high number of definitions appearing way before the theorems using them, I was wondering if you could remove some definitions. For example, do you need $\\mathrm{FSIZE-DEPTH}_{\\mathbb{R}^k}(s,d)[\\mathcal{A}]$  as a concept in other parts of the paper? Isn't it sufficient to just introduce Definition 2.7 without using it? It looks like the paper only deals with constant-depth circuits anyway.\n\nI strongly recommend all these issues to be eventually fixed in the camera ready of the paper, which should require modest effort.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Weaknesses\n\n1\\., 2\\. & 3\\. We will carefully revise our introduction to eliminate repetition and to ensure that all concepts are sufficiently treated. Currently our introduction starts with a subsection \"Background and Related Work\", we will split this section into two parts and collect relevant related work discussion to a separate \"Related Work\" subsection to the end of the introduction. We strongly believe that our work should be put into its context in the introduction by discussing related work there in a sufficient manner.\n\n4\\. & 5\\. Thanks for pointing this out. The star is indeed the Kleene star and the upward half arrow defines the restriction of a function. We will address this in the paper.\n\n6\\. We agree that there is high number of definitions, but our aim is to have a general framework to be able to reason about the complexity of GNNs. We therefore defined the C-GNNs to be as general as possible not just restricting ourselves to a version with only circuits of constant depth.\n## Questions \n1. Once we fix the circuit and the activation function we get the connection to the specific circuit class this circuit belongs to and are able to study it. Concerning the limits of what can be computed by arithmetic circuits using activation functions, we would like to mention that this is related to the question of which functions can be computed using other functions, or in other words, which functions are \"more complex\" than others. We are only aware of very little work in this area. Results include  an upper bound for arithmetic circuit complexity classes with the addition of the sign function shown by Cucker (Felipe Cucker. PR != NCR . J. Complexity, 8(3):230–238, 1992]). \n2. We are not entirely sure if we understand this question correctly. Are you asking if there exists a syntactic characterization of the notion of tail-symmetry, since this notion is purely semantical? If so, this is indeed a very good question that would be interesting to look into in the future.\n3. This is indeed true, thanks for pointing this out, we will make this more clear in our proof.\n4. We need the countable injectivity in activation functions for simulating circuits by using C-GNNs, since we encode the gate numbers of the circuit we are trying to simulate in the preimage of our activation functions. This way, we retrieve the gate number whenever we apply the activation function at the end of the computation of a node in our C-GNN. In general since countable injectivitiy is the weaker requirement bijectivity would also suffice.\n5. Any fixed arithmetic circuit has a fixed number of inputs. This means that any circuit can only work on inputs of a fixed length. This is why we defined families of such circuits for our results. Computational models with this property, i.e., where essentially a \"different machine\" is needed for every input length are generally called non-uniform. If one can by computational means obtain the circuits of a given family, this family is then called uniform, as there exists an algorithm to compute on every input length. In Boolean complexity theory, oftentimes a Turing machine outputting the nth circuit on input n is used as a witness of a circuit family's uniformity. \nUniformity is important, as it provides us with an algorithm that can work on inputs of arbitrary length, whereas the existence of e.g. a nonuniform circuit family that computes a particular function cannot really be seen as an implementable algorithm. \nFrom the constructive nature of our proofs, it follows that we will have some notion of uniformity, since they essentially define an algorithm to obtain the nth circuit or C-GNN. Defining that notion precisely will still require some work.", "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:

Meta-review: All reviewers agreed that this paper provides an important theoretical contribution by connecting arithmetic circuits and GNNs in a novel way. All major concerns could be resolved during the rebuttal. Therefore, I recommend acceptance of the paper as a poster.
Decision: Accept (poster)