New Gauge-Invariant Positional Encodings for Directed Graphs.

Applying spectral positional encodings (PEs) to directed graphs presents significant challenges, primarily due to the computational cost of Hermitian eigendecomposition for magnetic Laplacians and the gauge ambiguity of complex eigenvectors. This research proposes a novel solution: learnable spectral PEs that are inherently gauge-invariant. The new PEs are formulated as matrix functions of a normalized magnetic operator, ensuring gauge invariance by design. They are efficiently computed within a Hermitian block Krylov subspace, relying only on sparse matrix-vector products, which significantly reduces the computational burden. The authors demonstrate that a small number of block steps are sufficient for various response families. On a directed stochastic block model where traditional direction-blind PEs fail, the magnetic Krylov PEs converge to an oracle performance, also improving heterophilous benchmarks in the undirected case.