Research map / Graph learning / GNN architectures
A Scalable and Effective Alternative to Graph Transformers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GECO, a quasilinear graph layer that combines parameter-free neighborhood propagation with a non-causal global convolution (Hyena-style) to replace dense attention in graph transformers, scaling to large graphs.
Problem
Graph Transformers capture long-range dependencies via dense self-attention but scale quadratically with the number of nodes, limiting use on large graphs.
Approach
A compact layer pairing a parameter-free local propagation block (concatenating node and neighbor-aggregated features) with a graph-aware global convolution block (non-causal circular filters over node-ID order, no exponential decay, no short convolution), with dynamic random permutations per epoch to reduce order sensitivity.
Key results
- GECO reports the best Peptides-func AP (0.6975) and PascalVOC-SP F1 (0.4210) on LRGB, outperforming GraphGPS and Exphormer.
- On large node datasets GECO reaches 55.55% on Flickr and 73.10% on Arxiv, beating Exphormer and HSGT, while dense GTs (Graphormer, SAN, GraphGPS) run out of memory.
- Scaling study reports a 169x speedup over FlashAttention on a synthetic graph with 2M nodes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace dense attention with GECO | GraphGPS-style graph model · PascalVOC-SP | F1 score: 0.3975 ± 0.0037 -> 0.4210 ± 0.0080 | Helped |
| replace dense attention with GECO | GraphGPS-style graph model · COCO-SP | F1 score: 0.3455 ± 0.0009 -> 0.3320 ± 0.0032 | Hurt |
| replace dense attention with GECO | GraphGPS-style graph model · Peptides-func | AP: 0.6535 ± 0.0041 -> 0.6975 ± 0.0025 | Helped |
| replace dense attention with GECO | GraphGPS-style graph model · Peptides-struct | MAE: 0.2481 ± 0.0007 -> 0.2464 ± 0.0009 | Helped |
| replace dense attention with GECO | GraphGPS-style graph model · PCQM-Contact | MRR: 0.3637 ± 0.0020 -> 0.3526 ± 0.0016 | Hurt |
| replace dense attention with GECO | GraphGPS-style graph model · ogbg-ppa | Accuracy: 0.8015 ± 0.0033 -> 0.7982 ± 0.0042 | Hurt |
| replace dense attention with GECO | large node prediction model · Flickr | Accuracy: 54.12 ± 0.51 -> 55.55 ± 0.25 | Helped |
| replace dense attention with GECO | large node prediction model · Arxiv | Accuracy: 72.58 ± 0.31 -> 73.10 ± 0.24 | Helped |
| replace dense attention with GECO | large node prediction model · Reddit | Accuracy: 96.50 ± 0.03 -> 96.65 ± 0.05 | Helped |
| replace dense attention with GECO | large node prediction model · Yelp | Micro-F1 Score: 63.47 ± 0.45 -> 63.18 ± 0.59 | Hurt |
| use static or dynamic random node permutation instead of natural ordering (ablation) | GECO · large node prediction datasets | Accuracy: Flickr: 55.55 ± 0.25, 55.73 ± 0.27, 55.80 ± 0.38; Arxiv: 73.10 ± 0.24, 73.08 ± 0.28, 73.12 ± 0.22; Reddit: 96.65 ± 0.05, | No clear effect |
| replace LCB with Conv-1 (ablation) | GECO · PascalVOC-SP | F1: 0.2752 -> 0.3220 | Hurt |
Surprising findings
- Static and dynamic random permutation strategies give negligible differences in accuracy versus natural ordering.
- Replacing the local LCB block with 1D convolutions of growing filter size steadily degrades quality on PascalVOC-SP (0.2752 to 0.1445 for Conv-1 to Conv-40).
Limitations
- Global convolution is permutation-sensitive; permutation invariance is only approximated by random sampling and lacks a formal guarantee in practice.
- Positional/structural encodings are omitted on large datasets because computing them may be infeasible.
- Yelp is won by HSGT, and the work leaves combination with orthogonal scaling methods to future work.
Experimental setup
Datasets: PascalVOC-SP COCO-SP Peptides-func Peptides-struct PCQM-Contact ogbg-molhiv ogbg-molpcba ogbg-ppa ogbg-code2 PCQM4Mv2 Flickr ogbn-arxiv
Benchmarks: LRGB OGB PCQM4Mv2 Flickr ogbn-arxiv Reddit Yelp
Metrics: F1 score AP MAE MRR accuracy micro-F1 AUROC speedup
Baselines: GraphGPS Exphormer Graphormer GOAT HSGT SAN NAGphormer Hyena FlashAttention
Builds on: Hyena GraphGPS CKConv Janossy pooling NAGphormer
Closest papers by meaning
- Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · similarity 0.89)
- Generative Graph Pattern Machine (NeurIPS 2025 · similarity 0.89)
- Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.88)
- What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding (ICML 2024 · similarity 0.88)
- Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification (NeurIPS 2024 · similarity 0.88)
- G-Adapter: Towards Structure-Aware Parameter-Efficient Transfer Learning for Graph Transformer Networks (AAAI 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.