Pith. sign in

REVIEW 2 major objections 6 minor 19 references

Reviewed by Pith at T0; open to challenge.

T0 means a machine referee read the full paper against a public rubric. The mark states how deep the mechanical check went, never who wrote it. the ladder, T0–T4 →

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

T0 review · glm-5.2

Directed graph positions without eigenvectors: Krylov suffices

2026-07-09 21:16 UTC pith:M32AOFV4

load-bearing objection The core construction is sound and genuinely useful: gauge-invariant spectral PEs for directed graphs via matrix functions, with a clean O(log(1/ε)) Krylov guarantee. The empirical validation is thinner than I'd like — it works on synthetic data and honest negative results on real benchmarks. the 2 major comments →

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

Gauge-Invariant 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 positional encodingdirected graphsmagnetic LaplacianKrylov subspacematrix functiongauge invariancegraph neural networksblock Lanczos
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.

The paper claims that learnable spectral positional encodings for directed graphs need not compute eigenvectors at all. Instead of eigendecomposing a magnetic Laplacian—a costly Hermitian operator whose complex eigenvectors suffer from gauge ambiguity—the authors define the encoding as a matrix function h_θ(A_q) applied to a block of random probe vectors R. Because a matrix function depends only on the operator itself, not on any choice of eigenbasis, gauge invariance is automatic and no special invariant architecture is needed. The encoding is approximated in a Hermitian block Krylov subspace built from sparse matrix–vector products, and the authors prove that k = O(log(1/ε)) block steps suffice to uniformly approximate the entire heat–resolvent family of learnable spectral responses. The paper further argues, via a covering-number bound, that structured low-dimensional response families generalize better than free per-eigenvalue weights, which overfit in low-label regimes. On a synthetic directed stochastic block model whose symmetrization is deliberately uninformative, direction-blind encodings stay at chance while the magnetic Krylov encodings recover the planted directional structure, converging to the exact-eigendecomposition oracle as depth grows. The same random probes yield gauge-invariant pairwise node features with 1/√s Monte Carlo error, at no extra preprocessing cost.

Core claim

The central mechanism is the identity h_θ(A_q)R—a learnable scalar spectral response h_θ applied as a matrix function to the magnetic operator A_q and multiplied by random Gaussian probes R. This object is gauge-invariant by construction because matrix functions are defined through spectral projectors, not eigenvector coordinates. It is computable via block Lanczos iteration using only sparse matrix–vector products, with the approximation error bounded by 2∥R∥_F times the best degree-(k−1) polynomial approximation error of h_θ on [−1,1]. For heat–resolvent response families, this polynomial approximation error decays geometrically, giving uniform O(log(1/ε)) convergence over all parameter in

What carries the argument

