# What Are Good Positional Encodings for Directed Graphs?

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 70 references that are in the map.
- First posted on arXiv 30 Jul 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (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)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Devign: Effective Vulnerability Identification by Learning Comprehensive Program Semantics via Graph Neural Networks](https://mlsanity.com/paper/1909.03496/) (2019)
- [A Comprehensive Survey of Neural Architecture Search: Challenges and Solutions](https://mlsanity.com/paper/2006.02903/) (2020)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Directional Graph Networks](https://mlsanity.com/paper/2010.02863/) (2020)
- [Neural Predictor for Neural Architecture Search](https://mlsanity.com/paper/1912.00848/) (2019)
- [Global Self-Attention as a Replacement for Graph Convolution](https://mlsanity.com/paper/2108.03348/) (2021)
- [MagNet: A Neural Network for Directed Graphs](https://mlsanity.com/paper/2102.11391/) (2021)
- [D-VAE: A Variational Autoencoder for Directed Acyclic Graphs](https://mlsanity.com/paper/1904.11088/) (2019)
- [Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks](https://mlsanity.com/paper/2203.00199/) (2022)
- [GCN-RL Circuit Designer: Transferable Transistor Sizing with Graph Neural Networks and Reinforcement Learning](https://mlsanity.com/paper/2005.00406/) (2020)
- [Directed Graph Convolutional Network](https://mlsanity.com/paper/2004.13970/) (2020)
- [Directed Acyclic Graph Neural Networks](https://mlsanity.com/paper/2101.07965/) (2021)
- [MotifNet: a motif-based Graph Convolutional Network for directed graphs](https://mlsanity.com/paper/1802.01572/) (2018)
- [CktGNN: Circuit Graph Neural Network for Electronic Design Automation](https://mlsanity.com/paper/2308.16406/) (2023)
- [Transformers Meet Directed Graphs](https://mlsanity.com/paper/2302.00049/) (2023)
- [Spectral-based Graph Convolutional Network for Directed Graphs](https://mlsanity.com/paper/1907.08990/) (2019)
- [MSGNN: A Spectral Graph Neural Network Based on a Novel Magnetic Signed Laplacian](https://mlsanity.com/paper/2209.00546/) (2022)
- [High-Level Synthesis Performance Prediction using GNNs: Benchmarking, Modeling, and Advancing](https://mlsanity.com/paper/2201.06848/) (2022)

## Built on by (most cited first, 8 of 8)

- [Generating Directed Graphs with Dual Attention and Asymmetric Encoding](https://mlsanity.com/paper/2506.16404/) (2025)
- [Towards Data-centric Machine Learning on Directed Graphs: a Survey](https://mlsanity.com/paper/2412.01849/) (2024)
- [Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings](https://mlsanity.com/paper/2505.13087/) (2025)
- [GraViti: Graph-Level Variational Autoencoders with Relaxed Permutation Invariance](https://mlsanity.com/paper/2605.16668/) (2026)
- [Directed Homophily-Aware Graph Neural Network](https://mlsanity.com/paper/2505.22362/) (2025)
- [State Space Models over Directed Graphs](https://mlsanity.com/paper/2509.13735/) (2025)
- [Eigenbasis-Independent Learnable Spectral Positional Encodings for Directed Graphs via Hermitian Block Krylov Subspaces](https://mlsanity.com/paper/2607.07032/) (2026)
- [Path Laplacian Encodings for Directed Graphs](https://mlsanity.com/paper/2610.04657/) (2026)

## Abstract (arXiv)

Positional encodings (PEs) are essential for building powerful and expressive graph neural networks and graph transformers, as they effectively capture the relative spatial relationships between nodes. Although extensive research has been devoted to PEs in undirected graphs, PEs for directed graphs remain relatively unexplored. This work seeks to address this gap. We first introduce the notion of Walk Profile, a generalization of walk-counting sequences for directed graphs. A walk profile encompasses numerous structural features crucial for directed graph-relevant applications, such as program analysis and circuit performance prediction. We identify the limitations of existing PE methods in representing walk profiles and propose a novel Multi-q Magnetic Laplacian PE, which extends the Magnetic Laplacian eigenvector-based PE by incorporating multiple potential factors. The new PE can provably express walk profiles. Furthermore, we generalize prior basis-invariant neural networks to enable the stable use of the new PE in the complex domain. Our numerical experiments validate the expressiveness of the proposed PEs and demonstrate their effectiveness in solving sorting network satisfiability and performing well on general circuit benchmarks. Our code is available at https://github.com/Graph-COM/Multi-q-Maglap.