Standard Transformer architectures, while dominant in natural language and vision, are inherently "graph-blind." Because the self-attention mechanism treats input elements as a permutation-invariant set, a vanilla Transformer sees a molecule or a social network as a "bag of nodes," ignoring the vital topological links that define the data.
To bridge this gap, a major research direction has emerged to "inject" structural inductive biases into the Transformer. The goal is to combine the global receptive field of attention with the local, relational constraints of graph topology.
The Problem of Topological Blindness
In a sequence, position is linear (token $i$ is next to $i+1$). In a graph, "position" is multi-dimensional and dictated by connectivity. As noted by Chengxuan Ying and Di He in their work on Graphormer, standard attention fails to capture the inherent structural relationships that define graph data. Without explicit constraints, a model might treat a node's immediate neighbor and a node ten hops away with equal priority, losing the "local-first" logic that governs most physical and social systems.
Injecting Structure via Encodings
The most common way to fix this is by adding "structural DNA" to the node features before they enter the attention layers. This is often split into two categories:
- Positional Encodings (Where am I?): These give nodes "coordinates" in the graph. Liheng Ma and colleagues introduced GRIT, which uses learned random-walk probabilities to capture how a node is situated within the global structure.
- Structural Encodings (What is my neighborhood like?): These describe the local geometry. For instance, Lei Bao proposed MoSE, which uses motif (subgraph) counts to provide a richer description of a node's local environment than simple degree counts.
By concatenating these encodings to node features, the Transformer can finally distinguish between nodes that look similar but occupy different roles in the topology.
Biasing the Attention Mechanism
Rather than just changing the input, many researchers modify the attention calculation itself. The intuition is to "tilt" the model's focus toward structurally relevant nodes.
In Graformer, Martin Schmitt uses the shortest path distance between nodes as a bias term in the attention matrix. This ensures that while every node can attend to every other node, the "energy" required to attend to distant nodes is higher. Similarly, the Structure-Aware Transformer (SAT) by Leslie O'Bray extracts local subgraphs for each node and uses them to re-weight the attention scores, effectively baking message-passing-like constraints directly into the Transformer.
Scaling to Massive Graphs
A significant challenge in this field is that dense $O(N^2)$ attention is computationally ruinous for large graphs. To solve this, researchers like Yuankai Luo have developed Hierarchical Distance Structural Encoding (HDSE). By grouping nodes into multi-level hierarchies and biasing attention based on these "community" distances, they enable Transformers to scale to billion-node graphs while maintaining a sense of global and local scale.
Theoretical Expressivity and the WL Test
Why go through all this trouble? The answer lies in "expressive power." Traditional Graph Neural Networks (GNNs) are limited by the Weisfeiler-Leman (WL) graph isomorphism test—they cannot distinguish certain complex graph structures.
Wenhao Zhu and the authors of SEG-WL proved that a Transformer's ability to "see" these differences depends almost entirely on its structural encodings. By using sophisticated encodings like SPIS, Transformers can actually surpass the 3-WL test, making them theoretically more powerful than the GNNs they were designed to replace.