Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

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.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

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.

T0 review reviewed 2026-08-05 challenge →

load-bearing objection 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. the 4 major comments →

arxiv 2509.00772 v1 pith:OBPA3VFU submitted 2025-08-31 cs.LG

Flow Matters: Directional and Expressive GNNs for Heterophilic Graphs

Arman Gupta , Govind Waghmare , Gaurav Oberoi , Nitish Srivastava This is my paper
classification cs.LG
keywords heterophilic graphsnode classificationgraph neural networksedge directionalitypolynomial expressivityattention mechanismdirected message passingGAT
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

Core claim

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

What carries the argument

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

Load-bearing premise

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.

What would settle it

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.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • 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.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [Section 4.1, Eq. (10)-(11)] 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.
  2. [Abstract and Section 5.3] 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.
  3. [Section 5.3, Scalability] 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.
  4. [General reproducibility] 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.
minor comments (5)
  1. [Section 3.3] 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.
  2. [Table 1] 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.
  3. [Section 4.1] 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.
  4. [Introduction] The phrase 'Recent literature have introduced' is grammatically incorrect; should be 'Recent literature has introduced' or 'Several recent works have introduced.'
  5. [Section 5.2] 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.

Circularity Check

0 steps flagged

No circular derivation: the paper's claims are not fitted to or defined from their conclusions; the polynomial-expressivity proof in §4.1 is invalid, but that is a correctness gap, not circularity.

full rationale

The paper's derivation chain contains no step where an output is defined in terms of the target claim or where a fitted quantity is renamed as a prediction. The only materially questionable passage is the proof of polynomial expressivity in §4.1. The paper asserts: 'The result is that x(i) is a polynomial function of x with degree increasing in i: deg(x(i)) ≤ i' and justifies it by saying 'This is because each x(i) is built from elementwise and linear operations over x(i−1), which themselves are polynomials of degree i−1.' That justification is not sound: Eq. (10) composes σ (ReLU or sigmoid) and Conv_i (a GAT-style softmax attention convolution), neither of which is a polynomial map, so the claimed degree bound does not follow from the recurrence as written. However, this is an unsupported mathematical claim rather than circular reasoning. The architecture is not defined to be polynomial by construction; the experimental benchmark results are independent measurements; and no load-bearing self-citation, imported uniqueness theorem, or ansatz smuggled in via citation is used. Therefore the circularity score is 0. The §4.1 proof gap should be addressed as a correctness/rigor issue, not as a circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

No explicit free parameters are fitted in the theoretical derivation; the model's trainable weights (W_in, W_h, W_l, beta_i) are standard learned parameters. The proof depends on two ad hoc assumptions about the polynomial nature of nonlinear activations and attention, plus an unstated comparability assumption for the baseline results.

axioms (3)
  • ad hoc to paper The nonlinear activation sigma (e.g., ReLU or sigmoid) preserves or increases the polynomial degree in the recurrence.
    Section 4.1 uses sigma in Eq. (10) and then concludes deg(x(i)) <= i, which requires sigma to have finite polynomial degree. ReLU and sigmoid do not.
  • ad hoc to paper The attention convolution Conv_i is a polynomial function of the input features.
    Eq. (10) treats Conv_i(x(i-1)) as contributing linear or polynomial terms, but GAT attention coefficients are computed via softmax over scores, which is not a polynomial operation.
  • domain assumption The benchmark baseline numbers in Table 1 were obtained under comparable training conditions.
    The paper does not describe how baseline numbers were produced; comparability is assumed.

reviewed 2026-08-05 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Flow Matters: Directional and Expressive GNNs for Heterophilic Graphs." pith.science (2026). https://pith.science/paper/OBPA3VFU

@misc{pith2026250900772,
  author       = {Pith},
  title        = {Pith review of: Flow Matters: Directional and Expressive GNNs for Heterophilic Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OBPA3VFU}},
  note         = {Machine review of arXiv:2509.00772}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

