Reproduce “Exphormer: Sparse Transformers for Graphs” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, Ali Kemal Sinop
Exphormer replaces dense all-to-all attention in graph transformers with sparse interactions that combine real graph edges, constant-degree expander edges, and optional virtual nodes. This gives attention cost proportional to nodes and edges while providing routes for long-range information. On ogbn-arxiv, it reports 72.44% test accuracy; dense GraphGPS and SAN ran out of memory in the reported setup, not proving broader superiority.
Key insights
- Sparse attention for graphs should be explicitly designed for graph topology, as sequence-centric methods are suboptimal.
- Expander graphs provide theoretically robust, small-diameter structures for efficient long-range information propagation in sparse networks.
- Combining local, expander, and global attention components enables robust and expressive graph learning while maintaining scalability.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.