acceptodds
Under review as a conference paper at ICLR 2027

When Does Direction Help? A Separation Theorem for Directed Polynomial Graph Filters

Abstract

Many node-classification datasets are directed, and directed models improve accuracy on some benchmarks and not on others. It remains unclear when direction helps, and why. We study this question for polynomial graph filters. First, we prove a coefficient-budget separation for the self-looped walk that is deployed in practice. On complete binary trees of height and from a shared root-marking input, a polynomial in the directed walk approximates depth to uniform error with monomial coefficient norm , whereas any polynomial in the undirected walk needs norm at least , regardless of its degree: an over-squashing effect that the directed walk avoids. Second, from the constant input, symmetric polynomial filters cannot represent label components that are antisymmetric under an orientation-reversing symmetry. From this same input, a polynomial in the strict directed walk represents depth on rooted hierarchies and absorption-time potentials on DAGs exactly. Third, we introduce a supervised linear probe on Krylov features, scored on validation nodes before GNN training. Across directed datasets with random features, its score correlates with the measured directed-minus-symmetric test-accuracy gap at Pearson and agrees with its sign on of datasets; with dataset features, and of . Choosing the operator by that sign gives mean test accuracy close to that obtained by training both models and choosing on validation. On hierarchy tasks the directed filter improves over its symmetric counterpart and is competitive with the directed baselines MagNet and Dir-GNN. On most standard control graphs the symmetric filter remains the better choice. Direction helps when labels depend on orientation and are not already captured by node features.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, directed graphs, spectral graph filters, polynomial filters, expressive power, over-squashing, node classification, random walks, model selection, graph representation learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_4jw6OpenReview ↗
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.

Reviewer_ujcmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates when edge direction benefits node classification from the perspective of polynomial graph filters. The authors establish several theoretical results comparing directed and symmetric propagation operators. In particular, they prove a coefficient-norm separation on complete binary trees: approximating node depth requires a coefficient norm that grows linearly with tree height for directed propagation, but exponentially for symmetric propagation. The paper further introduces a polynomial-expressibility score based on supervised linear probes over Krylov features to predict the relative effectiveness of directed and symmetric propagation. Experiments on synthetic and real-world graphs examine their performance under different graph structures and labeling tasks.

The theoretical analysis is interesting, particularly the quantitative separation between directed and symmetric filters. However, its relevance to practical GNN learning remains unclear, as the main result relies on a specific tree construction and does not directly explain the behavior of trained models on real graphs. The empirical findings largely confirm that edge direction helps when labels depend on orientation, but provide limited insight into when this advantage extends to more general node-classification tasks. Furthermore, the proposed expressibility score has not been convincingly shown to predict the benefit of directed propagation beyond differences across dataset families. Overall, the paper provides useful theoretical insights, but the connection between these results and practical GNN performance remains insufficiently established.

Critical strengths
  1. The paper investigates when edge direction benefits node classification rather than proposing another directed GNN. The coefficient-budget separation on binary trees is an interesting result, providing a quantitative comparison of directed and symmetric polynomial filters beyond conventional expressivity analysis.

  2. The matched comparison between DIR-POLY and SYM-POLY helps isolate the effect of edge direction. The experiments cover both favorable and unfavorable settings for directed propagation, with additional comparisons against established directed GNNs.

Critical weaknesses

W1. The theoretical results are not sufficiently connected to practical GNN learning. The main coefficient-budget separation relies on a specific tree structure and prescribed input features, whereas the trained models operate on learned or real node representations without coefficient-norm constraints. It remains unclear whether this separation translates into better optimization or generalization. An analysis of learned coefficients and performance as tree height increases would help establish this connection.

W2. The Poly-gap predictor may mainly capture dataset-family differences. The reported correlation is largely driven by differences between hierarchy-based tasks and conventional graph benchmarks. The appendix shows weaker correlations within certain dataset groups, while a simple dataset-family selection rule matches or slightly exceeds the proposed predictor. This raises doubts about whether Poly-gap captures directional informativeness beyond dataset identity.

W3. The strongest improvements occur on tasks where labels explicitly depend on graph orientation, such as tree depth and ordered stochastic blocks. On attributed graphs, the gains are much smaller, and the selection rule does not consistently outperform symmetric propagation. More convincing evidence on naturally occurring direction-dependent labels is needed to establish practical relevance.

W4. Poly-gap requires supervised probes over Krylov features, making it closer to a lightweight model comparison than an independent prediction criterion. In some cases, the probe itself outperforms the subsequently trained polynomial models. The paper does not clearly establish when this additional model-selection step is worthwhile or whether its decisions extend beyond the two polynomial architectures.

