Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper establishes a dense graph limit framework for Graph Transformers by formalizing their $n \times n$ attention matrices as finite samples from continuous kernel limits termed attention graphons. Using dense graph limit theory, the authors derive distribution-free and regularity-aware concentration bounds under the cut-distance to characterize asymptotic attention behavior. Empirical evaluations confirm that learned attention stabilizes to these dataset-specific limits as graph size grows, exhibiting variance decay consistent with theory and enabling zero-shot transfer of attention patterns to larger graphs.
Graph Transformer attention doesn't degrade into unstructured noise at scale: learned interaction matrices converge to continuous, predictable graphons that transfer directly to larger graphs.
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$.