Do Transformers Really Perform Bad for Graph Representation?

In NLP, words sit in a sequence — position 1, 2, 3 — and the Transformer uses positional encoding to know where each token is. In computer vision, pixels live on a 2D grid. But in a graph, there is no canonical ordering. Node 5 is not "after" node 4 — it might be three hops away, or directly connected, or in a completely different subgraph.

Standard GNNs solve this by restricting communication: in message passing, each node collects information only from its direct neighbors. After $L$ layers, a node has seen its $L$-hop neighborhood. This respects graph structure naturally but limits the receptive field — distant nodes need many layers to communicate, and deep GNNs suffer from over-smoothing where all node representations converge.

The Transformer's self-attention gives every node a global receptive field in a single layer. But without structural information, the attention treats all pairs equally — it doesn't know that nodes 3 and 7 are neighbors while nodes 3 and 42 are five hops apart. This is why naive application of Transformers to graphs performed poorly.

In any graph, some nodes are more important than others. In a social network, a celebrity with millions of followers is structurally different from an ordinary user. In a molecule, an atom bonded to many others plays a different chemical role than a terminal atom. But standard self-attention computes similarity purely from node features — it has no idea how connected a node is.

Graphormer solves this with centrality encoding: for each node, it looks up a learnable embedding vector based on the node's degree (number of connections) and adds it directly to the node features at the input layer. Think of it as pinning a "popularity badge" on each node before the conversation begins.

For directed graphs, two separate embeddings capture indegree and outdegree. For undirected graphs, a single degree embedding suffices. This is surprisingly simple — yet the ablation studies show it provides one of the largest performance improvements.

In sequences, the Transformer knows that token 3 is closer to token 4 than to token 100 via positional encoding. Graphs need an analogous concept, but "position" in a graph means something fundamentally different — it's about topological distance, not index.

Graphormer's spatial encoding uses the shortest path distance (SPD) between any two nodes as the structural measure. For each possible distance value, a learnable scalar bias is added directly to the attention score before softmax. If two nodes are 1 hop apart, they get bias $b_1$; if 3 hops apart, they get $b_3$; if disconnected, they get a special bias $b_{-1}$.

The beauty of this design is that it naturally introduces a soft inductive bias: if the model learns $b_1 > b_2 > b_3$, it will pay more attention to nearby nodes — mimicking the locality that makes GNNs effective. But it can also learn other patterns: perhaps $b_3 > b_2$ for some heads, capturing long-range dependencies that GNNs miss entirely.

Many real-world graphs have rich edge features. In molecular graphs, edges carry bond types (single, double, aromatic); in knowledge graphs, edges carry relation labels. Previous GNNs encoded edge features in two limited ways: either adding them to the connected nodes' features, or using them during the neighbor aggregation step. Both only propagate edge information to directly connected nodes.

Graphormer's edge encoding takes a different approach. For any pair of nodes $(v_i, v_j)$, it finds the shortest path between them — a sequence of edges $(e_1, e_2, \ldots, e_N)$. It then computes the average dot product between each edge's feature vector and a learnable weight embedding, and adds this as another bias to the attention score.

This means that even for non-neighboring nodes, the model considers the path connecting them and the features of every edge along that path. It's like reading every sign on the hallways between two conference rooms, not just the sign on the door.

For graph-level tasks — predicting a property of the entire graph, not individual nodes — the model needs a way to aggregate all node representations into a single graph embedding. Previous GNNs used READOUT functions (sum, mean, or learned pooling). Graphormer borrows an idea from BERT: it adds a special virtual node ([VNode]) connected to every node in the graph, analogous to BERT's [CLS] token.

The [VNode] participates in self-attention like any regular node, but its spatial encoding uses a distinct learnable scalar — separating "virtual" connections from physical graph edges. After all Transformer layers, the [VNode]'s final representation becomes the graph-level output.

Each Graphormer layer follows the standard Transformer encoder pattern with pre-layer normalization: layer norm before multi-head attention, a residual connection, layer norm before the feed-forward network, and another residual connection. The FFN uses the same hidden dimension as the model dimension $d$, keeping the architecture clean and standard.

A natural question is whether adding these encodings actually makes Graphormer more powerful than existing GNNs, or just different. The authors provide a mathematical proof: with appropriate weight choices, a single Graphormer layer can simulate the AGGREGATE-COMBINE step of GIN, GCN, and GraphSAGE.

The key insight is that spatial encoding lets the self-attention distinguish between neighbors ($\phi = 1$) and non-neighbors ($\phi > 1$). Combined with centrality encoding (which provides degree information), the model can compute sum, mean, or max over the neighbor set — exactly what GNN aggregation functions do.

But Graphormer goes further. Standard message-passing GNNs are provably bounded by the 1-Weisfeiler-Lehman test for graph isomorphism — they cannot distinguish certain non-isomorphic graphs. The authors show a concrete example where Graphormer, using shortest-path distances, can distinguish graphs that the 1-WL test cannot, because shortest-path distances capture global structural patterns that local message passing misses.

Graphormer was evaluated on four major benchmarks. On the OGB Large-Scale Challenge (PCQM4M-LSC), containing 3.8 million molecular graphs, Graphormer achieved 0.1234 MAE — an 11.5% relative improvement over the previous best GIN-VN (0.1395). On OGB-MolHIV it reached 80.51% AUC, on MolPCBA 31.39% AP, and on ZINC it set a new state-of-the-art of 0.122 MAE, surpassing SAN (0.139).

Crucially, the naive Graph Transformer (GT) of Dwivedi and Bresson — using Laplacian positional encoding — did not outperform GIN-VN, even when scaled to 83M parameters. This shows that the Transformer alone is insufficient; what matters is how structural information is injected. Graphormer's three encodings are the difference between failure and state-of-the-art.

The ablation study reveals the contribution of each component. Starting from a bare Transformer (0.2276 MAE), adding spatial encoding drops the error to 0.1427. Adding centrality encoding on top reduces it further to 0.1396. Finally, edge encoding via attention bias brings it down to 0.1304.

An important comparison: Laplacian positional encoding (0.1483) is substantially worse than spatial encoding (0.1427) even though both encode node relationships. This is because spatial encoding provides pairwise information (distance between any two nodes) as a bias in the attention matrix, while Laplacian PE provides per-node information added to the input. The pairwise approach directly modulates which node pairs communicate strongly, giving the model finer structural control.