Positional Encoding meets Persistent Homology on Graphs
Authors: Yogesh Verma
Amauri H Souza
Vikas K Garg
Venue: ICML 2025 poster (2025)
Keywords: Topological Neural Networks
Persistent Homology
Positional Encodings
GNNs
Primary area: deep_learning->graph_neural_networks
TL;DR: We introduce a novel learnable positional encoding method that combines positional encodings with persistence homology and offers theoretical insights about additional expressivity with rigorous empirical validation

Abstract: The local inductive bias of message-passing graph neural networks (GNNs) hampers their ability to exploit key structural information (e.g., connectivity and cycles). Positional encoding (PE) and Persistent Homology (PH) have emerged as two promising approaches to mitigate this issue. PE schemes endow GNNs with location-aware features, while PH methods enhance GNNs with multiresolution topological features. However, a rigorous theoretical characterization of the relative merits and shortcomings of PE and PH has remained elusive. We bridge this gap by establishing that neither paradigm is more expressive than the other, providing novel constructions where one approach fails but the other succeeds. Our insights inform the design of a novel learnable method, PiPE (Persistence-informed Positional Encoding), which is provably more expressive than both PH and PE. PiPE demonstrates strong performance across a variety of tasks (e.g., molecule property prediction,  graph classification, and out-of-distribution generalization), thereby advancing the frontiers of graph representation learning. Code is available at https://github.com/Aalto-QuML/PIPE

Positional Encoding meets Persistent Homology on Graphs
Yogesh Verma' Amauri H. Souza 12 Vikas Garg 13
Abstract
(Gilmer al., 2017: Stokes et al., 2020; Satorras al., 2021), simulation of physical systems (Crammer et al., 2019; Sanchez-Gonzaler et al., 2020; Verma & Jena, 2021), algo- rithmic reasoning (Dudzik et al., 2023; Jurss et al., 2023), and recommender systems (Ying et al., 2018).
The local inductive bias of message-ppssingg graph neural networks (GNNs) hampers their ability to exploit key structural information (e.g., con- nectivity and cycles). Positional encoding (PE) and Persistent Homology (PH) have emerged as two promising approaches to mitigate this issue. PE schemes endow GNNs with location-aware features, while PH methods enhance GNNs with multiresolution topological features. However, a rigorous theoretical characterization of the rel- ative merits and shortcomings of PE and PH has remained elusive. We bridge this gap by establishing that neither paradigm is more ex- pressive than the other, providing novel construc- tions where one approach fails but the other suc- ceeds. Our insights inform the design of a novel learnable method, PiPE (Persistence- errfforence-iformeed Positional Encoding). which is provably more expressive than both PH and PE. PiPE demon- strates strong performance across variety of tasks (c.g., molecule property prediction, graph classification, and aut-of-distributie generaliza- tion), thereby advancing the frontiers of graph rep- resentation learning. Code is available at ht attps: //github www./awwoooooooooooooooooooooooa Aatiiaalltttu/PPPAA QUML/PIPE.
Despite this success, message-passing GNNs have rather limited expressivity - they are at most as powerful as the 1-Weisfeiler-Lehmne (1-WI.) test (Weisfeiler & Leman, 1968) in distinguishing non-isomorphic graphs (Xu et al., 2019; Morris et al., 2019; Nikolentzos et al., 2023). This inherent limitation has prompted the development of more expressive GNNs by leveraging, e.g. topological features (Horn et al., 2022), random features (Sato et al., 2021), higher-order message passing (Morris et al., 2019; Ballester et al., 2024), and structural/posiiiinaal encodings (Li et al., 2020; You et al., 2019; Wang al., 2023).
Inspired by the success of positional encodings (PEs) in Transformers (Vaswani et al., 2017) for sequences, several positional encodings for graphs have been proposed (You et al., 2019; Dwivedi al., 2022; Wang et al., 2023; Huang et al., 2024). For instance, spectral methods exploit global structure via the eigendecomposition of the graph Laplacian (Lim et al., 2023; Kreuzer al., 2021; Huang et al., 2024). However, these encodings suffer from inherent ambiguities due to sign flips, basis changes, stability, and eigenvalue multiplicities. Recent efforts have addressed sign and ba- sis symmetries (Lim et al., 2023; Wang et al., 2023) and stability with respect to graph perturbations (Huang et al., 2024). However, a common drawback persists: most meth- ods partition the Laplacian cigenvalue/ciienneetrr space and utilize only the partitioned eigenvalues/eigeneetoi This approach discards valuable information contained in the remaining eigenvalues and eigenvectors. Another class of methods leverage relative distances (c.g., computed from random walk diffusion) anchor-noder tural information (Dwivedi et al., 2022; Eliasof et al., 2023; Ying et al., 2021; You et al., 2019; Li al., 2020). Despite these advances, existing methods fail to extract detailed multiscale topological information, such as the persistence of connected components and independent cycles (i.e., 0- and 1-dim topological invariants), which may be relevant to downstream tasks and potentially more expressive.
1. Introduction
Many natural systems, such as social networks (Freeman, 2004) and proteins (Jha et al., 2022), exhibit complex rela- tional structures often represented as graphs. To tackle prediction problems in these domains, message-passing graph neural networks (GNNs) (Scarselli al., 2009; Bron- stein et al., 2017: Hamilton et al., 2017: Velickovie al., 2018) have become the dominant approach, leading to break- throughs in diverse applications such drug discovery
capture struc-
'Department of Computer Science, Aalto University, Finland Federal Institute of Ceará à Yai Ltd. Correspondence to: Yo- gesh Verma eyogesh.vent verma @ fi..
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Persistent homology (PH) (Edelsbrunner et al., 2002) is

---

Positional Encoding meets Persistent Homology Graphs
Main contributions
Shortcomings of PE and PH (Section 3):
Neither is more expressive: constructions exposing limitations
Prop. 3.1, 3.2
PH enhanced with PE (Section 3.1):
Different base PE - different persistent diagrams
Lem. 3.3
Comparison with standalone PE methods
Prop. 3.4,
On degree-hased filtrations and PE
Prop. 3.6
PiPE (Section 4):
LPE-based PiPE LPE-based LSPE, PH+LPE
Prop. 4.1, 4.2
RW-based PiPE and 3-WL
Prop. 4.3
On k-FWL and color separating sets
Prop. 4.4
Experiments (Section 5): Graph classification, property prediction, and OOD tasks
Figure 1: Overview of our key contributions
the cornerstone of topological data analysis and offers powerful framework to capture multi-scale topological in- formation from data. In the context of graphs, PH has been recently used, c.g., to boost the expressive and representa- tional power of GNNs (Horn al., 2022; Immonen al., 2023; Carriere al., 2020; Verma al., 2024). However, while both PE and PH schemes enhance the expressivity of GNNs, their relative merits and shortcomings remain unclear. Furthermore, whether the two can be harmonized to enable further expressivity gains remains unexplored.
2. (Methodolgy) Building on these insights, we intro- duce Pensistence-ifformed Positional Encoding (PiPE), a novel learnable PE method that unifies PE and PH through message-passingg networks by combining strengths of both.
(Empirical) We show that the improved expressivity of our approach also translates into gains in real-world problems such graph classification, molecule prop- erty prediction, out-of-distribution generalization, as well as on synthetic tree tasks.
In this work, we introduce novel constructions to reveal that neither paradigm is more expressive than the other. Leveraging insights, introduce PiPE (Persistence- informed Positional Encoding), learnable positional en- coding scheme that unifies PE and PH through message- passing networks. Notably, PiPE is very flexible as it can be based on any existing PE method for graphs, and renders provable expressivity benefits over what can be achieved by either PE PH methods on their own.
2. Background
This section overviews graph positional encoding methods, and some basic notions in persistent homology for graphs.
Notation. We define a graph as tuple G -V, where V = fl.....21 } is a set of vertices (or nodes) and E is set of unordered pairs of vertices, called edges. We denote the adjacency matrix of G by E {0, 1) 1 i.e., Ai is one { E and zero otherwise.
Specifically, theoretically analyze PiPE and compare its representational power popular learnable PE methods such as I.PP (Dwivedi et al., 2022), and analyze it in terms of the higher-order WL hierarchy, i.c., k-WL. To demon- strate the effectiveness of our proposal, we conduct rigorous empirical evaluations on various tasks, including molecule property prediction, aat-of-distribution generalization, and synthetic tree tasks.
use D to represent the diagonal degree matrix of G, i.c. D = Σ, Agj. We define the normalized Laplacian of G' as A In D D- 1/2 and its random walk Laplacian as Agw D-1 where In is the n-dimensional identity matrix. The set of neighbors of a node u denoted by N(v) = {u E [v,u] Furthermore, we use {( to denote multisets. Attributed graphs are augmented with a function assigns color (or d-dimensional feature vector) to nodes E V - for notational convenience, hereafter, we denote the feature vector of v by Ze. Finally, two attributed graphs G = (V, E, and G' = (V' E')x') are said to be isomor- phic if there is bijection V + V' such that {u, o) E E iff (g(u), g(v) E E' and r' o x.
u} E E}.
Rd that
In sum, contributions three-fold:
1. (Theory) We establish theoretical results about incom- parability of PE and PH methods, their limitations and how we can combine PH and PE to elevate the repre- sentational power summarized in Figure 1.
2

---

