  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}.
