Rotary Position Encodings for Graphs

WIRE (graph rotary positional encoding) adapts RoPE to graph transformers by using Laplacian eigenvectors as node coordinates and rotating queries and keys according to their relative spectral positions. Unlike common graph-attention biases based on shortest-path distance or effective resistance, this encoding keeps attention logits factorized, so linear-attention methods can avoid constructing an all-pairs matrix. The authors show that it recovers familiar rotary encodings on paths and grids, and that suitably scaled spectral coordinates connect squared coordinate distance to effective resistance. With random frequencies, expected attention logits decay with resistance. The full spectral representation also relates to the Laplacian pseudoinverse, though truncating eigenvectors limits that expressivity.

Benchmark results show modest gains rather than universal improvements: WIRE beats a Performer baseline on 11 of 12 tasks and outperforms a quadratic transformer on four. Tests of the resistance interpretation, however, find that one attention head ranks node pairs by resistance poorly, while averaging many random-frequency samples matches the predicted decay. Moreover, released benchmark code appears to use learned combinations of eigenvectors without the inverse-square-root eigenvalue scaling required for that theoretical link. The practical case is therefore strongest as a relative encoding compatible with linear attention, not as an effective-resistance estimator. Its cost is not eliminated entirely: computing Laplacian eigenvectors can be expensive, though only a subset may be needed. When all-pairs attention is feasible and resistance is the desired signal, inserting resistance directly into logits is more precise.