  Graph transformers have emerged as a promising architecture for a variety of
graph learning and representation tasks. Despite their successes, though, it
remains challenging to scale graph transformers to large graphs while
maintaining accuracy competitive with message-passing networks. In this paper,
we introduce Exphormer, a framework for building powerful and scalable graph
transformers. Exphormer consists of a sparse attention mechanism based on two
mechanisms: virtual global nodes and expander graphs, whose mathematical
characteristics, 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 resulting
transformer models. We show that incorporating Exphormer into the
recently-proposed GraphGPS framework produces models with competitive empirical
results on a wide variety of graph datasets, including state-of-the-art results
on three datasets. We also show that Exphormer can scale to datasets on larger
graphs than shown in previous graph transformer architectures. Code can be
found at \url{https://github.com/hamed1375/Exphormer}.
