mlsanityData to 7 Oct 2026

Transformers Meet Directed Graphs

arXiv 2302.00049 ↗First posted 31 Jan 2023cs.LGcited by 39

Not on the map. Why?

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%.

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

Builds on

43 of 77 references.

References · 43

  1. 2017Attention Is All You Needcited by 59,932
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  4. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 4,993
  5. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  6. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  7. 2020Reformer: The Efficient Transformercited by 1,658
  8. 2020Rethinking Attention with Performerscited by 1,584
  9. 2022Competition-Level Code Generation with AlphaCodecited by 1,427
  10. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  11. 2020CodeBERT: A Pre-Trained Model for Programming and Natural Languagescited by 1,286
  12. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
31 more
  1. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  2. 2020A Generalization of Transformer Networks to Graphscited by 653
  3. 2018Attention, Learn to Solve Routing Problems!cited by 646
  4. 2020GraphCodeBERT: Pre-training Code Representations with Data Flowcited by 600
  5. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  6. 2021High-Performance Large-Scale Image Recognition Without Normalizationcited by 359
  7. 2021Do Transformers Really Perform Bad for Graph Representation?cited by 318
  8. 2017Learning to Represent Programs with Graphscited by 219
  9. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 198
  10. 2022Structure-Aware Transformer for Graph Representation Learningcited by 191
  11. 2022Pure Transformers are Powerful Graph Learnerscited by 188
  12. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  13. 2020Scaling Graph Neural Networks with Approximate PageRankcited by 174
  14. 2021GraphiT: Encoding Graph Structure in Transformerscited by 146
  15. 2021Global Self-Attention as a Replacement for Graph Convolutioncited by 113
  16. 2022Transformer for Graphs: An Overview from Architecture Perspectivecited by 107
  17. 2021MagNet: A Neural Network for Directed Graphscited by 104
  18. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  19. 2021Language-Agnostic Representation Learning of Source Code from Structure and Contextcited by 63
  20. 2019Adversarial Examples for Models of Codecited by 61
  21. 2022CodeAttack: Code-Based Adversarial Attacks for Pre-trained Programming Language Modelscited by 48
  22. 2020Semantic Robustness of Models of Source Codecited by 43
  23. 2022Relational Attention: Generalizing Transformers for Graph-Structured Taskscited by 41
  24. 2020Adversarial Robustness for Codecited by 36
  25. 2021Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustnesscited by 35
  26. 2020Signal Processing on Directed Graphscited by 28
  27. 2022MSGNN: A Spectral Graph Neural Network Based on a Novel Magnetic Signed Laplaciancited by 28
  28. 2016Magnetic Eigenmaps for the Visualization of Directed Networkscited by 25
  29. 2020ProGraML: Graph-based Deep Learning for Program Optimization and Analysiscited by 23
  30. 2016Magnetic eigenmaps for community detection in directed networkscited by 22
  31. 2022A Library for Representing Python Programs as Graphs for Machine Learningcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 14; 2025: 16; 2026: 4.

39 papers.

Sort:

By area:

  1. 2023Edge Directionality Improves Learning on Heterophilic Graphscited by 88
  2. 2023Attending to Graph Transformerscited by 81
  3. 2023A Comprehensive Survey on Deep Graph Representation Learningcited by 72
  4. 2024Graph Transformers: A Surveycited by 32
  5. 2025Learning Efficient Positional Encodings with Graph Neural Networkscited by 21
  6. 2023HoloNets: Spectral Convolutions do extend to Directed Graphscited by 20
  7. 2024Comparing Graph Transformers via Positional Encodingscited by 20
  8. 2024Spatio-Spectral Graph Neural Networkscited by 17
  9. 2023Expressive Sign Equivariant Networks for Spectral Geometric Learningcited by 15
  10. 2025Biologically Plausible Brain Graph Transformercited by 9
  11. 2024Efficient Time Series Processing for Transformers and State-Space Models through Token Mergingcited by 7
  12. 2024What Are Good Positional Encodings for Directed Graphs?cited by 7
27 more
  1. 2024Commute Graph Neural Networkscited by 5
  2. 2025DualEquiNet: A Dual-Space Hierarchical Equivariant Network for Large Biomoleculescited by 5
  3. 2024Improving Graph Neural Networks by Learning Continuous Edge Directionscited by 3
  4. 2025Generating Directed Graphs with Dual Attention and Asymmetric Encodingcited by 3
  5. 2024Revisiting Edge Perturbation for Graph Neural Network in Graph Data Augmentation and Attackcited by 2
  6. 2024Improving Chinese Character Representation with Formation Treecited by 2
  7. 2024A Structure-Aware Lane Graph Transformer Model for Vehicle Trajectory Predictioncited by 2
  8. 2024Graph Neural Networks for Edge Signals: Orientation Equivariance and Invariancecited by 2
  9. 2025Efficient Learning on Large Graphs using a Densifying Regularity Lemmacited by 2
  10. 2025Generalizable Insights for Graph Transformers in Theory and Practicecited by 2
  11. 2024AUTONODE: A Neuro-Graphic Self-Learnable Engine for Cognitive GUI Automationcited by 1
  12. 2024A Benchmark on Directed Graph Representation Learning in Hardware Designscited by 1
  13. 2025Toward General Digraph Contrastive Learning: A Dual Spatial Perspectivecited by 1
  14. 2026Principled Latent Diffusion for Graphs via Laplacian Autoencoderscited by 1
  15. 2024Adaptive Critical Subgraph Mining for Cognitive Impairment Conversion Prediction with T1-MRI-based Brain Networkcited by 0
  16. 2025Rethinking Link Prediction for Directed Graphscited by 0
  17. 2025Understanding the Design Principles of Link Prediction in Directed Settingscited by 0
  18. 2025Using Subgraph GNNs for Node Classification:an Overlooked Potential Approachcited by 0
  19. 2025Toward Data-centric Directed Graph Learning: An Entropy-driven Approachcited by 0
  20. 2025The informativeness of the gradient revisitedcited by 0
  21. 2025Directed Homophily-Aware Graph Neural Networkcited by 0
  22. 2025SAFT: Structure-Aware Fine-Tuning of LLMs for AMR-to-Text Generationcited by 0
  23. 2025Long-Range Graph Wavelet Networkscited by 0
  24. 2025State Space Models over Directed Graphscited by 0
  25. 2026Size Transferability of Graph Transformers with Convolutional Positional Encodingscited by 0
  26. 2026Eigenbasis-Independent Learnable Spectral Positional Encodings for Directed Graphs via Hermitian Block Krylov Subspacescited by 0
  27. 2026Converse and Collision-Based Achievability for Node Localization with Hybrid Distance-Spectral Graph Positional Encodingscited by 0