In heterophilic graphs, where neighboring nodes often belong to different classes, conventional Graph Neural Networks (GNNs) struggle due to their reliance on local homophilous neighborhoods. Prior studies suggest that modeling edge directionality in such graphs can increase effective homophily and improve classification performance. Simultaneously, recent work on polynomially expressive GNNs shows promise in capturing higher-order interactions among features. In this work, we study the combined effect of edge directionality and expressive message passing on node classification in heterophilic graphs. Specifically, we propose two architectures: (1) a polynomially expressive GAT baseline (Poly), and (2) a direction-aware variant (Dir-Poly) that separately aggregates incoming and outgoing edges. Both models are designed to learn permutation-equivariant high-degree polynomials over input features, while remaining scalable with no added time complexity. Experiments on five benchmark heterophilic datasets show that our Poly model consistently outperforms existing baselines, and that Dir-Poly offers additional gains on graphs with inherent directionality (e.g., Roman Empire), achieving state-of-the-art results. Interestingly, on undirected graphs, introducing artificial directionality does not always help, suggesting that the benefit of directional message passing is context-dependent. Our findings highlight the complementary roles of edge direction and expressive feature modeling in heterophilic graph learning.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Graph Transductive Sharpening: Leveraging Unlabeled Predictions in Node Classification

    cs.LG 2026-05 unverdicted novelty 5.0

    Transductive Sharpening adds an entropy-minimization term on unlabeled-node predictions to the training objective for graph node classification.

Reference graph

Works this paper leans on

