# Transformers Meet Directed Graphs

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 77 references that are in the map.
- First posted on arXiv 31 Jan 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [CodeBERT: A Pre-Trained Model for Programming and Natural Languages](https://mlsanity.com/paper/2002.08155/) (2020)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [GraphCodeBERT: Pre-training Code Representations with Data Flow](https://mlsanity.com/paper/2009.08366/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [High-Performance Large-Scale Image Recognition Without Normalization](https://mlsanity.com/paper/2102.06171/) (2021)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [Learning to Represent Programs with Graphs](https://mlsanity.com/paper/1711.00740/) (2017)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [GraphiT: Encoding Graph Structure in Transformers](https://mlsanity.com/paper/2106.05667/) (2021)
- [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)
- [Transformer for Graphs: An Overview from Architecture Perspective](https://mlsanity.com/paper/2202.08455/) (2022)
- [Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks](https://mlsanity.com/paper/2203.00199/) (2022)

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

- [Edge Directionality Improves Learning on Heterophilic Graphs](https://mlsanity.com/paper/2305.10498/) (2023)
- [Attending to Graph Transformers](https://mlsanity.com/paper/2302.04181/) (2023)
- [A Comprehensive Survey on Deep Graph Representation Learning](https://mlsanity.com/paper/2304.05055/) (2023)
- [Graph Transformers: A Survey](https://mlsanity.com/paper/2407.09777/) (2024)
- [Learning Efficient Positional Encodings with Graph Neural Networks](https://mlsanity.com/paper/2502.01122/) (2025)
- [HoloNets: Spectral Convolutions do extend to Directed Graphs](https://mlsanity.com/paper/2310.02232/) (2023)
- [Comparing Graph Transformers via Positional Encodings](https://mlsanity.com/paper/2402.14202/) (2024)
- [Spatio-Spectral Graph Neural Networks](https://mlsanity.com/paper/2405.19121/) (2024)
- [Expressive Sign Equivariant Networks for Spectral Geometric Learning](https://mlsanity.com/paper/2312.02339/) (2023)
- [Biologically Plausible Brain Graph Transformer](https://mlsanity.com/paper/2502.08958/) (2025)
- [What Are Good Positional Encodings for Directed Graphs?](https://mlsanity.com/paper/2407.20912/) (2024)
- [Efficient Time Series Processing for Transformers and State-Space Models through Token Merging](https://mlsanity.com/paper/2405.17951/) (2024)
- [Commute Graph Neural Networks](https://mlsanity.com/paper/2407.01635/) (2024)
- [DualEquiNet: A Dual-Space Hierarchical Equivariant Network for Large Biomolecules](https://mlsanity.com/paper/2506.19862/) (2025)
- [Principled Latent Diffusion for Graphs via Laplacian Autoencoders](https://mlsanity.com/paper/2601.13780/) (2026)
- [Improving Graph Neural Networks by Learning Continuous Edge Directions](https://mlsanity.com/paper/2410.14109/) (2024)
- [Generating Directed Graphs with Dual Attention and Asymmetric Encoding](https://mlsanity.com/paper/2506.16404/) (2025)
- [Revisiting Edge Perturbation for Graph Neural Network in Graph Data Augmentation and Attack](https://mlsanity.com/paper/2403.07943/) (2024)
- [Improving Chinese Character Representation with Formation Tree](https://mlsanity.com/paper/2404.12693/) (2024)
- [A Structure-Aware Lane Graph Transformer Model for Vehicle Trajectory Prediction](https://mlsanity.com/paper/2405.20121/) (2024)
- [Graph Neural Networks for Edge Signals: Orientation Equivariance and Invariance](https://mlsanity.com/paper/2410.16935/) (2024)
- [Efficient Learning on Large Graphs using a Densifying Regularity Lemma](https://mlsanity.com/paper/2504.18273/) (2025)
- [Generalizable Insights for Graph Transformers in Theory and Practice](https://mlsanity.com/paper/2511.08028/) (2025)
- [AUTONODE: A Neuro-Graphic Self-Learnable Engine for Cognitive GUI Automation](https://mlsanity.com/paper/2403.10171/) (2024)
- [A Benchmark on Directed Graph Representation Learning in Hardware Designs](https://mlsanity.com/paper/2410.06460/) (2024)
- [Toward General Digraph Contrastive Learning: A Dual Spatial Perspective](https://mlsanity.com/paper/2510.16311/) (2025)
- [Size-Transferability of Graph Transformers with Convolutional Positional Encodings](https://mlsanity.com/paper/2602.15239/) (2026)
- [Adaptive Critical Subgraph Mining for Cognitive Impairment Conversion Prediction with T1-MRI-based Brain Network](https://mlsanity.com/paper/2403.13338/) (2024)
- [Rethinking Link Prediction for Directed Graphs](https://mlsanity.com/paper/2502.05724/) (2025)
- [Understanding the Design Principles of Link Prediction in Directed Settings](https://mlsanity.com/paper/2502.15008/) (2025)

## Abstract (arXiv)

Transformers were originally proposed as a sequence-to-sequence model for text but have become vital for a wide range of modalities, including images, audio, video, and undirected graphs. However, transformers for directed graphs are a surprisingly underexplored topic, despite their applicability to ubiquitous domains, including source code and logic circuits. In this work, we propose two direction- and structure-aware positional encodings for directed graphs: (1) the eigenvectors of the Magnetic Laplacian - a direction-aware generalization of the combinatorial Laplacian; (2) directional random walk encodings. Empirically, we show that the extra directionality information is useful in various downstream tasks, including correctness testing of sorting networks and source code understanding. Together with a data-flow-centric graph construction, our model outperforms the prior state of the art on the Open Graph Benchmark Code2 relatively by 14.7%.