Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Recurrent Graph Neural Networks and Their Connections to Bisimulation and Logic
Authors: Maximilian Pflueger, David Tena Cucala, Egor V. Kostylev
AAAI 2024 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we start to fill this gap and study the foundations of GNNs that can perform more than a fixed number of message-passing iterations. We first formalise two generalisations of the basic GNNs: recurrent GNNs (Rec GNNs), which repeatedly apply message-passing iterations until the node classifications become stable, and graph-size GNNs (GSGNNs), which exploit a built-in function of the input graph size to decide the number of message-passings. We then formally prove that GNN classifiers are strictly less expressive than Rec GNN ones, and Rec GNN classifiers are strictly less expressive than GSGNN ones. To get this result, we identify novel semantic characterisations of the three formalisms in terms of suitable variants of bisimulation, which we believe have their own value for our understanding of GNNs. Finally, we prove syntactic logical characterisations of Rec GNNs and GSGNNs analogous to the logical characterisation of plain GNNs, where we connect the two formalisms to monadic monotone fixpoint logic a generalisation of first-order logic that supports recursion. |
| Researcher Affiliation | Academia | 1University of Oxford, United Kingdom 2University of Oslo, Norway EMAIL, EMAIL, EMAIL |
| Pseudocode | No | The paper is theoretical and focuses on formal definitions, theorems, and proofs. It does not include any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper is theoretical and does not present an implementation or release source code for the described formalisms. |
| Open Datasets | No | The paper is theoretical and does not describe empirical experiments, dataset usage, or public dataset availability. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments with data splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental setup or provide software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup, hyperparameters, or training configurations. |