Gaussian Process Limit Reveals Structural Benefits of Graph Transformers

• URL: http://arxiv.org/abs/2603.17569v1
• Date: Wed, 18 Mar 2026 10:18:21 GMT
• Title: Gaussian Process Limit Reveals Structural Benefits of Graph Transformers
• Abstract summary: We prove that attention-based architectures have structural benefits over graph convolutional networks in the context of node-level prediction tasks.<n>Specifically, we study the neural network gaussian process limits of graph transformers with infinite width and infinite heads.<n>As a specific example, we prove that graph transformers structurally preserve community information and maintain discriminative node representations even in deep layers.
• Score: 7.277122777390684
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Spectral Neural Graph Sparsification [0.21932521132244476]
  Graphs are central to modeling complex systems in domains such as social networks, molecular chemistry, and neuroscience.<n>We propose the Spectral Preservation Network, a new framework for graph representation learning that generates reduced graphs serving as faithful proxies of the original.<n>We evaluate the effectiveness of Spectral Preservation Network on node-level sparsification by analyzing well-established metrics and benchmarking against state-of-the-art methods.
  arXiv  Detail & Related papers  (2025-10-31T13:51:50Z)
• A Survey of Graph Transformers: Architectures, Theories and Applications [54.561539625830186]
  Recent studies have proposed diverse architectures, enhanced explainability, and practical applications for Graph Transformers.<n>We categorize the architecture of Graph Transformers according to their strategies for processing structural information.<n>We provide a summary of the practical applications where Graph Transformers have been utilized, such as molecule, protein, language, vision, traffic, brain and material data.
  arXiv  Detail & Related papers  (2025-02-23T10:55:19Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  Graph Transformers, which incorporate self-attention and positional encoding, have emerged as a powerful architecture for various graph learning tasks. This paper introduces first theoretical investigation of a shallow Graph Transformer for semi-supervised classification.
  arXiv  Detail & Related papers  (2024-06-04T05:30:16Z)
• Are More Layers Beneficial to Graph Transformers? [97.05661983225603]
  Current graph transformers suffer from the bottleneck of improving performance by increasing depth. Deep graph transformers are limited by the vanishing capacity of global attention. We propose a novel graph transformer model named DeepGraph that explicitly employs substructure tokens in the encoded representation.
  arXiv  Detail & Related papers  (2023-03-01T15:22:40Z)
• Attending to Graph Transformers [5.609943831664869]
  transformer architectures for graphs emerged as an alternative to established techniques for machine learning with graphs. Here, we derive a taxonomy of graph transformer architectures, bringing some order to this emerging field. We probe how well graph transformers can recover various graph properties, how well they can deal with heterophilic graphs, and to what extent they prevent over-squashing.
  arXiv  Detail & Related papers  (2023-02-08T16:40:11Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  We propose a graph convolutional relationship between the observed and latent graphs, and formulate the graph learning task as a network inverse (deconvolution) problem. In lieu of eigendecomposition-based spectral methods, we unroll and truncate proximal gradient iterations to arrive at a parameterized neural network architecture that we call a Graph Deconvolution Network (GDN) GDNs can learn a distribution of graphs in a supervised fashion, perform link prediction or edge-weight regression tasks by adapting the loss function, and they are inherently inductive.
  arXiv  Detail & Related papers  (2022-05-19T14:08:15Z)
• Graph Kernel Neural Networks [53.91024360329517]
  We propose to use graph kernels, i.e. kernel functions that compute an inner product on graphs, to extend the standard convolution operator to the graph domain. This allows us to define an entirely structural model that does not require computing the embedding of the input graph. Our architecture allows to plug-in any type of graph kernels and has the added benefit of providing some interpretability.
  arXiv  Detail & Related papers  (2021-12-14T14:48:08Z)
• Spectral Graph Convolutional Networks With Lifting-based Adaptive Graph Wavelets [81.63035727821145]
  Spectral graph convolutional networks (SGCNs) have been attracting increasing attention in graph representation learning. We propose a novel class of spectral graph convolutional networks that implement graph convolutions with adaptive graph wavelets.
  arXiv  Detail & Related papers  (2021-08-03T17:57:53Z)
• A Generalization of Transformer Networks to Graphs [5.736353542430439]
  We introduce a graph transformer with four new properties compared to the standard model. The architecture is extended to edge feature representation, which can be critical to tasks s.a. chemistry (bond type) or link prediction (entity relationship in knowledge graphs)
  arXiv  Detail & Related papers  (2020-12-17T16:11:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.