# Gaussian Process Limit Reveals Structural Benefits of Graph Transformers

arXiv: https://arxiv.org/abs/2603.17569 · HTML: https://mlsanity.com/paper/2603.17569/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 27 references that are in the map.
- First posted on arXiv 18 Mar 2026.

## Builds on (most cited first, 21 of 21)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [Gaussian Process Behaviour in Wide Deep Neural Networks](https://mlsanity.com/paper/1804.11271/) (2018)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [On the Inductive Bias of Neural Tangent Kernels](https://mlsanity.com/paper/1905.12173/) (2019)
- [Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes](https://mlsanity.com/paper/1810.05148/) (2018)
- [Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation](https://mlsanity.com/paper/1902.04760/) (2019)
- [GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph](https://mlsanity.com/paper/2105.02605/) (2021)
- [Deep Convolutional Networks as shallow Gaussian Processes](https://mlsanity.com/paper/1808.05587/) (2018)
- [Infinite attention: NNGP and NTK for deep attention networks](https://mlsanity.com/paper/2006.10540/) (2020)
- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [Specformer: Spectral Graph Neural Networks Meet Transformers](https://mlsanity.com/paper/2303.01028/) (2023)
- [GEMSEC: Graph Embedding with Self Clustering](https://mlsanity.com/paper/1802.03997/) (2018)
- [A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2212.10701/) (2022)
- [Demystifying Oversmoothing in Attention-Based Graph Neural Networks](https://mlsanity.com/paper/2305.16102/) (2023)
- [On the Expressive Power of Spectral Invariant Graph Neural Networks](https://mlsanity.com/paper/2406.04336/) (2024)
- [Analysis of Convolutions, Non-linearity and Depth in Graph Neural Networks using Neural Tangent Kernel](https://mlsanity.com/paper/2210.09809/) (2022)
- [Graph Neural Network-Inspired Kernels for Gaussian Processes in Semi-Supervised Learning](https://mlsanity.com/paper/2302.05828/) (2023)

## Built on by (most cited first, 2 of 2)

- [Different Statistical Perspectives for Understanding Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2605.25452/) (2026)
- [Lifting Finite-Sample Gaussian Approximation of Wide Neural Networks to Functional Convergence](https://mlsanity.com/paper/2610.18166/) (2026)

## Abstract (arXiv)

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.