# On Structural Expressive Power of Graph Transformers

arXiv: https://arxiv.org/abs/2305.13987 · HTML: https://mlsanity.com/paper/2305.13987/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 57 references that are in the map.
- First posted on arXiv 23 May 2023.

## Builds on (most cited first, 30 of 37)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [On Layer Normalization in the Transformer Architecture](https://mlsanity.com/paper/2002.04745/) (2020)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Global Self-Attention as a Replacement for Graph Convolution](https://mlsanity.com/paper/2108.03348/) (2021)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Building powerful and equivariant graph neural networks with structural message-passing](https://mlsanity.com/paper/2006.15107/) (2020)

## Built on by (most cited first, 19 of 19)

- [Comparing Graph Transformers via Positional Encodings](https://mlsanity.com/paper/2402.14202/) (2024)
- [Learning Long Range Dependencies on Graphs via Random Walks](https://mlsanity.com/paper/2406.03386/) (2024)
- [Towards A Universal Graph Structural Encoder](https://mlsanity.com/paper/2504.10917/) (2025)
- [Future Directions in the Theory of Graph Machine Learning](https://mlsanity.com/paper/2402.02287/) (2024)
- [NeuroPath: A Neural Pathway Transformer for Joining the Dots of Human Connectomes](https://mlsanity.com/paper/2409.17510/) (2024)
- [Powerformer: A Section-adaptive Transformer for Power Flow Adjustment](https://mlsanity.com/paper/2401.02771/) (2024)
- [Transformers are efficient hierarchical chemical graph learners](https://mlsanity.com/paper/2310.01704/) (2023)
- [NRFormer: Nationwide Nuclear Radiation Forecasting with Spatio-Temporal Transformer](https://mlsanity.com/paper/2410.11924/) (2024)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Inductive Link Prediction on N-ary Relational Facts via Semantic Hypergraph Reasoning](https://mlsanity.com/paper/2503.20676/) (2025)
- [Topology-guided Hypergraph Transformer Network: Unveiling Structural Insights for Improved Representation](https://mlsanity.com/paper/2310.09657/) (2023)
- [GraViti: Graph-Level Variational Autoencoders with Relaxed Permutation Invariance](https://mlsanity.com/paper/2605.16668/) (2026)
- [Towards Graph Prompt Learning: A Survey and Beyond](https://mlsanity.com/paper/2408.14520/) (2024)
- [A method for the systematic generation of graph XAI benchmarks via Weisfeiler-Leman coloring](https://mlsanity.com/paper/2505.12437/) (2025)
- [HeSRN: Representation Learning On Heterogeneous Graphs via Slot-Aware Retentive Network](https://mlsanity.com/paper/2510.09767/) (2025)
- [k-Maximum Inner Product Attention for Graph Transformers and the Expressive Power of GraphGPS](https://mlsanity.com/paper/2604.03815/) (2026)
- [Invariant-Based Weight Sharing for Message Passing](https://mlsanity.com/paper/2605.25750/) (2026)
- [A Weisfeiler-Leman Characterization of Global-Attention Graph Transformers for Mixed-Integer Linear Programs](https://mlsanity.com/paper/2607.17570/) (2026)
- [DBMol: Design of High-Affinity, Target-Specific Small Molecules through Structure Prediction Models](https://mlsanity.com/paper/2607.19237/) (2026)

## Abstract (arXiv)

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 SEG-WL test (Structural Encoding enhanced Global Weisfeiler-Lehman 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 (textitSPIS) 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.