# Understanding Truncated Positional Encodings for Graph Neural Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 47 references that are in the map.
- First posted on arXiv 11 Jun 2026.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (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)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [A Note on Over-Smoothing for Graph Neural Networks](https://mlsanity.com/paper/2006.13318/) (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)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants](https://mlsanity.com/paper/2201.07083/) (2022)
- [An Empirical Study of Realized GNN Expressiveness](https://mlsanity.com/paper/2304.07702/) (2023)
- [On the Stability of Expressive Positional Encodings for Graphs](https://mlsanity.com/paper/2310.02579/) (2023)
- [Comparing Graph Transformers via Positional Encodings](https://mlsanity.com/paper/2402.14202/) (2024)
- [Affinity-Aware Graph Networks](https://mlsanity.com/paper/2206.11941/) (2022)
- [1-WL Expressiveness Is (Almost) All You Need](https://mlsanity.com/paper/2202.10156/) (2022)
- [On the Expressive Power of Spectral Invariant Graph Neural Networks](https://mlsanity.com/paper/2406.04336/) (2024)
- [Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers](https://mlsanity.com/paper/2011.08806/) (2020)
- [Biharmonic Distance and the Performance of Second-Order Consensus Networks with Stochastic Disturbances](https://mlsanity.com/paper/1709.02790/) (2017)
- [Towards Stable, Globally Expressive Graph Representations with Laplacian Eigenvectors](https://mlsanity.com/paper/2410.09737/) (2024)
- [Generalizable Insights for Graph Transformers in Theory and Practice](https://mlsanity.com/paper/2511.08028/) (2025)

## Abstract (arXiv)

Positional encodings (PEs) enhance the power of graph neural networks (GNNs), both theoretically and empirically. Two of the most popular families of PEs - spectral (e.g., Laplacian eigenspaces, effective resistance) and walk-based (polynomials of the adjacency matrix) - are theoretically equivalent in expressive power, with expressivity between the 1-WL and 3-WL tests. However, this equivalence assumes the GNN uses the "complete" version of these PEs, which requires O(n3) time and space complexity. Instead, practitioners commonly use truncated variants of these encodings, such as the first k eigenspaces or powers of the adjacency matrix. However, the theoretical properties of these truncated PEs are unknown. In this work, we initiate the study of these truncated PEs. Theoretically, we show that, under truncation, several families of PEs are fundamentally different in expressive power. As a corollary, we show that truncated spectral PEs are no longer stronger than the 1-WL test. We also study a family of spectral PEs, the k-harmonic distances, to highlight the differences in expressive power of even closely related truncated PEs. Finally, we experimentally show that a mix of truncated PEs is preferable to any single family on real-world datasets.