# Eigenbasis-Independent Learnable Spectral Positional Encodings for Directed Graphs via Hermitian Block Krylov Subspaces

arXiv: https://arxiv.org/abs/2607.07032 · HTML: https://mlsanity.com/paper/2607.07032/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 20 references that are in the map.
- First posted on arXiv 8 Jul 2026.

## Builds on (most cited first, 18 of 18)

- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation](https://mlsanity.com/paper/2106.10994/) (2021)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Specformer: Spectral Graph Neural Networks Meet Transformers](https://mlsanity.com/paper/2303.01028/) (2023)
- [Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks](https://mlsanity.com/paper/2203.00199/) (2022)
- [LanczosNet: Multi-Scale Deep Graph Convolutional Networks](https://mlsanity.com/paper/1901.01484/) (2019)
- [Transformers Meet Directed Graphs](https://mlsanity.com/paper/2302.00049/) (2023)
- [On the Stability of Expressive Positional Encodings for Graphs](https://mlsanity.com/paper/2310.02579/) (2023)
- [Graph Positional Encoding via Random Feature Propagation](https://mlsanity.com/paper/2303.02918/) (2023)
- [Learning Efficient Positional Encodings with Graph Neural Networks](https://mlsanity.com/paper/2502.01122/) (2025)
- [Stability of the Lanczos Method for Matrix Function Approximation](https://mlsanity.com/paper/1708.07788/) (2017)
- [What Are Good Positional Encodings for Directed Graphs?](https://mlsanity.com/paper/2407.20912/) (2024)
- [Learning Laplacian Positional Encodings for Heterophilous Graphs](https://mlsanity.com/paper/2504.20430/) (2025)
- [GIST: Gauge-Invariant Spectral Transformers for Scalable Graph Neural Operators](https://mlsanity.com/paper/2603.16849/) (2026)
- [Powers of Magnetic Graph Matrix: Fourier Spectrum, Walk Compression, and Applications](https://mlsanity.com/paper/2506.07343/) (2025)

## Abstract (arXiv)

Spectral positional encodings (PEs) for directed graphs face two obstacles: magnetic Laplacians require an O(n3) 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θ(Aq),R, where Aq is a normalized magnetic operator, hθ a learnable scalar spectral response, and R a block of random probes. Because the PE is a 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/√s Monte-Carlo error, and the undirected q=0 case improves heterophilous benchmarks over no-PE and polynomial baselines.