On Structural Expressive Power of Graph Transformers
Wenhao Zhu Tianyu Wen Guojie Song Liang Wang Bo Zheng
Graph Transformer has recently received wide attention in the research
community with its outstanding performance, yet its structural expressive power
has not been well analyzed. Inspired by the connections between
Weisfeiler-Lehman (WL) graph isomorphism test and graph neural network (GNN),
we introduce \textbf{SEG-WL test} (\textbf{S}tructural \textbf{E}ncoding
enhanced \textbf{G}lobal \textbf{W}eisfeiler-\textbf{L}ehman test), a
generalized graph isomorphism test algorithm as a powerful theoretical tool for
exploring the structural discriminative power of graph Transformers. We
theoretically prove that the SEG-WL test is an expressivity upper bound on a
wide range of graph Transformers, and the representational power of SEG-WL test
can be approximated by a simple Transformer network arbitrarily under certain
conditions. With the SEG-WL test, we show how graph Transformers' expressive
power is determined by the design of structural encodings, and present
conditions that make the expressivity of graph Transformers beyond WL test and
GNNs. Moreover, motivated by the popular shortest path distance encoding, we
follow the theory-oriented principles and develop a provably stronger
structural encoding method, Shortest Path Induced Subgraph (\textit{SPIS})
encoding. Our theoretical findings provide a novel and practical paradigm for
investigating the expressive power of graph Transformers, and extensive
synthetic and real-world experiments empirically verify the strengths of our
proposed methods.