mlsanityData to 7 Oct 2026

A Scalable and Effective Alternative to Graph Transformers

arXiv 2406.12059 ↗First posted 17 Jun 2024cs.LG cs.SIcited by 4

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks (GNNs) have shown impressive performance in graph representation learning, but they face challenges in capturing long-range dependencies due to their limited expressive power. To address this, Graph Transformers (GTs) were introduced, utilizing self-attention mechanism to effectively model pairwise node relationships. Despite their advantages, GTs suffer from quadratic complexity w.r.t. the number of nodes in the graph, hindering their applicability to large graphs. In this work, we present Graph-Enhanced Contextual Operator (GECO), a scalable and effective alternative to GTs that leverages neighborhood propagation and global convolutions to effectively capture local and global dependencies in quasilinear time. Our study on synthetic datasets reveals that GECO reaches 169x speedup on a graph with 2M nodes w.r.t. optimized attention. Further evaluations on diverse range of benchmarks showcase that GECO scales to large graphs where traditional GTs often face memory and time limitations. Notably, GECO consistently achieves comparable or superior quality compared to baselines, improving the SOTA up to 4.5%, and offering a scalable and effective solution for large-scale graph learning.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 75 of its 89 references that are in the map. First posted on arXiv 17 Jun 2024.

Builds on

75 of 89 references.

References · 75

  1. 2017Attention Is All You Needcited by 59,932
  2. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  3. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  4. 2014Microsoft COCO: Common Objects in Contextcited by 17,498
  5. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  6. 2017Graph Attention Networkscited by 8,854
  7. 2016Densely Connected Convolutional Networkscited by 6,691
  8. 2017Inductive Representation Learning on Large Graphscited by 6,284
  9. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,616
  10. 2018How Powerful are Graph Neural Networks?cited by 4,355
  11. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
  12. 2019Optuna: A Next-generation Hyperparameter Optimization Frameworkcited by 2,455
38 more
  1. 2021Efficiently Modeling Long Sequences with Structured State Spacescited by 2,424
  2. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  3. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  4. 2020Big Bird: Transformers for Longer Sequencescited by 1,673
  5. 2019Simplifying Graph Convolutional Networkscited by 1,470
  6. 2021MLP-Mixer: An all-MLP Architecture for Visioncited by 1,441
  7. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  8. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  9. 2018Link Prediction Based on Graph Neural Networkscited by 829
  10. 2023RWKV: Reinventing RNNs for the Transformer Eracited by 814
  11. 2022Simplified State Space Layers for Sequence Modelingcited by 776
  12. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  13. 2020Long Range Arena: A Benchmark for Efficient Transformerscited by 696
  14. 2020Benchmarking Graph Neural Networkscited by 672
  15. 2020A Generalization of Transformer Networks to Graphscited by 653
  16. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  17. 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
  18. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  19. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 540
  20. 2022Hungry Hungry Hippos: Towards Language Modeling with State Space Modelscited by 495
  21. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  22. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  23. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  24. 2023Hyena Hierarchy: Towards Larger Convolutional Language Modelscited by 388
  25. 2017Residual Gated Graph ConvNetscited by 341
  26. 2021OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphscited by 328
  27. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  28. 2021Mesh Graphormercited by 264
  29. 2022Long Range Graph Benchmarkcited by 258
  30. 2020Can Graph Neural Networks Count Substructures?cited by 235
  31. 2022Representing Long-Range Context for Graph Neural Networks with Global Attentioncited by 193
  32. 2022Structure-Aware Transformer for Graph Representation Learningcited by 191
  33. 2020Random Features Strengthen Graph Neural Networkscited by 184
  34. 2019Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networkscited by 177
  35. 2023Exphormer: Sparse Transformers for Graphscited by 166
  36. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  37. 2019Relational Pooling for Graph Representationscited by 150
  38. 2023Graph Inductive Biases in Transformers without Message Passingcited by 150

50 most cited of 75 All 75 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellencecited by 24
  2. 2025Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNscited by 3
  3. 2026Benchmarking Sheaf Neural Networks for Inductive Taskscited by 1
  4. 2025Exploring the Global-to-Local Attention Scheme in Graph Transformers: An Empirical Studycited by 0