Attention Graphons: A Graph Limit Perspective on Graph Transformers

Caio F. Deberaldini Netto; Moshe Eliasof; Luana Ruiz

cs.LGSep 28, 2026

Attention Graphons: A Graph Limit Perspective on Graph Transformers

Authors: Caio F. Deberaldini Netto, Moshe Eliasof, Luana Ruiz

Organizations: Johns Hopkins University Baltimore, MD · University of Cambridge Cambridge, UK

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$ .

Figures & tables

Panel of Figure 1 — Figure 1: Empirical cut-norm variance versus regularity-aware theoretical proxy. Each panel compares the empirical variance of $\|\hat{W}_{r}-\hat{W}\|_{\square}$ against the scaling proxy ${\mathcal{O}}(n^{-1})$ (Thm. 3.2 ).

Panel of Figure 2 — Figure 2: Estimated attention graphons across datasets and graph sizes. Each panel shows the $K{\times}K$ ( $K=64$ ) block-step estimate of the attention kernel at target size $N$ . Top row : Attention graphon convergence for ModelNet10, as target size $N$ grows ( $N\in\{128,256,512,1024\}$ ). Kernel estimates stabilize as $N$ increases and remains distinct across datasets Bottom row : Attention graphon estimate for COLLAB, PROTEINS, and REDDIT-MULTI-5K (resp., $N=\{118,70,705\}$ ).

Figure 3: Training dynamics and spectral summaries under synthetic graphon families. Left : training loss for SmoothW and SharpW at increasing sizes. Middle/right : spectral summaries of the estimated attention graphons (effective rank, top-5 energy, and spectral gap) as size grows. Metrics are defined in Appx F.2 .

Metric $\downarrow$ / Dataset $\rightarrow$	Synthetic			Real-World
Metric $\downarrow$ / Dataset $\rightarrow$	SmoothW	SharpW	NoisyCSBM	MUTAG	Proteins	NCI1	NCI109	Collab	IMDB-M	Reddit-M-5K	ModelNet
Graph size $n$	1024	1024	1024	28	600	111	111	498	89	1024	1024
Lipschitz ( $\hat{L}_{W}$ )	25.02	45.29	64.60	6.36	54.80	27.42	28.34	33.15	20.24	28.14	33.70
Accuracy (%) $\uparrow$	92.18	74.10	58.98	78.95	77.68	66.42	70.46	74.60	56.00	54.20	78.50
Correlation ( $r$ )	$-0.999$ ( $p=0.024$ )			$0.207$ ( $p=0.622$ )

Table 1: Lipschitz constants and test accuracy (%) of estimated attention graphons on synthetic and real-world datasets. For synthetic datasets, the Lipschitz constant correlates with task difficulty. For real-world datasets, it reflects the complexity of learned attention.

Figure 4: Attention graphon transferability to larger graphs. Relative test-accuracy gap between a model trained and evaluated on small graphs and the same model evaluated on a large-scale test set. Results show that training on smaller graphs and transferring can approach the performance of a model trained on larger datasets, while being faster and less computationally intensive. Furthermore, the smoother graphon has better transferability.

Appendix figures & tables33 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Comparison of candidate attention objects. Left : mean entry (solid) and spread (dotted) of the kernels of $\bar{P}$ , $n\bar{P}$ , and $A$ on BFS, for one GPS model trained at $n=32$ and evaluated with frozen weights. Right : largest entry of $n\bar{P}$ and largest logit magnitude on NoisyCSBM. In the legend, $A$ and $nA$ denote $\bar{P}$ and $n\bar{P}$ , and “sigmoid(logits) - offset” denotes $A=\sigma(\bar{S}-c)$ .

Parameter	MUTAG	PROTEINS	NCI1	NCI109	COLLAB	IMDB-MULTI	REDDIT-MULTI-5K	ModelNet10	NoisyCSBM	SmoothW	SharpW
Batch size	128	128	128	128	128	128	128	128	128	128	128
Learning rate	0.001	0.001	0.001	0.001	0.001	0.001	0.001	0.001	0.001	0.001	0.001
Hidden dimension	32	32	32	32	32	32	32	32	32	32	32
Num. of layers	1	1	1	1	1	1	1	1	1	1	1

Appendix

Table 2: GT training hyperparameters for each dataset.

	$W(x,y)$
SmoothW	$xy$
SharpW	$\dfrac{\exp(-xy)+\|\sin(\omega(x+y))\|}{2}$

Appendix

Table 3: Graphons used for the synthetic dataset experiments. The first is a smooth graphon, whereas the second is a high-frequency injected smooth graphon. For all experiments, the frequency used was

\omega=16

