On the Theoretical Expressive Power and the Design Space of Higher-Order Graph Transformers

Understand

Graph transformers have recently received significant attention in graph learning, partly due to their ability to capture more global interaction via self-attention.

• Nevertheless, while higher-order graph neural networks have been reasonably well studied, the exploration of extending graph transformers to higher-order variants is just starting.
• Both theoretical understanding and empirical results are limited.
• In this paper, we provide a systematic study of the theoretical expressive power of order-$k$ graph transformers and sparse variants.