Pith. sign in

REVIEW 3 major objections 6 minor 21 references

Learnable spectral positional encodings for directed graphs can be built as matrix functions of magnetic operators on random probes, so they never need eigenvectors and stay independent of eigenbasis choices.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-14 15:53 UTC pith:M32AOFV4

load-bearing objection Clean matrix-function PE for directed graphs: gauge-free by construction, uniform Krylov rates, and a controlled SBM that actually isolates direction. the 3 major comments →

arxiv 2607.07032 v2 pith:M32AOFV4 submitted 2026-07-08 cs.LG stat.ML

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

Jiaqing Xie , Yuxin Wang This is my paper
classification cs.LG stat.ML
keywords spectral positional encodingsdirected graphsmagnetic LaplacianHermitian block Krylovmatrix functionslearnable spectral filtersrandom probes
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Spectral positional encodings on directed graphs usually rely on magnetic Laplacians, which force expensive Hermitian eigendecompositions and leave complex eigenvectors defined only up to unitary gauge. This paper instead defines the encoding as a learnable matrix function of a normalized magnetic operator applied to a block of random probes. Because the encoding is a matrix function, eigenvectors never appear, so gauge and basis choices drop out by construction. The same object is computed inside a Hermitian block Krylov subspace from sparse matrix–vector products only, and the authors prove that a logarithmic number of block steps already approximates an entire heat–resolvent response family uniformly. On a directed stochastic block model whose undirected skeleton carries no class signal, direction-blind encodings stay at chance while the magnetic Krylov encodings climb to the exact-eigendecomposition oracle as Krylov depth grows. The same probes also supply gauge-invariant pairwise features with the expected Monte-Carlo rate, and the undirected special case improves heterophilous benchmarks over no-PE and pure polynomial baselines.

Core claim

The paper establishes that learnable spectral positional encodings for directed graphs can be realized as Z_q(θ)=h_θ(A_q)R—matrix functions of normalized magnetic operators applied to random probes—making them independent of any eigenbasis choice by construction, and that these encodings admit a Hermitian block-Krylov approximation whose error decays exponentially and uniformly over heat–resolvent response families with only O(log(1/ε)) sparse steps.

What carries the argument

The matrix-function PE Z_q(θ)=h_θ(A_q)R approximated inside the Hermitian block Krylov subspace K_k(A_q,R). This single object simultaneously removes eigenbasis gauge, supplies the uniform approximation theorem, and yields the Monte-Carlo pairwise estimator from the same probes.

Load-bearing premise

That a fixed grid of magnetic potentials together with low-dimensional structured scalar responses is expressive enough to capture the directed structure that matters in practice while staying low-capacity enough to generalize.

What would settle it

On a larger directed SBM or a real direction-critical task, raise Krylov depth k while holding probes and response capacity fixed: if accuracy fails to approach the exact-eigendecomposition oracle, or if a free per-eigenvalue oracle with many more labels still underfits the structured family, the uniform-approximation and capacity claims are false.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper proposes learnable spectral positional encodings for directed graphs of the form Z_q(θ)=h_θ(A_q)R, where A_q is a normalized magnetic operator, h_θ a scalar spectral response (Chebyshev, heat–resolvent, or MLP), and R a block of random Gaussian probes. Because the PE is a matrix function of A_q, it is independent of eigenbasis/gauge choices by spectral calculus (Proposition 1). The encoding is computed in a Hermitian block Krylov subspace from sparse matvecs only; Theorem 1 shows that k=O(log(1/ε)) block steps suffice uniformly over compact heat–resolvent families, while Lemma 1 gives exactness for degree-(k-1) polynomials. A covering-number argument (Proposition 4) contrasts low-dimensional structured responses with an unconstrained per-eigenvalue oracle. Empirically, on a cyclic directed SBM whose symmetrization is uninformative by construction, direction-blind PEs stay at chance while magnetic Krylov PEs converge to the dense-eigendecomposition oracle as k grows (Table 2, Figure 1). The same probes yield cross-response pairwise features with 1/√s Monte-Carlo error; the undirected q=0 case improves heterophilous synthetic and real benchmarks over no-PE and polynomial baselines, though LapPE remains strongest on feature-rich undirected graphs. Real directed node-classification benchmarks show no gain over random probes (Table 3), reported as a negative result.

