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

Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers
May 21, 2026Maya Bechler-Speicher, Gilad Yehudai, Gil Harari +3Transformer Expressivity Graph Representation Learning
Meta AI · John A. Paulson School of Engineering and Applied Sciences, Harvard University · Google Research +2
Attention Graphons: A Graph Limit Perspective on Graph Transformers
Sep 28, 2026Caio F. Deberaldini Netto, Moshe Eliasof, Luana RuizTransformer Attention Graph Transformer
Johns Hopkins University Baltimore, MD · University of Cambridge Cambridge, UK
k-Maximum Inner Product Attention for Graph Transformers and the Expressive Power of GraphGPS
Apr 4, 2026Jonas De Schouwer, Haitz Sáez de Ocáriz Borde, Xiaowen DongTransformer Attention Graph Transformer
Stanford University · University of Oxford

May 21, 2026J/K move · Enter open · S save

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

Maya Bechler-Speicher, Gilad Yehudai, Gil Harari, Clayton Sanford+2

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

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

Attention Graphons: A Graph Limit Perspective on Graph Transformers

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