Understanding Truncated Positional Encodings for Graph Neural Networks

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 random walk (polynomials of the adjacency matrix)---are theoretically equivalent in expressive power, and both are known to lie between the 1-WL and 3-WL tests in terms of expressivity. However, this equivalence assumes the GNN uses the "complete'' version of these PEs, which requires $O(n^3)$ time and space complexity. Practitioners therefore commonly use truncated variants of these encodings (e.g., the first $k$ eigenspaces or powers of 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.

Graph neural networks (GNNs) are machine learning models designed to make predictions about graph-structured data, such as molecules or relational databases. One trick to improve the performance of GNNs is to augment them with extra information called encodings about the position of nodes in the graph. Two of the most common pieces of positional information come from the graph's spectra or its distribution of random walks. In theory, if you use sufficiently large versions of these encodings, they are equally powerful. However, in practice, these large version are far too expensive to use, so people use only a fraction of this information. Our paper studies what happens in this more realistic truncated setting. We show that once these encodings are truncated, they carry very different information about the graph from one another, even if their full versions are theoretically equivalent. Motivated by this, we also study a family of spectral encodings called the k-harmonic distances and show that even closely related truncated encodings can capture different kinds of graph structure. Finally, our experiments suggest that the best practical strategy is often to combine several truncated encodings from different families rather than rely on just one.