# Attention Graphons: A Graph Limit Perspective on Graph Transformers

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 34 of its 54 references that are in the map.
- First posted on arXiv 28 Sep 2026.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [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)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (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)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Graph Inductive Biases in Transformers without Message Passing](https://mlsanity.com/paper/2305.17589/) (2023)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [Graphon Neural Networks and the Transferability of Graph Neural Networks](https://mlsanity.com/paper/2006.03548/) (2020)
- [Global Self-Attention as a Replacement for Graph Convolution](https://mlsanity.com/paper/2108.03348/) (2021)
- [Transformer for Graphs: An Overview from Architecture Perspective](https://mlsanity.com/paper/2202.08455/) (2022)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer](https://mlsanity.com/paper/2305.16380/) (2023)
- [Transferability of Spectral Graph Convolutional Neural Networks](https://mlsanity.com/paper/1907.12972/) (2019)
- [Attending to Graph Transformers](https://mlsanity.com/paper/2302.04181/) (2023)
- [Max-Margin Token Selection in Attention Mechanism](https://mlsanity.com/paper/2306.13596/) (2023)
- [Transferability Properties of Graph Neural Networks](https://mlsanity.com/paper/2112.04629/) (2021)
- [Stochastic blockmodel approximation of a graphon: Theory and consistent estimation](https://mlsanity.com/paper/1311.1731/) (2013)
- [A Consistent Histogram Estimator for Exchangeable Graph Models](https://mlsanity.com/paper/1402.1888/) (2014)
- [Learning Graphons via Structured Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2012.05644/) (2020)
- [Learning by Transference: Training Graph Neural Networks on Growing Graphs](https://mlsanity.com/paper/2106.03693/) (2021)
- [Network histograms and universality of blockmodel approximation](https://mlsanity.com/paper/1312.5306/) (2013)
- [Implicit Graphon Neural Representation](https://mlsanity.com/paper/2211.03329/) (2022)

## Abstract (arXiv)

Graph Transformers produce, for each attention head, a dense n× n matrix of learned pairwise interactions. We ask a fundamental question: do these attention-induced graphs converge to a stable limit object as n grows, or does the learned interaction pattern remain unstructured and size-dependent? We answer this using dense graph limit theory, treating each attention matrix as a finite sample from an underlying kernel---an attention graphon---and studying concentration around this limit under the cut-distance. We derive a worst-case variance bound requiring no assumptions on the graphon, and a sharper regularity-aware bound based on nonparametric estimation theory. To operationalize the theory, we propose a canonicalize-then-block-average pipeline for estimating dataset-level attention graphons, and a variance-based diagnostic for testing whether attention admits a stable continuum description. Experiments across multiple graph benchmarks show that learned attention stabilizes to dataset-specific graphon structure on several datasets; that empirical cut-distance and cut-norm variance decreases with n consistent with our bounds; and that attention graphons transfer to larger graph sizes with error decreasing in n.