Expressive Power of Graph Transformers via Logic
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908838557384704 |
|---|---|
| author | Ahvonen, Veeti Funk, Maurice Heiman, Damian Kuusisto, Antti Lutz, Carsten |
| author_facet | Ahvonen, Veeti Funk, Maurice Heiman, Damian Kuusisto, Antti Lutz, Carsten |
| contents | Transformers are the basis of modern large language models, but relatively little is known about their precise expressive power on graphs. We study the expressive power of graph transformers (GTs) by Dwivedi and Bresson (2020) and GPS-networks by Rampásek et al. (2022), both under soft-attention and average hard-attention. Our study covers two scenarios: the theoretical setting with real numbers and the more practical case with floats. With reals, we show that in restriction to vertex properties definable in first-order logic (FO), GPS-networks have the same expressive power as graded modal logic (GML) with the global modality. With floats, GPS-networks turn out to be equally expressive as GML with the counting global modality. The latter result is absolute, not restricting to properties definable in a background logic. We also obtain similar characterizations for GTs in terms of propositional logic with the global modality (for reals) and the counting global modality (for floats). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_01067 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Expressive Power of Graph Transformers via Logic Ahvonen, Veeti Funk, Maurice Heiman, Damian Kuusisto, Antti Lutz, Carsten Logic in Computer Science Artificial Intelligence F.4.1; F.1.1; I.2.0 Transformers are the basis of modern large language models, but relatively little is known about their precise expressive power on graphs. We study the expressive power of graph transformers (GTs) by Dwivedi and Bresson (2020) and GPS-networks by Rampásek et al. (2022), both under soft-attention and average hard-attention. Our study covers two scenarios: the theoretical setting with real numbers and the more practical case with floats. With reals, we show that in restriction to vertex properties definable in first-order logic (FO), GPS-networks have the same expressive power as graded modal logic (GML) with the global modality. With floats, GPS-networks turn out to be equally expressive as GML with the counting global modality. The latter result is absolute, not restricting to properties definable in a background logic. We also obtain similar characterizations for GTs in terms of propositional logic with the global modality (for reals) and the counting global modality (for floats). |
| title | Expressive Power of Graph Transformers via Logic |
| topic | Logic in Computer Science Artificial Intelligence F.4.1; F.1.1; I.2.0 |
| url | https://arxiv.org/abs/2508.01067 |