pith. sign in

arxiv: 2606.17882 · v2 · pith:DL2O75ZZnew · submitted 2026-06-16 · 💻 cs.AI

Structural Preservation and the Logical Expressiveness of Graph Neural Networks

Przemys{\l}aw Andrzej Wa{\l}\k{e}ga , Bernardo Cuenca Grau This is my paper

Pith reviewed 2026-07-01 07:18 UTC · model grok-4.3

classification 💻 cs.AI
keywords graph neural networksgraded modal logicexpressivenesshomomorphismsembeddingsstructural preservationunravelling-invariant classes
0
0 comments X

The pith

Graph neural networks preserved under embeddings, injective homomorphisms, or homomorphisms match the expressiveness of specific fragments of graded modal logic.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that classes of GNN classifiers preserved under embeddings correspond to existential graded modal logic, those preserved under injective homomorphisms correspond to its existential-positive fragment, and those preserved under homomorphisms correspond to existential-positive modal logic. These correspondences characterize the expressiveness of broad classes of GNNs without depending on particular choices for aggregation, combination, or activation functions. The authors further show that each of these logical fragments can be realized by some GNN architecture. The proofs rest on a new well-quasi-order result for trees of bounded height that produces finite representations of unravelling-invariant classes.

Core claim

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 each of these classes admits a GNN architecture of the same expressiveness.

What carries the argument

Preservation under embeddings, injective homomorphisms, and homomorphisms, which correspond to fragments of graded modal logic via unravelling-invariant classes given finite representations by a well-quasi-order on trees of bounded height.

If this is right

  • GNNs preserved under embeddings express exactly the properties definable in existential graded modal logic.
  • GNNs preserved under injective homomorphisms express exactly the properties definable in the existential-positive fragment of graded modal logic.
  • GNNs preserved under homomorphisms express exactly the properties definable in existential-positive modal logic.
  • For each of these logical fragments there exists a GNN architecture with precisely the same expressiveness.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Structural preservation properties could be checked directly on trained GNNs to determine which logical fragment they match.
  • The finite-representation technique might transfer to other graph classes or modal fragments beyond those treated here.
  • Results on the logical side could be used to construct GNNs guaranteed to respect particular structural invariances.

Load-bearing premise

The new well-quasi-order result for trees of bounded height applies to the unravelling-invariant classes and yields finite representations.

What would settle it

Existence of a GNN preserved under embeddings whose classification decisions cannot be matched by any formula of existential graded modal logic, or failure of the well-quasi-order to produce the required finite representations for the relevant classes.

Figures

Figures reproduced from arXiv: 2606.17882 by Bernardo Cuenca Grau, Przemys{\l}aw Andrzej Wa{\l}\k{e}ga.

