Graph Neural Networks and Arithmetic Circuits

Authors: timon  barlag
vivian  holzapfel
laura  strieker
jonni  virtema
heribert  vollmer
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 11:15:00

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.

Main paper: 
 introduction: 
 Neural networks have recently received growing attention from a theoretical point of view in a number of papers studying their computational properties. Relevant to this paper are examinations of the computational power of neural networks after training, i.e., the training process is not taken into account but instead the computational power of an optimally trained network is studied. Starting already in the nineties, the expressive power of feed-forward neural networks (FNNs) has been related to Boolean threshold circuits, see, e.g., [Maass et al., 1991 , Siegelmann and Sontag, 1995 , Maass, 1997 , He and Papakonstantinou, 2022] . Most importantly, Maass [1997] showed that when restricting networks to Boolean inputs, a language can be decided by a family of (in a certain sense) "polynomial-size" FNNs if and only if it belongs to the class TC 0 , 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 to the study of graph neural networks (GNNs) which is a model for machine learning tasks on graph-structured inputs. 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. [2020] consider 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 a certain fragment GC (guarded first-order logic with counting quantifiers) are computable by GNNs. The converse direction is a bit problematic; it 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 an extension of GNNs by so-called global readout and show that these GNNs can compute all queries from the logic FOC 2 (first-order restricted to two variables, but extended with counting quantifiers, a 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-hence 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, we consider GNNs as a model to compute functions from (vectors of) real numbers to (vectors of) real numbers, or from labeled graphs (i.e., undirected graphs whose nodes are annotated with vectors of real numbers) to labeled graphs.Instead of turning to logics, 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 an upper bound, or correspondence with respect to discrete classification tasks, but an equivalence between GNNs and constant-depth arithmetic circuits over the real functions they compute. In this way, we shed more light on 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 FAC 0 R , 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 a broad line of research outlined by Merrill [2022] , in this paper, we aim at a general statement about the computational power of neural networks following the GNN architecture, i.e., networks operating in layers where connections within layers and hence their communication capabilities 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 combine step (combining the aggregated information with the current information of the node-mostly a linear function followed by a unary non-linear activation function such as sigmoid or 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 et 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 aggregate-combine (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 a C-GNN with a 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 a GNN to compute a 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 a 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 0 R will lead to 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-GNNs as a generalization 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. [2009] . Since then, their expressive power has been studied in numerous works and from various perspectives as discussed above. As mentioned already, Barceló et al. [2020] established a close connection between classifiers definable in guarded FOC 2 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 et al. [2019] , 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 FOC 2 ). Grohe [2023] 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 a approximable by Boolean circuits or logic). This includes most of the commonly used activation functions. Since queries expressible in this logic are known to be TC 0 computable, he obtains a TC 0 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 TC 0 circuit is computable by a 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 a 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., 2024] .To the best of our knowledge, there are no other works considering real-valued 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.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? 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 appendix, 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 in 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
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 |x| to denote the length of x (i.e., the number of elements of x), and use [n] to denote the first n nonzero natural numbers {1, . . . , n}. For a k ∈ N we denote all possible n-tuples for every n of R k with R k * . The notation { {} } is used for multisets. A restriction of a function f to set S is written as f↾ S . Definition 2.1. Let k ∈ N, and let G = (V, E) be a graph with an ordered set of vertices V and a set of undirected edges E on V . Let g V : V → R k be a function which labels the vertices with attribute vectors. We then call G = (V, E, g V ) a labeled graph of dimension k and denote by Graph the set of all labeled graphs and by Graph k the set of all labeled graphs of dimension k.For a node v ∈ V , the neighborhood of v is defined as N G (v) := {w ∈ V | {v, w} ∈ 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 as 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.: R k ×• • •×R k → R k , a combine function (of dimension k) is a function COM : R k × R k → R k and a classification function (of dimension k) is a function CLS : R k → {0, 1}that classifies a real vector as either true or false. Finally, an activation function (of dimension k) is a componentwise function σ : R k → R k . Definition 2.2 (AC-GNN, cf. [Barceló et al., 2020] ). An L layer aggregate combine graph neural network(AC-GNN) is a tuple D = ({AGG (i) } L i=1 , {COM (i) } L i=1 , {σ (i) } L i=1 , CLS), where {AGG (i) } L i=1 and {COM (i) } L i=1 are sequences of aggregation and combine functions,{σ (i) } L i=1is a sequence of activation functions and CLS is a classification function.Given a labeled graph G = (V, E, g V ), the AC-GNN model computes vectorsx (i) v for every v ∈ V in every layer 1 ≤ i ≤ L as follows: x (0) v = g V (v) is the initial feature vector of v, and for i > 1x (i) v = σ (i) COM (i) x (i-1) v , y , where y = AGG (i) x (i-1) u | u ∈ N G (v) .The classification function CLS: R k → {0, 1} is applied to the resulting feature vectorsx (L) v .In this paper we focus on the real-valued computation part of GNNs and discard the classification function. We consider the feature vectors x(L) vafter the computation of layer L as our output. While we could also integrate CLS into our model, for our concerns this is not needed.Next we define arithmetic circuits as a 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 k rather than relative to R, as is done more commonly (cf. e.g. [Blum et al., 1997] ). Definition 2.3. Let k, n, m ∈ N. An R k -arithmetic circuit with n inputs and m outputs is a simple directed acyclic graph of labeled nodes, also called gates, such that • there are exactly n gates labeled input, which each have indegree 0, • there are exactly m gates labeled output, which have indegree 1 and outdegree 0, • there are gates labeled constant, which have indegree 0 and are labeled with a tuple c ∈ R k , • there are gates labeled projection i,j for 1 ≤ i, j ≤ 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 k -arithmetic circuit C with n inputs and m outputs computes the functionf C : (R k ) n → (R k ) mas 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 as inputs. By addition and multiplication we refer to the respective componentwise operations and the projection computes the function proj i,j : R k → R k , (x 1 , . . . , x i , . . . x k ) → (0, . . . , 0, x i position j , 0, . . . , 0). Analogously, each output gate takes the value of its predecessor, once its predecessor has one. The output of f C is then the tuple of values in the m output gates of C after the computation.The depth of C (written depth(C)) is the length of the longest path from an input gate to an output gate in C and the size of C (written size(C)) is the number of gates in C. For a gate g in C, we will write depth(g) to denote the length of the longest path from an input gate to g in C.Remark 2.4. In the context of the circuits over R k that we have just defined, a circuit over R is just a circuit over R 1 . Note that for circuits over R 1 , 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 k 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 a function with a fixed number of arguments, we extend this definition to families of arithmetic circuits in a natural way. Definition 2.5. An R k -arithmetic circuit family C is a sequence (C n ) n∈N of circuits, where each circuit C n has exactly n input gates. Its depth and size are functions mapping natural numbers n to depth(C n ) and size(C n ), respectively.C = (C n ) n∈N computes the function f C : (R k ) * → (R k ) * defined as f C (x) := f C |x| (x).Remark 2.6. Since a circuit family is an infinite sequence of circuits, one would be hard pressed to consider such a family a (finite) algorithm. Such models of computation, where a different instance is needed for any different input length, is called non-uniform. In order to deem a circuit family (C n ) n∈N to be an algorithm, a frequent requirement is the existence of an algorithm which, when given n as an input, outputs the circuit C n . Circuit families, for which such an algorithm exists are called uniform circuit families. For more details on circuit uniformity, see e.g. Vollmer [1999] and for more on uniformity with respect to real computation, see Blum et al. [1997] . Definition 2.7. For any k ∈ N and any two functions s, d :N → N, FSIZE-DEPTH R k (s, d) is the class of all functions (R k ) * → (R k ) * that are computable by arithmetic circuit families of size in O(s) and depth in O(d). Let A be a set of functions of the form f : R k → R k . Then FSIZE-DEPTH R k (s, d)[A]is the class of functions computable by arithmetic circuits with the same constraints, but with additional gate types g f , with indegree and outdegree 1 that compute f , for each f ∈ A.We call all classes of the form FSIZE-DEPTH R k (s, d)[A] (and their subclasses) circuit function classes. As usual in circuit complexity, an F-circuit family, where F is a class of functions, will denote a circuit family that computes a function in F.We restrict this work to versions of one specific circuit function class.Definition 2.8. FAC 0 R k is the class of all functions f : (R k ) * → (R k ) * that can be computed by arithmetic circuit families (C n ) n∈N of constant depth and polynomial size, i.e., FAC 0 R k = FSIZE-DEPTH R k (n O(1) , 1). By Definition 2.7, FAC 0 R k [A]-circuit families are FAC 0 R k -circuitfamilies where the circuits are expanded by additional gate types for all functions in A.A node in a 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 a symmetry condition on them. We require the functions they compute to be tail-symmetric, i.e., to only be able to single out their first argument. Definition 2.9.A function f : (R k ) * → (R k ) * is tail-symmetric, if f (x 1 , . . . , x n ) = f (x 1 , π(x 2 , . . . , x n )) for all permutations π.Remark 2.10. One way to construct a tail-symmetric function f is to take a binary function g and a fully symmetric function h of arbitrary arity and compose them: f (x 1 , . . . , x n ) := g(x 1 , h(x 2 , . . . , x n )). Note that this is precisely the notion required for the aggregate-combine step in AC-GNNs as per Definition 2.2.An arithmetic circuit C is tail-symmetric if f C is tail-symmetric. In the sequel, we will consider families of tail-symmetric functions computed by some circuit family C. In this setting, the circuit family computes one unique function f n for each arity n ∈ N. We will then writef C (x 1 , { {x 2 , . . . , x n } }) to denote f n (x 1 , . . . , x n ), when { {x 2 , . . . , x n } } is a multiset of cardinality n -1.Definition 2.11. Let F be a circuit function class. We denote by tF the class which contains all functions of F that are tail-symmetric.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: The theoretical limitations for our results were discussed and mentioned before the respective proofs. Experimental limitations do not apply to this theoretical paper. Guidelines:• The answer NA means that the paper has no 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 a 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 a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 of 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, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 3. Theory Assumptions and Proofs some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
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 a two-step aggregate and combine computation via which the new feature vector of a 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.A basis of a C-GNN is a set of functions of a 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 a non-empty set of functions from (R k ) * to (R k ) * and let A be a non-empty set of activation functions of dimension k. Then we call the set S × A a C-GNN-basis of dimension k.C-GNNs of a particular basis essentially consist of a fixed depth and a function assigning circuit families and activation functions from its basis to its different layers. Let G = (V, E, g V ) be a labeled graph. The labeled graph G ′ computed by f N (G) has the same structure as G, however, its nodes have different feature vectors. That is f N (G) = G ′ , where G ′ = (V, E, h V ) and h V is defined inductively as follows:h (0) V (w) := g V (w) h (i) V (w) := σ (i) f C (i) h (i-1) V (w), M , with M = h (i-1) V (u) | u ∈ N G (w)whereN (i) = C (i) , σ (i) . Finally h V (w) := h (d) V (w).The C-GNN model that we have just defined computes functions from labeled graphs to labeled graphs (with the same graph structure).Our results are stated for C-GNNs using functions from versions of the function class FAC 0 R k 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 FAC 0 R k -circuit families, there exists a (FAC 0 R k , 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 G = (V, E, g V ) be a labeled graph, n := |V |, and M = adj(G) be the adjacency matrix of (V, E), where the columns are ordered in accordance with the ordering of V . We write ⟨M ⟩ to denote the encoding of M as the n 2 matrix entries written using vectors (0, . . . , 0) and (1, . . . , 1) in R k , ordered in a row wise fashion. We denote them by m ij encoding the matrix entry m ij . We write ⟨G⟩ to denote the encoding of G as a tuple of real valued vectors, such that ⟨G⟩ = (⟨M ⟩, vec(G)) ∈ (R k ) n 2 +n , which consists of the encoding of M followed by vec(G), the feature vectors of G. The feature vectors vec(G) are g V (v) for all v ∈ V and ordered like V .Theorem 3.6. Let N be a (tFAC 0 R k [A], {id})-GNN. Then there exists an FAC 0 R k [A]-circuit family C, such that for all labeled graphs G the following holds:f N (G) = G ′ iff C(⟨G⟩) = ⟨G ′ ⟩, where ⟨G⟩ = (⟨adj(G)⟩, ⟨vec(G)⟩).Proof. We essentially roll out the given (tFAC 0 R k [A], {id})-GNN N by using a circuit to simulate each individual layer of N and concatenating these circuits to then simulate N . Since the computation in each node of N can be performed by a circuit of an FAC 0 R k [A]-family, 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 FAC 0 R k [A]-family. The full proof can be found in the arXiv version Barlag et 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, (tFAC 0 R k [A], {id})-GNNs are at least as powerful as (tFAC 0 R k , {id} ∪ A)-GNNs and (tFAC 0 R k , {id})-GNNs. The latter do not have access to the functions of A at all and (tFAC 0 R k , {id} ∪ A)-GNNs are more restricted in the use of the functions than (tFAC 0 R k [A], {id})-GNNs.In order to simulate FAC 0 R k -circuit 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 an 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 FAC 0 R k -circuit family. Then for every circuit C ∈ C there exists a circuit C ′ of the same depth in path-length normal form such that fC ′ (x) = f C (x), for all x ∈ (R k ) * .Proof. We describe a procedure that transforms C to C ′ . If a gate h 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(C)(= depth(C ′ )) be the length of the longest path from an input to an output node in C. For every path of length ℓ which is shorter than ℓ max , we add to C ′ ℓ max -ℓ 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 in 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 circuits typically work on vectors over R k , we show next how to represent a circuit as an input to a C-GNN. Definition 3.10. If C is a circuit with input x whose gates are additionally numbered with unique elements of R, let G C,x be the labeled graph (G, g V ), where G = (V, E) is the underlying graph of the circuit and the function g V is defined as follows. The feature vector of a 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 as its feature vector.v in1 v (1) in1 = 6 v in2 v (1) in2 = 9 v in3 v (1) in3 = 5 v + v (1) + = 1 v × v (1) × = 2 . . .The following theorems describe how C-GNNs are 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 k and R circuits can simulate each other with constant increase/decrease in size, so they also hold for R k circuits.Theorem 3.11. Let C = (C n ) n∈N be an FAC 0 R -circuit family. Then there exists a (tFAC 0 R , {id})-GNN N , such that for all n ∈ N and x ∈ R n , the feature vectors of the nodes of f N (G Cn,x ) corresponding to output gates in C n are exactly the components of f Cn (x) in the same order. The number of layers in N is equal to the depth of C.Proof. The general idea is to use the graphs of the circuits from C as input graphs for a 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 to decide which operation is applied to a feature vector. An example illustrating the proof idea is given in Figure 1 and Table 1 . For simplicity reasons an example omitting any special cases is 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 0 R k [A]-circuit families we now examine the converse direction: simulating these families with C-GNNs.Theorem 3.12. Let C = (C n ) n∈N be an FAC 0 R [A]-circuit family. Then there exists a (tFAC 0 R [A], {id})-GNN N , such that for all n ∈ N and x ∈ R n , the feature vectors of the nodes of f N (G Cn,x ) corresponding to output gates in C n are exactly the components of f Cn (x) in the same order. The number of layers in N is equal to the depth of C. 6) σ( 9) σ( 1) σ( 9) σ(σ -1 (3)) = 3 3 σ( 6) σ( 9) σ( 1) σ( 9) σ( 6) + σ( 9)v in1 v (1) in1 = 6 v in2 v (1) in2 = 9 v σ v (1) + = 1 v ′ σ v ′(1) + = 2 v + v (1) + = 3 . . .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 to the same set of functions A in the form of gates that compute them. Those are then used to simulate gates from C that compute functions of A. 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 0 R -circuit families as is and that they can simulate FAC 0 R [A]-circuit families if they have arbitrary access to the functions in A. If we consider A to consist of activation functions, though, it would be more natural to only permit them as such in our C-GNN model. In the following we will introduce a structural restriction of circuits, which will allow us to capture a subset of FAC 0 R [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 ≤ depth(C) all gates of C at depth d have the same gate type. Definition 3.14. Let F be a circuit function class. We denote by f F the class which contains all functions of F that can be computed by circuit families where all circuits are in function-layer form.We also need a small restriction on the functions we will permit as activation functions. Definition 3.15. A computable function f : R k → R k is countably injective if there is a countably infinite set S ⊆ R k such that f↾ S is injective. We also say that f is countably injective on S. Remark 3.16. The commonly used activation functions ReLU(x) = max(0, x), σ(x) = 1 1+e -x and tanh(x) = e x -e -x e x +e -x are countably injective. Theorem 3.17. Let A be a set of countably injective activation functions and let C = (C n ) n∈N be a f FAC 0 R [A]-circuit family. Then there exists a (tFAC 0 R , A ∪ {id})-GNN N , such that for all n ∈ N and x ∈ R n , the feature vectors of the nodes of f N (G Cn,x ) corresponding to output gates in C n are exactly the components of f Cn (x) in the same order. The number of layers in N is equal to the depth of C.Proof. Contrary to the proof of Theorem 3.12 the gates in C computing a function σ ∈ A are simulated in the C-GNN by using the respective function as an activation function applied to all nodes. To distinguish between nodes where this function should and should not be applied we assign σ -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 in Figure 2 and Table 2 . 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] . 
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 0 R [A]-circuit family needs to be in function-layer 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 if(tFAC 0 R k , {id} ∪ A)-GNNs can be simulated by f FAC 0 R k [A] families and, if (tf FAC 0 R k , {id} ∪ A)- GNNs and f FAC 0 R k [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 of Sato et al. [2019] , we 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 is 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-uniformity (U E * -uniformity) 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 expressiveness of a 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 a 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 a PTIME upper bound (in the so-called BSS-model of computation) for the arithmetic circuit complexity class NC R that uses the sign function Cucker [1992] .As it currently stands, there does not seem to be meaningful experiments that could be run for our model of computation. 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. 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 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. Merrill et al. [2022] , Merrill and Sabharwal [2022] have studied transformer networks from a computational complexity perspective and obtained a TC 0 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 to what we have done in this paper for GNNs. 
open access to data and code: 
 Question: Does the paper provide open access to the data and code, with sufficient instructions 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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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. 
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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• 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 or the standard error of the mean. Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or 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 as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We carefully inspected the NeurIPS Code of Ethics, and as a purely theoretical paper its requirements do not apply. In general, our research conforms with general research ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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:• 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 a 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 as 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 or unintentional) misuse of the technology. • If 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). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: [NA] Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a 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 is used and, if 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing 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 as 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 in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as 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. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on 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. 
 
 Appendix: For readability purposes the one-dimensional vectors in the C-GNN are written as real numbers. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - I think this paper would benefit from more detailed discussion on the relationship with WL tests.
