We characterise the computational power of recurrent graph neural networks (GNNs) in terms of arithmetic circuits over the real numbers. Our networks are not restricted to aggregate-combine GNNs or other particular types. Generalising similar notions from the literature, we introduce the model of recurrent arithmetic circuits, which can be seen as arithmetic analogues of sequential or logical circuits. These circuits utilise so-called memory gates which are used to store data between iterations of the recurrent circuit. While (recurrent) GNNs work on labelled graphs, we construct arithmetic circuits that obtain encoded labelled graphs as real valued tuples and then compute the same function. For the other direction we construct recurrent GNNs which are able to simulate the computations of recurrent circuits. These GNNs are given the circuit-input as initial feature vectors and then, after the GNN-computation, have the circuit-output among the feature vectors of its nodes. In this way we establish an exact correspondence between the expressivity of recurrent GNNs and recurrent arithmetic circuits operating over real numbers. Our results both deepen our understanding of the capabilities of trained neural networks and open new approaches to study recurrent neural networks using the lens of circuit complexity theory.
Figures & tables
Figure 1: Structure of a recurrent arithmetic circuit: ini are the input gates, auxi are the auxiliary memory gates, outi are the output gates and Vhalt the halting gates. Dashed edges are the recurrent edges of the set Erec . The halting function is not depicted.
Figure 2: Illustration of recurrent circuit rec-C with halting circuit Chalt computing the x1 -th Fibonacci number for 1<x1∈N . The dashed arrows mark the recurrent edges and the bold gate in1 is the single halting gate, i. e. the gate whose value forms the input for Chalt along with the iteration number i .
Figure 3: The different models of (recurrent) C-GNN s. One block stands for one layer of the different (recurrent) C-GNN models N , dashed edges mark recurrence
Figure 4: Assume the same circuit function classes for recurrence/ underlying circuit and the same set of activation functions, lines denote subclasses of computable functions
C-GNN with
Recurrent circuit
Outer recurrence
Inner recurrence
without sign
with sign
✓
✗
✓
✗
(Thm. 2 )
✗
✓
✗
✓
(Thm. 3 )
✓
✓
✗
✓
(Cor. 1 )
Table 1: Simulating Recurrent C-GNNs with Recurrent Circuits. One row in the table represents one result.
Recurrent circuit
Recurrent C-GNN
Outer recurrence
Inner recurrence
sign in internal circuits
Activation functions
local
global
no restrictions
✓
✗
✓
✓
✗
(Thm. 5 )
Predecessor Form
✓
✗
✗
✗
✓
(Thm. 4 )
Symmetric Functions
✗
✓
✗
✓
✗
(Thm. 6 )
Table 2: Simulating Recurrent Circuits with Recurrent C-GNN s. One row in the table represents one result.
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Circuit C= computing x1=x2 for inputs x1,x2 with depth 7 and size 16.
Figure 6: Circuit Cflag that computes the flag whether circuit rec- C has halted, dependent on the current iteration number i and the values of the halting gates val (Vhalt) .
Figure 7: Circuit Cin that sets the input y1′,…,ym′ to the second circuit correctly dependent on the flag t and given the output y1,…,ym of the first circuit
Figure 8: The circuit Caux_mem which ensures that the values of the auxiliary memory gates are not changed until the flag t is set
Figure 9: The construction of the composed circuit, dashed lines denote values from the respective predecessors, the dotted line denotes the connection from the halting gates
Figure 10: Schema of the recurrent circuit CnN where recurrent edges are dashed.
Figure 11: Depiction of switching gadget for layer ℓ . The inputs to this circuit are the outputs of the counting subcircuit (cnt) and of the subcircuits for each circuit family in N ( CN(ℓ) ). The gates labelled =ℓ are shorthand for the circuit computing equality with constant ℓ .
Figure 12: Proof of Corollary 1 : Circuit simulating a C-GNN with both methods of recurrence, ⟨G⟩ is the encoded input graph of the C-GNN , in the ordered vector of input values and out the ordered vector of output values, C(i) are the circuits that simulate each of the d layers of the C-GNN and Chalt(i) are the circuits computing the respective halting functions.
Figure 13: Circuit C on the left with halting circuit Chalt , encoded feature graph on the right. Teal dummy nodes have feature value 1, purple halting circuit representation, dummy nodes left out for halting circuit for better readability
Figure 14: The bipartite labelled graph G(Cn,x) . The nodes vi1,…,vin represent the inputs, vo1,…,vom represent the outputs, x=i1,…,in are the inputs to the circuit Cn .
Figure 15: Cn , the gate e computes the exponential function and is the halting gate
Recurrent GNNs iterate message passing to convergence, and their logical characterizations to date rely on multi-set aggregation, graded (counting) logics, and halting or acceptance conditions that cannot be verified from the network's parameters. We study recurrent GNNs with set-based aggregation and identify sufficient conditions checkable from the weights for networks to compile into formulas and formulas into networks. The main result is an effective, two-directional equivalence between a class of networks and the Boolean closure of reachability and safety properties, the fragment BΣ1∘ of the modal μ-calculus. The fragment is not an artifact: it is the exact expressive level of stabilization over finite vocabulary, which supports fixed points of a single polarity and Boolean combinations thereof, but not the composition of fixed points of opposite polarities. The correspondence needs no counting logic, no external halting signal, and no non-effective acceptance condition, yielding a verifiable path from weights to symbolic explanations for networks meeting the conditions.
What formal languages can a recurrent neural language model recognize? Formal results in the literature conflict: some authors report Turing-completeness, while others show equivalence to regular languages. The reason for this discrepancy is that the underlying arithmetic model differs. The paper develops a unified algebraic account of the expressivity of recurrent neural networks, starting with a formal account of various arithmetic models. This account reduces expressivity to an algebraic question, e.g., whether a network's syntactic monoid divides a certain wreath product. As a case study, the paper revisits diagonal state-space models: the same architecture cannot implement an even-modulus counter once floating-point recurrences are enforced, yet realizes every even-modulus counter under unsigned-integer quantization.
Understanding how the architecture of neural networks shapes the computations they carry is a central challenge in neuroscience and machine learning. While specific circuit architectures have been linked to particular network computations and theoretical bounds on expressivity of broad classes of networks have been found, we are still missing general principles connecting the structure of finite networks to their computational capabilities. Here, we characterize the computational abilities of recurrent neural networks as a function of their connectivity by training a large collection of different networks to compute a large set of Boolean functions. For small networks, we constructed the complete ``catalogs'' of network-function performance, which revealed that computational capacity varies widely across architectures and that most networks show poor performance, and most functions are hard to compute. However, we show that having local 2- and 3-cycles in a network strongly enhances its computational ability, and networks with such cycles are often the minimal architectures that can solve particular functions. We further show that a small set of structural statistics accurately predict networks' performance. Extending our analysis to large networks showed that typical networks fail even to approximate a randomly selected function. Surprisingly, adding a small number of sparsely connected biologically-inspired interneurons to the network dramatically increases computational capacity. As in small networks, adding short cycles improved networks' capacity, outperforming acyclic or reachability-matched controls. Thus, our results identify local cycles as design principles linking neural connectivity to computational power, and offer a general framework to explore structure-function relations in computing networks.
Tom Talpir, Elad Schneidman
Department of Brain Sciences, Weizmann Institute of Science, Rehovot, Israel