  We show that viewing graphs as sets of node features and incorporating
structural and positional information into a transformer architecture is able
to outperform representations learned with classical graph neural networks
(GNNs). Our model, GraphiT, encodes such information by (i) leveraging relative
positional encoding strategies in self-attention scores based on positive
definite kernels on graphs, and (ii) enumerating and encoding local
sub-structures such as paths of short length. We thoroughly evaluate these two
ideas on many classification and regression tasks, demonstrating the
effectiveness of each of them independently, as well as their combination. In
addition to performing well on standard benchmarks, our model also admits
natural visualization mechanisms for interpreting graph motifs explaining the
predictions, making it a potentially strong candidate for scientific
applications where interpretation is important. Code available at
https://github.com/inria-thoth/GraphiT.
