Graph neural networks and MSO
This work is incremental, offering a new proof for an existing theoretical result in graph neural networks and logic, relevant to researchers in theoretical computer science and machine learning.
The paper provides an alternative proof that recurrent graph neural networks with real numbers have the same expressive power as the graded modal substitution calculus when restricted to monadic second-order logic (MSO) for node properties over trees, and explores variants of acceptance conditions.
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.