Significance. If the results hold, the paper cleanly removes two long-standing obstacles for directed spectral PEs—dense Hermitian eigendecompositions per potential and unitary gauge ambiguity—by replacing eigenvectors with matrix functions of magnetic operators evaluated on random probes. The theory is standard spectral calculus and classical Krylov approximation made uniform over a compact analytic family; the proofs in Appendix A are short, match textbook rates, and are load-bearing for the method rather than decorative. The directed SBM is a falsifiable diagnostic that isolates directional signal, and the honest negative result on WebKB/Wikipedia is valuable. Strengths include: (i) eigenbasis independence by construction rather than by specialized invariant networks; (ii) a reusable block-Krylov cache with explicit approximation and capacity parameters (k, response family, s); (iii) matched baselines (Magnetic-RFP, Free oracle, exact oracles) that separate orthogonalization/response learning from raw power iteration; and (iv) a controlled 1/√s pairwise path that reuses the same probes. The contribution is a principled approximation framework for learnable magnetic spectral PEs, not a claim o

major comments (3)
  1. [Theorem 1 / Section 3 / Appendix C] Theorem 1’s uniform rate for the heat–resolvent family (Eq. 3) requires tj ≤ tmax and τj ≥ τmin > 0 with ℓ1-bounded mixture coefficients. Section 3 states these bounds, but Appendix C and the experimental protocol do not confirm that training enforces them (projection, soft constraints, or reparameterization). If the optimizer can drive τj → 0 or tj → ∞, the uniform O(ρ^k) guarantee no longer applies to the trained family. Please state explicitly how the compact parameter set is maintained during response training, or qualify Theorem 1 as applying only under that constraint.
  2. [Abstract / Section 5 / Table 3] Table 3 reports that all spectral PEs (magnetic or not) fail to beat random probes on WebKB and Wikipedia networks, and several underperform them on Chameleon. The abstract and introduction frame the work as addressing directed-graph PE obstacles in general; the negative result is acknowledged in Section 5 and Section 6 but is not reflected in the abstract’s empirical summary, which highlights only the SBM success and undirected gains. Either evaluate on at least one direction-critical task from Huang et al. (2025) beyond the SPD suite (e.g., circuits or sorting networks, as Section 6 itself flags as next steps), or more carefully scope the abstract/intro so that readers do not expect gains on standard directed node classification under the present setup.
  3. [Section 5.2 / Tables 7–9 / Tables 12–13] Tables 8–9 show that Mag-PE + SPE (keig=32) remains an order of magnitude better on SPD and substantially better on LPD/WP than the best Krylov pairwise configuration. Table 7 correctly contrasts asymptotic costs, but the only large-n scaling (Figure 1d, Tables 12–13) is for node-level SBM classification, not pairwise regression. The claim that the method “trades some accuracy for full-spectrum learnable magnetic filtering without extracting eigenvectors” is fair, yet without a large-graph pairwise diagnostic the sparse-matvec advantage for the pairwise use case remains largely asymptotic. A brief large-n pairwise scaling experiment (or a clear statement that pairwise claims are limited to the small-DAG regime of Huang et al.) would make the resource trade-off load-bearing rather than suggestive.
