Gaussian Process Limit Reveals Structural Benefits of Graph Transformers

Nil Ayday; Lingchu Yang; Debarghya Ghoshdastidar

stat.MLMar 18, 2026

Gaussian Process Limit Reveals Structural Benefits of Graph Transformers

Authors: Nil Ayday, Lingchu Yang, Debarghya Ghoshdastidar

Organizations: School of Computation, Information and Technology, Technical University of Munich · Graduate School of Information Science and Technology, The University of Tokyo

Abstract

Graph transformers are the state-of-the-art for learning from graph-structured data and are empirically known to avoid several pitfalls of message-passing architectures. However, there is limited theoretical analysis on why these models perform well in practice. In this work, we prove that attention-based architectures have structural benefits over graph convolutional networks in the context of node-level prediction tasks. Specifically, we study the neural network gaussian process limits of graph transformers (GAT, Graphormer, Specformer) with infinite width and infinite heads, and derive the node-level and edge-level kernels across the layers. Our results characterise how the node features and the graph structure propagate through the graph attention layers. As a specific example, we prove that graph transformers structurally preserve community information and maintain discriminative node representations even in deep layers, thereby preventing oversmoothing. We provide empirical evidence on synthetic and real-world graphs that validate our theoretical insights, such as integrating informative priors and positional encoding can improve performance of deep graph transformers.

Figures & tables

Panel of Figure 1 — Figure 1: Histogram of the output of GAT and Graphormer for different number of heads. The output distribution converges to a Gaussian (red line) fitted with mean and variance of the empirical distribution when both width and number of heads are large. Plots for Specformer is in Appendix F .

Model	Edge/Structural Kernel ( $K^{(\ell),E}_{ab}$ or ${K_{\lambda}}_{,ab}$ )	Node Kernel $\Sigma^{(\ell)}_{ab}$
GAT-GP (Theorem 6 )	$\sigma_{w}^{2}\sigma_{v}^{2}\bigl(K^{(\ell-1)}_{ab}+K^{(\ell-1)}_{ij}\bigr)$	$\sigma_{H}^{2}\sigma_{w}^{2}\sum_{i\in N_{a}}\sum_{j\in N_{b}}K^{(\ell-1)}_{ij}\,C^{(\ell)}_{ai,bj}$
Graphormer-GP (Theorem 9 )	$\Big(\sigma_{Q}^{2}\sigma_{K}^{2}\,\tilde{K}^{(\ell-1)}_{ab}\,\tilde{K}^{(\ell-1)}_{ij}+\sigma_{b}^{2}\,\mathbf{1}_{\phi(a,i)=\phi(b,j)}\Big)$	$\sigma_{H}^{2}\sigma_{w}^{2}\sum_{i,j\in V}\tilde{K}^{(\ell-1)}_{ij}C^{(\ell)}_{ai,bj}$
Specformer-GP (Theorem 11 )	$K_{\lambda,ab}=\mathbb{E}[\bar{\lambda}_{a}\bar{\lambda}_{b}]$ (Spectral)	$\sigma_{H}^{2}\sigma_{w}^{2}U(K_{\lambda}\odot(U^{\top}K^{(\ell-1)}U))U^{\top}$

Table 1: Summary of the GP kernels for graph transformers. The weight priors are in Table 4 in Appendix B . The table presents both the edge/structural kernels (

K^{(\ell),E}_{ab}

for spatial models or

K_{\lambda,ab}

for Specformer) and the node-level kernels (

\Sigma^{(\ell)}_{ab}

) that describe the propagation of covariance across layers. For GAT-GP and Graphormer-GP, the edge-level kernels capture correlations between attention scores, while the node-level kernels aggregate these correlations. The learned spectral kernel

K_{\lambda}

of Specformer-GP modulates the mapping of node representations in the Laplacian eigenbasis.

