Damian Heiman — accepted AI-conference papers

2026

Expressive Power of Graph Transformers via Logic

Veeti Ahvonen, Maurice Funk, Damian Heiman, Antti Kuusisto, Carsten Lutz

AAAI 2026technical

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

Cited by 0 Source ↗PDF ↗Scholar ↗

2024

Logical characterizations of recurrent graph neural networks with reals and floats

Veeti Ahvonen, Damian Heiman, Antti Kuusisto, Carsten Lutz

NeurIPS 2024poster

In pioneering work from 2019, Barceló and coauthors identified logics that precisely match the expressive power of constant iteration-depth graph neural networks (GNNs) relative to properties definable in first-order logic. In this article, we give exact logical characterizations of recurrent GNNs i…

Cited by 2 Source ↗PDF ↗Scholar ↗