Graph Positional and Structural Encodings

Strip the positional encoding out of a language transformer and it sees a bag of words. Strip it out of a graph transformer and every node with the same features becomes indistinguishable, because attention over all pairs discards the adjacency entirely. Sequences have an obvious fix: index the tokens. Graphs have no canonical ordering of nodes, so there is nothing to index, and the field's answer is to compute something that plays the role of a coordinate.

Two things are being asked for and they are routinely conflated. A positional encoding says where a node sits relative to others, so that two nodes far apart receive different codes. A structural encoding says what a node's local neighbourhood looks like, so that two nodes in similar structures receive similar codes. The distinction matters because a good positional code is deliberately not invariant to position, while a good structural code deliberately is (Dwivedi et al., 2022, Graph Neural Networks with Learnable Structural and Positional Representations, ICLR).

Laplacian eigenvectors, and why they misbehave

The standard positional encoding takes the \(k\) eigenvectors of the graph Laplacian with smallest non-zero eigenvalues and gives node \(i\) the vector of its \(i\)-th components. The analogy to sinusoidal encodings is exact: on a path graph, these eigenvectors are sines and cosines.

Two ambiguities arrive with them. First, an eigenvector is only defined up to sign, so \(k\) eigenvectors admit \(2^k\) equally valid encodings, and a network trained on one sign pattern sees a different input at test time. The usual mitigation is to flip signs randomly during training, which teaches invariance by augmentation rather than enforcing it. Second, when eigenvalues repeat, any orthonormal basis of the eigenspace is valid, so even fixing signs does not pin the encoding down. Architectures that are invariant by construction address both: SignNet applies a function \(\phi\) to each eigenvector and sums \(\phi(v) + \phi(-v)\), BasisNet handles whole eigenspaces, and both are universal under stated conditions and subsume spectral graph convolutions (Lim et al., 2023, Sign and Basis Invariant Networks for Spectral Graph Representation Learning, ICLR).

Eigendecomposition also costs \(O(n^3)\) dense, or a Lanczos iteration for the lowest few, and the eigenvectors of a graph are unstable under small perturbations near a spectral gap. Adding one edge can rotate the encoding.

Random walks and distances, which behave better

The structural alternative is to run a random walk. With \(P = D^{-1}A\), the random-walk structural encoding of node \(i\) is the diagonal sequence

the probability of returning to \(i\) after each of \(K\) steps. Return probabilities encode local density and cycle structure directly, there is no sign or basis ambiguity, and the whole thing is \(K\) sparse matrix products. The same paper that separates positional from structural representations pairs its architecture with this encoding and reports improvements from 1.79 to 64.14 percent over its baselines, the range reflecting how much different datasets depend on structure.

Graph transformers for molecules take a third route and inject structure into the attention logits rather than the inputs: Graphormer adds a learned bias per shortest-path distance, plus degree and edge encodings, and won the quantum-property track of the KDD Cup 2021 OGB large-scale challenge (Ying et al., 2021, Do Transformers Really Perform Badly for Graph Representation?, NeurIPS).

Where the encoding goes in the architecture

The current default is to use both local message passing and global attention in each layer and keep them separate, with the encoding fed to both. Decoupling real-edge aggregation from the fully connected attention makes complexity linear in nodes and edges, \(O(N+E)\), instead of quadratic in nodes, without sacrificing expressivity (Rampášek et al., 2022, Recipe for a General, Powerful, Scalable Graph Transformer, NeurIPS). In that recipe the encoding is a first-class component, on the same footing as the message passing and the attention, not a preprocessing detail.

When it breaks

Eigenvector encodings do not transfer across graph sizes. The \(k\)-th eigenvector of a 50-node graph and of a 5,000-node graph are not comparable quantities, so a model trained on small graphs and applied to large ones receives an input distribution it has never seen. Random-walk encodings degrade more gracefully, since a return probability means the same thing at any scale.

Shortest-path biases are quadratic in memory. A learned bias per node pair per head is an \(n^2\) table, which is why distance-biased attention is standard for molecules and absent for social graphs.

A structural encoding can substitute for the structure and hide a failure. If a precomputed degree and triangle count carries most of the label signal, the model will score well while the message passing contributes nothing. Ablate the encoding and the aggregation separately, or you will not know which part worked.

Precomputation is a pipeline dependency. Encodings must be recomputed when the graph changes, which for a dynamic graph means on every snapshot, and eigendecomposition on a changing million-node graph is not a per-request operation.