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

• URL: http://arxiv.org/abs/2607.07032v2
• Date: Sat, 11 Jul 2026 09:10:52 GMT
• Title: Eigenbasis-Independent Learnable Spectral Positional Encodings for Directed Graphs via Hermitian Block Krylov Subspaces
• Abstract summary: Spectral positional encodings for emph graphs face two obstacles.<n>Magnetic Laplacians require an $O(n3)$ Hermitian eigendecomposition per potential.<n>We propose learnable spectral PEs of the form $h_(A_q),R$, where $A_q$ is a normalized magnetic operator.<n>Because the PE is a emphmatrix function of the operator, it is gauge-invariant by construction.
• Score: 4.46261341603246
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Dynamical spectral functions from bitstring-sampled quantum subspaces: entanglement, not one-body magic, tracks the sampling cost [0.0]
  We use a bitstring-sampling primitive to reconstruct quantum subspaces.<n>The reconstruction matches exact diagonalization on Hubbard chains and, for $A()$, across nineteen molecules.<n>We prove moment exactness and a sampling bound in $|mathcalS|$, independent of Hilbert-space dimension.
  arXiv  Detail & Related papers  (2026-08-17T11:35:16Z)
• A Provable Oracle-Free Quantum Algorithm for Nonlinear Dynamics on Hybrid Oscillator-Qubit Processors [14.814423713691623]
  We develop a hybrid qubit-qumode algorithm for nonlinear ordinary differential equations of the form $dotmathbfx=mathbff(mathbfx)$ with warped degree$L$.<n>The algorithm propagates the state density and returns the trajectory as the peak of that density in the small-noise limit.
  arXiv  Detail & Related papers  (2026-07-30T17:10:47Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• Efficient Mean Curvature Computation on High-Dimensional Data Manifolds [52.452902154360565]
  Estimating local mean curvature at each point of a high-dimensional dataset is a key ingredient of machine learning algorithms.<n>This paper introduces two complementary contributions that together reduce this cost by several orders of magnitude.<n> Experiments on real-world datasets confirm speedups of 50 to 300 times relative to the original implementation.
  arXiv  Detail & Related papers  (2026-06-04T16:04:31Z)
• Candidate collapse-noise correlators from Generalized Trace Dynamics: a Hubble-scale spectral line under structural assumptions [0.0]
  We present a conditional construction of candidate CSL-type collapse-noise correlators inspired by Generalized Trace Dynamics (GTD)<n>The construction is not a parameter-free derivation from the minimal GTD Grassmann algebra.<n>The resulting narrow-band spectrum at the Hubble scale lies outside the bounds of current CSL bands.
  arXiv  Detail & Related papers  (2026-05-28T05:21:27Z)
• From Noncommutative Kinematics to \(U(1)_{\star}\) Gauge Theory: A Family of Spectral Triples with Localized Gauge-induced Perturbations [0.0]
  We construct a noncommutative planar system associated with a fixed nondegenerate irreducible unitary sector of the kinematical symmetry group $G_mathrmNC$.<n>For each $varrho$, this yields locally compact non-unital base spectral triples over the involutive Moyal algebra.<n>We prove strong resolvent convergence to a self-adjoint limiting operator, the closure of the formal minimally coupled operator.
  arXiv  Detail & Related papers  (2026-05-11T09:20:11Z)
• Spectral-angular parametrization of open qudit dynamics [0.0]
  A generic density matrix $rho_mathbfr,pmb$, characterized by $n2-1$ real parameters, naturally decomposes into two sets.<n>A key observation is that the spectral parameters $mathbfr = (r_1, ldots, r_n-1)$ admit a natural Lie-algebraic interpretation.
  arXiv  Detail & Related papers  (2026-04-13T16:02:24Z)
• Bounds on Lorentz-violating parameters in magnetically confined 2D systems: A phenomenological approach [0.0]
  We present a framework to constrain minimal SME coefficients $a_mu$ and $b_mu$ using magnetically confined two-dimensional electron systems.<n>Working in the nonrelativistic (Schr"odinger--Pauli) limit with effective mass, we derive the radial problem for cylindrical geometries.
  arXiv  Detail & Related papers  (2025-10-28T11:11:59Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• $O(N^2)$ Universal Antisymmetry in Fermionic Neural Networks [107.86545461433616]
  We propose permutation-equivariant architectures, on which a determinant Slater is applied to induce antisymmetry. FermiNet is proved to have universal approximation capability with a single determinant, namely, it suffices to represent any antisymmetric function. We substitute the Slater with a pairwise antisymmetry construction, which is easy to implement and can reduce the computational cost to $O(N2)$.
  arXiv  Detail & Related papers  (2022-05-26T07:44:54Z)
• Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
  We study efficient estimation and detection of a planted vector $v$ whose $ell_4$ norm differs from that of a Gaussian vector with the same $ell$ norm. We show that in the regime $n rho gg sqrtN$, any spectral method from a large class (and more generally, any low-degree of the input) fails to detect the planted vector.
  arXiv  Detail & Related papers  (2021-05-31T16:10:49Z)
• BRST-BV Quantum Actions for Constrained Totally-Symmetric Integer HS Fields [77.34726150561087]
  A non-minimal constrained BRST-BV Lagrangian formulation is presented for totally symmetric massless HS fields in a $d$-dimensional Minkowski space. A Fock-space quantum action is constructed as a shift of the total generalized field-antifield vector by a variational derivative of the gauge-fixing Fermion $Psi$ in a total BRST-BV action.
  arXiv  Detail & Related papers  (2020-10-29T16:40:32Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  Solving optimal transport with an entropic regularization requires computing a $ntimes n$ kernel matrix that is repeatedly applied to a vector. We propose to use instead ground costs of the form $c(x,y)=-logdotpvarphi(x)varphi(y)$ where $varphi$ is a map from the ground space onto the positive orthant $RRr_+$, with $rll n$.
  arXiv  Detail & Related papers  (2020-06-12T10:21:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.