Research map / Graph learning / GNN architectures
Logical characterizations of recurrent graph neural networks with reals and floats
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.
Gives exact logical characterizations of recurrent GNNs with floats (GNN[F]) and with reals (GNN[R]): floats match a rule-based graded modal substitution calculus (GMSC), reals match infinitary graded modal logic (ω-GML), and over MSO-definable properties both coincide with GMSC.
Problem
Expressive power of recurrent GNNs, both with real-valued and floating-point arithmetic, has lacked exact logical characterizations without relativising to a background logic such as FO.
Approach
Characterizes recurrent GNN[F]s by the graded modal substitution calculus (a rule-based graded modal logic) and recurrent GNN[R]s by infinitary graded modal logic, using counting message passing automata as an intermediate tool, and shows float and real GNNs coincide over MSO-definable properties.
Key results
- GNN[F]s, R-simple aggregate-combine GNN[F]s and GMSC have the same expressive power (absolute, no background logic).
- GNN[R]s have the same expressive power as infinitary graded modal logic ω-GML, and both match CMPAs.
- Over MSO-definable node properties, GNN[R]s and GNN[F]s have the same expressive power, both characterized by the finitary GMSC; in general floats are strictly weaker than reals.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use reals instead of floats | recurrent GNNs · general graph properties and MSO-definable properties | expressive power | Mixed |
Surprising findings
- Over MSO-definable properties, unrestricted real arithmetic gives no more expressive power than floats.
- A property expressible as a GNN[F] is not expressible in MSO (centre-point property).
Limitations
- Termination of recurrent GNNs during training/application is not studied.
- Global readouts and other acceptance conditions are only discussed in appendix or future work.
- Polynomial translation from GMSC to R-simple GNN[F] is conjectured, not proven.
Experimental setup
Baselines: Barceló et al. constant-iteration GNN characterization Pfluger et al. recurrent GNN characterization
Builds on: Barceló et al. 2019 GNN logical characterization modal substitution calculus graded modal logic counting message passing automata
Closest papers by meaning
- Recurrent Graph Neural Networks and Their Connections to Bisimulation and Logic (AAAI 2024 · similarity 0.93)
- The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics (NeurIPS 2025 · similarity 0.89)
- Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization (NeurIPS 2025 · similarity 0.87)
- Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNs (ICLR 2025 · similarity 0.86)
- Graph Neural Networks and Arithmetic Circuits (NeurIPS 2024 · similarity 0.86)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.86)
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.