Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.08021 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912913193697280 |
|---|---|
| author | Grau, Bernardo Cuenca Feng, Eva Wałęga, Przemysław Andrzej |
| author_facet | Grau, Bernardo Cuenca Feng, Eva Wałęga, Przemysław Andrzej |
| contents | Graph Neural Networks (GNNs) address two key challenges in applying deep learning to graph-structured data: they handle varying size input graphs and ensure invariance under graph isomorphism. While GNNs have demonstrated broad applicability, understanding their expressive power remains an important question. In this paper, we propose GNN architectures that correspond precisely to prominent fragments of first-order logic (FO), including various modal logics as well as more expressive two-variable fragments. To establish these results, we apply methods from finite model theory of first-order and modal logics to the domain of graph representation learning. Our results provide a unifying framework for understanding the logical expressiveness of GNNs within FO. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_08021 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic Grau, Bernardo Cuenca Feng, Eva Wałęga, Przemysław Andrzej Artificial Intelligence Graph Neural Networks (GNNs) address two key challenges in applying deep learning to graph-structured data: they handle varying size input graphs and ensure invariance under graph isomorphism. While GNNs have demonstrated broad applicability, understanding their expressive power remains an important question. In this paper, we propose GNN architectures that correspond precisely to prominent fragments of first-order logic (FO), including various modal logics as well as more expressive two-variable fragments. To establish these results, we apply methods from finite model theory of first-order and modal logics to the domain of graph representation learning. Our results provide a unifying framework for understanding the logical expressiveness of GNNs within FO. |
| title | The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2505.08021 |