# Rewiring with Positional Encodings for Graph Neural Networks

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 62 references that are in the map.
- First posted on arXiv 29 Jan 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Image Transformer](https://mlsanity.com/paper/1802.05751/) (2018)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Heterogeneous Graph Transformer](https://mlsanity.com/paper/2003.01332/) (2020)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (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)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)

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

- [On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology](https://mlsanity.com/paper/2302.02941/) (2023)
- [FoSR: First-order spectral rewiring for addressing oversquashing in GNNs](https://mlsanity.com/paper/2210.11790/) (2022)
- [DRew: Dynamically Rewired Message Passing with Delay](https://mlsanity.com/paper/2305.08018/) (2023)
- [Locality-Aware Graph-Rewiring in GNNs](https://mlsanity.com/paper/2310.01668/) (2023)
- [Graph Positional and Structural Encoder](https://mlsanity.com/paper/2307.07107/) (2023)
- [Probabilistically Rewired Message-Passing Neural Networks](https://mlsanity.com/paper/2310.02156/) (2023)
- [Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching](https://mlsanity.com/paper/2312.16560/) (2023)
- [Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges](https://mlsanity.com/paper/2311.07073/) (2023)
- [Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning](https://mlsanity.com/paper/2505.15547/) (2025)
- [Probabilistic Graph Rewiring via Virtual Nodes](https://mlsanity.com/paper/2405.17311/) (2024)
- [Joint Graph Rewiring and Feature Denoising via Spectral Resonance](https://mlsanity.com/paper/2408.07191/) (2024)
- [LogGD:Detecting Anomalies from System Logs by Graph Neural Networks](https://mlsanity.com/paper/2209.07869/) (2022)
- [Content Augmented Graph Neural Networks](https://mlsanity.com/paper/2311.12741/) (2023)
- [Towards A Universal Graph Structural Encoder](https://mlsanity.com/paper/2504.10917/) (2025)
- [Theoretical Understanding of In-Context Learning in Shallow Transformers with Unstructured Data](https://mlsanity.com/paper/2402.00743/) (2024)
- [CKGConv: General Graph Convolution with Continuous Kernels](https://mlsanity.com/paper/2404.13604/) (2024)
- [Discovering the Representation Bottleneck of Graph Neural Networks](https://mlsanity.com/paper/2205.07266/) (2022)
- [Asynchronous Neural Networks for Learning in Graphs](https://mlsanity.com/paper/2205.12245/) (2022)
- [Higher-Order Expander Graph Propagation](https://mlsanity.com/paper/2311.07966/) (2023)
- [Framelet Message Passing](https://mlsanity.com/paper/2302.14806/) (2023)
- [Spectral Maps for Learning on Subgraphs](https://mlsanity.com/paper/2205.14938/) (2022)
- [Relative Position Prediction as Pre-training for Text Encoders](https://mlsanity.com/paper/2202.01145/) (2022)
- [Effects of Dropout on Performance in Long-range Graph Learning Tasks](https://mlsanity.com/paper/2502.07364/) (2025)
- [Commute Networks as a Signature of Urban Socioeconomic Performance: Evaluating Mobility Structures with Deep Learning Models](https://mlsanity.com/paper/2507.04027/) (2025)
- [Local Virtual Nodes for Alleviating Over-Squashing in Graph Neural Networks](https://mlsanity.com/paper/2508.20597/) (2025)
- [Molecular Property Prediction by Semantic-invariant Contrastive Learning](https://mlsanity.com/paper/2303.06902/) (2023)
- [Topological Neural Networks: Mitigating the Bottlenecks of Graph Neural Networks via Higher-Order Interactions](https://mlsanity.com/paper/2402.06908/) (2024)
- [LGRPool: Hierarchical Graph Pooling Via Local-Global Regularisation](https://mlsanity.com/paper/2504.08530/) (2025)
- [Urban delineation through the lens of commute networks: Leveraging graph embeddings to distinguish socioeconomic groups in cities](https://mlsanity.com/paper/2507.11057/) (2025)
- [GraphTorque: Torque-Driven Rewiring Graph Neural Network](https://mlsanity.com/paper/2507.21422/) (2025)

## Abstract (arXiv)

Several recent works use positional encodings to extend the receptive fields of graph neural network (GNN) layers equipped with attention mechanisms. These techniques, however, extend receptive fields to the complete graph, at substantial computational cost and risking a change in the inductive biases of conventional GNNs, or require complex architecture adjustments. As a conservative alternative, we use positional encodings to expand receptive fields to r-hop neighborhoods. More specifically, our method augments the input graph with additional nodes/edges and uses positional encodings as node and/or edge features. We thus modify graphs before inputting them to a downstream GNN model, instead of modifying the model itself. This makes our method model-agnostic, i.e., compatible with any of the existing GNN architectures. We also provide examples of positional encodings that are lossless with a one-to-one map between the original and the modified graphs. We demonstrate that extending receptive fields via positional encodings and a virtual fully-connected node significantly improves GNN performance and alleviates over-squashing using small r. We obtain improvements on a variety of models and datasets and reach competitive performance using traditional GNNs or graph Transformers.