An Overview of Positional Encodings (PE)

Positional encodings (PE) for graphs are vectorized representations that can effectively describe the global position of nodes (absolute PE) or relative position of node pairs (relative PE). They provide crucial positional information and thus benefits many backbone models that is position-agnostic. For instance, on undirected graphs, PE can provably alleviate the limited expressive power of Message Passing Neural Networks [1], [2] ; PE are also widely adopted in many graph transformers to incorporate positional information and break the identicalness of nodes in attention mechanism [3], [4]. As a result, the design and use of PE become one of the most important factors in building powerful graph encoders.

Likely, one can expect that direction-aware PE are also crucial when it comes to directed graph encoders. ‘Direction-aware’ implies that PE should be able to capture the directedness of graphs. A notable example is Magnetic Laplacian PE [5], which adopts the eigenvectors of Magnetic Laplacian as PE. Note that Magnetic Laplacian can encode the directedness via the sign of phase of exp (±i2πq). Besides, when q=0, Magnetic Laplacian reduces to normal symmetric Laplacian. Thus, Magnetic Laplacian PE for directed graphs can be seen as a generalization of Laplacian PE for undirected graphs, and the latter is known to enjoy many nice spectral properties and be capable to capture many undirected graph distances. Therefore, Magnetic Laplacian appears to be a strong candidate for designing direction-aware PE. See [6] for a comprehensive introduction to Magnetic Laplacian.

Last, it is worth mentioning that there are also other PE for directed graphs, such as SVD of Adjacency matrix and directed random walk.