Full-Spectrum Graph Neural Networks: Expressive and Scalable

Deyu Bo; Kelin Xia; Longlong Li; Xiaohan Wang

REVIEW 2 major objections 2 minor 9 references

FSpecGNNs lift node signals to node pairs and replace univariate eigenvalue filters with bivariate ones over eigenvalue pairs.

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.3

2026-06-30 22:58 UTC pith:XVFD2TNJ

load-bearing objection FSpecGNN adds a bivariate eigenvalue-pair filter and node-pair lifting that generalizes classical spectral GNNs as the diagonal case, but the low-rank reduction for scalability may not preserve claimed universal node-pair approximation. the 2 major comments →

arxiv 2605.05759 v2 pith:XVFD2TNJ 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

classification cs.LG

keywords graph neural networksspectral methodsexpressivityheterophilic graphsnode-pair signalsbivariate filtersscalable convolution

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 introduces Full-Spectrum GNNs to move past the expressivity ceiling of standard spectral graph neural networks. It does so by moving computation into the node-pair domain and letting the filter depend on pairs of eigenvalues rather than single eigenvalues. Classical spectral GNNs appear inside this construction as the case where the bivariate filter is forced to act only on matching eigenvalue pairs. The new models stay within the power of Local 2-GNN yet can approximate arbitrary signals defined on node pairs, which matters for graphs in which neighbors often differ in type. Efficient versions avoid building the full pair graph by using low-rank reductions that keep the work comparable to ordinary polynomial filters.

Core claim

FSpecGNNs constitute a second-order generalization of classical spectral GNNs obtained by lifting signals from the node domain to the node-pair domain and replacing the univariate spectral filter with a bivariate filter defined over eigenvalue pairs. Classical spectral GNNs arise precisely as the diagonal special case of this construction. The resulting networks are at most as expressive as Local 2-GNN while being able to universally approximate node-pair signals; this property is shown to be useful for heterophilic graph learning. Scalable realizations are obtained by avoiding explicit node-pair construction and by reducing full-spectrum convolution to combinations of polynomial spectral fi

What carries the argument

Node-pair domain lifting together with a bivariate spectral filter over eigenvalue pairs

Load-bearing premise

The bivariate spectral filter combined with node-pair lifting yields universal approximation of node-pair signals without ever constructing the full node-pair graph.

What would settle it

A small heterophilic graph and a concrete node-pair target function that no FSpecGNN (even with arbitrary polynomial degree) can approximate to within a fixed error while a Local 2-GNN can.

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

If this is right

Classical spectral GNNs are recovered exactly by restricting the bivariate filter to the diagonal of eigenvalue pairs.
FSpecGNNs can approximate any continuous function on node pairs, directly improving modeling of heterophilic neighborhoods.
Low-rank approximations reduce the method to combinations of standard polynomial filters, preserving linear scaling in the number of edges.
The same lifting and filtering steps apply without change to any graph where the spectrum is known or can be estimated.

Where Pith is reading between the lines

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

The same bivariate construction could be applied to edge-labeled or weighted graphs by treating edge attributes as additional coordinates in the pair domain.
Because the method stays inside Local 2-GNN power, it offers a spectral route to tasks such as link prediction that currently rely on spatial higher-order models.
Replacing the low-rank step with an exact but sparse node-pair representation on moderate-sized graphs would provide a direct empirical check of the approximation quality.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

FSpecGNN adds a bivariate eigenvalue-pair filter and node-pair lifting that generalizes classical spectral GNNs as the diagonal case, but the low-rank reduction for scalability may not preserve claimed universal node-pair approximation.

read the letter

The main things here are the bivariate spectral filter over eigenvalue pairs plus the lift of signals to the node-pair domain. This setup lets them treat ordinary spectral GNNs as the diagonal special case and positions the model as at most as expressive as Local 2-GNN while claiming universal approximation on node-pair signals, aimed at heterophilic graphs. They also give a low-rank route that turns the full-spectrum convolution into a sum of polynomial filters to avoid quadratic costs.

The bivariate filter and the node-pair lifting step are not in the spectral GNN papers they cite, so that combination counts as new. Framing the classical case as diagonal is a clean observation. The focus on heterophily is reasonable, and the abstract says they validate the expressivity claims empirically on those benchmarks.