Figure 6: Visual explanation of the cut distance $\delta_{\square}$ and graphon computation. Top (cut distance) : The cut distance roughly measures the largest discrepancy over node subsets $S,T$ . Bottom (graphon computation) : From a dense, weighted attention graph with $n=8$ , the matrix is symmetrized, canonicalized via degree sorting, block-averaged, and finally used to estimate a dataset-level graphon.

Panel of Figure 7 — Figure 7: Empirical cut-norm variance versus a regularity-aware theoretical proxy (GPS, single-head). Each panel compares the empirical variance of $\|\hat{W}_{r}-\hat{W}\|_{\square}$ against the size-dependent scaling proxy ${\mathcal{O}}(n^{-1})$ from Theorem 3.2 .

Figure 8: Estimated attention graphons across datasets and graph sizes (GPS, single-head). Each row corresponds to a dataset, and each panel shows the $K{\times}K$ (here $K=64$ ) block-step estimate of the dataset-level attention kernel at a target size $N$ . The target sizes in this figure are: COLLAB ( $N\in\{35,45,63,118\}$ ), PROTEINS ( $N\in\{10,20,33,70\}$ ), ModelNet10 ( $N\in\{128,256,512,1024\}$ ), and REDDIT-MULTI-5K ( $N\in\{121,243,427,705\}$ ). Kernel estimates stabilize within each dataset as $N$ grows while remaining distinct across datasets.

Panel of Figure 9 — Figure 9: Multi-head attention graphons (GPS, 4 heads). Each row corresponds to a dataset (LRGBPeptides, ModelNet10, OGBmolhiv, REDDIT-MULTI-5K), and each column shows the average graphon followed by head-specific graphon estimates ( $h\in\{1,2,3,4\}$ ). Each dataset has a different fixed size ( $N\in\{36,259,427,512\}$ ), as stated in the figures’ titles. Different heads exhibit distinct kernel structures.

Panel of Figure 10 — Figure 10: Estimated attention graphons across datasets and graph sizes (Graphormer-GD, single-head). Each row corresponds to a dataset (COLLAB, IMDB-MULTI, LRGBPeptides, ModelNet10, MUTAG), and each column shows the block-step estimate of the dataset-level attention kernel at increasing target sizes $N$ . Kernel estimates stabilize within each dataset as $N$ grows.

Panel of Figure 11 — Figure 11: Estimated attention graphons across datasets and graph sizes (Graphormer-GD, single-head). Each row corresponds to a dataset (NCI1, NCI109, OGBmolhiv, PROTEINS, REDDIT-MULTI-5K), and each column shows the block-step estimate of the dataset-level attention kernel at increasing target sizes $N$ . Kernel estimates stabilize within each dataset as $N$ grows.

Panel of Figure 12 — Figure 12: Estimated attention graphons across datasets and graph sizes (GRIT, single-head). Each row corresponds to a dataset (COLLAB, IMDB-MULTI, LRGBPeptides, ModelNet10, MUTAG), and each column shows the block-step estimate of the dataset-level attention kernel at increasing target sizes $N$ . Kernel estimates stabilize within each dataset as $N$ grows.

Panel of Figure 13 — Figure 13: Estimated attention graphons across datasets and graph sizes (GRIT, single-head). Each row corresponds to a dataset (NCI1, NCI109, OGBmolhiv, PROTEINS, REDDIT-MULTI-5K), and each column shows the block-step estimate of the dataset-level attention kernel at increasing target sizes $N$ . Kernel estimates stabilize within each dataset as $N$ grows.

Panel of Figure 14 — Figure 14: Empirical cut-norm variance versus theoretical proxy (GPS, 4 heads). Each panel compares the empirical variance of $\|\hat{W}_{r}-\hat{W}\|_{\square}$ against the size-dependent scaling proxy ${\mathcal{O}}(n^{-1})$ from Theorem 4.2. The target sizes $N$ are dataset-dependent.

Panel of Figure 15 — Figure 15: Stronger hypothesis test results (GPS, single-head). Each panel shows the results of the stronger hypothesis test for the corresponding dataset. Each panel compares the empirical variance against the synthetic null, shown as its mean (dashed) with a band of one standard deviation , and against the scaling proxy ${\mathcal{O}}(n^{-1})$ (dotted).

Panel of Figure 16 — Figure 16: Empirical cut-norm variance versus theoretical proxy (Graphormer-GD, single-head). Each panel compares the empirical variance of $\|\hat{W}_{r}-\hat{W}\|_{\square}$ against the size-dependent scaling proxy ${\mathcal{O}}(n^{-1})$ from Theorem 4.2. The target sizes $N$ are dataset-dependent.

Panel of Figure 17 — Figure 17: Empirical cut-norm variance versus theoretical proxy (GRIT, single-head). Each panel compares the empirical variance of $\|\hat{W}_{r}-\hat{W}\|_{\square}$ against the size-dependent scaling proxy ${\mathcal{O}}(n^{-1})$ from Theorem 4.2. The target sizes $N$ are dataset-dependent.

