• On the theoretical expressive...

Treffer: On the theoretical expressive power of graph transformers for solving graph problems.

Title:
On the theoretical expressive power of graph transformers for solving graph problems.
Authors:
Nikolentzos G; Department of Informatics and Telecommunications, University of Peloponnese, Akadimaikou G.K. Vlachou Street, Tripoli, 22131, Greece. Electronic address: nikolentzos@uop.gr., Kelesis D; Institute of Informatics and Telecommunications, NCSR 'Demokritos', Patriarhou Gregoriou and Neapoleos St., Aghia Paraskevi, Athens, 15341, Greece. Electronic address: dkelesis@iit.demokritos.gr., Vazirgiannis M; LIX, Ecole Polytechnique, IP Paris, 1 Rue Honore d'Estienne d'Orves, Palaiseau, 91120, France; Mohamed bin Zayed University of Artificial Intelligence, Masdar City, Abu Dhabi, SE4505, the United Arab Emirates. Electronic address: mvazirg@lix.polytechnique.fr.
Source:
Neural networks : the official journal of the International Neural Network Society [Neural Netw] 2026 Feb; Vol. 194, pp. 108112. Date of Electronic Publication: 2025 Sep 16.
Publication Type:
Journal Article
Language:
English
Journal Info:
Publisher: Pergamon Press Country of Publication: United States NLM ID: 8805018 Publication Model: Print-Electronic Cited Medium: Internet ISSN: 1879-2782 (Electronic) Linking ISSN: 08936080 NLM ISO Abbreviation: Neural Netw Subsets: MEDLINE
Imprint Name(s):
Original Publication: New York : Pergamon Press, [c1988-
MeSH Terms:
Neural Networks, Computer* , Computer Graphics* , Problem Solving* , Natural Language Processing*, Algorithms ; Humans
Contributed Indexing:
Keywords: Congested clique; Expressive power; Graph problems; Graph transformers
Entry Date(s):
Date Created: 20250921 Date Completed: 20251216 Latest Revision: 20251216
Update Code:
20251216
DOI:
10.1016/j.neunet.2025.108112
PMID:
40975929
Database:
MEDLINE

Weitere Informationen

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.
(Copyright © 2025 The Author(s). Published by Elsevier Ltd.. All rights reserved.)

Declaration of competing interest The authors declare the following financial interests/personal relationships which may be considered as potential competing interests: Dimitrios Kelesis reports financial support was provided by Hellenic Foundation for Research and Innovation (HFRI). If there are other authors, they declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.