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

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

## Key facts

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

## Builds on (most cited first, 30 of 65)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [HiPPO: Recurrent Memory with Optimal Polynomial Projections](https://mlsanity.com/paper/2008.07669/) (2020)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [GemNet: Universal Directional Graph Neural Networks for Molecules](https://mlsanity.com/paper/2106.08903/) (2021)

## 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.