acceptodds
Under review as a conference paper at ICLR 2027

ChebyGNN: Linear-Time Spectral 2-WL Expressivity via Relational Chebyshev Fingerprints

Abstract

Isotropic message-passing Graph Neural Networks (MPNNs) are fundamentally bounded by the 1-Weisfeiler-Leman (1-WL) graph isomorphism test, rendering them blind to spatial symmetries and co-spectral regular topologies. While higher-order (k-WL) and equivariant subgraph architectures break this barrier, they inherit prohibitive polynomial O(N^(k+1)) time or combinatorial memory overheads, severely restricting their scalability to large-scale relational structures. In this work, we introduce ChebyGNN, a scalable and provably expressive framework driven by Relational Chebyshev Spectral Fingerprints (χ-SF). By extending spectral approximation theory from node-level local loop-counting to joint pairwise relational tracking, we extract multi-scale spectral diffusion traces without executing explicit matrix diagonalizations or dense tensor expansions. We theoretically prove that by restricting polynomial matrix evaluations strictly to adjacent vertex pairs, χ-SF captures macro-topological cycle configurations and achieves an expressivity equivalent to the 2-WL test, while preserving a strict linear-time complexity O(|E| * K) and a sparse memory footprint. Furthermore, we bridge this algebraic formulation with natural intelligence, mapping our three-term recurrence directly onto biological cortical loop dynamics with delayed feedback inhibition. Empirically, ChebyGNN achieves a complete separation score of 100% (212/212 distinguished graph pairs) on the BREC expressivity benchmark, bypassing the Out-of-Memory (OOM) crashes typical of higher-order baselines. Furthermore, experiments on molecular (ZINC-12k Test MAE 0.1057 ± 0.0029 with 182k parameters) and web-scale graphs (ogbn-arxiv Test Accuracy 71.80% ± 0.14% at 1.8 GB VRAM) confirm that ChebyGNN establishes a new Pareto-efficiency frontier, combining higher-order 2-WL expressivity with web-scale computational efficiency.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Weisfeiler-Leman Expressivity, Graph Neural Networks, Spectral Graph Theory, Chebyshev Polynomials, Relational Learning

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_zbh8OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes ChebyGNN, which augments a GNN with node-level and edge-level structural fingerprints obtained from Chebyshev polynomials of the graph operator L~\widetilde L. In particular, the method uses the diagonal entries Tk(L~)iiT_k(\widetilde L){ii} to construct fi(1-WL)f_i^{(1\text{-WL})} and the entries Tk(L~)ijT_k(\widetilde L){ij} on edges to construct fij(2-WL)f_{ij}^{(2\text{-WL})}. For large graphs, the authors use a stochastic Hutchinson approximation to avoid explicitly constructing dense matrices. The method is evaluated on BREC, ZINC-12k, and ogbn-arxiv.

Critical strengths
  1. The paper combines node fingerprints fi(1-WL)f_i^{(1\text{-WL})} and edge fingerprints fij(2-WL)f_{ij}^{(2\text{-WL})} with a standard GNN architecture. The stochastic computation of Tk(L~)iiT_k(\widetilde L){ii} and Tk(L~)ijT_k(\widetilde L){ij} is also useful in principle for large sparse graphs.
Critical weaknesses
  1. The main theoretical claims are not sufficiently supported, and some derivations appear incorrect. The most important concern is Theorem 5.1. The paper claims that the edge fingerprints fij(2-WL)f_{ij}^{(2\text{-WL})} can distinguish strongly regular graphs with the same parameters, including the Shrikhande graph and the 4×44\times4 Rook graph. However, for a dd-regular graph, the paper's operator satisfies L~=−A/d\widetilde L=-A/d. For two strongly regular graphs with the same parameters (n,d,λ,μ)(n,d,\lambda,\mu), the diagonal entries and the entries on adjacent pairs of any polynomial in AA, and therefore of Tk(L~)T_k(\widetilde L), are determined by these parameters. Thus, it is unclear how the fingerprints fi(1-WL)f_i^{(1\text{-WL})} and fij(2-WL)f_{ij}^{(2\text{-WL})} can distinguish the Shrikhande/Rook pair as claimed. This also seems inconsistent with the paper's statement that ChebyGNN is bounded by 2-FWL/3-WL, since the same Shrikhande/Rook pair is known to be indistinguishable by 3-WL.

