Research map / Graph learning / GNN architectures
Recurrent Graph Neural Networks and Their Connections to Bisimulation and Logic
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Formalises recurrent GNNs (RecGNNs) and graph-size GNNs (GSGNNs), proves they strictly extend plain GNNs, characterises all three via bisimulation variants, and gives logical characterisations in monadic monotone fixpoint logic.
Problem
Plain GNNs with a fixed number of message-passing layers cannot express recursive node classifiers such as reachability; the expressive power of GNNs that iterate beyond a fixed number of layers is unstudied.
Approach
Define RecGNNs (iterate a layer until classifications stabilise) and GSGNNs (iterate a number of times given by a function of graph size), give semantic characterisations via graded two-way bisimulation and gs-bisimulation, and derive logical characterisations via a local fragment of monadic monotone fixpoint logic with van Benthem-Rosen-style theorems.
Key results
- Proves GNN classifiers are strictly less expressive than RecGNN classifiers, and RecGNN classifiers strictly less expressive than GSGNN classifiers.
- Characterises GNNs, RecGNNs and GSGNNs exactly by invariance under graded two-way ℓ-bisimulation, bisimulation and gs-bisimulation respectively.
- Shows RecGNN-realisable classifiers coincide with LocMMFP formulas that are bisimulation-invariant, equivalent to MMFP(GML−) formulas over finite structures.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace a fixed number of message-passing iterations with recurrent iterations until classifications stabilise | GNNs · node classifiers over finite relational structures | expressive power | Helped |
| use a graph-size-dependent number of message-passing iterations | RecGNNs · node classifiers over finite relational structures | expressive power | Helped |
| use a graph-size-dependent number of message-passing iterations instead of a fixed number | GNNs · node classifiers over finite relational structures | expressive power | Helped |
Limitations
- Van Benthem-Rosen characterisations are only proved for the local fragment of MMFP, not full MMFP, MLFP or MSO
- Results are theoretical and Boolean-classifier-only; no experiments
- Abstracts away from concrete architectures and training details
Experimental setup
Baselines: plain GNNs (fixed-layer)
Builds on: Barceló et al. 2019 GNN-logic correspondence Scarselli et al. 2008 GNN Otto 2019 bisimulation van Benthem-Rosen theorem RunCSP
Closest papers by meaning
- Logical characterizations of recurrent graph neural networks with reals and floats (NeurIPS 2024 · similarity 0.93)
- On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning (NeurIPS 2025 · similarity 0.89)
- Towards Dynamic Message Passing on Graphs (NeurIPS 2024 · similarity 0.89)
- Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization (NeurIPS 2025 · similarity 0.89)
- Almost Surely Asymptotically Constant Graph Neural Networks (NeurIPS 2024 · similarity 0.88)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.