# Comparing Graph Transformers via Positional Encodings

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 41 references that are in the map.
- First posted on arXiv 22 Feb 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [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)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Graph Inductive Biases in Transformers without Message Passing](https://mlsanity.com/paper/2305.17589/) (2023)
- [GraphiT: Encoding Graph Structure in Transformers](https://mlsanity.com/paper/2106.05667/) (2021)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Attending to Graph Transformers](https://mlsanity.com/paper/2302.04181/) (2023)
- [A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants](https://mlsanity.com/paper/2201.07083/) (2022)
- [Transformers Meet Directed Graphs](https://mlsanity.com/paper/2302.00049/) (2023)
- [From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers](https://mlsanity.com/paper/2107.07999/) (2021)
- [An Empirical Study of Realized GNN Expressiveness](https://mlsanity.com/paper/2304.07702/) (2023)
- [Magnetic Eigenmaps for the Visualization of Directed Networks](https://mlsanity.com/paper/1606.08266/) (2016)
- [Fine-grained Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2306.03698/) (2023)
- [Edgeformers: Graph-Empowered Transformers for Representation Learning on Textual-Edge Networks](https://mlsanity.com/paper/2302.11050/) (2023)
- [On Structural Expressive Power of Graph Transformers](https://mlsanity.com/paper/2305.13987/) (2023)
- [Weisfeiler-Lehman meets Gromov-Wasserstein](https://mlsanity.com/paper/2202.02495/) (2022)
- [Three iterations of (d-1)-WL test distinguish non isometric clouds of d-dimensional points](https://mlsanity.com/paper/2303.12853/) (2023)
- [The Weisfeiler-Lehman Distance: Reinterpretation and Connection with GNNs](https://mlsanity.com/paper/2302.00713/) (2023)

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

- [Relational Transformer: Toward Zero-Shot Foundation Models for Relational Data](https://mlsanity.com/paper/2510.06377/) (2025)
- [Learning Efficient Positional Encodings with Graph Neural Networks](https://mlsanity.com/paper/2502.01122/) (2025)
- [A Survey of Graph Transformers: Architectures, Theories and Applications](https://mlsanity.com/paper/2502.16533/) (2025)
- [Benchmarking Positional Encodings for GNNs and Graph Transformers](https://mlsanity.com/paper/2411.12732/) (2024)
- [What Are Good Positional Encodings for Directed Graphs?](https://mlsanity.com/paper/2407.20912/) (2024)
- [CKGConv: General Graph Convolution with Continuous Kernels](https://mlsanity.com/paper/2404.13604/) (2024)
- [Homomorphism Expressivity of Spectral Invariant Graph Neural Networks](https://mlsanity.com/paper/2503.00485/) (2025)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [A Hierarchical Language Model For Interpretable Graph Reasoning](https://mlsanity.com/paper/2410.22372/) (2024)
- [Plain Transformers Can be Powerful Graph Learners](https://mlsanity.com/paper/2504.12588/) (2025)
- [Graph Transformers Dream of Electric Flow](https://mlsanity.com/paper/2410.16699/) (2024)
- [Generalizable Insights for Graph Transformers in Theory and Practice](https://mlsanity.com/paper/2511.08028/) (2025)
- [Graph Inference with Effective Resistance Queries](https://mlsanity.com/paper/2502.18350/) (2025)
- [Few-shot Learning on AMS Circuits and Its Application to Parasitic Capacitance Prediction](https://mlsanity.com/paper/2507.06538/) (2025)
- [From Small to Large: Generalization Bounds for Transformers on Variable-Size Inputs](https://mlsanity.com/paper/2512.12805/) (2025)
- [Size-Transferability of Graph Transformers with Convolutional Positional Encodings](https://mlsanity.com/paper/2602.15239/) (2026)
- [Understanding Truncated Positional Encodings for Graph Neural Networks](https://mlsanity.com/paper/2606.13671/) (2026)
- [A Weisfeiler-Leman Characterization of Global-Attention Graph Transformers for Mixed-Integer Linear Programs](https://mlsanity.com/paper/2607.17570/) (2026)
- [Do Geometry-Aware Positional Encodings Help Transformers in Spatial Imperfect-Information Games?](https://mlsanity.com/paper/2608.14982/) (2026)
- [Converse and Collision-Based Achievability for Node Localization with Hybrid Distance-Spectral Graph Positional Encodings](https://mlsanity.com/paper/2608.30152/) (2026)

## Abstract (arXiv)

The distinguishing power of graph transformers is closely tied to the choice of positional encoding: features used to augment the base transformer with information about the graph. There are two primary types of positional encoding: absolute positional encodings (APEs) and relative positional encodings (RPEs). APEs assign features to each node and are given as input to the transformer. RPEs instead assign a feature to each pair of nodes, e.g., graph distance, and are used to augment the attention block. A priori, it is unclear which method is better for maximizing the power of the resulting graph transformer. In this paper, we aim to understand the relationship between these different types of positional encodings. Interestingly, we show that graph transformers using APEs and RPEs are equivalent in terms of distinguishing power. In particular, we demonstrate how to interchange APEs and RPEs while maintaining their distinguishing power in terms of graph transformers. Based on our theoretical results, we provide a study on several APEs and RPEs (including the resistance distance and the recently introduced stable and expressive positional encoding (SPE)) and compare their distinguishing power in terms of transformers. We believe our work will help navigate the huge number of choices of positional encoding and will provide guidance on the future design of positional encodings for graph transformers.