Search papers, labs, and topics across Lattice.
This paper investigates the theoretical implications of truncated positional encodings (PEs) in graph neural networks (GNNs), revealing that truncation fundamentally alters their expressive power. The authors demonstrate that truncated spectral PEs do not exceed the capabilities of the 1-WL test, contrasting with the complete versions that are theoretically equivalent to the 3-WL test. Empirical results further indicate that a combination of truncated PEs outperforms any single family on real-world datasets, suggesting a more nuanced approach to encoding in GNNs.
Truncated positional encodings in GNNs can drastically change their expressive capabilities, with mixed encodings outperforming single families on real-world tasks.
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.
