mlsanityData to 7 Oct 2026

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

arXiv 2607.07032 ↗First posted 8 Jul 2026cs.LG stat.MLcited by 0

Not on the map. Why?

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.

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

Builds on

18 of 20 references.

References · 18

  1. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  2. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  3. 2020A Generalization of Transformer Networks to Graphscited by 653
  4. 2021BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximationcited by 195
  5. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  6. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  7. 2023Specformer: Spectral Graph Neural Networks Meet Transformerscited by 102
  8. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  9. 2019LanczosNet: Multi-Scale Deep Graph Convolutional Networkscited by 73
  10. 2023Transformers Meet Directed Graphscited by 39
  11. 2023On the Stability of Expressive Positional Encodings for Graphscited by 31
  12. 2023Graph Positional Encoding via Random Feature Propagationcited by 30
6 more
  1. 2025Learning Efficient Positional Encodings with Graph Neural Networkscited by 21
  2. 2017Stability of the Lanczos Method for Matrix Function Approximationcited by 15
  3. 2024What Are Good Positional Encodings for Directed Graphs?cited by 7
  4. 2025Learning Laplacian Positional Encodings for Heterophilous Graphscited by 4
  5. 2026GIST: Gauge-Invariant Spectral Transformers for Scalable Graph Neural Operatorscited by 3
  6. 2025Powers of Magnetic Graph Matrix: Fourier Spectrum, Walk Compression, and Applicationscited by 1

Built on by

Not cited yet.