Hermitian block Krylov subspace K_k(A_q, R) = span{R, A_q R, ..., A_q^{k-1} R}, constructed via QR-stabilized block Lanczos. The approximate PE is Q·h_θ(T)·G where Q is the Krylov basis, T = Q^H A_q Q is the projected operator, and G = Q^H R. The magnetic operator A_q = -D^{-1/2} H_q D^{-1/2} is Hermitian with spec(A_q) ⊆ [-1,1], encoding edge directions as complex phases. Uniform approximation (Theorem 1) follows from Cauchy interlacing (spec(T) ⊆ spec(A_q)) and Bernstein-ellipse analyticity of resolvents and heat kernels. Covering-number separation (Proposition 3): heat–resolvent mixtures with m components have O(Qm) parameters versus Ω(Qr) for free per-eigenvalue weights, yielding e^{O(√(

Load-bearing premise

The uniform approximation guarantee holds only for heat–resolvent response families (analytic functions on a Bernstein ellipse), not for arbitrary learnable responses like MLPs. The practical value also rests on the magnetic operator with a fixed grid of potentials capturing task-relevant directional structure—an assumption that fails on standard real directed benchmarks where all spectral PEs perform within noise of random probes.

What would settle it

A directed graph learning task where the relevant directional signal lives in spectral features that are not well-approximated by low-degree polynomials or heat–resolvent mixtures would break the O(log(1/ε)) guarantee, forcing large k and eliminating the computational advantage over direct eigendecomposition. Alternatively, if on some real-world directed benchmark the magnetic Krylov PE significantly outperformed both random probes and direction-blind PEs, that would validate the practical utility claim that the current real-data experiments cannot.

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

If this is right

  • Graph transformers that currently precompute expensive eigendecompositions for positional encodings could replace them with a fixed Krylov cache plus a lightweight learnable spectral filter, eliminating both the O(n³) cost and the sign/basis ambiguity problem simultaneously.
  • The separation of approximation bias (Krylov depth k), estimation variance (response family capacity), and Monte Carlo resolution (probe count s) into three independent tuning knobs provides a principled design framework for spectral PEs beyond the directed setting.
  • The pairwise readout—unbiased Hutchinson estimation of gauge-invariant matrix entries from the same cached probes—opens a route to edge-level and pair-level prediction tasks without any additional spectral preprocessing.
  • The negative result on real directed benchmarks (all spectral PEs within noise of random probes) suggests that standard node-classification datasets may not actually test directional structure, motivating the construction of new benchmarks with controlled directional signal.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The O(log(1/ε)) guarantee is specific to analytic response families (heat kernels, resolvents). The MLP response, which performs comparably on the synthetic benchmark, has no approximation guarantee—suggesting the theory covers a strict subset of what works in practice, and that the analytic-family assumption may be more conservative than necessary.
  • If the magnetic potential grid were made learnable rather than fixed, the Krylov cache would need rebuilding whenever q changes, creating a bi-level optimization problem whose cost geometry is unexplored here.
  • The covering-number argument for structured versus free responses parallels classical bias-variance tradeoffs but operates in the spectral domain: the 'capacity' is measured by how many independent spectral degrees of freedom the response can modulate, not by the dimension of the downstream network.

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

2 major / 6 minor

Summary. The paper proposes learnable spectral positional encodings (PEs) for directed graphs of the form Z_q(θ) = h_θ(A_q)R, where A_q is a normalized magnetic operator, h_θ is a learnable scalar spectral response, and R is a block of random Gaussian probes. Because the PE is defined as a matrix function of the operator rather than through its eigenvectors, it is gauge-invariant by construction, eliminating the sign/basis ambiguity that prior work addresses with specialized invariant architectures. The matrix function is approximated in a Hermitian block Krylov subspace using only sparse matrix-vector products, avoiding the O(n^3) dense Hermitian eigendecomposition required by magnetic Laplacian methods. The authors prove that k = O(log(1/ε)) block Krylov steps suffice for uniform ε-approximation over heat-resolvent response families (Theorem 1), provide a covering-number argument showing that low-dimensional structured response families have lower estimation variance than free per-eigenvalue weights (Proposition 3), and show that the same probes yield gauge-invariant pairwise features with O(1/√s) Monte-Carlo error (Proposition 2). Experiments on a directed stochastic block model (DSBM) designed so that symmetrization destroys all class signal show that direction-blind PEs stay at chance while magnetic Krylov PEs recover the planted structure, converging to the exact-eigendecomposition oracle as Krylov depth increases.

Significance. The paper addresses a genuine technical gap: existing magnetic Laplacian PEs require dense Hermitian eigendecompositions per potential and dedicated basis-invariant architectures to handle gauge ambiguity. The matrix-function formulation elegantly resolves both issues simultaneously — gauge invariance is automatic from the spectral calculus, and the Krylov approximation replaces cubic eigendecomposition with sparse matvecs. The uniform approximation guarantee (Theorem 1) is a clean application of classical Krylov convergence theory made uniform over a structured learnable family, which is the right level of analysis for a learning guarantee. The covering-number argument (Proposition 3) usefully separates approximation bias (controlled by k) from estimation variance (controlled by the response family), and the experimental confirmation that free per-eigenvalue weights overfit in the low-label regime while structured families succeed is a valuable empirical observation. The honest reporting of negative results on real directed benchmarks (Table 3) and the controlled DSBM diagnostic are commendable. The pairwise regression readout (Proposition 2, Tables 8-9) provides an additional use

major comments (2)
  1. The empirical validation is confined to synthetic settings where directional structure is planted by construction. The DSBM (Section 5) is designed so that symmetrization destroys all class signal, which makes it a clean diagnostic but also a setting where the method's advantage is guaranteed by construction. The pairwise regression results (Tables 8-9) use synthetic DAGs from the same framework as Huang et al. (2025). On real directed benchmarks (Table 3), all spectral PEs perform within noise of random probes. The paper acknowledges this honestly, but the practical utility of the method beyond controlled synthetic settings remains unclear. The authors mention in Section 6 that extending to circuit and sorting-network tasks is a 'natural next experimental step' — given that Huang et al. (2025) evaluate on exactly these tasks, some results on real directed graphs with genuine directional
  2. The abstract states that 'the undirected q=0 case improves heterophilous benchmarks over no-PE and polynomial baselines.' Table 6 shows Krylov-Heat improves over Direct-Cheb and no-PE on Minesweeper and Questions, but LapPE outperforms Krylov-Heat on all three datasets, and on Tolokers the improvement over no-PE is marginal (76.04 vs 73.49). The abstract's claim of improvement over 'baselines' is technically accurate for the polynomial baselines but could be read as a stronger claim than the data supports, since LapPE is the strongest method overall. The authors' interpretation that 'these undirected graphs have rich node features, and a fixed low-pass eigenvector summary suffices' is reasonable but the abstract should be more precise about which baselines are improved upon.
minor comments (6)
  1. Eq. (2): the relationship A_q = L_q - I is stated, but the sign convention and normalization of the magnetic Laplacian L_q should be stated more explicitly, as different papers use different conventions (normalized vs. unnormalized, sign of the phase term).
  2. Table 1: the 'Eigenvector-free' column for LanczosNet is marked 'partial' — a brief clarification of what 'partial' means in this context would help readers.
  3. Section 5, naming convention: 'HR' is used for heat-resolvent but 'Heat' is used for heat-only; making this distinction explicit earlier (e.g., in Section 3 where the families are defined) would reduce confusion.
  4. Figure 1d: the y-axis is labeled 'PE precompute time (s)' on a log scale, but the caption text refers to '0.09s at n=600 to 0.17s at n=50k' — these values appear to be on a linear scale while the figure is logarithmic. Please verify consistency.
  5. Appendix C mentions orthogonality error tracking but does not report the actual values observed across experiments. Including a summary table or a note in the main text about typical orthogonality residuals would strengthen the numerical reliability claim.
  6. The reference list appears to be incomplete — several works mentioned in the text (e.g., the directed SBM construction details) could benefit from more precise citations. Please verify all references are complete in the final version.

Circularity Check

0 steps flagged

No circularity found; derivation is self-contained using standard linear algebra and approximation theory

full rationale

The paper's three load-bearing claims are each derived from standard, external mathematics without circular dependencies. (1) Proposition 1 (gauge invariance) follows directly from the spectral calculus h(A) = Σ h(λ_i)Π_i, where spectral projectors Π_i are uniquely defined regardless of eigenbasis choice — a standard fact in linear algebra, applied self-containedly in Appendix A.1. (2) Theorem 1 (uniform Krylov approximation) chains Lemma 1 (block polynomial exactness, a standard block Lanczos property), Cauchy interlacing for compressions, and Bernstein ellipse approximation theory cited to Trefethen (2019, an external textbook). The exponential convergence rate ρ < 1 for heat-resolvent families (Eq. 7) is derived from the analyticity of resolvents and heat kernels on Bernstein ellipses — no fitted parameters are renamed as predictions. (3) Proposition 3 (covering number) uses standard empirical process theory: more parameters (free per-eigenvalue weights, d = Ω(Qr)) yield higher covering entropy than structured families (d = O(Qm)), giving worse generalization rates. The DSBM benchmark is a controlled diagnostic where directional structure is planted, but the success of magnetic Krylov PEs is not forced by construction — it requires that the Krylov approximation captures the relevant spectral information, and the convergence to the exact oracle as k grows is an empirical finding. The pairwise regression results (Tables 8-9) use the framework of Huang et al. (2025), but these are different authors (Yinan Huang, Haoyu Wang, Pan Li vs. Jiaqing Xie, Yuxin Wang), so there is no self-citation issue. The negative result on real benchmarks (Table 3) is honestly reported. No step in the derivation chain reduces to its own inputs by definition or by fitted-then-predicted construction.

Axiom & Free-Parameter Ledger

5 free parameters · 4 axioms · 0 invented entities

The paper introduces no new mathematical entities or physical postulates. The magnetic operator A_q, block Krylov subspaces, and heat-resolvent response families are all standard constructions from prior work. The contribution is in their combination and the resulting guarantees.

free parameters (5)
  • Krylov depth k = 10 (default), swept 2-20
    Controls approximation bias; chosen empirically, not derived from data.
  • Probe count s = 32 (default), swept 8-64
    Controls Monte-Carlo resolution; chosen empirically.
  • Number of heat/resolvent components m = 6-8
    Controls response family capacity; chosen empirically.
  • Magnetic potentials grid q = (0, 1/6, 1/3)
    Fixed grid; paper notes learnable q is left as future work.
  • RMS normalization gain = learnable
    Per-head learnable gain; authors note it is essential for fair comparisons.
axioms (4)
  • standard math Block Lanczos produces an orthonormal basis Q of the Krylov subspace K_k(A,R) with spec(T) ⊆ spec(A) via Cauchy interlacing
    Standard result from numerical linear algebra; invoked in Theorem 1 proof (Appendix A.4).
  • standard math Best uniform polynomial approximation of analytic functions on Bernstein ellipses decays geometrically
    Classical approximation theory (Trefethen 2019, Ch. 8); invoked for the exponential rate in Theorem 1.
  • domain assumption The magnetic Laplacian A_q faithfully encodes directional structure of directed graphs
    Inherited from Geisler et al. 2023 and Huang et al. 2025; the operator definition (Eq. 2) is standard but the assumption that it captures task-relevant structure is domain-specific.
  • standard math Bounded Lipschitz losses yield standard covering-number uniform deviation bounds
    Standard empirical process theory; invoked in Proposition 3 proof (Appendix A.5).

pith-pipeline@v1.1.0-glm · 18327 in / 2874 out tokens · 287870 ms · 2026-07-09T21:16:46.098784+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 ↗

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

19 extracted references · 19 canonical work pages · 1 internal anchor

  1. [1]

    A Generalization of Transformer Networks to Graphs

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

    work page internal anchor Pith review 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=

    work page

  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=

    work page

  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=

    work page

  5. [5]

    International Conference on Learning Representations , volume=

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

    work page

  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 =

    work page 2025

  7. [7]

    International Conference on Learning Representations , volume=

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

    work page

  8. [8]

    International conference on machine learning , pages=

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

    work page 2023

  9. [9]

    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=

    work page

  10. [10]

    Advances in neural information processing systems , volume=

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

    work page

  11. [11]

    International conference on machine learning , pages=

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

    work page 2022

  12. [12]

    The Eleventh International Conference on Learning Representations , year=

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

    work page

  13. [13]

    International Conference on Learning Representations , year=

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

    work page

  14. [14]

    Advances in neural information processing systems , volume=

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

    work page

  15. [15]

    International conference on machine learning , pages=

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

    work page 2023

  16. [16]

    International Conference on Learning Representations , volume=

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

    work page

  17. [17]

    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=

    work page 1992

  18. [18]

    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=

    work page 2018

  19. [19]

    2019 , publisher=

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

    work page 2019