Attention Graphons: A Graph Limit Perspective on Graph Transformers

1 INTRODUCTION

• A stable attention graphon could provide a dataset-level object for size-agnostic comparison and a theoretical basis for transferability across graph sizes.The paper relates this perspective to graphon theory’s account of size transfer for graph-learning models.Source: §1 · pp. 1–2
• The paper formalizes pre-softmax attention matrices as samples from an underlying kernel and estimates dataset-level attention graphons through canonicalization and block averaging.These graphons are proposed as a compact representation of learned interaction patterns.Source: §1 · p. 1
• Worst-case and regularity-aware variance bounds motivate cut-distance and cut-norm variance curves as diagnostics of whether attention admits a stable continuum description.The regularity-aware bound is based on nonparametric graphon estimation.Source: §1 · p. 2
• Across multiple benchmarks and synthetic graphon families, estimated attention graphons stabilize with graph size on several datasets, while empirical variance decreases with n.For datasets admitting an attention graphon, estimated kernels approximate attention on larger graphs with transfer error decreasing in n.Source: §1 · p. 2

2.1 GTS AND ATTENTION MATRICES AS WEIGHTED GRAPHS

• For each graph-transformer layer and head, pre-softmax attention is interpreted as the adjacency matrix of a dense weighted directed graph on the input nodes.The paper then works with symmetrized pre-softmax attention, turning directional relationships into undirected ones while preserving pairwise affinity structure.Source: §2.1 · p. 2

2.2 GRAPHONS AND GRAPH DISTANCES

• Graphons are symmetric measurable kernels that serve as limit objects for dense symmetric graphs; cut-distance compares graphs when labels are arbitrary, while cut-norm applies when node correspondences are known.Cut-distance allows relabeling, whereas aligned samples can be compared directly in cut norm.Source: §2.2 · p. 3
• Graphons also define generative models: sample latent variables uniformly, then assign pairwise weights from the kernel or sample edges as Bernoulli draws.The weighted model produces a complete graph; the undirected model samples edges for distinct node pairs.Source: §2.2 · p. 3

2.3 PRE-SOFTMAX ATTENTION GRAPHS

• The attention graph is formed by applying an increasing bijection to symmetrized pre-softmax scores after an offset; the paper uses the sigmoid and average pre-softmax score.Invertibility of the transform means the post-softmax attention can be recovered independently of the offset.Source: §2.3 · p. 3

3 THEORY: GRAPHON SAMPLE CONCENTRATION

• Attention graphs are embedded as induced graphons so differently sized matrices and continuous kernels share a function space; cut-distance measures discrepancy without assuming aligned node labels.Embedding alone does not establish graphon generation, so the paper tests that hypothesis using graphon sampling results.Source: §3 · p. 4

3.1 A UNIVERSAL VARIANCE BOUND

• The universal cut-distance variance bound makes no structural assumptions on the graphon, but its 1/log n rate is too slow to be useful as a practical diagnostic threshold.The paper notes that empirical variances could remain below this bound even for very large samples known not to come from a graphon.Source: §3.1 · p. 4

3.2 A REGULARITY-AWARE VARIANCE BOUND

• Under Hölder regularity, aligned representations yield a polynomial cut-norm variance rate of n^(-2 min(α,1)/(min(α,1)+1)), which stabilizes at n^-1 for α ≥ 1.The block-resolution trade-off balances kernel approximation error against noise; canonicalization recovers latent ordering consistently when the degree function is strictly monotone.Source: §3.2 · pp. 4–5

4.1 DOES GT ATTENTION CONVERGE TO A GRAPHON?

• For a fixed trained model, layer, and head, the graphon proxy treats attention matrices as noisy observations of affinities sampled from a bounded symmetric kernel, without assuming how input graphs are generated.The diagnostic tests whether the learned attention graphs fit this proxy as graph size grows.Source: §4.1 · p. 5

4.2 ESTIMATING ATTENTION GRAPHONS

• The estimator normalizes graph sizes, sorts nodes by attention degree, then block-averages into a step-function kernel with resolution k = min(64, N).It aggregates estimates across samples; padding preserves weights, and the chosen k avoids empty blocks over evaluated sizes.Source: §4.2 · pp. 5–6
• Degree sorting recovers latent ordering when the graphon degree function is strictly monotone; spectral ordering produced nearly identical variance decay.Strict monotonicity is the stated identifiability condition for this sorting approach.Source: §4.2 · p. 6

4.3 HYPOTHESIS TESTING

