Abstract
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. Generalizing 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.
Introduction
Understanding the theoretical expressive power of Graph Neural Networks (GNNs) is essential for identifying their computational limits. Most existing research evaluates GNNs by comparing them to Boolean logic frameworks, such as the Weisfeiler-Lehman (WL) test or first-order logic. However, GNNs naturally operate on real-valued feature vectors, making Boolean comparisons a poor fit that often requires complex approximations. Furthermore, while most theoretical results focus on fixed-depth GNNs, "recurrent" GNNs—which iterate until reaching a stable state or halting condition—have gained prominence for their ability to solve problems beyond the reach of fixed-depth networks. This paper bridges these gaps by establishing an exact correspondence between recurrent GNNs and a novel model: recurrent arithmetic circuits.
Recurrent Arithmetic Circuits
To capture the iterative nature of GNNs in a circuit-based framework, the authors introduce recurrent arithmetic circuits. Unlike traditional acyclic arithmetic circuits, this model incorporates two critical features: memory gates to store data between iterations and a halting function to determine when the computation is complete. This makes them an arithmetic analogue to the sequential logic circuits used in digital hardware.
The general architecture of these circuits involves feedback loops where outputs from one iteration become inputs for the next. As shown in the schematic below, the circuit $V_{\text{halt}}$ processes both primary inputs ($in_i$) and auxiliary memory states ($aux_j$) to produce outputs and update the memory for the subsequent step.
Bridging GNNs and Circuits
The equivalence between these models is established through two primary constructive simulations:
- GNN to Circuit: The authors demonstrate how to encode a labeled graph into a tuple of real numbers. A recurrent circuit can then process this tuple to produce the same result as the GNN, effectively "unrolling" the GNN's message-passing steps into circuit operations.
- Circuit to GNN: Conversely, the authors show how to build a GNN that simulates a circuit. A significant hurdle is that GNNs typically apply the same operation to every node (homogeneity). The authors overcome this by using node degrees as unique identifiers. By attaching "dummy nodes" to graph nodes, they ensure that a node's degree acts as an ID, allowing the GNN to perform the specific operation of a corresponding circuit gate at that node.
To facilitate this, the authors utilize Circuit-GNNs (C-GNNs), a generalized model where message passing is performed by any function computable by an arithmetic circuit, rather than being restricted to standard aggregate-combine steps.
Key Insights and Results
The core contribution of this work is the proof of an exact correspondence: for every recurrent C-GNN, there is an equivalent recurrent arithmetic circuit, and vice versa. This establishes that these two models are computationally identical over the real numbers.
Several key insights emerged from this derivation:
- The Power of Memory: Memory gates are the "aha moment" that allows static circuit structures to capture the iterative, stateful nature of recurrent GNNs.
- Tail-Symmetry: Because GNNs are permutation-invariant (they treat a node's neighbors as an unordered set), the corresponding arithmetic circuits must be "tail-symmetric." This mathematical constraint is essential for the equivalence to hold.
- Recurrence Hierarchy: The paper distinguishes between inner recurrence (where the message-passing function itself is a recurrent circuit within a fixed number of layers) and outer recurrence (where the entire GNN iterates). The authors prove that outer recurrence is strictly more powerful. For example, outer-recurrent GNNs can compute functions like $e^x$ that fixed-depth GNNs with inner recurrence cannot.
Conclusion and Future Work
By providing a precise characterization of recurrent GNNs via arithmetic circuits, this research moves GNN theory closer to the reality of real-valued computation. While the equivalence holds regardless of the specific halting condition—whether it be a fixed number of steps or reaching a fixed point—the proofs rely on certain circuit normal forms. Future work may explore whether these models remain comparable under stricter conditions like bisimulation, or how these theoretical bounds can inform the design of more efficient practical GNN architectures.
Summary updated