Research map / Graph learning / GNN architectures
On the Stability of Expressive Positional Encodings for Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical analysis of Laplacian-eigenvector positional encodings showing that expressive PE functions of eigenspace-invariant (sign/basis-invariant) inputs can universally approximate all invariant functions, and that the resulting encodings are Hölder continuous (stable) with respect to the input Laplacian.
Problem
Laplacian eigenvector positional encodings suffer from non-uniqueness (many eigendecompositions of the same Laplacian) and instability (small Laplacian perturbations can cause large changes in eigenvectors, especially with close eigenvalues), which hurts expressive power and robustness of graph tran
Approach
Model PEs as functions of spectral projection matrices X diag(psi(Lambda)) X^T, which are invariant to eigenvector sign/basis choice within eigenspaces; prove universal approximation over orthogonally invariant functions and derive Hölder stability bounds for the resulting PE, with a dependence on the eigengap.
Key results
- Proves every positional encoding of the form PE(L)=phi(X psi(Lambda) X^T,...) with Lipschitz/continuous components is Hölder continuous in the Laplacian, with exponent 1/2 for large perturbations and linear dependence on the Frobenius distance divided by the eigengap.
- Shows that the class of spectral PEs built from spectral projectors is universal over eigenspace-orthogonally-invariant functions of the eigendecomposition.
Limitations
- Results are purely theoretical with no empirical experiments reported in the provided text
- Stability bound depends on the eigengap, which can be small, making the bound loose
Experimental setup
Builds on: Davis-Kahan theorem Weyl's inequality Hoffman-Wielandt inequality
Closest papers by meaning
- Learning Efficient Positional Encodings with Graph Neural Networks (ICLR 2025 · similarity 0.92)
- Positional Encoding meets Persistent Homology on Graphs (ICML 2025 · similarity 0.91)
- What Are Good Positional Encodings for Directed Graphs? (ICLR 2025 · similarity 0.89)
- Homomorphism Counts as Structural Encodings for Graph Learning (ICLR 2025 · similarity 0.89)
- Graph Positional and Structural Encoder (ICML 2024 · similarity 0.89)
- Aligning Transformers with Weisfeiler-Leman (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.