- 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 . In particular, the method uses the diagonal entries to construct and the entries on edges to construct . 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
- The paper combines node fingerprints and edge fingerprints with a standard GNN architecture. The stochastic computation of and is also useful in principle for large sparse graphs.
Critical weaknesses
- 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 can distinguish strongly regular graphs with the same parameters, including the Shrikhande graph and the Rook graph. However, for a -regular graph, the paper's operator satisfies . For two strongly regular graphs with the same parameters , the diagonal entries and the entries on adjacent pairs of any polynomial in , and therefore of , are determined by these parameters. Thus, it is unclear how the fingerprints and 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 . 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.
- 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 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 using full matrix quantities, and the paper itself notes space for this mode. However, Table 1 reports complexity for the BREC result. The complexity instead applies to the stochastic Hutchinson mode.
Questions for authors
Please address weaknesses
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 :
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).
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.
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.
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.
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.