{"id":"efc412bb-b189-410e-aa90-2542978e55b1","arxiv_id":"2411.17296","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"GrokFormer parameterizes graph spectral filters as Fourier series over higher-order Laplacian spectra, achieving state-of-the-art accuracy on many node and graph classification tasks.","lead":"This paper introduces GrokFormer, a graph transformer that learns spectral filters as a Fourier series over powers of the graph Laplacian eigenvalues, claiming better expressiveness than polynomial or attention-based spectral filters. It reports accuracy gains on several node and graph classification benchmarks, with code on GitHub.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The special-case expressiveness proof is the load-bearing claim, and it is not derived: Appendix C's Eq. (13) simply asserts that Eq. (9) reduces to a polynomial, which is not exact for finite M. Propositions 4.2 and 4.3 therefore do not establish that existing filters are contained in GrokFormer.","rationale":"The reader's weakest_assumption identifies exactly the same issue: the reduction of the GrokFormer filter to a polynomial in Appendix C is asserted, not derived, and fails for finite M. This is the most load-bearing concern because the paper's headline theoretical contribution is the claim that GrokFormer is strictly more expressive than prior polynomial and Specformer filters, stated explicitly as Propositions 4.2 and 4.3 and in the sentence 'existing advanced filters are special cases of our GrokFormer filter.' If this containment proof is invalid, the theoretical argument for 'better expressiveness' collapses, even though the empirical filter-fitting results in Table 4 and the real-world accuracy improvements may still stand. The issue is an internal inconsistency with basic approximation theory—finite trigonometric polynomials are not polynomials—rather than a disagreement with the surrounding literature. Proposition 4.4's universal approximation claim is also not differentiating, since polynomial filters enjoy similar approximation properties; the distinguishing claim is containment. The reader's proposed conditional acceptance, asking that the theoretical claims be corrected, is the appropriate disposition. I did not find a more severe concern that would justify rejection: the architecture is clearly described, the code is released, and the empirical study is broad, even if some headline numbers (e.g., Penn94, several within-std gaps) are overstated. No ad hominem is intended; the critique targets the proof, not the authors. The proposed numerical test would settle whether the containment claim can be rescued in any exact finite-M sense, and if not, whether the paper should restate its contribution as approximate expressiveness.","tokens_in":29289,"tokens_out":4629,"duration_ms":46694,"concrete_test":"Directly test the containment claim numerically. For K = 1 and a representative finite M (e.g., M = 16, as in the paper's grid), solve the minimax problem min_{a_m,b_m} max_{λ∈[0,2]} |λ - Σ_{m=0}^M (cos(mλ)a_m + sin(mλ)b_m)| using a dense grid or a Remez-style exchange. If the minimum uniform error is strictly positive, Proposition 4.2's exact special-case claim is false; report the residual. Repeat with target λ² and with a Specformer-style first-order term a₀λ + Σ_i sin(m_i λ)a_i + cos(m_i λ)b_i to test Proposition 4.3. A nonzero residual means the Appendix C proofs must be revised to 'approximate containment' or 'containment in the M→∞ limit,' which weakens the theoretical expressiveness claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central theoretical claim is that existing advanced filters are special cases of the GrokFormer filter, giving it 'better universality and flexibility' (Section 4.1, Proposition 4.1). This claim rests on Propositions 4.2 and 4.3, whose proofs in Appendix C are not valid as written. For Proposition 4.2, the proof 'eliminates the learnable nonlinear function' and writes h(λ) = Σ_k α_k λ^k (Eq. 13). But Eq. (9) is h(λ) = Σ_k α_k Σ_m (cos(mλ^k)a_km + sin(mλ^k)b_km). To show that polynomial filters are special cases, one must exhibit, for every polynomial Σα_k λ^k, finite-M coefficients a_km,b_km satisfying Eq. (9) exactly for all λ ∈ [0,2]. A finite trigonometric series cannot exactly equal a monomial on an interval; e.g., λ has a nonzero projection onto the orthogonal complement of the span of {cos(mλ), sin(mλ)}. Thus Eq. (13) is a redefinition, not a consequence of Eq. (9). Proposition 4.3 has the same defect: Eq. (19) asserts a₀λ = R sin(λ + φ), which is not an identity on [0,2] (the left side is linear, the right side is bounded and nonlinear). Moreover, the proof reduces Specformer to the identity-attention case, not the full Specformer filter. Consequently, the 'special case' containment is unproven, and the theoretical superiority claim does not follow. The synthetic fitting results in Table 4 provide empirical evidence of strong expressiveness on six specific filter patterns, but they do not substitute for the containment proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes GrokFormer, a graph Transformer that augments multi-head self-attention with a spectral convolution module whose filter is parameterized as a learnable Fourier series over powers of the Laplacian eigenvalues. The filter is claimed to be adaptive in both spectral order and graph spectrum, and the paper argues theoretically that polynomial filters and Specformer's filter are special cases, while empirically reporting strong results on 11 node-classification datasets, 5 graph-classification datasets, synthetic filter-fitting tasks, ablations, and efficiency measurements. The Appendix contains the proofs of the four propositions, additional experiments, and hyperparameter details.","tokens_in":29693,"tokens_out":4154,"duration_ms":41435,"significance":"If the expressiveness claims were rigorously established, the paper would offer a useful unifying perspective on spectral graph filters and a practical architecture that combines spatial and spectral Transformer branches. The empirical study is broad and carefully structured: 11 node and 5 graph datasets, synthetic filter fitting with a low-comb target, ablations isolating the self-attention and Graph Fourier KAN components, and wall-clock/memory comparisons against Specformer and PolyFormer. The code is released. The synthetic fitting results in Table 4 are particularly informative and demonstrate that the proposed parameterization can fit complex frequency responses such as comb and low-comb filters better than the compared baselines. However, the theoretical containment arguments in Appendix C are not valid as written, and the empirical claims are overstated in places; the core contribution is nevertheless defensible after a substantive revision.","major_comments":[{"comment":"The proof of Proposition 4.2 asserts, in Eq. (13), that the GrokFormer filter h(λ) = Σ_k α_k Σ_m (cos(mλ^k)a_km + sin(mλ^k)b_km) simplifies to the polynomial h(λ) = Σ_k α_k λ^k by 'eliminating the learnable nonlinear function over the spectrum.' This reduction is not derived and is not a consequence of Eq. (9). A finite trigonometric series cannot equal a monomial exactly on an interval; for example, the function λ has a nonzero projection onto the orthogonal complement of span{cos(mλ), sin(mλ)}_{m=0}^M for any finite M. Therefore Proposition 4.2 does not establish that polynomial filters are special cases of the GrokFormer filter. The claim should be weakened to an approximation statement with an explicit density argument and a bound involving M, or the proof must show an exact coefficient assignment that the current family does not admit.","section":"Appendix C, Proposition 4.2"},{"comment":"The proof of Proposition 4.3 reduces Specformer to the case where the self-attention matrix is the identity, which is not the Specformer filter used in practice, and then relies on Eq. (19), a₀λ = R sin(λ + φ), which is not an identity on [0,2] since the left-hand side is linear while the right-hand side is bounded and nonlinear. Consequently, the statement that 'the graph filter in Specformer is a simplified variant of our graph filter' is unproven. At best the argument suggests a loose approximation in a restricted setting. The proposition and the surrounding text in Section 4.1 should be revised to state an approximation relationship, and the proof must either handle the actual Specformer attention mechanism or explicitly restrict the claim.","section":"Appendix C, Proposition 4.3"},{"comment":"The proof of Proposition 4.4 invokes the uniform convergence theorem for Fourier series to conclude that the GrokFormer filter can approximate any continuous function in [0,2]. This does not follow from the cited theorem. First, for K > 1 the family contains terms cos(mλ^k) and sin(mλ^k), which are not standard Fourier series terms, so uniform convergence of ordinary trigonometric series does not directly apply. Second, the parameterization uses finite M and finite K, giving a finite-dimensional function class, which cannot contain all continuous functions or approximate every continuous function to arbitrary accuracy unless M and K are allowed to grow. The proof as written only states that some Fourier series exists; it does not show that the specific family in Eq. (9) has the claimed uniform approximation property. A correct argument should specify the function class (e.g., K = 1 with M → ∞ and Stone-Weierstrass) and state the approximation up to ε, not exact containment.","section":"Section 4.1, Proposition 4.4 and Appendix C"},{"comment":"The text states that GrokFormer 'outperforms state-of-the-art baselines in both homophilic and heterophilic datasets,' but Table 2 shows that on Penn94, Specformer achieves 84.32±0.32 while GrokFormer achieves 83.59±0.26, so the claim is not supported by the reported results. Similarly, the Appendix B.4 results show that GrokFormer underperforms GRIT and GraphGPS on ZINC, CIFAR10, and Peptides-func. The empirical claims should be qualified to specify the datasets and settings in which GrokFormer is superior, and the main text should not claim universal superiority over all compared methods.","section":"Section 5.1, Table 2"}],"minor_comments":[{"comment":"The abstract says '10 real-world node classification datasets' while the contributions and experiments report 11; please correct the inconsistency.","section":"Abstract and Contributions"},{"comment":"The caption contains a typo: 'GorkFormer' should be 'GrokFormer.'","section":"Figure 1 caption"},{"comment":"The coefficients are written as am and bm in Eq. (6) but as akm and bkm in Eq. (9); please clarify the correspondence between the per-order basis in Eq. (6) and the full filter in Eq. (9).","section":"Notation in Eqs. (6) and (9)"},{"comment":"The text contains the typo 'comepting models' and should read 'competing models.'","section":"Section 5.2"},{"comment":"The section title and text refer to 'GrokFomer' once; please fix the spelling.","section":"Appendix B.4"}],"recommendation":"major_revision","confidential_remarks":"The paper's empirical contribution is substantial and the code release is a plus, but the theoretical expressiveness argument is the stated basis for the central 'better universality and flexibility' claim, and that argument is not currently valid. The good news is that the issue is local to Appendix C and the wording of Section 4.1; a corrected approximation-theoretic statement plus qualified empirical claims should be achievable within a revision. I would not recommend rejection, but the current version should not be accepted without these changes."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is an empirically solid graph transformer paper with a genuinely new filter parameterization, but the theoretical \"special cases\" claims do not hold up as written. The experiments are the contribution; the proofs in Appendix C are not.\n\nWhat's new: the filter h(λ)=Σ_k α_k Σ_m (cos(mλ^k)a_km + sin(mλ^k)b_km) — a finite Fourier series in λ^k with learnable order weights — inside a transformer with an efficient attention module. That combination is new relative to Specformer, FeTA, and PolyFormer. The paper reports broad node classification results across 11 datasets, with clear wins on heterophilic graphs (Squirrel, Texas, Chameleon) while staying competitive on homophilic ones, plus graph classification and efficiency numbers. Code is public. The synthetic filter-fitting experiment (Table 4) is a nice sanity check: GrokFormer fits comb and low-comb filters with SSE an order of magnitude lower than BernNet and Specformer. That is real evidence that the parameterization is expressive.\n\nSoft spots. The theoretical section overreaches. Proposition 4.2's proof in Appendix C simply asserts Eq. (13) (h(λ)=Σα_k λ^k) after \"eliminating the learnable nonlinear function.\" That is not a consequence of Eq. (9); a finite trigonometric series in cos(mλ^k) and sin(mλ^k) cannot exactly equal a monomial on an interval. Proposition 4.3 similarly reduces Specformer to an identity-attention case and uses the approximation a0λ ≈ R sin(λ+φ), which is not exact. So the claim that GrokFormer contains polynomial and Specformer filters is unproven. The synthetic results give empirical support for expressiveness, but not the containment theorem. Proposition 4.4 (universal approximation of continuous functions) is actually true — trig polynomials are dense in C[0,2] via Stone-Weierstrass — but the proof cites Fourier series uniform convergence without addressing periodicity, so it is misstated. Minor things: the abstract says 10 real-world node classification datasets while Table 2 has 11; the Penn94 result (83.59 vs Specformer's 84.32) undercuts the blanket \"outperforms state-of-the-art\" phrasing; and the synthetic hyperparameter search for GrokFormer is wider than for baselines, so the fitting table is suggestive, not a controlled comparison.\n\nWho this is for: anyone building spectral graph filters or graph transformers for heterophilic graphs. The filter is simple, competitive, and public; it deserves to be a baseline. The theory needs to be corrected or cut. I would send it to review with a request to rewrite the theoretical claims and fix the abstract. A serious referee can do that without throwing out the empirical contribution.","headline":"A Fourier-series spectral filter for graph transformers that wins on heterophilic benchmarks, but the paper's expressiveness proofs overclaim: the special-case containment is asserted, not derived.","tokens_in":30204,"tokens_out":3230,"would_cite":true,"duration_ms":29204,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A learnable Fourier-series filter over Laplacian eigenvalue powers is claimed to make polynomial and Specformer graph filters special cases.","keywords":["graph transformers","spectral graph filters","Fourier series","Kolmogorov-Arnold networks","heterophilic graphs","frequency-adaptive filtering","node classification","graph classification"],"falsifier":"Fit a polynomial target such as $h(\\lambda)=\\lambda^3$ using GrokFormer with small finite $M$ (for example $M=1,2,4$) and measure the residual; if the filter cannot reproduce the polynomial to numerical precision as $M$ grows, the containment claim is false. A complementary check is to constrain GrokFormer to $K=1$ and verify that its learned response matches Specformer's fitted filter on the same eigenvalues; any mismatch would falsify the special-case claim.","tokens_in":29107,"feed_emoji":"📡","tokens_out":9910,"duration_ms":83651,"temperature":0.7,"pith_summary":"Self-attention, the core of graph Transformers, behaves as a low-pass filter and therefore suppresses the high-frequency node-difference signals that matter on heterophilic graphs. GrokFormer addresses this by adding a spectral convolution whose frequency response is a learnable Fourier series over powers of the Laplacian eigenvalues, with learnable coefficients for both the spectral order and the spectrum. The paper claims that this filter contains existing polynomial filters and Specformer's first-order learnable filter as special cases, which would make it strictly more expressive than prior spectral graph filters. If that is right, one model can fit low-pass, high-pass, band, comb, and low-comb filters without hand-designing the frequency response, and the reported node and graph classification gains follow from that flexibility.","feed_headline":"Fourier filter out-fits polynomial and Specformer graph filters","feed_subtitle":"A learnable spectral filter adapts graph spectrum and order, beating 16 baselines on node and graph classification.","key_machinery":"The load-bearing object is the Graph Fourier KAN filter, a learnable spectral response written as a truncated Fourier series in the powers $\\lambda^k$ of each Laplacian eigenvalue. Fourier coefficients $a_{km}$ and $b_{km}$ shape the spectrum at each order, and order coefficients $\\alpha_k$ weight how much each order contributes; the result is applied as $U\\mathrm{diag}(h(\\lambda))U^\\top X$ and added to the output of efficient self-attention inside a Transformer layer. The Fourier representation does triple duty: sine and cosine orthogonality gives stable coefficient learning, Fourier approximation theory supplies a convergence guarantee for continuous filters, and the sum over orders lets the filter attend to all eigenvalues across the first through $K$-th spectral planes rather than only to Specformer's first-order spectrum.","core_discovery":"The paper's central claim is that a graph filter built as a Fourier-series expansion over the order-$K$ spectrum of the graph Laplacian is more expressive than all prior learnable spectral filters. The filter is $$h(\\$\\lambda$)=\\sum_{k=1}^{K}\\alpha_k\\sum_{m=0}^{M}\\left(\\cos(m\\$\\lambda$^k)a_{km}+\\sin(m\\$\\lambda$^k)b_{km}\\right),$$ applied to node features through $U\\mathrm{diag}(h(\\lambda))U^\\top X$ and combined in parallel with efficient self-attention. The argument is that $\\alpha_k$ adapts the spectral order while $a_{km}$ and $b_{km}$ adapt the spectrum itself; that removing the learnable nonlinearity reduces the filter to $\\sum_k \\alpha_k \\lambda^k$ and therefore contains every polynomial filter; that at $K=1$ the same formula contains Specformer's first-order filter; and that the uniform convergence of Fourier series makes the filter able to approximate any continuous function on $[0,2]$ while the spectral convolution remains permutation-equivariant. The empirical counterpart is the synthetic filter-fitting study, where fixed polynomial bases saturate at large error on comb-like targets while the Fourier-series filter continues to shrink the error.","pith_inferences":["The paper does not discuss this, but the Graph Fourier KAN filter is transportable: the same $U\\mathrm{diag}(h(\\lambda))U^\\top$ convolution could replace the fixed polynomial filter in non-Transformer spectral GNNs, and the containment argument would carry over unchanged.","A consequence the authors leave implicit is that the learned order weights $\\alpha_k$ can double as a heterophily diagnostic; concentrated small-$k$ mass indicates a mostly low-pass task, while mass spreading to large $k$ signals a complex frequency response.","A concrete extension the authors do not explore is replacing the real sine/cosine basis with complex exponentials $e^{im\\lambda^k}$, which would extend the construction to directed or asymmetric graph operators with complex spectra, at the cost of re-proving the convergence and containment statements."],"forward_implications":["Any filter that a polynomial GNN or polynomial graph Transformer can express, including FeTA and PolyFormer, is reproducible by GrokFormer's filter, so those models cannot be strictly more expressive.","Specformer's spectrum-adaptive first-order filter is a special case, so adding higher-order Fourier terms extends spectral adaptivity beyond Specformer's first-order spectrum without its quadratic attention over eigenvalues.","On heterophilic graphs the same architecture can learn high-pass or comb-like responses, which matches the gains reported on Chameleon, Squirrel, Actor, and Texas.","The synthetic filter-fitting results imply that complex targets such as comb and low-comb filters, which fixed polynomial bases fail to fit, are learnable in practice and not merely representable in principle.","The model's flexibility is controlled by the order $K$ and the Fourier grid size $M$, and the order-adaptivity analysis shows the learned $\\alpha_k$ weights concentrate on small $k$ for homophilic graphs and spread to larger $k$ for heterophilic ones."],"supporting_citations":[{"why":"Specformer is the main rival; Proposition 4.3 claims its first-order learnable filter is a simplified variant of GrokFormer's filter.","marker":"(Bo et al., 2023)"},{"why":"BernNet is a fixed-basis polynomial filter that Proposition 4.2 folds into GrokFormer and that fails on low-comb targets in the fitting study.","marker":"(He et al., 2021)"},{"why":"PolyFormer is the polynomial-basis graph Transformer baseline that GrokFormer compares against and claims to subsume.","marker":"(Ma et al., 2024)"},{"why":"FeTA is the polynomial spectral Transformer whose low-pass limitation motivates needing a more flexible filter.","marker":"(Bastos et al., 2022)"},{"why":"KANs supply the learnable-activation design that GrokFormer re-parameterizes as a Fourier series.","marker":"(Liu et al., 2024)"},{"why":"Provides the graph Fourier transform and convolution theorem that define the spectral filter and its application.","marker":"(Shuman et al., 2013)"}],"fun_headline_variants":["GrokFormer: Fourier-series filter adapts spectrum and order","Adaptive Fourier filter beats polynomial and Specformer filters","GrokFormer's Fourier filter adapts graph spectrum and spectral order","Learnable Fourier-series spectral filter for graph transformers","GrokFormer: Fourier filter that learns spectrum and order"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claim that every polynomial filter is a special case assumes that the learnable nonlinearity in the Fourier-series filter can be eliminated to leave exactly $\\sum_k \\alpha_k \\lambda^k$; Appendix C asserts this equivalence rather than deriving it, and it is exact only with infinitely many Fourier terms.","fun_headline_variants_meta":{"raw":{"variants":["GrokFormer: Fourier-series filter adapts spectrum and order","Adaptive Fourier filter beats polynomial and Specformer filters","GrokFormer's Fourier filter adapts graph spectrum and spectral order","Learnable Fourier-series spectral filter for graph transformers","GrokFormer: Fourier filter that learns spectrum and order"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000644,"raw_usage":{"total_tokens":2990,"prompt_tokens":1004,"completion_tokens":1986,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":620,"completion_tokens_details":{"reasoning_tokens":1905}},"tokens_in":620,"tokens_out":1986,"duration_ms":13883,"temperature":1.0,"reasoning_tokens":1905,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:16:54.596772+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fit a polynomial target such as $h(\\lambda)=\\lambda^3$ using GrokFormer with small finite $M$ (for example $M=1,2,4$) and measure the residual; if the filter cannot reproduce the polynomial to numerical precision as $M$ grows, the containment claim is false. A complementary check is to constrain GrokFormer to $K=1$ and verify that its learned response matches Specformer's fitted filter on the same eigenvalues; any mismatch would falsify the special-case claim.","supporting_citations":[],"review_version":1}