On the Stability of Expressive Positional Encodings for Graphs
This addresses a fundamental issue in graph neural networks for researchers and practitioners, offering a stable and expressive solution for tasks like molecular property prediction, though it is incremental as it builds on existing positional encoding methods.
The paper tackled the problem of instability in positional encodings for graphs, which arises from small perturbations to the Laplacian, by introducing Stable and Expressive Positional Encodings (SPE) that use eigenvalues to softly partition eigenspaces, resulting in improved generalization on molecular property prediction and out-of-distribution tasks compared to existing methods.
Designing effective positional encodings for graphs is key to building powerful graph transformers and enhancing message-passing graph neural networks. Although widespread, using Laplacian eigenvectors as positional encodings faces two fundamental challenges: (1) \emph{Non-uniqueness}: there are many different eigendecompositions of the same Laplacian, and (2) \emph{Instability}: small perturbations to the Laplacian could result in completely different eigenspaces, leading to unpredictable changes in positional encoding. Despite many attempts to address non-uniqueness, most methods overlook stability, leading to poor generalization on unseen graph structures. We identify the cause of instability to be a ``hard partition'' of eigenspaces. Hence, we introduce Stable and Expressive Positional Encodings (SPE), an architecture for processing eigenvectors that uses eigenvalues to ``softly partition'' eigenspaces. SPE is the first architecture that is (1) provably stable, and (2) universally expressive for basis invariant functions whilst respecting all symmetries of eigenvectors. Besides guaranteed stability, we prove that SPE is at least as expressive as existing methods, and highly capable of counting graph structures. Finally, we evaluate the effectiveness of our method on molecular property prediction, and out-of-distribution generalization tasks, finding improved generalization compared to existing positional encoding methods. Our code is available at \url{https://github.com/Graph-COM/SPE}.