mlsanityData to 14 Oct 2026

Decidability of Graph Neural Networks via Logical Characterizations

arXiv 2404.18151 ↗First posted 28 Apr 2024cs.LOcited by 14

Not on the map. Why?

Abstract (arXiv)

We present results concerning the expressiveness and decidability of a popular graph learning formalism, graph neural networks (GNNs), exploiting connections with logic. We use a family of recently-discovered decidable logics involving "Presburger quantifiers". We show how to use these logics to measure the expressiveness of classes of GNNs, in some cases getting exact correspondences between the expressiveness of logics and GNNs. We also employ the logics, and the techniques used to analyze them, to obtain decision procedures for verification problems over GNNs. We complement this with undecidability results for static analysis problems involving the logics, as well as for GNN verification problems.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). First posted on arXiv 28 Apr 2024.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 9; 2026: 4.

14 papers.

Sort:

  1. 2024Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floatscited by 13
  2. 2025Exact Verification of Graph Neural Networks with Incremental Constraint Solvingcited by 4
  3. 2025Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualizationcited by 3
  4. 2025A Logical View of GNN-Style Computation and the Role of Activation Functionscited by 3
  5. 2025Verifying Quantized Graph Neural Networks is PSPACE-completecited by 2
  6. 2025The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logicscited by 2
  7. 2025Expressive Power of Graph Transformers via Logiccited by 2
  8. 2025Sound Logical Explanations for Mean Aggregation Graph Neural Networkscited by 2
  9. 2025From Neural Networks to Logical Theories: The Correspondence between Fibring Modal Logics and Fibring Neural Networkscited by 1
  10. 2026How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?cited by 1
  11. 2025Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testingcited by 0
  12. 2026Structural Preservation and the Logical Expressiveness of Graph Neural Networkscited by 0
2 more
  1. 2026The Boolean Power of ReLUcited by 0
  2. 2026Beyond Trained Models: Compiling GNNs for a Sound Explainer Benchmarkcited by 0