Questions for authors
  1. Can the theoretical coefficient-budget separation be related to the learned coefficients, optimization behavior, or generalization of DIR-POLY and SYM-POLY?
  2. Does Poly-gap remain predictive when edge orientation and label dependence are varied within the same graph family, rather than across different benchmark families?
  3. When does training a polynomial GNN after the supervised Krylov probe provide a meaningful advantage over using the probe directly? Does the selection criterion extend to other directed GNN architectures?
Reviewer_VxcQOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates when preserving edge direction provides an advantage over symmetrized propagation in polynomial graph filters, aiming to characterize this advantage theoretically and predict it empirically. It provides 4 thoerms, Theorems 1–3 are relatively straightforward consequences of symmetry constraints and properties of directed random walks on trees and DAGs. Their theoretical novelty appears limited. Theorem 4 is more interesting. It establishes a coefficient-norm separation for approximating node depth on complete binary trees: the directed filter requires (O(H)), whereas the undirected filter requires at least (\Omega(2^H)).

Critical strengths

The paper addresses an interesting and relevant question: under what conditions does preserving edge direction benefit graph representation learning?

Critical weaknesses

The paper investigates when preserving edge direction benefits polynomial graph filters. Although the research question is relevant, I find the theoretical and empirical contributions limited relative to the broader claims.

Regarding the theoretical contributions, Theorems 1–3 appear to follow largely from established properties of equivariance and absorbing random walks (for example theorem 1 already existed in the literature; for example the ICLR 2019 paper : How Powerful are Graph Neural Networks? and also the ICLR 2023 paper 'Graph Neural Networks for Link Prediction with Subgraph Sketching'). Theorem 4 provides a quantitative coefficient-norm separation, but only for specific random-walk operators on complete binary trees with root-marking inputs and depth-prediction targets. The extent to which this result generalizes to other graph structures and polynomial propagation operators remains unclear (for example how it works for chebyshev). More importantly, the paper does not establish how the coefficient-norm separation relates to optimization, generalization, or the performance of the trained models.

Regarding the experiments, they are quite limited. The strongest positive results are obtained on hierarchy-based or synthetic ordering tasks where edge direction is inherently related to the target labels. This makes the improvements relatively expected. Moreover, the proposed operator-selection criterion does not outperform a dataset-family heuristic, raising questions about its generalizability. Further experiments directly connecting the theoretical separation to learning behavior, and testing operator selection across more diverse graph families and prediction tasks, would strengthen the contribution.

Questions for authors

The authors should investigate how tree depth, coefficient-norm constraints, and approximation error affect the performance of trained directed and undirected filters. Experiments beyond complete binary trees would also help establish whether the theoretical separation has broader practical significance.

Theorem 4 establishes a coefficient-norm separation for specific random-walk polynomial filters on complete binary trees. Its generalizability to other polynomial filters, such as Chebyshev filters, remains unclear. Moreover, the implications of this separation for training and generalization are not established. Does the exponential coefficient-budget separation persist under alternative polynomial bases, such as Chebyshev, and how does the choice of basis affect its practical implications?

Comments on the paper

1 comment
AuthorsOpenReview ↗

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/41/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/32^H/3. Under uncorrelated input noise of equal variance σ2\sigma^2, its root noise variance is at least κHσ2≥3.28⋅2Hσ2\kappa_H\sigma^2\ge 3.28\cdot 2^H\sigma^2 for H≥8H\ge 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)σ2O(H^2)\sigma^2, at every node (Sec. 4.3, App. A). Trained directly, the undirected monomial filter fails to fit beyond H=4H=4. Better-conditioned bases fit, with the predicted variance: 20,674σ220{,}674\sigma^2 at H=12H=12 against 144σ2144\sigma^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=4HK=4H and H=12H=12, SYM-POLY has the lower level-balanced RMSE, driven by levels 11 to 44 (99 of 2,4572{,}457 test nodes). DIR-POLY keeps the lower all-node RMSE, 0.190.19 against 0.970.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)2^{H/2}/(2\sqrt{3}). The lower bound holds on every undirected graph with the ratio of level volumes in place of 2H/32^H/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.84r=0.84, sign on 162162 of 180180 graphs). Its selection improves on the family rule by 9.89.8 points and on the best constant choice by 2.02.0 (95% interval [1.8,2.2][1.8, 2.2]). It comes within 0.50.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 R2R^2 by at most 0.0050.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.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.