# A Survey on Structure-Preserving Graph Transformers

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 40 references that are in the map.
- First posted on arXiv 29 Jan 2024.

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

- [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)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Representing Long-Range Context for Graph Neural Networks with Global Attention](https://mlsanity.com/paper/2201.08821/) (2022)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Exphormer: Sparse Transformers for Graphs](https://mlsanity.com/paper/2303.06147/) (2023)
- [Graph Inductive Biases in Transformers without Message Passing](https://mlsanity.com/paper/2305.17589/) (2023)
- [GraphiT: Encoding Graph Structure in Transformers](https://mlsanity.com/paper/2106.05667/) (2021)
- [NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs](https://mlsanity.com/paper/2206.04910/) (2022)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [Global Self-Attention as a Replacement for Graph Convolution](https://mlsanity.com/paper/2108.03348/) (2021)
- [Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature](https://mlsanity.com/paper/2211.15779/) (2022)
- [Hierarchical Graph Transformer with Adaptive Node Sampling](https://mlsanity.com/paper/2210.03930/) (2022)
- [GRPE: Relative Positional Encoding for Graph Transformer](https://mlsanity.com/paper/2201.12787/) (2022)
- [Gophormer: Ego-Graph Transformer for Node Classification](https://mlsanity.com/paper/2110.13094/) (2021)
- [Universal Graph Transformer Self-Attention Networks](https://mlsanity.com/paper/1909.11855/) (2019)
- [A Survey on Efficient Training of Transformers](https://mlsanity.com/paper/2302.01107/) (2023)
- [Are More Layers Beneficial to Graph Transformers?](https://mlsanity.com/paper/2303.00579/) (2023)
- [Transitivity-Preserving Graph Representation Learning for Bridging Local Connectivity and Role-based Similarity](https://mlsanity.com/paper/2308.09517/) (2023)
- [Deformable Graph Transformer](https://mlsanity.com/paper/2206.14337/) (2022)
- [Mitigating Degree Biases in Message Passing Mechanism by Utilizing Community Structures](https://mlsanity.com/paper/2312.16788/) (2023)
- [AGFormer: Efficient Graph Representation with Anchor-Graph Transformer](https://mlsanity.com/paper/2305.07521/) (2023)
- [Companion Animal Disease Diagnostics based on Literal-aware Medical Knowledge Graph Representation Learning](https://mlsanity.com/paper/2309.03219/) (2023)
- [Connector 0.5: A unified framework for graph representation learning](https://mlsanity.com/paper/2304.13195/) (2023)

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

- [Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification](https://mlsanity.com/paper/2406.08993/) (2024)
- [Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence](https://mlsanity.com/paper/2502.09263/) (2025)
- [Learning Graph Quantized Tokenizers](https://mlsanity.com/paper/2410.13798/) (2024)
- [Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning](https://mlsanity.com/paper/2405.16435/) (2024)
- [Invariant Graph Transformer for Out-of-Distribution Generalization](https://mlsanity.com/paper/2508.00304/) (2025)
- [Exploring Graph-Transformer Out-of-Distribution Generalization Abilities](https://mlsanity.com/paper/2506.20575/) (2025)
- [Learning to Model Graph Structural Information on MLPs via Graph Structure Self-Contrasting](https://mlsanity.com/paper/2409.05573/) (2024)

## Abstract (arXiv)

The transformer architecture has shown remarkable success in various domains, such as natural language processing and computer vision. When it comes to graph learning, transformers are required not only to capture the interactions between pairs of nodes but also to preserve graph structures connoting the underlying relations and proximity between them, showing the expressive power to capture different graph structures. Accordingly, various structure-preserving graph transformers have been proposed and widely used for various tasks, such as graph-level tasks in bioinformatics and chemoinformatics. However, strategies related to graph structure preservation have not been well organized and systematized in the literature. In this paper, we provide a comprehensive overview of structure-preserving graph transformers and generalize these methods from the perspective of their design objective. First, we divide strategies into four main groups: node feature modulation, context node sampling, graph rewriting, and transformer architecture improvements. We then further divide the strategies according to the coverage and goals of graph structure preservation. Furthermore, we also discuss challenges and future directions for graph transformer models to preserve the graph structure and understand the nature of graphs.