questions: questions: - Is there any numerical experiments you can run to demonstrate your theoretical findings?
limitations: limitations: The limitations have been sufficiently addressed in the paper.
paper_summary: paper_summary: In this article, the authors present new contributions on the understanding on the computational framework provided by GNNs.
In particular, they draw a connection between Arithmetic Circuits and GNNs. 

Based 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).
strength_weakness: strength_weakness: - 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:

$$ \text{AC-GNN} \subsetneq (\text{ C-GNNs} = FAC^{0}_{\mathbb{R}^{k}}[\mathcal{A}] )$$

There 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)? 

- 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.
questions: 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?

- 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.

- 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?)

- 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.]. 

- 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.
 

- 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:

- Impact of aggregation function: 		Eran Rosenbluth, Jan Tönshoff, Martin Grohe ``Some might say all you need is sum``
Martin Grohe, Eran Rosenbluth               ``Are Targeted Messages More Effective?``

- Impact of activation function on GNN expressivity: Sammy Khalife ``Graph Neural Networks with polynomial activations cannot express all GC2 queries``
						    
- Sammy Khalife, Amitabh Basu	``On the power of graph neural networks and the role of the activation function.``


- 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?

- 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: limitations: The authors are transparent in the conclusion of their work about the limitations of their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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)

2. 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)
questions: 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?