minor comments (6)
  1. [Table 1] Table 1 row for Mag-Krylov says “Basis independent: yes (matrix function)”; the caption correctly distinguishes this from magnetic gauge covariance. Consider adding a one-line footnote in the table itself so readers skimming the comparison do not conflate the two notions.
  2. [Proposition 2 / Section 5] Proposition 2 carefully separates fixed-probe conditional equivariance from distributional equivariance under fresh probes. The experimental sections should restate in one sentence that all node-classification runs use fixed probes (transductive), so no cross-graph transfer claim is made for raw probe coordinates.
  3. [Table 2 / Remark 1] In Table 2, Mag-Krylov-Cheb reaches only 83.2% while Heat/HR/MLP reach 97–99%. Since Chebyshev is the direct LLPE analogue (Remark 1), a short discussion of why the polynomial family underperforms the analytic families on this task would help readers transfer the lesson to undirected LLPE-style settings.
  4. [Figure 1] Figure 1 panels are dense; the caption is informative but the individual panel titles in the figure itself (if present in the camera-ready) should name the quantity on each axis so the figure is self-contained when extracted.
  5. [Introduction / Section 5.1 / Proposition 3] Typos / notation: “Erd˝os–Rényi” appears with mixed encoding in the introduction; “Questions: 1.2s vs. 14.5s” in Section 5.1 should be “Questions” (dataset name). Ensure A_q = L_q − I is stated once with the sign convention used for B_q = −A_q in Proposition 3.
  6. [Section 2 / References] Related work cites GIST as arXiv:2603.16849 (2026) and Huang et al. PNAS 2026; if these are concurrent or forthcoming, a brief note on independence of contribution would help priority-conscious readers.

Circularity Check

0 steps flagged

No significant circularity: matrix-function PE, uniform Krylov rates, and capacity bounds are self-contained applications of spectral calculus and classical approximation theory.

full rationale

The central claims do not reduce to their inputs by construction or self-citation. Proposition 1 follows immediately from the spectral definition of a matrix function h(A) = sum h(lambda_i) Pi (unique orthogonal projectors), so eigenbasis/gauge independence holds by definition of the PE Z = h(A)R rather than by fitting or architectural repair. Theorem 1 is an application of classical block-Lanczos error bounds (best uniform polynomial approximation on the spectral interval, Cauchy interlacing) made uniform over a compact heat-resolvent parameter set via Bernstein-ellipse rates (Trefethen); the O(log(1/eps)) statement is therefore not a fitted prediction of the target accuracy. Lemma 1 is the standard exactness of Krylov for polynomials of degree <k. Proposition 4 is a routine covering-number comparison of parametric dimension O(Qm) versus unconstrained rank-r (up to n) classes; it supplies an upper-bound capacity argument, not a circular forecast of the free-oracle collapse. The directed SBM is deliberately constructed so that the symmetrized graph is uninformative, making the chance performance of q=0 baselines a design check rather than a derived prediction. No load-bearing uniqueness theorems, ansatzes, or results are imported from overlapping-author prior work; related citations (Huang, Ito, Musco, Saad, GIST, etc.) are external. Negative real-graph results are reported honestly. The derivation chain is therefore independent of its experimental targets.

Axiom & Free-Parameter Ledger

6 free parameters · 5 axioms · 2 invented entities

The central claims rest on standard Hermitian spectral calculus and classical Krylov approximation theory, plus domain modeling choices for magnetic operators and structured response families. Free parameters are the usual method hyperparameters (Krylov depth, probes, potential grid, mixture size, RMS gain). No new physical entities are postulated; the PE is a computational object. The main non-standard modeling load is that fixed multi-q structured scalar responses suffice for useful directed information.

