# Graph Positional Encoding via Random Feature Propagation

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 75 references that are in the map.
- First posted on arXiv 6 Mar 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [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)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)

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

- [On the Stability of Expressive Positional Encodings for Graphs](https://mlsanity.com/paper/2310.02579/) (2023)
- [Learning Efficient Positional Encodings with Graph Neural Networks](https://mlsanity.com/paper/2502.01122/) (2025)
- [GraphMaker: Can Diffusion Models Generate Large Attributed Graphs?](https://mlsanity.com/paper/2310.13833/) (2023)
- [Improving Equivariant Networks with Probabilistic Symmetry Breaking](https://mlsanity.com/paper/2503.21985/) (2025)
- [Enhancing High-order Interaction Awareness in LLM-based Recommender Model](https://mlsanity.com/paper/2409.19979/) (2024)
- [GRANOLA: Adaptive Normalization for Graph Neural Networks](https://mlsanity.com/paper/2404.13344/) (2024)
- [Refined Graph Encoder Embedding via Self-Training and Latent Community Recovery](https://mlsanity.com/paper/2405.12797/) (2024)
- [Towards Graph Foundation Models: A Study on the Generalization of Positional and Structural Encodings](https://mlsanity.com/paper/2412.07407/) (2024)
- [Towards Invariance to Node Identifiers in Graph Neural Networks](https://mlsanity.com/paper/2502.13660/) (2025)
- [Understanding and Improving Laplacian Positional Encodings For Temporal GNNs](https://mlsanity.com/paper/2506.01596/) (2025)
- [DiGRAF: Diffeomorphic Graph-Adaptive Activation Function](https://mlsanity.com/paper/2407.02013/) (2024)
- [Graph Transformers Dream of Electric Flow](https://mlsanity.com/paper/2410.16699/) (2024)
- [On the Utilization of Unique Node Identifiers in Graph Neural Networks](https://mlsanity.com/paper/2411.02271/) (2024)
- [Positional Encoding meets Persistent Homology on Graphs](https://mlsanity.com/paper/2506.05814/) (2025)
- [On the Expressive Power of GNNs to Solve Linear SDPs](https://mlsanity.com/paper/2604.27786/) (2026)
- [LASE: Learned Adjacency Spectral Embeddings](https://mlsanity.com/paper/2412.17734/) (2024)
- [LGRPool: Hierarchical Graph Pooling Via Local-Global Regularisation](https://mlsanity.com/paper/2504.08530/) (2025)
- [Schreier-Coset Graph Propagation](https://mlsanity.com/paper/2505.10392/) (2025)
- [Feature Augmentation of GNNs for ILPs: Local Uniqueness Suffices](https://mlsanity.com/paper/2509.21000/) (2025)
- [On The Expressive Power of GNN Derivatives](https://mlsanity.com/paper/2510.02565/) (2025)
- [Multi-View Graph Feature Propagation for Privacy Preservation and Feature Sparsity](https://mlsanity.com/paper/2510.11347/) (2025)
- [Learning from Historical Activations in Graph Neural Networks](https://mlsanity.com/paper/2601.01123/) (2026)
- [Bridging Distance and Spectral Positional Encodings via Anchor-Based Diffusion Geometry Approximation](https://mlsanity.com/paper/2601.04517/) (2026)
- [AdvSynGNN: Structure-Adaptive Graph Neural Nets via Adversarial Synthesis and Self-Corrective Propagation](https://mlsanity.com/paper/2602.17071/) (2026)
- [Frequency-Corrupt Based Graph Self-Supervised Learning](https://mlsanity.com/paper/2604.15699/) (2026)
- [Federated Layer-Wise Exchange for Cross-Client Money Laundering Pattern Detection](https://mlsanity.com/paper/2605.06433/) (2026)
- [Eigenbasis-Independent Learnable Spectral Positional Encodings for Directed Graphs via Hermitian Block Krylov Subspaces](https://mlsanity.com/paper/2607.07032/) (2026)
- [Local-Global Geometric Insights for Graph Neural Networks via Entropic Curvature](https://mlsanity.com/paper/2607.22381/) (2026)
- [Schreier-Coset Graph Rewiring](https://mlsanity.com/paper/2607.27479/) (2026)
- [Converse and Collision-Based Achievability for Node Localization with Hybrid Distance-Spectral Graph Positional Encodings](https://mlsanity.com/paper/2608.30152/) (2026)

## Abstract (arXiv)

Two main families of node feature augmentation schemes have been explored for enhancing GNNs: random features and spectral positional encoding. Surprisingly, however, there is still no clear understanding of the relation between these two augmentation schemes. Here we propose a novel family of positional encoding schemes which draws a link between the above two approaches and improves over both. The new approach, named Random Feature Propagation (RFP), is inspired by the power iteration method and its generalizations. It concatenates several intermediate steps of an iterative algorithm for computing the dominant eigenvectors of a propagation matrix, starting from random node features. Notably, these propagation steps are based on graph-dependent propagation operators that can be either predefined or learned. We explore the theoretical and empirical benefits of RFP. First, we provide theoretical justifications for using random features, for incorporating early propagation steps, and for using multiple random initializations. Then, we empirically demonstrate that RFP significantly outperforms both spectral PE and random features in multiple node classification and graph classification benchmarks.