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

Apr 19, 2026cs.LG

Capacity-Controlled Global Attention for Graph Transformers

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.

Yang Liu, Dongxin Guo, Tom Zheng +3

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

Ask PDF

Jul 7, 2026cs.LG

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

Denoising graphs is a fundamental problem in graph learning and the core operation of graph diffusion models. Attention-based architectures like graph transformers have recently shown promise in denoising graphs. However, our principled understanding of attention-based graph denoising remains limited, making it unclear whether standard attention is the right mechanism for this task. Here we show that, under a denoising objective, linear attention is suboptimal and can only learn an average spectral denoising filter over the training distribution. This creates a fundamental limitation as graphs often vary spectrally across the distribution. To overcome this limitation, we introduce Spectral Attention, which directly utilizes the input graph spectrum and provably outperforms linear attention by a margin governed by the spectral diversity of the distribution. We then derive Graph Convolutional Attention (GCA), a practical and permutation-equivariant realization of this idea that implements spectral denoising through graph-filtered queries and keys. For stochastic block models, GCA provably matches the idealized Spectral Attention mechanism. We further show that the softmax operation, that follows the attention, provides additional denoising by approximately projecting noisy eigenvectors onto the clean eigenspace. Empirically, replacing linear attention with GCA consistently improves graph denoising and diffusion on synthetic and real datasets, with gains strongly correlated with spectral diversity. In DiGress, GCA matches standard graph-transformer performance without computing expensive structural features, and when combined with the recently proposed PEARL positional encodings, avoids explicit eigendecomposition computations resulting in faster inference without degrading quality. The code can be found here: github.com/shervinkhalafi/graph_conv_att

Shervin Khalafi, Igor Krawczuk, Sergio Rozada +3

University of Pennsylvania · King Juan Carlos University · Stanford University

Interleaved Graph Attention Iterative Denoising Methods Convolutional Block Attention Module Spectral Transformer Architectures

Ask PDF

May 15, 2026cs.LG

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

Transformer-based architectures have become the dominant paradigm for Continuous-Time Dynamic Graph (CTDG) learning, yet their performance remains limited on temporally shifted datasets. In this work, we identify attention dispersion as a shared failure mode of dynamic graph Transformers under temporal distribution shift. Through controlled ablation contrasting structurally and temporally distinguished historical neighbors against random ones, we show that prediction depends on a class of critical nodes that carry consistently more predictive signal than arbitrary neighbors. However, existing Transformers fail to focus on these nodes even when they are present in the input, as temporal shift weakens attention contrast and produces overly dispersed attention distributions. This diagnosis suggests a simple and transferable fix: replace standard attention with differential attention, which suppresses common-mode attention and amplifies distinctive token-level signals. When added to three representative CTDG Transformer baselines, differential attention consistently improves performance, with gains concentrated on high-shift datasets. Attention-level measurements further confirm the mechanism, showing reduced attention entropy and increased attention mass on critical nodes. Building on these findings, we introduce DiffDyG, a reference implementation combining differential attention with standard input encodings. Across 9 benchmarks and three negative sampling protocols, DiffDyG achieves SOTA performance, with especially large gains on the most shifted datasets.

Jinhao Zhang, Kangfei Zhao, Qiuhao Zeng +1

Beijing Institute of Technology · University of Toronto · Hong Kong Baptist University

Multiplex Graph Transformers Transformer Attention Transformer Architectures

Ask PDF