free parameters (6)
  • block Krylov depth k
    Chosen by hand (default k=10; swept 2–20). Controls approximation bias; theory only gives asymptotic O(log 1/ε), not a data-free optimal k for finite graphs.
  • probe count s
    Chosen by hand (default s=32; ablated 8/32/64). Sets Monte-Carlo resolution of node and pairwise features; accuracy depends on this free budget.
  • magnetic potential grid ⃗q
    Fixed discrete grid (e.g. (0,1/6,1/3) or Q=10). Not learned; task-aligned q is critical (Figure 1c) and left as an open direction in Section 6.
  • heat–resolvent mixture size m and bounds (tmin,tmax,τmin)
    Structured family capacity and analyticity constants that enter Theorem 1’s uniform rate; chosen as design hyperparameters (e.g. 6 components).
  • per-head RMS normalization with learnable gain
    Authors state this was essential for fair family comparison and large accuracy swings when disabled (Appendix C); it is an empirical parameterization choice, not derived.
  • PE dimension, heads H, MLP backbone width/depth, learning rates
    Standard training hyperparameters that affect reported accuracies though not the existence of the matrix-function PE itself.
axioms (5)
  • standard math A matrix function of a Hermitian operator is defined via spectral projectors and is independent of eigenbasis choices within eigenspaces.
    Used for Proposition 1 and the gauge-invariance claim; classical spectral calculus.
  • standard math Block Lanczos / Krylov approximation error for f(A)R is controlled by best uniform polynomial approximation of f on the spectral interval (with reorthogonalization for numerical stability).
    Theorem 1 and Lemma 1; cites Saad, Musco et al., Trefethen.
  • domain assumption Normalized magnetic operators A_q encode directed structure via phases Θ_uv^(q)=2πq(a_uv−a_vu), with multi-q needed for directed walk profiles.
    Setup Section 3 and Proposition 3; inherits Multi-q Mag-PE / Huang et al. magnetic Fourier correspondence.
  • ad hoc to paper Heat–resolvent mixtures and low-degree Chebyshev responses are a sufficiently rich yet low-dimensional hypothesis class for the PE task.
    Section 3 families and Proposition 4 capacity argument; design choice that drives both approximation and generalization claims.
  • standard math Complex Gaussian probes yield unbiased Hutchinson-style estimators of matrix entries of products of matrix functions with O(1/√s) error.
    Proposition 2; complex analogue of random spectral kernels used by GIST.
invented entities (2)
  • Mag-Krylov learnable PE (h_θ(A_q)R with Hermitian block-Krylov cache) no independent evidence
    purpose: Provide eigenbasis-independent, sparse-matvec, learnable spectral positional encodings for directed graphs and shared pairwise readouts.
    Computational construction rather than a new physical object; independent evidence is the controlled SBM recovery and scaling diagnostics, not an external measurement.
  • Unconstrained per-eigenvalue Free spectral oracle (diagnostic) no independent evidence
    purpose: Capacity foil showing high-parameter spectral weights overfit relative to structured families.
    Introduced only as a diagnostic hypothesis class in Section 3/Proposition 4; not proposed as a practical method.

pith-pipeline@v1.1.0-grok45 · 21929 in / 4040 out tokens · 46922 ms · 2026-07-14T15:53:36.315338+00:00 · methodology

0 comments
read the original 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_\theta(A_q)\,R$, where $A_q$ is a normalized magnetic operator, $h_\theta$ 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.

Figures

Figures reproduced from arXiv: 2607.07032 by Jiaqing Xie, Yuxin Wang.

