Graph Neural Networks: Structural preservation and logic

Przemysław Andrzej Wałęga and Bernardo Cuenca Grau submitted an arXiv paper on 16 Jun 2026 (arXiv:2606.17882) that characterises the logical expressiveness of classes of graph neural network classifiers defined by structural preservation properties. The 20-page paper shows exact correspondences between three preservation properties and fragments of graded modal logic, and it constructs matching GNN architectures for each class.

What does the paper claim?

The paper asserts that classes of GNN classifiers preserved under particular structural mappings correspond exactly to fragments of graded modal logic. Specifically, preservation under embeddings corresponds to existential graded modal logic, preservation under injective homomorphisms corresponds to the existential-positive fragment of that logic, and preservation under homomorphisms corresponds to existential-positive modal logic. The authors also show that each of these logically characterised classes admits a GNN architecture with the same expressiveness.

Those are not presented as mere examples. The correspondences are central results of the paper, and the authors derive them from a semantic perspective rather than by fixing low-level architectural choices such as aggregation or activation functions. The paper frames these results as characterising broad classes of GNNs independently of specific architectural choices.

How do the three structural properties map to logic?

The paper gives a direct mapping: embeddings map to existential graded modal logic, injective homomorphisms map to the existential-positive fragment of existential graded modal logic, and general homomorphisms map to existential-positive modal logic. The opening sentence in this section summarises the mapping, and the remainder of the section in the paper develops the formal translations in both directions, showing that formulae in each fragment can be translated into equivalent GNNs and vice versa.

The authors insist this is a semantic approach. Rather than deriving expressiveness limits from particular aggregator functions, they tie classes of GNN classifiers to logical fragments determined by preservation under structural properties. They further prove that each logically defined class can be implemented by a GNN architecture of the same expressiveness, closing the circle between logic and implementable GNN models.

What technical tools underpin the results?

A new well-quasi-order result for trees of bounded height provides the technical backbone. The paper uses this result to obtain finite representations of unravelling-invariant classes, which support the translations between logical formulae and GNN classifiers. That combinatorial tool appears as a key technical innovation enabling the characterisation results.

Other concrete bibliographic details support the paper's provenance: it is arXiv:2606.17882, was submitted on 16 Jun 2026, and the downloadable submission is 20 pages long.

Why it matters

This work separates semantic limits of GNNs from implementation details. By tying expressiveness to structural preservation properties and explicit logical fragments, the paper gives a clearer language for stating what a class of GNNs can and cannot distinguish. That matters for researchers seeking principled comparisons of GNN variants and for theoreticians who need exact expressiveness bounds independent of low-level architectural choices.

The constructive direction, showing each class admits a GNN architecture with matching expressiveness, reduces the gap between abstract logical characterisations and concrete model design. The new well-quasi-order result also supplies a technical tool that could be reused in other expressiveness or invariance proofs.

What to watch

Follow subsequent work that either applies these logical correspondences to specific GNN architectures or that extends the well-quasi-order technique beyond trees of bounded height. Evidence that the paper's mappings affect empirical architecture design would be a concrete next milestone.