# Relational Attention: Generalizing Transformers for Graph-Structured Tasks

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

## Key facts

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

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (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)
- [Offline Reinforcement Learning as One Big Sequence Modeling Problem](https://mlsanity.com/paper/2106.02039/) (2021)
- [Heterogeneous Graph Transformer](https://mlsanity.com/paper/2003.01332/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [Stabilizing Transformers for Reinforcement Learning](https://mlsanity.com/paper/1910.06764/) (2019)
- [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)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Graph-Bert: Only Attention is Needed for Learning Graph Representations](https://mlsanity.com/paper/2001.05140/) (2020)
- [Are we really making much progress? Revisiting, benchmarking, and refining heterogeneous graph neural networks](https://mlsanity.com/paper/2112.14936/) (2021)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)

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

- [Graph Inductive Biases in Transformers without Message Passing](https://mlsanity.com/paper/2305.17589/) (2023)
- [Graph Neural Networks for Learning Equivariant Representations of Neural Networks](https://mlsanity.com/paper/2403.12143/) (2024)
- [Graph Metanetworks for Processing Diverse Neural Architectures](https://mlsanity.com/paper/2312.04501/) (2023)
- [Transformers Meet Directed Graphs](https://mlsanity.com/paper/2302.00049/) (2023)
- [Never Train from Scratch: Fair Comparison of Long-Sequence Models Requires Data-Driven Priors](https://mlsanity.com/paper/2310.02980/) (2023)
- [Neural Algorithmic Reasoning with Causal Regularisation](https://mlsanity.com/paper/2302.10258/) (2023)
- [Simulation of Graph Algorithms with Looped Transformers](https://mlsanity.com/paper/2402.01107/) (2024)
- [G-Adapter: Towards Structure-Aware Parameter-Efficient Transfer Learning for Graph Transformer Networks](https://mlsanity.com/paper/2305.10329/) (2023)
- [Coarse-to-Fine: a Hierarchical Diffusion Model for Molecule Generation in 3D](https://mlsanity.com/paper/2305.13266/) (2023)
- [Improved Generalization of Weight Space Networks via Augmentations](https://mlsanity.com/paper/2402.04081/) (2024)
- [MART: MultiscAle Relational Transformer Networks for Multi-agent Trajectory Prediction](https://mlsanity.com/paper/2407.21635/) (2024)
- [Neural Algorithmic Reasoning Without Intermediate Supervision](https://mlsanity.com/paper/2306.13411/) (2023)
- [Deep Linear Probe Generators for Weight Space Learning](https://mlsanity.com/paper/2410.10811/) (2024)
- [Joint-Relation Transformer for Multi-Person Motion Prediction](https://mlsanity.com/paper/2308.04808/) (2023)
- [SALSA-CLRS: A Sparse and Scalable Benchmark for Algorithmic Reasoning](https://mlsanity.com/paper/2309.12253/) (2023)
- [How to Train Neural Field Representations: A Comprehensive Study and Benchmark](https://mlsanity.com/paper/2312.10531/) (2023)
- [Towards Principled Graph Transformers](https://mlsanity.com/paper/2401.10119/) (2024)
- [On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methods](https://mlsanity.com/paper/2403.04929/) (2024)
- [Gradformer: Graph Transformer with Exponential Decay](https://mlsanity.com/paper/2404.15729/) (2024)
- [Towards Dynamic Message Passing on Graphs](https://mlsanity.com/paper/2410.23686/) (2024)
- [Recurrent Aggregators in Neural Algorithmic Reasoning](https://mlsanity.com/paper/2409.07154/) (2024)
- [Transformers as Graph-to-Graph Models](https://mlsanity.com/paper/2310.17936/) (2023)
- [A Scalable and Effective Alternative to Graph Transformers](https://mlsanity.com/paper/2406.12059/) (2024)
- [Rethinking Addressing in Language Models via Contexualized Equivariant Positional Encoding](https://mlsanity.com/paper/2501.00712/) (2025)
- [ViTE: Virtual Graph Trajectory Expert Router for Pedestrian Trajectory Prediction](https://mlsanity.com/paper/2511.12214/) (2025)
- [Open-Book Neural Algorithmic Reasoning](https://mlsanity.com/paper/2501.00072/) (2024)
- [Flow to Learn: Flow Matching on Neural Network Parameters](https://mlsanity.com/paper/2503.19371/) (2025)
- [Learnable Spatial-Temporal Positional Encoding for Link Prediction](https://mlsanity.com/paper/2506.08309/) (2025)
- [Generalizable Insights for Graph Transformers in Theory and Practice](https://mlsanity.com/paper/2511.08028/) (2025)
- [A Context-Enhanced Framework for Sequential Graph Reasoning](https://mlsanity.com/paper/2412.09056/) (2024)

## Abstract (arXiv)

Transformers flexibly operate over sets of real-valued vectors representing task-specific entities and their attributes, where each vector might encode one word-piece token and its position in a sequence, or some piece of information that carries no position at all. But as set processors, transformers are at a disadvantage in reasoning over more general graph-structured data where nodes represent entities and edges represent relations between entities. To address this shortcoming, we generalize transformer attention to consider and update edge vectors in each transformer layer. We evaluate this relational transformer on a diverse array of graph-structured tasks, including the large and challenging CLRS Algorithmic Reasoning Benchmark. There, it dramatically outperforms state-of-the-art graph neural networks expressly designed to reason over graph-structured data. Our analysis demonstrates that these gains are attributable to relational attention's inherent ability to leverage the greater expressivity of graphs over sets.