Recurrent Graph Neural Networks and Arithmetic Circuits

Heribert Vollmer; Jonni Virtema; Laura Strieker; Timon Barlag; Vivian Holzapfel

arxiv: 2603.05140 · v2 · submitted 2026-03-05 · 💻 cs.CC · cs.AI· cs.LG

Recurrent Graph Neural Networks and Arithmetic Circuits

Timon Barlag , Vivian Holzapfel , Laura Strieker , Jonni Virtema , Heribert Vollmer This is my paper

Pith reviewed 2026-05-15 15:32 UTC · model grok-4.3

classification 💻 cs.CC cs.AIcs.LG

keywords recurrent graph neural networksarithmetic circuitsexpressivitycomputational powermemory gateslabelled graphsreal numbers

0 comments

The pith

Recurrent graph neural networks match the expressivity of recurrent arithmetic circuits over real numbers.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves an exact two-way correspondence: any function computed by a recurrent GNN on labelled graphs can be computed by a recurrent arithmetic circuit on the same graphs encoded as real tuples, and conversely any circuit function can be realized by a suitably constructed recurrent GNN. The circuits use memory gates to retain values across iterations, mirroring how recurrent networks propagate information step by step. The constructions are direct and preserve exact real-valued outputs without approximation. This equivalence lets circuit-theoretic tools analyze what recurrent GNNs can and cannot learn. Readers should care because it supplies a concrete bridge between practical neural architectures and classical models of computation, clarifying the precise computational limits of trained GNNs.

Core claim

We establish an exact correspondence between the expressivity of recurrent GNNs and recurrent arithmetic circuits operating over real numbers. Recurrent arithmetic circuits are introduced as arithmetic analogues of sequential circuits that employ memory gates to store data between iterations. For any recurrent GNN, an arithmetic circuit is built that receives the labelled graph encoded as a real-valued tuple and produces the identical output. Conversely, for any recurrent arithmetic circuit, a recurrent GNN is constructed that receives the circuit input as initial node features and extracts the circuit output among its final node features after the message-passing rounds.

What carries the argument

Recurrent arithmetic circuits equipped with memory gates that process real-valued encodings of labelled graphs and simulate GNN message-passing rounds.

Load-bearing premise

Labelled graphs can be faithfully encoded as real-valued tuples so that GNN message-passing exactly reproduces the arithmetic operations and memory gates of the circuit without precision loss.

What would settle it

Exhibit one concrete labelled-graph function that a recurrent GNN computes exactly but no recurrent arithmetic circuit can compute on the corresponding real encoding, or the reverse.

read the original 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. 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives an exact equivalence between recurrent GNNs and a new recurrent arithmetic circuit model with memory gates.

read the letter

This paper shows that recurrent GNNs match the power of recurrent arithmetic circuits over the reals through explicit constructions both ways. The new circuit model adds memory gates to handle state across iterations, which lets them capture the recurrent behavior without restricting to specific GNN types like aggregate-combine networks. They encode labeled graphs as real tuples for the circuits and build GNNs that simulate the circuits by placing inputs in initial features and reading outputs from node features at the end. That bidirectional mapping is the main result and it generalizes earlier links between GNNs and circuits. The approach looks clean on paper because the constructions are direct rather than relying on limits or approximations. One soft spot is the encoding step: turning arbitrary labeled graphs into real-valued tuples has to carry all structural and label information exactly, and any slip in how edges or features are represented could break the correspondence in practice even if the math holds. The constructed GNNs also seem tailored to the simulation, so they may not tell us much about standard trained models. This work is mainly for researchers who already care about expressivity bounds in GNNs or who want to import circuit complexity tools into neural network analysis. It deserves peer review because the central claim rests on concrete mappings rather than loose analogies, and the abstract gives enough structure to make the result checkable.

Referee Report

0 major / 2 minor

Summary. The manuscript claims to establish an exact correspondence between the expressivity of recurrent graph neural networks (GNNs) and recurrent arithmetic circuits over real numbers. It introduces recurrent arithmetic circuits with memory gates and provides bidirectional constructions: arithmetic circuits that compute the same functions as recurrent GNNs on encoded labelled graphs represented as real-valued tuples, and recurrent GNNs that simulate the circuits by taking circuit inputs as initial node features and producing circuit outputs among the node features after message passing.

Significance. If the bidirectional constructions hold, the result provides a precise characterization of recurrent GNN computational power in terms of arithmetic circuit complexity over the reals. This strengthens the theoretical toolkit for analyzing GNN expressivity and enables transfer of techniques from circuit complexity to neural network models, particularly for recurrent settings.

minor comments (2)

[Abstract] Abstract: the phrase 'generalising similar notions from the literature' would be strengthened by citing one or two specific prior works on arithmetic circuits or GNN expressivity bounds.
The weakest assumption noted in the model (faithful encoding of labelled graphs as real-valued tuples without precision loss) is stated but could be expanded with a brief remark on the chosen encoding scheme in the main text.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our manuscript and for recommending acceptance. The referee's summary correctly captures the bidirectional constructions establishing the exact correspondence between the expressivity of recurrent GNNs and recurrent arithmetic circuits with memory gates over the reals.

Circularity Check

0 steps flagged

No significant circularity in bidirectional constructions

full rationale

The paper proves exact equivalence between recurrent GNN expressivity and recurrent arithmetic circuits via two independent, explicit constructions: one direction encodes labelled graphs as real tuples and simulates GNN message-passing inside arithmetic circuits with memory gates; the reverse direction initializes GNN node features from circuit inputs and extracts circuit outputs from final node features. These mappings are defined directly from the model semantics without self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The result is a standard theoretical equivalence proof that remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The claim rests on the new definition of recurrent arithmetic circuits and the assumption that graph inputs can be encoded as real tuples without loss of information.

axioms (1)

standard math Arithmetic operations over the real numbers are closed and well-defined for the circuit computations
The model operates over reals as stated in the abstract.

invented entities (1)

recurrent arithmetic circuits with memory gates no independent evidence
purpose: Model iterative computations with storage to match recurrent GNN behavior
New model introduced to establish the correspondence between GNNs and circuits.

pith-pipeline@v0.9.0 · 5521 in / 1107 out tokens · 31739 ms · 2026-05-15T15:32:28.511205+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/ArithmeticFromLogic.lean ArithmeticFromLogic.equivNat unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We establish an exact correspondence between the expressivity of recurrent GNNs and recurrent arithmetic circuits operating over real numbers... bidirectional constructions establishing exact equivalence between recurrent GNN expressivity and recurrent arithmetic circuits over reals, with memory gates handling iteration state.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.