{"id":"244175ea-98c7-4e4f-a2fb-1de5040107e4","arxiv_id":"2509.00772","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A GAT model with polynomial gating (Poly) and a directed variant (Dir-Poly) report strong heterophilic node classification results, with Dir-Poly's largest gain on a single directed dataset.","lead":"This paper combines two existing GNN ideas, polynomial-style gating and direction-aware aggregation, into models called Poly and Dir-Poly. Tests on five heterophilic graph benchmarks reportedly beat several baselines, but the central theoretical proof of polynomial expressivity is incomplete.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Polynomial expressivity proof in §4.1 fails at the first layer: ReLU/sigmoid and GAT softmax attention are not polynomial operations, so deg(x(i))≤i does not follow.","rationale":"The paper's central positive claim has two parts: (1) Poly/Dir-Poly are polynomially expressive, and (2) this expressivity plus directionality yields state-of-the-art results on heterophilic benchmarks. The proof of (1) is the only formal justification, and it is invalid because Eq. (10) contains non-polynomial operations. This is an internal inconsistency in the derivation, not merely a disagreement with prevailing theory. The empirical component is also thinly documented—no code, hyperparameters, data splits, or training details are provided—and the omission of Polynormer, the direct predecessor, makes the comparison difficult to interpret. Since the theoretical foundation fails and the empirical results cannot be independently checked from the manuscript, the rejection is warranted. I agree with the reader's weakest-assumption analysis; my reading does not change the verdict. If the authors supply a corrected formal statement, such as piecewise-polynomial expressivity, and release reproducible code, the paper could be reconsidered.","tokens_in":902,"tokens_out":810,"duration_ms":79966,"concrete_test":"Instantiate Eq. (10) with L=1 on a two-node graph: node 1 has scalar feature t, node 2 has feature 1, fixed weights, and a standard GAT Conv_1. In any fixed linear region of the attention scoring function, the attention coefficient from node 2 to node 1 is exp(a t + b) / (exp(a t + b) + exp(c t + d)) for some constants a,b,c,d, so x^(1)(t) contains exponential terms in denominators and is not a polynomial in t. If the closed form is non-polynomial, Eq. (11) is false as stated. As a second check, replace Conv_i with a fixed linear convolution and sigma with ReLU: the output is only piecewise polynomial, so the 'nonlinearity preserves polynomial degree' step also fails globally. The authors would need to restate the claim as piecewise-polynomial or approximate expressivity, with a proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.1, Eq. (10)–(11), claims the recurrence produces x(i) with deg(x(i))≤i and concludes Poly is L-polynomial expressive. The induction step is invalid because the recurrence composes sigma(W_h x(i−1)) and Conv_i(x(i−1)), then multiplies elementwise. If sigma is ReLU or sigmoid, it is not a polynomial map: ReLU is piecewise linear, and sigmoid is a rational function of exponentials. Conv_i is a GAT-style attention convolution; its coefficients are softmax over input-dependent scores, so the output is a normalized exponential function of x(i−1), not a polynomial. Consequently x(1) is not a polynomial in the input features, and the assertion just before Eq. (11)—that each x(i) is built from elementwise and linear operations over polynomials—is false. This is not a minor gap in one proof: it is the paper's stated theoretical basis for why the architecture is expressive and why the reported gains occur. The empirical results could still be correct, but the central claim that Poly/Dir-Poly are L-polynomial expressive is unsupported as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two GNN architectures for node classification on heterophilic graphs: Poly, a GAT-based model augmented with multiplicative gating and recursive attention/linear layers, and Dir-Poly, which additionally aggregates incoming and outgoing edges separately. The central theoretical claim is that the recurrence in Eq. (10) produces features whose polynomial degree in the input grows with layer index, making the model 'L-polynomial expressive' (Section 4.1). The empirical section reports results on five heterophilic benchmarks (Roman Empire, Amazon Ratings, Minesweeper, Tolokers, Questions), claiming that Poly consistently outperforms existing baselines and Dir-Poly achieves further gains on inherently directed graphs, with no added time complexity compared to standard GAT. The paper does not provide code, hyperparameters, or runtime measurements.","tokens_in":8306,"tokens_out":2223,"duration_ms":29355,"significance":"If the theoretical claim were valid, the paper would make a useful contribution by unifying two previously separate lines of work—polynomial expressivity and edge directionality—for heterophilic graphs. The empirical study is also potentially informative, especially the observation that artificial directionality does not always help. However, the paper's main theoretical contribution, the polynomial expressivity proof in Section 4.1, is invalid as written: the nonlinear activation and softmax-based attention are not polynomial maps, so the induction deg(x(i)) <= i fails at the first layer. In addition, the empirical claims are overstated relative to the reported Table 1, and the absence of code, hyperparameters, and runtime analysis weakens reproducibility. The strengths are the breadth of baseline comparisons and the honest reporting (standard deviations, per-dataset results) that allows readers to see the mixed performance of Dir-Poly.","major_comments":[{"comment":"The proof of polynomial expressivity is invalid. The induction claims deg(x(i)) <= i, but x(1) = (1-beta_1)(sigma(W_h^(1) x) ⊙ (Conv_1(x) + W_l^(1) x)) + beta_1 (Conv_1(x) + W_l^(1) x). This is not a polynomial in the input features because sigma is ReLU or sigmoid (neither is a polynomial map) and Conv_1 is a GAT-style attention convolution with softmax coefficients that depend on x in a non-polynomial way. Therefore the assertion 'each x(i) is built from elementwise and linear operations over polynomials' is false. Since this proof is the paper's theoretical basis for why Poly/Dir-Poly are expressive, the central claim is unsupported.","section":"Section 4.1, Eq. (10)-(11)"},{"comment":"The abstract and Section 5.3 claim that 'Poly consistently outperforms all existing baselines' and 'consistently achieves strong and reliable performance across all datasets.' Table 1 contradicts this: on Questions, Poly (77.31) is worse than FSGNN (78.86), and Dir-Poly underperforms Poly on four of five datasets. The phrase 'consistently outperforms' is not supported by the data. The discussion at the end of Section 5.3 partially acknowledges this, but the framing in the abstract and introduction should be corrected.","section":"Abstract and Section 5.3"},{"comment":"The paper claims 'no added time complexity' compared to standard GATs, but no complexity analysis or runtime experiments are provided. The recursive architecture in Eq. (8) stacks L layers of attention and elementwise products; whether this preserves GAT's complexity depends on the specific implementation, attention head count, and L. Without measurements or a formal argument, this claim is unsupported.","section":"Section 5.3, Scalability"},{"comment":"The paper does not provide code, hyperparameters, training details, or model configuration (e.g., number of layers L, hidden dimensions, dropout, learning rate, weight initialization). The reported results are averaged over 10 runs, but without these details the experiments cannot be reproduced or verified. This is a significant omission for an empirical paper claiming state-of-the-art results.","section":"General reproducibility"}],"minor_comments":[{"comment":"The notation for Eq. (4)-(5) is inconsistent with the variable list: messages are denoted m_i,← and m_i,→ but the list defines m_i,← and m_i,→ with different superscripts. Please align the notation.","section":"Section 3.3"},{"comment":"The table header states 'Averaged node classification results over 10 runs' and reports Accuracy for roman-empire/amazon-ratings and ROC AUC for the others. It would be clearer to state which metric is used for each dataset directly in the column headers or a separate row.","section":"Table 1"},{"comment":"The phrase 'The result is that x(i) is a polynomial function of x' is stated without proof or qualification. Even if the activations were polynomial, the proof would need to account for the fact that Conv_i coefficients (attention weights) are data-dependent. Please either provide a rigorous proof under explicit assumptions or soften the claim.","section":"Section 4.1"},{"comment":"The phrase 'Recent literature have introduced' is grammatically incorrect; should be 'Recent literature has introduced' or 'Several recent works have introduced.'","section":"Introduction"},{"comment":"Several baselines are introduced without full citations (e.g., GAT-sep, G2-GNN). Although references appear later, including the citations at first mention would improve readability.","section":"Section 5.2"}],"recommendation":"reject","confidential_remarks":"The theoretical proof of polynomial expressivity is not a minor gap but the paper's core contribution; it fails because ReLU/sigmoid and softmax attention are not polynomial operations. The empirical results, while potentially interesting, are undermined by the absence of code and hyperparameters and by overstatements in the abstract. The paper would need substantial revision—likely a re-framing as an empirical study without the formal expressivity claim, plus full reproducibility details—before it could be considered for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper recombines two known ideas—Polynormer's polynomial attention and Dir-GNN's directional aggregation—and tests them on five standard heterophilic benchmarks. That combination is new as far as I know, and the empirical results are plausible: Poly does well on minesweeper and tolokers, and Dir-Poly's gain on Roman-empire is consistent with earlier findings on directionality. The experiments are standard, report 10-run means with stds, and the observation that artificial directionality sometimes hurts is honest and useful. This is a clean, easy-to-read paper.\n\nThe soft spots are serious. Section 4.1's proof of polynomial expressivity is simply wrong. The recurrence uses ReLU/sigmoid and GAT-style softmax attention; neither is a polynomial map, so the claim deg(x(i)) <= i fails at the first layer. That is not a minor gap—it is the paper's central theoretical contribution. The abstract also overstates results: FSGNN beats Poly on Questions, and Dir-Poly is worse than Poly on four of five datasets, so \"consistently outperforms\" and \"state-of-the-art\" are too strong. More importantly, Polynormer is the direct predecessor of Poly and is not in the baseline table; omitting it makes the empirical comparison incomplete. There is also no code or hyperparameter details, and the \"no added time complexity\" claim is not backed by runtime measurements.\n\nThe empirical findings could still be correct, but as written the paper is not ready. The theory needs to be either fixed or reframed as an empirical study, and the missing baseline and reproducibility details should be provided. If the authors do that, this could become a useful empirical note for the heterophilic GNN community. I would not desk-reject it; I would send it for peer review with a clear request for major revision. In its current form, I would not cite it or base further work on it.","headline":"A sensible empirical combination of Polynormer-style attention and Dir-GNN directionality, but the polynomial expressivity proof collapses at the first layer and the missing Polynormer baseline makes the empirical claims hard to evaluate.","tokens_in":8750,"tokens_out":2595,"would_cite":false,"duration_ms":32610,"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":"This paper argues that edge direction and high-degree polynomial attention are complementary fixes for heterophilic graphs, and backs the argument with state-of-the-art benchmark results.","keywords":["heterophilic graphs","node classification","graph neural networks","edge directionality","polynomial expressivity","attention mechanism","directed message passing","GAT"],"falsifier":"Symbolically expand the output of a one-layer Poly on a two-node graph with scalar features, with sigmoid activation and softmax attention written out. The expression contains exponential rational terms from softmax and sigmoid, so it is not a polynomial of degree ≤ 1; that single expansion falsifies the claimed degree bound.","tokens_in":7933,"feed_emoji":"🧭","tokens_out":6131,"duration_ms":72393,"temperature":0.7,"pith_summary":"This paper tries to establish that two previously separate fixes for heterophilic graphs—using edge directionality and using polynomially expressive message passing—reinforce each other. It proposes Poly, a GAT variant that recursively composes attention, linear transforms, and multiplicative gating to learn high-degree polynomial feature interactions, and Dir-Poly, which additionally aggregates incoming and outgoing edges separately. On five standard heterophilic benchmarks, Poly consistently outperforms existing GNN baselines, and Dir-Poly adds further gains on a graph whose edge directions carry real signal (Roman Empire), while artificial directionality on undirected graphs does not always help. The paper's claim is that these results demonstrate that direction and expressive aggregation are complementary, and that both can be added to a GAT backbone at no extra time complexity.","feed_headline":"Direction-aware polynomial GNNs top heterophilic benchmarks","feed_subtitle":"Poly beats GCN, GAT, and heterophily baselines; Dir-Poly adds a 3-point gain where edge direction matters.","key_machinery":"The load-bearing object is the Poly recurrence, Eq. (10): x(i) = (1 - beta_i)(sigma(W_h x(i-1)) ⊙ (Conv_i(x(i-1)) + W_l x(i-1))) + beta_i(Conv_i(x(i-1)) + W_l x(i-1)), summed into x_local = Σ_i x(i). The paper argues that because each layer composes previous features by elementwise products, linear maps, and attention convolutions, the degree of x(i) as a polynomial in the input satisfies deg(x(i)) ≤ i, so L layers give L-polynomial expressivity. Dir-Poly swaps Conv_i for a directed-GAT convolution that aggregates messages from in-neighbors and out-neighbors separately, keeping the same recurrence. This single mechanism is what claims to explain both the expressive-power gains and the direct","core_discovery":"The core discovery, in the authors' telling, is that a simple change to the GAT update—replacing plain attention with a recurrence that mixes a nonlinear activation, an attention convolution, and a linear term through an elementwise product—turns the model into an L-polynomial expressive architecture, and the same recurrence carries over cleanly to directed aggregation. Poly is claimed to represent sums of polynomials up to degree L in the input features, with the degree bound deg(x(i)) ≤ i justifying the name. Dir-Poly instantiates the attention convolution as separate in- and out-neighbor aggregations, preserving the polynomial construction while adding directional inductive bias. Empirica","pith_inferences":["Beyond the paper: the degree bound could likely be repaired for ReLU networks by proving piecewise-polynomial expressivity, since ReLU is piecewise linear; the benchmark wins do not depend on the proof being sound.","Beyond the paper: the Roman Empire result suggests a testable predictor—datasets where weighted directed homophily is higher than undirected homophily are exactly where Dir-Poly should beat Poly.","Beyond the paper: because the polynomial gating multiplies the attention output by a nonlinear transform, the same gating could be transplanted onto other backbone convolutions to see whether the gains are specific to attention or general to multiplicative gating.","Beyond the paper: the context-dependence of directionality implies an adaptive model could learn whether to use directed or undirected aggregation per node or per edge, something neither Poly nor Dir-Poly does."],"forward_implications":["Poly's top-two or top-three placement on all five datasets implies that high-degree polynomial interactions, not just deeper linear aggregation, are what lift heterophilic classification.","Dir-Poly's 94.51 on Roman Empire, nearly three points over Poly, implies that preserving edge direction can encode asymmetrical structure that feature polynomials alone miss.","The mixed effect of artificial directionality on undirected datasets implies that direction-aware architectures should be switched on selectively, based on whether edges are semantically directed.","Since both models add no asymptotic time complexity over GAT, the expressivity and directionality gains are available to large graphs without sacrificing scalability.","The claimed degree bound implies that stacking L layers would let one model represent feature interactions of degree up to L, offering a direct route to high-order expressivity within a standard GNN backbone."],"supporting_citations":[{"why":"Supplies the polynomial-expressive local attention design that Poly's recurrence builds on.","marker":"[3]"},{"why":"Supplies the in/out-neighbor directional aggregation scheme that Dir-Poly instantiates.","marker":"[13]"},{"why":"Provides the five heterophilic benchmark datasets and the evaluation protocol used for all comparisons.","marker":"[12]"},{"why":"Serves as a standard GCN baseline whose linear aggregation motivates the polynomial extension.","marker":"[7]"},{"why":"Supplies the GAT attention convolution that Poly augments and compares against.","marker":"[19]"},{"why":"Represents the prior tensor-based high-polynomial-expressive approach whose scalability or expressivity trade-off Poly aims to beat.","marker":"[6]"}],"fun_headline_variants":["Polynomial expressive GNNs with directional edges beat heterophily baselines","Directional edge aggregation improves polynomial GNNs on heterophilic graphs","Poly and Dir-Poly: where flow matters, directional GNNs win","Heterophilic GNNs get a flow boost with directional polynomial aggregation","Dir-Poly: directional polynomial GNN tops heterophilic benchmarks"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The proof that Poly is L-polynomial expressive assumes that the nonlinear activations (ReLU or sigmoid) and the attention coefficients preserve polynomial degree under composition; since none of these is a polynomial function, the degree bound deg(x(i)) ≤ i is not established by the argument given.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial expressive GNNs with directional edges beat heterophily baselines","Directional edge aggregation improves polynomial GNNs on heterophilic graphs","Poly and Dir-Poly: where flow matters, directional GNNs win","Heterophilic GNNs get a flow boost with directional polynomial aggregation","Dir-Poly: directional polynomial GNN tops heterophilic benchmarks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001027,"raw_usage":{"total_tokens":4177,"prompt_tokens":767,"completion_tokens":3410,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":511,"completion_tokens_details":{"reasoning_tokens":3315}},"tokens_in":511,"tokens_out":3410,"duration_ms":29048,"temperature":1.0,"reasoning_tokens":3315,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T13:13:53.156993+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Symbolically expand the output of a one-layer Poly on a two-node graph with scalar features, with sigmoid activation and softmax attention written out. The expression contains exponential rational terms from softmax and sigmoid, so it is not a polynomial of degree ≤ 1; that single expansion falsifies the claimed degree bound.","supporting_citations":[{"cited_title":"High-Order Pooling for Graph Neural Networks with Tensor Decomposition","cited_arxiv_id":"2205.11691","evidence_quote":"Represents the prior tensor-based high-polynomial-expressive approach whose scalability or expressivity trade-off Poly aims to beat."}],"review_version":1}