• The one-sided test compares empirical variance of cut-norm deviations from the estimated graphon with the Thm. 3.2 bound, using O(n^-1) when smoothness is unknown.Rejecting indicates inconsistency with a common graphon; failing to reject indicates concentration but does not certify a common limit, since nearly uniform attention can also have low dispersion.Source: §4.3 · pp. 6–7

5.1 ESTIMATED ATTENTION GRAPHONS

• On most datasets, empirical cut-norm variance decreases with graph size and remains below the theoretical bound; REDDIT-MULTI-5K exceeds it at its two largest sizes and the test rejects.The experiments use eight real-world graph classification benchmarks and three synthetic node-classification datasets.Source: §5 · p. 7, §5.1 · p. 8
• Estimated kernels become more consistent as size increases while remaining qualitatively distinct across datasets, supporting dataset-dependent interaction structure.The reported estimates cover four datasets with large graphs.Source: §5.1 · p. 8

5.2 TRANSFERABILITY, TRAINING DYNAMICS, AND TASK-HARDNESS

• The transfer accuracy gap decreases as training graph size increases, and SmoothW has smaller transfer error throughout, consistent with its smaller Lipschitz constant.Models trained on smaller graphs can approach large-scale baseline accuracy; graphon-sampled attention reduces inference cost relative to computing query-key products.Source: §5.2 · p. 8, Figure 4 · p. 8
• SharpW has higher training loss, higher effective rank, and lower top-5 energy than SmoothW at every tested size, suggesting less regular kernels are harder to learn.The tested sizes are n ∈ {64, 128, 256, 512}.Source: §5.2 · p. 9
• On synthetic datasets, smoother graphons accompany higher accuracy, but no clear regularity–difficulty correlation emerges on real-world datasets, where features and domain factors also matter.The authors limit the link between regularity and learnability to synthetic data, not a general proxy for task difficulty.Source: §5.2 · p. 9

• For a fixed trained Graph Transformer, attention often has dataset-dependent graphon structure, with cut-norm dispersion decreasing as graph size grows.This provides a way to summarize and compare attention patterns across datasets and scales.Source: §6 · p. 9
• The graphon view is a modeling assumption that may fail for size-dependent attention or discrete structures that a single size-invariant kernel cannot capture.Non-monotonic variance can signal these regimes but can also reflect finite-sample effects or imperfect canonicalization.Source: §6 · p. 9
• The view is less reliable for strongly asymmetric attention, discrete motifs, or degenerate degree profiles that prevent canonicalization from recovering latent order.For sparse attention, vanishing kernel mass can also make variance vanish and the diagnostic fail to reject; tracking kernel mass flags this regime.Source: §6 · p. 9
• Degree sorting is a practical surrogate for optimal cut-metric relabeling, but is not guaranteed to recover latent order; the framework also symmetrizes attention.Directed kernels could instead accommodate raw row-stochastic attention matrices.Source: §6 · p. 9
• Although input graphs may be sparse, attention matrices are dense; how sparse structure, positional encodings, and attention sparsification affect induced kernels remains open.Source: §6 · p. 9
• The per-head diagnostic selects which heads to model by graphons: retain full attention for heads whose test rejects.Kernels in a common function space also allow head comparison; close kernels are candidates for merging or pruning.Source: §6 · p. 9

7 CONCLUSION

• Across benchmarks, attention graphons stabilize and cut-norm variance typically decreases with graph size, supporting the usefulness of graph-limit tools for attention.Source: §7 · p. 9

A RELATED WORK

• Unlike work proposing new Graph Transformer architectures, this work studies whether their induced attention matrices exhibit principled limit behavior as graph size grows.Prior architectures combine global attention with local message passing (Rampášek et al., 2022).Source: A RELATED WORK · p. 14
• Graph attention offers learned dense interactions that can represent long-range dependencies, motivating questions about stability and generalization across graph sizes.This line of work responds to expressive limits associated with local message passing (Morris et al., 2019).Source: A RELATED WORK · p. 14
• Graph-limit theory uses graphons and cut-distance to compare dense graphs across sizes, and has also informed graph neural network transferability.The paper applies this continuum perspective to attention matrices as weighted dense graphs.Source: A RELATED WORK · p. 14
• Graphon estimation offers histogram, optimal-transport, and neural approaches, while minimax theory characterizes rates under regularity assumptions.This work uses graphon estimation to compare attention patterns across datasets and graph sizes, with concentration quantified through cut-distance variance.Source: A RELATED WORK · p. 14

