# Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limit

arXiv: https://arxiv.org/abs/2505.00291 · HTML: https://mlsanity.com/paper/2505.00291/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 38 references that are in the map.
- First posted on arXiv 1 May 2025.

## Builds on (most cited first, 14 of 14)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction](https://mlsanity.com/paper/2208.10227/) (2022)
- [Some Might Say All You Need Is Sum](https://mlsanity.com/paper/2302.11603/) (2023)
- [Distinguished In Uniform: Self Attention Vs. Virtual Nodes](https://mlsanity.com/paper/2405.11951/) (2024)
- [Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats](https://mlsanity.com/paper/2405.14606/) (2024)
- [Graphs Identified by Logics with Counting](https://mlsanity.com/paper/1503.08792/) (2015)
- [On dimensionality of feature vectors in MPNNs](https://mlsanity.com/paper/2402.03966/) (2024)

## Built on by (most cited first, 4 of 4)

- [On Halting vs Converging in Recurrent Graph Neural Networks](https://mlsanity.com/paper/2604.25551/) (2026)
- [Recurrent Graph Neural Networks with Set-Based Aggregation](https://mlsanity.com/paper/2609.15932/) (2026)
- [The Expressive Power of Random-Feature MPNNs Across Graph Sizes](https://mlsanity.com/paper/2610.12809/) (2026)
- [Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's Conjecture](https://mlsanity.com/paper/2610.16993/) (2026)

## Abstract (arXiv)

We precisely characterize the expressivity of computable Recurrent Graph Neural Networks (recurrent GNNs). We prove that recurrent GNNs with finite-precision parameters, sum aggregation, and ReLU activation, can compute any graph algorithm that respects the natural message-passing invariance induced by the Color Refinement (or Weisfeiler-Leman) algorithm. While it is well known that the expressive power of GNNs is limited by this invariance [Morris et al., AAAI 2019; Xu et al., ICLR 2019], we establish that recurrent GNNs can actually match this limit. This is in contrast to non-recurrent GNNs, which have the power of Weisfeiler-Leman only in a very weak, "non-uniform", sense where each graph size requires a different GNN to compute with. Our construction introduces only a polynomial overhead in both time and space. Furthermore, we show that by incorporating random initialization, for connected graphs recurrent GNNs can express all graph algorithms. In particular, any polynomial-time graph algorithm can be emulated on connected graphs in polynomial time by a recurrent GNN with random initialization.