Attention Graphons: A Graph Limit Perspective on Graph Transformers

arXiv:2609.35620v1 Announce Type: new Abstract: Graph Transformers produce, for each attention head, a dense nimes 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.

Source: arXiv cs.LG | 2026-09-29