EUVIMEDEUVIMED entdecken
Crossref

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

Eran Rosenbluth, Martin Grohe

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (30) · 25168-25175

DOI: 10.1609/aaai.v40i30.39707 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Eran Rosenbluth und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Rosenbluth, E., & Grohe, M. (2026). Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message Passing Limit. Proceedings of the AAAI Conference on Artificial Intelligence, 40(30), 25168-25175. https://doi.org/10.1609/aaai.v40i30.39707

Vancouver

Rosenbluth E, Grohe M. Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message Passing Limit. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(30):25168-25175. doi:10.1609/aaai.v40i30.39707

BibTeX
@article{Rosenbluth2026,
  author = {Rosenbluth, Eran and Grohe, Martin},
  title = {Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message Passing Limit},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {30},
  pages = {25168--25175},
  doi = {10.1609/aaai.v40i30.39707}
}
Kostenlos starten →