Graph neural networks and MSO
Veeti Ahvonen, Damian Heiman, Antti Kuusisto · arXiv (Cornell University) · 2025
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.