# Recurrent Graph Neural Networks with Set-Based Aggregation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 38 references that are in the map.
- First posted on arXiv 14 Sep 2026.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [Implicit Graph Neural Networks](https://mlsanity.com/paper/2009.06211/) (2020)
- [A Generalist Neural Algorithmic Learner](https://mlsanity.com/paper/2209.11142/) (2022)
- [Graph Neural Networks are Dynamic Programmers](https://mlsanity.com/paper/2203.15544/) (2022)
- [Learning Graph Cellular Automata](https://mlsanity.com/paper/2110.14237/) (2021)
- [Logical Characterizations of GNNs with Mean Aggregation](https://mlsanity.com/paper/2507.18145/) (2025)
- [Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limit](https://mlsanity.com/paper/2505.00291/) (2025)
- [Which Algorithms Can Graph Neural Networks Learn?](https://mlsanity.com/paper/2602.13106/) (2026)
- [Tree algebras and bisimulation-invariant MSO on finite graphs](https://mlsanity.com/paper/2407.12677/) (2024)

## Abstract (arXiv)

Recurrent GNNs iterate message passing to convergence, and their logical characterizations to date rely on multi-set aggregation, graded (counting) logics, and halting or acceptance conditions that cannot be verified from the network's parameters. We study recurrent GNNs with set-based aggregation and identify sufficient conditions checkable from the weights for networks to compile into formulas and formulas into networks. The main result is an effective, two-directional equivalence between a class of networks and the Boolean closure of reachability and safety properties, the fragment BSigmacirc1 of the modal μ-calculus. The fragment is not an artifact: it is the exact expressive level of stabilization over finite vocabulary, which supports fixed points of a single polarity and Boolean combinations thereof, but not the composition of fixed points of opposite polarities. The correspondence needs no counting logic, no external halting signal, and no non-effective acceptance condition, yielding a verifiable path from weights to symbolic explanations for networks meeting the conditions.