mlsanityData to 7 Oct 2026

Recipe for a General, Powerful, Scalable Graph Transformer

arXiv 2205.12454 ↗First posted 25 May 2022cs.LGcited by 702

Not on the map. Why?

Abstract (arXiv)

We propose a recipe on how to build a general, powerful, scalable (GPS) graph Transformer with linear complexity and state-of-the-art results on a diverse set of benchmarks. Graph Transformers (GTs) have gained popularity in the field of graph representation learning with a variety of recent publications but they lack a common foundation about what constitutes a good positional or structural encoding, and what differentiates them. In this paper, we summarize the different types of encodings with a clearer definition and categorize them as being textitlocal, textitglobal or textitrelative. The prior GTs are constrained to small graphs with a few hundred nodes, here we propose the first architecture with a complexity linear in the number of nodes and edges O(N+E) by decoupling the local real-edge aggregation from the fully-connected Transformer. We argue that this decoupling does not negatively affect the expressivity, with our architecture being a universal function approximator on graphs. Our GPS recipe consists of choosing 3 main ingredients: (i) positional/structural encoding, (ii) local message-passing mechanism, and (iii) global attention mechanism. We provide a modular framework textitGraphGPS that supports multiple types of encodings and that provides efficiency and scalability both in small and large graphs. We test our architecture on 16 benchmarks and show highly competitive results in all of them, show-casing the empirical benefits gained by the modularity and the combination of different strategies.

Key facts. Cited by 702 papers in the map (data through 7 Oct 2026). Builds on 57 of its 76 references that are in the map. First posted on arXiv 25 May 2022.

Builds on

57 of 76 references.

References · 57

  1. 2017Attention Is All You Needcited by 59,932
  2. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,491
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  4. 2017Graph Attention Networkscited by 8,854
  5. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  6. 2018How Powerful are Graph Neural Networks?cited by 4,355
  7. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  8. 2020Longformer: The Long-Document Transformercited by 3,362
  9. 2021Efficiently Modeling Long Sequences with Structured State Spacescited by 2,424
  10. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  11. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  12. 2020Big Bird: Transformers for Longer Sequencescited by 1,673
38 more
  1. 2020Reformer: The Efficient Transformercited by 1,658
  2. 2020Rethinking Attention with Performerscited by 1,584
  3. 2020Linformer: Self-Attention with Linear Complexitycited by 1,462
  4. 2019Strategies for Pre-training Graph Neural Networkscited by 964
  5. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  6. 2020Long Range Arena: A Benchmark for Efficient Transformerscited by 696
  7. 2020Benchmarking Graph Neural Networkscited by 672
  8. 2020A Generalization of Transformer Networks to Graphscited by 653
  9. 2020A Survey on Visual Transformercited by 653
  10. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  11. 2021ConViT: Improving Vision Transformers with Soft Convolutional Inductive Biasescited by 484
  12. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  13. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  14. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  15. 2019Provably Powerful Graph Networkscited by 385
  16. 2017Residual Gated Graph ConvNetscited by 341
  17. 2021OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphscited by 328
  18. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  19. 2021Do Transformers Really Perform Bad for Graph Representation?cited by 318
  20. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  21. 2021CMT: Convolutional Neural Networks Meet Vision Transformerscited by 310
  22. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  23. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  24. 2022Representing Long-Range Context for Graph Neural Networks with Global Attentioncited by 193
  25. 2022Structure-Aware Transformer for Graph Representation Learningcited by 191
  26. 2020Design Space for Graph Neural Networkscited by 182
  27. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  28. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  29. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  30. 2019Relational Pooling for Graph Representationscited by 150
  31. 2020Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learningcited by 148
  32. 2021GraphiT: Encoding Graph Structure in Transformerscited by 146
  33. 2020Directional Graph Networkscited by 132
  34. 2021AMMUS : A Survey of Transformer-based Pretrained Models in Natural Language Processingcited by 131
  35. 2021Global Self-Attention as a Replacement for Graph Convolutioncited by 113
  36. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  37. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  38. 2020My Body is a Cage: the Role of Morphology in Graph-Based Incompatible Controlcited by 68

