arXiv:2607.07032cs.LGstat.ML2026-07

提出新型谱位置编码,解决有向图中复特征向量的规范不变性难题。

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

  • 基于厄米块克雷洛夫子空间,用稀疏矩阵-向量乘法计算谱编码
  • 仅需O(log(1/ε))步即可逼近热核与摄动响应族,误差可控
  • 适用于有向图节点分类,比传统方法更稳定且可推广

针对有向图的谱位置编码面临两大挑战:磁拉普拉斯算子需对每种势能进行复杂度为O(n³)的厄米特征分解,且其复特征向量仅在单位规范下定义。本文提出可学习的谱位置编码形式 $h_θ(A_q)ackslash R$,其中 $A_q$ 为归一化磁算子,$h_θ$ 为可学习标量谱响应,$R$ 为随机探针块。由于该编码是算子的矩阵函数,天然具备规范不变性。通过厄米块克雷洛夫子空间仅用稀疏矩阵-向量乘法实现计算,证明对热-摄动响应族,仅需 $k = O(/log(1/))$ 步即能达到一致逼近效果,并给出覆盖数论证说明低维结构家族泛化能力强于自由参数的过拟合模型。在对称化后信息缺失的有向随机块模型上,忽略方向的编码表现仅达随机水平,而磁克雷洛夫编码随深度增加趋近于精确特征分解基线。相同探针亦可生成规范不变的成对特征,蒙特卡洛误差为 $1/\/sqrt{s}$;无方向情形(q=0)在异质性基准上超越无编码和多项式基线。

原文摘要 · Abstract (English)

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_θ(A_q)\,R$, where $A_q$ is a normalized magnetic operator, $h_θ$ 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.

图神经网络谱编码有向图克雷洛夫子空间

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。