# Transformers over Directed Acyclic Graphs

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 72 references that are in the map.
- First posted on arXiv 24 Oct 2022.

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

- [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)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [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)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [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)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [Efficient Neural Architecture Search via Parameter Sharing](https://mlsanity.com/paper/1802.03268/) (2018)
- [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)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [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)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks](https://mlsanity.com/paper/1503.00075/) (2015)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Modeling polypharmacy side effects with graph convolutional networks](https://mlsanity.com/paper/1802.00543/) (2018)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [A Survey of Machine Learning for Big Code and Naturalness](https://mlsanity.com/paper/1709.06182/) (2017)
- [Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings](https://mlsanity.com/paper/2006.13009/) (2020)
- [Representing Long-Range Context for Graph Neural Networks with Global Attention](https://mlsanity.com/paper/2201.08821/) (2022)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [code2seq: Generating Sequences from Structured Representations of Code](https://mlsanity.com/paper/1808.01400/) (2018)

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

- [Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification](https://mlsanity.com/paper/2406.08993/) (2024)
- [Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence](https://mlsanity.com/paper/2502.09263/) (2025)
- [Enhancing Graph Transformers with Hierarchical Distance Structural Encoding](https://mlsanity.com/paper/2308.11129/) (2023)
- [DeepGate4: Efficient and Effective Representation Learning for Circuit Design at Scale](https://mlsanity.com/paper/2502.01681/) (2025)
- [FlowerFormer: Empowering Neural Architecture Encoding using a Flow-aware Graph Transformer](https://mlsanity.com/paper/2403.12821/) (2024)
- [Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning](https://mlsanity.com/paper/2405.16435/) (2024)
- [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)
- [Convolutional Learning on Directed Acyclic Graphs](https://mlsanity.com/paper/2405.03056/) (2024)
- [Commute Graph Neural Networks](https://mlsanity.com/paper/2407.01635/) (2024)
- [DeepSeq2: Enhanced Sequential Circuit Learning with Disentangled Representations](https://mlsanity.com/paper/2411.00530/) (2024)
- [DualEquiNet: A Dual-Space Hierarchical Equivariant Network for Large Biomolecules](https://mlsanity.com/paper/2506.19862/) (2025)
- [NN-Former: Rethinking Graph Structure in Neural Architecture Representation](https://mlsanity.com/paper/2507.00880/) (2025)
- [Scale-aware Message Passing For Graph Node Classification](https://mlsanity.com/paper/2411.19392/) (2024)
- [Simple Path Structural Encoding for Graph Transformers](https://mlsanity.com/paper/2502.09365/) (2025)
- [Flow-Attentional Graph Neural Networks](https://mlsanity.com/paper/2506.06127/) (2025)
- [Directed Acyclic Graph Convolutional Networks](https://mlsanity.com/paper/2506.12218/) (2025)
- [CaTs and DAGs: Integrating Directed Acyclic Graphs with Transformers for Causally Constrained Predictions](https://mlsanity.com/paper/2410.14485/) (2024)
- [Language Embedding Meets Dynamic Graph: A New Exploration for Neural Architecture Representation Learning](https://mlsanity.com/paper/2506.07735/) (2025)
- [State Space Models over Directed Graphs](https://mlsanity.com/paper/2509.13735/) (2025)
- [Can Graph Learning Learn Circuits?](https://mlsanity.com/paper/2608.08536/) (2026)
- [Node-wise Feature Encoding for Neural Performance Prediction](https://mlsanity.com/paper/2608.27794/) (2026)
- [Learning Sparse Decision Trees via Transformer Variational Auto-Encoders](https://mlsanity.com/paper/2609.01430/) (2026)

## Abstract (arXiv)

Transformer models have recently gained popularity in graph representation learning as they have the potential to learn complex relationships beyond the ones captured by regular graph neural networks. The main research question is how to inject the structural bias of graphs into the transformer architecture, and several proposals have been made for undirected molecular graphs and, recently, also for larger network graphs. In this paper, we study transformers over directed acyclic graphs (DAGs) and propose architecture adaptations tailored to DAGs: (1) An attention mechanism that is considerably more efficient than the regular quadratic complexity of transformers and at the same time faithfully captures the DAG structure, and (2) a positional encoding of the DAG's partial order, complementing the former. We rigorously evaluate our approach over various types of tasks, ranging from classifying source code graphs to nodes in citation networks, and show that it is effective in two important aspects: in making graph transformers generally outperform graph neural networks tailored to DAGs and in improving SOTA graph transformer performance in terms of both quality and efficiency.