mlsanityData to 7 Oct 2026

The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic

arXiv 2505.08021 ↗First posted 12 May 2025cs.AIcited by 5

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 11 of its 26 references that are in the map. First posted on arXiv 12 May 2025.

Builds on

11 of 26 references.

References · 11

  1. 2018How Powerful are Graph Neural Networks?cited by 4,355
  2. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  3. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  4. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  5. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  6. 2018Link Prediction Based on Graph Neural Networkscited by 829
  7. 2021ETA Prediction with Graph Neural Networks in Google Mapscited by 130
  8. 2022A Survey on Graph Neural Networks and Graph Transformers in Computer Vision: A Task-Oriented Perspectivecited by 56
  9. 2023A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphscited by 32
  10. 2019Graded modal logic and counting bisimulationcited by 13
  11. 2023On the Correspondence Between Monotonic Max-Sum GNNs and Datalogcited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 3.

5 papers.

  1. 2025The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logicscited by 2
  2. 2025From Neural Networks to Logical Theories: The Correspondence between Fibring Modal Logics and Fibring Neural Networkscited by 1
  3. 2026How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?cited by 1
  4. 2026Towards Understanding the Expressive Power of GNNs with Global Readoutcited by 0
  5. 2026Structural Preservation and the Logical Expressiveness of Graph Neural Networkscited by 0