On the theoretical expressive power of graph transformers for solving graph problems

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.