A Logic for Reasoning about Aggregate-Combine Graph Neural Networks
Authors: Pierre Nunn, Marco Sälzer, François Schwarzentruber, Nicolas Troquard
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | 1University of Rennes, IRISA, CNRS, France 2Theoretical Computer Science / Formal Methods, University of Kassel, Germany 3Gran Sasso Science Institute, L Aquila, Italy |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. It describes algorithmic procedures in natural language. |
| Open Source Code | No | The paper does not provide concrete access to source code, nor does it explicitly state that code will be released or is available. |
| Open Datasets | No | The paper is theoretical and does not involve the use of datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not provide specific dataset split information for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not provide specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not contain specific experimental setup details, hyperparameters, or training configurations. |