Model	Node Kernel ( $K^{(\ell)}$ )
GCN-GP [ Niu et al., 2023 ]	$K^{(\ell)}=\sigma_{w}^{2}AK^{\ell-1}A^{T}$
GAT-GP (Corollary 8 )	$K^{(\ell)}=\sigma_{H}^{2}\sigma_{w}^{4}\sigma_{v}^{2}\Big(K^{(\ell-1)}\odot(AK^{(\ell-1)}A^{\top})+A(K^{(\ell-1)}\odot K^{(\ell-1)})A^{\top}\Big)$
Graphormer-GP (Corollary 10 )	$K^{(\ell)}_{ab}=\sigma_{H}^{2}\sigma_{w}^{2}\Bigg[\sigma_{Q}^{2}\sigma_{K}^{2}\,\tilde{K}^{(\ell)}_{ab}\sum_{i,j\in V}\tilde{K}^{(\ell-1)}_{ij}\,\tilde{K}^{(\ell-1)}_{ij}+\sigma_{b}^{2}\sum_{i,j\in V}\tilde{K}^{(\ell-1)}_{ij}\,\mathbf{1}_{\rho(a,i)=\rho(b,j)}\Bigg]$
Specformer-GP (Theorem 11 )	$K^{(\ell)}=\sigma_{H}^{2}\sigma_{w}^{2}U(K_{\lambda}\odot(U^{\top}K^{(\ell-1)}U))U^{\top}$

Table 2: Closed-form expressions for the node-level Gaussian process (GP) kernels under linear attention and linear activation. These kernels provide an explicit characterization of kernel propagation for each architecture. For comparison, the GCN-GP kernel from [ Niu et al., 2023 ] is included, which does not involve attention.

Model	Intra/Inter-Community Formulas ( $x_{\ell},y_{\ell}$ )	Oversmoothing ( $\ell\to\infty$ )
GCN-GP	$\frac{1}{2}(\frac{n}{2})^{2\ell}\left[(x_{0}+y_{0})(p+q)^{2\ell}\pm(x_{0}-y_{0})(p-q)^{2\ell}\right]$ (Corollary 36 )	Yes (Corollary 1 )
GAT-GP	$\frac{1}{2}\frac{G^{2\ell}}{(\frac{n}{2})^{2}(p+q)^{2}}\left[1\pm\left(\frac{x_{0}-y_{0}}{x_{0}+y_{0}}\right)F^{\ell}\right]$ (Corollary 37 )	No, if communities are separated ( $F\geq 1$ ) (Corollary 2 )
Graphormer-GP	$\tilde{x}_{\ell}=\alpha^{\ell}x_{0}+(1-\alpha^{\ell})p,\quad\tilde{y}_{\ell}=\alpha^{\ell}y_{0}+(1-\alpha^{\ell})q$ (Corollary 38 )	No, if the prior ( $R$ ) captures communities (Remark 3 )
Specformer-GP	$\frac{1}{2}\left[(x_{0}+y_{0})\bar{\lambda}_{1}^{2\ell}\pm(x_{0}-y_{0})\bar{\lambda}_{2}^{2\ell}\right]$ (Corollary 39 )	No, if $\|\bar{\lambda}_{2}\|\geq\|\bar{\lambda}_{1}\|$ (Remark 5 )

Table 3: Evolution of the GP kernel

K^{(\ell)}=\left(\begin{smallmatrix}x_{\ell}\mathbf{1}\mathbf{1}^{\top}&y_{\ell}\mathbf{1}\mathbf{1}^{\top}\\ y_{\ell}\mathbf{1}\mathbf{1}^{\top}&x_{\ell}\mathbf{1}\mathbf{1}^{\top}\end{smallmatrix}\right)

under CSBM and conditions for oversmoothing. To preserve community structure, the kernel must maintain a gap between the intra-community (

x_{\ell}

) and inter-community (

y_{\ell}

) values; this discriminative signal is captured by the second term in each expression.The second column indicates whether oversmoothing occurs as

\ell\to\infty

, i.e., whether the kernel loses its ability to distinguish the two communities. For graph transformers oversmoothing can be avoided, maintaining the discriminative signal across layers.

