arXiv:2607.13577 2026 Architecture 1 ideas extracted · analyzed Aug 30, 2026
The transferable contribution is the characterization of main eigenvalues through the Krylov space generated by the adjacency matrix and the all-ones vector. If a graph has only k main eigenvalues, all global walk-count features j, Aj, A^2j, ... lie in a k-dimensional invariant subspace, allowing long-range structural information to be compressed exactly. This suggests a rank-adaptive positional encoder for graph neural networks that replaces many walk-count channels with an orthonormal basis of the main Krylov space. The strongest initial test is graph classification on trees and small graph benchmarks, comparing this basis against random-walk and Laplacian positional encodings.
Add a structural positional channel formed from the Krylov sequence generated by the graph adjacency matrix and the all-ones vector. For graphs with k main eigenvalues, this sequence has rank k, so a GNN can retain all information obtainable from global walk counts using only k node features rather than storing many adjacency powers.