Search papers, labs, and topics across Lattice.
This paper establishes a formal equivalence between recurrent graph neural networks (GNNs) and recurrent arithmetic circuits over real numbers, offering a novel characterization of GNN computational power. The authors introduce recurrent arithmetic circuits with memory gates, analogous to sequential circuits, and demonstrate how these circuits can encode and process labeled graphs. By constructing GNNs that simulate recurrent circuit computations and vice versa, the paper proves an exact correspondence in expressivity between the two models.
Recurrent GNNs are shown to be exactly as expressive as recurrent arithmetic circuits over real numbers, providing a new theoretical foundation for understanding their computational limits.
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.