Figure 2: Oversmoothing behaviour and the impact of positional encodings. Test accuracy of Graphormer-GP on Chameleon (left) and SBM with random features (right) as a function of the number of layers. While accuracy in graph models typically suffers from performance degradation with an increasing number of layers, Graphormer-GP exhibits increasing accuracy with depth when utilizing informative positional encodings, such as Laplacian Eigenvectors (blue) and Spectral Reconstruction (orange). This empirical trend aligns with the theoretical results in Corollary 3 .

Figure 3: Oversmoothing behaviour across various GNN-GP architectures. Test accuracy is shown as a function of depth for the original models (left) and models augmented with Laplacian Eigenvectors (right). In the original configurations, GCN-GP (blue) consistently suffers from a performance drop-off as the number of layers increases . In contrast, GAT-GP (orange) demonstrates resilience to depth , maintaining stable performance as argued in Corollary 2 . The behavior of Specformer-GP and Graphormer-GP depends on the dataset. Notably, upon incorporating Laplacian Eigenvectors (right), the tendency to oversmooth is significantly mitigated across all architectures.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Model	Weight Priors (Variance)
GAT	$W^{\ell,H}_{ij}\sim\mathcal{N}\!\left(0,\frac{\sigma_{H}^{2}}{d^{\ell,H}d_{\ell-1}}\right),W^{\ell,h}_{ij}\sim\mathcal{N}\!\left(0,\frac{\sigma_{w}^{2}}{d_{\ell-1}}\right),\vec{v}^{\ell h}_{k}\sim\mathcal{N}\!\left(0,\frac{\sigma_{v}^{2}}{d_{\ell-1}}\right)$
Graphormer	$W^{Q,\ell h}_{ij}\sim\mathcal{N}\!\left(0,\frac{\sigma_{Q}^{2}}{d_{\ell-1}}\right),W^{K,\ell h}_{ij}\sim\mathcal{N}\!\left(0,\frac{\sigma_{K}^{2}}{d_{\ell-1}}\right),W^{\ell,H}_{ij}\sim\mathcal{N}\!\left(0,\frac{\sigma_{H}^{2}}{d^{\ell,H}d_{\ell-1}}\right),W^{V,\ell h}_{ij}\sim\mathcal{N}\!\left(0,\frac{\sigma_{w}^{2}}{d_{\ell-1}}\right),b_{\rho}(i,j)\sim\mathcal{N}(0,\sigma_{b}^{2})$
Specformer	$W^{Q,tkh}_{ij}\sim\mathcal{N}(0,\sigma_{Q}^{2}/d_{t-1}),\quad W^{K,tkh}_{ij}\sim\mathcal{N}(0,\sigma_{K}^{2}/d_{t-1}),\quad W^{V,tkh}_{ij}\sim\mathcal{N}(0,\sigma_{V}^{2}/d_{t-1}),W^{th,H}_{ij}\sim\mathcal{N}\!\Big(0,\frac{\sigma_{O}^{2}}{d^{t,H}d_{t-1}}\Big),$

Appendix

Table 4: Summary of the Gaussian weight priors used for each graph transformer in the GP analysis. These priors define the variance of the initial weights for all linear transformations and attention parameters.

Dataset	GCN	GAT	HAN	GTN	GTN-GP
DBLP	87.30	93.71	92.83	94.18	94.33
ACM	91.60	92.33	90.96	92.68	92.19
IMDB	56.89	58.14	56.77	60.92	60.50

Appendix

Table 5: Node classification accuracy on heterogeneous graphs.

Dataset	Level	Splits	Nodes	Edges	Classes	Features	Homophily
Pubmed	Node	1	19,717	44,338	3	500	0.80
Chameleon	Node	10	2,277	31,421	10	2,325	0.23

Appendix

Table 6: Dataset statistics for node-level classification tasks.

Dataset	Nodes	Edges	Edge type	Features	Training	Validation	Test
DBLP	18405	67946	4	334	800	400	2857
ACM	8994	25922	4	1902	600	300	2125
IMDB	12772	37288	4	1256	300	300	2339

