  Graph Transformers (GTs) have significantly advanced the field of graph
representation learning by overcoming the limitations of message-passing graph
neural networks (GNNs) and demonstrating promising performance and expressive
power. However, the quadratic complexity of self-attention mechanism in GTs has
limited their scalability, and previous approaches to address this issue often
suffer from expressiveness degradation or lack of versatility. To address this
issue, we propose AnchorGT, a novel attention architecture for GTs with global
receptive field and almost linear complexity, which serves as a flexible
building block to improve the scalability of a wide range of GT models.
Inspired by anchor-based GNNs, we employ structurally important $k$-dominating
node set as anchors and design an attention mechanism that focuses on the
relationship between individual nodes and anchors, while retaining the global
receptive field for all nodes. With its intuitive design, AnchorGT can easily
replace the attention module in various GT models with different network
architectures and structural encodings, resulting in reduced computational
overhead without sacrificing performance. In addition, we theoretically prove
that AnchorGT attention can be strictly more expressive than Weisfeiler-Lehman
test, showing its superiority in representing graph structures. Our experiments
on three state-of-the-art GT models demonstrate that their AnchorGT variants
can achieve better results while being faster and significantly more memory
efficient.
