Graph Transformer

If message passing is limited by the edges it is given, let every node attend to every other and put the structure back in as a bias on the scores. A graph transformer does that: full attention, with the graph entering through how far apart two nodes are rather than through whether they are connected at all.

Structure arrives as encodings rather than as masking — shortest-path distance added to the attention score, edge features along that path, degree folded into the input. This escapes the WL bound and the oversmoothing ceiling in one move, and pays for both in quadratic cost, which is why it wins on molecules with tens of atoms and struggles on graphs with millions of nodes.

Score(u,v) = (h sub _u  W sub _Q )(h sub _v  W sub _K ) super ^T /√d + b sub _φ(u,v)  where φ is the shortest-path distance and b is a learned scalar per distance. Because b is learned rather than fixed at −∞ for non-edges, a pair with no edge is discouraged rather than forbidden — the difference between a bias and a mask, and the whole reason the architecture is more expressive.