Understanding Truncated Positional Encodings for Graph Neural Networks
For practitioners using GNNs with positional encodings, this work reveals that common truncation choices significantly affect expressive power, guiding better design of PEs.
The paper studies truncated positional encodings (PEs) for graph neural networks, showing that under truncation, different families of PEs (spectral vs. walk-based) have fundamentally different expressive power, and truncated spectral PEs are no stronger than the 1-WL test. Experiments on real-world datasets show that a mix of truncated PEs outperforms any single family.
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, we show that, under truncation, several families of PEs are fundamentally different in expressive power. As a corollary, we show that truncated spectral PEs are no longer stronger than the 1-WL test. We also study a family of spectral PEs, the $k$-harmonic distances, to highlight the differences in expressive power of even closely related truncated PEs. Finally, we experimentally show that a mix of truncated PEs is preferable to any single family on real-world datasets.