# Graph Inductive Biases in Transformers without Message Passing

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

## Key facts

- Cited by 153 papers in the map (data through 14 Oct 2026).
- Builds on 52 of its 63 references that are in the map.
- First posted on arXiv 27 May 2023.

## Builds on (most cited first, 30 of 52)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [FiLM: Visual Reasoning with a General Conditioning Layer](https://mlsanity.com/paper/1709.07871/) (2017)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [How Do Vision Transformers Work?](https://mlsanity.com/paper/2202.06709/) (2022)

## Built on by (most cited first, 30 of 153)

- [GraphLLM: Boosting Graph Reasoning Ability of Large Language Model](https://mlsanity.com/paper/2310.05845/) (2023)
- [Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark](https://mlsanity.com/paper/2309.00367/) (2023)
- [Polynormer: Polynomial-Expressive Graph Transformer in Linear Time](https://mlsanity.com/paper/2403.01232/) (2024)
- [Graph Metanetworks for Processing Diverse Neural Architectures](https://mlsanity.com/paper/2312.04501/) (2023)
- [Cooperative Graph Neural Networks](https://mlsanity.com/paper/2310.01267/) (2023)
- [VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections](https://mlsanity.com/paper/2403.16030/) (2024)
- [Cometh: A continuous-time discrete-state graph diffusion model](https://mlsanity.com/paper/2406.06449/) (2024)
- [Graph Transformers: A Survey](https://mlsanity.com/paper/2407.09777/) (2024)
- [Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence](https://mlsanity.com/paper/2502.09263/) (2025)
- [Unifying Generation and Prediction on Graphs with Latent Graph Diffusion](https://mlsanity.com/paper/2402.02518/) (2024)
- [Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generation](https://mlsanity.com/paper/2402.03687/) (2024)
- [Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching](https://mlsanity.com/paper/2312.16560/) (2023)
- [Learning Efficient Positional Encodings with Graph Neural Networks](https://mlsanity.com/paper/2502.01122/) (2025)
- [Comparing Graph Transformers via Positional Encodings](https://mlsanity.com/paper/2402.14202/) (2024)
- [Learning Graph Quantized Tokenizers](https://mlsanity.com/paper/2410.13798/) (2024)
- [Learning Long Range Dependencies on Graphs via Random Walks](https://mlsanity.com/paper/2406.03386/) (2024)
- [Spatio-Spectral Graph Neural Networks](https://mlsanity.com/paper/2405.19121/) (2024)
- [Enhancing Graph Transformers with Hierarchical Distance Structural Encoding](https://mlsanity.com/paper/2308.11129/) (2023)
- [Improving Equivariant Networks with Probabilistic Symmetry Breaking](https://mlsanity.com/paper/2503.21985/) (2025)
- [Jointly-Learned Exit and Inference for a Dynamic Neural Network : JEI-DNN](https://mlsanity.com/paper/2310.09163/) (2023)
- [Probabilistic Graph Rewiring via Virtual Nodes](https://mlsanity.com/paper/2405.17311/) (2024)
- [On the Expressive Power of Spectral Invariant Graph Neural Networks](https://mlsanity.com/paper/2406.04336/) (2024)
- [Facilitating Graph Neural Networks with Random Walk on Simplicial Complexes](https://mlsanity.com/paper/2310.19285/) (2023)
- [Understanding Virtual Nodes: Oversquashing and Node Heterogeneity](https://mlsanity.com/paper/2405.13526/) (2024)
- [A Survey of Graph Transformers: Architectures, Theories and Applications](https://mlsanity.com/paper/2502.16533/) (2025)
- [What Can We Learn from State Space Models for Machine Learning on Graphs?](https://mlsanity.com/paper/2406.05815/) (2024)
- [Benchmarking Positional Encodings for GNNs and Graph Transformers](https://mlsanity.com/paper/2411.12732/) (2024)
- [Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Tasks](https://mlsanity.com/paper/2506.07624/) (2025)
- [Recurrent Distance Filtering for Graph Representation Learning](https://mlsanity.com/paper/2312.01538/) (2023)
- [Towards Principled Graph Transformers](https://mlsanity.com/paper/2401.10119/) (2024)

## Abstract (arXiv)

Transformers for graph data are increasingly widely studied and successful in numerous learning tasks. Graph inductive biases are crucial for Graph Transformers, and previous works incorporate them using message-passing modules and/or positional encodings. However, Graph Transformers that use message-passing inherit known issues of message-passing, and differ significantly from Transformers used in other domains, thus making transfer of research advances more difficult. On the other hand, Graph Transformers without message-passing often perform poorly on smaller datasets, where inductive biases are more crucial. To bridge this gap, we propose the Graph Inductive bias Transformer (GRIT) -- a new Graph Transformer that incorporates graph inductive biases without using message passing. GRIT is based on several architectural changes that are each theoretically and empirically justified, including: learned relative positional encodings initialized with random walk probabilities, a flexible attention mechanism that updates node and node-pair representations, and injection of degree information in each layer. We prove that GRIT is expressive -- it can express shortest path distances and various graph propagation matrices. GRIT achieves state-of-the-art empirical performance across a variety of graph datasets, thus showing the power that Graph Transformers without message-passing can deliver.