# Structural Preservation and the Logical Expressiveness of Graph Neural Networks

arXiv: https://arxiv.org/abs/2606.17882 · HTML: https://mlsanity.com/paper/2606.17882/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 31 references that are in the map.
- First posted on arXiv 16 Jun 2026.

## Builds on (most cited first, 13 of 13)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [The Descriptive Complexity of Graph Neural Networks](https://mlsanity.com/paper/2303.04613/) (2023)
- [Decidability of Graph Neural Networks via Logical Characterizations](https://mlsanity.com/paper/2404.18151/) (2024)
- [Graded modal logic and counting bisimulation](https://mlsanity.com/paper/1910.00039/) (2019)
- [On the Correspondence Between Monotonic Max-Sum GNNs and Datalog](https://mlsanity.com/paper/2305.18015/) (2023)
- [A Logic for Reasoning About Aggregate-Combine Graph Neural Networks](https://mlsanity.com/paper/2405.00205/) (2024)
- [The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic](https://mlsanity.com/paper/2505.08021/) (2025)
- [Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2](https://mlsanity.com/paper/2508.06091/) (2025)
- [Relational Graph Convolutional Networks Do Not Learn Sound Rules](https://mlsanity.com/paper/2408.10261/) (2024)
- [Sound Logical Explanations for Mean Aggregation Graph Neural Networks](https://mlsanity.com/paper/2511.11593/) (2025)

## Abstract (arXiv)

Bridges between graph neural networks (GNNs) and logical formalisms have been established by fixing architectural choices, such as the types of aggregation, combination, and activation functions. These choices define restricted classes of GNNs for which tight correspondences with logical formalisms can be obtained, by showing that logical formulae can be translated into equivalent GNNs and, conversely, that GNNs can be translated into equivalent formulae. In this paper we take a semantic perspective by establishing the logical expressiveness of classes of GNN classifiers that are preserved under structural properties: embeddings (extensions), injective homomorphisms, and homomorphisms. We show that, for each such property, there exists a fragment of graded modal logic characterising the class of GNNs. In particular, preservation under embeddings, injective homomorphisms, and homomorphisms corresponds to existential graded modal logic, its existential-positive fragment, and existential-positive modal logic, respectively. These results characterise the expressiveness of broad classes of GNNs independently of specific architectural choices, but we also show that each of these classes admits a GNN architecture of the same expressiveness. Technically, our approach uses a new well-quasi-order result for trees of bounded height, yielding finite representations of unravelling-invariant classes.