mlsanityData to 7 Oct 2026

Transformers over Directed Acyclic Graphs

arXiv 2210.13148 ↗First posted 24 Oct 2022cs.LG cs.AIcited by 23

Not on the map. Why?

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.

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

Builds on

50 of 72 references.

References · 50

  1. 2017Attention Is All You Needcited by 59,932
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 4,993
  5. 2018How Powerful are Graph Neural Networks?cited by 4,355
  6. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  7. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  8. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  9. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  10. 2018Self-Attention with Relative Position Representationscited by 1,112
  11. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  12. 2020Learning to Simulate Complex Physics with Graph Networkscited by 867
38 more
  1. 2018Efficient Neural Architecture Search via Parameter Sharingcited by 831
  2. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  3. 2020A Generalization of Transformer Networks to Graphscited by 653
  4. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  5. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  6. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  7. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  8. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 442
  9. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  10. 2015Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networkscited by 305
  11. 2022Long Range Graph Benchmarkcited by 258
  12. 2018Modeling polypharmacy side effects with graph convolutional networkscited by 237
  13. 2019Learning Discrete Structures for Graph Neural Networkscited by 228
  14. 2017A Survey of Machine Learning for Big Code and Naturalnesscited by 220
  15. 2020Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddingscited by 212
  16. 2022Representing Long-Range Context for Graph Neural Networks with Global Attentioncited by 193
  17. 2022Structure-Aware Transformer for Graph Representation Learningcited by 191
  18. 2018code2seq: Generating Sequences from Structured Representations of Codecited by 177
  19. 2021GraphiT: Encoding Graph Structure in Transformerscited by 146
  20. 2018Graph HyperNetworks for Neural Architecture Searchcited by 131
  21. 2022Transformer for Graphs: An Overview from Architecture Perspectivecited by 107
  22. 2021MagNet: A Neural Network for Directed Graphscited by 104
  23. 2019D-VAE: A Variational Autoencoder for Directed Acyclic Graphscited by 98
  24. 2021Directed Acyclic Graph Network for Conversational Emotion Recognitioncited by 97
  25. 2021Parameter Prediction for Unseen Deep Architecturescited by 89
  26. 2020Code Prediction by Feeding Trees to Transformerscited by 70
  27. 2021Directed Acyclic Graph Neural Networkscited by 70
  28. 2018MotifNet: a motif-based Graph Convolutional Network for directed graphscited by 63
  29. 2021Language-Agnostic Representation Learning of Source Code from Structure and Contextcited by 63
  30. 2019TreeGen: A Tree-Based Transformer Architecture for Code Generationcited by 58
  31. 2020A Large-Scale Database for Graph Representation Learningcited by 54
  32. 2019Spectral-based Graph Convolutional Network for Directed Graphscited by 38
  33. 2020Answering Complex Queries in Knowledge Graphs with Bidirectional Sequence Encoderscited by 28
  34. 2022On the Learning of Non-Autoregressive Transformerscited by 27
  35. 2019Improving Graph Neural Network Representations of Logical Formulae with Subgraph Poolingcited by 20
  36. 2022PACE: A Parallelizable Computation Encoder for Directed Acyclic Graphscited by 20
  37. 2022Neural Topological Ordering for Computation Graphscited by 12
  38. 2015DAG-Recurrent Neural Networks For Scene Labelingcited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 9; 2025: 10; 2026: 3.

23 papers.

Sort:

  1. 2024Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classificationcited by 83
  2. 2025Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellencecited by 24
  3. 2023Enhancing Graph Transformers with Hierarchical Distance Structural Encodingcited by 16
  4. 2025DeepGate4: Efficient and Effective Representation Learning for Circuit Design at Scalecited by 12
  5. 2024Node Identifiers: Compact, Discrete Representations for Efficient Graph Learningcited by 10
  6. 2024FlowerFormer: Empowering Neural Architecture Encoding using a Flow-aware Graph Transformercited by 9
  7. 2025Biologically Plausible Brain Graph Transformercited by 9
  8. 2024What Are Good Positional Encodings for Directed Graphs?cited by 7
  9. 2024Convolutional Learning on Directed Acyclic Graphscited by 6
  10. 2024Commute Graph Neural Networkscited by 5
  11. 2024DeepSeq2: Enhanced Sequential Circuit Learning with Disentangled Representationscited by 5
  12. 2025DualEquiNet: A Dual-Space Hierarchical Equivariant Network for Large Biomoleculescited by 5
11 more
  1. 2025NN-Former: Rethinking Graph Structure in Neural Architecture Representationcited by 2
  2. 2024Scale-aware Message Passing For Graph Node Classificationcited by 1
  3. 2025Simple Path Structural Encoding for Graph Transformerscited by 1
  4. 2025Flow-Attentional Graph Neural Networkscited by 1
  5. 2025Directed Acyclic Graph Convolutional Networkscited by 1
  6. 2024CaTs and DAGs: Integrating Directed Acyclic Graphs with Transformers for Causally Constrained Predictionscited by 0
  7. 2025Language Embedding Meets Dynamic Graph: A New Exploration for Neural Architecture Representation Learningcited by 0
  8. 2025State Space Models over Directed Graphscited by 0
  9. 2026Can Graph Learning Learn Circuits?cited by 0
  10. 2026Node-wise Feature Encoding for Neural Performance Predictioncited by 0
  11. 2026Learning Sparse Decision Trees via Transformer Variational Auto-Encoderscited by 0