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

arXiv:2404.03380v1 Announce Type: new
Abstract: 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. We first …

abstract arxiv attention cs.cg cs.lg design exploration global graph graph learning graph neural networks networks neural networks power self-attention space transformers type variants via