Abstract
Graph transformers have emerged as a promising architecture for a variety ofgraph learning and representation tasks. Despite their successes, though, itremains challenging to scale graph transformers to large graphs whilemaintaining accuracy competitive with message-passing networks. In this paper,we introduce Exphormer, a framework for building powerful and scalable graphtransformers. Exphormer consists of a sparse attention mechanism based on twomechanisms: virtual global nodes and expander graphs, whose mathematicalcharacteristics, such as spectral expansion, pseduorandomness, and sparsity,yield graph transformers with complexity only linear in the size of the graph,while allowing us to prove desirable theoretical properties of the resultingtransformer models. We show that incorporating Exphormer into therecently-proposed GraphGPS framework produces models with competitive empiricalresults on a wide variety of graph datasets, including state-of-the-art resultson three datasets. We also show that Exphormer can scale to datasets on largergraphs than shown in previous graph transformer architectures. Code can befound at \url{https://github.com/hamed1375/Exphormer}.