  The dominant paradigm for machine learning on graphs uses Message Passing
Graph Neural Networks (MP-GNNs), in which node representations are updated by
aggregating information in their local neighborhood. Recently, there have been
increasingly more attempts to adapt the Transformer architecture to graphs in
an effort to solve some known limitations of MP-GNN. A challenging aspect of
designing Graph Transformers is integrating the arbitrary graph structure into
the architecture. We propose Graph Diffuser (GD) to address this challenge. GD
learns to extract structural and positional relationships between distant nodes
in the graph, which it then uses to direct the Transformer's attention and node
representation. We demonstrate that existing GNNs and Graph Transformers
struggle to capture long-range interactions and how Graph Diffuser does so
while admitting intuitive visualizations. Experiments on eight benchmarks show
Graph Diffuser to be a highly competitive model, outperforming the
state-of-the-art in a diverse set of domains.
