Positional Encoding meets Persistent Homology on Graphs

Many thanks for your thoughtful feedback! We address all your questions and comments below.

The claim in Section 1 about the drawbacks of partitioning eigenvalue/eigenvector spaces requires clarification.

Thank you for the opportunity to clarify this point. We agree that, in theory, one can utilize the full eigenspectrum of the Laplacian PE. However, in practical scenarios—especially when dealing with datasets containing graphs of varying sizes—the number of eigenmaps, $k$, is treated as a hyperparameter and chosen independently of graph sizes. Most methods, including SPE and BasisNet, follow this approach for network parametrization.

One could, in theory, set $k$ to the maximum graph size in the training set to incorporate the full spectrum. However, this approach becomes memory-intensive and infeasible for large graphs. Moreover, adjustments would still be required during testing if the test set contains graphs larger than those seen during training.

We will add a clarification regarding it in section 1 of the revised version of the paper.

A foundational assumption....

Thanks for pointing this out. We will highlight this assumption in the revised manuscript.

Empirical validation....

Based on your feedback, we have performed an additional experiment on OGBG-MOLHIV, and here are the ROC-AUC results over the test dataset for the RW and SPE methods.

An ablation study explicitly comparing the separate effects of utilizing only 0-dimensional or 1-dimensional persistent diagrams....

Thank you for another excellent suggestion! We conducted an ablation study using $0$-dimensional (VC diagram) and $0$ and $1$-dimensional PH diagrams (RePHINE diagram), with the results presented below. For OGBG-MOLHIV, we report the ROC-AUC, while for ZINC and Alchemy, we report the MAE on the test dataset.

Some relevant references on analyzing the expressive power of PH are missing...

Thank you for providing the reference. We agree that this work is relevant to ours, and we will ensure it is appropriately positioned in the revised version.

It would improve readability to index equations explicitly (e.g., The equation on line 307 of page 6).

Thank you for pointing this out. We will numerate all the equations in the revised version of the paper.

We are grateful for your insightful and constructive feedback. We hope our response has addressed your questions and concerns, and would appreciate your stronger support for this work. Thank you so much!

Thank you so much for your thoughtful comments and excellent suggestions! We've acted on all of them, and also address all your concerns, as we describe below.

The compared baselines are all positional encoding approaches....

Thank you for an excellent suggestion. Based on your feedback, we have conducted an ablation study comparing different PH-based approaches, including vertex-color (VC) filtrations, RePHINE filtrations, and TOGL. Below, we present the test MAE results on the ZINC and Alchemy datasets.

The theoretical analysis is based on unattributed graphs....

Thank you for another insightful remark. Based on your feedback, we have now conducted an empirical study to evaluate the expressiveness of standard PH, PH + LPE and PiPE on the BREC[1] dataset consisting of unattributed graphs across five categories: Basic, Regular, Extension, CFI, and Distance. The table below reports accuracy, with the numbers in parentheses indicating the number of graph pairs in each dataset.

[1] Y. Wang et al. An empirical study of realized GNN expressiveness, ICML 2024.

At the end of the 3rd paragraph in Introduction,...

Several recent works provide evidence that topological information is relevant for downstream tasks in machine learning.

For instance, [1] highlights that incorporating topological structures enhances relational learning by capturing higher-order dependencies beyond standard graph-based representations. Additionally, [2] extends topological networks by incorporating persistence and equivariance, demonstrating applications in molecular dynamics, drug property prediction, etc. Moreover, [3] introduces $E(n)$-equivariant topological neural networks, showing their effectiveness in geometric and molecular modeling tasks. Similarly, [4] proposes TopoDiffusionNet, which integrates topological priors into diffusion models, leading to improved performance in generative modeling.

These works collectively support the claim that topological information can benefit various downstream applications. We will add these references in the revised version of the manuscript.

[1] T. Papamarkou et al. Position: Topological Deep Learning is the New Frontier for Relational Learning, ICML 2024

[2] Y. Verma et al. Topological Neural Networks go Persistent, Equivariant, and Continuous, ICML 2024

[3] C. Battiloro et al. $E(n)$ Equivariant Topological Neural Networks, ICLR 2025

[4] S. Gupta et al. TopoDiffusionNet : A topology aware diffusion model, ICLR 2025

Many thanks again for your constructive feedback and incisive comments. We hope we have satisfactorily addressed your concerns, and would appreciate the same being reflected in an increased score.

Many thanks for your constructive feedback, and for appreciating the different aspects of this work. We address your comments below.

The paper could benefit from further clarification or additional examples to help readers less familiar with advanced topological concepts.

Thank you for an excellent suggestion. We will add a detailed background section in the appendix in the updated version.

Can the method be trivially extended to higher dimensional simplicial complexes?

Thank you for an interesting question. Two steps are required to extend the proposed method to higher dimensional simplicial complexes. First, the positional encodings for various higher-order simplical complexes can be computed using the Hodge Laplacian [1, 2], which generalizes graph Laplacian and serves as a higher dimensional shift operator. Second, one needs to compute the persistent homology (PH) diagram over higher-order simplices, e.g., see [3]. Additionally, one could replace the GNN with a persistence-encoding Topological Neural Network (TNN), e.g. [4], integrating positional encodings and enabling message passing over simplices for downstream tasks.