2. 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?

3. The paper does not discuss applications to deep learning, which may limit its appeal to the NeurIPS audience. 
- Could you elaborate on potential practical problems that the FAC-circuit family can solve or not solve? 
- 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?

4. 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.

[1] Sato, Ryoma, Makoto Yamada, and Hisashi Kashima. "Approximation ratios of graph neural networks for combinatorial problems." NeurIPS 2019.
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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).

I think there are some weaknesses regarding the presentation at multiple points in the paper (hence the 2/4 score), which I list below:
- 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.
- 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.
- 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).
- 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.
- L202 uses the star symbol. I suppose this is the Kleene star operator, but it seems to not be defined.
- 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.
- 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.

I strongly recommend all these issues to be eventually fixed in the camera ready of the paper, which should require modest effort.
questions: questions: I list my questions below:
1. 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?
2. 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?
3. 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.
4. 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?
5. 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: 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.

Comments: title: Response by authors
Connections between our work and VVc-GNNs
comment: *Regarding tail symmetric functions:* One very simple way of constructing tail-symmetric functions would be by defining a circuit that computes a symmetric function in arbitrarily many inputs $f(x_1, ..., x_n)$ (e.g. the sum of all inputs) and one that computes a binary function $g(x_1, x_2)$ (e.g. a linear function in two variables). If one then takes the result of the symmetric function as the second input to the binary function, i.e., $h(x_1, ..., x_n) := g(x_1, f(x_2, ..., x_(n+1)))$, then the resulting functin $h$ is tail-symmetric. This particular example would yield one way to define aggregate-combine GNNs as per Barceló et al. [Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, Juan Pablo Silva. The Logical Expressiveness of Graph Neural Networks. ICLR 2020.], but of course any kind of such functions are possible.
It should be noted, that this is by no means a complete characterization of such functions and that investigating functions of that kind would be an interesting avenue for further research. In particular, we deem it interesting to study circuits which compute tail-symmetric functions and ideally obtain a normal form of such circuits, i.e., a syntactical characterization for all functions of that kind.

