- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper proposes PathLapPE, a positional encoding for directed graphs derived from the path Laplacian of the directed path complex. It provides real-valued node- and edge-level features and, unlike magnetic Laplacian encodings, needs no tuning of the charge parameter q. The authors also introduce EdgeSPE, an edge-level extension of SPE that makes the edge encodings sign- and basis-invariant. Experiments on synthetic, node-level and graph-level benchmarks show PathLapPE obtains competitive performance against the other directed (and undirected) graph positional encoding methods.
Critical strengths
The paper is well written, and the related work section gives a helpful overview for readers less familiar with the topic. The motivation for building positional encodings from the path Laplacian of the directed path complex, rather than the magnetic Laplacian, is convincing, since tuning the charge parameter q for each dataset can be costly. The experiments cover a range of settings and show how the method behaves across different benchmarks.
Critical weaknesses
However, the node classification evaluation is limited, as it relies on three small WebKB graphs and Roman-Empire. The paper would benefit from additional directed benchmarks commonly used in the directed-GNN literature. For example, Telegram, used in MagNet (Zhang et al., 2021) and more recently in Fiorini et al. (2026), is a directed influence network on which direction-aware models clearly outperform undirected ones. This makes it a natural test of whether PathLapPE captures useful directional information. Moreover, although Appendix H analyses computational cost, all graphs in the paper are small compared with real-world scenarios, the largest having about 22k nodes. Evaluating on large directed benchmarks such as arxiv-year or snap-patents, as used in Dir-GNN (Rossi et al., 2024), would show how the method compares with the alternative methods on very large graphs, in both accuracy and computational cost.
I also find the motivation for EdgeSPE underdeveloped. The paper notes that SPE cannot be applied directly to edge-level encodings, but I don't find it too fitting in the general narrative. Empirically, based on the experiments, its benefit is not very clear. I believe the paper should frame EdgeSPE more clearly.
References:
Fiorini, S., Aktas, H. E., Duta, I., Morerio, P., Del Bue, A., Lio, P., & Coniglio, S. (2026). Sheaves Reloaded: A Direction Awakening. International Conference on Learning Representations (ICLR).
Rossi, E., Charpentier, B., Di Giovanni, F., Frasca, F., Gunnemann, S., & Bronstein, M. M. (2024). Edge directionality improves learning on heterophilic graphs. Proceedings of the Second Learning on Graphs Conference, PMLR 231, 25:1-25:27.
Zhang, X., He, Y., Brugnone, N., Perlmutter, M., & Hirn, M. (2021). MagNet: A neural network for directed graphs. Advances in Neural Information Processing Systems, 34, 27003-27015.
Questions for authors
-
Rationale for EdgeSPE. What is the motivation for the specific design of EdgeSPE (diagonal, successor and predecessor terms)? From the experiments, it seems to help mainly on the graph-level tasks (OCB, HLS) and much less on the node-level ones. How does EdgeSPE fit the paper's narrative?
-
Choice of node classification datasets. Why were only the WebKB datasets and Roman-Empire used for node classification? Did the authors try other directed benchmarks such as Telegram (Zhang et al., 2021), where direction-aware models clearly outperform undirected ones?
-
Cost on larger graphs. Since L1 grows with the number of edges, could the authors report preprocessing time and memory on a larger directed graph, such as arxiv-year (Rossi et al., 2024)? If the method is not feasible at that scale, this would limit its practical use.
9 comments
Q1 & W3 (Part 1): Motivation for EdgeSPE
We agree with the reviewer that the discussion on EdgeSPE should be expanded. We would therefore like to clarify how it fits within our framework, motivate our choice of aggregation, and provide a brief explanation of its invariance properties.
Motivation
Our PE is spectral in nature, meaning that it is basis-dependent and can be prone to instability: small perturbations of the Laplacian may lead to significant changes in its eigenvectors. This motivates processing the PE to obtain stable descriptors that are invariant under changes of basis. That is precisely the purpose of SPE (Huang et al., 2024), which is also essential for the success of Multi-q-MagLapPE on graph-level benchmarks (Huang et al, 2025). In our case, we have to process spectral information from two Laplacians, and . The node-level encodings from can be processed by the standard (Node)SPE of Huang et al. (2024). The edge-level encodings from are not covered by it and require an analogous treatment. EdgeSPE provides this treatment by closely following the approach of Huang et al. (2024). Within our framework, it is therefore the edge-level counterpart of SPE.
Benefits on graph-level tasks
Indeed, we expect the gains from EdgeSPE to appear mainly on graph-level benchmarks, as the reviewer observes. On node-level benchmarks, the train/validation/test splits are defined over node subsets of a single graph, and the encodings are computed once and cached. Thus the choice of signs and bases is arbitrary but fixed throughout training, so the model never sees the same structure encoded in two different bases, effectively circumventing sign and basis ambiguity. In contrast, on graph-level benchmarks, eigenvectors need to be computed independently for each graph. Structurally similar edges in different graphs can therefore receive encodings that differ by an arbitrary sign flip or basis. Without EdgeSPE, the model must learn approximate robustness to this variation from data, which effectively injects noise into training. EdgeSPE removes this variation by construction.
This matches our empirical observations. On the OCB & HLS regression tasks, PathLapPE with EdgeSPE consistently outperforms its counterpart without EdgeSPE (Table 3 of the revised paper). The effect is even larger on FlowGraphs, where the task depends exclusively on the directional information carried by the PEs:
| PathLapPE | FG2 | FG3 | FG6 |
|---|---|---|---|
| (+) EdgeSPE | 97.56 $\pm$ 0.47 | 74.25 $\pm$ 2.47 | 38.75 $\pm$ 2.54 |
| (—) EdgeSPE | 83.88 $\pm$ 2.92 | 49.17 $\pm$ 9.35 | 22.63 $\pm$ 5.47 |
Q1 & W3 (Part 2): Motivation for EdgeSPE
Construction and motivation for the aggregation
Following Huang et al. (2024), we construct sign- and basis-invariant spectral kernels from the eigenvectors and eigenvalues of L1. Let $U\in\mathbb{R}^{|E|\times k}$ contain the eigenvectors of L1 associated with the k smallest eigenvalues $\lambda\in\mathbb{R}^k$. We define the spectral kernels
$$
\quad K_\ell=U\operatorname{diag}(\phi_\ell(\lambda))U^\top,
\qquad \ell=1,\ldots,m,
$$
where the functions $\phi_\ell$ are permutation-equivariant, as in Huang et al. (2024). Since L1 acts on directed edges, the resulting kernels $K_\ell\in\mathbb{R}^{|E|\times|E|}$ are naturally indexed by pairs of directed edges. To obtain an encoding supported on each individual edge, we introduce an aggregation step.
Our choice of aggregation is motivated by the directed path structure underlying PathLapPE. We consider a simple and interpretable construction that combines the diagonal entries of the spectral kernels with their values on predecessor and successor edges. More precisely, for a directed edge e, we consider its sets of successors and predecessors,
$$
\quad S(e)= \{ f:\operatorname{tail}(f)=\operatorname{head}(e) \},
\qquad
\quad P(e)=\{f:\operatorname{head}(f)=\operatorname{tail}(e) \}.
$$
For each kernel $K_\ell$, we compute
$$
\quad h_\ell^{\mathrm{diag}}(e)=K_\ell(e,e), \
\qquad
h_\ell^{\mathrm{succ}}(e)=\sum_{f\in S(e)}K_\ell(e,f),\
\qquad
h_\ell^{\mathrm{pred}}(e)=\sum_{f\in P(e)}K_\ell(f,e).
$$
The diagonal term captures spectral information associated with the edge itself, while the predecessor and successor terms capture its relationships with edges that can respectively precede or follow it in a directed 2-step walk. By treating these two relationships separately, the aggregation preserves the distinction between the two possible positions of an edge in such a walk. This provides a natural way to obtain edge-level representations from the spectral kernels while retaining information about the directed structure of the graph. Our implementation also allows users to select which of these aggregation terms to retain, providing flexibility in the construction of EdgeSPE.
The resulting features are concatenated and processed by an MLP to obtain the final edge-level encodings.
Invariance properties
The sign- and basis-invariance of EdgeSPE follow directly from the construction of the spectral kernels, using the same arguments as in Huang et al. (2024):
- Sign invariance: Changing the sign of an eigenvector leaves its contribution to the kernels unchanged, since these depend on the outer products .
- Basis invariance: For repeated eigenvalues, the permutation-equivariance of $\phi_\ell$ ensures that the corresponding eigenvectors receive equal weights. The kernels are therefore invariant under orthogonal changes of basis within the associated eigenspaces.
- Preservation under aggregation: Since the kernels are sign- and basis-invariant, taking their diagonal entries, aggregating over predecessor and successor edges, and applying an MLP preserve these properties.
Thus, EdgeSPE provides sign- and basis-invariant edge-level representations while retaining the directed structural relationships described above.
[Huang et al., 2024] On the Stability of Expressive Positional Encodings for Graphs. ICLR 2024.
[Huang et al., 2025] What are Good Positional Encodings for Directed Graphs? ICLR 2025.
Rebuttal overview and changes to PDF
We thank reviewer Un9r for their time and valuable feedback. We have aimed to answer their questions and address their concerns, and of course would be happy to address any follow-ups. In particular, we motivate here the introduction of EdgeSPE and provide further details on its construction and invariance properties. We also uploaded a revised PDF, in which new and updated sections are colored blue. We provide several additional baselines in the revised PDF, also marked in blue: