# Graph Neural Networks and Arithmetic Circuits

Author1

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

om{{#2}} marginparsep has been altered.
topmargin has been altered.
marginparpush has been altered.
The page layout violates the ICML style. Please do not change the page layout,
or include packages like geometry, savetrees, or fullpage, which change it for
you. We’re not able to reliably undo arbitrary changes to the style. Please
remove the offending package(s), or layout-changing commands and try again.

Graph Neural Networks and Arithmetic Circuits

Timon Barlag 1  Vivian Holzapfel 1  Laura Strieker 1  Jonni Virtema 2
Heribert Vollmer 1

††footnotetext:  1Institute for Theoretical Computer Science, Leibniz
University Hanover, Hanover, Germany 2Department of Computer Science,
University of Sheffield, Sheffield, United Kingdom. Correspondence to:
Heribert Vollmer<EMAIL_ADDRESS>

##  1 Introduction

Background and Related Work. Neural networks have recently received growing
attention from a theoretical point of view in a number of papers studying
their computational properties. The computational complexity of the training
process has been studied in Šíma (2002); Abrahamsen et al. (2021);
Bertschinger et al. (2022); Hankala et al. (2023). For a wide range of
activation functions, it is essentially complete for the class
$\exists\mathbb{R}$, i.e., equivalent to the existential theory of the real
numbers, extended with the corresponding activation function. In a sense,
complexity of training and the class $\exists\mathbb{R}$ correspond to each
other, and the activation function becomes a parameter in this correspondence
Hankala et al. (2023).

More important for 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 & Sontag (1995); Maass (1997); He &
Papakonstantinou (2022). Most importantly, Maass 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 $\mathrm{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). Their expressive power can be closely related to the
Weisfeiler-Leman algorithm Xu et al. (2019); Morris et al. (2019; 2021).
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. 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. Barceló et al. then consider an extension of
GNNs by so called global readout and show that these can compute all queries
from the logic FOC2 (first-order restricted to two variables, but extended
with counting quantifiers, a superclass of GC), but the converse is open.

Grohe Grohe (2023) very recently extended these results, and furthermore
connected GNNs to Boolean circuits. First, he considers a different 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 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)333The 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 $\mathrm{TC}^{0}$ computable, he obtains a $\mathrm{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
$\mathrm{TC}^{0}$ circuit is computable by a GNN with so-called random
initialization.

Our Contribution. Our paper differs from and extends the mentioned previous
studies mainly in two respects.

First, neural networks operate on real numbers, 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 their computational power—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 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. A
logic MPLang operating directly on real numbers was introduced in Geerts et
al. (2022) 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.

Our goal is exactly to characterize the computational power of GNNs as a model
of computation over real numbers or labeled graphs. We do not aim to relate
these to a Boolean computation model by approximating the real numbers.
Instead 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. 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 as in the previous studies, but an equivalence between GNNs and
constant-depth arithmetic circuits over the reals. 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.

Our second contribution is 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.

Following a broad line of research outlined by William Merrill 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 between layers and hence their communication
capabilites correspond to the given input graph. However, contrary to most
predecessor papers Morris et al. (2019); Barceló et al. (2020) we 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 continous graph-based “message passing” 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. This form of result is
similar to the above mentioned result by Hankala et al. (2023) about the
training process, in both the activation function is a parameter in the
statement of the theorem.

A number of remarks are in order.

  * –

Our result establishes an exact correspondence between GNNs and arithmetic
circuits, not only an upper bound for neural networks.

  * –

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, 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 inidivudal 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 proved principal
limits of networks following the GNN framework, extending the current AC-GNNs.
Our results show that if we need a network whose abilities are beyond that of
constant-depth circuits over the reals, we will have to develop a new network
architecture. Scaling up GNN networks or allowing more powerful computations
in the nodes of GNN networks will not help.

Organisation. 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, some proofs marked with $\dagger$ are deferred to the appendix.

##  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 $\lvert\overline{x}\rvert$ to denote the length of
$\overline{x}$ (i.e., the number of elements of $\overline{x}$), and use $[n]$
to denote the first $n$ nonzero natural numbers $\\{1,\dots,n\\}$. The
notation $\left\\{\\!\\!\left\\{\right\\}\\!\\!\right\\}$ is used for
multisets.

######  Definition 2.1.

Let $k\in\mathbb{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}\colon
V\to\mathbb{R}^{k}$ be a function. We then call $\mathfrak{G}=(V,E,g_{V})$ a
_labeled graph of dimension $k$_ and denote by $\mathfrak{Graph}$ the set of
all labeled graphs and by $\mathfrak{Graph}_{k}$ the set of all labeled graphs
of dimension $k$.

For a node $v\in V$, the _neighborhood of $v$_ is defined as
$N_{\mathfrak{G}}(v)\coloneqq\\{w\in V\mid\\{v,w\\}\in 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.

An _aggregation function_ (of dimension $k$) is a permutation-invariant
function
$\text{AGG}:\mathbb{R}^{k}\times\dots\times\mathbb{R}^{k}\to\mathbb{R}^{k}$, a
_combine function_ (of dimension $k$) is a function
$\text{COM}:\mathbb{R}^{k}\times\mathbb{R}^{k}\to\mathbb{R}^{k}$ and a
_classification function_ (of dimension $k$) is a function
$\text{CLS}:\mathbb{R}^{k}\to\\{0,1\\}$ that classifies a real vector as
either true or false. Finally, an _activation function_ (of dimension $k$) is
a componentwise function $\sigma\colon\mathbb{R}^{k}\to\mathbb{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
$\mathcal{D}=(\\{\text{AGG}^{(i)}\\}_{i=1}^{L},\\{\text{COM}^{(i)}\\}_{i=1}^{L},\\{\sigma^{(i)}\\}_{i=1}^{L},\allowbreak\text{CLS})$,
where $\\{\text{AGG}^{(i)}\\}_{i=1}^{L}$ and
$\\{\text{COM}^{(i)}\\}_{i=1}^{L}$ are sequences of combine and aggregation
functions, $\\{\sigma^{(i)}\\}_{i=1}^{L}$ is a sequence of activation
functions and CLS is a classification function.

Given a labeled graph $\mathfrak{G}=(V,E,g_{V})$, the AC-GNN model computes
vectors $\overline{x}_{v}^{(i)}$ for every $v\in V$ in every layer $1\leq
i\leq L$ as follows: $\overline{x}_{v}^{(0)}=g_{V}(v)$ is the initial feature
vector of $v$, and for $i>1$

$\displaystyle\overline{x}_{v}^{(i)}=\sigma^{(i)}\left(\text{COM}^{(i)}\left(\overline{x}_{v}^{(i-1)},\overline{y}\right)\right),$
$\displaystyle\text{where
}\overline{y}=\text{AGG}^{(i)}\left(\ms[\big{]}{\overline{x}_{u}^{(i-1)}\mid
u\in N_{\mathfrak{G}}(v)}\right).$

The classification function CLS: $\mathbb{R}^{k}\to\\{0,1\\}$ is applied to
the resulting feature vectors $\overline{x}_{v}^{(L)}$.

In this paper we focus on the real computation part of GNNs and discard the
classification function. We consider the feature vectors
$\overline{x}_{v}^{(L)}$ after 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
$\mathbb{R}^{k}$ rather than relative to $\mathbb{R}$, as is done more
commonly (cf. e.g. Blum et al. (1997)). It should be noted that for any fixed
$k\in\mathbb{N}$, circuits over $\mathbb{R}^{k}$ and circuits over
$\mathbb{R}$ can easily simulate each other as we will show in Lemmas 2.8 and
2.9.

######  Definition 2.3.

Let $k,n,m\in\mathbb{N}$. An _$\mathbb{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\in\mathbb{R}^{k}$,

  * •

there are gates labeled _projection i,j_ for $1\leq i,j\leq 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 $\mathbb{R}^{k}$-arithmetic circuit $C$ with $n$ inputs and $m$ outputs
computes the function $f_{C}\colon(\mathbb{R}^{k})^{n}\to(\mathbb{R}^{k})^{m}$
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 as inputs. By addition and multiplication we refer
to the respective componentwise operations and the projection computes the
function
$\textit{proj}_{i,j}{}\colon\mathbb{R}^{k}\rightarrow\mathbb{R}^{k},\>(x_{1},\dots,x_{i},\dots
x_{k})\mapsto(0,\dots,0,\underset{\text{position }j}{x_{i}},0,\dots,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 $0pt(C)$) is the length of the longest path from
an input gate to an output gate in $C$ and the _size_ of $C$ (written
$\textit{size}(C)$) is the number of gates in $C$. For a gate $g$ in $C$, we
will write $0pt(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 $\mathbb{R}^{k}$ that we have just
defined, a circuit over $\mathbb{R}$ is just a circuit over $\mathbb{R}^{1}$.
Note that for circuits over $\mathbb{R}^{1}$, projection gates are just
identity gates and can therefore be omitted.

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 _$\mathbb{R}^{k}$ -arithmetic circuit family_ $\mathcal{C}$ is a sequence
$(C_{n})_{n\in\mathbb{N}}$ of circuits, where each circuit $C_{n}$ has exactly
$n$ input gates. Its $0pt$ and size are functions mapping natural numbers $n$
to $0pt(C_{n})$ and $\textit{size}(C_{n})$, respectively.

An arithmetic circuit family $\mathcal{C}=(C_{n})_{n\in\mathbb{N}}$ computes
the function
$f_{\mathcal{C}}\colon(\mathbb{R}^{k})^{*}\to(\mathbb{R}^{k})^{*}$ defined as
$f_{\mathcal{C}}(\overline{x})\coloneqq
f_{C_{\lvert\overline{x}\rvert}}(\overline{x}).$

######  Definition 2.6.

For any $k\in\mathbb{N}$ and any two functions
$s,d\colon\mathbb{N}\to\mathbb{N}$,
$\mathrm{FSIZE}\text{-}\mathrm{DEPTH}_{\mathbb{R}^{k}}(s,d)$ is the class of
all functions $(\mathbb{R}^{k})^{*}\to(\mathbb{R}^{k})^{*}$ that are
computable by arithmetic circuit families of size in $\mathcal{O}(s)$ and
depth in $\mathcal{O}(d)$. Let $\mathcal{A}$ be a set of functions of the form
$f\colon\mathbb{R}^{k}\to\mathbb{R}^{k}$. Then
$\mathrm{FSIZE}\text{-}\mathrm{DEPTH}_{\mathbb{R}^{k}}(s,d)[\mathcal{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\in\mathcal{A}$.

We call all classes of the form
$\mathrm{FSIZE}\text{-}\mathrm{DEPTH}_{\mathbb{R}^{k}}(s,d)[\mathcal{A}]$ (and
their subclasses) _circuit function classes_. As usual in circuit complexity,
an _$\mathfrak{F}$ -circuit family_, where $\mathfrak{F}$ is a class of
functions, will denote a circuit family that computes a function in
$\mathfrak{F}$.

We restrict this work to versions of one specific circuit function class.

######  Definition 2.7.

$\mathrm{FAC}^{0}_{\mathbb{R}^{k}}$ is the class of all functions
$f\colon(\mathbb{R}^{k})^{*}\to(\mathbb{R}^{k})^{*}$ that can be computed by
arithmetic circuit families $(C_{n})_{n\in\mathbb{N}}$ of constant depth and
polynomial size, i.e.,
$\mathrm{FAC}^{0}_{\mathbb{R}^{k}}=\mathrm{FSIZE}\text{-}\mathrm{DEPTH}_{\mathbb{R}^{k}}(n^{\mathcal{O}(1)},1)$.

By Definition 2.6, $\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}]$-circuit
families are $\mathrm{FAC}^{0}_{\mathbb{R}^{k}}$-circuit families where the
circuits are expanded by additional gate types for all functions in
$\mathcal{A}$.

As mentioned earlier, circuits over $\mathbb{R}^{k}$ can be simulated by
circuits over $\mathbb{R}$ in the following sense.

######  Lemma 2.8.

Let $k,n,m\in\mathbb{N}$ be arbitrary. For each arithmetic circuit $C$ over
$\mathbb{R}^{k}$ with $n$ input and $m$ output gates, there exists an
arithmetic circuit $C^{\prime}$ over $\mathbb{R}$ with $n\cdot k$ input and
$m\cdot k$ output gates, such that $\textit{size}(C^{\prime})\leq
k\cdot\textit{size}(C)$, $0pt(C^{\prime})\leq 0pt(C)$ and for all
$\overline{x},\overline{y}\in\mathbb{R}^{k}$

$f_{C}\left((x_{11},\dots,x_{1k}),\dots,(x_{n1},\dots,x_{nk})\right)=\\\
((y_{11},\dots,y_{1k}),\dots,(y_{m1},\dots,y_{nk}))$

if and only if

$f_{C^{\prime}}(x_{11},\dots,x_{1k},\dots,x_{n1},\dots,x_{nk})=\\\
(y_{11},\dots,y_{1k},\dots,y_{m1},\dots,y_{mk}).$

###### Proof.

Each componentwise operation is replaced by the respective individual real
operations. Projections are realized by directly working with the projected
value and disregarding the values corresponding to the other elements of the
vectors and replacing them by constant $0$ gates. This way, there are $k$
arithmetic gates in $C^{\prime}$ for each arithmetic gate in $C$ and the depth
of $C$ is not increased. ∎

Similarly, $\mathbb{R}$ circuits can be simulated by $\mathbb{R}^{k}$
circuits.

######  Lemma 2.9.

Let $k,n,m\in\mathbb{N}$ be arbitrary. For each arithmetic circuit $C$ over
$\mathbb{R}$ with $n\cdot k$ input and $m\cdot k$ output gates, there exists
an arithmetic circuit $C^{\prime}$ over $\mathbb{R}^{k}$ with $n$ input and
$m$ output gates, such that $\textit{size}(C^{\prime})\leq
k\cdot(n+m)+m+\textit{size}(C)$, $0pt(C^{\prime})\leq 0pt(C)+3$ and for all
$\overline{x},\overline{y}\in\mathbb{R}^{k}$

$f_{C}(x_{11},\dots,x_{1k},\dots,x_{n1},\dots,x_{nk})=\\\
(y_{11},\dots,y_{1k},\dots,y_{m1},\dots,y_{mk})$

if and only if

$f_{C^{\prime}}((x_{11},\dots,x_{1k}),\dots,(x_{n1},\dots,x_{nk}))=\\\
((y_{11},\dots,y_{1k}),\dots,(y_{m1},\dots,y_{mk})).$

###### Proof.

First project all tuple elements to the first component of each tuple (i.e.
$(x_{1},\dots,x_{k})\mapsto(x_{1},0,\dots,0),(x_{2},0,\dots,0),\dots,(x_{k},0,\dots,0)$),
then compute as in the $\mathbb{R}^{1}$ circuit and finally project back when
reaching the output gates. Projecting from the input gates requires $k$
projection gates in $C^{\prime}$ for each input gate in $C$ and projecting
back to the output gates requires $k$ projection gates and one addition gate,
to put all projected values back into one vector. This results in a total
overhead in size of $k\cdot(n+m)+m$ and a total overhead in depth of $3$. ∎

######  Corollary 2.10.

For each arithmetic circuit family $\mathcal{C}$ over $\mathbb{R}$ of
polynomial size and constant depth, there exists an arithmetic circuit family
$\mathcal{C}^{\prime}$ over $\mathbb{R}^{k}$ of polynomial size and constant
depth such that for all $\overline{x},\overline{y}\in\mathbb{R}^{k}$

$f_{\mathcal{C}}(x_{11},\dots,x_{1k},\dots,x_{n1},\dots,x_{nk})=\\\
(y_{11},\dots,y_{1k},\dots,y_{m1},\dots,y_{mk})$

if and only if

$f_{\mathcal{C}^{\prime}}\left((x_{11},\dots,x_{1k}),\dots,(x_{n1},\dots,x_{nk})\right)=\\\
((y_{11},\dots,y_{1k}),\dots,(y_{m1},\dots,y_{nk})).$

Respectively an analogous family over $\mathbb{R}$ exists for each family over
$\mathbb{R}^{k}$.

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

A function $f\colon(\mathbb{R}^{k})^{*}\to(\mathbb{R}^{k})^{*}$ is _tail-
symmetric_ , if
$f(\overline{x}_{1},\dots,\overline{x}_{n})=f(\overline{x}_{1},\pi(\overline{x}_{2},\dots,\overline{x}_{n}))$
for all permutations $\pi$.

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 $\mathcal{C}$. In this setting, the circuit family
computes one unique function $f_{n}$ for each arity $n\in\mathbb{N}$. We will
then write
$f_{\mathcal{C}}\left(\overline{x}_{1},\left\\{\\!\\!\left\\{\overline{x}_{2},\dots,\overline{x}_{n}\right\\}\\!\\!\right\\}\right)$
to denote $f_{n}(\overline{x}_{1},\dots,\overline{x}_{n})$, when
$\left\\{\\!\\!\left\\{\overline{x}_{2},\dots,\overline{x}_{n}\right\\}\\!\\!\right\\}$
is a multiset of cardinality $n-1$.

######  Definition 2.12.

Let $\mathfrak{F}$ be a circuit function class. We denote by $t\mathfrak{F}$
the class which contains all functions of $\mathfrak{F}$ 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 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.

###  3.1 Model of Computation

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 $\mathcal{S}$ be a non-empty set of functions from $(\mathbb{R}^{k})^{*}$
to $(\mathbb{R}^{k})^{*}$ and let $\mathcal{A}$ be a non-empty set of
activation functions of dimension $k$. Then we call the set
$\mathcal{S}\times\mathcal{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 levels.

######  Definition 3.2.

Let $B=\mathcal{S}\times\mathcal{A}$ be a C-GNN-basis of dimension $k$. A
_circuit graph neural network (of dimension $k$)_ of depth $d\in\mathbb{N}$ is
a function $\mathcal{N}\colon[d]\to B$. If all functions in $\mathcal{S}$
belong to a circuit function class $\mathfrak{F}$, we also say that
$\mathcal{N}$ is a $(\mathfrak{F},\mathcal{A})$-GNN.

######  Definition 3.3.

Let $\mathcal{N}$ be a C-GNN of depth $d$. The function
$f_{\mathcal{N}}\colon\mathfrak{Graph}_{k}\to\mathfrak{Graph}_{k}$ computed by
$\mathcal{N}$ is defined as follows:

Let $\mathfrak{G}=(V,E,g_{V})$ be a labeled graph. The labeled graph
$\mathfrak{G}^{\prime}$ computed by $f_{\mathcal{N}}(\mathfrak{G})$ has the
same structure as $\mathfrak{G}$, however, its nodes have different feature
vectors. That is $f_{\mathcal{N}}(\mathfrak{G})=\mathfrak{G}^{\prime}$, where
$\mathfrak{G}^{\prime}=(V,E,h_{V})$ and $h_{V}$ is defined inductively as
follows:

$\displaystyle h_{V}^{(0)}(w)$ $\displaystyle\coloneqq~{}g_{V}(w)$
$\displaystyle h_{V}^{(i)}(w)$
$\displaystyle\coloneqq~{}\sigma^{(i)}\left(f_{\mathcal{C}^{(i)}}\left(h_{V}^{(i-1)}(w),M\right)\right),$
$\displaystyle\text{ with }M=\left\\{\\!\\!\left\\{h_{V}^{(i-1)}(u)\mid u\in
N_{\mathfrak{G}}(w)\right\\}\\!\\!\right\\}$

where
$\mathcal{C}^{(i)}\coloneqq\textit{proj}_{1}{\left(\mathcal{N}(i)\right)}$ and
$\sigma^{(i)}\coloneqq\textit{proj}_{2}{\left(\mathcal{N}(i)\right)}$ with
$\textit{proj}_{j}{}$ projecting onto the $j$th element, for $i\geq 1$.
Finally $h_{V}(w)\coloneqq h_{V}^{(d)}(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 $\mathrm{FAC}^{0}_{\mathbb{R}^{k}}$ as defined in Definitions
2.12 and 2.7.

######  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
$\mathcal{A}$ where the aggregation functions are computable by
$\mathrm{FAC}^{0}_{\mathbb{R}^{k}}$-circuit families, there exists a
$(\mathrm{FAC}^{0}_{\mathbb{R}^{k}},\mathcal{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 $\mathfrak{G}=(V,E,g_{V})$ be a labeled graph, $n\coloneqq\lvert V\rvert$,
and $M=\text{adj}(\mathfrak{G})$ be the adjacency matrix of $(V,E)$, where the
columns are ordered in accordance with the ordering of $V$. We write $\langle
M\rangle$ to denote the encoding of $M$ as the $n^{2}$ matrix entries written
using vectors $(0,\dots,0)$ and $(1,\dots,1)$ in $\mathbb{R}^{k}$, ordered in
a row wise fashion. We denote them by $\overline{m}_{ij}$ encoding the matrix
entry $m_{ij}$. We write $\langle\mathfrak{G}\rangle$ to denote the encoding
of $\mathfrak{G}$ as a tuple of real valued vectors, such that
$\langle\mathfrak{G}\rangle=\left(\langle
M\rangle,\text{vec}(\mathfrak{G})\right)\in(\mathbb{R}^{k})^{n^{2}+n}$, which
consists of the encoding of $M$ followed by $\text{vec}(\mathfrak{G})$, the
feature vectors of $\mathfrak{G}$. The feature vectors
$\text{vec}(\mathfrak{G})$ are $g_{V}(v)$ for all $v\in V$ and ordered like
$V$.

######  Theorem 3.6†.

Let $\mathcal{N}$ be a
$(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}],\\{\mathrm{id}\\})$-GNN.
Then there exists an $\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}]$-circuit
family $\mathcal{C}$, such that for all labeled graphs $\mathfrak{G}$ the
following holds:

$f_{\mathcal{N}}(\mathfrak{G})=\mathfrak{G^{\prime}}\text{ iff
}\mathcal{C}(\langle\mathfrak{G}\rangle)=\langle\mathfrak{G^{\prime}}\rangle$

where
$\langle\mathfrak{G}\rangle=(\langle\text{adj}(\mathfrak{G})\rangle,\langle\text{vec}(\mathfrak{G})\rangle)$.

###### Proof.

We essentially roll out the given
$(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}],\\{\mathrm{id}\\})$-GNN
$\mathcal{N}$ by using a circuit to simulate each individual layer of
$\mathcal{N}$ and concatenating these circuits to then simulate $\mathcal{N}$.
Since the computation in each node of $\mathcal{N}$ can be performed by a
circuit of an $\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}]$-family,
simulating this computation is no problem. Similarly, connecting the simulated
nodes and layers can be done relatively simply, and thus the resulting circuit
family is an $\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}]$-family. ∎

######  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 $\mathcal{A}$,
$(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}],\\{\mathrm{id}\\})$-GNNs are
at least as powerful as
$(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}},\\{\mathrm{id}\\}\cup\mathcal{A})$-GNNs
and $(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}},\\{\mathrm{id}\\})$-GNNs. The latter
do not have access to the functions of $\mathcal{A}$ at all and
$(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}},\\{\mathrm{id}\\}\cup\mathcal{A})$-GNNs
are more restricted in the use of the functions than
$(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}],\\{\mathrm{id}\\})$-GNNs.

###  3.3 Simulating arithmetic circuits with C-GNNs

In order to simulate $\mathrm{FAC}^{0}_{\mathbb{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 $\mathcal{C}$ be an $\mathrm{FAC}^{0}_{\mathbb{R}^{k}}$-circuit family.
Then for every circuit $C\in\mathcal{C}$ there exists a circuit $C^{\prime}$
of the same depth in path-length normal form such that
$f_{C^{\prime}}(\overline{x})=f_{C}(\overline{x})$, for all
$\overline{x}\in(\mathbb{R}^{k})^{*}$.

###### Proof.

We describe a procedure that transforms $C$ to $C^{\prime}$. 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^{\prime}$ for each successor of $h$.
These copies are then used as the respective input for those successors which
results in every gate in $C^{\prime}$ 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.
This entire procedure can be performed with polynomial overhead in size, and
$C^{\prime}$ therefore stays polynomial in size.

Let $\ell_{max}=0pt(C)(=0pt(C^{\prime}))$ be the length of the longest path
from an input to an output node in $C$. For every path of length $\ell$ which
is shorter than $\ell_{max}$, we add to $C^{\prime}$ $\ell_{max}-\ell$ unary
addition gates directly after the input. The depth of the resulting circuit
$C^{\prime}$ 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^{\prime}$ 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 $\mathbb{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 $\overline{x}$ whose gates are additionally
numbered with unique elements of $\mathbb{R}$, let
$\mathfrak{G}_{{C},\overline{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.

The following theorems describe how arithmetic circuits are able to simulate
C-GNNs. The proofs are given for $\mathbb{R}$ circuits, but since we proved in
Corollary 2.10 that families of constant depth and polynomial size
$\mathbb{R}^{k}$ and $\mathbb{R}$ circuits can simulate each other with
constant increase/decrease in size, they also hold for $\mathbb{R}^{k}$
circuits.

######  Theorem 3.11†.

Let $\mathcal{C}=(C_{n})_{n\in\mathbb{N}}$ be an
$\mathrm{FAC}^{0}_{\mathbb{R}}$-circuit family. Then there exists a
$(t\mathrm{FAC}^{0}_{\mathbb{R}},\\{\mathrm{id}\\})$-GNN $\mathcal{N}$, such
that for all $n\in\mathbb{N}$ and $\overline{x}\in\mathbb{R}^{n}$, the feature
vectors of the nodes of $f_{\mathcal{N}}(\mathfrak{G}_{{C_{n}},\overline{x}})$
corresponding to output gates in $C_{n}$ are exactly the components of
$f_{C_{n}}(\overline{x})$ in the same order. The number of layers in
$\mathcal{N}$ is equal to the depth of $\mathcal{C}$.

###### Proof.

The general idea is to use the graphs of the circuits from $\mathcal{C}$ as
input graphs for a C-GNN and then simulate the gates layerwise. The gates of
$\mathcal{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 (see Lemma A.3). 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. ∎

$6$$9$$5$$+$$nr(g_{+})=1$$\times$$nr(g_{\times})=2$$\vdots$ (a) Underlying
circuit, to be simulated by the C-GNN ($nr(\ast)$ denotes the unique number of
the gate)

$v_{\mathrm{in}_{1}}$$\overline{v}^{(1)}_{\mathrm{in}_{1}}=6$$v_{\mathrm{in}_{2}}$$\overline{v}^{(1)}_{\mathrm{in}_{2}}=9$$v_{\mathrm{in}_{3}}$$\overline{v}^{(1)}_{\mathrm{in}_{3}}=5$$v_{+}$$\overline{v}^{(1)}_{+}=1$$v_{\times}$$\overline{v}^{(1)}_{\times}=2$$\vdots$
(b) The labeled graph and initial feature vectors of the C-GNN ($v_{g}^{(i)}$
denotes the feature vector of a gate at layer $i$)

Figure 1: Example illustrating the proof of Theorem 3.11† 555For readability
purposes the one-dimensional vectors in the C-GNN are written as real numbers.

Table 1: Example illustrating the proof of Theorem 3.11†: The values of the
feature vectors during the computation of the C-GNN

Layer | $\overline{v}_{\mathrm{in}_{1}}$ | $\overline{v}_{\mathrm{in}_{2}}$ | $\overline{v}_{\mathrm{in}_{3}}$ | $\overline{v}_{+}$ | $\overline{v}_{\times}$
---|---|---|---|---|---
1 | $6$ | $9$ | $5$ | $1$ | $2$
2 | $6$ | $9$ | $5$ | $6+9=15$ | $2$
3 | $6$ | $9$ | $5$ | $15$ | $5\times 15=75$

Since we have shown in Section 3.2 that C-GNNs can be simulated by
$\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}]$-circuit families we now
examine the converse direction: simulating these families with C-GNNs.

######  Theorem 3.12†.

Let $\mathcal{C}=(C_{n})_{n\in\mathbb{N}}$ be an
$\mathrm{FAC}^{0}_{\mathbb{R}}[\mathcal{A}]$-circuit family. Then there exists
a $(t\mathrm{FAC}^{0}_{\mathbb{R}}[\mathcal{A}],\\{\mathrm{id}\\})$-GNN
$\mathcal{N}$, such that for all $n\in\mathbb{N}$ and
$\overline{x}\in\mathbb{R}^{n}$, the feature vectors of the nodes of
$f_{\mathcal{N}}\left(\mathfrak{G}_{{C_{n}},\overline{x}}\right)$
corresponding to output gates in $C_{n}$ are exactly the components of
$f_{C_{n}}(\overline{x})$ in the same order. The number of layers in
$\mathcal{N}$ is equal to the depth of $\mathcal{C}$.

###### 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 $\mathcal{A}$ in the form of gates that compute them. Those
are then used to simulate gates from $\mathcal{C}$ that compute functions of
$\mathcal{A}$.∎

In the previous two theorems, we have shown that C-GNNs can simulate
$\mathrm{FAC}^{0}_{\mathbb{R}}$-circuit families as is and that they can
simulate $\mathrm{FAC}^{0}_{\mathbb{R}}[\mathcal{A}]$-circuit families if they
have arbitrary access to the functions in $\mathcal{A}$. If we consider
$\mathcal{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 $\mathrm{FAC}^{0}_{\mathbb{R}}[\mathcal{A}]$ using C-GNNs
that have access to $\mathcal{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\leq 0pt(C)$ all gates of $C$ at depth $d$
have the same gate type.

######  Definition 3.14.

Let $\mathfrak{F}$ be a circuit function class. We denote by $f\mathfrak{F}$
the class which contains all functions of $\mathfrak{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\colon\mathbb{R}^{k}\to\mathbb{R}^{k}$ is _countably
injective_ if there is a countably infinite set $S\subseteq\mathbb{R}^{k}$
such that $f\\!\\!\restriction_{S}$ is injective. We also say that $f$ is
countably injective on $S$.

######  Remark 3.16.

The commonly used activation functions $\mathrm{ReLU}(x)=\max(0,x)$,
$\sigma(x)=\frac{1}{1+\mathrm{e}^{-x}}$ and
$\mathrm{tanh}(x)=\frac{\mathrm{e}^{x}-\mathrm{e}^{-x}}{\mathrm{e}^{x}+\mathrm{e}^{-x}}$
are countably injective.

######  Theorem 3.17†.

Let $\mathcal{A}$ be a set of countably injective activation functions and let
$\mathcal{C}=(C_{n})_{n\in\mathbb{N}}$ be a
$f\mathrm{FAC}^{0}_{\mathbb{R}}[\mathcal{A}]$-circuit family. Then there
exists a
$(t\mathrm{FAC}^{0}_{\mathbb{R}},\mathcal{A}\cup\\{\mathrm{id}\\})$-GNN
$\mathcal{N}$, such that for all $n\in\mathbb{N}$ and
$\overline{x}\in\mathbb{R}^{n}$, the feature vectors of the nodes of
$f_{\mathcal{N}}\left(\mathfrak{G}_{{C_{n}},\overline{x}}\right)$
corresponding to output gates in $C_{n}$ are exactly the components of
$f_{C_{n}}(\overline{x})$ in the same order. The number of layers in
$\mathcal{N}$ is equal to the depth of $\mathcal{C}$.

###### Proof.

Contrary to the proof of Theorem 3.12† the gates in $\mathcal{C}$ computing a
function $\sigma\in\mathcal{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 $\sigma^{-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 LABEL:tbl:circ_to_cgnn_fnc. As in the proof of Theorem 3.17† an example
omitting any special cases is chosen. ∎

$6$$9$$\sigma$$nr(g_{\sigma})=1$$\sigma$$nr(g^{\prime}_{\sigma})=2$$+$$nr(g_{+})=3$$\vdots$
(a) Underlying circuit, to be simulated by the C-GNN ($nr(\ast)$ denotes the
unique number of teh gate)

$v_{\mathrm{in}_{1}}$$\overline{v}^{(1)}_{\mathrm{in}_{1}}=6$$v_{\mathrm{in}_{2}}$$\overline{v}^{(1)}_{\mathrm{in}_{2}}=9$$v_{\sigma}$$\overline{v}^{(1)}_{+}=1$$v_{\sigma}^{\prime}$$\overline{v}^{\prime(1)}_{+}=2$$v_{+}$$\overline{v}^{(1)}_{+}=3$$\vdots$
(b) The labeled graph and initial feature vectors of the C-GNN ($v_{g}^{(i)}$
denotes the feature vector of a gate at layer $i$)

Figure 2: Example illustrating the proof of Theorem 3.17† ††footnotemark:

Table 2: Example illustrating the proof of Theorem 3.17†: The values of the
feature vectors during the computation of the C-GNN.

Layer | $\overline{v}_{\mathrm{in}_{1}}$ | $\overline{v}_{\mathrm{in}_{2}}$ | $\overline{v}_{\sigma}$ | $\overline{v}^{\prime}_{\sigma}$ | $\overline{v}_{+}$
---|---|---|---|---|---
1 | $6$ | $9$ | $1$ | $2$ | $3$
2 | $\sigma(6)$ | $\sigma(9)$ | $\sigma(1)$ | $\sigma(9)$ | $\sigma(\sigma^{-1}(3))=3$
3 | $\sigma(6)$ | $\sigma(9)$ | $\sigma(1)$ | $\sigma(9)$ | $\sigma(6)+\sigma(9)$

##  4 Conclusion

In this paper we have shown a correspondence between a generalization of graph
neural networks using circuits and arithmetic circuits themselves. However,
some restrictions needed to be imposed on the particular circuits used in our
constructions. In particular, the circuits used in our C-GNNs needed to be
tail symmetric and for Theorem 3.17† the corresponding
$\mathrm{FAC}^{0}_{\mathbb{R}}[\mathcal{A}]$-circuit family needed to be in
function-layer form. In order to arrive at a connection which is in some sense
more direct, an interesting avenue for further research is the question,
whether those restrictions can be made “on both sides of the inequalities”.
This means in particular to ask if
$(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}},\\{id\\}\cup\mathcal{A})$-GNNs can be
simulated by $f\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}]$ families and,
if $(tf\mathrm{FAC}^{0}_{\mathbb{R}^{k}},\\{id\\}\cup\mathcal{A})$-GNNs and
$f\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}]$ can simulate each other.

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 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. This should be made more precise. In the case of circuits, logtime-
uniformity (UE°∗-uniformity) has become the standard requirement Vollmer
(1999). What is the corresponding precise uniformity notion for GNNs?

William Merrill and co-authors Merrill et al. (2022); Merrill & Sabharwal
(2022) have studied transformer networks from a computational complexity
perspective and obtained a $\mathrm{TC}^{0}$ upper bound, similar as Grohe did
for GNNs. We think it is worthwhile to study transformers and study their
computational power from the point of view of computation over the reals,
similar to what we have done in this paper for GNNs.

In the introduction we mentioned the complexity of the problem of training
neural networks. This paper studies 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?

## Acknowledgements

The first and the fourth author were partially supported by the DFG grant VI
1045-1/1.

## References

  * Abrahamsen et al. (2021) Abrahamsen, M., Kleist, L., and Miltzow, T.  Training Neural Networks is $\exists$R-complete.  In Ranzato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P., and Vaughan, J. W. (eds.), _Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual_ , pp. 18293–18306, 2021.  URL https://proceedings.neurips.cc/paper/2021/hash/9813b270ed0288e7c0388f0fd4ec68f5-Abstract.html.
  * Barceló et al. (2020) Barceló, P., Kostylev, E. V., Monet, M., Pérez, J., Reutter, J. L., and Silva, J. P.  The Logical Expressiveness of Graph Neural Networks.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_ , 2020.  URL https://openreview.net/forum?id=r1lZ7AEKvB.
  * Bertschinger et al. (2022) Bertschinger, D., Hertrich, C., Jungeblut, P., Miltzow, T., and Weber, S.  Training fully connected neural networks is $\exists$R-complete.  _CoRR_ , abs/2204.01368, 2022.  doi: 10.48550/ARXIV.2204.01368.  URL https://doi.org/10.48550/arXiv.2204.01368.
  * Blum et al. (1997) Blum, L., Cucker, F., Shub, M., and Smale, S.  _Complexity and Real Computation_.  Springer-Verlag, Berlin, Heidelberg, 1997.  ISBN 0387982817.
  * Geerts et al. (2022) Geerts, F., Steegmans, J., and Van den Bussche, J.  On the Expressive Power of Message-Passing Neural Networks as Global Feature Map Transformers.  In Varzinczak, I. (ed.), _Foundations of Information and Knowledge Systems - 12th International Symposium, FoIKS 2022, Helsinki, Finland, June 20-23, 2022, Proceedings_ , volume 13388 of _Lecture Notes in Computer Science_ , pp. 20–34. Springer, 2022.  doi: 10.1007/978-3-031-11321-5“˙2.  URL https://doi.org/10.1007/978-3-031-11321-5_2.
  * Grohe (2023) Grohe, M.  The Descriptive Complexity of Graph Neural Networks.  In _LICS_ , pp. 1–14, 2023.  doi: 10.1109/LICS56636.2023.10175735.  URL https://doi.org/10.1109/LICS56636.2023.10175735.
  * Hankala et al. (2023) Hankala, T., Hannula, M., Kontinen, J., and Virtema, J.  Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions.  _CoRR_ , abs/2305.11833, 2023.  doi: 10.48550/ARXIV.2305.11833.  URL https://doi.org/10.48550/arXiv.2305.11833.
  * He & Papakonstantinou (2022) He, S. and Papakonstantinou, P. A.  Deep Neural Networks: The Missing Complexity Parameter.  _Electron. Colloquium Comput. Complex._ , TR22-159, 2022.  URL https://eccc.weizmann.ac.il/report/2022/159.
  * Maass (1997) Maass, W.  Bounds for the Computational Power and Learning Complexity of Analog Neural Nets.  _SIAM J. Comput._ , 26(3):708–732, 1997.  doi: 10.1137/S0097539793256041.  URL https://doi.org/10.1137/S0097539793256041.
  * Maass et al. (1991) Maass, W., Schnitger, G., and Sontag, E. D.  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_ , pp. 767–776. IEEE Computer Society, 1991.  doi: 10.1109/SFCS.1991.185447.  URL https://doi.org/10.1109/SFCS.1991.185447.
  * Merrill (2022) Merrill, W.  Transformers are Uniform Constant-Depth Threshold Circuits.  https://www.youtube.com/watch?v=XF2UoA0oovg, 2022.
  * Merrill & Sabharwal (2022) Merrill, W. and Sabharwal, A.  Log-Precision Transformers are Constant-Depth Uniform Threshold Circuits.  _CoRR_ , abs/2207.00729, 2022.  doi: 10.48550/ARXIV.2207.00729.  URL https://doi.org/10.48550/arXiv.2207.00729.
  * Merrill et al. (2022) Merrill, W., Sabharwal, A., and Smith, N. A.  Saturated Transformers are Constant-Depth Threshold Circuits.  _Trans. Assoc. Comput. Linguistics_ , 10:843–856, 2022.  URL https://transacl.org/ojs/index.php/tacl/article/view/3465.
  * Morris et al. (2019) Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M.  Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks.  In _The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019_ , pp. 4602–4609. AAAI Press, 2019.  doi: 10.1609/AAAI.V33I01.33014602.  URL https://doi.org/10.1609/aaai.v33i01.33014602.
  * Morris et al. (2021) Morris, C., Fey, M., and Kriege, N. M.  The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs.  In Zhou, Z. (ed.), _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021_ , pp. 4543–4550. ijcai.org, 2021.  doi: 10.24963/IJCAI.2021/618.  URL https://doi.org/10.24963/ijcai.2021/618.
  * Siegelmann & Sontag (1995) Siegelmann, H. T. and Sontag, E. D.  On the Computational Power of Neural Nets.  _J. Comput. Syst. Sci._ , 50(1):132–150, 1995.  doi: 10.1006/JCSS.1995.1013.  URL https://doi.org/10.1006/jcss.1995.1013.
  * Vollmer (1999) Vollmer, H.  _Introduction to Circuit Complexity - A Uniform Approach_.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999.  ISBN 978-3-540-64310-4.  doi: 10.1007/978-3-662-03927-4.  URL https://doi.org/10.1007/978-3-662-03927-4.
  * Šíma (2002) Šíma, J.  Training a Single Sigmoidal Neuron is Hard.  _Neural Comput._ , 14(11):2709–2728, 2002.  doi: 10.1162/089976602760408035.  URL https://doi.org/10.1162/089976602760408035.
  * Xu et al. (2019) Xu, K., Hu, W., Leskovec, J., and Jegelka, S.  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 https://openreview.net/forum?id=ryGs6iA5Km.

##  Appendix A Appendix

The Appendix is organized as follows: Section A.1 goes into the concepts of
Section 3.1 and contains a proof for the remark concerning the connection
between AC-GNNs and C-GNNs. The other Sections A.2 and A.3 contain the full
proofs for the theorems of its respective section in the paper, as well as
additional required results.

###  A.1 Proofs of Section 3.1

As mentioned in Remark 3.4 our considered model of C-GNN relates to the
classical AC-GNN in the following way. The definition of an AC-GNN does not
fix the complexity of its aggregate and combine functions, hence to be able to
compare the two models we need to restrict both functions to be of a specific
circuit function class. This restriction holds for most practically used
functions like aggregating via the weighted sum and combining via summation of
the previous feature vector and the aggregate, each multiplied by a parameter
matrix. We now proceed to prove this.

######  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
$\mathcal{A}$ where the aggregation functions are computable by
$\mathrm{FAC}^{0}_{\mathbb{R}^{k}}$-circuit families, there exists a
$(\mathrm{FAC}^{0}_{\mathbb{R}^{k}},\mathcal{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.

###### Proof.

Let
$\mathcal{D}=(\\{\text{AGG}^{(i)}\\}_{i=1}^{L},\\{\text{COM}^{(i)}\\}_{i=1}^{L},\\{\sigma^{(i)}\\}_{i=1}^{L},\allowbreak\text{CLS})$
be an arbitrary AC-GNN as defined in Definition 2.2. A
$(\mathrm{FAC}^{0}_{\mathbb{R}^{k}},\mathcal{A})$-GNN computing the same
function can be realized by using $\mathrm{FAC}^{0}_{\mathbb{R}^{k}}$-circuit
families which compute the functions in $\\{\text{AGG}^{(i)}\\}_{i=1}^{L}$ and
$\\{\text{COM}^{(i)}\\}_{i=1}^{L}$. To compute a permutation-invariant
aggregation function a tail-symmetric circuit family
$\mathcal{C}_{\text{AGG}}$ computing a function
$f_{\mathcal{C}_{\text{AGG}}}=\text{AGG}^{(i)}$ as described in Definition
2.11 is used. The computation of a combine function can also be realised by
using $\mathrm{FAC}^{0}_{\mathbb{R}^{k}}$\- circuit families computing a
function $f_{\mathcal{C}_{\text{COMB}}}=\text{COMB}^{(i)}$. Afterwards the
application of the activation function $\sigma^{(i)}$ can be achieved by
adding $\sigma^{(i)}$ to the set $\mathcal{A}$ and denoting it as the
activation function for layer $i$ which is applied to all feature vectors
after the circuit computations of these layers are done. As said in the
beginning we are not concerned with classification in this paper, so we do not
aim to simulate the transition from the continuous to the discrete as
performed in the classification function of AC-GNNs. ∎

###  A.2 Proofs of Section 3.2

The proof of Theorem 3.6† requires us to be able to distinguish the feature
vectors of the neighborhood of a given node. This can be achieved by
essentially zeroing out all non-neighbors as follows.

######  Lemma A.1.

For each $k,n,i\in\mathbb{N}$ where $1\leq i\leq n$ there exists an
$\mathrm{FAC}^{0}_{\mathbb{R}^{k}}$-circuit family $\mathcal{C}$ such that for
all $\mathfrak{G}=(V,E,g_{V})\in\mathfrak{Graph}_{k}$ with
$V=\\{v_{1},\dots,v_{n}\\}$ it holds that

$f_{\mathcal{C}}(\langle\mathfrak{G}\rangle)=\langle\text{vec}(\mathfrak{G})^{\prime}\rangle$

where
$\langle\mathfrak{G}\rangle=(\langle\text{adj}(\mathfrak{G})\rangle,\langle\text{vec}(\mathfrak{G})\rangle)$
and for all $1\leq j\leq n$

$\text{vec}(\mathfrak{G})^{\prime}_{j}=\begin{cases}\text{vec}(\mathfrak{G})_{j},&\text{
if $\\{v_{i},v_{j}\\}\in E$}\\\ \overline{0},&\text{otherwise}\end{cases}$

where $\text{vec}(\mathfrak{G})^{\prime}_{j}$ and
$\text{vec}(\mathfrak{G})_{j}$ are the respective $j$th vectors of
$\text{vec}(\mathfrak{G})^{\prime}$ and $\text{vec}(\mathfrak{G})$.

###### Proof.

We write $v_{i}$ for the node $v$ which has number $i$ and $\overline{v}_{i}$
for its feature vector. Since the vectors in $\langle M\rangle$ with
$M=\text{adj}(\mathfrak{G})$ are ordered and the vectors $\overline{m}_{ij}$
for $1\leq j\leq\lvert V\rvert$ correspond to one row in the adjacency matrix,
row $\overline{m}_{ij}$ describes all edge relations of $v_{i}$. Given the
ordering on $\text{vec}(\mathfrak{G})$ we know that the $i$th vector in
$\text{vec}(\mathfrak{G})$ is the vector $\overline{v}_{i}$. We multiply each
vector $\overline{m}_{ij}$ with $\overline{v}_{j}$, resulting in

$\overline{m}_{ij}\overline{v}_{j}=\begin{cases}\overline{v}_{j},&\text{if
}(v_{i},v_{j})\in E\\\ \overline{0},&\text{otherwise}\end{cases}.$

We continue to work with these values. This sets all feature vectors of non-
neighboring nodes of $v_{i}$ to $\overline{0}$. ∎

We now proceed to prove Theorem 3.6†. A simplified illustration of the proof
is given in Figure 3.

######  Theorem 3.6†.

Let $\mathcal{N}$ be a
$(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}],\\{\mathrm{id}\\})$-GNN.
Then there exists an $\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}]$-circuit
family $\mathcal{C}$, such that for all labeled graphs $\mathfrak{G}$ the
following holds:

$f_{\mathcal{N}}(\mathfrak{G})=\mathfrak{G^{\prime}}\text{ iff
}\mathcal{C}(\langle\mathfrak{G}\rangle)=\langle\mathfrak{G^{\prime}}\rangle$

where
$\langle\mathfrak{G}\rangle=(\langle\text{adj}(\mathfrak{G})\rangle,\langle\text{vec}(\mathfrak{G})\rangle)$.

###### Proof.

We would like to mimic each of the (constantly many) C-GNN layers with a
circuit of constant depth. To do this we need to retrieve the correct circuit
from the circuit families of our C-GNN for each layer $i$ and for each
possible size of the neighborhood for a node $v\in V$. These values are
bounded by the number of layers $d$ of the C-GNN and the size $n=\lvert
V\rvert$ of the input labeled graph $\mathfrak{G}=(V,E,g_{V})$.

Since $\mathfrak{G}$ has $n$ nodes, our encoding $\langle\mathfrak{G}\rangle$
consists of $n^{2}$ vectors for the encoding of the adjacency matrix $M$ and
the feature vectors of the $n$ nodes. We construct a circuit family
$\mathcal{K}$ which consists of a series of circuits for any possible number
of nodes $n$.

While constructing a circuit $K$ from $\mathcal{K}$ we use
$\mathcal{C}^{(i)}=\textit{proj}_{1}{\left(\mathcal{N}(i)\right)}$ (see
Definition 3.3) to retrieve the circuit family of layer $i$ of the C-GNN. The
first observation we make is that if a node $v$ has $k$ neighbors, we need to
consider the $k+1$st circuit from the circuit family for the computation, as
this circuit gets all of the feature vectors of the neighbors of $v$ and the
feature vector of $v$ as input. We also observe that, since our circuits are
tail-symmetric, the order of the neighbors’ feature vectors does not matter.
We can figure out how many neighbors $v$ has by summing over $v$’s row in the
adjacency matrix of $\mathfrak{G}$.

The circuit $K$ works for a node $v$ in the following way. When given the
initial feature vectors and the encoding of the adjacency matrix $M$ of
$\langle\mathfrak{G}\rangle$ as input it first computes the size $k$ of the
neighborhood of $v$. It then sets the feature vectors of non-neighboring nodes
of $v$ to $\overline{0}$ via the functionality described in Lemma A.1.
Afterwards it orders the feature vectors of all nodes in $\mathfrak{G}$ such
that the initial order remains the same, but all $\overline{0}$ vectors get
pushed to the end.

We can achieve such an ordering by essentially using the idea of the counting
sort algorithm. We start by zeroing the non-neighbors, and then do a pairwise
comparison with all nodes in the following way: When we compare two nodes
$v_{p}$ and $v_{q}$ where $v_{p}$ is a neighbor of $v$ and $v_{q}$ is not,
then $v_{p}>v_{q}$ and if neither or both are neighbors of $v$, then
$v_{p}>v_{q}$ iff $p>q$. We can do these kinds of comparisons, since we know
that the comparison only needs to work for all numbers $\leq n-1$ in
$\mathbb{N}_{0}$ and we can thus create a polynomial that works like the sign
function for all these values. We then count (i.e. sum up) the number of
comparison victories for each node and use equality checks (again, for numbers
$\leq n-1$ in $\mathbb{N}_{0}$) to make sure the right vector is put in the
right place.

Afterwards all circuits $C^{(i)}_{j}$ from the circuit family
$\mathcal{C}^{(i)}$ for $j\in\\{1,\dots,n\\}$ are simulated in parallel. Since
the circuits $C^{(i)}_{j}$ are tail-symmetric, it does not matter that we
changed the order of the vectors. Moreover since at most $k+1$ vectors are
nonzero after we zeroed the non-neighbors, they are in the first $k+1$ vectors
in our new ordering. Each of these simulations is followed by an equality
check on $j$ and $k+1$. The sum is then formed over these which ensures that
only the results of the circuit simulation for the correct number of neighbors
of $v$ is considered further.

We repeat the described computations for all nodes $v\in V$ for every layer
$0\leq i\leq d$, using the resulting feature vectors from the computations
before as input to the following ones. Now we have the following:

  * •

The circuit $K$ has constant depth.

  * •

The computations for one layer are done in parallel for every node.

  * •

The number of layers is a constant given by the C-GNN.

  * •

As $\mathcal{N}$ is a
$(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}],\\{\mathrm{id}\\})$-GNN the
simulation of its circuit families are also
$t\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}]$-circuit families.

  * •

The family of subcircuit described in Lemma A.1 is also an
$\mathrm{FAC}^{0}_{\mathbb{R}^{k}}$-circuit family.

Therefore $\mathcal{K}$ is an
$\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}]$-circuit family. ∎

$\langle M\rangle$$\overline{v}_{1}^{(1)}$$\dots$$\overline{v}_{n}^{(1)}$
determine neighborhood relations simulate the correct circuit from
$\mathcal{C}^{(1)}$
$C^{(1)}_{k}$$\overline{v}_{1}^{(2)}$$\overline{v}_{1}^{(1)}$$\overline{u}_{1}^{(1)}$$\overline{u}_{k}^{(1)}$$\dots$
Figure 3: Proof of Theorem 3.6†, where $\overline{v}_{i}$ are the feature
vectors of the C-GNN, $\overline{u}_{j}$ the feature vectors of the neighbors
of a node.

Other types of C-GNNs, mainly
$(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}},\\{\mathrm{id}\\}\cup\mathcal{A})$-GNNs
and $(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}},\\{\mathrm{id}\\})$-GNNs are also
introduced in this paper. Restricting Theorem 3.6† to
$(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}],\\{\mathrm{id}\\})$-GNNs is
not a restraint on generality as the following corollary shows.

######  Corollary A.2.

Let $\mathcal{A}$ be a set of activation functions. Then
$\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}]$-circuit families can simulate
$(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}},\\{\mathrm{id}\\}\cup\mathcal{A})$-GNNs
and $(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}},\\{\mathrm{id}\\})$-GNNs in the sense
of Theorem 3.6†.

###### Proof.

As $(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}}[\mathcal{A}],\\{\mathrm{id}\\})$-GNNs
have access to the functions in $\mathcal{A}$ at any point during the
computations in a layer they are less restricted than
$(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}},\\{\mathrm{id}\\}\cup\mathcal{A})$-GNNs
and $(t\mathrm{FAC}^{0}_{\mathbb{R}^{k}},\\{\mathrm{id}\\})$-GNNs, since those
can either only apply the functions from $\mathcal{A}$ as activation functions
to all nodes at the end of a layers computation or do not have access to them
at all. This is especially relevant for functions which cannot be computed by
$t\mathrm{FAC}^{0}_{\mathbb{R}^{k}}$-circuit families. ∎

###  A.3 Proofs of Section 3.3

The complete proofs of Section 3.3 make use of the following lemma which
allows us to distinguish individual vectors from a finite subset of
$\mathbb{R}^{k}$ while still following our desired complexity constraints.

######  Lemma A.3.

Let $A\subseteq\mathbb{R}^{k}$ be finite and let $\overline{a}\in A$. Then the
function $\chi_{A,\overline{a}}\colon A\to\\{\overline{0},\overline{1}\\}$
defined as

$\chi_{A,\overline{a}}(\overline{x})\coloneqq\begin{cases}\overline{1},\textnormal{
if $\overline{x}=\overline{a}$}\\\ \overline{0},\textnormal{
otherwise}\end{cases}$

where $\overline{1}$ is the $k$-dimensional vector of ones, respectively
$\overline{0}$ the $k$-dimensional vector of zeros, is computable by a
$\mathbb{R}^{k}$ circuit whose size only depends on $\lvert A\rvert$ and whose
depth is constant.

###### Proof.

Let
$A=\\{\overline{a},\overline{a}_{1},\dots,\overline{a}_{\ell}\\}\subseteq\mathbb{R}^{k}$
be a finite set and let the univariate polynomial $p_{A,\overline{a}}\colon
A\to\mathbb{R}^{k}$ be defined as follows:

$p_{A,\overline{a}}(\overline{x})\coloneqq\left(\prod_{1\leq
i\leq\ell}(\overline{a}_{i}-\overline{x})\right)\cdot\frac{\overline{1}}{\prod_{1\leq
i\leq\ell}(\overline{a}_{i}-\overline{a})},$

where all operations are applied componentwise. Now, for every element $e\in
A\setminus\\{\overline{a}\\}$, $p_{A,\overline{a}}(e)$ yields $\overline{0}$,
since one factor in the left multiplication will be $\overline{0}$. On the
other hand, $p_{A,\overline{a}}(\overline{a})$ evaluates to $\overline{1}$,
since the left product yields exactly $\prod_{1\leq
i\leq\ell}(\overline{a_{i}}-\overline{a})$, which is what it gets divided by
on the right. Thus, $p_{A,\overline{a}}=\chi_{A,\overline{a}}$, and since for
any given $A$ and $\overline{a}\in A$, $p_{A,\overline{a}}$ is a polynomial of
constant degree, it can be evaluated by a circuit of constant depth and
polynomial size in $\lvert A\rvert$. ∎

######  Definition A.4.

Let $C$ be a circuit of an $\mathrm{FAC}^{0}_{\mathbb{R}^{k}}$-circuit family
with $n$ inputs, $m$ outputs and numbered gates via an injective function
$nr\colon V_{C}\rightarrow\mathbb{R}$ such that for all gates $g,g^{\prime}$
of $C_{n}$: $0pt(g)<0pt(g^{\prime})\implies nr(g)<nr(g^{\prime})$. Let $C$
also be in path-length-normal form and let
$\overline{x}\in\left(\mathbb{R}^{k}\right)^{n}$ be a tuple of vectors, the
input of the circuit.

Then $\mathfrak{G}_{{C},\overline{x}}$ is the labeled graph
$(G_{C},g_{V_{C}})$, where $G_{C}=(V_{C},E_{C})$ is the underlying graph of
the circuit and the function $g_{V_{C}}$ 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.

We now proceed to prove the theorems of Section 3.3 in depth.

As mentioned in the main paper our proofs of this section are formulated using
$\mathbb{R}$ circuits. This technically results in our C-GNNs having feature
vectors of dimension 1, i. e. vectors in $\mathbb{R}^{1}$. For simplicity
reasons and because we also stated that $\mathbb{R}$ circuits and
$\mathbb{R}^{1}$ circuits are equivalent we use real numbers, still called
feature vectors, instead.

######  Theorem 3.11†.

Let $\mathcal{C}=(C_{n})_{n\in\mathbb{N}}$ be an
$\mathrm{FAC}^{0}_{\mathbb{R}}$-circuit family. Then there exists a
$(t\mathrm{FAC}^{0}_{\mathbb{R}},\\{\mathrm{id}\\})$-GNN $\mathcal{N}$, such
that for all $n\in\mathbb{N}$ and $\overline{x}\in\mathbb{R}^{n}$, the feature
vectors of the nodes of $f_{\mathcal{N}}(\mathfrak{G}_{{C_{n}},\overline{x}})$
corresponding to output gates in $C_{n}$ are exactly the components of
$f_{C_{n}}(\overline{x})$. The number of layers in $\mathcal{N}$ is equal to
the depth of $\mathcal{C}$.

###### Proof.

Without loss of generality let all circuits of $\mathcal{C}$ be in path-length
normal form and let the gates in the circuits $C_{n}$ of $\mathcal{C}$ be
numbered via the injective function $nr\colon V_{C_{n}}\rightarrow\mathbb{R}$
specified in Definition A.4.

We then define $\mathcal{N}$ as follows: Let $d$ be the depth of the circuits
in $\mathcal{C}$. $\mathcal{N}$ has $d$ layers and maps each number in $[d]$
to a circuit family $\mathcal{C}^{(i)}_{\mathcal{N}}$, i.e. it assigns a
circuit family to every layer $i$. Since each node $v_{g}$ in the given
labeled graph $\mathfrak{G}_{{C_{n}},\overline{x}}$ represents a gate $g$ in
the underlying circuit $C_{n}$, each of the circuit families
$\mathcal{C}^{(i)}_{\mathcal{N}}$ of the C-GNN essentially make use of local
neighborhood information in the graph of $C_{n}$. The circuit family
$\mathcal{C}^{(i)}_{\mathcal{N}}$ uses the gate numbers in the gate numbering
of $C_{n}$, the depth and gate type of the respective gates and the number of
the unique successor of each gate.

Let $v_{g}^{(i)}$ denote the feature vector of node $v_{g}$ in layer $i$. As
per the definition of $\mathfrak{G}_{{C_{n}},\overline{x}}$, the feature
vector of each node in $\mathfrak{G}_{{C_{n}},\overline{x}}$ is initialized
with the gate number of the gate in $C_{n}$ it represents, and the nodes
representing input gates are initialized with the respective input values of
$\overline{x}$. In each layer $i$, the respective circuit of
$\mathcal{C}^{(i)}_{\mathcal{N}}$ determines whether to perform a computation
or just keep the feature vector as is. The circuit gets the previous feature
vector $v_{g}^{(i-1)}$ of the node as one of its inputs. It then checks
whether $v_{g}^{(i-1)}$ is among the gate numbers of gates with depth $i$ in
$C_{n}$. This is done in the following way: Let $Y^{(i)}$ be the set of all
gate numbers for gates in $C_{n}$ that have depth $i$. Now
$\mathcal{C}^{(i)}_{\mathcal{N}}$ simply computes
$\chi_{Y^{(i)},y}\left(v_{g}^{(i-1)}\right)$ for each $y\in Y^{(i)}$ (see
Lemma A.3) to check if $v_{g}^{(i-1)}$ is the number of a gate at depth $i$.
If that is not the case, then the gate $g$ with $nr(g)=y$ is not at depth $i$
and should not be evaluated in layer $i$ and $\mathcal{C}^{(i)}_{\mathcal{N}}$
keeps its feature vector as is, i.e., outputs the one it was given as its
input. Otherwise, $\mathcal{C}^{(i)}_{\mathcal{N}}$ computes the respective
function of $g$ in the following way: $\mathcal{C}^{(i)}_{\mathcal{N}}$
computes $\chi_{X_{\textit{op}},y}\left(v_{g}^{(i-1)}\right)$ for
$\textit{op}\in\\{+,\times,out\\}$, where $X_{\textit{op}}$ contains the gate
numbers of op-gates in $C_{n}$, to determine which function it needs to
evaluate. If $\textit{op}=+$, then $\mathcal{C}^{(i)}_{\mathcal{N}}$ computes
the sum of all the feature vectors in the neighborhood of $v_{g}$.

Since the neighborhood of each node in $\mathfrak{G}_{{C_{n}},\overline{x}}$
contains not only the predecessors of the node, but also the successor of the
node, this value still needs to be removed from the aggregation. This is
achieved by figuring out which node is the successor of $v_{g}$ using the gate
number of the gate corresponding to $v_{g}$. We extract this information from
the circuit $C_{n}$ when constructing the C-GNN circuits and use it in the
manner of a lookup table. For every $y\in Y^{(i)}$ we check whether
$v_{g}^{(i-1)}=y$, using the $\chi$ function from Lemma A.3, and if true
subtract the gate number we saved for $y$, which is $nr(w)$ where $w$ is the
successor of $v_{g}$. $\mathcal{C}^{(i)}_{\mathcal{N}}$ proceeds analogously
for nodes corresponding to $\times$ gates. For nodes corresponding to output
gates $\mathcal{C}^{(i)}_{\mathcal{N}}$ computes the sum over the single
neighbor. As all input circuits to the C-GNN are in path length normal form it
is ensured that nodes corresponding to output gates are only evaluated in the
last layer of the C-GNN. The complete functionality of
$\mathcal{C}^{(i)}_{\mathcal{N}}$ for each layer $i$ is described by Algorithm
1. By Lemma A.3 we know that for any finite set $A$ and any $a\in A$,
$\chi_{A,a}$ can be evaluated with a circuit whose size only depends on
$\lvert A\rvert$ and whose depth is constant. Since we only need to evaluate
polynomially many such functions and we can compute them in parallel, the
circuit family we outline here is still an
$\mathrm{FAC}^{0}_{\mathbb{R}}$-circuit family.

For example a node corresponding to a $+$ gate with number $5$ at depth 2,
which knows that the gate its successor has number $9$, will sum up all of its
neighbors values and subtract $9$ in the second layer of the C-GNN. See Figure
7 for visualisation. The only activation function used in each C-GNN layer is
the identity function. ∎

Algorithm 1 Proof Theorem 3.11†: algorithm for the circuit family in layer $i$
of the C-GNN

Input: $v_{g}^{(i-1)}$, $U_{g}=\\{u^{(i-1)}\mid u\in\mathcal{N}_{G}(v_{g})\\}$

$Y^{(i)}=\\{nr(g)\mid 0pt(g)=i\\}$ {The set of numbers of gates that need to
be evaluated in this layer}

$X_{+}=\\{nr(g)\mid g\text{ is + gate}\\}$

$X_{\times}=\\{nr(g)\mid g\text{ is }\times\text{ gate}\\}$

$X_{out}=\\{nr(g)\mid g\text{ is }out\text{ gate}\\}$

if $v_{g}^{(i-1)}\in Y^{(i)}$ then {If a node needs to be evaluated in this
layer}

if $v_{g}^{(i-1)}\in X_{+}$ then {If $v_{g}$ corresponds to an addition gate}

$v_{g}^{(i)}=\sum U_{g}-nr\left(suc\left(v_{g}\right)\right)$

else if $v_{g}^{(i-1)}\in X_{\times}$ then {If $v_{g}$ corresponds to a
multiplication gate}

$v_{g}^{(i)}=\prod U_{g}/nr\left(suc\left(v_{g}\right)\right)$

else {If $v_{g}$ corresponds to an output gate}

$v_{g}^{(i)}=\sum U_{g}$

end if

else {If $v_{g}$ does not correspond to a gate at depth $i$}

$v_{g}^{(i)}=v_{g}^{(i-1)}$

end if

$+$$nr\left(g_{+}\right)=5$$z$$nr\left(g_{z}\right)=9$$x$$y$depth 2depth
3depth 1$\vdots$$3$$7$ (a) Initial circuit

$v_{g_{+}}$$v_{g_{+}}^{(1)}=5$$v_{g_{z}}$$v_{g_{z}}^{(1)}=9$$v_{g_{x}}$$v_{g_{x}}^{(1)}=3$$v_{g_{y}}$$v_{g_{y}}^{(1)}=7$$\vdots$$\vdots$$\vdots$
(b) Feature graph with feature vectors

(c) Before the computation of the layer of the C-GNN

$+$$nr\left(g_{+}\right)=5$$z$$nr\left(g_{z}\right)=9$$x$$y$depth 2depth
3depth 1$\vdots$$3$$7$ (d) Initial circuit

$v_{g_{+}}$$v_{g_{+}}^{(2)}=10$$v_{g_{z}}$$v_{g_{z}}^{(2)}=9$$v_{g_{x}}$$v_{g_{y}}$$\vdots$$\vdots$$\vdots$
(e) Feature graph with feature vectors

(f) After the computation of the layer of the C-GNN

Figure 5: Example in the proof of Theorem 3.11† 777For readability purposes
the one-dimensional vectors in the C-GNN are written as real numbers.

######  Theorem 3.12†.

Let $\mathcal{C}=(C_{n})_{n\in\mathbb{N}}$ be an
$\mathrm{FAC}^{0}_{\mathbb{R}}[\mathcal{A}]$-circuit family. Then there exists
a $(t\mathrm{FAC}^{0}_{\mathbb{R}}[\mathcal{A}],\\{\mathrm{id}\\})$-GNN
$\mathcal{N}$, such that for all $n\in\mathbb{N}$ and
$\overline{x}\in\mathbb{R}^{n}$, the feature vectors of the nodes of
$f_{\mathcal{N}}\left(\mathfrak{G}_{{C_{n}},\overline{x}}\right)$
corresponding to output gates in $C_{n}$ are exactly the components of
$f_{C_{n}}(\overline{x})$. The number of layers in $\mathcal{N}$ is equal to
the depth of $\mathcal{C}$.

###### Proof.

This proof follows the same ideas as the proof of Theorem 3.11† but includes
the occurrence of gates computing functions besides + and $\times$ in the
circuit family $\mathcal{C}$ as well as in the circuit families
$\mathcal{C}^{(i)}_{\mathcal{N}}$ used in the C-GNN.

