  A current goal in the graph neural network literature is to enable
transformers to operate on graph-structured data, given their success on
language and vision tasks. Since the transformer's original sinusoidal
positional encodings (PEs) are not applicable to graphs, recent work has
focused on developing graph PEs, rooted in spectral graph theory or various
spatial features of a graph. In this work, we introduce a new graph PE, Graph
Automaton PE (GAPE), based on weighted graph-walking automata (a novel
extension of graph-walking automata). We compare the performance of GAPE with
other PE schemes on both machine translation and graph-structured tasks, and we
show that it generalizes several other PEs. An additional contribution of this
study is a theoretical and controlled experimental comparison of many recent
PEs in graph transformers, independent of the use of edge features.

Machine Learning