Recently, transformer architectures for graphs emerged as an alternative to established techniques for machine learning with graphs, such as graph neural networks. So far, they have shown promising empirical results, e.g., on molecular prediction datasets, often attributed to their ability to circumvent graph neural networks' shortcomings, such as over-smoothing and over-squashing. Here, we derive a taxonomy of graph transformer architectures, bringing some order to this emerging field. We overview their theoretical properties, survey structural and positional encodings, and discuss extensions for important graph classes, e.g., 3D molecular graphs. Empirically, we probe how well graph transformers can recover various graph properties, how well they can deal with heterophilic graphs, and to what extent they prevent over-squashing. Further, we outline open challenges and research direction to stimulate future work. Our code is available at https://github.com/luis-mueller/probing-graph-transformers.

翻译：最近,图表变压器结构的出现替代了以图形神经网络等图形进行机器学习的既定技术,到目前为止,这些变压器结构显示了很有希望的经验性结果,例如分子预测数据集,往往归因于它们能够绕过图形神经网络的缺点,例如过度吸附和过度隔热。在这里,我们从图形变压器结构的分类学中得出一个图表变压器结构的分类学,为这个新兴领域带来一些秩序。我们概述了它们的理论特性、调查结构和定位编码,并讨论了重要图表类的扩展,例如3D分子图。我们研究图变压器如何很好地恢复各种图形特性,它们如何很好地处理外科生物学图,以及它们在多大程度上防止过热。此外,我们概述了公开的挑战和研究方向,以刺激未来的工作。我们的代码可以在 https://github.com/luis-mueller/ probing-traction-tratrafers。