mlsanityData to 14 Oct 2026

A Logic for Reasoning About Aggregate-Combine Graph Neural Networks

arXiv 2405.00205 ↗First posted 30 Apr 2024cs.AI cs.LG cs.LOcited by 10

Not on the map. Why?

Abstract (arXiv)

We propose a modal logic in which counting modalities appear in linear inequalities. We show that each formula can be transformed into an equivalent graph neural network (GNN). We also show that a broad class of GNNs can be transformed efficiently into a formula, thus significantly improving upon the literature about the logical expressiveness of GNNs. We also show that the satisfiability problem is PSPACE-complete. These results bring together the promise of using standard logical methods for reasoning about GNNs and their properties, particularly in applications such as GNN querying, equivalence checking, etc. We prove that such natural problems can be solved in polynomial space.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 9 of its 37 references that are in the map. First posted on arXiv 30 Apr 2024.

Builds on

9 of 37 references.

References · 9

  1. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  2. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,576
  3. 2020Explainability in Graph Neural Networks: A Taxonomic Surveycited by 384
  4. 2022Graph neural networks for materials science and chemistrycited by 182
  5. 2021The Logic of Graph Neural Networkscited by 85
  6. 2022Global Explainability of GNNs via Logic Combination of Learned Conceptscited by 65
  7. 2023On the Correspondence Between Monotonic Max-Sum GNNs and Datalogcited by 12
  8. 2022DT+GNN: A Fully Explainable Graph Neural Network using Decision Treescited by 6
  9. 2020Satisfiability and Query Answering in Description Logics with Global and Local Cardinality Constraintscited by 5

Built on by

Cited by year (2026 to 14 Oct)

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

10 papers.

  1. 2025Exact Verification of Graph Neural Networks with Incremental Constraint Solvingcited by 4
  2. 2025Verifying Quantized Graph Neural Networks is PSPACE-completecited by 2
  3. 2025The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logicscited by 2
  4. 2025Sound Logical Explanations for Mean Aggregation Graph Neural Networkscited by 2
  5. 2025DeepGraphLog for Layered Neurosymbolic AIcited by 1
  6. 2025From Neural Networks to Logical Theories: The Correspondence between Fibring Modal Logics and Fibring Neural Networkscited by 1
  7. 2025Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testingcited by 0
  8. 2026Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approachcited by 0
  9. 2026Structural Preservation and the Logical Expressiveness of Graph Neural Networkscited by 0
  10. 2026Beyond Trained Models: Compiling GNNs for a Sound Explainer Benchmarkcited by 0