mlsanityData to 7 Oct 2026

GEN: A Practical Alternative to Graph Transformers for Long-Range Graph Modeling

arXiv 2401.01233 ↗First posted 2 Jan 2024cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Message Passing Neural Networks (MPNNs) model local relations effectively but struggle to propagate information over long distances. Graph Transformers (GTs) mitigate this via global self-attention, yet their quadratic cost in the number of nodes limits scalability. We propose Graph Elimination Networks (GENs), an MPNN variant that approximates GT-like long-range modeling while maintaining high efficiency. GENs combine edge-wise and hop-wise self-attention in parallel; their multiplicative composition yields an attention kernel separable across edge and hop factors within a bounded K-hop receptive field. To enable hop-wise attention, we introduce the Graph Elimination Algorithm (GEA), which prevents double counting across hops, ensuring that each round injects the k-hop incremental contribution exactly once. Taking differences between successive rounds recovers the k-hop increment and yields disentangled multi-hop features as inputs for hop-wise attention. This preserves clearer structural distinctions across hop distances and enables more faithful modeling of pairwise dependencies between distant nodes within the K-hop neighborhood. On the Long-Range Graph Benchmark (LRGB), GENs outperform strong MPNN baselines by 7.7 and 6.0 percentage points (pp) on PascalVOC-SP and COCO-SP, and achieve performance on par with or better than state-of-the-art Graph Transformers. On OGBN-Products, GENs support full-batch training/inference, while sparse-attention baselines like Exphormer struggle with memory limits under comparable budgets, highlighting GENs as a practical alternative for large, sparse graphs.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 65 of its 83 references that are in the map. First posted on arXiv 2 Jan 2024.

Builds on

65 of 83 references.

References · 65

  1. 2017Attention Is All You Needcited by 59,932
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,616
  5. 2018How Powerful are Graph Neural Networks?cited by 4,355
  6. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  7. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  8. 2019Optuna: A Next-generation Hyperparameter Optimization Frameworkcited by 2,455
  9. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  10. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  11. 2020Big Bird: Transformers for Longer Sequencescited by 1,673
  12. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
38 more
  1. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  2. 2018Pitfalls of Graph Neural Network Evaluationcited by 994
  3. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  4. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  5. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  6. 2020Learning to Simulate Complex Physics with Graph Networkscited by 867
  7. 2020Simple and Deep Graph Convolutional Networkscited by 857
  8. 2019Graph Neural Networks for Social Recommendationcited by 711
  9. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  10. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 679
  11. 2020A Generalization of Transformer Networks to Graphscited by 653
  12. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  13. 2020HiPPO: Recurrent Memory with Optimal Polynomial Projectionscited by 600
  14. 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 544
  15. 2019DeepGCNs: Can GCNs Go as Deep as CNNs?cited by 527
  16. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 442
  17. 2021GemNet: Universal Directional Graph Neural Networks for Moleculescited by 342
  18. 2017Residual Gated Graph ConvNetscited by 341
  19. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  20. 2020GPT-GNN: Generative Pre-Training of Graph Neural Networkscited by 302
  21. 2020Towards Deeper Graph Neural Networkscited by 296
  22. 2022Long Range Graph Benchmarkcited by 258
  23. 2020Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networkscited by 253
  24. 2020DeeperGCN: All You Need to Train Deeper GCNscited by 249
  25. 2023A Survey on Oversmoothing in Graph Neural Networkscited by 246
  26. 2023NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classificationcited by 207
  27. 2022Structure-Aware Transformer for Graph Representation Learningcited by 191
  28. 2023Exphormer: Sparse Transformers for Graphscited by 166
  29. 2020Rumor Detection on Social Media with Bi-Directional Graph Convolutional Networkscited by 152
  30. 2019On the Universality of Invariant Networkscited by 151
  31. 2023Graph Inductive Biases in Transformers without Message Passingcited by 150
  32. 2021GraphiT: Encoding Graph Structure in Transformerscited by 146
  33. 2022NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphscited by 137
  34. 2023SGFormer: Simplifying and Empowering Transformers for Large-Graph Representationscited by 131
  35. 2021Global Self-Attention as a Replacement for Graph Convolutioncited by 113
  36. 2021Position Information in Transformers: An Overviewcited by 103
  37. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 94
  38. 2020Scalable Graph Neural Networks via Bidirectional Propagationcited by 87

50 most cited of 65 All 65 (JSON)

Built on by

Not cited yet.