The soft spot is the low-rank approximation. The stress-test note is right to flag that truncating to polynomial filters could drop the cross-eigenvalue interactions needed for true universal approximation on arbitrary node-pair signals. The abstract states the proofs and the approximation but supplies no steps, no error bounds, and no concrete account of how the lifting stays sub-quadratic. Without those details it is hard to know whether the universality claim survives the scalability fix.

This paper is for people already working on spectral GNN extensions and heterophilic learning. Readers who want new filter designs in that niche would find the bivariate idea worth seeing. It deserves a serious referee because the core construction is distinct and the target problem is active, even though the approximation details will need scrutiny.

Referee Report

2 major / 2 minor

Summary. The paper proposes Full-Spectrum Graph Neural Networks (FSpecGNNs) as a second-order generalization of classical spectral GNNs. It lifts node signals to the node-pair domain and replaces the univariate spectral filter with a bivariate filter over eigenvalue pairs. Classical spectral GNNs are recovered as the diagonal special case. The central claims are that FSpecGNNs are at most as expressive as Local 2-GNN while still universally approximating arbitrary node-pair signals (beneficial for heterophilic graphs), and that a low-rank approximation reduces the full-spectrum convolution to a combination of polynomial spectral filters, enabling scalable implementation without materializing the quadratic node-pair domain. Empirical results on heterophilic benchmarks are reported to support the predicted expressivity gains.

Significance. If the expressivity upper bound, the universal-approximation result for node-pair signals, and the preservation of that universality under the low-rank reduction all hold, the work would supply a concrete, scalable route to move spectral GNNs beyond the 1-WL barrier for tasks that depend on pairwise node information. The reduction of the bivariate filter to polynomial filters is a potentially useful implementation device, and the explicit positioning relative to Local 2-GNN supplies a clear expressivity reference point.

major comments (2)

[expressivity and low-rank approximation paragraph] Expressivity and low-rank approximation paragraph: the claim that the bivariate filter combined with node-pair lifting yields universal approximation of node-pair signals, even after the low-rank reduction to polynomial filters, is load-bearing for the central contribution. No error bound, truncation analysis, or explicit argument is supplied showing that higher-order cross-eigenvalue interactions remain spannable; if the chosen rank or polynomial degree truncates these interactions, universality for general node-pair signals is lost even while the Local 2-GNN upper bound may still hold.
[Implementation section] Implementation section (scalable realizations): the manuscript asserts that FSpecGNN admits implementations that avoid explicit node-pair-level computations, yet provides no concrete complexity analysis or pseudocode demonstrating how the node-pair lifting is realized in linear or near-linear time. This detail is required to substantiate the scalability claim that underpins practical use on large graphs.

minor comments (2)

[abstract and expressivity section] The abstract states that proofs of expressivity bounds and universal approximation are given, but the main text should include at least a high-level derivation sketch or reference to the key lemmas so that the logical steps can be followed without external material.
[preliminaries / filter definition] Notation for the bivariate filter (eigenvalue-pair domain) should be introduced with an explicit equation before the low-rank reduction is applied, to avoid ambiguity when comparing the diagonal special case to the general bivariate case.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the opportunity to respond to the referee's report. We appreciate the referee's careful reading and the identification of areas where the manuscript can be strengthened. We address the two major comments below.

read point-by-point responses

Referee: Expressivity and low-rank approximation paragraph: the claim that the bivariate filter combined with node-pair lifting yields universal approximation of node-pair signals, even after the low-rank reduction to polynomial filters, is load-bearing for the central contribution. No error bound, truncation analysis, or explicit argument is supplied showing that higher-order cross-eigenvalue interactions remain spannable; if the chosen rank or polynomial degree truncates these interactions, universality for general node-pair signals is lost even while the Local 2-GNN upper bound may still hold.