Appendix

Table 7: Datasets for node classification on heterogeneous graphs.

Figure 4: Histogram of the eigenvalue encoding of Specformer for different number of heads. The output distribution converges to a Gaussian (red line) fitted with mean and variance of the empirical distribution when both width and number of heads are large.

Figure 5: Oversmoothing behaviour and the impact of positional encodings. Test accuracy of Graphormer-GP on Pubmed (left) and CSBM (right) as a function of the number of layers.

Explore similar work

May 21, 2026

Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers

Transformers have become a central architecture for graph learning, but their application to graphs requires first choosing a tokenization: a graph-to-token map that determines which structural information is exposed at the input. In this work, we show that this choice is a fundamental component of transformer expressivity. We examine three tokenizations that serve as building blocks for many existing graph tokenizations: spectral, random-walk, and adjacency tokenizations. We prove that different tokenizations induce distinct depth regimes: the same graph computation may be realizable by a shallow transformer under one tokenization, while requiring substantially larger depth under another. For example, we prove that random-walk tokenization is lossy for any walk length, making it impossible in general to recover the graph from it, and that while spectral tokenization is lossless, it is ill-conditioned for local tasks. We further show that although both random-walk and spectral tokenizations are derived from adjacency information, it is impossible for a limited-depth transformer to convert between tokenization families in general. In particular, we establish lower bounds and impossibility results showing that unfavorable tokenizations may preclude the efficient recovery of more suitable structural representations. Finally, we complement our theory with controlled experiments on synthetic and real-world tasks, validating the predicted separations and showing that different tasks favor different structural views, and combining complementary tokenizations allows the transformer to leverage distinct signals from each representation.

Maya Bechler-Speicher, Gilad Yehudai, Gil Harari +3

Meta AI · John A. Paulson School of Engineering and Applied Sciences, Harvard University · Google Research +2

Transformer Expressivity Graph Representation Learning Neural Network Expressivity Graph Transformer

Ask PDF

Sep 28, 2026

Attention Graphons: A Graph Limit Perspective on Graph Transformers

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

Caio F. Deberaldini Netto, Moshe Eliasof, Luana Ruiz

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

Transformer Attention Graph Transformer

Ask PDF

Apr 4, 2026

k-Maximum Inner Product Attention for Graph Transformers and the Expressive Power of GraphGPS

Graph transformers have shown promise in overcoming limitations of traditional graph neural networks, such as oversquashing and difficulties in modeling long-range dependencies. However, their application to large-scale graphs is hindered by the quadratic memory and computational complexity of the all-to-all attention mechanism. Although alternatives such as linearized attention and restricted attention patterns have been proposed, these often degrade performance or limit expressive power. To better balance efficiency and effectiveness, we introduce k-Maximum Inner Product (k-MIP) attention for graph transformers. k-MIP attention selects the most relevant key nodes per query via a top-k operation, yielding a sparse yet flexible attention pattern. Combined with an attention score computation based on symbolic matrices, this results in linear memory complexity and practical speedups of up to an order of magnitude compared to all-to-all attention, enabling the processing of graphs with over 500k nodes on a single A100 GPU. We provide a theoretical analysis of expressive power, showing that k-MIP attention does not compromise the expressiveness of graph transformers: specifically, we prove that k-MIP transformers can approximate any full-attention transformer to arbitrary precision. In addition, we analyze the expressive power of the GraphGPS framework, in which we integrate our attention mechanism, and establish an upper bound on its graph distinguishing capability in terms of the S-SEG-WL test. Finally, we validate our approach on the Long Range Graph Benchmark, the City-Networks benchmark, and two custom large-scale inductive point cloud datasets, consistently ranking among the top-performing scalable graph transformers.

Jonas De Schouwer, Haitz Sáez de Ocáriz Borde, Xiaowen Dong

Stanford University · University of Oxford

Transformer Attention Graph Transformer Sparse Attention GNN Expressivity

Ask PDF