SCGT: Toward Scalable and Comprehensive Graph Transformer.

Graph Transformers (GTs) have shown great potential in graph representation learning over the past few years. In spite of their promising performance on small graphs, how to develop a scalable and powerful architecture still remains to be explored. While some of the existing works devote to designing linear attention mechanisms, the expressiveness is confined by their smooth attention score distributions. Another impact factor of expressiveness is the inductive bias. Unfortunately, GTs generally lack strong graph-specific inductive bias, which leads to failure in capturing long-range hierarchical structures or community structures. To address the issues above, we develop a Scalable and Comprehensive Graph Transformer (SCGT). Specifically, we leverage a Focused Graph Linear Attention (FGLA) to generate a sharp distribution of attention scores. In addition, we design a Comprehensive Positional Encoding (CPE) to capture comprehensive awareness of the original node-level features. Extensive empirical results show that SCGT achieves highly competitive performance with decent efficiency on 12 datasets. Theoretical analysis demonstrates the expressiveness of our proposed method.