{"id":"99bc1ee5-dd3a-4949-a8fa-b10022afc99f","arxiv_id":"2501.13456","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Swapping attentive GNN score mappings for a single-layer Kolmogorov-Arnold Network improves benchmark performance and, on a specially constructed input matrix, provably achieves zero maximum ranking error.","lead":"The paper replaces the learnable part of graph attention scoring functions with a Kolmogorov-Arnold Network (KAN), calls the result KAA, and reports consistent gains on node and graph learning benchmarks. It also introduces a ranking-based measure, Maximum Ranking Distance, to argue that KAN-based scoring is more expressive than linear or MLP scoring under tight parameter budgets.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 1's lower bound is derived through an invalid max/min exchange; the claimed MRD hierarchy, and with it the headline expressive-power advantage of KAA, is not established as written.","rationale":"The reader's conditional verdict already identifies the invalid max/min exchange in Appendix A.5 and the co-designed circulant/b-spline construction in Appendices A.4 and A.7; my stress-test confirms both. The max/min swap is the more fundamental internal defect: Proposition 1's lower bound is the foundation of the claimed ordering MRD(S_KAA) ≤ MRD(S_MLP) ≤ MRD(S_LT), and if that bound is not proven, the theoretical core of the paper does not establish that KAN scoring is more expressive than linear or MLP scoring under the stated parameter constraints. The co-design issue is equally important for the abstract's unqualified claim, because Proposition 3 only shows that a KAN with d^2 spline coefficients can realize arbitrary rankings on one specially structured alignment matrix, not on real node-pair representations. The empirical results are reported consistently and include useful comparisons, but the theoretical claim carries the headline and is not sound as written. Since the reader already recommends a conditional accept with a request to correct or re-scope the theory, my analysis does not change the verdict; it strengthens the reasons for that condition.","tokens_in":26928,"tokens_out":6490,"duration_ms":763608,"concrete_test":"Independently recompute Proposition 1 for the small case N=4, d=2 by exhaustive enumeration: enumerate all 24 target permutations π' of {1,2,3,4}, all linear scorers W ∈ R^2, and compute max_{π'} min_W Σ_j (W·P_j − π'^{−1}(j))^2 exactly, comparing the result with Eq. (14)'s lower bound √5. If the exact MRD is less than √5, Proposition 1 is false and Theorem 1 collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The single most load-bearing defect is in the proof of Proposition 1 (Appendix A.5). MRD is defined as max_{π'} min_{s'} sqrt(Σ_j (s'(P_j)−π'^{−1}(j))^2). In Eqs. (32)–(34), the proof moves the max over π' inside the min over s' and claims MRD ≥ min_{s'} sqrt(max_{π'} Σ_{i=1}^{N+1−d} (s'(P_i)−π'^{−1}(i))^2). The valid inequality for a max over one variable and a min over another is max min ≤ min max, so the displayed direction is unjustified and can fail on simple finite examples. Proposition 1's lower bound therefore has no valid derivation; Proposition 2's lower bound uses the same pattern, and Theorem 1 orders the MRD values using these bounds. Separately, even if the bound were repaired, Proposition 3's δ-result is obtained by taking P to be the first d columns of a circulant matrix with N=d^2 and placing B-spline knots at multiples of d, so every row activates exactly one of the d^2 coefficients; this makes the KAN a lookup table co-designed with P. The paper itself concedes in Appendix A.4 that the composition of P controls the analysis, with P=1 making all scoring functions identical. Thus the formal advantage is both unproven and, as stated, restricted to a contrived instance; the abstract's unqualified claim of nearly infinite expressive power for KAA is not supported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Kolmogorov-Arnold Attention (KAA), a drop-in replacement for the scoring function in attentive GNNs, and introduces Maximum Ranking Distance (MRD) as a metric for the expressive power of scoring functions. The authors claim a theoretical hierarchy MRD(S_KAA) ≤ MRD(S_MLP) ≤ MRD(S_LT) under limited parameters, and support this with extensive node- and graph-level experiments on five backbone architectures showing consistent performance gains, some exceeding 20%.","tokens_in":27169,"tokens_out":5000,"duration_ms":43078,"significance":"If the theoretical hierarchy were established, the work would provide a principled explanation for why KAN-based scoring can outperform linear and MLP scoring in attentive GNNs, and the empirical study is a useful contribution in its own right. The experiments are detailed, cover multiple backbones and tasks, and include comparisons against GATv2 and other KAN-GNN variants. The code is released. However, the central theoretical claim is not proven as written: the proof of Proposition 1 contains an invalid max/min exchange, and Proposition 3's near-zero MRD is achieved by a lookup-table construction tailored to a specific alignment matrix, so the advertised 'nearly infinite expressive power' is an overstatement.","major_comments":[{"comment":"The proof of Proposition 1 moves the max over π′ inside the min over s′ and claims MRD ≥ min_{s′} sqrt(max_{π′} Σ (s′(P_i)−π′^{-1}(i))^2). For a max over one variable and a min over another, the valid inequality is max min ≤ min max, so the displayed direction is unjustified and can fail on simple finite examples. This invalidates the lower bound in Eq. (14) for linear-transformation attention. Since Theorem 1 relies on this bound to compare MRD(S_MLP) with MRD(S_LT), the proposed hierarchy is not established as written.","section":"Appendix A.5, Eqs. (32)–(34)"},{"comment":"Even after the exchange, the evaluation of min_{a,b} max_{π′} Σ (a i + b − π′^{-1}(i))^2 is not carried out correctly: the authors first fix the 'uniformly distributed' worst-case permutation and then minimize over a and b, which computes something like max_{π′} min_{a,b} rather than the required min_{a,b} max_{π′}. The minimax value of this quantity is not derived, so the closed-form expression in Proposition 1 is unsupported regardless of the exchange issue.","section":"Appendix A.5, Eq. (35)–(38)"},{"comment":"The near-zero MRD for KAA is obtained by a construction where the alignment matrix P is the first d columns of an N×N circulant matrix with N=d^2 and the zero-order B-spline grid is chosen so that each row of P activates exactly one of the d^2 coefficients. This makes the KAN a lookup table with one learnable parameter per input row—i.e., the scoring function can memorize any ranking on this specific P. The paper itself concedes in Appendix A.4 that the composition of P controls the analysis (e.g., if P=1, all scoring functions are identical). The abstract's unqualified claim of 'nearly infinite expressive power' is therefore not supported by the theory; at most, the construction shows that a specially designed KAN can realize arbitrary rankings on a specially designed alignment matrix.","section":"Appendix A.7, Proposition 3 and Eq. (70)–(78)"},{"comment":"The ordering MRD(S_KAA, P) ≤ MRD(S_MLP, P) ≤ MRD(S_LT, P) depends on Proposition 1's lower bound, Proposition 2's bounds, and Proposition 3's upper bound. Since Proposition 1's lower bound is invalid for the reasons above, the ordering is not proven. A correct lower bound for linear-transformation attention might be smaller than the MLP upper bound, in which case the hierarchy could fail. The authors should either provide a valid proof of the bound or explicitly restrict the theoretical claims to the empirical finding that KAA improves performance in practice.","section":"Theorem 1, Section 4.2.3"}],"minor_comments":[{"comment":"There is a recurring typo: 'matirx' should be 'matrix' in the statements of Propositions 1, 2, and 3.","section":"Propositions 1–3 and Appendix A.7"},{"comment":"The displayed formula has an extra parenthesis: 'a − π′^{-1}(i))2' should be '(a − π′^{-1}(i))^2'.","section":"Appendix A.6, Eq. (48)"},{"comment":"The 'Avg Imp' row mixes classification accuracies (higher is better) with regression MAE values (lower is better). The reported positive average improvements for regression tasks should be clarified as decreases in MAE, otherwise the 'improvement' sign convention is inconsistent.","section":"Table 3 and Section 5.3"},{"comment":"The phrase 's(hi, hj) = Pd k=1' is missing proper typesetting; the sum should be written as s(hi, hj) = Σ_{k=1}^d φ_k(AF(hi, hj)_k).","section":"Section 4.2.3, paragraph before Proposition 3"},{"comment":"The abstract states 'nearly infinite expressive power' without the qualifications introduced in Appendix A.4 and A.7 (the specific circulant alignment matrix and the lookup-table-style B-spline grid). Please add a caveat to the abstract or intro so the claim matches the proof conditions.","section":"Abstract and Section 1"}],"recommendation":"major_revision","confidential_remarks":"The empirical study is solid and likely publishable as an experimental contribution, but the theoretical section as written contains a load-bearing error in the proof of Proposition 1 and an overclaim in Proposition 3. The authors may be able to repair the theory by proving a valid minimax lower bound (or replacing it with a different formal statement) and by framing Proposition 3 as a construction for a specific alignment matrix. If the theoretical claim cannot be repaired, the paper should be repositioned as an empirical study with a more modest framing of the expressive-power analysis."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper is worth engaging. The empirical core—swap the learnable score mapping in five attentive GNNs for a single-layer KAN and get consistent gains, mostly modest but sometimes large—is believable and well described. The MRD measure is a genuinely new diagnostic for ranking expressiveness of scoring functions, and the unified form s = Ψ ∘ AF is a nice organizing lens. I would cite that part even if I never used KAA.\n\nThe soft spots are concentrated in the theory, and they are load-bearing. Proposition 1's lower bound swaps max and min in the wrong direction; the valid inequality for max over one variable and min over another is max min ≤ min max, so the displayed direction is unjustified. Proposition 2 inherits the pattern, and Theorem 1 orders MRDs using those bounds. Separately, Proposition 3's δ-expressiveness is built on a co-designed instance: P is the first d columns of a circulant matrix with N = d², and the B-spline grid is sized so each row activates exactly one coefficient, making the KAN a lookup table. The paper itself concedes in Appendix A.4 that the composition of P controls the analysis. So the abstract's unqualified claim of nearly infinite expressive power is not supported as written.\n\nThe experiments also mostly use near-linear KAN configurations (spline order 1, grid size 1), so they do not actually stress the nonlinear mechanism the theory highlights. There are no significance tests, and some reported gaps are within one standard deviation. The MLP-attention baseline appears only in the appendix. These are fixable rather than fatal.\n\nWho this is for: graph learning researchers who use attentive GNNs and want a practical, low-overhead module. The empirical claim is useful regardless of the theory's fate. This paper deserves a serious referee: it is not incoherent, the experimental protocol is described in enough detail to reproduce, and the MRD idea is worth refining. I would send it to review with a clear request to repair or rescope the theoretical claims, add significance checks, and move the MLP baseline into the main tables.","headline":"Useful drop-in attention upgrade with a solid empirical story, but the theoretical expressiveness claims rest on a broken inequality and a contrived instance.","tokens_in":27806,"tokens_out":1464,"would_cite":true,"duration_ms":15466,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that KAN-based attention scoring has nearly unlimited ranking expressive power under bounded parameters and consistently outperforms linear and MLP scoring in attentive GNNs.","keywords":["Kolmogorov-Arnold attention","attentive graph neural networks","attention scoring functions","maximum ranking distance","expressive power","B-spline KAN","node classification","graph classification"],"falsifier":"Collect the alignment vectors $\\mathrm{AF}(h_i,h_j)$ from a trained backbone on a benchmark dataset and test whether each row contains exactly one coordinate divisible by the B-spline grid size $d$, as Appendix A.7 requires; if real rows are duplicate or lack this pattern, Proposition 3's bound does not apply to them. Independently, run KAA against each original scorer with matched parameter counts and the same hyperparameter search; the paper's universal empirical claim would be contradicted by any dataset on which a KAA-enhanced model does not beat its backbone.","tokens_in":26595,"feed_emoji":"🧠","tokens_out":8982,"duration_ms":71196,"temperature":0.7,"pith_summary":"The paper tries to establish that in attentive graph neural networks the scoring function—the part that decides how much each neighbor matters—is a real bottleneck, and that swapping it for a Kolmogorov-Arnold network (KAN) removes the bottleneck. It first unifies nearly all existing attentive-GNN scoring functions as a fixed alignment step followed by a learnable score mapping, then introduces Maximum Ranking Distance (MRD) to measure how far a scoring family can be from any desired neighbor ranking. Under bounded parameters, the paper shows linear and MLP scorers have positive MRD lower bounds, while a single-layer KAN with zero-order B-splines can push MRD below any positive threshold, giving it essentially arbitrary ranking power. The empirical claim is that KAA-enhanced models outperform their original backbones across all tested node- and graph-level tasks, with some improvements exceeding 20 percent.","feed_headline":"KAN attention outranks linear and MLP scoring in GNNs","feed_subtitle":"Swapping the attention scorer for a Kolmogorov-Arnold network lifts accuracy by up to 20 percent across benchmarks.","key_machinery":"Central object: the unified scoring function $s(h_i,h_j) = \\Psi \\circ \\mathrm{AF}(h_i,h_j)$, where $\\mathrm{AF}$ is a fixed, non-learnable alignment (concatenation, absolute difference, or dot product) and $\\Psi$ is the learnable score mapping. KAA sets $\\Psi$ to a single-layer KAN whose univariate functions are sums of modified zero-order B-splines $\\phi_k(x) = \\sum_{l=1}^d c_{k,l} B^*_{k,l}(x)$. The load-bearing mechanism is the lookup-table effect: with grid size $d$, a row of the alignment matrix that contains exactly one coordinate divisible by $d$ activates exactly one spline coefficient, so the $d^2$ coefficients give one free parameter per row, enough to encode any target score assignment and hence any ranking of the $N=d^2$ nodes.","core_discovery":"On the paper's own terms, the central discovery is that the score mapping inside attentive-GNN attention—not the feature transformation—is the limiting component, and that replacing it with a Kolmogorov-Arnold network removes the limit. The paper proves for its constructed alignment matrix $P \\in \\mathbb{R}^{N\\times d}$ that a linear scorer satisfies $\\mathrm{MRD}(S_{\\mathrm{LT}}, P) \\ge \\sqrt{\\frac{1}{12}(N^3 - N - d^3 + 3d^2 - 2d)}$, that a two-layer MLP scorer has both upper and lower bounds of the same order, and that a single-layer KAN with modified zero-order B-splines satisfies $\\mathrm{MRD}(S_{\\mathrm{KAA}}, P) \\le \\delta$ for any $\\delta > 0$, giving Theorem 1's ordering $\\mathrm{MRD}(S_{\\mathrm{KAA}}, P) \\le \\mathrm{MRD}(S_{\\mathrm{MLP}}, P) \\le \\mathrm{MRD}(S_{\\mathrm{LT}}, P)$. Empirically, KAA versions of GAT, GLCN, CFGAT, GT, and SAN outperform their originals on every evaluated node- and graph-level dataset, with average node-task gains around 1.6%, graph-task gains around 7.7%, and individual gains exceeding 20%.","pith_inferences":["Editorial inference: the theory's lookup-table proof depends on the B-spline grid lining up with the alignment matrix; on real learned representations that lack this exact divisibility structure, the provable MRD advantage may shrink, which is an empirical question the paper does not resolve.","Editorial inference: if the unified scoring view is right, the same KAN replacement could be tested in other attention architectures beyond graphs, such as sequence Transformers, where the dot-product score is also a low-capacity linear mapping.","Editorial inference: a direct extension would be to measure, on real trained models, how close the matrix of alignment vectors is to the paper's circulant template, and to correlate that closeness with the size of the observed KAA gain.","Editorial inference: the MRD metric itself could serve as a diagnostic for scoring functions in retrieval and ranking tasks, where what matters is exactly the ordering induced by a learned score."],"forward_implications":["KAA can be applied to nearly any attentive GNN by replacing only the learnable score mapping, leaving the alignment function, aggregation, and training pipeline unchanged.","At matched or slightly lower parameter counts, KAA scorers have strictly smaller maximum ranking distance than linear and MLP scorers on the paper's construction, so the theoretical expressive-power ordering favors KAA.","KAA-enhanced GAT, GLCN, CFGAT, GT, and SAN beat their original versions on all evaluated datasets, with average improvements of about 1.6% on node-level tasks and 7.7% on graph-level tasks, and individual gains over 20%.","KAA also improves advanced attentive GNNs such as SuperGAT, HAT, NAGphormer, and SGFormer, so the benefit is not limited to the basic backbones.","The success locates the bottleneck in the score mapping rather than in the feature transformation, complementing earlier KAN-GNN work that used KANs to transform node features."],"supporting_citations":[{"why":"Supplies the KAN architecture and B-spline parameterization that KAA inserts as the score mapping.","marker":"Liu et al., 2024b"},{"why":"Defines GAT, the canonical GAT-based scoring function that KAA replaces.","marker":"Veličković et al., 2018"},{"why":"Introduces MLP-based attention (GATv2) and the static/dynamic attention analysis that MRD refines and compares against.","marker":"Brody et al., 2021"},{"why":"Underlies the universal approximation claim for MLPs that the paper argues does not hold under bounded width and depth.","marker":"Cybenko, 1989"},{"why":"Supplies the MLP approximation theorem whose practical assumptions the paper says scoring functions violate.","marker":"Hornik, 1991"},{"why":"Provides the circulant matrix facts used to build the alignment matrix P and to evaluate the linear-scoring lower bound.","marker":"Davis, 1979"},{"why":"Cited for the full-rank property of circulant matrices used to make P sufficiently distinguishable.","marker":"Kra & Simanca, 2012"},{"why":"Supplies the Transformer attention paradigm whose dot-product scoring is included in the unified form and used in GT and SAN backbones.","marker":"Vaswani et al., 2017"},{"why":"Provides the taxonomy of GAT-based and Transformer-based scoring that the paper unifies into Ψ ∘ AF.","marker":"Sun et al., 2023"}],"fun_headline_variants":["KAN-based scorer beats linear and MLP in GNNs","Single-layer KAN scorer lifts GNN accuracy by up to 20%","KAA removes expressivity limit in attentive GNN scorers","KAA unifies attention scoring and beats all baselines"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The theoretical advantage is proven for one specially structured set of node-pair inputs, namely a circulant alignment matrix in which each row activates exactly one spline coefficient, and the paper concedes that for other inputs, such as all-identical rows, every scoring function collapses to the same ranking.","fun_headline_variants_meta":{"raw":{"variants":["KAN-based scorer beats linear and MLP in GNNs","Single-layer KAN scorer lifts GNN accuracy by up to 20%","KAA removes expressivity limit in attentive GNN scorers","KAA unifies attention scoring and beats all baselines"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000748,"raw_usage":{"total_tokens":3404,"prompt_tokens":1091,"completion_tokens":2313,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":707,"completion_tokens_details":{"reasoning_tokens":2239}},"tokens_in":707,"tokens_out":2313,"duration_ms":14604,"temperature":1.0,"reasoning_tokens":2239,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T16:00:08.511633+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Collect the alignment vectors $\\mathrm{AF}(h_i,h_j)$ from a trained backbone on a benchmark dataset and test whether each row contains exactly one coordinate divisible by the B-spline grid size $d$, as Appendix A.7 requires; if real rows are duplicate or lack this pattern, Proposition 3's bound does not apply to them. Independently, run KAA against each original scorer with matched parameter counts and the same hyperparameter search; the paper's universal empirical claim would be contradicted by any dataset on which a KAA-enhanced model does not beat its backbone.","supporting_citations":[{"cited_title":"On circulant matrices","cited_arxiv_id":null,"evidence_quote":"Cited for the full-rank property of circulant matrices used to make P sufficiently distinguishable."},{"cited_title":"Attention-based graph neural networks: a survey","cited_arxiv_id":null,"evidence_quote":"Provides the taxonomy of GAT-based and Transformer-based scoring that the paper unifies into Ψ ∘ AF."}],"review_version":1}