UBC, Google & Amii's Exphormer: Scaling Graph Transformers While Slashing Costs

The ability of graph transformers (GT) to model long-range interactions has improved expressivity and made such architectures a promising alternative to traditional graph neural network (GNN) approaches. The GT downside is their poor scalability, which renders them prohibitively expensive when dealing with large and complex graphs. In the new paper Exphormer: Sparse Transformers for Graphs, a research team from the University of British Columbia, Google Research and the Alberta Machine Intelligence Institute proposes Exphormer, a framework that equips sparse GTs with impressive scalability, reduces computational complexity to linear, and achieves state-of-the-art performance on graph benchmarks. The proposed Exphormer is based on and inherits the desirable properties of the recently introduced GraphGPS (Rampasek et al., 2022) modular framework for building general, powerful and scalable GTs with linear complexity. GraphGPS combines traditional local message passing and a global attention mechanism while also allowing for "sparse" attention mechanisms to boost performance and reduce computation costs.