50 most cited of 57 All 57 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 20; 2023: 133; 2024: 193; 2025: 194; 2026: 162.

702 papers.

Sort:

By area:

  1. 2024LightRAG: Simple and Fast Retrieval-Augmented Generationcited by 310
  2. 2022Long Range Graph Benchmarkcited by 258
  3. 2023Large Language Models on Graphs: A Comprehensive Surveycited by 190
  4. 2023Exphormer: Sparse Transformers for Graphscited by 166
  5. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 163
  6. 2023Graph Inductive Biases in Transformers without Message Passingcited by 150
  7. 2022NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphscited by 137
  8. 2023Temporal Graph Benchmark for Machine Learning on Temporal Graphscited by 137
  9. 2024Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spacescited by 132
  10. 2023SGFormer: Simplifying and Empowering Transformers for Large-Graph Representationscited by 131
  11. 2023Specformer: Spectral Graph Neural Networks Meet Transformerscited by 102
  12. 2023Graph Foundation Models: Concepts, Opportunities and Challengescited by 101
38 more
  1. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
  2. 2024Graph Mamba: Towards Learning on Graphs with State Space Modelscited by 84
  3. 2023Where Did the Gap Go? Reassessing the Long-Range Graph Benchmarkcited by 83
  4. 2024Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classificationcited by 83
  5. 2023Attending to Graph Transformerscited by 81
  6. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 81
  7. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  8. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  9. 2022One Transformer Can Understand Both 2D & 3D Molecular Datacited by 77
  10. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  11. 2024Polynormer: Polynomial-Expressive Graph Transformer in Linear Timecited by 64
  12. 2025SAMGPT: Text-free Graph Foundation Model for Multi-domain Pre-training and Cross-domain Adaptationcited by 61
  13. 2023On the Connection Between MPNN and Graph Transformercited by 60
  14. 2023GraphCare: Enhancing Healthcare Predictions with Personalized Knowledge Graphscited by 57
  15. 2023Locality-Aware Graph-Rewiring in GNNscited by 55
  16. 2023Graph Metanetworks for Processing Diverse Neural Architecturescited by 55
  17. 2022Multimodal learning with graphscited by 54
  18. 2023How does over-squashing affect the power of GNNs?cited by 53
  19. 2025Position: Graph Learning Will Lose Relevance Due To Poor Benchmarkscited by 52
  20. 2025PyG 2.0: Scalable Learning on Real World Graphscited by 49
  21. 2023Ewald-based Long-Range Message Passing for Molecular Graphscited by 46
  22. 2023Virtual Node Tuning for Few-shot Node Classificationcited by 46
  23. 2023GNNDelete: A General Strategy for Unlearning in Graph Neural Networkscited by 43
  24. 2025El Agente: An Autonomous Agent for Quantum Chemistrycited by 43
  25. 2025On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learningcited by 42
  26. 2022Relational Attention: Generalizing Transformers for Graph-Structured Taskscited by 41
  27. 2023Transformers Meet Directed Graphscited by 39
  28. 2024Hypformer: Exploring Efficient Transformer Fully in Hyperbolic Spacecited by 39
  29. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  30. 2023Dink-Net: Neural Clustering on Large Graphscited by 38
  31. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 38
  32. 2023Efficient Approximations of Complete Interatomic Potentials for Crystal Property Predictioncited by 37
  33. 2023Towards Foundational Models for Molecular Learning on Large-Scale Multi-Task Datasetscited by 37
  34. 2024On the Scalability of GNNs for Molecular Graphscited by 36
  35. 2023HINormer: Representation Learning On Heterogeneous Information Networks with Graph Transformercited by 35
  36. 2024TGB 2.0: A Benchmark for Learning on Temporal Knowledge Graphs and Heterogeneous Graphscited by 35
  37. 2022Explaining the Explainers in Graph Neural Networks: a Comparative Studycited by 34
  38. 2024VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connectionscited by 34

50 most cited of 702 All 702 (JSON)