Overview
This work proposes learnable spectral positional encodings (PEs) designed for directed graphs. The method addresses two challenges associated with magnetic Laplacians in directed graphs: the $O(n^3)$ computational complexity for Hermitian eigendecomposition per potential and the unitary gauge ambiguity of complex eigenvectors. The proposed PEs are formulated as a matrix function $h_\theta(A_q)\,R$, where $A_q$ is a normalized magnetic operator, $h_\theta$ represents a learnable scalar spectral response, and $R$ is a block of random probes. This formulation inherently ensures gauge-invariance. The computational approach leverages Hermitian block Krylov subspaces, relying solely on sparse matrix-vector products.
Research Context
Spectral positional encodings for directed graphs encounter specific obstacles. Magnetic Laplacians, which are relevant for directed graphs, necessitate a Hermitian eigendecomposition that scales with $O(n^3)$ computational cost for each potential value. Furthermore, the complex eigenvectors derived from these Laplacians are defined only up to a unitary gauge, a factor that prior research has addressed through the use of basis-invariant architectural designs. The current work aims to provide an alternative solution to these challenges.
Approach
The proposed spectral PEs are defined by the form $h_\theta(A_q)\,R$. In this formulation, $A_q$ functions as a normalized magnetic operator. The term $h_\theta$ denotes a learnable scalar spectral response, while $R$ represents a block of random probes. A key aspect of this approach is that the PE is conceptualized as a matrix function of the operator $A_q$. This design choice ensures gauge-invariance by construction. The computation of this matrix function is performed within a Hermitian block Krylov subspace. This computation exclusively utilizes sparse matrix-vector products. The researchers prove that $k = O(\log(1/\varepsilon))$ block steps are sufficient, a uniformity that holds across families of heat-resolvent response functions. A covering-number argument is also provided to explain why low-dimensional, structured families demonstrate generalizability, contrasting with free per-eigenvalue weights that tend to overfit.
Findings
- The proposed PE formulation, $h_\theta(A_q)\,R$, maintains gauge-invariance due to its definition as a matrix function of the operator.
- The computation in a Hermitian block Krylov subspace relies exclusively on sparse matrix-vector products.
- It was proven that $k = O(\log(1/\varepsilon))$ block steps are sufficient universally for heat-resolvent response families.
- A covering-number argument indicates that low-dimensional, structured families generalize effectively, while free per-eigenvalue weights are prone to overfitting.
- On a directed Stochastic Block Model (SBM) where the symmetrization is uninformative by design, direction-blind PEs perform at chance levels. In contrast, magnetic Krylov PEs converge to the exact-eigendecomposition oracle as the depth increases.
- The same probes used in the PE formulation yield gauge-invariant pairwise features with a Monte-Carlo error of $1/\sqrt{s}$.
- For the undirected case where $q{=}0$, the method shows improvements on heterophilous benchmarks when compared to no-PE and polynomial baselines.