Recurrent Graph Neural Networks and Arithmetic Circuits

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

TL;DR

This paper establishes a formal equivalence between the computational power of recurrent Graph Neural Networks (GNNs) and a newly defined model called recurrent arithmetic circuits. By bridging these two frameworks, the authors provide a precise characterization of what iterative GNNs can compute over real-valued data, moving beyond traditional Boolean logic comparisons.

What Problem Does This Paper Address?

While GNNs are widely used, understanding their theoretical "expressive power"—what they can and cannot calculate—is a major challenge. Most existing research compares GNNs to Boolean logic (like first-order logic) or Boolean circuits (like $TC^0$). However, GNNs naturally operate on real numbers (feature vectors), making Boolean comparisons a poor fit that often requires complex "coding" or approximations.

Furthermore, most theoretical results focus on GNNs with a fixed number of layers. Recently, "recurrent" GNNs—which iterate until they reach a stable state or a specific halting condition—have gained popularity because they can solve problems that fixed-depth networks cannot. This paper seeks to provide an exact, real-valued computational model that matches the power of these recurrent GNNs.

Methods

The authors bridge the gap between GNNs and circuit complexity through several key innovations:

  1. Recurrent Arithmetic Circuits: The authors introduce an extension of standard arithmetic circuits. Unlike traditional acyclic circuits, these include memory gates (to store data between iterations) and a halting function (to decide when to stop). This makes them an arithmetic analogue to the sequential logic circuits used in digital hardware.
  2. Circuit-GNNs (C-GNNs): Instead of restricting GNNs to standard "aggregate-combine" steps (like simple sums and ReLUs), the authors use a generalized model where message passing is performed by any function computable by an arithmetic circuit.
  3. Constructive Simulations:
  4. GNN to Circuit: They show how to encode a labeled graph into a tuple of real numbers that a recurrent circuit can process to produce the same result as the GNN.
  5. Circuit to GNN: They demonstrate how to build a GNN that simulates a circuit. To do this, they use a clever trick: they attach "dummy nodes" to graph nodes so that a node's degree acts as a unique identifier, telling the GNN which specific circuit gate's operation to perform at that node.

Datasets

This is a theoretical computer science paper and does not use empirical datasets or benchmarks. The "inputs" discussed are abstract labeled graphs and real-valued tuples used for mathematical proofs.

Key Insights and Ideas

  • The Power of Memory: The introduction of "memory gates" is the "aha moment" that allows static arithmetic circuits to capture the iterative nature of recurrent GNNs.
  • Tail-Symmetry: Because GNNs are permutation-invariant (they don't care about the order of a node's neighbors), the corresponding arithmetic circuits must be "tail-symmetric." This mathematical constraint is essential for the equivalence to hold.
  • Inner vs. Outer Recurrence: The paper distinguishes between two types of recurrence:
  • Outer: The entire GNN iterates its layers.
  • Inner: The message-passing function itself is a recurrent circuit, but the GNN has a fixed number of layers.
  • Node Degree as an ID: One of the hardest parts of simulating a circuit with a GNN is that GNNs usually perform the same operation on every node. By using node degrees as "IDs," the authors show that a GNN can actually simulate highly heterogeneous circuit structures.

Key Results

  • Exact Correspondence: The paper proves that 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 reals.
  • Hierarchy of Power: The authors prove that outer recurrence is strictly more powerful than inner recurrence. For example, a GNN with outer recurrence can compute functions like the exponential function ($e^x$) that a GNN with only inner recurrence (and a fixed number of layers) cannot, provided the activation functions are restricted.
  • Halting Flexibility: The equivalence holds regardless of whether the halting condition is a fixed number of steps, reaching a fixed point (stabilization), or a condition depending on the graph size.

Limitations and Future Work

  • Normal Forms: The proofs rely on circuits being in "path-length normal form" or "predecessor form." While the authors show these forms don't technically limit power, they add structural constraints that might not reflect "natural" GNN designs.
  • Incomparability Conjecture: The authors conjecture that models with only inner recurrence and those with only outer recurrence might be "provably incomparable" under certain conditions (like bisimulation), suggesting a more complex hierarchy yet to be fully mapped.
  • Practical Architectures: While this work defines the limit of what is possible, it doesn't prescribe how to build the most efficient recurrent GNN for a specific task. Translating these theoretical bounds into practical architectural guidelines remains an open area for research.

Summary updated

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.
BibTeX
@inproceedings{barlag2026recurrent,
  author = {Timon Barlag and Vivian Holzapfel and Laura Strieker and Jonni Virtema and Heribert Vollmer},
  title = {{Recurrent Graph Neural Networks and Arithmetic Circuits}},
  booktitle = {KR},
  year = {2026},
  doi = {10.24963/kr.2026/78},
}

Loading related content...

Figure