[1] L.-H. Lim. Hodge Laplacians on graphs, SIAM Review 62.3 (2020): 685-715.

[2] Z. Yan et al. Cycle Invariant Positional Encoding for Graph Representation Learning, LoG, 2023.

[3] F. Chazal et al. Convergence Rates for Persistence Diagram Estimation in Topological Data Analysis, JMLR 16 (2015): 3603-3635.

[4] Y. Verma et al. Topological Neural Networks go Persistent, Equivariant, and Continuous, ICML, 2024.

We are grateful for your thoughtful feedback and suggestions. Thank you so much!

Many thanks for your thoughtful review. We address your concerns and incorporate your suggestions below.

could you numerate all the equations? That is very helpful for the reader and the reviewers in order to refer to them

Thank you for pointing this out. We will numerate all the equations in the revised version of the paper.

Proposition 3.1: what is the multiset of Laplacian positional encodings (LPE)? Can you define this more precisely?

The multiset of Laplacian positional encodings consists of the PE vectors (eigenmaps) assigned to all nodes, derived from the Laplacian eigen-decomposition of the graph structure. We will be sure to make it clear in the revised version of the paper.

Proposition 3.1: is S2 and S3 true for any k?

Yes. S2 and S3 are true for any $k$. Specifically, for any given $k$, we can always find graphs for which S2 holds. Similarly for S3.

Proposition 3.1: what about S2 and S3 together? i.e. if $\beta_0$ and $\beta_1$ are both unequal, is it possible the eigenvectors are still equal?

Thanks for an interesting question. Yes. For any $k$, there exist graphs $G,G'$ such that $\beta_0(G) \neq \beta_0(G')$ and $\beta_1(G) \neq \beta_1(G')$, but $\Phi_{k}(G) = \Phi_{k}(G')$, where $\Phi$ denotes the laplacian positional encoding based on $k$-lowest eigenmaps. We describe the proof below.

Let $K_i$ denote the complete graph with $i$ nodes. Consider a graph $G= \cup_{i=1}^{n/2}K_1 \cup K_3$ --- here $K_1 \cup K_3$ denotes a graph with two components comprising one isolated node and a triangle i.e. $\beta_0(G) = n, \beta_1(G) = n/2$. Also, consider $G'= \cup_{i=1}^{n/2} (K_1 \cup K_1 \cup K_1 \cup K_1)$ --- i.e., $4n/2$ isolated nodes i.e. $\beta_0(G') = 2n, \beta_1(G') = 0$. The $k$ smallest eigenvalues corresponding to $G$ are all equal to 0 with the identical constant eigenvector, when $k \leq n$. Similarly, $G'$ has the same eigenvalues with identical constant eigenvectors. However, the number of connected components and basis cycles in $G$ and $G'$ differ, i.e. $\beta_1(G) \neq \beta_1(G')$ and $\beta_0(G) \neq \beta_0(G')$.

Sec 4. page 5, what is A in the equations? are $z_v$ scalars?

Thanks for pointing this out. The $z_{v}$ are the latent encodings obtained at layer $\ell$ after GNN message passing, and are vectors. $A$ represents the graph structure i.e. the adjacency matrix which is used to compute the $0$-dim and $1$-dim PH diagrams.

Sec 4. page 5, how are the diagrams turned into node or edge features?

Thank you for the opportunity to elaborate on this. To obtain node features from $\mathcal{D}_0$ we note that $|\mathcal{D}_0|=n$, and, therefore, we can define a bijection between $V$ and $\mathcal{D}_0$. In particular, we can associate the death of a connected component with a node and leverage that fact to obtain node features from $\mathcal{D}_0$. For dimension 1, although $|\mathcal{D}_1|$ is equal to the number of independent cycles, we can use dummy tuples for edges that are not linked to any cycle. Details of this procedure can be found in Appendix A.4 in [1]. We agree this is important for the method and we will add a paragraph to clarify the diagram vectorization in the revised manuscript.

[1] M. Horn et al. Topological Graph Neural Networks, ICLR, 2022.

Proposition 4.2: is the point of this proposition that computing PH at each layer is more expressive than doing it only once?

Thank you for the opportunity to underscore the significance of Proposition 4.2. In Proposition 4.2, the idea is to show the message-passing layers of PiPE brings in additional expressivity over simply applying PH on top of base positional encoders. Thus, this result motivates the adoption of message-passing in PiPE.

Do I understand correctly that PH + LPE is essentially similar to a 1-layer PiPE to computed features used by a generic predictor?

For the sake of the analysis, PH + LPE represents the $0$-th and $1$-th persistence diagrams from a filtration function $f$ on the LPE positional encoder $p_v$ for all $v$. As you pointed out, this is similar to a $0$-layer PiPE (i.e., before message passing) --- $f(p_v)$ is the generic predictor that you mentioned (e.g., an MLP mapping $p_v$ to a real number).

We are grateful for your insightful questions that have helped shed light on some subtle and salient aspects of this work. Thank you for your support!