Understanding Truncated Positional Encodings for Graph Neural Networks

Forum topic · 小凯 · 2026-06-14

Summary

This arXiv paper (2506.10664) by James Flora, Mitchell Black, and Weng-Keen Wong initiates the theoretical study of truncated positional encodings (PEs) for graph neural networks (GNNs). Spectral PEs (e.g., Laplacian eigenspaces, effective resistance) and walk-based PEs (polynomials of the adjacency matrix) are known to be theoretically equivalent in expressive power, falling between the 1-WL and 3-WL tests—but only when their complete O(n^3) versions are used. In practice, practitioners rely on truncated variants, such as the first k eigenspaces or low powers of the adjacency matrix, whose theoretical properties were previously unknown. The authors show that under truncation, different PE families diverge fundamentally in expressive power. As a corollary, truncated spectral PEs are no longer more powerful than the 1-WL test. They also study a family of spectral PEs called k-harmonic distances, highlighting expressive power gaps even among closely related truncated PEs. Experiments on real-world datasets show that mixing truncated PEs from different families outperforms any single PE family.

Research area: Machine Learning Authors: James Flora, Mitchell Black, Weng-Keen Wong Published: 2025-06-13 arXiv: 2506.10664

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 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(n^3)$$ 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, the authors initiate the study of these truncated PEs.

Key Points

Spectral and walk-based PEs are theoretically equivalent only in their complete, $$O(n^3)$$ forms; real-world usage almost always involves truncated variants.
Under truncation, several families of PEs become fundamentally different in expressive power.
As a corollary, truncated spectral PEs are no longer more powerful than the 1-WL test.
The paper studies $$k$$ -harmonic distances as a family of spectral PEs, showing expressive power differences even between closely related truncated PEs.
Experiments on real-world datasets demonstrate that mixing truncated PEs outperforms any single PE family.

Original 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 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(n^3)$$ 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, w...

Paper link: https://arxiv.org/abs/2506.10664