pith. sign in

arxiv: 2605.05759 · v2 · pith:XVFD2TNJnew · submitted 2026-05-07 · 💻 cs.LG

Full-Spectrum Graph Neural Networks: Expressive and Scalable

Xiaohan Wang , Deyu Bo , Longlong Li , Kelin Xia This is my paper

Pith reviewed 2026-05-08 14:51 UTC · model grok-4.3

classification 💻 cs.LG
keywords spectral graph neural networksexpressivityheterophilic graphsnode-pair signalsbivariate filterslow-rank approximationfull-spectrum convolutionLocal 2-GNN
0
0 comments X

The pith

FSpecGNN lifts classical spectral GNNs to the node-pair domain using bivariate filters over eigenvalue pairs, recovering the old models as a diagonal case while reaching universal approximation of node-pair signals.

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

The paper establishes a second-order generalization of spectral graph neural networks that moves beyond their standard 1-dimensional Weisfeiler-Lehman bound. It does so by lifting node signals into the node-pair domain and replacing univariate eigenvalue filters with bivariate filters that act on pairs of eigenvalues. Classical spectral GNNs emerge directly as the special case where only matching eigenvalue pairs are considered. This construction matters because node-pair signals are especially useful when graphs are heterophilic, and the method still permits scalable implementations on large graphs through low-rank approximations that reduce the full convolution to combinations of polynomial filters.

Core claim

FSpecGNN advances spectral filtering by lifting signals from the node domain to the node-pair domain and extending the univariate spectral filter over eigenvalues to a bivariate filter over eigenvalue pairs. Classical spectral GNNs arise as a diagonal special case. The model is at most as expressive as Local 2-GNN yet can universally approximate node-pair signals, which supports improved learning on heterophilic graphs. Scalable realizations avoid explicit node-pair computations and employ a low-rank approximation that combines polynomial spectral filters, enabling use on large graphs.

What carries the argument

The bivariate spectral filter over eigenvalue pairs, applied after lifting the input signal to the node-pair domain.

If this is right

  • Classical spectral GNNs are recovered exactly as the diagonal special case of FSpecGNN.
  • FSpecGNN is at most as expressive as Local 2-GNN.
  • FSpecGNN universally approximates arbitrary node-pair signals.
  • The approach yields scalable implementations that avoid explicit node-pair computations.
  • FSpecGNN delivers strong empirical performance on heterophilic graph benchmarks.

Where Pith is reading between the lines

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

  • The node-pair lifting may prove useful for other tasks that depend on pairwise relationships rather than single-node labels.
  • The low-rank reduction to polynomial filters suggests that existing efficient spectral GNN codebases could be adapted with modest changes.
  • Extending the bivariate construction to higher-order tuples of nodes could be a direct next step if the pair-wise version succeeds.
  • The separation between expressivity bound and approximation power highlights a design space where models can be tuned for specific heterophilic regimes.

Load-bearing premise

The low-rank approximation of the full-spectrum convolution preserves both the universal approximation property for node-pair signals and the claimed expressivity bound without introducing errors that invalidate the theoretical results on realistic graphs.

What would settle it

A small graph where the low-rank approximated FSpecGNN fails to recover a specific node-pair signal that the exact version or a Local 2-GNN can approximate within a given error tolerance.

Figures

Figures reproduced from arXiv: 2605.05759 by Deyu Bo, Kelin Xia, Longlong Li, Xiaohan Wang.

Figure 1
Figure 1. Figure 1: FSPECGNN generalizes spectral filtering by lifting sig￾nals to the node-pair domain and extending univariate eigenvalue filters to bivariate filters over eigenvalue pairs. Proposition 3.3 embeds spectral GNN (SpecGNN) to the diagonal restriction of FSPECGNN, and Theorem 3.8 establishes that FSPECGNN can be as expressive as Local 2-GNN. provides a principled lens for comparing the representational power of … view at source ↗
Figure 2
Figure 2. Figure 2: Off-diagonal components grow with heterophily. Top: Synthetic graphs with increasing heterophily h(G) = 1 |E| P (u,v)∈E 1[ℓ(u) ̸= ℓ(v)]. Bottom-left: For each graph, we compute the optimal convolution and plot the near-diagonal energy ratio EC∗ (δ) as a function of the bandwidth δ. Curves that are close to 1 already at δ = 0 indicate that most spectral energy concentrates on the diagonal, whereas curves th… view at source ↗
Figure 3
Figure 3. Figure 3: The Frucht graph (image adapted from (Wikipedia contributors, 2025)). Despite having a trivial automorphism group, the stable 1-WL refinement assigns a single color to all vertices. Recall that the 1-WL color refinement is defined by χ 1−WL,(k+1)(i) = hash χ 1−WL,(k) (i), χ 1−WL,(k) (j) : j ∈ N(i)  , where hash is a perfect hash function and χ 1−WL,(0)(i) = ℓ(i). Since each update function H(k) depends… view at source ↗
read the original abstract