24 extracted references · 6 canonical work pages · cited by 1 Pith paper · 5 internal anchors

  1. [1]

    Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. 2020. Joint Adaptive Feature Smoothing and Topology Extraction via Generalized PageRank GNNs. CoRRabs/2006.07988(2020).arXiv:2006.07988 https://arxiv.org/abs/2006.07988

    Pith/arXiv arXiv 2020

  2. [2]

    2020.PrincipalNeighbourhoodAggregationforGraphNets

    GabrieleCorso,LucaCavalleri,DominiqueBeaini,PietroLiò,andPetarVelickovic. 2020.PrincipalNeighbourhoodAggregationforGraphNets. CoRRabs/2004.05718 (2020). arXiv:2004.05718 https://arxiv.org/abs/2004.05718

    Pith/arXiv arXiv 2020

  3. [3]

    Chenhui Deng, Zichao Yue, and Zhiru Zhang. 2024. Polynormer: Polynomial- Expressive Graph Transformer in Linear Time. arXiv:2403.01232 [cs.LG] https: //arxiv.org/abs/2403.01232

    Pith/arXiv arXiv 2024

  4. [4]

    Schoenholz, Patrick F

    Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. 2017. Neural Message Passing for Quantum Chemistry. arXiv:1704.01212 [cs.LG] https://arxiv.org/abs/1704.01212 Flow Matters: Directional and Expressive GNNs for Heterophilic Graphs

    Pith/arXiv arXiv 2017

  5. [5]

    InductiveRepresentation Learning on Large Graphs.CoRR abs/1706.02216 (2017)

    WilliamL.Hamilton,RexYing,andJureLeskovec.2017. InductiveRepresentation Learning on Large Graphs.CoRR abs/1706.02216 (2017). arXiv:1706.02216 http://arxiv.org/abs/1706.02216

    Pith/arXiv arXiv 2017

  6. [6]

    High-Order Pooling for Graph Neural Networks with Tensor Decomposition

    ChenqingHua,GuillaumeRabusseau,andJianTang.2022. High-OrderPoolingfor Graph Neural Networks with Tensor Decomposition. arXiv:2205.11691 [cs.LG] https://arxiv.org/abs/2205.11691

    work page internal anchor Pith review Pith/arXiv arXiv 2022

  7. [7]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. 2016. Semi-Supervised Classification with Graph Convolutional Networks.CoRR abs/1609.02907 (2016). arXiv:1609.02907 http://arxiv.org/abs/1609.02907

    Pith/arXiv arXiv 2016

  8. [8]

    Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. 2022. Finding Global Homophily in Graph Neural Networks When MeetingHeterophily. arXiv:2205.07308[cs.LG] https://arxiv.org/abs/2205.07308

    Pith/arXiv arXiv 2022

  9. [9]

    Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. 2017. Gated Graph Sequence Neural Networks. arXiv:1511.05493 [cs.LG] https://arxiv.org/ abs/1511.05493

    Pith/arXiv arXiv 2017

  10. [10]

    Ningyi Liao, Zihao Yu, and Siqiang Luo. 2024. DHIL-GT: Scalable Graph Transformer with Decoupled Hierarchy Labeling. arXiv:2412.04738 [cs.LG] https://arxiv.org/abs/2412.04738

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  11. [11]

    Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. 2021. Improving Graph Neural Networks with Simple Architecture Design. arXiv:2105.07634 [stat.ML] https://arxiv.org/abs/2105.07634

    Pith/arXiv arXiv 2021

  12. [12]

    AcriticallookattheevaluationofGNNsunderheterophily: Are we really making progress? arXiv:2302.11640 [cs.LG] https://arxiv.org/abs/ 2302.11640

    Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova.2024. AcriticallookattheevaluationofGNNsunderheterophily: Are we really making progress? arXiv:2302.11640 [cs.LG] https://arxiv.org/abs/ 2302.11640

    Pith/arXiv arXiv 2024

  13. [13]

    Emanuele Rossi, Bertrand Charpentier, Francesco Di Giovanni, Fabrizio Frasca, Stephan Günnemann, and Michael Bronstein. 2023. Edge Directionality Improves Learning on Heterophilic Graphs. arXiv:2305.10498 [cs.LG] https://arxiv.org/ abs/2305.10498

    Pith/arXiv arXiv 2023

  14. [14]

    Gradient Gating for Deep Multi-Rate Learning on Graphs

    T. Konstantin Rusch, Benjamin P. Chamberlain, Michael W. Mahoney, Michael M. Bronstein, and Siddhartha Mishra. 2023. Gradient Gating for Deep Multi-Rate Learning on Graphs. arXiv:2210.00513 [cs.LG] https://arxiv.org/abs/2210.00513

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  15. [15]

    FrancoScarselli,MarcoGori,AhChungTsoi,MarkusHagenbuchner,andGabriele Monfardini. 2009. The Graph Neural Network Model.IEEE Transactions on Neural Networks20, 1 (2009), 61–80. doi:10.1109/TNN.2008.2005605

    arXiv 2009

  16. [16]

    Yunchong Song, Chenghu Zhou, Xinbing Wang, and Zhouhan Lin. 2023. Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing. arXiv:2302.01524 [cs.LG] https://arxiv.org/abs/2302.01524

    Pith/arXiv arXiv 2023

  17. [17]

    Zekun Tong, Yuxuan Liang, Changsheng Sun, Xinke Li, David Rosenblum, and Andrew Lim. 2020. Digraph Inception Convolutional Networks.Advances in Neural Information Processing Systems 33 (2020)

    work page 2020

  18. [18]

    Directed Graph Convolutional Network

    Zekun Tong, Yuxuan Liang, Changsheng Sun, David S. Rosenblum, and Andrew Lim. 2020. Directed Graph Convolutional Network. arXiv:2004.13970 [cs.LG] https://arxiv.org/abs/2004.13970

    work page internal anchor Pith review Pith/arXiv arXiv 2020

  19. [19]

    GraphAttentionNetworks

    PetarVeličković,GuillemCucurull,ArantxaCasanova,AdrianaRomero,PietroLiò, andYoshuaBengio.2018. GraphAttentionNetworks. arXiv:1710.10903[stat.ML] https://arxiv.org/abs/1710.10903

    Pith/arXiv arXiv 2018

  20. [20]

    Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. 2019. A Comprehensive Survey on Graph Neural Networks.CoRR abs/1901.00596 (2019). arXiv:1901.00596 http://arxiv.org/abs/1901.00596

    Pith/arXiv arXiv 2019

  21. [21]

    Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra

  22. [22]

    Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, and Matthew Hirn. 2021. MagNet: A Neural Network for Directed Graphs. arXiv:2102.11391 [cs.LG] https://arxiv.org/abs/2102.11391

    work page internal anchor Pith review Pith/arXiv arXiv 2021

  23. [23]

    Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020. Generalizing Graph Neural Networks Beyond Homophily.CoRR abs/2006.11468 (2020). arXiv:2006.11468 https://arxiv.org/abs/2006.11468

    Pith/arXiv arXiv 2020

  24. [2022]

    arXiv:2102.06462 [cs.LG] https://arxiv.org/abs/ 2102.06462

    Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks. arXiv:2102.06462 [cs.LG] https://arxiv.org/abs/ 2102.06462

    Pith/arXiv arXiv

This paper was first reviewed by deepseek-v4-flash on August 5, 2026.