Panel of Figure 18 — Figure 18: Transferability gap across graph sizes (GPS, single-head). Each panel shows the transferability gap as a function of graph size for the corresponding dataset.

Panel of Figure 19 — Figure 19: Transferability gap across graph sizes (GPS, single-head). Each panel shows the transferability gap as a function of graph size for the corresponding dataset.

Panel of Figure 20 — Figure 20: Transferability gap across graph sizes (GPS, 4 heads). Each panel shows the transferability gap as a function of graph size for the corresponding dataset.

Panel of Figure 21 — Figure 21: Transferability gap across graph sizes (GPS, 4 heads). Each panel shows the transferability gap as a function of graph size for the corresponding dataset.

Panel of Figure 22 — Figure 22: Transferability gap across graph sizes (Graphormer-GD, single-head). Each panel shows the transferability gap as a function of graph size for the corresponding dataset.

Panel of Figure 23 — Figure 23: Transferability gap across graph sizes (GRIT, single-head). Each panel shows the transferability gap as a function of graph size for the corresponding dataset.

Panel of Figure 24 — Figure 24: Runtime analysis of the graphon estimation pipeline. Each panel shows the per-graph runtime (in seconds, log scale) as a function of graph size $n$ for the corresponding dataset. The runtime is decomposed into Estimation , which computes the attention graph, orders its nodes, and computes the block averages, and Cutnorm , the approximate cut-norm computation, which add up to the Total . The Node ordering curve times the ${\mathcal{O}}(nd)$ computation of the ordering statistic from queries and keys, without forming the $n\times n$ matrix. Estimation remains nearly constant across graph sizes, while the cut-norm computation dominates the total runtime. Overall, the pipeline processes each graph in tens of milliseconds, even for larger graphs.

Panel of Figure 25 — Figure 25: Sensitivity of graphon estimation to block size $K$ . Each row corresponds to a dataset (BFS, COLLAB, Dijkstra, LRGBPeptides, PROTEINS), and each column shows the estimated graphon for increasing block sizes ( $K\in\{16,32,64,128\}$ ). Larger values of $K$ yield finer-grained estimates. The estimated graphons remain qualitatively stable across different values of $K$ , demonstrating robustness of the estimation procedure to this hyperparameter choice.

Panel of Figure 26 — Figure 26: Sensitivity of hypothesis test to block size $K$ . Each panel shows the empirical variance of the cut-norm as a function of graph size $n$ for $K\in\{16,32,64,128\}$ and for the growing resolution $K_{n}=\lceil\sqrt{n}\rceil$ (dashed), compared against the scaling proxy ${\mathcal{O}}(n^{-1})$ (dotted). The curves for fixed $K$ nearly coincide and lie well below the proxy, and the growing resolution gives a lower variance only at the smallest sizes, where it uses few blocks. The results therefore do not depend on the default $K=64$ .

Panel of Figure 27 — Figure 27: Sensitivity of hypothesis test to canonicalization method. Each panel compares the empirical variance of cut-distance using two canonicalization methods: degree sorting and spectral sorting (via Fiedler vector), against the theoretical bound . Despite differences in absolute values, the two methods exhibit nearly identical decay patterns across all datasets, with curves closely aligned in log-log scale. This demonstrates that our findings are robust to the choice of canonicalization method, and the observed variance decay reflects genuine properties of the learned attention rather than artifacts of a particular node ordering strategy.

Panel of Figure 28 — Figure 28: Sensitivity of hypothesis test to canonicalization method (MUTAG). On each panel: on the left is the estimated graphon via degree sorting, while on the right via Fiedler vector sorting.

Panel of Figure 29 — Figure 29: Sensitivity of hypothesis test to canonicalization method (PROTEINS). On each panel: on the left is the estimated graphon via degree sorting, while on the right via Fiedler vector sorting.

Panel of Figure 30 — Figure 30: Sensitivity of hypothesis test to canonicalization method (COLLAB). On each panel: on the left is the estimated graphon via degree sorting, while on the right via Fiedler vector sorting.

Panel of Figure 31 — Figure 31: Sensitivity of hypothesis test to canonicalization method (LRGBPeptides). On each panel: on the left is the estimated graphon via degree sorting, while on the right via Fiedler vector sorting.

$n$	Dense $\tilde{P}V$	Factorized	Speed-up
512	13.9 ms	0.6 ms	$22.7\times$
2048	8.9 ms	1.5 ms	$5.8\times$
8192	19.2 ms	4.7 ms	$4.1\times$

Appendix

Table 4: Runtime of the dense product

\tilde{P}V

and of the factorized product