Figure 1
Figure 1. Figure 1: DSBM diagnostics, left to right: (a) test accuracy vs. block Krylov depth k (dashed lines: exact eigendecomposition oracles), the experimental counterpart of Theorem 1; (b) label efficiency in exact mode; free per-eigenvalue weights need far more labels than the O(m)-parameter heat–resolvent family, consistent with Proposition 3; (c) single-potential accuracy vs. q, peaking near the cycle-aligned potential… view at source ↗
Figure 1
Figure 1. Figure 1: DSBM diagnostics, left to right: (a) test accuracy vs. block Krylov depth k (dashed lines: exact eigendecomposition oracles), the experimental counterpart of Theorem 1, together with the matched Magnetic￾RFP power-iterate baseline; (b) label efficiency in exact mode; the unconstrained per-eigenvalue oracle needs far more labels than the O(m)-parameter heat–resolvent family, consistent with Proposition 4; (… view at source ↗

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 1 canonical work pages

  1. [1]

    arXiv preprint arXiv:2012.09699 , year=

    A generalization of transformer networks to graphs , author=. arXiv preprint arXiv:2012.09699 , year=

    Pith/arXiv arXiv 2012

  2. [2]

    Advances in Neural Information Processing Systems , volume=

    Recipe for a general, powerful, scalable graph transformer , author=. Advances in Neural Information Processing Systems , volume=

  3. [3]

    The Eleventh International Conference on Learning Representations , year=

    Sign and Basis Invariant Networks for Spectral Graph Representation Learning , author=. The Eleventh International Conference on Learning Representations , year=

  4. [4]

    International Conference on Learning Representations , year=

    Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks , author=. International Conference on Learning Representations , year=

  5. [5]

    International Conference on Learning Representations , volume=

    On the stability of expressive positional encodings for graphs , author=. International Conference on Learning Representations , volume=

  6. [6]

    Proceedings of The 28th International Conference on Artificial Intelligence and Statistics , pages =

    Learning Laplacian Positional Encodings for Heterophilous Graphs , author =. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics , pages =. 2025 , editor =

    2025

  7. [7]

    International Conference on Learning Representations , volume=

    Learning efficient positional encodings with graph neural networks , author=. International Conference on Learning Representations , volume=

  8. [8]

    International conference on machine learning , pages=

    Graph positional encoding via random feature propagation , author=. International conference on machine learning , pages=. 2023 , organization=

    2023

  9. [9]

    arXiv preprint arXiv:2603.16849 , year=

    GIST: Gauge-Invariant Spectral Transformers for Scalable Graph Neural Operators , author=. arXiv preprint arXiv:2603.16849 , year=

    Pith/arXiv arXiv

  10. [10]

    Advances in neural information processing systems , volume=

    Convolutional neural networks on graphs with fast localized spectral filtering , author=. Advances in neural information processing systems , volume=

  11. [11]

    Advances in neural information processing systems , volume=

    Bernnet: Learning arbitrary graph spectral filters via bernstein approximation , author=. Advances in neural information processing systems , volume=

  12. [12]

    International conference on machine learning , pages=

    How powerful are spectral graph neural networks , author=. International conference on machine learning , pages=. 2022 , organization=

    2022

  13. [13]

    The Eleventh International Conference on Learning Representations , year=

    Specformer: Spectral Graph Neural Networks Meet Transformers , author=. The Eleventh International Conference on Learning Representations , year=

  14. [14]

    International Conference on Learning Representations , year=

    LanczosNet: Multi-Scale Deep Graph Convolutional Networks , author=. International Conference on Learning Representations , year=

  15. [15]

    Advances in neural information processing systems , volume=

    Magnet: A neural network for directed graphs , author=. Advances in neural information processing systems , volume=

  16. [16]

    International conference on machine learning , pages=

    Transformers meet directed graphs , author=. International conference on machine learning , pages=. 2023 , organization=

    2023

  17. [17]

    International Conference on Learning Representations , volume=

    What are good positional encodings for directed graphs? , author=. International Conference on Learning Representations , volume=

  18. [18]

    Proceedings of the National Academy of Sciences , year=

    Powers of magnetic graph matrix: Fourier spectrum, walk compression, and applications , author=. Proceedings of the National Academy of Sciences , year=. doi:10.1073/pnas.2516664123 , url=

    work page doi:10.1073/pnas.2516664123

  19. [19]

    SIAM Journal on Numerical Analysis , volume=

    Analysis of some Krylov subspace approximations to the matrix exponential operator , author=. SIAM Journal on Numerical Analysis , volume=. 1992 , publisher=

    1992

  20. [20]

    Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Stability of the Lanczos method for matrix function approximation , author=. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2018 , organization=

    2018

  21. [21]

    2019 , publisher=

    Approximation theory and approximation practice, extended edition , author=. 2019 , publisher=

    2019