Graph neural networks and MSO
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915288209948672 |
|---|---|
| author | Ahvonen, Veeti Heiman, Damian Kuusisto, Antti |
| author_facet | Ahvonen, Veeti Heiman, Damian Kuusisto, Antti |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_07816 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graph neural networks and MSO Ahvonen, Veeti Heiman, Damian Kuusisto, Antti Logic in Computer Science Artificial Intelligence F.4.1; F.1.1; I.2.0 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. |
| title | Graph neural networks and MSO |
| topic | Logic in Computer Science Artificial Intelligence F.4.1; F.1.1; I.2.0 |
| url | https://arxiv.org/abs/2505.07816 |