• The matrix cut-norm is defined for A ∈ R^{n×n}; analogously, the kernel cut-norm is defined for K: [0, 1]² → [−1, 1].Source: B PROOF OF THEOREM 3.1 · pp. 14–15
• Cut-distance compares graphs across labelings and sizes, using node replication to align graphs with different numbers of nodes.Source: B PROOF OF THEOREM 3.1 · pp. 14–15
• A graphon is a symmetric measurable kernel, and sampling uniform points from it defines a weighted graph whose induced graphon is denoted W_n.The appendix also defines an unweighted graph model by sampling each edge with probability given by the kernel.Source: B PROOF OF THEOREM 3.1 · p. 15
• Theorem B.10 bounds the variance of cut-distance between a graphon and a random weighted graph sampled from it.W_n denotes the graphon induced by the sampled graph.Source: B PROOF OF THEOREM 3.1 · p. 16
• The proof expands the variance, conditions one term, then applies the sampling lemma and the cut-distance upper bound while disregarding a third term.The resulting rate is stated as O(1/log n).Source: B PROOF OF THEOREM 3.1 · p. 16

C PROOF OF THEOREM 3.2

• The sharper bound assumes a consistent canonical ordering, instantiated by degree sorting under regularity conditions and strict monotonicity of the degree function.The pipeline is identified as a direct instance of the Sort-And-Smooth estimator.Source: C PROOF OF THEOREM 3.2 · p. 17
• The block-average bias is controlled by Hölder regularity only up to min(α,1), so block-constant estimation cannot exploit smoothness beyond Lipschitz.On the specified event, each summand is bounded using latent-position differences of order 1/k.Source: C PROOF OF THEOREM 3.2 · p. 17
• Theorem C.12 gives a regularity-aware cut-norm bound for the block approximation, with rate n^-2min(α,1)/(min(α,1)+1).The rate follows by choosing k = ⌈n^(1/(min(α,1)+1))⌉; the stated high-probability event has probability at least 1 − exp(−c2n).Source: C PROOF OF THEOREM 3.2 · pp. 17–18
• The tighter result uses cut norm under fixed labeling; unlike cut distance, it requires aligned node correspondences to obtain the faster polynomial rate.The more general cut-distance bound has a loose (log n)^−1 rate.Source: C PROOF OF THEOREM 3.2 · pp. 16, 19

D CHOICE OF THE ATTENTION OBJECT

• Post-softmax attention induces cut distance 1/n from the zero graphon for every model, while n times symmetrized attention can have entries at least n/2.Empirically, the largest rescaled entry on NoisyCSBM grows from 90 to 681 as n increases from 128 to 1024, while the largest logit magnitude grows from 42 to 53.Source: D CHOICE OF THE ATTENTION OBJECT · p. 19
• A bijective ρ is needed to recover post-softmax attention from A and to define inverse-transformed scores for kernels sampled at new graph sizes.The section uses the sigmoid, whose inverse is the log-odds function.Source: D CHOICE OF THE ATTENTION OBJECT · p. 20
• The chosen object A = ρ( S̄ − c) stays bounded when pre-softmax scores are bounded, and its cut-distance limits remain within [ρ(−B), ρ(B)].With bounded scores, the resulting attention graph retains mass bounded away from zero and determines post-softmax attention.Source: D CHOICE OF THE ATTENTION OBJECT · p. 20
• The estimation pipeline transforms logits, size-normalizes and degree-sorts each graph, block-averages it, aggregates a template, then computes discrepancies and empirical variance.It reports concentration curves and applies a hypothesis-test decision rule.Source: D CHOICE OF THE ATTENTION OBJECT · p. 21

E ADDITIONAL DETAILS OF SECTION 4

• Within graph-size bins, empirical variance summarizes the cut-norm residuals of per-graph kernel estimates around the dataset-level estimate.The resulting variance curve is compared with the proxy scaling suggested by Theorem 3.2.Source: E ADDITIONAL DETAILS OF SECTION 4 · p. 21
• The test rejects at size n when empirical variance exceeds n^-1 with C = 1, a fixed comparison threshold rather than an estimated dataset-specific constant.The theoretical rate holds up to a regularity- and canonicalization-dependent constant.Source: E ADDITIONAL DETAILS OF SECTION 4 · p. 21
• Because exact cut-norm computation is NP-hard, the experiments use an SDP-relaxation and rounding approximation with a fast orthogonality-constrained optimizer.Distance estimates were stable across restart counts, which were fixed for cross-dataset comparisons.Source: E ADDITIONAL DETAILS OF SECTION 4 · p. 21

