# Scaling Graph Transformers: A Comparative Study of Sparse and Dense Attention

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 14 references that are in the map.
- First posted on arXiv 24 Aug 2025.

## Builds on (most cited first, 11 of 11)

- [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)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Exphormer: Sparse Transformers for Graphs](https://mlsanity.com/paper/2303.06147/) (2023)

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

- [Geometry-Guided Generative Representation for Functional Brain Graphs](https://mlsanity.com/paper/2511.04539/) (2025)

## Abstract (arXiv)

Graphs have become a central representation in machine learning for capturing relational and structured data across various domains. Traditional graph neural networks often struggle to capture long-range dependencies between nodes due to their local structure. Graph transformers overcome this by using attention mechanisms that allow nodes to exchange information globally. However, there are two types of attention in graph transformers: dense and sparse. In this paper, we compare these two attention mechanisms, analyze their trade-offs, and highlight when to use each. We also outline current challenges and problems in designing attention for graph transformers.