GRPE: Relative Positional Encoding for Graph Transformer
This work addresses a key bottleneck in graph representation learning for researchers and practitioners by providing a more effective positional encoding method, though it appears incremental as it builds on existing Transformer-based approaches.
The authors tackled the problem of positional encoding for graph Transformers by introducing Graph Relative Positional Encoding (GRPE), which avoids graph linearization and integrates node-topology and node-edge interactions, resulting in significant performance improvements on various graph datasets.
We propose a novel positional encoding for learning graph on Transformer architecture. Existing approaches either linearize a graph to encode absolute position in the sequence of nodes, or encode relative position with another node using bias terms. The former loses preciseness of relative position from linearization, while the latter loses a tight integration of node-edge and node-topology interaction. To overcome the weakness of the previous approaches, our method encodes a graph without linearization and considers both node-topology and node-edge interaction. We name our method Graph Relative Positional Encoding dedicated to graph representation learning. Experiments conducted on various graph datasets show that the proposed method outperforms previous approaches significantly. Our code is publicly available at https://github.com/lenscloth/GRPE.