F EXPERIMENTAL DETAILS

• The evaluation spans eight real-world graph-classification benchmarks and three synthetic node-classification settings, with 10 runs per experiment and a one-layer GPS setup.The real-world benchmarks cover bioinformatics, social interaction, and 3D point-cloud graphs; the GPS uses hidden dimension 32 and no local message passing.Source: F EXPERIMENTAL DETAILS · pp. 21–22

F.1 SYNTHETIC GRAPHONS

• Synthetic graphs sample latent positions uniformly, connect node pairs according to the graphon, and derive three balanced node-label classes from latent-position terciles.The two graphons are smooth and high-frequency injected smooth, with frequency ω = 16.Source: §F.1 · p. 22, Table 3 · p. 22

F.2 SPECTRAL SUMMARIES OF ESTIMATED ATTENTION GRAPHONS

• Estimated attention graphons are summarized by effective rank, top-5 Frobenius energy, and spectral gap.The gap is defined from the top two eigenvalues.Source: §F.2 · p. 22

F.3 LIPSCHITZ CONSTANT COMPUTATION

• The Lipschitz constant estimate uses an interpolated graphon on a finer 200 × 200 grid and finite-difference partial derivatives.The estimate is the maximum gradient magnitude over grid points.Source: §F.3 · p. 23

G FRAMEWORK PIPELINE

• The framework figure shows a dense weighted attention graph being symmetrized, degree-sorted, and block-averaged to estimate a dataset-level graphon.Its cut-distance illustration describes discrepancy over node subsets.Source: Figure 6 · p. 23

Cut-norm variance: empirical vs. theoretical scaling

• Empirical cut-norm variance tracks below the theoretical proxy across architectures and benchmarks; bootstrap, permutation, and synthetic-null checks support the decay interpretation.Bootstrap intervals are narrow and below the bound; permutation results are strongest on some datasets, while the synthetic null reveals weaker convergence where it remains above the null mean.Source: H ADDITIONAL RESULTS · pp. 23–24, Figure 7 · p. 26

Statistical calibration

• Across tested datasets, bootstrap intervals are narrow, and permutation and synthetic-null tests provide complementary checks on variance decay and weaker convergence.The synthetic null compares trained attention with random symmetric matrices; permutation p-values are near the minimum achievable value on some datasets.Source: H ADDITIONAL RESULTS · p. 24

Single-head attention graphons

• Estimated attention graphons stabilize within datasets as target size grows across GPS, Graphormer-GD, and GRIT.The estimates remain distinct across datasets.Source: H ADDITIONAL RESULTS · p. 24, Figure 8 · p. 27, Figure 10 · p. 29

Multi-head attention graphons

• Four-head GPS estimates show distinct kernel structures across heads on LRGBPeptides, ModelNet10, OGBmolhiv, and REDDIT-MULTI-5K.The per-head limits are still dataset-determined.Source: H ADDITIONAL RESULTS · p. 24, Figure 9 · p. 28

Transferability

• Transferability gaps decrease with graph size across GPS, Graphormer-GD, and GRIT, including GPS in both single- and four-head settings.The reported sweep covers eleven benchmarks for GPS single-head and repeats the analysis across architectures and head settings.Source: H ADDITIONAL RESULTS · p. 24, Figure 18 · p. 34, Figure 20 · p. 35

Sensitivity to block size k

• Changing block size preserves qualitative graphon structure; fixed-K variance curves nearly coincide, and growing resolution differs mainly at the smallest sizes.These results indicate that the default K = 64 does not drive the reported conclusions.Source: H ADDITIONAL RESULTS · pp. 25, 39, Figure 25 · p. 38, Figure 26 · p. 39

Sensitivity to canonicalization

• Degree and spectral canonicalization yield nearly identical variance-decay patterns despite differences in absolute values.The comparison includes MUTAG, PROTEINS, COLLAB, and LRGBPeptides.Source: H ADDITIONAL RESULTS · p. 25, Figure 27 · p. 39, Figure 28 · p. 39

Node features versus graph structure

• Node features contribute to the estimated kernel: randomizing them destroys concentration on synthetic families, while PROTEINS variance is nearly unchanged and its kernel shifts by about 0.16 in relative L1 distance.On the synthetic families, features carry the structural signal that stabilizes attention; on PROTEINS, stability survives their removal.Source: H ADDITIONAL RESULTS · p. 25