It is well established that spectral graph neural networks (GNNs) can universally approximate node signals; however, their expressive power remains bounded by the 1-dimensional Weisfeiler-Lehman test, which is mirrored in their lack of universality for higher-order signals. To go beyond this bound, we propose the Full-Spectrum GNNs (FSpecGNNs), a second-order generalization of classical spectral GNNs. FSpecGNN advances spectral filtering from two perspectives: (1) it lifts signals from the node domain to the node-pair domain; and (2) it extends the univariate spectral filter over eigenvalues to a bivariate filter over eigenvalue pairs. We show that classical spectral GNNs arise as a diagonal special case of FSpecGNNs, and prove that FSpecGNNs can be at most as expressive as Local 2-GNN while universally approximating node-pair signals, the latter being particularly beneficial for heterophilic graph learning. Moreover, FSpecGNN admits scalable implementations that avoid explicit node-pair-level computations; combined with a low-rank approximation that reduces full-spectrum convolution to a combination of polynomial spectral filters, it enables learning on large graphs. Empirically, FSpecGNN validates the predicted expressivity and delivers strong performance on heterophilic benchmarks.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper proposes the Full-Spectrum Graph Neural Network (FSpecGNN) as a second-order generalization of classical spectral GNNs. It lifts node signals to the node-pair domain and replaces univariate spectral filters with bivariate filters over eigenvalue pairs. Classical spectral GNNs are recovered as the diagonal special case. The authors prove that FSpecGNN is at most as expressive as Local 2-GNN while universally approximating arbitrary node-pair signals (with benefits for heterophilic graphs), and they supply scalable implementations that avoid explicit pair-wise computations by means of a low-rank approximation that reduces the operator to a combination of polynomial spectral filters. Empirical results on heterophilic benchmarks are reported in support of the claims.

Significance. If the expressivity and universal-approximation theorems are rigorously established and the low-rank approximation is shown to preserve them, the work would supply a principled, scalable route to spectral GNNs that exceed the 1-WL barrier while retaining the computational advantages of polynomial filters. The explicit reduction to Local 2-GNN expressivity and the targeted improvement on heterophilic tasks would be useful contributions to the literature on higher-order graph learning.

major comments (1)
  1. [Abstract and scalable implementation section] Abstract and the description of the scalable implementation: the central claims of universal approximation of node-pair signals and equivalence (at most) to Local 2-GNN expressivity are stated for the full-spectrum bivariate convolution. The practical algorithm, however, substitutes a low-rank approximation that reduces the operator to polynomial filters. No explicit error bound, convergence rate, or perturbation analysis is supplied showing that the approximation error vanishes in a manner that preserves both the universality property and the exact expressivity ceiling on finite, non-ideal graphs. This omission is load-bearing because the paper's scalability argument rests on the approximation.
minor comments (1)
  1. [Abstract] The abstract asserts that FSpecGNN 'can be at most as expressive as Local 2-GNN'; a brief clarification of whether the bound is tight or whether there exist graphs on which FSpecGNN is strictly weaker would improve precision.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. The feedback highlights an important aspect of the scalability claims, and we address it directly below. We will revise the paper to incorporate the requested analysis.

read point-by-point responses

  1. Referee: [Abstract and scalable implementation section] Abstract and the description of the scalable implementation: the central claims of universal approximation of node-pair signals and equivalence (at most) to Local 2-GNN expressivity are stated for the full-spectrum bivariate convolution. The practical algorithm, however, substitutes a low-rank approximation that reduces the operator to polynomial filters. No explicit error bound, convergence rate, or perturbation analysis is supplied showing that the approximation error vanishes in a manner that preserves both the universality property and the exact expressivity ceiling on finite, non-ideal graphs. This omission is load-bearing because the paper's scalability argument rests on the approximation.

    Authors: We agree that the current manuscript does not supply an explicit error bound or perturbation analysis for the low-rank approximation, and that this is a substantive point given the role of the approximation in the scalability argument. The universal-approximation and expressivity results (at most Local 2-GNN) are rigorously established for the exact full-spectrum bivariate convolution. The low-rank approximation is introduced solely as a computational device that expresses the bivariate filter as a sum of univariate polynomial filters, thereby avoiding explicit node-pair operations. In the revised version we will add a dedicated subsection under the scalable-implementation heading that provides (i) an operator-norm bound on the difference between the exact bivariate filter and its low-rank surrogate, (ii) a convergence rate showing that the approximation error vanishes as the rank parameter increases, and (iii) a perturbation argument demonstrating that, for any finite graph, the node-pair signal approximation error can be made arbitrarily small while the expressivity ceiling remains unchanged (the approximated operator is still a linear combination of spectral filters and therefore cannot exceed Local 2-GNN power). This analysis will be stated for both the theoretical model and the practical algorithm, thereby closing the gap identified by the referee. revision: yes

Circularity Check

0 steps flagged

No significant circularity; claims rest on independent proofs and standard graph theory

full rationale

The paper defines FSpecGNN via lifting to node-pair signals and bivariate spectral filters over eigenvalue pairs, then states that classical spectral GNNs are the diagonal special case and proves an expressivity upper bound matching Local 2-GNN plus universal approximation for node-pair signals. These are presented as theorems without reducing any quantity to a fitted parameter renamed as prediction, without self-definitional loops, and without load-bearing self-citations that substitute for external verification. The low-rank approximation is introduced separately for scalability and does not retroactively alter the stated full-spectrum theorems. The derivation chain therefore remains self-contained against external benchmarks such as 1-WL and standard spectral theory.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on established spectral graph theory and Weisfeiler-Lehman results without introducing new free parameters or postulated entities.

axioms (2)
  • standard math Eigenvalues and eigenvectors of the graph Laplacian define valid spectral filters
    Invoked throughout the definition of spectral convolution.
  • domain assumption Standard spectral GNNs are bounded by the 1-dimensional Weisfeiler-Lehman test
    Used as the baseline expressivity limit to surpass.

pith-pipeline@v0.9.0 · 5529 in / 1368 out tokens · 60103 ms · 2026-05-08T14:51:22.625269+00:00 · methodology

discussion (0)

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