Figure 1
Figure 1. Figure 1: Embedding (a), injective homomorphism (not an embedding) (b), and a homomorphism [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A pointed graph and its 2-unravelling Importantly, GNNs with L layers are invariant under this transformation: evaluating a GNN with L layers on a graph yields the same result as evaluating it on its L-unravelling. This observation will be central to our analysis, as it allows us to reason about GNNs using tree-shaped structures, and has been exploited in prior work to relate GNNs to logical formalisms [4]… view at source ↗
Figure 3
Figure 3. Figure 3: An infinite antichain of rooted trees with respect to the injective homomorphism [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper claims that classes of GNN classifiers preserved under embeddings, injective homomorphisms, and homomorphisms are characterized by existential graded modal logic, its existential-positive fragment, and existential-positive modal logic, respectively. These results are architecture-independent, each such class admits a matching GNN architecture, and the characterizations are obtained via a new well-quasi-order on trees of bounded height that yields finite representations of unravelling-invariant classes.

Significance. If the results hold, the semantic approach yields architecture-independent expressiveness characterizations for broad GNN classes via structural preservation, complementing prior work that fixes aggregation/combination functions. The existence of matching GNN architectures for each fragment and the new WQO result (if verified) are notable strengths that could enable broader applications in logic and graph learning.

major comments (2)
  1. [Abstract] Abstract and technical approach: the claimed exact correspondences and finite characterizations rest on a new well-quasi-order result for trees of bounded height that produces finite representations of unravelling-invariant classes. This result is load-bearing; without a complete, self-contained proof that the ordering is a WQO and applies to the relevant fragments, the semantic characterizations and architecture-existence claims do not follow.
  2. [Abstract] Abstract: the assertion that each preservation class admits a GNN architecture of identical expressiveness depends on the WQO yielding the required finite bases for the unravelling-invariant classes; the manuscript must exhibit or reference the explicit construction or translation that realizes this for each of the three fragments.
minor comments (1)
  1. Ensure consistent notation for the GNN classes and the three logic fragments throughout; define all preservation properties (embeddings, injective homomorphisms, homomorphisms) explicitly before the main theorems.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful and detailed report. The comments correctly identify the central technical pillar of the paper—the new well-quasi-order on bounded-height trees—and we address each point below with references to the existing proofs and planned clarifications.

read point-by-point responses

  1. Referee: [Abstract] Abstract and technical approach: the claimed exact correspondences and finite characterizations rest on a new well-quasi-order result for trees of bounded height that produces finite representations of unravelling-invariant classes. This result is load-bearing; without a complete, self-contained proof that the ordering is a WQO and applies to the relevant fragments, the semantic characterizations and architecture-existence claims do not follow.

    Authors: Section 4 of the manuscript contains a self-contained proof that the proposed ordering on trees of bounded height is a well-quasi-order (including the verification of the WQO property via Dickson’s lemma and the height bound) and that it induces finite bases for the unravelling-invariant classes corresponding to existential graded modal logic, its existential-positive fragment, and existential-positive modal logic. The proof directly supports both the preservation characterizations and the existence of finite representations. To improve readability and address the concern about prominence, we will insert a short dedicated subsection in the main text that summarizes the key lemmas and cross-references the full appendix proof. revision: partial

  2. Referee: [Abstract] Abstract: the assertion that each preservation class admits a GNN architecture of identical expressiveness depends on the WQO yielding the required finite bases for the unravelling-invariant classes; the manuscript must exhibit or reference the explicit construction or translation that realizes this for each of the three fragments.

    Authors: The finite bases obtained from the WQO are used to construct the matching GNNs via a uniform translation: each minimal tree in the basis is encoded as a fixed-depth GNN layer that computes the corresponding graded modal formula, with the overall classifier obtained by disjunction over the finite basis. This construction is sketched in Section 5 for all three fragments and is fully detailed in the appendix. We will add an explicit reference and a brief worked example for each fragment in the revised main text to make the translation steps immediately visible. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on new well-quasi-order theorem

full rationale

The paper derives logical characterizations of GNN classes from structural preservation properties (embeddings, injective homomorphisms, homomorphisms) mapping to fragments of graded modal logic. These correspondences are obtained via a new well-quasi-order result on trees of bounded height that provides finite representations of unravelling-invariant classes. No equations reduce to inputs by construction, no parameters are fitted and renamed as predictions, and no load-bearing steps depend on self-citations or prior ansatzes from the same authors. The central claims are independent of specific GNN architectures and rest on the (presumably proven) new ordering result rather than redefinition or external self-reference. This is a standard self-contained mathematical derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on a new well-quasi-order result for trees of bounded height that is introduced to obtain finite representations; no free parameters or invented entities are mentioned.

axioms (1)
  • ad hoc to paper New well-quasi-order result for trees of bounded height yielding finite representations of unravelling-invariant classes
    Invoked to establish the finite characterizations that underpin the logic-GNN correspondences.

pith-pipeline@v0.9.1-grok · 5764 in / 1359 out tokens · 52379 ms · 2026-07-01T07:18:07.098839+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

36 extracted references · 1 canonical work pages

  1. [1]

    Abramsky and L

    S. Abramsky and L. Reggio. Arboreal categories and equi-resource homomorphism preservation theorems.Ann. Pure Appl. Log., 175(6):103423, 2024

    2024

  2. [2]

    Andréka, I

    H. Andréka, I. Németi, and J. van Benthem. Modal languages and bounded fragments of predicate logic.J. Philos. Log., 27(3):217–274, 1998

    1998

  3. [3]

    Baader, D

    F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, and P. F. Patel-Schneider, editors.The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, 2003

    2003

  4. [4]

    Barceló, E

    P. Barceló, E. V . Kostylev, M. Monet, J. Pérez, J. L. Reutter, and J. P. Silva. The logical expressiveness of graph neural networks. InProc. of ICLR, 2020

    2020

  5. [5]

    Benedikt, C.-H

    M. Benedikt, C.-H. Lu, B. Motik, and T. Tan. Decidability of Graph Neural Networks via Logical Characterizations. InProc. of ICALP, volume 297, pages 127:1–127:20. Schloss Dagstuhl, 2024

    2024

  6. [6]

    Cuenca Grau, E

    B. Cuenca Grau, E. Feng, and P. Walega. The correspondence between bounded graph neural networks and fragments of first-order logic. InProc. of AAAI, 2026

    2026

  7. [7]

    de Rijke

    M. de Rijke. A note on graded modal logic.Stud Logica, 64(2):271–283, 2000

    2000

  8. [8]

    Gilmer, S

    J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. InProc. of ICML, volume 70, pages 1263–1272, 2017

    2017

  9. [9]

    Grädel, P

    E. Grädel, P. G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Y . Vardi, Y . Venema, and S. Weinstein.Finite Model Theory and Its Applications. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2007

    2007

  10. [10]

    M. Grohe. The descriptive complexity of graph neural networks.TheoretiCS, 3, 2024

    2024

  11. [11]

    S. P. Hauke and P. A. Wał˛ ega. Aggregate-combine-readout GNNs are more expressive than logic C2. InProc. of AAAI, 2026

    2026

  12. [12]

    Hodges.A Shorter Model Theory

    W. Hodges.A Shorter Model Theory. Cambridge University Press, 1997

    1997

  13. [13]

    Libkin.Elements of Finite Model Theory

    L. Libkin.Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2004

    2004

  14. [14]

    Lopez.First Order Preservation Theorems in Finite Model Theory : Locality, Topology, and Limit Constructions

    A. Lopez.First Order Preservation Theorems in Finite Model Theory : Locality, Topology, and Limit Constructions. (Théorèmes de préservation pour la logique au premier ordre: localité, topologie et constructions limites). PhD thesis, University of Paris-Saclay, France, 2023

    2023

  15. [15]

    Ło ´s and R

    J. Ło ´s and R. Suszko. On the extending of models (ii).Fundamenta Mathematicae, 42(2):343– 347, 1955

    1955

  16. [16]

    R. C. Lyndon. Properties preserved under homomorphism. 1959

    1959

  17. [17]

    Morris, M

    C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. InProc. of AAAI, pages 4602–4609. AAAI Press, 2019

    2019

  18. [18]

    Morris, M

    C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. InProc. of AAAI, volume 33, pages 4602–4609, 2019

    2019

  19. [19]

    Morris, D

    M. Morris, D. J. T. Cucala, B. C. Grau, and I. Horrocks. Relational graph convolutional networks do not learn sound rules. In P. Marquis, M. Ortiz, and M. Pagnucco, editors,Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, KR 2024, Hanoi, Vietnam. November 2-8, 2024, 2024

    2024

  20. [20]

    Morris and I

    M. Morris and I. Horrocks. Sound logical explanations for mean aggregation graph neural networks. InThe Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. 10

    2025

  21. [21]

    P. Nunn, M. Sälzer, F. Schwarzentruber, and N. Troquard. A logic for reasoning about aggregate- combine graph neural networks. InProc. of IJCAI, pages 3532–3540. ijcai.org, 2024

    2024

  22. [22]

    M. Otto. Graded modal logic and counting bisimulation.CoRR, abs/1910.00039, 2019

    work page arXiv 1910

  23. [23]

    E. Rosen. Modal logic over finite structures.J. Log. Lang. Inf., 6(4):427–439, 1997

    1997

  24. [24]

    E. Rosen. Some aspects of model theory and finite structures.Bull. Symb. Log., 8(3):380–403, 2002

    2002

  25. [25]

    B. Rossman. Homomorphism preservation theorems.J. ACM, 55(3):15:1–15:53, 2008

    2008

  26. [26]

    Tena Cucala, B

    D. Tena Cucala, B. Cuenca Grau, B. Motik, and E. V . Kostylev. On the correspondence between monotonic max-sum gnns and datalog. In P. Marquis, T. C. Son, and G. Kern-Isberner, editors, Proc. of KR, pages 658–667, 2023

    2023

  27. [27]

    D. J. Tena Cucala and B. Cuenca Grau. Bridging max graph neural networks and datalog with negation. In P. Marquis, M. Ortiz, and M. Pagnucco, editors,Proc. of KR, 2024

    2024

  28. [28]

    D. J. Tena Cucala, B. Cuenca Grau, B. Motik, and E. V . Kostylev. Expressive power of monotonic graph neural networks via datalog. InHandbook on Neurosymbolic AI and Knowledge Graphs, pages 780–807. IOS Press, 2025

    2025

  29. [29]

    S. Tobies. PSPACE reasoning for graded modal logics.J. Log. Comput., 11(1):85–106, 2001

    2001

  30. [30]

    Wang and M

    X. Wang and M. Zhang. How powerful are spectral graph neural networks. InProc. of ICML, 2022

    2022

  31. [31]

    K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? InProc. of ICLR, 2019. Technical Appendix A Proofs for Section 4.4 Theorem 4.The embedding relation on any class of rooted trees, whose heights are uniformly bounded by a fixed constant, is a well-quasi-order. Proof. Let L be the uniform bound on the height of the trees und...

    2019

  32. [32]

    ifφ ℓ is a proposition or the negation of a proposition, thenC ℓℓ = 1

  33. [33]

    ifφ ℓ =φ j ∧φ k, thenC jℓ =C kℓ = 1andb ℓ =−1

  34. [34]

    ifφ ℓ =φ j ∨φ k, thenC jℓ =C kℓ = 1andb ℓ = 0

  35. [35]

    All other entries are set to0

    ifφ ℓ =♢ ≥cφk, thenA kℓ = 1andb ℓ =−c+ 1. All other entries are set to0. Observe that all entries of A and C are non-negative, so Nφ is a positive-weight GNN with additional augmented layer. Hence, by Proposition 13,N φ is an augmented MGNN, as required. We now show correctness of the construction. Consider the application of Nφ to a graph G= (V, E, λ). W...

  36. [36]

    It remains to consider the case when N is an augmented MAX-MGNN, and show that it is equivalent to some ∃ML formula

    there exists a formulaφin the required fragment of modal logic. It remains to consider the case when N is an augmented MAX-MGNN, and show that it is equivalent to some ∃ML formula. We observe that every MAX-MGNN can be seen as a bounded AC-GNN with set-based aggregation, denoted as GNNAC s , as defined in [6]. It has been shown that GNNAC s s have the sam...