Why GNNs Need Positional Encodings
Published:
Intuition First
Imagine reading a sentence where all words are presented as an unordered bag — you lose the crucial information about what comes first, second, last. Transformers solve this with sinusoidal positional encodings that inject a unique “address” for each position.
Graphs face the same problem, but harder: there is no canonical position 1, 2, 3 — the graph has no start or end. Two nodes can have the same local neighborhood structure yet be in fundamentally different global positions. Without positional encodings, a GNN is forced to treat them identically.
Permutation Equivariance: A Double-Edged Sword
GNNs are designed to be permutation equivariant: the result of processing a graph should not depend on the arbitrary labelling of nodes. If you permute the node indices, the output node embeddings permute accordingly.
This is a desirable property — the graph has no canonical ordering, so the model should not depend on one.
But it has a sharp consequence. A message-passing GNN’s node representations are always a refinement of the 1-WL colouring: if 1-WL assigns two nodes the same colour after \(k\) rounds, no \(k\)-layer MPNN can give them different embeddings. Whatever 1-WL cannot see, message passing cannot see either.
Two distinct things get conflated here, and it is worth separating them:
- Automorphic nodes. If some automorphism of the graph maps \(v\) to \(w\), then every permutation-equivariant function — GNN, Laplacian eigenvector, random-walk profile, anything computed from the graph alone — must assign them the same value. This is not a limitation of message passing; it is a theorem about equivariance, and no positional encoding escapes it.
- 1-WL-equivalent but non-automorphic nodes. These are merely invisible to message passing. A positional encoding computed by other means can separate them, and this is the gap that graph PEs actually fill.
The Symmetric Node Problem
Consider a path graph: A — B — C — D — E
1-WL colours B and D identically at every round — from either node’s perspective the graph looks the same — so no MPNN of any depth separates them. And in this example they are genuinely automorphic (reverse the path), so this is the hard case: nothing equivariant will give them different values, and LapPE separates them only up to the eigenvector’s sign.
But B and D may still need different predictions. If A carries a feature that makes “the second node from A” meaningful, the model needs some way to break the tie — which in practice means either a task-specific anchor (distance from A, which is not permutation-invariant by design) or accepting sign information from the eigenvectors.
More extreme: in a regular graph with uniform initial node features, 1-WL never refines past a single colour, so all nodes get the same embedding for any depth. (With distinct input features, message passing can of course still tell nodes apart — the collapse is about what structure alone provides.)
Why Sequences Don’t Have This Problem
In a Transformer processing a sentence, position 3 is always “position 3” regardless of the token’s content. Positional encodings inject this absolute location.
In graphs, there is no canonical position 3. The graph has no start, no end, no linear order. This is why graph PEs must be derived from the graph structure itself.
What Positional Encodings Can Provide
A good graph PE \(p_v\) should:
- Separate as much as possible — ideally distinct values for nodes that are not automorphic (full uniqueness is unattainable, since automorphic nodes must tie)
- Vary continuously with structure — structurally similar nodes get similar encodings, so small perturbations of the graph do not scramble the representation
- Be computationally affordable — no dense \(O(N^3)\) eigendecomposition
- Be well defined — free of arbitrary choices (sign, basis, anchor selection) that differ between two runs on the same graph
- Be transferable — a PE computed on training graphs should carry the same meaning on test graphs
Points 1 and 2 pull against each other, and point 4 is exactly where Laplacian eigenvectors get into trouble.
Types of Graph Positional Information
| Type | What it encodes | Example |
|---|---|---|
| Positional | Where the node is in the global graph | Laplacian eigenvectors |
| Structural | What role the node plays locally | Degree, clustering coefficient, cycle membership |
| Distance-based | Distances to other nodes | Random walk landing probabilities |
Positional and structural encodings are complementary — some tasks need absolute position, others need local role information.
Impact on Graph Transformers
For Graph Transformers (which lack the inductive structural bias of message passing), positional encodings are essential. Without them, the Transformer has no information about which nodes are connected — it processes a set of feature vectors with no graph structure at all.
With Laplacian eigenvector PEs: the model can compute attention scores that reflect graph distance. With random walk PEs: the model can identify structurally similar nodes. Graph PEs are to Graph Transformers what sinusoidal encodings are to sequence Transformers.
Summary
| Without PEs | With PEs |
|---|---|
| 1-WL-equivalent nodes are indistinguishable | Nodes get a structural fingerprint that message passing cannot derive |
| Regular graph + uniform features: all nodes identical | Eigenvector and random-walk PEs separate many such nodes |
| Graph Transformer ignores structure entirely | Structure enters via node PEs and pairwise attention biases |
| Bounded by 1-WL | Can exceed 1-WL — though automorphic nodes still tie, for any equivariant encoding |
The next posts cover specific PE methods: Laplacian eigenvectors, random walk PEs, shortest-path encodings, and the challenges they introduce.
References
- Dwivedi, V. P., Lim, A. T., Beaini, D., & Lió, P. (2021). Graph Neural Networks with Learnable Structural and Positional Representations. ICLR 2022.
- Srinivasan, B., & Ribeiro, B. (2020). On the Equivalence between Positional Node Embeddings and Structural Graph Representations. ICLR 2020.