Rotary Position Encodings for Graphs
Authors: Isaac Reid, Arijit Sehanobish, Cederik Höfs, Bruno Kacper Mlodozeniec, Leonhard Vulpius, Federico Barbero, Adrian Weller, Krzysztof Marcin Choromanski, Richard E. Turner, Petar Veličković
Abstract
We study the extent to which rotary position encodings (RoPE), a recent transformer position encoding algorithm broadly adopted in large language models (LLMs) and vision transformers (ViTs), can be applied to graph-structured data. We find that rotating tokens depending on the spectrum of the graph Laplacian efficiently injects structural information into the attention mechanism, boosting performance in synthetic and real-world graph learning tasks. This approach, coined _Wave-Induced Rotary Encodings_ (WIRE), enjoys intriguing theoretical properties: it recovers regular RoPE on grids, and depends asymptotically on the graph effective resistance. Unlike bias-based relative position encodings, WIRE is compatible with linear attention.