mlsanityData to 7 Oct 2026

Towards Principled Graph Transformers

arXiv 2401.10119 ↗First posted 18 Jan 2024cs.LG cs.AIcited by 11

Not on the map. Why?

Abstract (arXiv)

Graph learning architectures based on the k-dimensional Weisfeiler-Leman (k-WL) hierarchy offer a theoretically well-understood expressive power. However, such architectures often fail to deliver solid predictive performance on real-world tasks, limiting their practical impact. In contrast, global attention-based models such as graph transformers demonstrate strong performance in practice, but comparing their expressive power with the k-WL hierarchy remains challenging, particularly since these architectures rely on positional or structural encodings for their expressivity and predictive performance. To address this, we show that the recently proposed Edge Transformer, a global attention model operating on node pairs instead of nodes, has at least 3-WL expressive power. Empirically, we demonstrate that the Edge Transformer surpasses other theoretically aligned architectures regarding predictive performance while not relying on positional or structural encodings. Our code is available at https://github.com/luis-mueller/towards-principled-gts

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 41 of its 58 references that are in the map. First posted on arXiv 18 Jan 2024.

Builds on

41 of 58 references.

References · 41

  1. 2017Attention Is All You Needcited by 59,932
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2016Layer Normalizationcited by 5,579
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
  6. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  7. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  8. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  9. 2020Benchmarking Graph Neural Networkscited by 672
  10. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  11. 2019Provably Powerful Graph Networkscited by 385
  12. 2018Invariant and Equivariant Graph Networkscited by 339
29 more
  1. 2021OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphscited by 328
  2. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  3. 2019Measuring Compositional Generalization: A Comprehensive Method on Realistic Datacited by 280
  4. 2015Order Matters: Sequence to sequence for setscited by 236
  5. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  6. 2022Pure Transformers are Powerful Graph Learnerscited by 188
  7. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  8. 2019On the Universality of Invariant Networkscited by 151
  9. 2023Graph Inductive Biases in Transformers without Message Passingcited by 150
  10. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  11. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  12. 2021Global Self-Attention as a Replacement for Graph Convolutioncited by 113
  13. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  14. 2022The CLRS Algorithmic Reasoning Benchmarkcited by 103
  15. 2023Specformer: Spectral Graph Neural Networks Meet Transformerscited by 102
  16. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
  17. 2021The Logic of Graph Neural Networkscited by 84
  18. 2023Attending to Graph Transformerscited by 81
  19. 2019Cross-lingual Knowledge Graph Alignment via Graph Matching Neural Networkcited by 68
  20. 2022A Generalist Neural Algorithmic Learnercited by 58
  21. 2021Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passingcited by 46
  22. 2022Relational Attention: Generalizing Transformers for Graph-Structured Taskscited by 41
  23. 2021Systematic Generalization with Edge Transformerscited by 38
  24. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  25. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  26. 2021Transformers Generalize DeepSets and Can be Extended to Graphs and Hypergraphscited by 35
  27. 2023Improving Compositional Generalization Using Iterated Learning and Simplicial Embeddingscited by 15
  28. 2023Diffusing Graph Attentioncited by 5
  29. 2023Triplet Edge Attention for Algorithmic Reasoningcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 5; 2026: 5.

11 papers.

  1. 2025Position: Graph Learning Will Lose Relevance Due To Poor Benchmarkscited by 52
  2. 2024Probabilistic Graph Rewiring via Virtual Nodescited by 15
  3. 2025How simple can you go? An off-the-shelf transformer approach to molecular dynamicscited by 10
  4. 2025Generalizable Insights for Graph Transformers in Theory and Practicecited by 2
  5. 2025Random Search Neural Networks for Efficient and Expressive Graph Learningcited by 1
  6. 2026FloydNet: A Learning Paradigm for Global Relational Reasoningcited by 1
  7. 2026On the Expressive Power of GNNs to Solve Linear SDPscited by 1
  8. 2025Efficiently Learning Branching Networks for Multitask Algorithmic Reasoningcited by 0
  9. 2026SatQNet: Satellite-assisted Quantum Network Entanglement Routing Using Directed Line Graph Neural Networkscited by 0
  10. 2026Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planningcited by 0
  11. 2026Project Auto-World: Towards Automated Benchmarking of Neural Relational Reasonerscited by 0