Expressive Power of Graph Transformers via Logic
This work addresses the theoretical understanding of graph transformers' capabilities for researchers in machine learning and logic, providing foundational insights but is incremental as it builds on existing models.
The paper studied the expressive power of graph transformers and GPS-networks under soft and hard attention, showing that with real numbers, GPS-networks match graded modal logic with the global modality for first-order logic definable vertex properties, and with floats, they are equally expressive as graded modal logic with the counting global modality without restrictions.
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).