Loading...
On the theoretical expressive power of graph transformers for solving graph problems
Nikolentzos, Giannis Kelesis, Dimitrios Vazirgiannis, Michalis
Nikolentzos, Giannis
Kelesis, Dimitrios
Vazirgiannis, Michalis
Files
Loading...
minerals-15-01035.pdf
Adobe PDF, 2.45 MB
Supervisor
Department
Machine Learning
Embargo End Date
Type
Journal article
Date
2026
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
In recent years, Transformers have become the dominant neural architecture in the fields of natural language processing and computer vision. The generalization of Transformers to graphs, so-called Graph Transformers, have recently emerged as a promising alternative to the successful message passing Graph Neural Networks (MPNNs). While the expressive power of MPNNs has been intensively studied in the past years, that of Graph Transformers is still underexplored. Existing results mostly rely on the employed structural/positional encodings and not on the pure architecture itself. However, gaining an understanding of the strengths and limitations of Graph Transformers would be very useful both for the scientific community and the practitioners. In this paper, we derive a connection between Graph Transformers and the Congested clique, a popular model in distributed computing. This connection allows us to translate theoretical results for different graph problems from the latter to the former. We show that under certain conditions, Graph Transformers with depth 2 are Turing universal. We also show that there exist Graph Transformers that can solve problems which cannot be solved by MPNNs. We empirically investigate whether Graph Transformers and MPNNs with depth 2 can solve graph problems on some molecular datasets. Our results demonstrate that Graph Transformers can generally address the underlying tasks, while MPNNs are incapable of learning any information about the graph.
Citation
G. Nikolentzos, D. Kelesis, and M. Vazirgiannis, “On the theoretical expressive power of graph transformers for solving graph problems,” Neural Networks, vol. 194, p. 108112, Feb. 2026, doi: 10.1016/J.NEUNET.2025.108112
Source
Neural Networks
Conference
Keywords
Congested Clique, Expressive Power, Graph Problems, Graph Transformers, Computer Architecture, Distributed Computer Systems, Graph Neural Networks, Natural Language Processing Systems, Problem Solving, Undirected Graphs, Congested Clique, Expressive Power, Generalisation, Graph Problems, Graph Transformer, Language Processing, Message-passing, Natural Languages, Neural Architectures, Network Architecture, Article, Computer Vision, Controlled Study, Graph Neural Network, Learning, Natural Language Processing, Nerve Cell Network
Subjects
Source
Publisher
Elsevier