Graph neural networks and MSO

2025/05/12 by Ahvonen, Veeti, Heiman, Damian, Kuusisto, Antti
#Artificial Intelligence (cs.AI) #F.1.1 #F.4.1 #FOS: Computer and information sciences #I.2.0 #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2505.07816

Abstract

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.

Citations

• Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats

Related

• Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats
• A Modal Logic for Explaining some Graph Neural Networks
• A Logic for Reasoning About Aggregate-Combine Graph Neural Networks
• Lecture Notes on Verifying Graph Neural Networks
• The logic of rational graph neural networks