# Benchmarking Positional Encodings for GNNs and Graph Transformers

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 45 references that are in the map.
- First posted on arXiv 19 Nov 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (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)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Representing Long-Range Context for Graph Neural Networks with Global Attention](https://mlsanity.com/paper/2201.08821/) (2022)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [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)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Global Self-Attention as a Replacement for Graph Convolution](https://mlsanity.com/paper/2108.03348/) (2021)
- [A Generalization of ViT/MLP-Mixer to Graphs](https://mlsanity.com/paper/2212.13350/) (2022)
- [Everything is Connected: Graph Neural Networks](https://mlsanity.com/paper/2301.08210/) (2023)
- [Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark](https://mlsanity.com/paper/2309.00367/) (2023)

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

- [Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence](https://mlsanity.com/paper/2502.09263/) (2025)
- [A Survey of Graph Transformers: Architectures, Theories and Applications](https://mlsanity.com/paper/2502.16533/) (2025)
- [Fixed Aggregation Features Can Rival GNNs](https://mlsanity.com/paper/2601.19449/) (2026)
- [CanonNet: Canonical Ordering and Curvature Learning for Point Cloud Analysis](https://mlsanity.com/paper/2504.02763/) (2025)
- [OpenGT: A Comprehensive Benchmark For Graph Transformers](https://mlsanity.com/paper/2506.04765/) (2025)
- [LEAP: Local ECT-Based Learnable Positional Encodings for Graphs](https://mlsanity.com/paper/2510.00757/) (2025)
- [From Message-Passing to Linearized Graph Sequence Models](https://mlsanity.com/paper/2605.12358/) (2026)
- [Feature Augmentation of GNNs for ILPs: Local Uniqueness Suffices](https://mlsanity.com/paper/2509.21000/) (2025)
- [NuBench: An Open Benchmark for Deep Learning-Based Event Reconstruction in Neutrino Telescopes](https://mlsanity.com/paper/2511.13111/) (2025)
- [Breaking the Bottlenecks: Scalable Diffusion Models for 3D Molecular Generation](https://mlsanity.com/paper/2601.08963/) (2026)
- [Graph Cascades: Contagion-Based Mesoscopic Rewiring for Structure-Aware Graph Machine Learning](https://mlsanity.com/paper/2606.05046/) (2026)
- [Do Geometry-Aware Positional Encodings Help Transformers in Spatial Imperfect-Information Games?](https://mlsanity.com/paper/2608.14982/) (2026)
- [Analytic-Walk Rotary Positional Encodings for Graphs](https://mlsanity.com/paper/2609.32178/) (2026)

## Abstract (arXiv)

Positional Encodings (PEs) are essential for injecting structural information into Graph Neural Networks (GNNs), particularly Graph Transformers, yet their empirical impact remains insufficiently understood. We introduce a unified benchmarking framework that decouples PEs from architectural choices, enabling a fair comparison across 8 GNN and Transformer models, 9 PEs, and 10 synthetic and real-world datasets. Across more than 500 model-PE-dataset configurations, we find that commonly used expressiveness proxies, including Weisfeiler-Lehman distinguishability, do not reliably predict downstream performance. In particular, highly expressive PEs frequently fail to improve, and can even degrade performance on real-world tasks. At the same time, we identify several simple and previously overlooked model-PE combinations that match or outperform recent state-of-the-art methods. Our results demonstrate the strong task-dependence of PEs and underscore the need for empirical validation beyond theoretical expressiveness. To support reproducible research, we release an open-source benchmarking framework for evaluating PEs for graph learning tasks.