# Graph neural networks and MSO

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 6 references that are in the map.
- First posted on arXiv 12 May 2025.

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

- [Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats](https://mlsanity.com/paper/2405.14606/) (2024)

## Abstract (arXiv)

We give an alternative proof for the existing result that recurrent graph neural networks working with reals have the same expressive power in restriction to monadic second-order logic MSO as the graded modal substitution calculus. The proof is based on constructing distributed automata that capture all MSO-definable node properties over trees. We also consider some variants of the acceptance conditions.