Graph transformers produce stable large-scale interaction patterns
Attention Graphons: A Graph Limit Perspective on Graph Transformers
Machine Learning
Summary
When graph transformers analyze networks, they create attention maps that show how parts of the graph relate to each other. The authors wondered if these attention maps settle into predictable patterns as the graphs get bigger or if they stay random and depend on size. They used math from graph limit theory to show that these attention maps do converge to a stable pattern they call an "attention graphon." This means the model learns meaningful, consistent structures that hold up even for very large graphs.
What this means in practice
- •For machine learning engineers: Use the attention graphon concept to train graph transformers that generalize better to larger graphs than those seen during training.
- •For data engineers: Diagnose stability and structure of attention patterns in graph transformer models for large-scale graph datasets.
Authors
Caio F. Deberaldini Netto, Moshe Eliasof, Luana Ruiz
Abstract
Graph Transformers produce, for each attention head, a dense $n\times 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 \emph{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$.