Authors: We clarify that the universal approximation result is proven for the full FSpecGNN model using the bivariate spectral filter on the lifted node-pair signals. The low-rank approximation is introduced separately as a means to achieve scalability by reducing the convolution to polynomial filters, but it is an approximation and does not necessarily preserve exact universality. The manuscript positions the low-rank version as a practical trade-off. We agree that an explicit analysis of the truncation error would be valuable and will add a new subsection providing error bounds and conditions under which the approximation maintains good performance for node-pair signal approximation. revision: yes
Referee: Implementation section (scalable realizations): the manuscript asserts that FSpecGNN admits implementations that avoid explicit node-pair-level computations, yet provides no concrete complexity analysis or pseudocode demonstrating how the node-pair lifting is realized in linear or near-linear time. This detail is required to substantiate the scalability claim that underpins practical use on large graphs.

Authors: We acknowledge that the current version lacks detailed pseudocode and complexity analysis for the scalable implementation. The description in the manuscript is high-level, relying on the fact that the low-rank reduction allows computation via standard polynomial spectral filters on the original graph without materializing pairs. We will revise the Implementation section to include explicit pseudocode for the forward pass and derive the computational complexity, which is linear in the number of edges for sparse graphs when using the low-rank factors. revision: yes

Circularity Check

0 steps flagged

No circularity; expressivity claims rest on stated proofs rather than self-referential fits or citations

full rationale

The abstract states that the authors prove FSpecGNNs are at most as expressive as Local 2-GNN while universally approximating node-pair signals, with classical spectral GNNs as a diagonal special case. These are presented as derived results from the node-pair lifting and bivariate filter construction. No equations reduce the claimed universality or expressivity bound to quantities fitted from the same data, nor do any load-bearing steps rely on self-citations whose content is unverified within the paper. The low-rank approximation is introduced solely for scalable implementation and does not redefine or presuppose the expressivity results. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the central claims rest on standard graph spectral theory and the unshown proof that the bivariate construction yields universal node-pair approximation.

pith-pipeline@v0.9.1-grok · 5763 in / 1199 out tokens · 16721 ms · 2026-06-30T22:58:28.119402+00:00 · methodology

0 comments

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.

Figures

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

**Figure 1.** Figure 1: FSPECGNN generalizes spectral filtering by lifting signals 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: 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: 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 ↗

**Figure 3.** Figure 3: 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 4.** Figure 4: 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 ↗

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

[1]

URL https://openreview.net/forum? id=SJU4ayYgl. Liu, F. and Wang, Q. Asymmetric learning for spectral graph neural networks. InProceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 18798–18806, 2025. Luan, S., Hua, C., Xu, M., Lu, Q., Zhu, J., Chang, X.-W., Fu, J., Leskovec, J., and Precup, D. When do graph neural networks help wit...

work page 2025
[2]

propose homomorphism expressivity as a finer quantitative hierarchy for comparing substructure-counting capabilities. In contrast, theoretical understanding of spectral GNN expressivity is relatively limited: Wang & Zhang (2022) establish universality results for spectral filtering on node signals, while also relating spectral models to 1-WL limitations. ...

work page 2022
[3]

, αR ∈R n andβ 1,

Ifrank(A) =R, there exist vectorsα 1, . . . , αR ∈R n andβ 1, . . . , βR ∈R n such that A= RX i=1 αiβ⊤ i . 15 Full Spectrum Graph Neural Network: Expressive and Scalable

work page
[4]

no multiple eigenvalues

Conversely, ifAcan be written as A= RX i=1 αiβ⊤ i , thenrank(A)≤R. In particular, the minimal number of rank-one matrices{α iβ⊤ i }required in such a decomposition equalsrank(A). Proof. (1) Since rank(A) =R , the column space of A has dimension R. Choose a basis c1, . . . , cR ∈R n for the column space and set C= [c 1 · · ·c R ]∈R n×R. Then there exists D...

work page 2022
[5]

for every u′ ∈N G(u), one child whose attached subtree is L-UNR(k−1) G (u′, v), with the edge from the root to this child labeled by1

work page
[6]

