Search papers, labs, and topics across Lattice.
This paper introduces a novel approach to spectral positional encodings (PEs) for directed graphs that leverages learnable functions and Hermitian block Krylov subspaces to overcome the computational challenges associated with magnetic Laplacians. The proposed method ensures gauge invariance by constructing PEs as matrix functions of normalized magnetic operators, allowing for efficient computation through sparse matrix-vector products. Key results demonstrate that the new PEs significantly outperform direction-blind alternatives, converging to the exact eigendecomposition oracle in specific scenarios, while also improving performance on heterophilous benchmarks in undirected cases.
Learnable spectral positional encodings can achieve gauge invariance and outperform traditional methods, converging to optimal solutions in directed graph settings.
Spectral positional encodings (PEs) for \emph{directed} graphs face two obstacles: magnetic Laplacians require an $O(n^3)$ Hermitian eigendecomposition per potential, and their complex eigenvectors are defined only up to unitary gauge, which prior work handles with basis-invariant architectures. We propose learnable spectral PEs of the form $h_\theta(A_q)\,R$, where $A_q$ is a normalized magnetic operator, $h_\theta$ a learnable scalar spectral response, and $R$ a block of random probes. Because the PE is a \emph{matrix function} of the operator, it is gauge-invariant by construction. We compute it in a Hermitian block Krylov subspace from sparse matrix--vector products only, prove that $k = O(\log(1/\varepsilon))$ block steps suffice uniformly over heat--resolvent response families, and give a covering-number argument for why low-dimensional structured families generalize where free per-eigenvalue weights overfit. On a directed SBM whose symmetrization is uninformative by construction, direction-blind PEs stay at chance while magnetic Krylov PEs converge to the exact-eigendecomposition oracle as the depth grows. The same probes yield gauge-invariant pairwise features with $1/\sqrt{s}$ Monte-Carlo error, and the undirected $q{=}0$ case improves heterophilous benchmarks over no-PE and polynomial baselines.
