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

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 $H$ and from a shared root-marking input, a polynomial in the directed walk approximates depth to uniform error $1/4$ with monomial coefficient norm $O(H)$, whereas any polynomial in the undirected walk needs norm at least $2^H/6$, 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 $15$ directed datasets with random features, its score correlates with the measured directed-minus-symmetric test-accuracy gap at Pearson $r=0.89$ and agrees with its sign on $14$ of $15$ datasets; with dataset features, $r=0.81$ and $12$ of $15$. 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.