There are other theoretical issues. In Lemma 1, the derivation effectively uses (D−1/2AD−1/2)m=D−1/2AmD−1/2(D^{-1/2}AD^{-1/2})^m=D^{-1/2}A^mD^{-1/2}. This is not valid in general because intermediate degree factors appear. Then, the derivation of Eq. (18) is not correct as written.

In addition, the abstract claims that ChebyGNN is equivalent to 2-WL, but Theorem 5.1 only attempts to show that it is stronger than 1-WL. The proof of the Hutchinson concentration bound also appears incomplete as written.

  1. The experiments do not fully support the main expressivity and complexity claims. BREC contains 400 graph pairs, but Table 1 reports results on only 212 pairs and describes 212/212212/212 as 100 percent separation. The paper does not clearly explain which 212 pairs were used or why the remaining pairs were excluded. The description of the BREC categories is also inconsistent across the paper.

Since the main theoretical contribution is described in terms of the WL hierarchy, direct 2-WL and 3-WL results on BREC would be important for evaluating the claimed expressivity, but these results are not reported. There is also a complexity issue. In the exact BREC mode, the paper computes Tk(L~)=2L~Tk−1(L~)−Tk−2(L~)T_k(\widetilde L)=2\widetilde L T_{k-1}(\widetilde L)-T_{k-2}(\widetilde L) using full matrix quantities, and the paper itself notes O(N2)O(N^2) space for this mode. However, Table 1 reports O(∣E∣K)O(|E|K) complexity for the BREC result. The O(SK∣E∣)O(SK|E|) complexity instead applies to the stochastic Hutchinson mode.

Questions for authors

Please address weaknesses

1 comment
AuthorsOpenReview ↗

Response to Reviewer zbh8: Mathematical Proofs, 3-WL Bounds, and BREC Audit

Dear Reviewer zbh8,