Positional Encoding meets Persistent Homology on Graphs
PiPE integration with backbone GNN
Readout (graph-level)
{al
11 fu
(4)
GNN
Lo fu
{
Fu
Pool1
hG
(pl-11) "'
GNN
{pu Fu
11,,0 (0)1
Pool2
((-1)).0 Nu
(r1000) 10,1
PD ft
Dl. D
Vectorization;
((-1),1 Fu
Figure 2: Overview of PiPE and integration with backbone GNN, At each layer é, the node embeddings { " are updated using the positional embeddings {pf-1 a and the topologiaal embeddings (rā-100 r rff1111 )u. The position
embeddings (p(-1) au are updated and then leading the computation of persistence diagrams Dj, D2 leading topological
embeddings {re. r.11).. u-- In readout phase, the final layer node embeddings {ar/)w are combined with the topological
embeddings [r - Ju,e for various tasks.
2.1. Graph positional encoding
Random walk PE (Dwivedi et al., 2022): This approach captures node proximity through the random walk dif- fusion process and can viewed as a simplified ver- sion of Distance PE. In particular, Dwivedi al. (2022) adopt p [[ARw) vw ( (www)ve...... ... (A )wul
Given graph G, a positional encoder acts on A (adjacency matrix of G) to obtain an embedding matrix P E Bann where the e-th row of P comprise the positional feature of node v, denoted by Pv- Integrating PEs into message- passing GNNs (Gilmer al., 2017; Xu et al., 2019) enables them to learn intricate relationships between nodes based on positional information, ultimately enhancing their repre- sentational power. Although several PE methods (Dwivedi et al., 2022; Li et al., 2020; Lim et al., 2023; Wang et al., 2023) have been proposed, most approaches build upon:
Dwivedi et al. (2022) also propose learnable structural and positional encodings (LSPE) as general framework that builds upon base positional encoders (e.g., LapPE). More specifically, the key idea of LPSE lies at decoupling posi- tional and structural representations and learn them using message-passing layers. Formally, starting from ze 2, and p Pv Vu V. LSPE recursively updates positional and node embeddings as
Laplacian PE (Dwivedi & Bresson, 2020): This ap- proach employs the idea of Laplacian eigenmaps (Belkin & Niyogi, 2003) as PE. In particular, let A = UAUT,, where U E Raxx is an orthonor- mal matrix with cigenvectors uj....,u4 Un and the ma- trix A = diag(>1,...., An) comprises the correspond- ing eigenvalues (or spectrum) of A, with A S < An- Then, Laplacian PE uses the k smallest (non-trivial) eigenvectors positional en- codings, i.e., Pe = [uz.r: U2,...... Uk,el for all e V. We note that this corresponds to the solution to: max trace( PT AP) subject to PT DP = T
o -- Updd (ot, Aggi (o PL uu ((O)))))) = =pd? (p': Agg7(1ii (N))))))
(1)
(2)
where Agg² and Aggž are arbitrary order-invariant func- tions, and Updğ and Upd are arbitrary functions (often multilayer perceptrons, MLPs). After iterative updating, the final layer node embeddings are concatenated with the final positional ones, i.e., { pf]]). and then leveraged for downstream tasks, such as node classification, graph classification, link prediction.
X2
Distance PE (Li et al., 2020): Let S C V be a target subset of vertices. Distance PE learns node features for each node e based on distances from v to elements in S (You al., 2019). The distances comprise either random walk probabilities generalized PageRank scores (Li et al., 2019). Formally, using sum-pooling, Distance PE computes P.- = Eves fdd((, s)) with s)(v,s) = [(ARw) (2ww)
2.2. Persistent homology on graphs
A key notion in persistent homology is that of filtration. In this regard, a filtration of graph G is a finite nested se- quence of subgraphs of G, i.e., @ Go G1 C ... G. A popular choice to obtain filtration consists of consid- cring sublevel sets of a function defined on the vertices of a graph. In particular, let f V - R be a filtering func- tion and G. be the subgraph of G induced by the vertex set V. = {v fwv) S a) for a E R. By varying a from
(A&w) mnal or M where 7/s E and f(-)
da(v, s) = 1 is multilayer perceptron.
3

---

Positional Encoding meets Persistent Homology on Graphs
G
G'
K
K'
Figure 3: Incomparability of PH and PE. The graph G. resembling an anthracene molecule, consists of three conjoined 3-cycles sharing a ring. Using the l = Bo(G) + lowest Laplacian PE eigenmaps. PE fails to capture the number of basis cycles. The tt (Fiedler's) ss eigenvector partitions G into two components, as shown in G', missing the cyclic structure. The graphs K consist of two 4-cycles sharing consecutive nodes, and K' consist of a 4-cycle inscribed in a 5-cycle sharing three consecutive nodes. Both K and K" have the same number of connected components (5)) and basis cycles (51) but have distinct Laplacian eigenspectra.
-00 co, obtain sub-level filtration of G. Impor- tantly, we can monitor the emergence and vanishing of topo- logical characteristics (e.g., connected components, loops) throughout a filtration, which is the core idea of PH. More specifically, if a topological feature first appears in Go, and disappears in Gas: then we encode its persistence as pair (as, aa): if a feature does not disappear, then its persistence is (as, o0). The collection of all pairs forms multiset that we call persistence diagram (PD). We use D (G, f') to de- note the i-dimensional PD of G obtained using the function f. Additionally, for any graph G. (G) and 3, (G) are its Betti numbers, i.c., the number of connected components and independent (basic) cycles, respectively. For a formal treatment of PH, we refer to Edelsbrunner & Harer (2010) and Hensel et al. (2021).
3. Shortcomings of PE and PH
This section examines the limitations of positional encod- ings (PE) and PH methods in distinguishing non-isomorphic graphs. We focus on Laplacian PE, random-wall PE, and distance encodings (see Section 2.1) as they are the funda- mental building blocks behind most PE methods. Regarding PH. we mainly consider persistence diagrams derived from VC filtrations. We defer all proofs to Appendix C.
Our first result (Proposition 3.1) establishes the incompara- bility of PH and LapPE unattributed graphs, i.e., neither method encompasses the capabilities of the other. Recall that the expressive power of PH from VC filtrations on unattributed graphs is bounded by 8o and 31.
Proposition 3.1. For any graph G and k > 0, lei &R(G) denote the multiset of Laplacian positional encodings (LPP) of G built using the k lowest eigenpairs. The following holds:
In graph learning, persistent homology has been harnessed to enhance the expressive power of GNNs. Horn et al. (2022) introduced TOGL., a general framework for integrating topo- logical features derived from PH into GNN layers. TOGL employs learnable function (a multilayer perceptron, MLP) on node features / colors obtain graph filtrations, which we refer to vertex-color (VC) filtrations. Importantly, Immonen et al. (2023) characterized the expressive power of VC filtrations via the notions of color-separating sets and component-wise colors. Formally, a color-separating set for a pair of attributed graphs (G, G') with corresponding coloring functions x and x' is set of colors Q such that the subgraphs induced by V \ (w E V Iw Q} and V' fw E V" | E Q} have distinct component-wi colors- - defined as the multiset comprising the set of node colors of each connected component. When dealing with VC filtrations, we use DG, C, f) to denote the i-th dim persistence diagram of G considering the indexed set of ver- tex colors C {co )vev())) with e, E U4 and the filtration function/ f :u + R- Z is the universe of possible colors.
S1. There exist GIZGA
FG2 s.t. Bo( (.)). (,;G;) B1 B1(G2) but (x # ( for all k > (o(G)):
S2. There exist G1 7 G2 such that (G,) + 31 (G2) but
4 (G,) = (G2)
S3. There exist G| 2 G2 such that Bo(Gr) # (o( but T (G,) = 4b
This shows that the incomparability holds even if we con- sider only O-dim or 1-dim topological features. Proposition 3.2 shows the same result also applies to random walk PE.
Proposition 3.2. Let & (G) denote the multiset of random walk positional encodings obtained from walks of length k. The statements SI, S2, S3 of Proposition 3.1 still holds.
Overall, Propositions 3.1 and 3.2 reveal that both PE and PH methods have complementary limitations. A key conse- quence of statement $2 is that LapPE cannot determine the number of basis cycles in a graph. As illustrated in Figure 3, even when using = 3 + lowest Laplacian eigenmaps, the ttth (Fiedler's 's) eigenvector merely bisects graph G' into two components, failing to capture the cyclic structure.
4

---

Positional Encoding meets Persistent Homology Graphs
G
G'
K
K'
Figure 4: Construction for Propositions 3.4 and 4.3. The graph G with copies of Cs is indistinguishable from graph G" with Coo by RW-based PE, despite having disconnected components. This follows since every node in G and G' has the same degree and same RW-based PE &s. In contrast, PH can separate them due to distinct connected components. Likewise, K and K' are 4-regular and 2-WL equivalent graphs which are indistinguishable due to the same RW-based PE.
In the following, we describe how we can leverage PE and PH methods to overcome their individual limitations and achieve enhanced representational capabilities.
$ and ( $1 (G2),))
Additionally, Proposition 3.6 considers PH based on degree filtrations and shows that does not subsume combinations of PH with LapPE and RWPE.
3.1. Benefits of combining PE with PH
Proposition 3.6. Consider D(G) (doleev(a) where du is the degree of node v. Again, let +x(G)) be either the k-dim Laplacian PEs or k-length random walk PEs of G. Then, there exist > 0, G1 E G2 such that D2 D(G2). f) for all f, but DO (GG,))(G)).))) + D (G2, (G2). f) for some f-
We now show that persistent homology benefits from additional expressive power due to positional encoding. We start by showing that defining filtering functions positional encodings results in O-dim persistence diagrams that are least as expressive the positional encodings in distinguishing non-isomorphic graphs. In other words, we do not lose expressive power by relying only on O-dim diagrams. This is a direct consequence (corollary) of Lemma 5 by Immonen et al. (2023).
D (G,, D(G,).
Figure 8 (in the Appendix) illustrates two graphs G and G' that are indistinguishable by degree-based filtration func- tions. Note that in contrast, the Laplacian eigenspectra are distinct, allowing LPE-based methods to distinguish them. Next, we present a learnable approach that combines PH, PE, and graph neural networks (GNNs), which are the most widely used methods for learning on graphs.
Lemma 3.3. Let (GG) = {poleev(Gr denote the node embeddings of G from any base PE method. For any G1 and G2. if (GG) (G2),, then there exists a function f such that (G1, ((G)).) # (G2, f).
In Propositions 3.4 and 3.5, show there pairs of graphs that LapPE, random walk PE and distance encodings cannot distiguish but their combination with PH can. Im- portantly, together with Lemma 3.3, these results show that combining PH and PE is strictly more expressive than the base PE methods alone.
4. Persistence-informed positional encoding
In this section, we introduce Persistence-infonn informed positional encoding (PiPF, in short). PiPE unifies PE with PH, via GNN-based message passing networks and leverages de- tailed topological information of graphs. Here, we also analyze the expressivity properties of our proposal.
Proposition 3.4. Let (G) be either the Laplacian PEs with the lowest eigenpairs or the random walk PEs with walks of length k of G. Then, there exist G1 # G2 and filtration function such that (G. (G2 and (G1, (x(G)),f) # (G2, (x
Let Pa IR be a base PE (e.g., Laplacian PE) for node E V(G). We propagate positional embeddings over the graph following a vanilla message- message-passing procedure while computing the topological features. In particular, starting from ph = Pv for all v, we recursively update the positional embeddings
To illustrate this limitation, consider graphs G and G' in Figure 4. Despite having different connected components, they share identical RW-based Φ; for some k. demonstrat- ing RW-based PE's inability to determine the number of connected components.
f.
VG(D) (r:)o.
(3)
r Σ ( (A, fr)l
(4)
e:VEe
Proposition 3.5. Let (G) denote the distance encodings of G considering the d-sized node subset E (G). Then, there exist G1 # G2 and I such that $ (G1)
2+1 = Updf( 40
P
(5)
Agge (r f1 P.) (uE((()))))
5

---

Positional Encoding meets Persistent Homology Graphs
ZINC
Alchemy
MOLTOX21
MOLPCBA
0.82
0.30
0.20
0.80
0.25
0.15
AUC ROC
0.78
MAE
0.10
0.76
0.20
0.74
0:05
0.15
0.00
0.70
0.10
PEG
DE
RW SignNet SPE
PEG
DE
RW SignNet SPE
LapPE
DE
RWPE
LapPE
DE
RWPE
None
PiPE (VC)
PiPE (RePHINE)
Figure 5: Test MAE for drug molecule property prediction and graph classification results. Integration of PiPE into backbone message passing schemes leads to better downstream performance across diverse datasets. For more details, Table 5.
where Agg, is an order-invariant function, Updz is an arbitrary update function at layer c, and v and f denote diagram vectorization schemes, detailed in the following.
embedding Pool((r,") f- r Je,w) and send the resulting vec- tor through an MLP to achieve graph-level predictions Pool is either a global mean or addition operator.
Computing topological features. We use the positional encodings {pt Ju as node features to compute persistence diagrams Dj. D induced by filtering function ft followed by the vectorization procedures Vy Vf at each layer &. We followed the vectorization schemes in (Horn et al., 2022). To obtain node features from Do we note that [Dol = nt, and, therefore, we can define a bijection between and Do- Thus, we apply an MLP to each tuple to obtain the node- level features y..0 For dimension 1, we first employ the edge-level vectorization V (e.g.. MI.P) and then aggregate the edge embeddings obtain node-level ones rf. Note that, although |D1| is equal to the number of basic cycles (not to the number of edges), we can use dummy tuples for edges that have not created a cycle. Details of this procedure can be found in Appendix A.4 in (Horn et al., 2022). We r as the topological embedding associated with the base PE p
Figure describes the architectural steps of our method. Im- portantly, our framework versatile and can accommodate any selection of base (initial) positional encoding well as various topological descriptors (e.g., RePHINE) and GNNs.
4.1. Analysis
We now report results the expressiveness of LPE and RW-based PiPE. All proofs are in Appendix C.
In Propositions 4.1 and 4.2, we show that PiPE is strictly more expressive than simple PH and LSPE a popular method for learnable positional encodings using GNNs.
Proposition 4.1 (LPE-based PiPE > LPF-based LSPE). Consider the space of unattributed graphs. Let Q and J be the classes of PiPE and LSPE models using Laplacian PE as base encoding, respectively. Then, strictly more expressive than in distinguishing non-isomorphic graphs.
refer to (. 0
Integration with backbone GNNs. A simple strategy to in- tegrate PiPE with the backbone GNNs over node features is to combine (e.g., concatenate or add) them with GNN node embeddings {. Then, the resulting GNN's message- passing procedure at layer becomes
Proposition 4.2 (LPE-bbsed PiPE > PH + LPE). Consider the space of unattributed graphs. Lel Q be the class of PiPE models using Laplacian PE (LPE) base encoding. Also, let PH be the class of models that computes persistence diagrams (dimensions O and 1) from filtrations induced by vertex colors derived from LPE. Then, Q is strictly more ex- pressive than PH in distinguishing non-isomorphic graphs.
+ = Upd (he, Agge((g uE ((O)))))) V V.
where b = [= |1 1 r || 1...
Next, Proposition 4.3 describes a shortcoming of random walk-based PiPE: its inability to distinguish certain graph pairs that are separable by 3-WL.
Achieving class predictions. For graph classification, as usual, apply readout function (e.g., sum mean) to the embeddings at the last GNN layer, T., to obtain graph-level embedding IG, i.c., IG = Readout (fx, he)) Similarly to LSPE, we can also concatenate positional embeddings p with node representations zi before applying the readout function. Then, we combine FG with global topological
Proposition 4.3 (RW-based PiPE and 3-WL). There exists certain pair of con-ioomopppic unattributed graphs, which can be distinguished by 3- WL but RW-based PiPE cannot.
Figure 4 illustrates graphs and K' that are 2-WL equiva-
6

---

Positional Encoding meets Persistent Homology Graphs
Assay (ID-Test)
Assay (00D-Test)
Scaffold (ID-Test)
Scaffold (OOD-Test)
0.96
0.74
0.74
0.90
0.72
0.94
AUC-ROC
0.92
0.70
0.85
0.68
0.90
0.80
0.66
0.66
0.88
0.75
0.64
PEG
SignNet BasisNet
SPE
PEG
SignNet BasisNet
SPE
PEG
SignNet BasisNe:
SPE
PEG
SignNet BasisNet
SPE
None
PIPE (VC)
PIPE (RePHINE)
Figure 6: AUC-ROC (1) results for DrugOOD Benchmark. better scores for OOD-Test. For more details, see Table 7.
PiPE outperforms the competing baselines in achieving
lent, sharing identical node degrees and RW-based 4: for some k. Despite their structural differences, the PE method fail to distinguish between them.
performance of PiPE on synthetic tree-structured tasks.
Implementation. PiPE is implemented in PyTorch (Paszke et al., 2019) with same training configuration as the compet- ing baselines. More details in Appendix D.
Since PiPE combines GNNs with PH, we also provide result on the connection between color-separating sets and the &- WL hierarchy. Proposition 4.4 shows that whenever F-FWI. distinguishes two graphs, there exists a filtration that produces O-dim persistence diagrams for these graphs, or equivalently, there is color-separating set. We also provide explicit coloring for the graphs based the stable colorings from k-FWL.
Baselines. To empirically demonstrate the effectiveness of our method, we compared against existing positional encoding approaches on various tasks. We utilized several established baselines for graph tasks: (i) No positional en- codings, (ii) SignNet & BasisNet (Lim et al., 2023), (iii) PEG (Wang et al., 2023), (iv) LapPE & RWPE (Dwivedi et al., 2022), (v) SPE (Huang et al., 2024) and (vi) DE (Li et al., 2020). In order to compute the topological descriptors via persistence homology, we utilized (i) Vertex Color (VC) (Horn et al., 2022) and (ii) RePHINE (Immonen et al., 2023) as learnable methods compute the diagrams. For the syn- thetic tree tasks, we compared our method against these positional encoding approaches: (i) Sinusodial (Gehring et al., 2017). (ii) Relative (Shaw et al., 2018) and (iii) RoPE (Su et al., 2024) positional embedding methods.
Proposition 4.4. If k-FWL deems two attributed graphs (G, x) and (G', x') non-isomorphic with stable colorings C. V + N and Ch V + N, then Q 0 is trivial color-separating set for the graphs (G, H) and (G', ø'), with d(u) = hash( (Coo : u U. E V*) V Vueu V and H' F'(u) = hash(fC' (v) U.EUEEVV VuEV.
We note that Proposition 4.4 strengthens the results by Ballester & Rieck (2024) (Proposition 5) in two ways. First, we show how to use k-FWL to find a specific filtering func- tion that gives separable diagrams - in fact, given the pro- posed coloring, separability holds for any injective vertex- color function. Also, with our scheme, even O-dim diagrams are different, while Proposition in (Ballester & Rieck, 2024) provides that k - 1 or k-dim diagrams are different.
Table 1: Unattributed Graphs. The table below reports accuracy, with the numbers in parentheses indicating the number of graph pairs in each dataset.
Dataset
PH
PH+LLP
PiPE
Basic (60)
0.03
0.10
0.72
Regular (50)
0.00
0.15
0.40
5. Experiments
Extension (100)
0.07
0.13
0.67
CFI (100)
0.03
0.03
0.03
We assess the performance PiPE on diverse and challeng- ing tasks. In Section 5.1, we evaluate the expressivity of persistent homology and its combination with positional coding unattributed graphs. In Section 5.2, we assess its offectiveness in predicting properties of drug molecules and performing real-world graph classification. In Section 5.3 we evaluate PiPE's robustness by benchmarking its ability to handle domain shifts in data, and Section 5.4 shows the
Distance (20)
0.00
0.00
0.05
5.1. Expressivity on Unattributed Graphs
We conducted an empirical study to assess the expressivity of standard O-dim PH and PH+LPE on the BREC dataset (Wang Zhang, 2023), which evaluates GNN expressive-

---

Positional Encoding meets Persistent Homology on Graphs
ness across four graph categories: Basic, Regular, Extension, and CFI. Table presents the accuracy results for each graph category. The findings indicate that PH+LPE demonstrates greater expressiveness than standard PH, corroborating our theoretical analysis.
Interestingly, all models achieve similar performance on the in-distribution test set (ID--Test). However, performance drops for all methods on the out-of-distribution test set (OOD-Test). This highlights the challenge of generalizing to unseen data. Our method exhibits the best performance on the OOD-Test set. This demonstrates the effectiveness of our approach in capturing features relevant for general- izability, even when encountering unseen data distributions.
5.2. Drug Molecule Property Prediction and Graph Classification
We used the ZINC (Dwivedi et al., 2023) and Alchemy (Chen et al., 2019) datasets, containing quantum mechan- ical properties of drug molecules, with the aim to predict these properties. We followed the data preparation strat- egy of Huang al. (2024) with GIN as the base model for a fair comparison. For graph classification, we used OGBG-MOLTOX21 (Huang et al., 2017; Wu et al., 2018), a multi-task binary classification dataset comprising of 7.8k molecular graphs for toxicity prediction across 12 measure- ments; OGBG-MOLHIV (Hu et al., 2020), which contains 41k molecular graphs with a binary classification task for HIV activity; and OGBG-MOLPCH, (Wang et al., 2012; Wu et al., 2018) 8), a large-scale dataset with 437.9k graphs for predicting molecular activity or inactivity across 128 bioassays. We followed the experimental setup of Dwivedi et al. (2022), using Gated-GCN as the base model.
5.4. Synthetic Tree Tasks
We explored three synthetic tree-tasks involving binary branching trees: (i) Tree-copy. analogous to sequence copy-task; (ii) Tree-rotation, where the output tree mirrors the input, interchanging left and right children; and (iii) Algebraic expression reduction, where input trees represent complex expressions from the cyclic group C3, and the model is tasked with performing a single reduction step, i.e., reducing all depth-1 I subtrees into leaves. We followed the data preparation strategy of Kogkalidis al. (2024) and utilized same splits and hyperparameters.
Improved Performance on Tree Tasks. Table 2 presents the Perplexity (PPL) scores for all methods on the synthetic tree tasks. Our method consistently achieves lower PPL scores compared to the baseline across all tasks. This indi- cates that incorporating our approach on top of a positional encoding method leads improved performance on down- stream tasks. This finding highlights the versatility of our method, demonstrating its effectiveness across various data domains, including those involving tree-structured data.
Superior Results. Figure 5 and Table present the test Mean Absolute Error (MAE) for property predic- tion tasks (ZINC, Alchemy) and graph classification tasks (OGBG-MOLTOX21, OGBG-MOLPCBA, across various PH-vectorization schemes. Additionally, Table 6 also re- ports the ROC-AUC results on the OGBG-MOLHIV dataset. We observe that incorporating PiPE into PE schemes con- sistently outperforms baselines, particularly on ZINC and MOLPCBA, achieving notable improvements. Integrating PiPE with the PEG baseline yields the largest MAE reduc- tion on ZINC, highlighting approach's 's ability to capture richer graph representations.
6. Ablations
Identity Filtrations. We investigated the impact of learn- able versus non-learnable filtrations in vertex-color (VC) PH method. We compared using positional encodings directly via identity filtration function (VC-I), to define filtra- tion values for computing persistence diagrams, against a learned filtration function. Figure 7 shows the results along- side comparisons with learnable variants (VC & RePHINE) on ZINC dataset. We observe that using the positional encodings as filtration values to compute the persistence di- agrams improves the performance. This is further enhanced by learning a parameterized filtration function, highlighting the method's 's increased expressiveness.
5.3. Out of Distribution Prediction
To evaluate method's 's ability to handle domain shifts, we used DrugOOD, an diitrii-iitiiitoo (OOD) benchmark (Ji et al., 2023). We focused on the ligand-based affinity prediction task to assess drug activity. DrugOOD intro- duces two types of distribution shifts: (i) Assay, denoting the assay to which the data point belongs, and (ii) Scaffold, representing the core structure of molecules. The DrugOOD dataset is divided into five parts: training set, in-distribution (ID) validation/test sets, and out-of-distribuiis (OOD) val- idation/test sets. The OOD sets have different underlying distributions compared to the ID sets, allowing us to assess generalizability to unseen data.
Runtime Comparison. We conducted an ablation study to investigate the computational cost of our method. We mea- sured the time (in seconds) per epoch for different models on a single V100 GPU. The results for various PH and PE methods are shown in Figure/ 7 over the Alchemy dataset. We observe that SPE introduces additional computational overhead due to its more intensive computations compared to the simpler methods such as PEG. However, PiPE only
Superior OOD Generalizability, Figure 6 summarizes the AUC-ROC scores for different methods over test datasets.
8

---

Positional Encoding meets Persistent Homology Graphs
Identity Filtrations
Computational Time
and Aatos Erkko Foundation project (grant 7001703) on "Biodesign: Use of artificial intelligence in enzyme design for synthetic biology", and Finnish Center for Artificial In- telligence FCAI (Flagship programme). We acknowledge CSC IT Center for Science, Finland, for providing gener- ous computational resources. YV acknowledges the support from the Finnish Foundation for Technology Promotion (grant 10477).
0.20
20
0.15
Seconds
MAE
10
0.05
0.00
PEG
SPE
PEG
SPE
Impact Statement
(MC-))
(VC)
(RePHINE)
Graph representation learning (GRL) is an area of active re- search, and finds use in important applications such as drug discovery. Our work advances the state of GRL, and thus opens exciting avenues. We are not aware of any specific negative societal consequences of this work.
Figure 7: Identity filtrations and Runtime Comparisons.
Table 2: Synthetic Tree tasks. Perplexity (PPL) + syn- thetic tree tasks, where B stands for breadth and D for depth.
C3
Reorder
Copy
References
Scheme
Persistence
B
D
B
D
D
Babai, L. Lectures on graph isomorphism. In
None
2.47
2.90
6.93
7.11
1.14
5.76
Mimeographed lecture notes, 1979.
Sinusodial
VC
2.42
2.75
6.80
7.21
1.10
5.47
RePHINE
2.33
2.64
6.75
7.51
1.00
5.32
Balcilar, M., Héroux, P., Gauzere, B., Vasseur, P., Adam, S., and Honeine, P. Breaking the limits of message passing graph neural networks. In International Conference on Machine Learning (ICML), 2021.
None
1.85
2.62
6.00
7.72
1.10
5.94
Relative
2.42
5.92
8.11
1.01
5.04
RePHINE
1.70
2.31
6.12
7.97
1.00
4.82
None
1.84
2.52
4.93
6.63
1.85
3.17
RoPE
VC
1.65
1.94
4.76
5.24
1.14
2.35
RePHINE
1.59
1.77
4.49
4.70
1.00
2.05
Ballester, R. and Rieck, B. On the expressivity of persistent homology in graph learning. Learning on Graphs (LoG), 2024.
adds a slight overload over the base method.
Ballester, R., Hernández-Gareía, P., Papillon, M., Battiloro, C., Miolane, N., Birdal, T., Casacuberta, C., Escalera, S., and Hajij, M. Attending to topological spaces: The cellular transformer. 2024.
7. Conclusion and Limitations
We highlight the incomparability of positional encoding and persistent homology methods. Building on these insights, we introduce "Persistence-infomes informed Positional Encoding" (PiPE), a novel method that unifies the power of PH with general positional encoding methods. We theoretically ana- lyze PiPE's expressive power and characterize its capabil- ities within the &L hierarchy. Our extensive empirical evaluations across diverse tasks demonstrate PiPE's effec- tiveness, showing significant improvements over existing methods. PiPE incurs computational overhead due to the cost of computing persistent homology (PH) embeddings. Moreover, combining message passing with persistence- augmented node representations may result in graph-level representations that are not commutation-invaiiann tionally, current approach is limited to 1-dimensional simplicial complexes.
Belkin, M. and Niyogi, P. Laplacian eigenmaps for di- mensionality reduction and data representation. Neural Computation, 15:1373-1396, 2003.
Brilliantov, K., Souza, A., and Garg, V. Compositional pac-bayes: Generalization gnns with persistence and beyond. Advances in Neural Information Processing Systems (NeurIPS), 2024.
Bronstein, M. M., Bruna, J., LeCun, Y., Szlam, A., and Van- dergheynst, P. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34, 2017.
Addi-
Brouwer, A. E., Haemers, W. H., Brouwer, A. E., and Haemers, W. Distance-regular graphs. Springer, 2012.
Acknowledgements
This work has been supported by the Research Council of Finland under the HEALED project (grant 13342077), Jane
Carriere, M., Chazal, F., Ike, Y., Lacombe, T., Royer, M., and Umeda, PersLay: Neural Network Layer for

---

Positional Encoding meets Persistent Homology on Graphs
Persistence Diagrams and New Graph Topological Signa- tures. In Artificial Intelligence and Statistics (AISTATS), 2020.
Hajij, M., Zamzmi, G., and Cai, X. Persistent homol-
ogy and graphs representation learning. arXiv preprint arXiv:2102. 12926,, 2021.
Cesa, G. and Behboodi, A. Algebraic topological networks via the persistent local homology sheaf. arXiv preprint arXiv:2311.10156, 2023.
Hamilton, W., Ying. 7 and Leskovec, J. Inductive repre- sentation learning on large graphs. Advances in neural information processing systems (NeurIPS), 2017.
Chen, G., Chen, P., Hsich, C.-Y., Lee, C.-K., Liao, B., Liao, R., Liu, W., Qiu, J., Sun, Q.. Tang, J., et al. Alchemy: A quantum chemistry dataset for benchmarking ai models. arXiv e-print :1966 094,,, 2019.
Hensel, F., Moor, M., and Rieck, B. A survey of topolog- ical machine learning methods. Frontiers in Artificial Intelligence, 4, 2021.
Horn, M., De Brouwer, E.,, Moor, M., Moreau, Y., Rieck, B., and Borgwardt, K. Topological graph neural networks. In International Conference on Learning Representations (ICLR), 2022.
Cranmer, M. D., Xu, R., Battaglia, P., and Ho, S. Learning symbolic physics with graph networks. arXiv e-print 1909.05862, 2019.
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:221 18-22133, 2020.
Dudzik, A. J., von Glehn, T., Pascanu, R., and Velickovic, Asynchronous algorithmic alignment with cocycles. In Learning on Graphs Conference (LoG), 2023.
Dwivedi, V. P. and Bresson, X. A generalization of trans- former networks to graphs. arXiv e-print::0122096699, 2020.
Huang, N. T. and Villar, S. A short tutorial on the weisfeiler-
lehman test and its variants. In ICASSP 2021-2021 I IEEE International Conference on Acoustics, Speech and Sig- nal Processing (ICASSP). IEEE, 2021.
Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio. Y., and Bres- son, X. Graph neural networks with learnable structural and positional representations. In International Confer- ence on Learning Representations (ICLR), 2022.
Huang, R., Xia, M., Nguyen, D., et al. Editorial: Tox21
challenge to build predictive models of nuclear receptor and stress response pathways as mediated by exposure environmental toxicants and drugs. Front. Environ. Sci, 5, 2017.
Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Benchmarking graph neural networks. Journal of Machine Learning Research, 24, 2023.
Huang. Y., Lu, W., Robinson, J., Yang, Y., Zhang, M., Jegelka, S., and Li, P. On the stability of expressive positional encodings for graph neural networks. 2024.
Edelsbrunner, Letscher, and Zomorodian. Topological per- sistence and simplification. Discrete & Computational Geometry, 28, 2002.
Immerman, N. and Lander, E. Describing graphs: A first- order approach to graph canonization. Springer, 1990.
Edelsbrumner, H. and Harer, J. Computational Topology Introduction. American Mathematical Society, 2010.
Immonen, J., Souza, A., and Garg, V. Going beyond persis- tent homology using persistent homology In Advances in Neural Information Processing Systems (NeurIPS), 2023.
Eliasof, M., Frasca, F., Bevilacqua, B., Treister, E., Chechik, G., and Maron, H. Graph positional encoding via ran- dom feature propagation. In International Conference on Machine Learning (ICML). PMLR, 2023.
Jha, K., Saha, S., and Singh, H. Prediction of protein- protein interaction using graph neural networks. Scientific Reports, 12, 2022.
Freeman, L. The development of social network analysis. A Study in the Sociology of Science, 1, 2004.
Ji, Y., Zhang, L., Wu, J., WU, B., Li, L.., Huang, I.-K., Xu, T., Rong. Y., Ren, J., Xue, D., et al. Drugood: Out-of- distribution dataset curator and benchmark for ai-aided drug discovery-a focus on affinity prediction problems with noise annotations. In Association for the Advance- ment of Artificial Intelligence (AAAI). 2023.
Gehring, J., Auli, M., Grangier, D., Yarats, D., and Dauphin, Y. N. Convolutional sequence to sequence learning. In International conference on machine learning (ICML), 2017.
Gilmer, J.. Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. In International Conference on Machine Learning (ICML), 2017.
Jurss, J., Jayalath, D. H., and Velickovic, P. Recursive al- gorithmic reasoning. In Learning on Graphs Conference (LoG), 2023.
10

---

Positional Encoding meets Persistent Homology Graphs
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Sanchez-Gonzalez, A., Godwin, J., Pfaff, T., Ying, R., Leskovec, J., and Battaglia, P. W. Learning simulate complex physics with graph networks. In International Conference on Machine Learning (ICML). 2020.
Kogkalidis, K., Bernardy, J.-P., and Garg, Algebraic positional encodings. Advances in Neural Information Processing Systems (NeurIPS), 2024.
Sato, R., Yamada, M., and Kashima, H. Random features strengthen graph neural networks. In SIAM International Conference on Data Mining (SDM), 2021.
Kreuzer, D., Beaini, D., Hamilton, W., Letourneau, V., and Tossou, Rethinking graph transformers with spectral attention. Advances Neural Information Processing Systems (NeurIPS), 2021.
Satorras, G.G., Hoogeboom, E., and Welling, M. E(n) equiv- ariant graph neural networks. In International Conference on Machine Learning (ICML), 2021.
Li, P., Chien, I., and Milenkovic, O. Optimizing general- ized pagerank methods for seed-expansion community detection. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE Transactions on Neural Networks, 20, 2009.
Shaw, P., Uszkoreit, J., and Vaswani, A. Self-attention with relative position representations. Nations of the Americas Chapter of the Association for Computational Linguistics (NAACL), 2018.
Li, P., Wang, Y., Wang, H.,, and Leskovec, J. Distance en- coding: Design provably more powerful neural networks for graph representation learning. Advances Neural Information Processing Systems (NeurIPS), 2020.
Stokes, M., Yang, K., Swanson, K., Jin, W., Cubillos-Ruiz, A., Donghia, N. M., MacNair, C. R., French, S., Carfrae, L. A.,
Lim, D., Robinson, J., Zhao, L.,, Smidt, T., Sra, S., Maron, H., and Jegelka, S. Sign and basis invariant networks for spectral graph representation learning. International Conference on Learning Representations (ICLR), 2023.
Z., et al. A deep learning approach to antibiotic discovery. Cell, 180, 2020.
Su, J., Ahmed, M., Lu, Y., Pan, S., Bo, W., and Liu, Y. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, 568, 2024.
Maskey, S., Parviz, A., Thiessen, M., Stark, H., Sadikaj, Y., and Maron, H. Generalized laplacian positional en- coding for graph representation learning. arXiv preprint arXiv:2210.15955 2022.
Van Dam, E. R. and Haemers, W. H. Which graphs are determined by their spectrum? Linear Algebra and its applications, 373, 2003.
Morris, C., Ritzert, M., Fey, M.. Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In Associa- tion for the Advancement of Artificial Intelligence (AAAI), 2019.
Vaswani, A., Shazeer, N.. Parmar, N., Uszkorcit. J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. At- tention is all you need. Advances in neural information processing systems (NeurIPS), 2017.
Morris, C., Lipman, Y., Maron, H., Rieck, B., Kriege, N. M.,, Grohe, M., Fey, M., and Borgwardt, K. Weisfeiler and leman go machine learning: The story so far. The Journal of Machine Learning Research, 24, 2023.
Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. Interna- tional Conference on Learning Representations (ICLR), 2018.
Nikolentzos, G., Chatzianastasis, M., and Vazirgiannis, M. What do gnns actually learn? towards understanding their representations. arXiv preprint arXiv:2304. 10851, 2023.
Verma, Y. and Jena, S. Jet characterization in heavy ion collisions by ged-aware graph neural networks. arXiv preprint arXiv: 14906, 2021.
Paszke, A., Gross, S., Massa, F. Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. Pytorch: An imperative style, high-performance deep learning library. Advances neural information processing systems (NeurIPS), 2019.
Verma, Y., Souza, A. H., and Garg, V. Topological neural networks go persistent, equivariant, and continuous. In International Conference on Machine Learning (ICMI.), 2024.
Rosen, P., Hajij, M., and Wang, B. Homology-preserring multi-scale graph skeletonization using mapper on graphs. In 2023 Topological Data Analysis and Visualization (TopolnVis)). IEFE, 2023.
Wang. H., Yin, H., Zhang, M., and Li, P. Equivariant and stable positional encoding for more powerful graph neu- ral networks. In International Conference on Learning Representations (ICLR), 2023.

---

Positional Encoding meets Persistent Homology on Graphs
Wang, M., HU, Y., Huang, Z., Wang. D., and Xu, Persis tent local homology in graph learning. Transactions Machine Learning Research, 2024.
Wang, and Zhang, M. empirical study of realized gnn expressiveness. arXiv preprint arXiv:2304 077002 2023.
Wang, Y., Xiao, J., Suzek, T. O., Zhang, J., Wang, J., Zhou, Z., Han, L., Karapetyan, K., Dracheva, S., Shoemaker, B. A., et Pubchem's bioassay database. Nucleic acids research, 40, 2012.
Weisfeiler, B. and Leman, A. The reduction of graph to canonical form and the algebra which appears therein. nti, Series, 2, 1968.
Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Ge- niesse, C., Pappu, A. S., Leswing, K., and Pande, V. Moleculenet: a benchmark for molecular machine learn- ing. Chemical science, 9, 2018.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations (ICIR), 2019.
Yan, Z., Zhao, Q., Ye, Z., Ma, T., Gao, L., Tang, Z., Wang, Y., and Chen, C. Enhancing graph representation learning with localized topological features. Journal of Machine Learning Revearch, 1-65):133,, 2025.
Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T--.. Do transformers really perform bad for graph representation? Advances in Neural Information Processing Systems (NeurIPS), 2021.
Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W. L., and Leskovec, J. Graph convolutional neural networks for web-scale recommender systems. In In- ternational Conference on Knowledge Discovery & Data Mining (KDD), 2018.
You, J., Ying, R., and Leskovec, J. Position-aware graph neural networks. In International Conference on Machine Learning (ICML), 2019.
12

---

Positional Encoding meets Persistent Homology on Graphs
A. Related works
Graph positional encodings. Positional encodings enhance representations in Graph Neural Networks (GNNs) (Gilmer et al., 2017; Xu al., 2019: Velickovic et al., 2018) by incorporating relational information between nodes based on their positions. Several approaches have been developed to achieve this, including Laplacian- bbased methods that utilize the graph laplacian (Dwivedi et al., 2022; Kreuzer et al., 2021; Maskey et al., 2022; Lim et al., 2023; Wang et al., 2023; Huang et al., 2024), random walk-based techniques that leverage walks on graphs (Dwivedi et al., 2022; Eliasof et al., 2023), and SereRank-inspirees approaches that compute auxiliary distances (Ying et al., 2021; Li et al., 2020), However, these methods partition the Laplacian cigenvaluud/iieenvecoor space and utilize only the partitioned cigenvaluesseegeenvecoos disregarding the valuable information contained in the remaining eigenvalues and eigenvectors. To address this limitation, we propose complementing the existing approaches with topological descriptors based on persistent homology, which can capture additional structural information from the graph.
Persistent homology on graphs Persistence homology methods (Horn et al., 2022; Carriere et al., 2020; Immonen et al., 2023; Rosen et al., 2023; Hajij et al., 2021) from topological data analysis have made rapid strides, providing topological descriptors that augment GNNs (Cesa & Behboodi, 2023; Verma et al., 2024) with persistent information to obtain more powerful representations, enhancing the expressivity (Ballester & Rieck, 2024; Wang et al., 2024; Yan al., 2025) and generalizability (Brilliantov al., 2024). However, these methods have not been analyzed in regards with positional encodings in graphs, and the unification of these topological descriptors with positional encodings remains an unexplored frontier.
B. WL Tests
The Weisfeiler-Leman test (L-WL), also known as the color refinement algorithm (Weisfeiler & Leman, 1968), aims to determine if two graphs are isomorphic. It does by iteratively assigning colors to nodes. Initially, nodes receive labels based on their features. In each iteration, nodes sharing the same label get distinct labels if their sets of similarly labeled neighbors differ. Termination happens when label counts diverge between graphs, indicating non-isomorphism.
Due to the shortcomings of the 1-WL in distinguishing non-isomorphic graphs, Babai (1979); Immerman & Lander (1990) introduced a more powerful variant known as k-dim (folklore) Weisfeiler-Leman algorithm. In this approach, k-FWL colors subgraphs instead of a single node. Specifically, given a graph G, it colors tuples from V(G)* for h 2 instead of nodes and defines neighborhoods between these tuples. Formally, let G be graph, and let k 2 2. If E V(G)* then G[v] is the subgraph induced by the components of v, where the nodes are labeled with integers from {1. (1...... k} corresponding to indices of v.
In each iteration i 2 0, the algorithm computes a coloring C+ V(G)* + N. and in the initial iteration (i = 0) two tuples v and w in * get the same color if the map 8; + wi induces an isomorphism between G[v] and G[w]]. For > 0, the algorithm proceeds as,
C (+ = RELABEL
(6)
where the multi-set M(v) {Vi...., 2/-1, w. Us+1, w The oz (v, w) replaces the j-th component of the tuple v with the node w. Consequently, two tuples are adjacent or j-neighbors (with respect to a node w:) if they differ in the jth component (or are equal, in the case of self-loops). The algorithm iterates until convergence, i.e., (v) = C. (w) - C++ (v) = C (w) for all v, defining the stable partition induced by Ct², define C (v) = C (v). The algorithm then proceeds analogously to the 1-WL.
(v,,
C+ (ox w))
E V(G) and (v,
We say that the k-FWL distinguishes two graphs G and H if their color histograms differ. This means there exist a color c in the image of Ck: such that G and H have distinet numbers of node tuples of color c. Morris et al. (2023) also describe another variant of W-- known as k-dim (oblivious) WI. algorithm. The key distinction between the two lies in aggregating over different neighborhoods. In this case, for each position j E [k] we obtain a set of [V))) neighbors by replacing uy by w E V. A hash for position j is obtained using these colors, and the overall color is obtained by aggregating the hashed colors across all k positions (and e's color from previous iteration). We utilize the former variant throughout the paper and refer to Morris et al. (2023): Huang& & Villar (2021) for a thorough discussion of the algorithm and its properties.
13

---

Positional Encoding meets Persistent Homology on Graphs
C. Proofs
C.1. Proof of Proposition 3.1
S1. There exist G1 2G2 s.t.
= (( but (x(Gi) 2x(2) for all & > Bo(G1)
To prove this statement, we will provide a pair of graphs G1 and G2 with (G( Go( and (G1)) = Gz for which (G1) # (G2) with k (o(G)) 1. Naturally, if the graphs can be distinguished based the k smallest eigenpairs, they also distinguished based on any k >>> k'.
Consider the unattributed graph complexes K = (V, E) and K' = (V",'") as shown in Fig. 3, with associated positional encodings 4x () and 4x (K') based on = 3o K*) + lowest eigenvalue/vector pairs. Both K and K" has the same number of connected components i.e. (K( = Bo (K') = 1, and basis cycles (1(K) = (K() = 3. However, the
laplacian positional encoding based on k = (o(K) + lowest eigenvalues, for K and K" are
0..5
-0.32
0.37
0
0.50
0.32
0.17
0.62
0
0.53
0.37
0
(K)
(x') =
(7)
0.53
-0.17
-0.62
0.50
0.32
0.58
-0335
0.50
0.32
0.58
0.35
Hence, the positional encodings differ i.c. (K) + (x(K)).
S2 & S3. There exist G1 z G2 s.t. (G,) * B1 (G2), Bo(Gr) + Bo(G22 but (Gn) = (G2)
Similarly statement S1, here we proceed with a proof by example.
To prove this statement, we will provide pair of graphs G1 and G2 with Bo( # (G and B1 (G1) + (G for which 4 (G,) &x (G2) for some k.
Let K; denote the complete graph with nodes. Consider graph G K Ki K3 here K₁ K3 denotes a graph with two components comprising one isolated node and a triangle i.c. G)) n, ( = n/2. Also, consider G" = (K U Ki U K, U K1) - i.e., 4n/2 isolated nodes i.e. Bo(G") - 2n, (G') 0, shown in Figure 8. The A smallest cigenvalues corresponding to G' are all equal to with the identical constant eigenvector, when k: S n. Similarly, G" has the same cigenvalues with identical constant eigenvectors. However, the number of connected components and basis cycles in G and G' differ, i.e. (G) + (G') and Bo(G) # Bo(G")
C.2. Proof of Proposition 3.2
S1. There exist G₁ G2 s.t. Bo(G))= (( = (G2) (
but (b( A (G2) for all k > Bo(G1)
To prove this statement, we will provide a pair of graphs Gi and G2 with (C (G()2 and Bi (G1) Bi B1(G2) for which (G, * they are also distinguished based on any k > k.
(G2) for to = Bo(G,) + 1. Naturally, if the graphs can be distinguished based on the k' = Bo(Gi) +1,
Consider the unattributed graph complexes K = EV and K' = (V', , E') as shown in Fig. 3, with associated positional encodings & (K) and 4 (K') based on k = 3 (K) length random walk positional encodings, where (k) = 1. Both K and K' has the same number of connected components 8o (K) = (K') = 1, and basis cycles 31 (K) = 31 (K') = 3.
The positional encodings for both the graphs are,
0 0.41
0
0.33
0.41
0
0.50
0.44
0
0.33
(K)
(K')
(8)
0.44
0
0.50
0.41
0
0.41
0
0.41
0
0.41
Hence, the positional encodings differ i.e. & (K) + (K())) for = ()(() +
S2 & S3. There exist G1 # G2 s.t. (G.) # 31 (G2), (1) # GG but कx (Gn) (G2)
14

---

Positional Encoding meets Persistent Homology Graphs
K1 K3
Kt
C4
P4
G
G
Figure 8: Exemplar graphs for Propositions 3.1, 3,4 and 4.2.
Similarly to statement S1, here we proceed with a proof by example.
To prove this statement, we will provide a pair of graphs G1 and G2 with Bo + (6()2) and Bi( + Bi for which (G1) & (G2) for some k.
Let C2 denote the eyclic graph with i nodes. Consider graph G = C10 having ((G) = 1, = 1, and G' Cs U Cs (Figure 4) with (G") = 2, (G') 2, both having a total 10 nodes, with associated positional encodings $ (G) and (e(G")) based on k = 4 length random walk positional encodings. The positional encodings for both the graphs are
0.50
0.37
0.50
0.37
0 0.50
0.37
0.50
0.37
0
0.50
0.37
0.50
0.37
0
0.50
0.37
0.50
0.37
0 0.50
0
0.37
0
0.50
0
0.37
2R (G)
(G')
(9)
0 0.50
0
0.37
O
0.50
0
0.37
0 0.50
0
0.37
0
0.50
0
0.37
0
0.50
0
0.37
0.50
0.37
0 0.50
0.37
0.50
0.37
0 0.50
0.37
0.50
0.37
Hence, the positional encodings for both the graphs are same i... (G) (G'),,, but the number of connected components and basis eycle differ i.e. Bo(G) # (o(G") and (G) # (G').
C.3. Proof of Lemma 3.3
To prove Lemma 3.3, we need to show that the persistence diagram pairs obtained when using (G) and @(G") as vertex colors different. Importantly, Lemma 5 in Immonen al. (2023) states that the multiset of birth times of persistence tuples encodes the multiset of vertex colors in VC filtrations when using injective filtration functions.
Therefore, if we use (GG and (G22 as colors and adopt an injective filtration function, then the corresponding VC diagrams DO (G1, & () and DO (G2, ((G2), differ in their birth times since (G,,) * ((G)). This is agnostic to the chosen graphs and positional encoding.
C.4. Proof of Proposition 3.4
(1) Laplacian PE
To prove this statement, we will provide a pair of graphs G1 and G2 with for which (Gi) = (x for some k, but the persistence diagrams of G2 and G2 differ.
Let K; denote the complete graph with i nodes. Consider graph G = Un/ UK3 here Ki U K3 denotes graph with two components comprising one isolated node and triangle. Also, consider G = u U K1 K1 UK) i.c. 4n/2 isolated nodes, shown in Figure 8. The k smallest eigenvalues corresponding to G are all equal to 0 with the identical constant eigenvector, for & < n. Similarly, G' has the same eigenvalues with identical constant eigenvectors. Therefore, Laplacian PE relying on fixed & smallest eigenvalue/eigenvecor pairs, cannot distinguish these graphs.
By leveraging Theorem from Immonen et al. (2023), since the number of connected components in G and G' are different, they necessarily have different O-dimensional persistence diagrams i.c., D (G, (G), # DQ" @ f) for any injective color-filtration function over vertices and using (G) and & (G') as colors. This difference in persistence
15

---

Positional Encoding meets Persistent Homology Graphs
diagrams allows distinguish between the graphs despite their identical smallest eigenvalues and eigenvectors.
(2) Random Walk PE
Similarly to the above statement, here we proceed with proof by example.
Consider a graph G = C1o having (u(G) = 1, (G) = 1, and G' = Cs U Cs (Figure 4) with Bo(G") 2, (G)) both having a total 10 nodes, with associated positional encodings 4x (G) and (x()") based on k = length random walk positional encodings. The positional encodings for both the graphs are same i... 4x(G)
*x(G") as shown in Equation (9). However, the number of connected components (Bo) in G and G' differ. Hence, by leveraging Theorem I from Immonen al. (2023) and using the & initial colors will provide different O-dimensional persistence diagrams i.e. (G, Dx () + (G',, Px (G'),, f') for any injective separate these graphs.
function / over vertices. Hence, PH RW can
C.5. Proof of Proposition 3.6
(1) Laplacian PE
To prove this statement, we will provide a pair of graphs G1 and G2 for which (G,, D(G1),)) (D,, D(G2), f) for all f but have different diagrams (G1, (x(G)), = (G2, (x(G2), f) derived from LapPE. colors (G1) and (xi) for some and f.
Consider the unattributed graph complexes = EV and G' (V",E") as shown in Fig. with associated positional encodings (G) and (G") based on le lowest eigenvalue/vector pairs, for k (G) + 1, where Bo 1. Using degree the initial colors and adopting an injective filtration function f, we can have the following two scenarios: (i) a, and (ii) < a, where y = f 2) and = f(d = 3) where d denotes node degree. In both cases, the obtained diagrams for both G and G" are identical, i.e..
{(a, (a, xx (7,7)) ify>
DG,
(10)
{8 x (1), (1,)) < D' ((,,a), (7,7)) if {8
(11)
i
Thus, (G, D(G) = - PH relying on degree information cannot distinguish these graphs.
However, the Laplacian positional encodings for these graphs are different:
0.42
-0.88
0.37
0.35
0.42
0.18
0.37
0.35
- 0.26
0.39
- 0.29
-0.05
0.00
0.34
-0.19
-0.49
0.26
0.39
-0.29
-0.05
(G)
(G')
(12)
0.42
0.18
0.19
-0.99
0.42
-0.18
0.29
-0.55
0.26
-0.39
0.37
0.35
-0.00
-0.34
0.37
0.35
0.26
-0.39
0.29
0.05
By leveraging Theorem from Immonen al. (2023) and Lemma 3.3, using & as colors and adopting an injective filtration function, then the corresponding VC diagrams (G,, (G), and DD (G'), f) differ their birthtimes. This difference will help to distinguish between these graphs.
(2) Random Walk PE
Similarly to the above statement, here we proceed with a proof by example.
We follow the same proof for G and G' having the same 0- dim diagrams based on degree-base based filtration functions, as described in the previous statement.
16

---

Positional Encoding meets Persistent Homology Graphs
The associated RW positional encodings for both graphs differ i.e. @x(G) + xx for length, as shown in Equation (13).
0
0.50
0
0.35
0.50
0
0.35
0.04
0
0.50
0
0.35
0.50
0
0.35
0.04
0
0.41
0
0.28
0.41
0
0.28
0.04
0
0.44
0
0.31
0.44
0
0.31
0.04
0
0.41
0
0.28
0.41
0.28
0.04
(G)
Px (G')
(13)
0
0.50
0.35
0.44
0.31
0.04
0
0.50
0
0.35
0.41
0.28
0.04
0
0.41
0
0.28
0.50
0
0.35
0.04
0
0.44
0
0.31
0.50
0
0.35
0.04
0
0.41
0
0.28
0.41
0
0.28
0.04
Again, by leveraging Theorem from Immonen et al. (2023) and Lemma 3.3, using injective filtration functions on these colors leads to diagrams that differ in their birth times.
C.6. Proof of Proposition 3.5
To prove this statement, we will provide a pair of graphs G1 and G2 with for which 42(G1) = (a(GG2) for 1, but the persistence diagrams G and G2 differ.
Let Qj denote a hypercube graph with nodes. Consider graph G Q3 comprising of 2 nodes, with BG) 1. Also, consider G' Q2 Q2, with 3o(G") 2 consisting of two Q2 graphs, having total of 2 + 2 nodes Since, Q2 and Q3 are distance regular graphs (Brouwer al., 2012), both G and G' have the same DE-1 i.e. &a = 2a(G") for each node in the graph with 1. Therefore, distance encoding relying on shortest path distance, cannot distinguish these graphs.
By leveraging Theorem from Immonen et al. (2023), since the number of connected components in and are different i.e. (o(G) * Bo(G"), they necessarily have different O-dimensional persistence diagrams i.e., DG, (a(G), # (G", (a(G"), f) for any color-filtration function over vertices and initial colors.
C.7. Proof of Proposition 4.1
To prove this statement, suffices to show that i) PiPE subsumes LSPE for certain choices of Agg, Upd functions, and (ii) there exists a pair of graphs which cannot be separated by LSPE but PiPE can. Note that LSPE can be seen as GNN LPE, and consider unattributed graphs here.
PiPE subsumes LSPE
The message passing steps of PiPE shown below, where hy = [2 pt 1 +
2. Se(p!)
(14)
re
4.0 (A, 2)),
(15)
fl Σ (DD 2),
(16)
Pe
++ = UpdE'rr 111 Per
o .d) (E:((N))))) VVEV
(17)
#+1 Updž (he Agg/ (1h E N(b))) Voe V.
(18)
Consider the following choices for the Agg and Upd
Agg = Agg ag I.S.EE
m AggZ Aggz LSPE m
PiPE
Updž UpdR.LSPE m
Upd Upd LSPE o to
17

---

Positional Encoding meets Persistent Homology on Graphs
where Agg; P. and Upd are the aggregate and update functions used in LSPE, and m ?. , hi function that that masks out the topological embeddings r6.0 rrd every layer of the message-passing step. These choices for the functions will lead to the same message-passing dynamics of LSPE neglecting the topological features. Hence, this shows that PiPE subsumes LSPE.
are the masking
PiPE > LSPE Let C, denote a cycle graph with nodes without node attributes. Consider graph G = ==1 Ca. having 3n connected components and 12n nodes. Also, consider G' = - C U Co. having 12n nodes and 2n connected components. Since, G and G' have the same number of nodes and identical local neighborhoods, aggregate-combine GNN cannot distinguish them. Moreover, for I 12m, the & (G) = (G'). are same having identical constant eigenvector, LPE does not add any distinguishability power.
However, since the number of components in G and G' are different, they have different O-dimensional persistence diagram (G, Da (G), f) * (G',, &x f) for any filtration function and initial colors. This difference in persistence diagrams allows PiPE to distinguish between the graphs.
C.8. Proof of Proposition 4.2
To prove this, it suffices to show that i) PiPE subsumes PH + LPE, and (ii) there exists a pair of graphs which cannot be separated by PH + LPE but PiPE can.
PiPE subsumes PH+LPE We can write PiPE as GNN PH o LPE. Consider, the GNN to be an identity map, then it will reduce to PH o LPE. Hence, PiPE subsumes PH+LPE.
PiPE PH+LPE Let C, denote a cycle graph with nodes without node attributes and P; denotes a path graph with nodes without node attributes. Consider a graph G C4 and G' U2 (shown in Figure 8), which has connected components and 4n nodes. The k smallest laplcian cigenvalues corresponding G' and G' all equal to 0 with the identical constant eigenvector, where k < 4n, and both of the graphs consists of same number of connected components. Hence, by leveraging Theorem I from Immonen et al. (2023) the filtrations based on laplaician eigen value and vector pairs would correspond to the same O-dimensional diagram, i.e. D DG, (G) = DD ( /) for any filtration function and initial colors. Hence, Laplacian eigen spectra relying on prrtialdccommosstiion and relying on O-dim persistence diagrams would not be able to separate these two graphs.
However, the nodes in G and G' have different degrees, allowing GNNs (in PiPE) to distinguish these two graphs.
C.9. Proof of Proposition 4.3
To prove this, suffices to show that a pair of graphs that can be separated by 3- WL have the same random walk positional encoding & for k > O.
Consider the graph representation of pair of cospectral and 4-regular graphs K and K' (Van Dam & Haemers, 2003) from Figure 4, with the associated positional encodings & obtained via random walk PE for k = 4. These pair of graphs are 2-WL equivalent (Balcilar et al., 2021) i.e., these two graphs cannot be separated by 2-WL but 3- WL can separate them. The positional encodings for both the graphs are
0 0.25
0.62
0.14
0
0.25
0.93
0.14
0
0.25
0.62
0.14
0
0.25
0.62
0.14
0
0.25
0.62
0.14
0
0.25
0.93
0.14
0
0.25
0.93
0.14
0
0.25
0.93
0.14
0.25
0.93
0.14
0
0.25
0.93
0.14
(K)
(K')
(19)
0.25
0.62
0.14
0
0.25
0.62
0.14
0
0.25
0.62
0.14
0
0.25
0.62
0.14
0.25
0.93
0.14
0
0.25
0.62
0.14
0
0.25
0.62
0.14
0
0.25
0.62
0.14
0
0.25
0.93
0.14
0
0.25
0.62
0.14
Hence, the positional encodings for both the graphs are same i... (K) = o (K') with Bo(K) = Bo(K') = 1.Thus,
using positional encodings & as initial colors with an injectve filtration function will lead the same VC persistence
18

---

Positional Encoding meets Persistent Homology Graphs
diagrams, that is, (K, (K), (K', (,((K)) Thus, PiPE based random walk positional encodings cannot separate these graphs which be separated by 3-WL..
C.10. Proof of Proposition 4.4
Consider two attributed graphs G - E) and G² (V',E) with their corresponding coloring functions and x'. Assume these graphs are deemed non-isomorphic by k-FWL with stable colorings, Coo V N and C V + N.
Then we can use hash functions (u))
E E }*)) for all u E V and ('()) hash (v) V. E }* ) for all E V", to project the colorings from k-tuple of nodes to obtain node colors in the associated graphs (G) and (G" F'). Since, hash functions are injective in nature, and (G, and (G", ,x)) can be distinguished via k-FWI,, then there exists a tuple Vw E y such that (vo(Vv) * C% (v')) V v E V Then, any node in E Va (note that E V) will have color that not in nodes of V", i.e., M(v) + I' (u) for u E V". This will provide us with different node colors for the associated graphs (G and (G', Hence, by leveraging the definition of color-separating sets from Immonen et al. (2023), Q is trivial color-separating set for these graphs.
D. Implementation Details
Below are the implementation details. We trained all the methods on a single NVIDIA V100 GPU.
D.I. Drug Molecule Property prediction and Graph Classification
We adhered to the precise hyperparameters and training configuration outlined in Huang et al. (2024) for predicting drug molecule properties and Dwivedi et al. (2022) for classifying real-world graphs in our experiments. For graph classification, we used GaNed-GCN (Kipf & Welling, 2017) as our base model. To compute the Persistence Homology (PH) diagrams, we employed the learnable PH method proposed by Immonen al. (2023). The PH layers operated exclusively on the position encoding features of every layer with the following specified hyperparameters in Table 3.
Table 3: Default hyperparameters for RePHINE/VC method
Hyperparameter
Meaning
Value
PH embed dim
Latent dimension of PH features
64
Num Filt
Number of filtrations
8
Hiden Filtration
Hidden dimension of filtration functions
16
D.2. Out distribution Prediction
We adhered the precise hyperparameters and training configuration outlined in Huang et al. (2024) for Drug OOD benchmark. To compute the Persistence Homology (PH) diagrams, we employed the learnable PH method proposed by Immonen al. (2023). The PH layers operated exclusively on the position encoding features of every layer with the following specified hyperparameters in Table 3.
D.3. Synthetic Tree Tasks
We created the synthetic tree dataset by sampling random trees of maximum depths from discretized normal W/(7, 1) and followed similar training setup described in Kogkalidis et al. (2024). We adhered to the hyper-parameters and training configuration used in Kogkalidis et al. (2024) and employed the PH-layers on top of the position encoding features with an additional layer to update position encodings, using hyper-parameters described in Table
E. Tabular Results
19

---

Positional Encoding meets Persistent Homology Graphs
Table 4: Default hyperparameters for RePHINE/VC method
Hyperparameter
Meaning
Value
PH embed dim
Latent dimension of PH features
64
Num Filt
Number of filtrations
8
Hiden Filtration
Hidden dimension of filtration functions
128
Table 5: Test MAE results. Baselines are taken from Huang et al. (2024).
PE method
Persistence
ZINC 1
Alchemy |
None
None
0.1772 +00004
0.112 +0.001
PEG
None
0.1878 #0.012
0.114 #0.001
VC
0.1256 #0.017
0.112 #0.003
PiPE
RePHINE
0.1082 +00022
0.111 +0.004
DE
None
0.1356 #0.007
0.125 #0.003
VC
0.107 #0.013
0.119
PiPE
RePHINE
0.090 #0.009
0.116
RW
None
0.090 #0.005
0.121 #0.002
VC
0.075 10.011
0.113 #0.002
PiPE
RePHINE
0.070 #0.010
0.111 #0.002
SignNet
None
0.0853 #0.002
0.113 #0.002
VC
0.0687 #0.015
0.111 #0.002
PiPE
RePHINE
0.0632 +0.012
0.110 +0.002
SPE
None
0.0693 +0.004
0.108 +0.001
VC
0.0599 #0.010
0.105 #0.003
PiPE
RePHINE
0.0588 +0.007
0.103 +0.004
Table 6: (left) AUC-ROC results on OGBG-MOLHIV and (right) Test MAE results for TOGL..
PE method
Persistence
OGBG-MOLHIV
RW
None
0.762 +0.007
PE method
Persistence
ZINC
Alchemy
VC
0.781 10.005
PiPE
RePHINE
0.798 =0.004
RW
TOGL
0.080 +0.005
0.114 #0.002
PEG
TOGL
0.143 10.012
0.112 10.002
SPE
None
0.776 +0.004
SPF
TOGL.
0.062 +0.003
0.112 +0.002
VC
0.785 =0.005
PiPE
RePHINE
0.791 +0.003
20

---

Positional Encoding meets Persistent Homology Graphs
Table 7: AUC-ROC (t) results. DrugOOD Benchmark and baselines are taken from Huang al. (2024). PiPE outperforms the competing baselines in achieving better scores for OOD-Test.
Domain
PE method
Persistence
ID-Val
ID-Testt
OOD-Val f
OOD-Testf
None
None
92.92
92.89
71.02+0.79
71.68
PEG
None
92.51
92.57
70.86
71.98
VC
92.62+0.19
92.75+0.40
71.62+0..5
72.13
PiPE
RePHINE
92.42.0.27
92.35
72.0210.51
72.33
SignNet
None
92.2640.21
92.43 20.27
70.1640.55
72.27 20.97
VC
91.66.0.30
92.70 400.28
70.37+0.60
73.07
Assay
PiPE
RePHINE
91.36
92.15 15.22
69.47.1043
73.87
73.87_1132 L1.32
BasisNet
None
88.9641.35
89.42+1.0
71.19+0.72
71.1620.05
VC
90.36+0.66
90.78+1.00
72.76
72.98
PiPE
RePHINE
90.73+.0.45
91.10+.0.9
72.98
73.10
SPE
None
92.84+0.20
92.9440.11
71.26++0.2
72.53
VC
92.78
92.49 +0.58
71.78+0.00
1111
PiPE
RePHINE
92.16
93.12 12.122 10.91
72.33.10 1..93
73.11 11.07
None
None
96.56+0.10
87.95
79.07
68.00
PEG
None
95.6540.20
86.20
79.1740.29
69.15
VC
96.65 06.65
86.44+0.88 0.81
79.79+0.17
70.12=0.32
PiPE
RePHINE
96.9440.62
86.54+0.77
79.40+0.30
69.31+0099
SignNet
None
95.48
86.73 13.00.56
77.81
66.43 1.06
VC
93.03
83. 23.65.t0.777
74.73
67.37 67.37 1.12
Scaffold
PiPE
RePHINE
93.35
85.05 10079
75.05
68.03 1.34
BasisNet
None
85.80 L3.75
78. 44. 12.45
73.36 1::44
66.32 1.568
VC
86.10+2.10
79. 1.32
73.89+1.12
67. 67.11 1.111
PiPE
RePHINE
86.50
79.97 1.41
74.05
67.85..m $2.89
SPE
None
96.32
88. 12.
80.03
69.6440.49
VC
96.57 +0.13
88.37 +0.89
80.5640.00
70.92
PiPE
RePHINE
96.87+0.70
89.98
80.7640.55
70.46
21


Reviews:
[{"review_id": "74BcRarstE", "reviewer": "Reviewer_G9xp", "summary": "This paper introduces a novel method—Persistence informed by Positional Encoding (PiPE)—which unifies positional encoding (PE) with persistent homology to enhance the expressivity of graph neural networks . The authors provide both theoretical insights and empirical evidence, demonstrating that PiPE overcomes some of the limitations inherent in standalone PE or PH approaches. The method is evaluated on diverse tasks and the results are quite promising.\n\n\n## update after rebuttal", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your constructive feedback, and for appreciating the different aspects of this work. We address your comments below. \n\n> The paper could benefit from further clarification or additional examples to help readers less familiar with advanced topological concepts.\n\nThank you for an excellent suggestion. We will add a detailed background section in the appendix in the updated version.\n\n> Can the method be trivially extended to higher dimensional simplicial complexes?\n\nThank 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.\n\n[1] L.-H. Lim. Hodge Laplacians on graphs, SIAM Review 62.3 (2020): 685-715.\n\n[2] Z. Yan et al. Cycle Invariant Positional Encoding for Graph Representation Learning,  LoG, 2023. \n\n[3] F. Chazal et al. Convergence Rates for Persistence Diagram Estimation in Topological Data Analysis, JMLR 16 (2015): 3603-3635.\n\n[4] Y. Verma et al. Topological Neural Networks go Persistent, Equivariant, and Continuous, ICML, 2024.\n\nWe are grateful for your thoughtful feedback and suggestions. Thank you so much!", "claims_and_evidence": "The detailed theoretical analysis—including propositions, lemmas, and discussions around the expressive power of the method within the k-WL hierarchy—provides strong justification for the proposed approach. This solid theoretical grounding makes the work a valuable contribution to the graph learning literature.", "methods_and_evaluation_criteria": "The paper leverages a broad range of benchmarks—including both real-world and synthetic networks—alongside robust theoretical contributions, which add value to paper and help to convey the message", "theoretical_claims": "The theoretical claims included in the paper are robust and well-founded, though there remains a slight possibility I might have overlooked something.", "experimental_designs_or_analyses": "The experimental design is rigorous, incorporating a diverse set of real-world benchmarks and controlled synthetic tasks that thoroughly assess both the performance and generalizability of the proposed method. Moreover, detailed ablation studies and runtime analyses substantiate its scalability and performance improvements, reinforcing the empirical evidence supporting the approach.", "relation_to_broader_scientific_literature": "The paper has nice contributions to the graph representation learning literature and could be tied with works around how graph neural networks capture both structural and feature-based information [1].\n\n[1] What Do GNNs Actually Learn? Towards Understanding their Representations, Nikolentzos et al.", "essential_references_not_discussed": "Related work is sufficiently discussed.", "other_strengths_and_weaknesses": "The paper introduces a novel approach that creatively combines positional encoding with persistent homology, offering a fresh perspective on enhancing GNN expressivity. Its contributions are further solidified by a rigorous theoretical analysis that thoroughly underpins the proposed method. However, the approach comes with increased complexity and is currently limited to 1-dimensional simplicial complexes.", "other_comments_or_suggestions": "The paper could benefit from further clarification or additional examples to help readers less familiar with advanced topological concepts.", "questions_for_authors": "Can the method be trivially extended to higher dimensional simplicial complexes?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vIM6MTQTVc", "reviewer": "Reviewer_VeW5", "summary": "The paper proposes a novel graph neural network architecture combining existing positional encoding (PE) strategies with persistent homology (PH) and shows the resulting method is strictly more expressive than previous works using either PE or PH.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your thoughtful review. We address your concerns and incorporate your suggestions below. \n\n> could you numerate all the equations? That is very helpful for the reader and the reviewers in order to refer to them\n\nThank you for pointing this out. We will numerate all the equations in the revised version of the paper.\n\n>Proposition 3.1: what is the multiset of Laplacian positional encodings (LPE)? Can you define this more precisely?\n\nThe 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.\n\n> Proposition 3.1: is S2 and S3 true for any k?\n\nYes. 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.\n\n> 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?\n\nThanks 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.\n\nLet $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')$.\n\n> Sec 4. page 5, what is A in the equations? are $z_v$ scalars?\n\nThanks 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.\n\n> Sec 4. page 5, how are the diagrams turned into node or edge features?\n\nThank 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.\n\n[1] M. Horn et al. Topological Graph Neural Networks, ICLR, 2022.\n\n> Proposition 4.2: is the point of this proposition that computing PH at each layer is more expressive than doing it only once?\n\nThank 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.\n\n> Do I understand correctly that PH + LPE is essentially similar to a 1-layer PiPE to computed features used by a generic predictor?\n\nFor 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).\n\nWe 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!", "claims_and_evidence": "The theoretical claims seems to be supported by theoretical proofs and convincing experimental results.", "methods_and_evaluation_criteria": "See below.", "theoretical_claims": "I didn't verify the theoretical proofs.", "experimental_designs_or_analyses": "Different variations of the proposed method obtained by combining different PE strategies and different PH vectorization methods are evaluated on different graph datasets, consistently showing the improvements obtained by combining these strategies.", "relation_to_broader_scientific_literature": "The manuscript is well motivated and provides context in the related literature.\nI am quite familiar with graph deep learning and persistent homology / topological methods in this context, but it's not my main expertise, so I might be missing some related works.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper proposes and efficient and powerful method to strictly improve the expressivity of graph neural networks.\nThis seems a relevant paper for the scientific community.\n\nI think the main weakness of the manuscript is that it is at times unclear. See comments below.\nImproving clarify could help the adoption of the proposed method.", "other_comments_or_suggestions": "- could you numerate all the equations? That is very helpful for the reader and the reviewers in order to refer to them\n\n- Proposition 3.1:  what is the multiset of Laplacian positional encodings (LPE)? Can you define this more precisely?\n\n- Proposition 3.1:  is S2 and S3 true for any k?\n\n- Proposition 3.1:  what about S2 and S3 together? i.e. if b_0 and b_1 are both unequal, is it possible the eigenvectors are still equal?\n\n- Sec 4. page 5, what is A in the equations? are z_v scalars? \n\n- Sec 4. page 5, how are the diagrams turned into node or edge features? How are $\\Psi_i^l$ functions defined? This is briefly mentioned in the first paragraph in the next page but 1) it's not defined and 2) it would be beneficial to briefly define all variables in the equations when they are stated, to avoid confusing the reader. Because this step seems particularly important for the method, I think the authors could reserve a short paragraph to explain how this vectorization and bijection work.", "questions_for_authors": "- Proposition 4.2: is the point of this proposition that computing PH at each layer is more expressive than doing it only once? Do I understand correctly that PH + LPE is essentially similar to a 1-layer PiPE to computed features used by a generic predictor?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nQNCzyVsjU", "reviewer": "Reviewer_rkwW", "summary": "This paper introduces Persistence informed Positional Encoding (PiPE), a novel learnable method that synergizes positional encoding with persistent homology to enhance graph neural networks (GNNs). The authors argue that traditional message-passing GNNs suffer from limitations in expressiveness, being constrained by the 1-Weisfeiler-Lehman test in distinguishing non-isomorphic graphs. They demonstrate that integrating PiPE leads to improved performance in various real-world applications, including graph classification and molecule property predictions, by enabling richer graph representations. The empirical results indicate that PiPE not only outperforms baseline methods in predictive tasks but also shows superior generalizability in out-of-distribution scenarios, showcasing its effectiveness in capturing relevant features for unseen data distributions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> The compared baselines are all positional encoding approaches....\n\nThank 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.\n\n| PE method | Diagram         | ZINC               | Alchemy            |\n|-----------|----------------|--------------------|--------------------|\n| RW        | -              | 0.090 $\\pm$ 0.005 | 0.121 $\\pm$ 0.002 |\n|           | TOGL           | 0.080 $\\pm$ 0.005 | 0.114 $\\pm$ 0.002 |\n|           | PiPE (VC)      | 0.075 $\\pm$ 0.011 | 0.113 $\\pm$ 0.002 |\n|           | PiPE (RePHINE) | **0.070** $\\pm$ 0.010 | **0.111** $\\pm$ 0.002 |\n| PEG       | -              | 0.187 $\\pm$ 0.012 | 0.114 $\\pm$ 0.001 |\n|           | TOGL           | 0.143 $\\pm$ 0.012 | 0.112 $\\pm$ 0.002 |\n|           | PiPE (VC)      | 0.125 $\\pm$ 0.017 | 0.112 $\\pm$ 0.003 |\n|           | PiPE (RePHINE) | **0.108** $\\pm$ 0.022 | **0.111** $\\pm$ 0.004 |\n| SPE       | -              | 0.069 $\\pm$ 0.004 | 0.108 $\\pm$ 0.001 |\n|           | TOGL           | 0.062 $\\pm$ 0.003 | 0.112 $\\pm$ 0.002 |\n|           | PiPE (VC)      | 0.059 $\\pm$ 0.010 | 0.105 $\\pm$ 0.003 |\n|           | PiPE (RePHINE) | **0.058** $\\pm$ 0.007 | **0.103** $\\pm$ 0.004 |\n\n> The theoretical analysis is based on unattributed graphs....\n\nThank 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. \n\n| Dataset          | PH   | PH+LPE | PiPE  |\n|-----------------|------|--------|-------|\n| Basic (60)      | 0.03 | 0.10   | **0.72** |\n| Regular (50)    | 0.00 | 0.15   | **0.40** |\n| Extension (100) | 0.07 | 0.13   | **0.67** |\n| CFI (100)       | 0.03 | 0.03   | 0.03  |\n| Distance (20)   | 0.00 | 0.00   | **0.05** |\n\n[1] Y. Wang et al. An empirical study of realized GNN expressiveness, ICML 2024.\n\n> At the end of the 3rd paragraph in Introduction,...\n\nSeveral recent works provide evidence that topological information is relevant for downstream tasks in machine learning.\n\nFor 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.\n\nThese 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.\n\n[1] T. Papamarkou et al. Position: Topological Deep Learning is the New Frontier for Relational Learning, ICML 2024\n\n[2] Y. Verma et al. Topological Neural Networks go Persistent, Equivariant, and Continuous, ICML 2024\n\n[3] C. Battiloro et al. $E(n)$ Equivariant Topological Neural Networks, ICLR 2025\n\n[4] S. Gupta et al. TopoDiffusionNet : A topology aware diffusion model, ICLR 2025\n\nMany 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.", "claims_and_evidence": "The claims made in the submission are supported by clear evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense.", "theoretical_claims": "The theoretical claims in this paper are well-developed.", "experimental_designs_or_analyses": "The experimental designs are valid.", "relation_to_broader_scientific_literature": "The key contributions of the paper are related to graph Transformer.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strength:\nThis paper takes a good approach by demonstrating through examples that PH and PE cannot replace each other on their own. Therefore, it makes sense to me that the combination of them leads to better expressivity.\n\nWeakness: \n1. The compared baselines are all positional encoding approaches. How about the comparison with PH-based approaches? From my perspective, the only difference between the proposed method and TOGL [1] is that in TOGL the filtration function is applied to node attributes rather than PEs. I wonder how the results might differ.\n2. The theoretical analysis is based on unattributed graphs, while the graphs used in experiments are attributed. Besides, the theoretical analysis is about the expressiveness, while the experiments are about regression and classification tasks that are not related to the expressiveness. If the theoretical analysis does not align with the experimental results, what is the significance of the theoretical analysis? \n\n[1] Horn, Max, et al. \"Topological graph neural networks.\" arXiv preprint arXiv:2102.07835 (2021).", "other_comments_or_suggestions": "No.", "questions_for_authors": "At the end of the 3rd paragraph in Introduction, the authors mention that topological information may be relevant to downstream tasks. Could you provide some evidence or literature?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sK5ACTJua5", "reviewer": "Reviewer_n4Zk", "summary": "The manuscript introduces a novel positional encoding (PE) methodology for GNNs by combining eigenvalue and eigenvector information from graph Laplacians with persistent homology (PH). The authors present theoretical insights demonstrating that neither PE nor PH independently surpasses the other in expressiveness. A new method termed Persistence-informed Positional Encoding (PiPE) is proposed, theoretically and empirically validated to outperform standalone PE and PH methods in various tasks including molecule property prediction, graph classification, and out-of-distribution generalization.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your thoughtful feedback! We address all your questions and comments below.\n\n> The claim in Section 1 about the drawbacks of partitioning eigenvalue/eigenvector spaces requires clarification.\n\nThank 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.\n\nOne 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. \n\nWe will add a clarification regarding it in section 1 of the revised version of the paper.\n\n> A foundational assumption....\n\nThanks for pointing this out. We will highlight this assumption in the revised manuscript. \n\n> Empirical validation....\n\nBased 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.\n\n| PE method | Diagram         | OGBG-MOLHIV         |\n|-----------|----------------|---------------------|\n| RW        | -              | 0.762 $\\pm$ 0.007  |\n|           | PiPE (VC)      | 0.781 $\\pm$ 0.005  |\n|           | PiPE (RePHINE) | **0.798** $\\pm$ 0.004  |\n| SPE       | -              | 0.776 $\\pm$ 0.004  |\n|           | PiPE (VC)      | 0.785 $\\pm$ 0.005  |\n|           | PiPE (RePHINE) | **0.791** $\\pm$ 0.003  |\n\n> An ablation study explicitly comparing the separate effects of utilizing only 0-dimensional or 1-dimensional persistent diagrams....\n\nThank 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.\n\n| PE method | Diagram         | OGBG-MOLHIV        | ZINC               | Alchemy            |\n|-----------|----------------|--------------------|--------------------|--------------------|\n| RW        | -              | 0.762 $\\pm$ 0.007 | 0.090 $\\pm$ 0.005 | 0.121 $\\pm$ 0.002 |\n|           | PiPE (VC)      | 0.781 $\\pm$ 0.005 | 0.075 $\\pm$ 0.011 | 0.113 $\\pm$ 0.002 |\n|           | PiPE (RePHINE) | 0.798 $\\pm$ 0.004 | 0.070 $\\pm$ 0.010 | 0.111 $\\pm$ 0.002 |\n| SPE       | -              | 0.776 $\\pm$ 0.004 | 0.069 $\\pm$ 0.004 | 0.108 $\\pm$ 0.001 |\n|           | PiPE (VC)      | 0.785 $\\pm$ 0.005 | 0.059 $\\pm$ 0.010 | 0.105 $\\pm$ 0.003 |\n|           | PiPE (RePHINE) | 0.791 $\\pm$ 0.003 | 0.058 $\\pm$ 0.007 | 0.103 $\\pm$ 0.004 |\n \n> Some relevant references on analyzing the expressive power of PH are missing...\n\nThank 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.\n\n> It would improve readability to index equations explicitly (e.g., The equation on line 307 of page 6).\n\n\nThank you for pointing this out. We will numerate all the equations in the revised version of the paper.\n\nWe 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!", "claims_and_evidence": "**W1.** The claim in Section 1 about the drawbacks of partitioning eigenvalue/eigenvector spaces requires clarification. Specifically, the manuscript should clearly state that the basis invariant PEs (e.g. BasisNet proposed by Lim et al. (2023)) can utilize the full eigenvalue/eigenvector space.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "**W2.** A foundational assumption of Proposition 3.1 and subsequent propositions is that the positional encodings should be permutation equivariant and basis invariant, ensuring identical PE outputs for isomorphic graphs regardless of permutation or eigenvector selection. The manuscript must explicitly acknowledge and highlight this critical assumption to reinforce the validity and relevance of the theoretical claims.", "experimental_designs_or_analyses": "**W3.** Empirical validation would benefit from the inclusion of popular benchmarks, such as the OGBG-MOLHIV dataset to provide broader benchmarking and reinforce the generalizability and practical impact of the proposed method.\n\n**W4.** An ablation study explicitly comparing the separate effects of utilizing only 0-dimensional or 1-dimensional persistent diagrams should be conducted. Such an analysis would clarify the relative importance and specific contributions of each dimensional component, enhancing methodological robustness and clarity.", "relation_to_broader_scientific_literature": "The manuscript positions itself within the broader context of graph representation learning by directly addressing known limitations in positional encoding methods and persistent homology-based approaches. It builds upon prior works on positional encodings, and complements existing theoretical insights regarding the expressiveness of PH frameworks. By integrating these two methodologies, PiPE advances current understanding and capabilities in distinguishing complex graph structures, particularly within molecular and synthetic benchmarks.", "essential_references_not_discussed": "**W5.** Some relevant references on analyzing the expressive power of PH are missing. For instance, Theorems 1–3 of [1] examine the expressive power of PH in distinguishing non-isomorphic graphs when specific filter functions, such as shortest-path distances, are employed. Additionally, Theorem 4 of [1] investigates the expressive power of PH specifically in distinguishing regular graphs.\n\n[1] Yan et al., Enhancing Graph Representation Learning with Localized Topological Features. JMLR, 2025.", "other_strengths_and_weaknesses": "Strengths:\n\n**S1.**\tThe paper provides a theoretical foundation, elucidating the complementary nature of positional encodings and persistent homology.\n\n**S2.**\tPiPE offers demonstrable performance gains across multiple benchmarks and tasks, highlighting practical effectiveness and versatility.\n\n**S3.**\tThe integration of PH with positional encoding is a novel contribution, expanding the toolset for improving the expressivity of GNNs.", "other_comments_or_suggestions": "W6. It would improve readability to index equations explicitly (e.g., The equation on line 307 of page 6).", "questions_for_authors": "N/A.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This submission presents a novel framework for imbuing positional encodings of graphs with topology-based features (as measured using persistent homology). Next to providing the theoretical properties, i.e., advantages and shortcomings, of both approaches, the manuscript contains extensive experiments in a variety of tasks. Reviewers were unanimous in their positive assessment of the paper, and the strong rebuttal helped in alleviate some of the concerns. Of particular noteworthiness to the AC is the high quality of the writing and the illustrations of the paper. Already in its current state, this submission is clearly ready for presentation at the conference and will prove to be a relevant work in graph representation learning.

I trust the authors to implement the changes they promised during the rebuttal in the camera-ready version. Along those lines, I would also like to kindly request authors to include tables of experimental results into the appendix whenever they deem it appropriate. These could nicely complement the graphical depictions of experiments in the paper.
Decision: Accept (poster)