mlsanityData to 14 Oct 2026

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

arXiv 2505.00291 ↗First posted 1 May 2025cs.LG cs.CCcited by 4

Not on the map. Why?

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.

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

14 of 38 references.

References · 14

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  3. 2015Gated Graph Sequence Neural Networkscited by 796
  4. 2017Residual Gated Graph ConvNetscited by 346
  5. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 200
  6. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  7. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  8. 2021The Logic of Graph Neural Networkscited by 85
  9. 2022One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfactioncited by 27
  10. 2023Some Might Say All You Need Is Sumcited by 21
  11. 2024Distinguished In Uniform: Self Attention Vs. Virtual Nodescited by 20
  12. 2024Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floatscited by 13
2 more
  1. 2015Graphs Identified by Logics with Countingcited by 11
  2. 2024On dimensionality of feature vectors in MPNNscited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026On Halting vs Converging in Recurrent Graph Neural Networkscited by 0
  2. 2026Recurrent Graph Neural Networks with Set-Based Aggregationcited by 0
  3. 2026The Expressive Power of Random-Feature MPNNs Across Graph Sizescited by 0
  4. 2026Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's Conjecturecited by 0