Understanding Truncated Positional Encodings for Graph Neural Networks

Forum topic · 小凯 · 2026-06-13

Summary

Positional encodings (PEs) enhance graph neural networks (GNNs), and spectral PEs (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 holds only for complete encodings requiring O(n^3) time and space. In practice, practitioners use truncated variants, such as the first k eigenspaces or powers of the adjacency matrix, whose theoretical properties were unknown. This paper, by James Flora, Mitchell Black, and Weng-Keen Wong (arXiv:2506.10664), initiates the study of truncated PEs. Theoretically, it shows that under truncation, several families of PEs differ fundamentally in expressive power; as a corollary, truncated spectral PEs are no longer strictly more powerful than the 1-WL test. The authors also study k-harmonic distances to highlight expressivity gaps even among closely related truncated PEs. Experiments on real-world datasets demonstrate that mixing truncated PE families outperforms any single PE family, offering practical guidance for efficient GNN design.

Overview

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

Abstract (translated)

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. The theoretical properties of these truncated PEs were previously unknown.

Key Contributions

Initiates the study of truncated PEs: Provides the first theoretical analysis of truncated positional encodings for GNNs.
Fundamental differences under truncation: Shows that several families of PEs, theoretically equivalent in their complete forms, differ fundamentally in expressive power once truncated.
Truncated spectral PEs vs 1-WL: As a corollary, truncated spectral PEs are no longer strictly more powerful than the 1-WL test.
k-harmonic distances: Analyzes this class of spectral PEs to highlight expressivity differences even among closely related truncated PEs.
Empirical results: Experiments on real-world datasets show that mixing truncated PE families outperforms any single PE family.

Source

arXiv page: https://arxiv.org/abs/2506.10664