English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original

Understanding Truncated Positional Encodings for Graph Neural Networks

Forum topic · 小凯 · 2026-06-14

Summary

This paper (arXiv 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 equivalent in expressive power when used in full, falling between the 1-WL and 3-WL tests—but the complete versions require O(n^3) time and space. Practitioners therefore use 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 become fundamentally different in expressive power. As a corollary, truncated spectral PEs are no longer more expressive than the 1-WL test. They also study k-harmonic distance, a spectral PE, 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.

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*

Tags

#graph-neural-networks#positional-encodings#expressivity#spectral-methods#weisfeiler-leman#machine-learning#arxiv

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/177981276