- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper presents a theory of when edge direction helps polynomial graph filters. It proves a "coefficient-budget separation" showing that a polynomial in the directed walk approximates depth with a far smaller coefficient norm than one in the undirected walk.
Critical strengths
S1: The paper asks when a directed operator should be preferred over a symmetric one, a practical question that existing directed GNN papers leave open.
S2: Theorem 4 holds at every polynomial degree, and the proofs are short and backed by numerical checks.
S3: The directed and symmetric filters differ only in the operator, and negative results, including the control graphs and the citation-era label, are reported openly.
Critical weaknesses
W1: The main result concerns coefficient budgets on complete binary trees, yet no experiment varies tree height or tracks learned coefficients.
W2: The positive results are limited to a few small hierarchy subtrees with nearly saturated performance and a synthetic model. The control datasets are also older benchmarks whose relevance has been questioned [1].
W3: The paper is motivated by uneven gains of directed models on real benchmarks, yet the main study replaces node features with random ones, and with dataset features the selection rule no longer beats the symmetric default on the control graphs.
W4: The probe seems to be a cheaper validation comparison of the two operators on the same labels. Since the dataset-family rule performs equally well, I am not convinced that the probe provides much additional value.
References
[1] Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks, ICML 2025.
[2] GraphBench: Next-generation graph learning benchmarking.
[3] GraphLand: Evaluating Graph Machine Learning Models on Diverse Industrial Data, NeurIPS 2025.
[4] OgBench: A Framework for Evaluating Graph Neural Networks on Omics Data.
Questions for authors
Q1: Q1: I would like to see DIR-POLY and SYM-POLY trained on complete binary trees of increasing height. Do the accuracy gaps or learned coefficient norms follow Theorem 4?
Q2: Can you report the main comparison and the selection rule with dataset features on larger and more realistic directed benchmarks, such as those in [1, 2, 3]?
Q3: Can you show datasets where the probe's choice differs from the family rule and turns out to be correct?
References
[1] GraphBench: Next-generation graph learning benchmarking.
[2] GraphLand: Evaluating Graph Machine Learning Models on Diverse Industrial Data, NeurIPS 2025.
[3] OgBench: A Framework for Evaluating Graph Neural Networks on Omics Data.
Summary for the AC and reviewers: each concern and where the revision answers it
We thank the reviewers and the AC for their time. We ask the AC to consider the revised paper for acceptance on two principal contributions: a basis-independent stability separation between directed and symmetrized polynomial filters, and an operator-selection diagnostic validated under orientation interventions within a dataset family. Below we summarize the evidence that addresses the reviews, with references to the revised PDF (changes in blue).
1. Does Theorem 4 say anything about trained models? (all three reviewers) Yes, in two ways: Corollary 2 constrains every accurate undirected fit, however it is found, and the trained filters show the predicted cost. In Corollary 2 we prove that every undirected polynomial fitting depth to uniform error 1/4 from the root-marking input on complete binary trees, in any basis and of any degree, amplifies some bounded input perturbation at the root by at least 2H/3. Under uncorrelated input noise of equal variance σ2, its root noise variance is at least κHσ2≥3.28⋅2Hσ2 for H≥8. Thus every accurate undirected fit has an exponential lower bound on root noise variance, while the directed construction of Theorem 4 achieves a polynomial upper bound, O(H2)σ2, at every node (Sec. 4.3, App. A). Trained directly, the undirected monomial filter fails to fit beyond H=4. Better-conditioned bases fit, with the predicted variance: 20,674σ2 at H=12 against 144σ2 for the directed fit (App. D.1). In the deployed DIR-POLY and SYM-POLY, the directed advantage grows with height in all four settings. Without input dropout at K=4H and H=12, SYM-POLY has the lower level-balanced RMSE, driven by levels 1 to 4 (9 of 2,457 test nodes). DIR-POLY keeps the lower all-node RMSE, 0.19 against 0.97 averaged over five seeds (App. D.1).
2. Does the separation hold in other bases and on other graphs? (VxcQ) Yes. Corollary 2 is basis-independent, and in the Chebyshev basis the coefficient norm is at least 2H/2/(23). The lower bound holds on every undirected graph with the ratio of level volumes in place of 2H/3, and the directed upper bound holds on every rooted tree (App. A).
3. Does the probe only recognize the dataset family? (all three reviewers) No. Within each WordNet hierarchy, with graph, labels, features and splits fixed and only edge orientations reversed, the probe's score tracks the measured gap (r=0.84, sign on 162 of 180 graphs). Its selection improves on the family rule by 9.8 points and on the best constant choice by 2.0 (95% interval [1.8,2.2]). It comes within 0.5 points of training both filters (Sec. 5, App. D.2).
4. Realistic data and other architectures (4jw6, ujcm). On GraphLand's city-roads with native features, direction changes R2 by at most 0.005 for these filters (App. D.3), and the probe does not transfer to Dir-GNN (App. D.4). We define the probe's scope as the matched polynomial pair. The closing sentence of the paper says that the benefit of direction depends on the architecture, the node features and the task.
5. Novelty of Theorems 1–3 (VxcQ). Theorems 1–3 set up the same-input comparison, and in the revision we attribute them to standard equivariance and absorbing-walk arguments, citing Xu et al. (2019) and Chamberlain et al. (2023). The main theoretical contribution is Theorem 4 with Corollary 2.
These results establish an unavoidable stability cost of symmetrizing in the theorem's setting and show that the diagnostic responds to orientation beyond dataset identity. We believe these are substantive contributions with direct experimental support, and we ask that the final assessment consider them for acceptance.