Thank you for your exceptionally detailed mathematical audit. Your remarks allowed us to identify and resolve critical gaps in our proofs and empirical reporting specially the Lemma 1 and the Theorem 5.1 :

  1. Strongly Regular Graphs & 3-WL Upper Bound (Theorem 5.1): You are entirely correct that for matching SRGs (such as Shrikhande vs. 4x4 Rook's graph), any matrix polynomial in the adjacency operator yields identical entries on all diagonal and adjacent pairs. We have removed this claim from Theorem 5.1, repositioned SRGs as our strict theoretical upper bound (3-WL / 2-FWL), and proved 1-WL separation using 1-WL-indistinguishable regular pairs with distinct non-local walk topologies (Decagram vs. 2-Pentagram, i.e., C_10 vs. C_5 \sqcup C_5).

  2. Terminology Alignment (2-WL vs. 2-FWL / 3-WL): We replaced the ambiguous "2-WL" notation throughout the Title, Abstract, and Methodology with "3-WL (2-FWL) bounded expressivity" to align with standard graph isomorphism hierarchy definitions.

  3. Generalization of Lemma 1 to Non-Regular Graphs: We revised Appendix A to remove the implicit regularity cancellation. The updated proof explicitly tracks intermediate inverse degree matrices, proving that (\tilde{L}^m)_{ij} evaluates degree-discounted walk densities across arbitrary non-regular graphs, with d-regular graphs recovered as a special case.

  4. Complete Bernstein Concentration Bound (Theorem 5.2): In Appendix C, we replaced the incomplete Hoeffding step with Bernstein's inequality, explicitly bounding single-probe realizations via the maximum row-sum norm B = max_i ||T_k(\tilde{L})_{i,\cdot}||_1 alongside unit spectral variance, yielding the sample bound S >= 2(1 + 2B/3)log(2/\delta)/\epsilon^2.

  5. BREC Pair Counts, 3-WL Baselines & Exact Complexity: We normalized Table 2 across all 400 BREC graph pairs, fixed the CFI category name, and included non-GNN WL oracles (1-WL at 0.00%, SPD-WL at 20.80%, and 3-WL at 67.50%) alongside our local PPGN reproduction (57.68%). Under BREC's Reliable Paired Comparisons (RPC) protocol, ChebyGNN separates 212.2 +/- 0.63 / 400 pairs (53.05%). Finally, we updated Table 2 to explicitly state the O(N^3 * K) time complexity for Exact Mode on BREC, distinguishing it from our O(|E| * S * K) stochastic Hutchinson mode used on ogbn-arxiv.

Reviewer_hL1tOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes ChebyGNN, which advances message passing with diagonal and edge entries of Chebyshev polynomials of the normalized adjacency operator. These fingerprints encode weighted return walks and transitions between adjacent vertices. The paper provides an exact matrix-based computation for small graphs and a stochastic probing approximation for larger graphs.

Critical strengths

None

Critical weaknesses
  1. There are many placeholder words in this paper, resulting in a lack of information and clear hallmarks of AI generation. For example, two paragraphs in the introduction are repeated, and the manuscript abuses bullet points. All these issues make this paper hard to follow.

  2. The main expressivity claim is false. Theorem 5.1 claims that ChebyGNN can distinguish the Shrikhande and rook graphs. However, these graphs have the same node and edge fingerprints at every polynomial order. With uniform input features, the proposed model cannot distinguish them.

  3. The BREC results are unclear. The paper reports perfect separation on 212 pairs, but standard BREC and the supplied evaluator use 400 pairs. The selected pairs and reasons for excluding others are not given. The reported nonzero separation by a 1-WL kernel also needs explanation.

  4. There are too many errors in the references of this paper, and I only list a part of them.

    • Non-existent literature:

      • Understanding and extending subgraph filtering for graph neural networks
      • Two’s company, three’s a crowd: A biological learning rule for generalized hebbian plasticity in network motifs
      • Towards expressiveness benchmark for graph neural networks
    • Incorrect author information:

      • Deyu=Deyu Bo and Xiao Wang and Chuan Shi and Huawei Shen Bo
      • Eli Chien Chien, Wei-Lin Peng, Li Pan, and Olgica Milenkovic
      • ...
Questions for authors

See weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer hL1t: Presentation Cleanup, BREC Normalization, and Bibliography Audit

Dear Reviewer hL1t,

We sincerely thank you for catching the critical presentation and bibliographic defects in our initial submission. We have thoroughly revised the manuscript and addressed every point:

  1. Presentation, Duplication Cleanup & Architectural Summary: We removed the duplicated paragraphs in the Introduction, eliminated redundant bullet lists in favor of continuous academic prose, standardized all mathematical notations, and added a unified architectural comparison table (Table 1) in Section 2 to clarify our positioning relative to spatial, spectral, RWPE/RWSE, and higher-order GNNs.

  2. Expressivity Bound (Theorem 5.1): We removed the incorrect claim regarding the separation of the Shrikhande and 4x4 Rook's graphs. Theorem 5.1 now strictly proves separation on 1-WL-indistinguishable regular pairs (Decagram vs. 2-Pentagram, i.e., C_{10} vs. C_5 \sqcup C_5) while explicitly establishing 3-WL (2-FWL) as our theoretical upper bound.

  3. BREC Normalization & 1-WL Baseline Correction: We corrected the erroneous non-zero 1-WL baseline and normalized all results in Table 2 over the complete 400-pair BREC dataset. ChebyGNN achieves 53.05% (212.2 \pm 0.63 / 400), closely tracking dense higher-order architectures like PPGN (58.20% literature; 57.68% local reproduction) while outperforming subgraph models such as NestedGNN (41.50%) and DropGNN (44.20%).

  4. Complete Bibliography Overhaul & Resolution of Non-Existent Entries (entry by entry): We manually audited our entire .bib file against DBLP and official conference proceedings. Specifically:

  • We completely purged the non-existent/hallucinated placeholder titles noted in your review (such as the corrupted merge strings for subgraph filtering and biological Hebbian rules).
  • We properly restored the correct metadata for the BREC benchmark (Wang & Zhang), Specformer (Deyu Bo, Xiao Wang, Chuan Shi, Huawei Shen), and GPR-GNN (Eli Chien, Wei-Lin Peng, Pan Li, Olgica Milenkovic), fixing all author string malformations and duplicate tags.
Reviewer_geziOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper introduces ChebyGNN. The paper claims strong expressivity with low computational cost.

Critical strengths

None.

Critical weaknesses

The reference issues raised in the discussion and acknowledged by the AC raise serious concerns about the reliability of the paper’s scholarly grounding. These issues need to be resolved before the contribution can be properly assessed. I do not support acceptance in its current form.

Questions for authors

None.

1 comment
AuthorsOpenReview ↗

Response to Reviewer gezi: Complete Bibliographic Verification and Baseline Audit

Dear Reviewer gezi,

We deeply apologize for the bibliographic errors in our initial draft that raised concerns regarding scholarly grounding. As detailed in our general response to the Area Chair, these were unintentional formatting artifacts caused by an automated reference manager conflict during final compilation.

We have manually verified every single entry in our bibliography against DBLP and official conference proceedings, completely purging all non-existent placeholder titles and fixing all corrupted author strings. Furthermore, we audited all reported baseline numbers across Tables 2, 3, and 4 against their original publications and proactively added a dedicated comparison against concurrent RWPE/RWSE encodings along with a unified architectural summary table (Table 1) in Section 2. We respectfully invite you to re-evaluate our technical contributions based on this fully verified manuscript.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response & Summary of Manuscript Revisions

Dear Area Chair and Reviewers,

We sincerely thank you for your time, rigorous evaluation, and constructive feedback. As this represents our first submission to ICLR, your mathematical and methodological insights have been invaluable in helping us elevate the rigor of this manuscript.

  1. Complete Bibliographic Audit, Presentation Polish & Proactive RWPE/RWSE Comparison: We apologize unreservedly for the reference errors and text duplications in our initial submission. As disclosed in our submission form, we used a generative AI assistant solely to assist with LaTeX formatting and boilerplate code structure around public evaluation repositories. Due to an oversight under deadline constraints, placeholder titles and corrupted BibTeX metadata bypassed our final check. We take full, personal responsibility for this oversight.
  • We have manually audited every single entry in our .bib file against DBLP and official conference proceedings, completely purging all non-existent placeholder entries and restoring corrupted metadata (including BREC, Specformer, and GPR-GNN).
  • We removed the duplicated paragraphs in the Introduction, replaced fragmented bullet lists with formal academic prose, and standardized all matrix notations.
  • In the spirit of full academic transparency and continuous improvement, we also proactively added a dedicated comparison in Section 2 contrasting ChebyGNN with concurrent Random Walk Positional/Structural Encodings (RWPE/RWSE; e.g., Dwivedi et al., TPAMI 2022) , alongside a unified architectural summary table (Table 1) positioning our expressivity bound, feature decoupling, and linear complexity against existing GNN paradigms.
  1. Mathematical Generalization & Expressivity Bounds (Reviewers zbh8 and hL1t ):
  • Generalization of Lemma 1: We removed the implicit d-regular graph assumption and derived the exact degree-discounted walk expansion for general non-regular graphs, explicitly tracking intermediate inverse degree factors.
  • Correction of Theorem 5.1 (3-WL / 2-FWL Upper Bound): We removed the incorrect claim regarding Strongly Regular Graphs (Shrikhande vs. 4x4 Rook's graph). We now accurately position SRGs as the strict theoretical upper bound of our framework (bounded by 3-WL / 2-FWL) and prove 1-WL separation using valid 1-WL-indistinguishable regular pairs (Decagram vs. 2-Pentagram, i.e., C_{10} vs. C_5 \sqcup C_5).
  • Rigorous Hutchinson Concentration (Theorem 5.2): We replaced the incomplete Hoeffding argument with a complete derivation via Bernstein's inequality, bounding the estimator via the maximum row-sum norm B and unit spectral variance.
  1. Empirical Clarification, Baseline Audit, Complexity & Open-Source Reproducibility:
  • BREC Normalization: We normalized Table 2 across all 400 graph pairs of the complete BREC benchmark and corrected the CFI category name. Across 10 seeds, ChebyGNN separates 212.2 \pm 0.63 / 400 pairs (53.05%), matching dense higher-order architectures (PPGN: 58.20% literature, 57.68% local reproduction) and aligning directly with our 3-WL theoretical boundary.
  • Mode Complexities & Hardware: We clarified the distinction between our dense Exact Mode (\mathcal{O}(N^3 \cdot K), used on small diagnostic graphs in BREC and ZINC) and our linear-time Stochastic Hutchinson Mode (\mathcal{O}(|\mathcal{E}| \cdot S \cdot K), used on ogbn-arxiv on 16 GB Kaggle GPUs at 1.8 GB peak VRAM).
  • Literature Baselines Audit: We audited and updated Tables 2, 3, and 4 against original peer-reviewed publications to ensure 100% reporting accuracy.
  • Open-Source Reproducibility: To ensure complete reproducibility of our reported empirical results across BREC, ZINC-12k, and ogbn-arxiv, we have fully documented and shared our modular codebase alongside explicit execution instructions in our repository.

We have uploaded the revised PDF and invite the Area Chair and Reviewers to assess our updated manuscript and detailed individual responses in each reviewer's thread.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.