II · THE IDEA · ARTIFICIAL INTELLIGENCE
Graph Transformers with Structural Encodings
▶ Listen · narrated
On molecular graphs, a transformer that knows how far apart two atoms sit can beat architectures built only for graphs. The difference is positional information drawn from the graph itself.
At a glance
- Problem
- Message passing can crush long-range signals into fixed-size vectors
- Response
- Inject graph distances and related structure into transformer attention
- Key cue
- Shortest-path distances between node pairs
- Domain
- Molecular graphs and related structured prediction
- Claim
- With those encodings, transformers can outperform dedicated GNNs
Think of a rumour moving through a village. In a message-passing network, people only talk to their immediate neighbours. If two people live far apart, the rumour must pass through a chain of go-betweens. If those go-betweens also carry dozens of other rumours, the original message gets crushed and muddled before it arrives. That crush is the bottleneck.
A transformer is more like a town meeting where anyone can speak directly to anyone. That sounds perfect for long-distance rumours—until you realise nobody has been told who lives next door and who lives across the valley. Without a map, the loud conversation has no sense of the village layout.
Structural encodings hand the meeting a simple map: how many steps separate each pair of people along the real paths. Shortest-path distance is the plainest version of that map. Once speakers know who is near and who is far on the actual graph, direct conversation becomes useful rather than noisy. On molecules, atoms are the villagers and bonds are the paths. With those distances in the model, transformers have been shown to beat networks that only ever whisper along bonds.
Message-passing GNNs update node states by aggregating neighbour messages. After k layers a node’s receptive field is its k-hop neighbourhood, but the information from that neighbourhood is repeatedly written into fixed-dimensional vectors along the unique paths the graph supplies. When a large set of distant nodes must influence a target through a small cut, the Jacobian of the target with respect to those sources vanishes in practice—the over-squashing phenomenon analysed as a bottleneck with direct practical implications for tasks that need long-range dependence.
A transformer layer computes attention between all pairs, offering O(1) path length for any interaction at cost O(n²) in nodes. On graphs this is insufficient by itself: standard positional embeddings assume a sequence. Graph-oriented designs therefore inject structural encodings. Shortest-path distance (SPD) between node pairs is encoded as a bias on attention logits or as a feature of the pair, so that attention weight α_ij depends on both content and graph distance. Complementary signals—centrality of nodes, attributes of edges along connecting paths—play the same role of restoring topology.
With SPD-style encodings, the model retains global receptive field while remaining sensitive to bond topology. On molecular representation tasks this combination has been shown to outperform dedicated GNN baselines, answering the question whether transformers need perform badly for graph representation with a conditional no: they perform well once graph-theoretic position replaces sequence position. Limitations remain explicit. Dense attention is costly for large n; encodings must be precomputed or approximated; and when the task is purely local the inductive bias of sparse message passing can still be the better prior.
Look closer
The bottleneck is geometric, not merely deep
In a message-passing GNN, information travels along edges. When many distant nodes must influence a target through a few bridging nodes or a thin cut, their signals are forced into the same small vector. That compression is structural: stacking more layers does not widen the cut. Tasks that need long-range interaction feel the loss even when local chemistry looks well modelled.
Distance becomes a first-class input
A graph transformer does not have to route every signal hop by hop. It can attend between any pair of nodes in one step, but only if the model knows which pairs are close, which are far, and which are connected at all. Encoding shortest-path distance—and related graph-theoretic position—into the attention bias or the node features supplies that map without inventing a Euclidean grid the molecule does not have.
Attention still needs a graph vocabulary
A plain sequence transformer treats tokens as a line. On a graph the “line” is false: bond topology, ring closures and branching matter. Structural encodings are the substitute for order indices. They tell the model that two atoms three bonds apart share a different relationship from two atoms that merely sit near each other in an arbitrary serialisation of the molecule.
The story
Graph neural networks learn by passing messages along edges. Each layer mixes a node with its immediate neighbours. That design matches local chemistry well, and for many years it was the default for molecules and other irregular structures. It has a cost that is easy to overlook until a task depends on it.
When a property hinges on interaction between regions that are many hops apart, the relevant signals must travel a long path. Along the way they share intermediate node states with every other signal that uses the same bridges. If a large neighbourhood funnels through a narrow cut, the fixed-width vectors at those cut nodes become a bottleneck. Distinct long-range messages overwrite one another. The failure is sometimes called over-squashing: not a lack of depth, but a lack of capacity on the routes the graph actually provides.
Transformers look, at first glance, like a way around that geometry. Self-attention lets every node speak to every other node in a single layer, so no path need be traversed hop by hop. Early attempts to drop graphs into vanilla transformers were disappointing. The model saw a set of tokens and, at best, a weak sense of order from whatever serialisation produced the input. It did not see the molecule.
The missing piece was positional information that belongs to the graph rather than to a sequence. Shortest-path distance between two nodes is one such signal. It is graph-theoretic, cheap to precompute on the small graphs typical of molecules, and directly related to how message-passing would have had to travel. When that distance—often together with other structural cues such as centrality or edge attributes along the path—is encoded into the attention mechanism, pairs that are close on the graph can be treated differently from pairs that are remote, even though both pairs are fully visible in the same layer.
With those encodings in place, the architectural comparison changes. The transformer is no longer a structure-blind set model. It can use global attention for long-range mixing while still respecting topology. On molecular tasks where dedicated GNNs had been the specialist tools, this combination has been shown to outperform them. The gain is not magic attention; it is attention conditioned on the same kind of relational facts a GNN would have discovered only slowly, and sometimes not at all past a bottleneck.
Two ideas therefore sit side by side. One paper isolates the bottleneck in message passing and spells out why practical graphs suffer from it. The other asks whether transformers are truly weak on graphs and answers by giving them structural encodings—shortest-path distances among them—until the weakness largely disappears on the workloads that matter. Read together, they sketch a division of labour: GNNs remain natural when locality dominates and graphs are huge; transformers with explicit structure become competitive, and often preferable, when long-range dependence is the point and the graph is small enough to afford dense attention plus distance features.
Why it mattered then
Message-passing GNNs had become the standard tool for learning on molecules and other graphs. Their local inductive bias looked like a feature. Evidence that they systematically under-deliver on long-range dependence complicated that story: the limitation was not only shallow architectures or weak features, but a structural compression inherent in how information moves. At the same time, transformers were dominating sequence domains, yet transferring them to graphs without a substitute for position produced weak results and a reputation that they “perform bad” at graph representation. Structural encodings answered both pressures at once. They gave transformers a graph-native sense of where nodes sit relative to one another, and they offered a route to long-range mixing that did not squeeze signals through narrow cuts. On molecular benchmarks that reward exactly that mixing, the approach overturned the expectation that specialist GNNs would remain ahead by default.
Why it matters now
Many modern graph workloads still sit on the same fault line. Local chemistry, local citations, local links are well handled by message passing; global properties, scaffold-level effects and cross-branch interactions are not. Dense graph transformers are not free—attention scales poorly on very large graphs—but for the molecule-sized regime they are practical, and structural encodings remain the difference between a set model and a graph model. The same lesson travels to other domains where practitioners bolt transformers onto irregular structure: if the only position signal is an arbitrary order, performance will look like the early weak results; if shortest paths, distances or equivalent relational maps are injected, attention can exploit topology instead of ignoring it. The bottleneck analysis also still guides GNN design itself, encouraging rewiring, residual long-range edges and other ways to widen cuts when a full transformer is not the right tool.
The surprising detail
The decisive ingredient is almost mundane: how many hops separate two nodes. No new physics, no learned simulator—just classical shortest-path distances fed into attention as a bias or feature. That small graph-theoretic table is enough to flip the narrative from “transformers are bad at graphs” to outperformance over purpose-built GNNs on molecular tasks. The implication is slightly unsettling for pure end-to-end learning: a precomputed relational map, older than deep learning, carries information the network would otherwise struggle to assemble through a bottleneck.
What is disputed
The claim that transformers with structural encodings outperform dedicated GNNs is tied to the molecular and graph-representation settings examined in the source work. It does not automatically extend to every graph size, sparsity pattern or task. On very large graphs, dense attention may be impractical, and strong local GNN designs can still win when long-range dependence is weak. Evidence should be read as conditional on regime, not as a universal ranking of architectures.
Remember this
Transformers beat GNNs on graphs when they are told the graph’s own distances; global attention without structural encodings is not enough.
Test yourself
A molecule has two functional groups separated by a long chain. A message-passing GNN and a graph transformer with shortest-path encodings both see the full graph. Why might the transformer more reliably let one group influence the other’s representation in a single forward pass, and what exactly would go wrong if you removed the distance encoding but kept full attention?
Full attention already gives every atom a direct channel to every other atom, so the transformer need not push the signal hop by hop along the chain or through narrow intermediate states—the route that exposes a GNN to over-squashing. The shortest-path encoding is what tells attention that those two groups are far in graph distance and how that distance relates to other pairs; without it, the model still mixes all pairs but lacks a graph-native notion of position, so the long-range mix is unstructured and often little better than treating the atoms as an unordered set. The win comes from global mixing plus topology, not from global mixing alone.
Go deeper
- [2006.05205] On the Bottleneck of Graph Neural Networks and its Practical Implications · arxiv.org
- [2106.05234] Do Transformers Really Perform Bad for Graph Representation? · arxiv.org
Image: Original diagram, The Daily Triptych. Licence: Original work. Source.