Without loss of generality let all circuits of $\mathcal{C}$ be in path-length
normal form and let the gates in the circuits $C_{n}$ of $\mathcal{C}$ be
numbered via an injective function as described in Definition A.4. We will use
$nr(C_{n})$ to denote the set of all gate numbers in the circuit $C_{n}$.

We now define $\mathcal{N}$ as follows: For every circuit in all circuit
families $\mathcal{C}^{(i)}_{\mathcal{N}}$, we initialize all nodes with their
respective gate number or input value as described in the proof of Theorem
3.11†. The sets $Y^{(i)}$ for all layers $i$ of the $\mathcal{C}$-GNN and the
sets $X_{+}$, $X_{\times}$ and $X_{\textit{out}}$ are defined the same as
well. Additionally, we now need sets $X_{\sigma}$ for every function
$\sigma\in\mathcal{A}$, such that $X_{\sigma}$ contains all gate numbers of
gates computing $\sigma$ in $C_{n}$. All these sets are finite, since they are
all subsets of $nr(C_{n})$ which is the set of gate numbers of $C_{n}$.

The idea is to handle the nodes corresponding to $\sigma$-gates in the same
way as the other nodes – for every node $v_{g}$ we check if it is to be
evaluated in this layer, i.e. the depth of gate $g$ in $C_{n}$ equals the
current layer $i$, by checking whether $v_{g}^{(i-1)}\in Y^{(i)}$ and if so,
assess of which type $g$ is by checking $v_{g}^{(i-1)}$ for inclusion in a set
$X_{\textit{op}}$ where
$\textit{op}\in\\{+,\times,\textit{out}\\}\cup\mathcal{A}$. We do this as in
the proof of Theorem 3.11† by computing
$\chi_{X_{\textit{op}},x}\left(v_{g}^{(i-1)}\right)$ for all $X_{\textit{op}}$
and all $x\in X_{\textit{op}}$.

If we determined that a gate $g$ corresponding to the node $v_{g}$ computes a
function $\sigma\in\mathcal{A}$, we compute the function on the feature vector
of the node corresponding to its predecessor in $C_{n}$. Since all
$\sigma\in\mathcal{A}$ are unary functions, $g$ has only one predecessor and
given that $C_{n}$ is in path-length normal form, it also has only one
successor. Let $u$ be the predecessor and $w$ be the successor of $v_{g}$. We
compute $v_{g}^{(i)}=\sigma\left(u^{(i-1)}\right)$ by summing up the feature
vectors of all neighbors of $v_{g}$ in $\mathfrak{G}_{{C_{n}},\overline{x}}$
and then determining the gate number of the gate corresponding to $w$ and
subtract this value from the sum as described in the proof of Theorem 3.11†.
This leaves us with the feature vector of the predecessor of $v_{g}$, since
$u^{(i-1)}+w^{(i-1)}-w^{(i-1)}=u^{(i-1)}$. Then $\sigma$ is applied to
$u^{(i-1)}$ using an $\sigma$-gate and $v_{g}^{(i)}$ is set to this value.

For all nodes $v_{h}$ which do not represent gates which have depth $i$ in
$C_{n}$, the new feature vector $v_{h}^{(i)}$ equals $v_{h}^{(i-1)}.$

All layers of $\mathcal{N}$ use the identity as their activation function. ∎

######  Theorem 3.17†.

Let $\mathcal{A}$ be a set of countably injective activation functions and let
$\mathcal{C}=(C_{n})_{n\in\mathbb{N}}$ be an
$f\mathrm{FAC}^{0}_{\mathbb{R}}[\mathcal{A}]$-circuit family. Then there
exists a
$(t\mathrm{FAC}^{0}_{\mathbb{R}},\mathcal{A}\cup\\{\mathrm{id}\\})$-GNN
$\mathcal{N}$, such that for all $n\in\mathbb{N}$ and
$\overline{x}\in(\mathbb{R})^{n}$, the feature vectors of the nodes of
$f_{\mathcal{N}}\left(\mathfrak{G}_{{C_{n}},\overline{x}}\right)$
corresponding to output gates in $C_{n}$ are exactly the components of
$f_{C_{n}}(\overline{x})$. The number of layers in $\mathcal{N}$ is equal to
the depth of $\mathcal{C}$.

###### Proof.

We again reuse the basic concept of the proof of Theorem 3.11† but adapt it
for function gates. Unlike in Theorem 3.12†, the circuit families of our
$(t\mathrm{FAC}^{0}_{\mathbb{R}},\mathcal{A}\cup\\{\mathrm{id}\\})$-GNN do not
have arbitrary access to functions in $\mathcal{A}$ and thus cannot decide for
each individual node, whether to apply an activation or not. We can only apply
it to all of our nodes’ feature vectors, or to none of them.

Let $\sigma\in\mathcal{A}$ be countably injective on a set
$S\subseteq\mathbb{R}$ and let the gates in $C_{n}$ be numbered as described
in Definition A.4 by values from $S$. Let $i\in\mathbb{N}$ be such that all
gates at depth $i$ in $C_{n}$ are $\sigma$-gates. Since $C_{n}$ is in
function-layer form, if any gate at depth $i$ is a $\sigma$-gate, then all
gates at depth $i$ are. The circuit family $\mathcal{C}_{\mathcal{N}}^{(i)}$
used for each node in layer $i$ in $\mathcal{N}$ then first checks whether its
previous feature vector $v_{g}^{(i-1)}$ corresponds to a gate number of a gate
$g$ in layer $i$ by querying $v_{g}^{(i-1)}\in Y^{(i)}$ using
$\chi_{Y^{(i)},y}\left(v_{g}^{(i-1)}\right)$, where $Y^{(i)}$ is the set of
all gate numbers for gates in $C_{n}$ that have depth $i$, as introduced
before.

If $v_{g}^{(i-1)}\in Y^{(i)}$, then $\mathcal{C}_{\mathcal{N}}^{(i)}$ proceeds
as in the case for addition gates in Algorithm 1, summing over its neighbors
and removing the value of its successor. This way, after the activation
function is applied, $v_{g}^{(i)}=\sigma\left(v_{g}^{(i-1)}\right)$, the
intended value after layer $i$ in $\mathcal{N}$.

If $v_{g}^{(i-1)}\notin Y^{(i)}$, we need to make sure that after the
application of $\sigma$ as an activation function, $v_{g}^{(i)}$ is still the
gate number of its corresponding gate $g$ in $C_{n}$. For this purpose,
$\mathcal{C}_{\mathcal{N}}^{(i)}$ determines and outputs
$\sigma^{-1}\left(v_{g}^{(i-1)}\right)$, so that after applying the activation
function,
$v_{g}^{(i)}=\sigma\left(\sigma^{-1}\left(v_{g}^{(i-1)}\right)\right)=v_{g}^{(i-1)}$.
The inverse $\sigma^{-1}\left(v_{g}^{(i-1)}\right)$ exists, because $\sigma$
is countably injective in the set of gate numbers of $C_{n}$. The circuit
family $\mathcal{C}_{\mathcal{N}}^{(i)}$ sets its output to
$\sigma^{-1}\left(v_{g}^{(i-1)}\right)$ by computing
$\sum_{v\in\textit{nr}(C_{n})}\sigma^{-1}(v)\cdot\chi_{S,v}\left(v_{g}^{(i-1)}\right)$,
where $\textit{nr}(C_{n})$ is the set of gate numbers of $C_{n}$. This works
for all gates at depths $>i$. Gates at depths $<i$ do not have an influence on
the output of the computation anymore, and what happens to them is thus of no
importance.

The procedure performed by $\mathcal{C}_{\mathcal{N}}^{(i)}$ is outlined in
Algorithm 2.

The preceding procedure requires that all functions in $\mathcal{A}$ are
countably injective in the same set. If they are not countably injective in
the same set, we modify the construction by using a new gate numbering of
$C_{n}$ for each function layer, assigning new values to the feature vectors
before the activation function is used. All sets of numbers of specific gates,
e.g. numbers of addition gates are updated accordingly.

Algorithm 2 Proof Theorem 3.17†: algorithm for the circuit in layer $i$ of the
C-GNN if layer $i$ evaluates function gates

Input: $v_{g}^{(i-1)}$, $U_{g}=\\{u^{(i-1)}\mid u\in\mathcal{N}_{G}(v_{g})\\}$

$Y^{(i)}=\\{nr(g)\mid 0pt(g)=i\\}$ {The set of numbers of gates that need to
be evaluated in this layer}

$X_{+}=\\{nr(g)\mid g\text{ is $+$ gate}\\}$

$X_{\times}=\\{nr(g)\mid g\text{ is }\times\text{ gate}\\}$

$X_{out}=\\{nr(g)\mid g\text{ is }\textit{out}\text{ gate}\\}$

if $v_{g}^{(i-1)}\in Y^{(i)}$ then {If a node needs to be evaluated in this
layer}

if $v_{g}^{(i-1)}\in X_{+}$ then {If $v_{g}$ corresponds to addition gate}

$v_{g}^{(i)}=\sum U_{g}-nr\left(suc\left(v_{g}\right)\right)$

else if $v_{g}^{(i-1)}\in\sigma\left(X_{\times}\right)$ then {If $v_{g}$
corresponds to multiplication gate}

$v_{g}^{(i)}=\prod U_{g}/nr\left(suc\left(v_{g}\right)\right)$

else {If $v_{g}$ corresponds to output gate}

$v_{g}^{(i)}=\sum U_{g}$

end if

else {If $v_{g}$ does not correspond to a gate at depth $i$}

$v_{g}^{(i)}=\sigma^{-1}\left(v_{g}^{(i-1)}\right)$

end if

∎