Understanding Truncated Positional Encodings for Graph Neural Networks

James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:31161-31188, 2026.

Abstract

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 random walk (polynomials of the adjacency matrix)—are theoretically equivalent in expressive power, and both are known to lie between the 1-WL and 3-WL tests in terms of expressivity. However, this equivalence assumes the GNN uses the "complete” version of these PEs, which requires $O(n^3)$ time and space complexity. Practitioners therefore commonly use truncated variants of these encodings (e.g., the first $k$ eigenspaces or powers of 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-flora26a, title = {Understanding Truncated Positional Encodings for Graph Neural Networks}, author = {Flora, James and Black, Mitchell and Wong, Weng-Keen and Nayyeri, Amir}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {31161--31188}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/flora26a/flora26a.pdf}, url = {https://proceedings.mlr.press/v306/flora26a.html}, abstract = {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 random walk (polynomials of the adjacency matrix)—are theoretically equivalent in expressive power, and both are known to lie between the 1-WL and 3-WL tests in terms of expressivity. However, this equivalence assumes the GNN uses the "complete” version of these PEs, which requires $O(n^3)$ time and space complexity. Practitioners therefore commonly use truncated variants of these encodings (e.g., the first $k$ eigenspaces or powers of 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.} }
Endnote
%0 Conference Paper %T Understanding Truncated Positional Encodings for Graph Neural Networks %A James Flora %A Mitchell Black %A Weng-Keen Wong %A Amir Nayyeri %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-flora26a %I PMLR %P 31161--31188 %U https://proceedings.mlr.press/v306/flora26a.html %V 306 %X 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 random walk (polynomials of the adjacency matrix)—are theoretically equivalent in expressive power, and both are known to lie between the 1-WL and 3-WL tests in terms of expressivity. However, this equivalence assumes the GNN uses the "complete” version of these PEs, which requires $O(n^3)$ time and space complexity. Practitioners therefore commonly use truncated variants of these encodings (e.g., the first $k$ eigenspaces or powers of 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.
APA
Flora, J., Black, M., Wong, W. & Nayyeri, A.. (2026). Understanding Truncated Positional Encodings for Graph Neural Networks. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:31161-31188 Available from https://proceedings.mlr.press/v306/flora26a.html.

Related Material