Understanding Truncated Positional Encodings for Graph Neural Networks

AI summary

Overview

Research area: Graph machine learning — specifically the expressive power of positional encodings (PEs) used in graph neural networks and graph transformers.

Technical level: Advanced. The paper assumes familiarity with the Weisfeiler-Lehman (WL) hierarchy, spectral graph theory (Laplacian eigenvalues, eigenspace projections, pseudoinverse), and graph transformer architectures.

Scope: A theoretical and empirical study of what happens to the expressive power of spectral and walk-based positional encodings when they are truncated to a fixed size, plus experiments on BREC and ZINC-12k showing that mixtures of truncated PEs outperform any single family.

What This Paper Is About

Spectral PEs (built from Laplacian eigenspaces or effective resistance) and walk-based PEs (powers of the adjacency matrix) are known to have equivalent expressive power in their "complete" form, but that form costs O(n³) time and space. In practice, people use truncated variants — the first k eigenspaces, the first k powers of the adjacency matrix — and nobody had characterized what those truncated versions can and cannot distinguish. This paper proves that truncated PEs from different families are fundamentally different in power, that some truncated spectral PEs drop below the 1-WL test, and that combining PEs from multiple families works better empirically than any single one.

Key Contributions

1. First theory of truncated PEs. The authors show that truncated spectral and walk encodings have very different expressive power: a constant-sized version of one family can distinguish graphs that an Ω(n)-sized version of the other cannot, and an Ω(n)-sized spectral encoding can be less expressive than the 1-WL test (Theorem 4.1, Theorem 4.2). This makes truncated PEs incomparable to the WL hierarchy rather than nested within it.

2. A negative result for effective resistance on weighted graphs. Effective resistance (the Resistance-WL test) is shown to be weaker than both eigenspace projections and walk PEs on weighted graphs (Theorem 4.3, Corollary 4.1), and it is not stronger than the weighted analogue of the 1-WL test. This disproves two conjectures from Zhang et al. (2023): that Resistance-WL is stronger than the shortest-path-WL test, and that it encodes the entire spectrum of the graph.

3. A systematic study of k-harmonic distances. The paper proves that Θ(n) k-harmonic distances match the expressive power of the complete spectral and walk encodings, specifically that the [2n]-harmonic WL test is as strong as EP-WL (Theorem 4.6). It also exhibits a gap within the family — Sparse-Biharmonic-WL can separate some graph pairs in one iteration that Sparse-Resistance-WL cannot separate in o(n) iterations (Theorem 4.7) — while showing that if one k-harmonic distance separates a pair of graphs, all but O(n⁵) values of k′ do so as well (Theorem 4.8).

4. An empirical case for mixing PEs. On BREC and ZINC-12k, a mix of truncated PEs from different families beats any single family, and a single k-harmonic channel achieves competitive accuracy at lower dimensionality than stacked eigenspace projections.

Main Findings

• Truncated spectral PEs can be weaker than 1-WL. There exist pairs of n-vertex graphs distinguishable by the 1-WL test but indistinguishable by k-EP-WL for k ∈ Ω(n

Authors’ 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. 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.