for every v′ ∈N G(v), one child whose attached subtree is L-UNR(k−1) G (u, v′), with the edge from the root to this child labeled by2. Two such trees are said to be isomorphic if there exists a bijection between their vertex sets that preserves: (i) the root, (ii) the parent–child relation, (iii) the vertex labels, and (iv) the directed edge labels in{1,2...

work page 2020
[7]

35 Full Spectrum Graph Neural Network: Expressive and Scalable

Ifs= 0, thenrank(R) = 0andrank(M) =u−2. 35 Full Spectrum Graph Neural Network: Expressive and Scalable

work page
[8]

If s= 1 , then rank(R)∈ {0,1} ; in particular, αJ =β J = 0⇐ ⇒rank(R) = 0 , otherwise rank(R) = 1, hence rank(M) =u−1

work page
[9]

Proof of Theorem F .12.Let U= [u 1,

Ifs≥2, then: •ifα J andβ J are linearly independent,rank(R) = 2andrank(M) =u; •if they are collinear but not both zero,rank(R) = 1andrank(M) =u−1; •ifα J =β J = 0,rank(R) = 0andrank(M) =u−2. Proof of Theorem F .12.Let U= [u 1, . . . , un] be the orthogonal eigenbasis of L, and define Mi = U−i diag(u1(i), . . . , un(i)) as above. The ℓ-th column of Mi equa...

work page 2020

[1] [1]

URL https://openreview.net/forum? id=SJU4ayYgl. Liu, F. and Wang, Q. Asymmetric learning for spectral graph neural networks. InProceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 18798–18806, 2025. Luan, S., Hua, C., Xu, M., Lu, Q., Zhu, J., Chang, X.-W., Fu, J., Leskovec, J., and Precup, D. When do graph neural networks help wit...

work page 2025

[2] [2]

propose homomorphism expressivity as a finer quantitative hierarchy for comparing substructure-counting capabilities. In contrast, theoretical understanding of spectral GNN expressivity is relatively limited: Wang & Zhang (2022) establish universality results for spectral filtering on node signals, while also relating spectral models to 1-WL limitations. ...

work page 2022

[3] [3]

, αR ∈R n andβ 1,

Ifrank(A) =R, there exist vectorsα 1, . . . , αR ∈R n andβ 1, . . . , βR ∈R n such that A= RX i=1 αiβ⊤ i . 15 Full Spectrum Graph Neural Network: Expressive and Scalable

work page

[4] [4]

no multiple eigenvalues

Conversely, ifAcan be written as A= RX i=1 αiβ⊤ i , thenrank(A)≤R. In particular, the minimal number of rank-one matrices{α iβ⊤ i }required in such a decomposition equalsrank(A). Proof. (1) Since rank(A) =R , the column space of A has dimension R. Choose a basis c1, . . . , cR ∈R n for the column space and set C= [c 1 · · ·c R ]∈R n×R. Then there exists D...

work page 2022

[5] [5]

for every u′ ∈N G(u), one child whose attached subtree is L-UNR(k−1) G (u′, v), with the edge from the root to this child labeled by1

work page

[6] [6]

for every v′ ∈N G(v), one child whose attached subtree is L-UNR(k−1) G (u, v′), with the edge from the root to this child labeled by2. Two such trees are said to be isomorphic if there exists a bijection between their vertex sets that preserves: (i) the root, (ii) the parent–child relation, (iii) the vertex labels, and (iv) the directed edge labels in{1,2...

work page 2020

[7] [7]

35 Full Spectrum Graph Neural Network: Expressive and Scalable

Ifs= 0, thenrank(R) = 0andrank(M) =u−2. 35 Full Spectrum Graph Neural Network: Expressive and Scalable

work page

[8] [8]

If s= 1 , then rank(R)∈ {0,1} ; in particular, αJ =β J = 0⇐ ⇒rank(R) = 0 , otherwise rank(R) = 1, hence rank(M) =u−1

work page

[9] [9]

Proof of Theorem F .12.Let U= [u 1,

Ifs≥2, then: •ifα J andβ J are linearly independent,rank(R) = 2andrank(M) =u; •if they are collinear but not both zero,rank(R) = 1andrank(M) =u−1; •ifα J =β J = 0,rank(R) = 0andrank(M) =u−2. Proof of Theorem F .12.Let U= [u 1, . . . , un] be the orthogonal eigenbasis of L, and define Mi = U−i diag(u1(i), . . . , un(i)) as above. The ℓ-th column of Mi equa...

work page 2020