The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic
Bernardo Cuenca Grau, Przemysław A. Wałęga · 2025
Read The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic by Bernardo Cuenca Grau, Przemysław A. Wałęga (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-08021.txt.
Description
Cuenca Grau and co-authors draw an exact map between graph neural networks and logic. These networks learn from graph-shaped data of any size while treating relabeled graphs as the same, but how much they can express has been unclear. The authors design network variants that match, precisely, well-known fragments of first-order logic, including modal logics and stronger two-variable fragments.
The proofs borrow tools from finite model theory, the study of logic on finite structures. The result is a shared language: questions about what a network can compute become questions about what a logic can say. The authors offer the correspondence as a unifying frame for understanding the power of graph learning.
Catalog record
| CREATOR | Bernardo Cuenca Grau, Przemysław A. Wałęga |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-08021