We propose a recipe on how to build a general, powerful, scalable (GPS) graph Transformer
with linear complexity and state-of-the-art results on a diverse set of benchmarks. Graph
Transformers (GTs) have gained popularity in the field of graph representation learning with
a variety of recent publications but they lack a common foundation about what constitutes a
good positional or structural encoding, and what differentiates them. In this paper, we
summarize the different types of encodings with a clearer definition and categorize them as …