# Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks

arXiv: https://arxiv.org/abs/2203.00199 · HTML: https://mlsanity.com/paper/2203.00199/

## Key facts

- Cited by 94 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 63 references that are in the map.
- First posted on arXiv 1 Mar 2022.

## Builds on (most cited first, 30 of 44)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [E(n) Equivariant Graph Neural Networks](https://mlsanity.com/paper/2102.09844/) (2021)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [Inductive Relation Prediction by Subgraph Reasoning](https://mlsanity.com/paper/1911.06962/) (2019)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks](https://mlsanity.com/paper/2101.05974/) (2021)

## Built on by (most cited first, 30 of 94)

- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Graph Inductive Biases in Transformers without Message Passing](https://mlsanity.com/paper/2305.17589/) (2023)
- [Let Your Graph Do the Talking: Encoding Structured Data for LLMs](https://mlsanity.com/paper/2402.05862/) (2024)
- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [Graph Mamba: Towards Learning on Graphs with State Space Models](https://mlsanity.com/paper/2402.08678/) (2024)
- [Attending to Graph Transformers](https://mlsanity.com/paper/2302.04181/) (2023)
- [DRew: Dynamically Rewired Message Passing with Delay](https://mlsanity.com/paper/2305.08018/) (2023)
- [Graph Neural Networks for Link Prediction with Subgraph Sketching](https://mlsanity.com/paper/2209.15486/) (2022)
- [Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking](https://mlsanity.com/paper/2306.10453/) (2023)
- [Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing](https://mlsanity.com/paper/2302.01524/) (2023)
- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Position: Topological Deep Learning is the New Frontier for Relational Learning](https://mlsanity.com/paper/2402.08871/) (2024)
- [Provably expressive temporal graph networks](https://mlsanity.com/paper/2209.15059/) (2022)
- [Transformers Meet Directed Graphs](https://mlsanity.com/paper/2302.00049/) (2023)
- [OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs](https://mlsanity.com/paper/2205.15117/) (2022)
- [Graph Positional and Structural Encoder](https://mlsanity.com/paper/2307.07107/) (2023)
- [On the Stability of Expressive Positional Encodings for Graphs](https://mlsanity.com/paper/2310.02579/) (2023)
- [Networked Time Series Imputation via Position-aware Graph Enhanced Variational Autoencoders](https://mlsanity.com/paper/2305.18612/) (2023)
- [Graph Positional Encoding via Random Feature Propagation](https://mlsanity.com/paper/2303.02918/) (2023)
- [Learning Domain-Independent Heuristics for Grounded and Lifted Planning](https://mlsanity.com/paper/2312.11143/) (2023)
- [Revisiting Link Prediction: A Data Perspective](https://mlsanity.com/paper/2310.00793/) (2023)
- [GPS++: An Optimised Hybrid MPNN/Transformer for Molecular Property Prediction](https://mlsanity.com/paper/2212.02229/) (2022)
- [The Expressive Power of Graph Neural Networks: A Survey](https://mlsanity.com/paper/2308.08235/) (2023)
- [A Canonicalization Perspective on Invariant and Equivariant Learning](https://mlsanity.com/paper/2405.18378/) (2024)
- [A Survey on Spectral Graph Neural Networks](https://mlsanity.com/paper/2302.05631/) (2023)
- [Unifying Generation and Prediction on Graphs with Latent Graph Diffusion](https://mlsanity.com/paper/2402.02518/) (2024)
- [Learning Efficient Positional Encodings with Graph Neural Networks](https://mlsanity.com/paper/2502.01122/) (2025)
- [Data-centric Graph Learning: A Survey](https://mlsanity.com/paper/2310.04987/) (2023)
- [Generalized Laplacian Positional Encoding for Graph Representation Learning](https://mlsanity.com/paper/2210.15956/) (2022)

## Abstract (arXiv)

Graph neural networks (GNN) have shown great advantages in many graph-based learning tasks but often fail to predict accurately for a task-based on sets of nodes such as link/motif prediction and so on. Many works have recently proposed to address this problem by using random node features or node distance features. However, they suffer from either slow convergence, inaccurate prediction, or high complexity. In this work, we revisit GNNs that allow using positional features of nodes given by positional encoding (PE) techniques such as Laplacian Eigenmap, Deepwalk, etc. GNNs with PE often get criticized because they are not generalizable to unseen graphs (inductive) or stable. Here, we study these issues in a principled way and propose a provable solution, a class of GNN layers termed PEG with rigorous mathematical analysis. PEG uses separate channels to update the original node features and positional features. PEG imposes permutation equivariance w.r.t. the original node features and imposes O(p) (orthogonal group) equivariance w.r.t. the positional features simultaneously, where p is the dimension of used positional features. Extensive link prediction experiments over 8 real-world networks demonstrate the advantages of PEG in generalization and scalability.