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.

设计有效的位置编码对于构建强大的图形变压器和增强消息传递图神经网络至关重要。我们提出了稳定且表达能力强的位置编码（SPE），它是第一个经过验证的稳定架构，同时尊重特征向量的所有对称性，并且至少与现有方法一样具有表达能力，对于基础不变函数非常强大，同时在分子属性预测和超出分布泛化任务上表现出改进的泛化性能。