What Are Good Positional Encodings for Directed Graphs?
This work addresses a gap in graph neural networks for directed graphs, which is important for applications like program analysis and circuit performance prediction, but is incremental as it builds on existing Magnetic Laplacian methods.
The paper tackled the problem of positional encodings for directed graphs, which are underexplored compared to undirected graphs, by proposing a Multi-q Magnetic Laplacian PE that provably expresses walk profiles and demonstrated effectiveness in sorting network satisfiability and circuit benchmarks.
Positional encodings (PEs) are essential for building powerful and expressive graph neural networks and graph transformers, as they effectively capture the relative spatial relationships between nodes. Although extensive research has been devoted to PEs in undirected graphs, PEs for directed graphs remain relatively unexplored. This work seeks to address this gap. We first introduce the notion of Walk Profile, a generalization of walk-counting sequences for directed graphs. A walk profile encompasses numerous structural features crucial for directed graph-relevant applications, such as program analysis and circuit performance prediction. We identify the limitations of existing PE methods in representing walk profiles and propose a novel Multi-q Magnetic Laplacian PE, which extends the Magnetic Laplacian eigenvector-based PE by incorporating multiple potential factors. The new PE can provably express walk profiles. Furthermore, we generalize prior basis-invariant neural networks to enable the stable use of the new PE in the complex domain. Our numerical experiments validate the expressiveness of the proposed PEs and demonstrate their effectiveness in solving sorting network satisfiability and performing well on general circuit benchmarks. Our code is available at https://github.com/Graph-COM/Multi-q-Maglap.