Understanding Truncated Positional Encodings for Graph Neural Networks

Forum topic · 小凯 · 2026-06-13

Summary

Positional encodings (PEs) boost the expressive power of graph neural networks (GNNs). The two most popular families—spectral PEs (e.g., Laplacian eigenspaces, effective resistance) and walk-based PEs (polynomials of the adjacency matrix)—are theoretically equivalent, with expressivity between the 1-WL and 3-WL tests. However, this equivalence assumes complete PEs requiring O(n^3) time and space, whereas practitioners typically use truncated variants such as the first k eigenspaces or low powers of the adjacency matrix. This paper by James Flora, Mitchell Black, and Weng-Keen Wong (arXiv:2506.10664, June 2025) initiates the theoretical study of truncated PEs. The authors show that under truncation, the different PE families become fundamentally different in expressive power; in particular, truncated spectral PEs are no longer strictly more powerful than the 1-WL test. They also analyze k-harmonic distances to highlight expressivity gaps among closely related truncated spectral PEs. Experiments on real-world datasets show that mixing truncated PE families outperforms any single family, offering practical guidance for GNN design under compute constraints.

Paper Overview

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

Theoretical separation under truncation: While complete spectral and walk-based PEs are equivalent in expressive power, the paper shows that once truncated, several families of PEs differ fundamentally in what they can express.
Truncated spectral PEs vs. 1-WL: As a corollary, truncated spectral PEs are no longer guaranteed to be strictly more powerful than the 1-WL test.
k-harmonic distances: The authors study a family of spectral PEs, k-harmonic distances, to highlight expressivity differences even among closely related truncated spectral PEs.
Practical recommendation: Experiments on real-world datasets demonstrate that combining (mixing) truncated PE families outperforms using any single PE family alone.

Takeaway

The equivalence results established for complete positional encodings do not carry over to the truncated versions used in practice. This work provides the first theoretical framework for reasoning about truncated PEs and suggests practitioners should mix PE families rather than rely on a single truncated encoding.

--- *Auto-collected on 2026-06-13*