Paper Overview
Field: 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. The theoretical properties of these truncated PEs were previously unknown. This work initiates the study of truncated PEs.
Key Findings
- Fundamental divergence under truncation: Several PE families that are theoretically equivalent in their complete form become fundamentally different in expressive power once truncated.
- Corollary on spectral PEs: Truncated spectral PEs are no longer more expressive than the 1-WL test.
- Case study — k-harmonic distance: The authors study this spectral PE to highlight expressivity differences even between closely related truncated PEs.
- Empirical result: Experiments on real-world datasets show that mixing truncated PE families outperforms any single PE family.
Why It Matters
Because full PEs are computationally prohibitive at \(O(n^3)\) cost, most practical GNN systems rely on truncated encodings. This paper provides the first theoretical grounding for that common practice, clarifying what expressive power practitioners actually sacrifice (or gain) when truncating, and motivating hybrid PE approaches.
---
*Auto-collected on 2026-06-14*