*Regarding uniformity:* We will add some comments about uniformity to the main body of the paper.
Thanks for the detailed explanations. I think this paper will be of interest for the GNN community and researchers at the interface with circuit complexity. I strongly encourage the authors to include the changes discussed and will maintain my score as is.
Thank you for your kind comments. We added an official comment that highlights the issues raised in point 4.
As requested by the reviewer FVmx, we highlight here possible connections and differences of our work and VVc-GNNs introduced in [1] that we mentioned in our response to FVmx.

The article [1] is indeed an important paper as it is a precursor for the logical characterisations of Barceló et al. [2] and Grohe [3]. 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 [4] (where the model VVc of distributed computing that [1] take inspiration from is studied) one obtains a weaker form of the logical characterisation later proved directly for GNNs in [2]. We will add a comment about this in the final version.

[1] Ryoma Sato, Makoto Yamada, Hisashi Kashima: Approximation Ratios of Graph Neural Networks for Combinatorial Problems. NeurIPS 2019.

[2] Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, Juan Pablo Silva. The Logical Expressiveness of Graph Neural Networks. ICLR 2020.

[3] Martin Grohe. The Descriptive Complexity of Graph Neural Networks. LICS 2023

[4] Lauri Hella, Matti Järvisalo, Antti Kuusisto, Juhana Laurinharju, Tuomo Lempiäinen, Kerkko Luosto, Jukka Suomela, Jonni Virtema. Weak Models of Distributed Computing, with Connections to Modal Logic. PODC 2012.
>Are you asking if there exists a syntactic characterization of the notion of tail-symmetry, since this notion is purely semantical?

Yes, or better, I am asking what are the possible ways to construct tail-symmetric functions. Can you also provide some examples?

>Defining that notion precisely will still require some work.

Thank you for the very clear explanation.
I still suggest the authors to try to give an outline of what "uniform" means in the paper.


I have updated my score as to reflect the answers given by the authors.
I appreciate the authors' rebuttal, which has addressed many of my concerns, prompting me to increase my score to 6. While the practical impact of the paper remains unclear to me, I am convinced that it has the potential to inspire subsequent research in the field. I would suggest that the authors highlight the takeaways and proofs that could spark future work. Additionally, I would like to remind the authors to **include an official comment on the point raised in item 4 of the rebuttal** as soon as possible.
Many thanks for your rebuttal!