Preservation Theorems for Unravelling-Invariant Classes: A Uniform Approach for Modal Logics and Graph Neural Networks
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914301075259392 |
|---|---|
| author | Wałęga, Przemysław Andrzej Grau, Bernardo Cuenca |
| author_facet | Wałęga, Przemysław Andrzej Grau, Bernardo Cuenca |
| contents | We study preservation theorems for modal logics over finite structures with respect to three fundamental semantic relations: embeddings, injective homomorphisms, and homomorphisms. We focus on classes of pointed Kripke models that are invariant under bounded unravellings, a natural locality condition satisfied by modal logics and by graph neural networks (GNNs). We show that preservation under embeddings coincides with definability in existential graded modal logic; preservation under injective homomorphisms with definability in existential positive graded modal logic; and preservation under homomorphisms with definability in existential positive modal logic. A key technical contribution is a structural well-quasi-ordering result. We prove that the embedding relation on classes of tree-shaped models of uniformly bounded height forms a well-quasi-order, and that the bounded-height assumption is essential. This well-quasi-ordering yields a finite minimal-tree argument leading to explicit syntactic characterisations via finite disjunctions of (graded) modal formulae.
As an application, we derive consequences for the expressive power of GNNs. Using our preservation theorem for injective homomorphisms, we obtain a new logical characterisation of monotonic GNNs, showing that they capture exactly existential-positive graded modal logic, while monotonic GNNs with MAX aggregation correspond precisely to existential-positive modal logic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_01856 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Preservation Theorems for Unravelling-Invariant Classes: A Uniform Approach for Modal Logics and Graph Neural Networks Wałęga, Przemysław Andrzej Grau, Bernardo Cuenca Logic in Computer Science We study preservation theorems for modal logics over finite structures with respect to three fundamental semantic relations: embeddings, injective homomorphisms, and homomorphisms. We focus on classes of pointed Kripke models that are invariant under bounded unravellings, a natural locality condition satisfied by modal logics and by graph neural networks (GNNs). We show that preservation under embeddings coincides with definability in existential graded modal logic; preservation under injective homomorphisms with definability in existential positive graded modal logic; and preservation under homomorphisms with definability in existential positive modal logic. A key technical contribution is a structural well-quasi-ordering result. We prove that the embedding relation on classes of tree-shaped models of uniformly bounded height forms a well-quasi-order, and that the bounded-height assumption is essential. This well-quasi-ordering yields a finite minimal-tree argument leading to explicit syntactic characterisations via finite disjunctions of (graded) modal formulae. As an application, we derive consequences for the expressive power of GNNs. Using our preservation theorem for injective homomorphisms, we obtain a new logical characterisation of monotonic GNNs, showing that they capture exactly existential-positive graded modal logic, while monotonic GNNs with MAX aggregation correspond precisely to existential-positive modal logic. |
| title | Preservation Theorems for Unravelling-Invariant Classes: A Uniform Approach for Modal Logics and Graph Neural Networks |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2602.01856 |