Comparing Graph Transformers via Positional Encodings
Mitchell Black Zhengchao Wan Gal Mishne Amir Nayyeri Yusu Wang
The distinguishing power of graph transformers is closely tied to the choice
of positional encoding: features used to augment the base transformer with
information about the graph. There are two primary types of positional
encoding: absolute positional encodings (APEs) and relative positional
encodings (RPEs). APEs assign features to each node and are given as input to
the transformer. RPEs instead assign a feature to each pair of nodes, e.g.,
graph distance, and are used to augment the attention block. A priori, it is
unclear which method is better for maximizing the power of the resulting graph
transformer. In this paper, we aim to understand the relationship between these
different types of positional encodings. Interestingly, we show that graph
transformers using APEs and RPEs are equivalent in terms of distinguishing
power. In particular, we demonstrate how to interchange APEs and RPEs while
maintaining their distinguishing power in terms of graph transformers. Based on
our theoretical results, we provide a study on several APEs and RPEs (including
the resistance distance and the recently introduced stable and expressive
positional encoding (SPE)) and compare their distinguishing power in terms of
transformers. We believe our work will help navigate the huge number of choices
of positional encoding and will provide guidance on the future design of
positional encodings for graph transformers.