Z(\tilde{\Theta}(Z^{\top}V))

for

d_{v}=32

Dataset	Features	Variance ratio (randomized / original)
SmoothW	Random-walk PE	380	931	$1.9\times 10^{4}$	$2.7\times 10^{5}$
SharpW	Random-walk PE	$1.8\times 10^{8}$	$2.8\times 10^{9}$	$1.2\times 10^{10}$	$1.4\times 10^{9}$
PROTEINS	Node attributes	1.00	1.01	1.00	1.00

Appendix

Table 5: Ratio of cut-norm variances after and before replacing node features with i.i.d. noise, over the four sizes of each sweep in increasing order.

Dataset	Range	Dataset	Range
BFS	0.006–0.070	MUTAG	0.064–0.247
NCI1	0.009–0.114	REDDIT-MULTI-5K	0.047–0.217
IMDB-MULTI	0.041–0.074	PROTEINS	0.113–0.260
ModelNet10	0.051–0.333	COLLAB	0.082–0.284

Appendix

Table 6: Relative symmetrization residual

\|P-\bar{P}\|_{F}/\|P\|_{F}

, as a range over the sizes of each sweep.

Panel of Figure 32 — Figure 32: Attention restricted to input edges on NoisyCSBM (GPS, single-head), against full attention. Left : empirical variance and the scaling proxy ${\mathcal{O}}(n^{-1})$ . Right : cut norm $\|\hat{W}\|_{\square}$ of the estimated kernel, which vanishes when attention is masked.

Explore similar work

Capacity-Controlled Global Attention for Graph Transformers
Apr 19, 2026Yang Liu, Dongxin Guo, Tom Zheng +3Transformer Attention Linear Attention
Brain Investing Limited Hong Kong, China · The University of Hong Kong Hong Kong, China · Stellaris AI Limited Hong Kong, China
Graph Convolutional Attention: A Spectral Perspective on Graph Denoising and Diffusion
Jul 7, 2026Shervin Khalafi, Igor Krawczuk, Sergio Rozada +3Interleaved Graph Attention Iterative Denoising Methods
University of Pennsylvania · King Juan Carlos University · Stanford University
Attention Dispersion in Dynamic Graph Transformers: Diagnosis and a Transferable Fix
May 15, 2026Jinhao Zhang, Kangfei Zhao, Qiuhao Zeng +1Multiplex Graph Transformers Transformer Attention
Beijing Institute of Technology · University of Toronto · Hong Kong Baptist University

Apr 19, 2026, cs.LGJ/K move · Enter open · S save

Capacity-Controlled Global Attention for Graph Transformers

Yang Liu, Dongxin Guo, Tom Zheng, Siu Ming Yiu+2

Brain Investing Limited Hong Kong, China · The University of Hong Kong Hong Kong, China · Stellaris AI Limited Hong Kong, China

Transformer Attention Linear Attention Bottlenecks

Open paper AskPDF arXiv

Global self-attention drives modern graph transformers, yet the softmax at its core imposes a structural constraint rarely examined directly: every attention row is non-negative and sums to one, so each per-head output is a mass-conserving convex combination of value vectors. A node can never "attend to nothing." We argue this conservation constraint is a single root cause behind three pathologies usually studied in isolation: the collapse of node representations with depth (over-smoothing), a low-rank bottleneck on per-head outputs, and brittle optimization in deep stacks. Drawing on how sigmoid gating removes analogous attention sinks in language models, we introduce SigGate-GT, a graph transformer that applies a learned, per-head, input-conditioned sigmoid gate to the attention output inside the GraphGPS framework. The gate is a smooth, per-dimension "volume control" that can drive head outputs toward zero, relaxing the constraint without abandoning attention's probabilistic interpretation. Analytically and through synthetic experiments, we show the gate strictly increases the stable rank of per-head outputs, and connect this rank gain to all three manifestations. On five molecular and long-range benchmarks, SigGate-GT matches the prior best on ZINC (0.059 MAE), records the strongest result among the graph-transformer baselines we evaluate on ogbg-molhiv (82.47% ROC-AUC), and is competitive on ogbg-molpcba and the Long-Range Graph Benchmark, with statistically significant gains over GraphGPS on all five datasets (p < 0.05). Mechanism analyses confirm the diagnosis: gating slows over-smoothing (a 30% mean relative gain in representation diversity across 4-16 layers), keeps attention entropy from collapsing, and stabilizes training across a 10x learning-rate range, at about 1% parameter overhead on OGB and under 3% wall-clock cost.

Abstract

Explore similar work

Capacity-Controlled Global Attention for Graph Transformers

Graph Convolutional Attention: A Spectral Perspective on Graph Denoising and Diffusion

Attention Dispersion in Dynamic Graph Transformers: Diagnosis and a Transferable Fix