Showing 2025Show all
2 papers · 1 filter
cs.LO2025
Expressive Power of Graph Transformers via Logic
Veeti Ahvonen, Maurice Funk, Damian Heiman +2
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 tr…
cs.AI2025
Logical Characterizations of GNNs with Mean Aggregation
Moritz Schönherr, Carsten Lutz
We study the expressive power of graph neural networks (GNNs) with mean as the aggregation function, with the following results. In the non-uniform setting, such GNNs have exactly…