Persistent Local Homology in Graph Learning
Authors: Minghua Wang
Yan HU
Ziyun Huang
Di Wang
Jinhui Xu
Venue: Accepted by TMLR ()

Abstract: In this study, we introduce Persistent Local Homology (PLH) for graphs, a novel method that synergizes persistent homology with local homology to analyze graph structures. We begin by mathematically formalizing PLH, defining it as the application of persistent homology to annular local subgraphs. This foundation paves the way for the development of a computational pipeline, specifically tailored for PLH, which we explore in various graph learning contexts. Despite its utility, a complexity analysis reveals potential computational bottlenecks in PLH application. To address this, we propose Reduced PLH (rPLH), an efficient variant designed to significantly lower computational complexity. Experimental evaluations with rPLH demonstrate its capability to retain the effectiveness of the original PLH while substantially reducing computational demands. The practical utility of PLH and rPLH is further corroborated through comprehensive experiments on both synthetic and real-world datasets, highlighting their broad applicability and potential in diverse analytical scenarios.

Published in Transactions on Machine Learning Research (04/2024)
Persistent Local Homology in Graph Learning
Minghua Wang
minghuuano@oufflll.ccoo edu
Department of Computer Science and Engineering State University of New York Buffalo, NY, USA
Yan Hu
yan.hu@kuuut..ede edu.
Computer, Electrical and Mathematical Sciences and Engineering Division King Abduliah University of Science and Technology, Saudi Arabia
Ziyun Huang
zah201 @psu edu
Deportment of Computer Science and Software Engineering Penn State Eric, The Beloend College, PA, USA
Di Wang
di www.unnkkkkss..coe edu. edu..a
Computer, Electrical and Mathermatical Sciences and Engineering Division King Abdullah University of Science and Technology, Saudi Arabia
Jinhui Xu
jinbui@buffall.. edu
Department of Computer Science and Engineering State University of New York at Buffalo, NY, USA
Reviewed on OpenReview: https: oww.eviee......ee net/ pormforum? id- qunyX9WYr6
Abstract
In this study, we introduce Persistent Local Homology (PLH) for graphs, novel method that synergizes persistent homology with local homology to analyze graph structures. We begin by mathematically formalizing PLH, defining it as the application of persistent homology lo annular local subgraphs. This foundation paves the way for the development of compu- tational pipeline, specifically tailored for PLH, which we explore in various graph learning contexts. Despite its utility, a complexity analysis reveals potential computational bottle- necks PLH application. To address this, we propose Reduced PLH (rPLH), an efficient variant designed to significantly lower computational complexity. Experimental evaluations with rPLH demonstrate its capability retain the effectiveness of the original PLH while substantially reducing computational demands. The practical utility of PLH and rPLH is further corroborated through comprehensive experiments on both synthetic and real-world datasets, highlighting their broad applicability and potential in diverse analytical scenarios.
1 Introduction
Topological Data Analysis (TDA) has emerged as a powerful tool for understanding complex data structures. offering insights into the underlying geometry and topology of datascts. One of the key techniques TDA is Persistent Homology (PH), which quantifies topological features across multiple scales and has been utilized in numerous tasks, proving its efficacy in capturing the topological properties of data (Edelsbrunner et al, 2002). The application of PH has notably extended to graph-based tasks, highlighting its growing importance in understanding graph structures and properties.
In the realm of graph learning, PH provides global topological signatures that lead to successful topology- driven machine learning approaches for graphs (Carrière al. 2020 Hofer et al. 2020 Chen et al. 2021a
Hofer al. 2017 2019 Horn et al.) 2022; RReck et al.) [2019 Wong & Vong 2021). The evolution of PH, particularly through variants like Zigzag persistence and multipersistence, has been instrumental in

---

Published in Transactions on Machine Learning Research (04/2024)
advancing spatial-temporal graph neural network tasks, offering refined analysis tools for these dynamic systems (Chen et al. b 2022). Moreover, the field has seen innovative integrations of PH into neural networks, where learnable filtration and vectorization methods have been utilized for end-to-end learning (Carrière et al.) 2020 Hofer et al.) 2020 Leygonic et al.) 2021). This integration has substantially enriched the predictive capabilit of graph models, demonstrating the versatility and effectiveness of topological methods in complex graph-based learning scenarios.
Building upon these advancements, the application of PH local subgraphs has recently become focal point in graph learning. This shift towards more localized approach represents significant evolution in the use of PH, aiming to tackle unique challenges within subgraph structures. For example, Zhao et al. (2020) proposed network architecture that integrates PH in local subgraphs to optimize message passing in graph convolution processes. Similarly, [Chen et al. (0021a) utilized PH to analyze node neighborhoods, incorporating topological summaries to counter challenges like oversmoothing and vulnerability to graph perturbations. In link prediction tasks, Yan et al. (2021) leveraged PH on local subgraphs to analyze node interactions, enhancing the lask's performance signilicantly.
Motivation Despite these successes, applying PH to local subgraph analysis has its limitations, primarily in potentially overlooking crucial local topological features. This issue is highlighted in Subsection where we demonstrate that PH's application to local subgraphs might be insensitive to variations among these structures, which could limit its effectiveness in certain scenarios. To address this, our paper introduces the concept of Persistent Local Homology (PLH) in graphs. It aims to provide a more nuanced understanding of the topological characteristics of local graph structures, thereby overcoming the limitations of traditional PH in local subgraph analysis. This rescarch presents several key questions, including the formalization of PLH on graphs its impact on graph learning (asks, the computational complexities involved, and strategies for enhancing scalability. Our work is dedicated to exploring these questions, with the goal of broadening the understanding and application of PLH in graph learning.
Contributions We established the formulation of PLH on graphs, designed to reveal topological charac- teristics frequently omitted in traditional PH. Our novel method harnessos PLH's capacity for probing local structures, thereby enhaneing both algorithms and applications in graph-based learning. To our knowledge, this is the first study to establish linkage between PLH and graph learning paradigms. In addition, we propose an innovative variant, termed Reduced PLH (rPLH) which retains comparable efficacy to PLH but with significantly reduced complexity. Our experimental results demonstrate that PLH not only consis- tently surpasses PH in synthetic datasets, but also significantly contributes to performance improvements in various real-word world graph learning models. Furthermore, PLH has been shown to advance the state-of shate-of-the-ars the-art (SOTA) in graph learning models.
2 Related Works
Persistent Homology Variants PH has been a powerful tool for data analysis since its introduction by Edelsbrunner et al. (2000). It has been applied to wide range of problems, including the study of protein structure, image analysis, and machine learning. In recent years, number of variants of PH have been proposed. Extended persistence broadens the scope of persistence analysis by considering not only the sublevel sets of a real-valued function but also the superlevel sets (Cohen-Steiner et al., 2009 Zigzag persistent homology addresses the limitations of the original framework in dealing with dynamic data sets by introducing a more flexible construction of persistence modules (Carlsson et al. 2009). Multiparameter persistent homology extends the persistence concept to higher dimensions, enabling more comprehensive understanding of data sets with complex structures (Carlsson & Zomorodian, (007). Our work, PLH graphs, can also be seen as variant of PH on graphs since it extends the concept of PH to graphs by considering the topological properties on annular local subgraphs.
Persistent Local Homology The exploration of local homology in data analysis has been a subject of substantial interest in recent research. Bendich et al. 2007 and Bendich (2008) laid the groundwork by
The term 'reduced' in HPLH does not refer reduced homology.
2

---

Published in Transactions on Machine Learning Research (04/2024)
developing methods to assess local homology in stratified spaces and extending persistent homology theory to local homology, respectively. This enabled deeper understanding of the local topological structures in data sets. Building on this, [ey et al. (2014) focused on estimating manifold dimensions using local homology derived from point samples. In a novel application, [Ahmed et al. (2014) introduced a now distance metric for road network comparison, leveraging local persistent homology to simultaneously consider spatial proximity and local topology. Further, Fasy & Wang (2016) provided survey of local homology's application data analysis, emphasizing its efficacy in extracting local structures from datasets. Contrasting these approaches, Stolz al. (2020) proposed approximation of local homology through the absolute homology of small annuli within specified neighborhoods. In similar vein, Von Rohrscheidt & Rieck 2023 introduced a multi-scale persistent framework for local homology, enhancing the capture of local geometric information.
PLH in A Metric Space A pivotal work closely related to our study is that Von Rohrscheidt. & Rieck )023). This research is grounded in a novel formulation PLH in a metric space, which is instrumental evaluating the shape of neighborhoods across multiple scales. A key application of PLH in their work is locally estimate the intrinsic dimension of points within given space. However, a fundamental distine- tion between approach and that of Von Rohrscheidt & Ricck (2023) lies in a significant divergence in methodological requirements. Specifically, our approach does not necessilate the embedding of graphs within metric space, thereby allowing for broader application in scenarios where such embeddings are either impractical or infeasible. This distinction underscores the unique contribution of our work in the realm of graph analysis, setting apart from the existing literature on PLH in metric spaces.
3 Preliminaries
To enhance the introduction our methodology, we offer a succinct overview of the fundamental concepts integral to our approach. For readers seeking more in-depth technical insights, we recommend consulting the seminal works of Edelsbrunner Harer (2022), Doy & Wang (202)), and Hatcher (2002), which provide comprehensive treatments of these lopics.
3.1 Homology
Homology, a fundamental topological invariant, distinguishes between different topological spaces, offering computationally feasible yet less stringent equivalence relation than homotopy- This paper mainly uses simplicial homology, investigating sequences of homology groups associated with a simplicial complex.
Simplicial Complex A simplicial complex, denoted as K, is defined as a collection of simplices that adhere to two conditions: every face of a simplex in K must also be in K, and the intersection of any two simplices in K should be either a mutual face or emply. Simplices, generalizing entities like triangles or tetrahedra, can extend into higher-dimenssonal spaces.
Simplicial Homology For a given simplicial complex K, the p-th chain group, C,(K), ) is formed either a vector space or free abelian group over the integers Z. The generators of this group are the p-simplices of K. The introduction of boundary homomorphisms, 0p Cp( - Cp-1(K), facilitates the definition of homology groups, defined as H₂(K) Ker(0,)/ Im(0p+1). These groups encapsulate critical topological information, with elements in Ker(a,) representing cycles, and those in Im(0)+1) being identified as boundarics. The elements the homology group (K), known as homology classes, are precisely those cycles that are not boundaries and represent the p-dimensional holes in the complex. They highlight the fundamental distinction between cycles and boundaries within homology. This distinction central to the application of homology in algebraic topology (Hatcher 2002).
3.2 Persistent Homology
Persistent Homology Persistent homology formalizes the notion of topological simplification through a process called filtration (Edelsbrunner et al.] 2000). In this context, a filtration is defined as a nested sequence of simplicial complexes F (Ko, Ki,... Km), where each complex K, is subcomplex of its
3

---

Published in Transactions on Machine Learning Research (04/2024)
successor K,+1, and K in 9 Ku S K1 C ... Km K represents the final simplicial complex in the sequence.
An important aspect of persistent homology is the mapping of homology groups through this sequence. The inclusion map from a complex K; to a subsequent complex Kj (i I 5) induces a homomorphism 1/y Hp (K.) - Hp (Kz), connecting the functorial nature of homology in topological data analysis. This results in sequence of homology groups for fixed dimension p. given by 0 Hp (Ko) - Hp (Ki) .... Hn (Km) (K)
The p-th persistent homology groups, denoted by H are the images of these induced homomorphisms for 0 S i S S m. They capture the homology classes of K; that persist through to Kj. The ranks of these groups, known as the p-th persistent Betti numbers, are expressed as 33 = rank Hp..
Morcover, the count of p-dimensional homology classes that are born the simplicial complex K, and cease exist before reaching Kj is defined as p calculated using the formula: pb (3) - -3 1 1)) for all i < and for each dimension p. This count reflects the birth and death of homology classes across the filtration.
Persistence Diagram The Persistence Diagram (PD) for each dimension p, denoted dgm,(F), is constructed by plotting each pair (i,j) with a multiplicity equal to منب These diagrams, essentially multisets, provide a comprehensive visual representation of the persistence of homology classes throughout the filtration. According to the fundamental lemma of persistent homology, these diagrams encode the entirety of the persistent homology groups' information.
Bottleneck Distance Among the metrics used for comparing persistence diagrams, the bottleneck dis- (ance is particularly prevalent (Cohen-Steiner et al. (2005). For two persistence diagrams dgm, and dgm', sup, || (>))] where E dgm, and n
the bottleneck distance dø is defined as: d (dgm,, (dgmp.dgm)) denotes a bijection between the points of the diagrams. This definition incorporates points from the diagonal of the diagrams for correspondence when dgın, and dgm', have differing numbers of points, facilitating a meaningful comparison between diagrams.
4 Methodology
In this section, establish our methodology, centered around three key elements. First, we define the PLH in graphs, exploring its stability properties. Next, we detail the computation pipeline for PLH on graphs, including a comprehensive analysis of its computational complexity. Finally, we introduce a reduced method designed to lower this complexity, ensuring efficiency in large-scale applications.
4.1 Formalization of PLH on Graphs
Local Subgraph and Annular Local Subgraph In graph theory, particularly concerning an undirected graph G = (V, E), we introduce the notions of local subgruph (v) and annular local subgruph gf(v) to understand localized graph structures. For a vertex U E V, the local subgraph (v(v) encompasses vertices within a distance 8, defined as {u E V d(u,v) S s}, where d(u, v) represents the shortest path terms of hops. Extending this concept, the annular local subgraph g²(v) is obtained by excluding a smaller local subgraph (*()) from (v), i.e., consisting of vertices {u E V perspective by focusing on ring-shaped region around As special case, the punctured local subgraph (r) is obtained by excluding the central vertex v from (w), thus providing insights into the vertex's immediate neighborhood.
d(u,v) s). offering nuanced
Local Homology on Graphs We employ the homology on annular local subgraphs to represent local homology within graphs. This approach necessitates a preliminary review of local homology as pertains to topological spaces and simplicial complexes. In topological spaces, the local homology a point x, denoted by Hp(X.X (a)), is conceptualized as categorical colimit of the homology groups H,(X, X (U) neighborhoods U of x (Munkres 2018 Hatcher 2002. Skraba & Wang 2014). This concept. becomes
4

---

Published in Transactions on Machine Learning Research (04/2024)
practically significant when interpreting X as simplicial complex, with constituent vertex. In this context, two pivotal constructs are introduced: the Star of v, denoted St(r), which is the aggregate of simplices incorporating and the Link of æ, denoted Lk(x), comprising simplices in St(r) but not including x itself. Von Rohrschoidt & Ricck (2023) clucidated that the relative homology Hp(X, (z)) is isomorphic by employing the excision axiom and exact sequences reduced
to the reduced homology homology. This finding underscores the representational efficacy Lk(z) in capturing local homological characteristics I. Since graph can be viewed as 1-dimensional simplicial complex, formalize local homology in graphs the homology approach in Von Rohrscheidt. & Rieck (2023), we expand the punctured local subgraphs into annular local subgraphs and treat the inner and outer hops as hyperparameters to accommodate various requirements. Therefore, we formalize local homology on graphs to homology on annular local subgraphs.
the punctured local subgraphs within hop. Inspired by the
Topological Difference between Local Subgraph and Annular Local Subgraph While first glance, the distinction between local subgraph and an annular local subgraph may appear subtle, the exclusion of the inner subgraph in the latter fundamentally alters its topological structure. This modification is not merely reduction in the number of vertices and edges, but transformation that significantly impact the graph's intrinsic properties. To elucidate this concept, we present an example demonstrating how the removal of the inner subgraph in forming an annular local subgraph leads to a substantial change in the subgraph's topology. This example underscores the importance of considering such alterations when analyzing graph-based data structures, particularly in applications where topological characteristics play a pivotal role.
(a)
(b)
(c)
(d)
(
(h)
The upper and bottom rows illustrate local subgraphs and their corresponding annular local subgraphs 9i: respectively.
Figure
Table 1 Homologies of the subgraphs in Figure 1
Homology
(a)
(b)
(c)
(d)
Ho
Z
Z
Local subgraphs
H1
Z4
Z
Z4
Homology
(e)
(f)
(g)
(h)
Ho
Z
2
2
2²
Annular local subgraphs
H
0
Z
Given four distinct local subgraphs, as illustrated the upper row of Figure we derive their corresponding annular (or punctured) local subgraphs, shown in the bottom row, by excluding the central vertex from each.

---

Published in Transactions on Machine Learning Research (04/2024)
To quantify and compare their topological differences, treat these subgraphs as simplicial complexes and compute their homologies over Z. The computed homologies are tabulated in Table 1 which presents the rank O and homologies for each of the subgraphs depicted in Figure ! An analysis of these homologies reveals a key insight: while the homologies the upper row subgraphs (local subgraphs) fail to offer a distinct differentiation among them, a combination of Hg and H1 homologies of the bottom row subgraphs (annular local subgraphs) successfully distinguishes all four. This observation emphasizes the superior efficacy of homology applied to annular local subgraphs, which is adept at discerning topological subtleties that often elude detection through the homology of conventional local subgraphs. This example effectively demonstrates the added value of employing local homology on graphs for discerning subtle topological variations.
Persistent Local Homology Graphs Persistent local homology, akin to persistent homology, is method for discerning local topological features of a space across various spatial resolutions. This concept is defined as the persistent homology computed on an annular local subgraph, facilitating the detection of topological features the vicinity of a central vertex. In essence, persistent local homology on graphs aims to delineate the persistent homology of annular local subgraphs, thereby uncovering the graph's persistent topological traits on a localized scale.
4.2 PLH Computation and Its Stability
PLH Computation Recall that our principal objective is to examine the efficacy of PLH in graph learning, process that typically necessitates inputs in vector form. We define the operator plh, V + Hd as the mapping that transforms vertices into vectors. Consequently, plh,(u) represents the vectorized p-th PLH for vertex v. In this paper, the operator is conceptualized as a composition of three functions:
(*), (PI dgm, o g.)) (v,F);
with being the vertex under observation and F as the selected filtration function. Herein, of produces the required annular local subgraph. The dgm, function computes the p-th persistent diagram using matrix reduction or other advanced algorithms, yielding finite multiset of two-dimensional points whose coordinates specify birth and death times for topological features. Subsequently, the persistence image PI converts a diagram into a finitedimeensional vector representation in Rd (Adams et al. 2017). For further details, we direct readers to the relevant surveys (Otter et al., 2017 Ali et al.) 2022), as these topics possess their own distinct intcrests. Ultimately, by concatenating different p-th PLHs, we achieve the complete topological descriptor: plh(v) ( Dy...... plh,, (v) for each v V. This final outcome plh can be readily incorporated into various learning models, underscoring the versatility of our proposed approach.
The PLH computation hinges on the choice of filtration function, which is crucial for determining the topological descriptors. A common choice for filtration is the Vietoris-Rips Rips filtration (Carlsson, 2009). This is also our main choice since the distances between pairs of vertices in a graph can be calculated from the shortest path based on the edge weighs or hops.
Victoris-Rips Filtration on An Annular Local Subgraph Given a weighted graph of = (V.E, w). where is the set of vertices, E the set of edges, and w : E - R20 is the weight function assigning non-negative real numbers as weights to the edges, the Vietoris-Rip filtration with respect the shortest path distances is defined as a sequence of simplicial complexes, (VRe()))))2) constructed follows. For a non-negative real number c, the simplicial complex (R, is defined as:
Vertices: Each vertex in V corresponds to a O-simplex in (g)).
Edges: For each pair of vertices u, E V, an edge (also as a 1-simplex) {u, u} is included in (R.(g.) and only if d(u, v) S e, where d(u, v) is the shortest path distance between u and v.
Higher-Dimensional Dimensional Simplices: Similarly, set of vertices (vo, U1, bx forms a k-simplex (R,( if and only if all pairwise distances between these vertices are less than or equal to c. This means that for every pair of vertices 0i 1y in the set, d(vi, 11) Se e.
6

---

Published in Transactions on Machine Learning Research (04/2024)
The Victoris- filtration of 9f is the collection (V)e())))e20 where each VRe(g,) is simplicial complex as defined above. As increases, more simplices are added to the complexes, capturing the topology of the graph at different scales.
Stability of PLH The stability of the topological features in question is maintained with respect to perturbations in the edge weights of the annular local subgraph. This stability characteristic aligns with the previously established stability the PI, as proven by Adams et al. (2017). To ensure the stability of PLH, we present stability theorem specific to our context.
Theorem 4.1.
Let gf (V,E, w) and 9," = (V,E, w') be two finâte weighted subgraphs on the same verter and edge sets but with different edge weight functions, we use Vietoris-Rips filtration w.r.t. the shortest path distance, i.e,, f(e) = VR. (97), and f'(c = VR. (9,"). Then, the bottleneck distance between their persistence dingrams dgmp and dgm for any dimension p of homology is bounded by the maximum change in edge weights: dp (dgmp, dgmn)) S max.ee w(e)) w'(e)
4.3 Reduced PLH
Reduced PLH (rPLH) is designed as an alternative to the conventional PLH, offering enhanced scalabil- ity compared to the original PLH. In this section, we will analyze the complexity PLH, subsequently introducing rPLH, and then examine its complexity.
Complexity of PLH Persistent diagram can be computed matrix multiplication time, for instance, O(n)), where n denotes the number of simplices and = 2.376 using Coppersmith- -eggorrith--nnogrd (Milosavljević et al. 2011), or w 2.372 with more recent results (Duan et al. 2022). Considering a graph as a 1- dimensional simplicial complex, subsequently becomis O(IV)), leading to the PD complexity of ((()) A critical observation in dense graphs is that they often cause dense local subgraphs. If we proceed to compute PD for each node, the worst-case complexity clevates to (( This has been empirically corroborated by our experiments, where we observed substantial slowness, hindering the practical applications of PLH extensively.
be defined
= E IV In the context of dense graph, n
Construction of Reduced Annular Local Subgraph To address this computational bottleneck, we propose roduced PLH. The main idea is lower the complexity by restricting the total number of simplices, which can archive by restricting the total vertices in the annular local subgraph. To archive this, we introduce maximum degree threshold, denoted as D. The vertices of reduced annular local subgraph is given by Algorithm !
Algorithm Reduced annular local subgraph vertex set building algorithm.
1: Vi < [w}
b Initialize with the given vertex v
2: for <- to 8 do
b. Tterate over s layers
3: Vi f 0
for all u Vi_1 do
V/2 V-U top-D D i-th edge layer vertices with highest degree connected vertex u > Output the vertex set that induces annular local subgraph of
6: return V/4 U...UV.
This algorithm essentially builds successive layers of vertices, with each layer being determined by the connectivity and degree of vertices in relation to the previous layer. The aim is to expand from single initial vertex v outward, layer by layer, selecting at cach step the most connected vertices from the immediate neighborhood of the last layer. The threshold D essentially set an upper bound for the total number of the connections from the vertex to the next layer. We can prioritize neighbors with higher degrees first, allowing the local subgraph to retain its topological structure to the highest feasible extent. We name the PH on the reduced annular local subgraph as the reduced PLH (rPLH). is noteworthy that rPLH maintains the same stability outlined in Theorem 4.1 provided that the reduced annular local subgraph is constructed.
7

---

Published in Transactions on Machine Learning Research (04/2024)
Complexity of rPLH The complexity of PD in rPLH for graph is O(IVID2=)) where s is the maximum hop in local subgraph. Notably, the complexity of rPLH can be significantly lower than PLH if we set D < [V], a condition that we can fully control in practice. Furthermore, our experimental results demonstrate that a properly configured rPLH can achieve a level of effectiveness comparable to that of the standard PLH while tremendously reducing compulation time. This proposed method offers a promising avenue for the efficient application of PI.H in the context of complex graph structures.
4.4 PLH in Graph Learning
To further investigate the effectiveness of PLH in graph learning, we establish the required methods construct the models used in the subsequent experiments. This section is divided into three parts. Initially, we introduce the key component in graph learning: GNNs. Then, we explore the integration of PLH into graph learning models. Finally, present model that establishes a new SOTA performance on PPI datasets, thereby underscoring the utility and efficacy of our proposed methodology.
Graph Neural Networks GNNs represent a family of architectures that have demonstrated considerable success in various applications over recent years. More specifically, the majority of GNNs can be interpreted as a variant of the Message Passing Neural Networks (MPNNs) (Bronstein et al.) 2021). From a technical standpoint, MPNNs operate based on an iterative paradigm. Upon initializing h. X. for cach v E V, where X2 denotes the feature vector of node v, MPNNs learn the embeddings h: (1+1) for each node E V by executing the following steps during the 1-th layer iteration:
h h.*1) )()
h
20 (h... (b.....)
wEN,
In this context, h, significs its embedded feature. The superscripts serve to diffcrentiate between layers, indicating the iteration number. The function & represents a learnable message function that computes the message conveyed from node u to v. The aggregation operation θ collects the messages from the neighbors of node v which then update the node features using the learnable function 6. From the perspective of a single node, the core steps in the MPNN process involve the aggregation of messages from its neighboring nodes and the subsequent update of its feature by integrating its own characteristics with the aggregated message. Ultimately, the network outputs the node embedding h, for every v E V.
PLH Integration Building upon earlier discussions, the output of the PLH already vectorized for each node within a graph. This vectorization facilitates scamless integration of the PLH with various graph learning models. For instance, in the case of GNNs, existing initial node features x,, can be augmented by concatenation, thereby enriching the node's feature representation. Alternatively, the PLH output can be appended to the embedded feature h, after iterations, enhancing the performance of subsequent processes in graph learning models.
PLH-GNN Model PLH-GNN is a model designed to perform link prediction a graph. The framework of the model similar to TLC-GNN in Yan et al. (2021). The model extracts node features from both GNN and PLH. Then we transform the node features into edge features by applying operations such as elementwise sum, difference, squared difference, just concatenation. The outputs of these transformations are denoted as h(u,v) and plh(,.)) respectively, representing the GNN-leernt and PLLl-extracted features of the edge connecting nodes u and v. By executing a concatenation operation, we generate ((,,)) Q (..)) which encapsulates information derived from both the GNN and PLH of our model. This enriched feature representation is subsequently fed into a MLP before the final prediction is made by the Fermi-Diras Decoder Nickel Kiela, 2017 Yan et al. 2021
[Kiookov et al. 2010
5 Experiments
In the experiment section of our study, we comprehensively evaluate the performance enhanced by PLH in both synthetic and real-world scenarios, demonstrating their superiority over conventional PH. Specifically,
8

---

Published in Transactions on Machine Learning Research (04/2024)
GNN
h
((,,r)
= (E,V)
((,,)) + (l,))
Fermi-Dirac Decoder
PLH
plh, plh (a.1)
Figure 2: PLH-GNN Architecture. Node feature vector h, is output by the GNN module, while plh, is output by the PLH module. Edge feature (u,)) (or (u,)) for PLH) is computed via a combination operation that merges the respective node features.
in the synthetic experiments, we meticulously design tasks to illustrate the enhanced capabilities of PLH compared PH. Complementing this, our real-world experiments provide empirical evidence of PLH's overall superiority in practical applications. Furthermore, into a SOTA model yields approximately 1% increase in performance. The ablation study subsection also provides more detailed comparative analysis of the computational efficiency between the rPLH and PLH algorithms. Notably, throughout our experiments, we employ various metrics to ensure a robust and fair comparison with existing baselines, reflecting the diverse tasks and datasets on which PLH is implemented. This multifaceted approach allows us to present a thorough evaluation of PLH's effectiveness across different contexts.
ablation study reveals that integrating PLH
5.1 Synthetic Experiments
The synthetic experiments designed in this study aim to evaluate the effectiveness of the PLH in capturing local topological features within a graph, thereby augmenting the performance in graph- basod learning tasks. Specifically, these experiments focus on the classification of nodes based the count of 2-simplices (triangles) proximal to them, excluding their own presence. Considering undirected graph G (V, E)) where each edge denotes unit distance, the assessment revolves around each node v V and its punctured local subgraph (v). Here, represents the maximum predefined distance from the node v, and the label ((v) quantifies the total number of 2-simplices within (v). For these experiments, we set 8 = 2, thus exploring a two-edge radius around each node. Figure g presents an illustrative example of this setup, providing a concrete visual representation of the classification of the nodes.
1 =
1=
1=1
Up
18
15
14
1=
1=
l= 2
1=
Figure 3: Illustration of synthetic experiment: given == =, 2, focus vertex Us- The local graph (v6) includes single 2-simplex, specifically [va, 17, u8], not encompass V/ itself, which implics that the simplex [Ua, Us. 0g] is not included.
ug) resulting in = 1. It is important to note that gā (va) does
We performed node classification tasks on three randomly generated graphs. The node features were adeptly represented using PH and PLH, with their filtration process contingent upon the dimension of simplices identified within each subgraph. To operationalize these features for classification, we employed the per- sistence image technique for vectorization. Subsequently, a Multi-Layer Perceptron (MLP) was utilized as the classifier. Hyperparameters remained consistent across all experimental setups and can be found in the Appendix.
The experimental results, as presented in Table 2 reveal notable pattern: the accuracies achieved through the of PI. consistently and significantly perperfor those attained by PH across all cases. This disparity
9

---

Published in Transactions on Machine Learning Research (04/2024)
Table 2: Experimental results on syuthetic data. Row C: Represents the number of distinct classes in the dataset. Row F: Indicates the specific features utilized in the Multilayer Perceptron (MLP) model. Comparison Metric: The benchmark used is PH applied to local subgraphs denoted as g²(w). Performance Measure: The results are presented in terms of Accuracy, quantified as pereentage (%).
C
2
3
5
7
F
PH
PLH
PH
PLH
PH
PLH
PH
PLH
G1
93.63+2.67
100.00=0.00
28.32
99.80=0.69
81.38
95.30=2.37
78. 38.5873.07
95.50=3.55
G2
78.99+11.7
100.00=0.00
91.49=1.40
99.69=0011
86.74#1778
96.64+1.15
84.57+3.69
93.57=2.87
G3
96.15=0.900
99.96+0.12
93.63=0.81
99.95=0.10
90.31
98.53=0.53
89.85+1.32
97.80=1.09
in performance underscores the inherent advantage of PLH, particularly in its ability to capture topological information that remains elusive to PH. The results clearly demonstrate the unique strengths of PLH, providing empirical evidence its superior capability in handling such tailored synthetic experiments.
5.2 Rerl-World Experiments
Although PLH demonstrated superior performance in synthetic experiments, the question arises regarding efficacy real-world applications. To address this, we conducted a series of experiments real-world scenarios. These experiments were divided into two primary segments: OGB and PPI. In the OGB segment, utilized datasets from Hu et al. (2020), integrating PLH into existing models without any model-specific fine-tuning. This approach allowed
assess the adaptability and generalizability of PLH in real-world context. For the PPI segment, we employed Protein-Protein Interaction (PPI) datasets, applying the PLH- GNN model as introduced in 4.4 Notably, the experiments conducted were limited to reduced PLH due to the complexity of real-world datasets.
5.2.1 Experiments OGB Datasets
The primary objective of the experiments is to quantitatively assess the performance improvements achieved by the integration of PLH features, without the nocessity for any model fino-tuning. For this purpose, we have employed benchmarks from the Open Graph Benchmark (OGB) (Hu et al. 2020 as our fundamental comparison baselines. Specifically, our experimental framework involved conducting node classification tasks on the ogbu-arxiv dataset, and link prediction tasks on the ogbl-ddi dataset. Detailed information regarding the datasets employed and the hyperparameters utilized in experiments is comprehensively documented in the A Appendix. The results of our experiments are systematically presented in Table 3a
Table 3: Experimental results.
(a) Results for ugbn-arxiv and ogbl-ddi. Comparing with OGB baselines, used identical hyperparam- eters in an ablation-style design to emphasize perfor- mance differences.
(b) Results on the PPI dataset. This table presents the outcomes from analyses conducted on the initial five graphs
within the PPI datasel. Except for our results in the last row, results are replicated from Yan
20211.
Method
Accuracy (%) ogbn-arxiv
@o (%)
ogbl-ddi
Method
AUROC (%)
2
3
4
MLP
55.5040.23
MLP w/ PLH
57.7 37.74+0.2
GCN
75.21
74.42
77.68
76.22
69.67
GCN
71.7410.29
37.07
GIL
57.69
1.45
34.90
85.61
33.65
GCN w/ PLH
72.1 100.29
45.2348.53
SEAL
50.00
64.79
67.14
72.55
50.00
SAGE
71.49+0.22
53.9 13.90=4.77
TLC-GNN
83.92
81.21
83.95
83.03
83.53
SAGE w/ PLH
72.01
63.73
PLH-GNN
88.77
86.84
87.86
88.14
86.90
10

---

Published in Transactions on Machine Learning Research (04/2024)
Dataset ogbn-arxiv A pivotal finding from experiments with the ogbn-arxiv dataset is the notable performance enhancement of the Multi-Layer Perceptron (MLP) model when augmented with PL,H features. This enhancement enables the augmented MLP model to surpass the performance of the traditional MLP model. The underlying reason for this improvement is primarily ascribed to the PLH's capability to leverage the topological structure of data. This ability enriches the model's predictive capabilities by providing ad- ditional contextual insights. In a similar vein, enhancements are also observable in GCN and GraphSAGE models when integrated with PLH. However, the extent of improvement in these models is relatively modest in comparison to that observed in the MLP model. This phenomenon is likely attributable the intrinsic properties of GNNs, which are adept at extracting information from graph topological structures. Consid- ering that GNNs already exhibit higher performance compared to MLP models, the marginal yet significant boost provided by PLH underscores its elfectiveness.
Dataset ogbl-ddi In our investigation, link prediction tasks were performed on the ogbl-ddi dataset. To facilitate direct comparison with the established baselines in the Open Graph Benchmark (OGB), we adapted our evaluation metric accordingly. The results were noteworthy: there was substantial increase in performance, with the Hits@20 metric rising from 37.07% to 45.23% on the GCN. Furthermore, an impressive improvement in Hits@20 was observed, escalating from 53.90% to 63.73% on the GraphSAGE. These empirical findings strongly suggest that the integration of PLH significantly enhances the performance of both GCN and GraphSAGE models.
5.2.2 Experiments on PPI Datasets
The preceding experiments underscored the capability of PLH in augmenting MLP and GNNs through the integration of topological features derived from PLH. Building upon this foundation, the current experiments aim to explore the potential of PLH in enhancing a SOTA model. In this context, we applied the PLH- GNN model, as detailed in 4.4 to Protein-Protein Interaction (PPI) datasets for link prediction tasks Zitnik & Leskoved (2017)- The model utilizes GraphSAGE for node embedding, capitalizing on its proficiency in encoding node features and graph structures effectively. To ensure robust comparison with existing baselines, we employed the Area Under the Receiver Operating Characteristie (AUROC) as our primary evaluation metric. The comparative results are tabulated in Table 3b] juxtaposed against baselines including Graph Convolutional Network (GCN) (Kipf & Welling 2016), Gcometry Intcraction Learning (GIL) (Zhu et al. 2020 SEAL (Zhang & Chen 2018), and Topological Loop-counling Graph Neural Network (TLC- GNN) (Yan et al. 2021). The empirical evidence unequivocally demonstrates the superior performance of
the PLHI-GNN model, which achieves SOTA results on the PPI datasets, thereby attesting to its efficacy. This success prompted subsequent ablation study to dissect the contributing factors of this achievement.
5.3 Ablation Study and Computational Efficiency
This study aims to address a lingering question from the previous section: to what extent does PLH contribute to SOTA performances? To investigate this, we conduct a comparative analysis of results obtained using PH, PLH, and their combined methodology (PH w/ PLH). These results are presented in Table 4
The comparison is between the row representing the PLH, particularly the highlighted one identified as the top performer, and the baseline model, which is detailed in the first row of the table. This comparison indicates that integrating PI.H into the GNN model results in an approximate 1% improvement over the existing SOTA performance. Notably, the bascline model itsclf SOTA model, and this slight yet significant enhancement further emphasizes the effectiveness of PLH in boosting the performance of the model.
A critical observation from the results presented in the table is the evident superiority of the combined method. Specifically, PH w/ PLH demonstrates a consistent performance odge over the standalone imple- mentations of both PH and PLH. Remarkably, the inclusion of PLH enhances the model's capability, con- tributing to an additional performance increase of up to 0.53%. While this increment might seem marginal, it is important to note that this enhancement realized by simply puncturing the center of local subgraphs. This outcome is noteworthy, as it represents significant gain derived from a soemingly minimal modifica- tion. Furthermore, this finding corroborates our previous claims regarding the distinct capabilities of PI.H in
11

---

Published in Transactions on Machine Learning Research (04/2024)
Table 4: Ablation study for PPI in AUROC (%). И is the maximum hop and is degree threshoold. The first row is the results without any topological features, which services the baseline.
Feature
Parameters
2
3
87.93
85.44+1.41
86.71+0.61
87.07
85.31
PH PLH
=
87.71+0.66
85,44+1.31
86.88+0.68
87.06+0.64
85.41+0.74
= 1, =
87.67=0.53
85.67=0.88
86. 06.70+0.66
87.09+0.00
85.35+0.75
PH w/ PLH
1,
87.87 00.74
85.91:t0.94
87.11#0.66
87.28+00.3
85.94=0.85
PH
H = 2, D = 4
88.55=0075
86.68=+0.86
87 0..38
87.98:+0.51
$6.83+0.63
PLH
= 2, =
88.49100.8
86.66100.2
87.82.1..45
88.00.10.47
86.67 10.73
PH w/ PLH
= 2, =
88.65
86.9640.84
88.01=0.41 =0.41
87.98:t0.6
87.02=0.52
PH
H = 2, D 8
88.81
86.98:0.87
87.90+0.57
88. +0.55
86.80+0.60
PLH
H = 2, D = 8
88.77
86.84.10.96
87.86110.57
88. 18.14
86.9010.53
PH w/ PLH
H = 2, D = 8
88.89+0.41 87.12+0081
87.87
86.96=0.62
PLH
= D 0
88.16
86.40+1.03
87.53+0.43
87.9240.28
86.59
capturing topological characteristics that PH alone cannot. Consequently, this suggests that PH and PLH, individual methods, provide unique and complementary topological insights.
Comparing rPLH and PLH: Computational Efficiency In the preceding discussion of real-world experiments, we did not explicitly distinguish between rPLH and PLH, treating rPLH as an alternate form of PI... This approach is justified, as indicated by the final entry in Table where rPL.H effectively becomes identical to PLH when the threshold parameter D is set to co. The computational times for both rPLH and PLH, calculated for various graphs, are presented in Table with specific reference to the relevant data from Table A critical observation is the significantly reduced computation time for rPLH compared to PLH in these datasets, underlining rPLH's scalability in practice.
Table 5: Comparison of computational time (in seconds) for rPLH and PLH PPI datasets. For rPLH, values are rounded to the nearest unit, whereas for PLH (last line), they are rounded to the nearest hundred.
Feature
Parameters
1
2
5
= 1, D
2
2
2
rPLH
H =2
4
4
= =8
6
5
10
6
PLH
H 80
500
500
3000
3500
700
6 Future Works and Conclusion
Our experiments confirm the effectiveness of PLH on smaller graphs; however, the scalability to larger graphs presents a considerable challenge due to the intricacies involved processing simplicial complexes. More specifically, the computational complexity of PLH is denoted as O([V]==11) when graphs are treated 1-dimensional simplicial complexes. This represents significant escalation from the O(IV)²)) complexity associated with PH full graphs. Such increase in computational demand notably constrains PLH's applicability for analysis of larger graphs. Although the reduced version, rPLH, enhances scalability by regulating the size and sparsity of the annular local subgraphs, it is imperative to maintain these subgraphs sufficiently close to their originals to effectively extract meaningful features. As such, the scalability still remains as an issue in practice. Consequently, future work will include developing scalable algorithms for simplicial complexes within graph data, aiming to enhance the applicability of PLH for comprehensive large- scale graph analysis.
12

---

Published in Transactions on Machine Learning Research (04/2024)
While scalability remains a key challenge, there are two additional avenues for potentially improving experimental results. The first approach focuses on enhancing the underlying prediction models used within PLH. The field of graph-related models is constantly evolving, and incorporating more advanced models such as RevGNN (Li et al.) (021) for node classification, or GNNs enhanced by the labeling trick (Zhang et al. 2021 and NCNG (Wang el al., 2023) for link prediction, could potentially lead to performance gains. Second, we can explore methods to directly improve the effectiveness of PLH itself. According to Hofer et al. (2020), making the filtration learnable can provide better expressive power, thereby potentially improving the performance of our method. Theoretical evidence supporting this idea can be found in recent paper by Rieck (2023), which demonstrates that filtration plays a key role in the expressivity of PH in graph learning. Additionally, varying vectorization methods could present another avenue for improving the performance of PLH. A comprehensive survey by Ali et al. (2022) underscores the significant influence vectorization can have on performance. Considering these findings, investigating learnable filtrations and different vectorizations are promising strategies for enhancing the effectiveness of PLH.
In the context of our work, rPI.H emerges as an riguing alternative to PLH. Upon examination of Table 4 we observe that rPLH with proper parameter can surpass PLH. Various conjectures could explain this trend, such as noise and lack of topological properties due to high density in PLH; However, a more thorough investigation into the causal factors underlying the comparative efficiency of rPLH remains promising area for future research, which would yield a deeper understanding of the mechanisms responsible for the observed performance enhancements.
Central our study is the understanding that puncturing the centeral vertex aids in extracting more intricate topological information from local subgraphs. The procedure can be conceptualized as manipulating the filtration domain, allowing us to delve deeper into the topology of the data. As promising as this appears, it incites a compelling question: how can we harness the full extent of these latent topological properties? The task is nontrivial and demands meticulous exploration.
Conclusion In summary, this study presents a mathematical formalization of Persistence Local Homology (PLH) for graphs, achieved by applying Persistence Homology (PH) to anmular local subgraphs. We illustrate how PLH reveals local structures that are overlooked by conventional PH techniques applied to local sub- graphs. Moreover, the benefits of this approach, which extend to graph learning methodologies incorporating PLH as features, are substantiated by our experiments demonstrating the efficacy of PLH in graph learn- ings. Significantly, the introduction of Reducod PLH enhances scalability while maintaining its effectiveness, underscoring its potential for practical applications in intricate graph-based learning environments.
Acknowledgments
The research of Wang and Xu was supported in part by NSF through grant CCF-2200173 and by KAUST through grant CRG10-4663.2. 2. Di Wang was supported in part by the baseline funding FCC/1/1976-42 funding from the CRG grand TRF/1/4663-0) from CBRC of King Abdullah University of Science and Technology (KAUST). He was also supported by the funding RGC/3/4816-099 01 of the EDAIA-KAUST Center of Excellence in Data Science and Artificial Intelligence (SUATA-KAUST AT). The authors would like to express their sincere ude to the anonymous reviewers for their careful reading of the manuscript and their insightful comments and valuable suggestions.
REI/ REI/I/5232 1/5232-011200000
RIEI/15533-001
References
Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25(3):211 230, 2003.
Henry Adams, Tegan Emerson, Michael Kirby, Rachel Neville, Chris Peterson, Patrick Shipman, Sofya Chepushtanova, Eric Hanson, Francis Motta, and Lori Ziegelmeier. Persistence images: A stable vector representation of persistent homology. Journal of Machine Learning Research, 18, 2017.
Mahmuda Ahmod, Brittany Terese Fasy, and Carola Wenk. Local persistent homology based distance between maps. In Proceedings of the 22nd ACM SIGSPATIAL international conference on advances in geographic information systems, pp. 43 52, 2014.
13

---

Published in Transactions on Machine Learning Research (04/2024)
Dashti Ali, Aras Asaad, Maria-Jose Jimenez, Vidit Nanda, Eduardo Paluzo Paluzo-Hidalgo, and Manuel Soriano-
Trigueros. A survey of vectorization methods in topological data analysis. arviv preprint Saa:2212.09700 2022.
Paul Bendich. Analyzing stratified spaces using persistent versions of intersection and local homology. Duke University, 2008.
Paul Bendich, David Cohen-Steiner, Herbert Edelsbrunner, John Harer, and Dmitriy Morozov. Inferring local homology from sampled stratified spaces. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pp. 536-546. IEFE, 2007.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesies, and gauges. Xr preprint vrXic:2104.134770 2021.
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chual Chang, A comprchensive survey of graph embed- ding: Problems, techmiques, and applications. IEEE transactions on knowledge and data engineering, 30 (9):1616-166) 16616661667,,, 2018.
Gunnar Carlsson. Topology and data. Bulletin of the American Mathematical Society, 46(2):255 308, 2009.
Gunnar Carlsson and Afra Zomorodian. The theory of multidimensional persistence. In Proceedings of the twenty-third annual symposium on Computational geometry, pp. 184-193, 2007.
Gunnar Carlsson, Vin De Silva, and Dmitriy Morozov. Zigzag persistent homology and real-valued functions. Proceedings of the twenty-fifth annual symposium on Computational geometry, pp. 247-256, 2009.
Mathieu Carrière, Frédéric Chazal, Yuichi Ike, Théo Lacombe, Martin Royer, and Yuhei Umeda. Perslay:
A neural network layer for persistence diagrams and new graph topological signatures. In International Conference on Artificial Intelligence and Statistics, pp. 2786 2796. PMLR, 2020.
Frédéric Chazal and Bertrand Michel. introduction topological data analysis: fundamental and practical aspects for data scientists. Frontiers in artificial intelligence, 4:108, 2021.
Yuzhou Chen, Baris Coskunuzer, and Yulia Gel. Topological relational learning graphs. Advances in neural information processing systems, 1127029-27042 2021a.
Yuzhou Chen, Ignacio Segovia, and Yulia R Gel. Z-genets: Time zigzags at graph convolutional networks for time series forecasting. In International Conference on Machine Learning, pp. 1684-1694. PMLR, 2021b.
Yuzhou Chen, IJ Segovia Dominguez, B Coskunuzer, and YR Gel. Tamp-s2genets: When time-aware multi- persistence meets spatio-supra graph convolutional nets while forecasting time scries. In The International Conference on Learning Representations (ICLR), 2022.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An elficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 257-266, 2019.
David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. In Proceed- ings of the twenty-firsl annuaal symposium on Compulational geometry, pp. 263 271, 2005.
David Cohen-Steiner Herbert Edelsbrunner, and John Harer. Extending persistence using poincaré and lefschetz duality. Foundations of Computational Mathematics, 9(1):79 100,, 2009.
Stéphane Coulomb, Michel Bauer, Denis Bernard, and Marie-Claude Marsolier-Kergont Gene essentiality and the topology of protein interaction networks. Proceedings of the Royal Society B: Biological Sciences, 272(1573):12211177 2005.
Tamal K Dey, Fengtao Fan, and Yusu Wang. Dimension detection with local homology. orXiv preprint 105551440..9534, 2014.
14

---

Published in Transactions on Machine Learning Research (04/2024)
Tamal Krishna Dey and Yusu Wang. Computational topology for data analysis. Cambridge University Press, 2022.
Ran Duan, Hongxum Wu, and Renfei Zhou. Faster matrix multiplication via asymmetric hashing. arXiv preprint ar Xiv:22200. 101 10173, 2022.
David Easley and Jon Kleinberg. Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge university press, 2010.
Edelsbrunner, Letscher, and Zomorodian. Topological persistence and simplification. Discrete & Computa-
tional Geometry, 28:511-533, 2002.
Herbert Edelsbrunner and John L Harer. Computational topology: introduction. American Mathematical Socicty, 2022.
Herbert Edelsbrunner, David Letscher, and Afra Zomorodian. Topological persistence and simplification. In Proceedings 41st annual symposium on foundations of computer science, pp. 454-463. IEEE, 2000.
P ERDAS and A R&wwi. On random graphs i. Publ. math. debrecen, 6(290-297):18, 1959.
Brittany Terese Fasy and Bei Wang. Exploring persistent local homology in topological data analysis. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6430 6434. IEEE, 2016.
Edgar N Gilbert. Random graphs. The Annals of Mathematioal Statistics, 30(4):1141 1144, 1959.
Aditya Grover and Jure Leskovee. node2voc: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and dala mining, pp. 855 864, 2016.
Jiuxiang Gu, Handong Zhao, Zhe Lin, Sheng Li, Jianfei Cai, and Mingyang Ling. Scene graph generation with external knowledge and image reconstruction. In Proceedings of the IFFE/CVE conference on compuler vision and pattern recognition, pp. 1969 1978, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
A. Hatcher. Algebraic Topology- Algebraic Topology. Cambridge University Press, 2002.
ISBN
9780521795401. URL https://bookss. google. wwwpolllw.o/oooooooooooooooooooo hoom///ooossi.dBBB886isooo.
Christoph Hofer, Roland Kwitt, Mare Niethammer, and Andreas Uhl. Deep learning with topological signa- tures. Advances in newral information processing systems, 30, 2017.
Christoph Hofer, Florian Graf, Bastian Ricck, Mare Nicthammer, and Roland Kwitt. Graph filtration learning. In International Conference on Machine Learning, pp. 4314 4323. PMLR, 2020.
Christoph D Hofer, Roland Kwitt, and Marc Nicthammer. Learning representations of persistence barcodes. J. Mach. Learn. Res., 20(126):1-44 2019.
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt. Topological graph neural networks. In International Conference on Learning Representations, 2022. URL httpp:://peereeviw http:////ppppppeeee.eeeeeee/a/a/ http://orruuntttoxxxoXeeEEEEEE
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datascts for machine learning on graphs. Advances in neural information processing systems, 33:22118 22133, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks arXiv preprinl ar X60: 02907, 2016.
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30 -0,07,05555 2009.
15

---

Published in Transactions on Machine Learning Research (04/2024)
Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná. Hyperbolic geometry of complex networks. Physical Review E,, 82(3):036106, 2010.
Jacob Leygonie, Steve Oudot, and Ulrke Tilmmann. A framework for differential calculus on persistence barcodes. Foundations of Compulational Mathematics, pp. 1-63, 2021.
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. In International conference on machine learning, pp.
PMLR, 2021.
David Liben-Nowell and Jon Kleinberg. The link prediction problem for social networks. In Proceedings of the twelfth international conference on Information and knowledge management, pp. 556-559, 2003.
Nikola Milosavljević, Dmitriy Morozov, and Primoz Skraba. Zigzag persistent homology in matrix multi- plication time. In Proceedings of the twenty-seventh Annual Symposium on Computational Geometry, pp. 216 225, 2011.
James R. Munkres. Elements of algebraic topology. CRC press, 2018.
Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. Ad- vances in neural information processing systems, 30, 2017.
Nina Otter, Mason A Porter, Ulrike Tillman,, Peter Grindrod, and Heather A Harrington. A roadmap for the computation of persistent homology. EPJ Data Science, 6:1-38, 2017.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Bastian Rieck. On the expressivity of persistent homology in graph learning. arXiv:2302.0080 2023.
ar preprint
Bastian Rieck, Christian Bock, and Karsten Borgwardt. A persistent weisteller-lehman procedure for graph classification. In International Conference on Machine Learning, pp. 1448-5458. PMLR, 2019.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collec- tive classification in network data. AI magazine, 2933)933, 2008.
Primoz Skraba and Bei Wang. Approximating local homology from samples. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pp. 174-192. SIAM, 2014.
Bernadette J Stolz, Jared Tanner, Heather A Harrington, and Vidit Nanda. Geometric anomaly detection in data. Proceedings of the national academy of sciences, 117(33)):966441166 2020.
Komal Teru, Etienne Denis, and Will Hamilion. Inductive relation prediction by subgraph reasoning. In PMTR, 2020.
International Conference on Machine Learning, pp.
Pelar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXio preprint arXiv: 10903, 2017.
Julius Von Rohrscheidt and Bastian Rieck. Topological singularity detection at multiple scales. In Interna- tional Conference on Machine Learning, pp. 35175-35197. PMLR, 2023.
Xiyuan Wang, Haotong Yang, and Muhan Zhang. Neural common neighbor with completion for link pre- diction. arXiv preprint arXio:2302.00800 2023.
Chi-Chong Wong and Chi-Man Vong. Persistent homology based graph convolution network for fine-grained 3d shape segmentation. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 7098 7107, 2021.
Zuoyu Yan, Tengfei Ma, Liangeai Gao, Zhi Tang, and Chao Chen. Link prediction with persistent homology: An interactive view. Tn International Conference on Machine Learning, pp. 11659 1099-1160 11669. PMTRR, 2021.
16

---

Published in Transactions on Machine Learning Research (04/2024)
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances Neural Information Processing Systems, 34: 9061 9073, 2021.
Qi Zhao, Ze Ye, Chao Chen, and Yusu Wang. Persistence enhanced graph neural network. In International Conference on Artificial Intelligence and Statistics, pp. 2896-2906. PMLR, 2020.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al open, 1:57- 81, 2020.
Shichao Zhu, Shirui Pan, Chuan Zhou, Jia Wu, Yanan Cao, and Bin Wang. Graph geometry interaction learning. Advances in Neural Information Processing Systems, 33:7548 7558, 2020.
Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propagation. ProQuest Number: INFORMATION TO ALL USERS, 2002.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(14))110--1198, 2017.
Marinka Zitnik, Monica Agrawal, and Jure Leskovee. Modcling polypharmacy side effects with graph con- volutional networks. Bioinformatics, 34(13):1457 i466, 2018.
A More Related Works
Graph Learning In this research, our primary objective is to investigate the effectiveness of PLH in the domain of graph learning tasks. Graph learning has recently gained significant attention due its ability model complex relationships within various types of data, leading to novel insights and improved performance in multitude of applications Bronstein et al. (2021). The origins of graph learning be traced back to graph theory and graph-based algorithms,, which have been explored for several decades Fasley & Kleinberg (2010). The emergence of contemporary machine learning approaches has accelerated advancements in this field, with deep learning on graphs emerging as an especially promising area of research. The amalgamation of these disciplines has given rise to a multitude of innovative algorithms and techniques, such as Graph Convolutional Networks (GCN) Kipf & Welling (2016), Graph Attention Networks (GAT) Veličkovié et al.. (2017,, and GraphSAGI. Hamilton al. (2017). Graph learning techniques have found applications in nu- merous domains, including social network analysis, recommendation systems, bioinformatics, and computer vision Zhou et al. 2020). For instance, in social networks, researchers have utilized graph learning methods to detect communities, link prediction, and identify influential nodes Cai et al. (2018). In the realm of bioin- formatics, these methods have demonstrated potential in predicting protein-protein interactions, drug-larget interactions, and gene-disease associations Zitnik et al. (2018). Additionally, graph learning has exhibited considerable potential in computer vision tasks, such as semantic segmentation and 3D shape analysis Gu et al. 2019).
Node Classification and Link Prediction Graph learning, particularly in the realms of node classifica- tion and link prediction, has substantially propelled the progress in graph-based machine learning. In node classification tasks, the assignment of labels to graph nodes is informed by their attributes and the graph's 's structure. This field has evolved from heuristic methods to advanced machine learning techniques. For instance, early approaches, such as the one presented by Zhu & Ghahramani (2002). relied on the majority label of neighboring nodes for classification. The shift to more sophisticated models was marked by the integration of feature engincering and learning models, with significant contributions like Sen et al.] (2008) combining structural and attribute information. The emergence of graph embedding techniques, including works by Perozzi et al. (2014) and Grover & Leskoved (0166), introduced the concept of representing nodes
17

---

Published in Transactions on Machine Learning Research (04/2024)
low-dimensional vectors. The most transformative development, however, has been the advent of Graph Neural wetworks (GNNs), as evidenced by studies such as Kipl & Welling 20166 Veličković et al. 2017 Hamilton et al. (017)) and Chiang et al. (2019)
Link prediction, another significant graph task, is integral to analyzing complex networks with applications across various domains including social network analysis (Liben-Nowell & Kleinberg 2003), recommendation systems (Koren et al. 2209 Addmic & Adar 2003), biological networks (Coulomb et al,, 2005), and knowledge graph completion (TTeru et al. 2020). The goal here is to predict potential connections between pairs of nodes based existing network data, which is fundamental in understanding network structures. Techniques for link prediction have evolved over time, ranging from similarity-baser methods (e.g., common neighbors, Jaccard coefficient, Adamic-Adary and matrix factorization to machine learning approaches like node2vec
and graph convolutional networks (rrovrr & Leskovec 2016
Kipf & Welling 2016
Yan et al. 2021
B Proof of Theorem 4.1
Proof. Noting that both subgraphs are finite, the numbers of both vertices and edges are finite. Hence the number of simplices VR, (g")) or VR. (g²") are finite. It shows that the number of births and deaths of topological features are finte. Consequently, there is a finite number of changes in the topological features
varies. Therefore, the persistence modules induced by the Vietoris-Rips filtration q-tame. By Theorem 8 in Chazal & Michel (2021) we have da (dgmp, dgm,)) S max.ge wwe)- w w'(e) I.
C Fermi-Dirac Decoder
The Fermi-Dirac Decoder is a component of the PLH-GNN model and serves as type of activation function. It is inspired by the Fermi-Dirac distribution from quantum mechanics, which describes the probability of finding particles in quantum states. Tn deep learning, what we take away mostly is the flexibility of the function. Here, we define the decoder as F(u, v) = 1/(1 + e(d(a,e) where d(u, v) is the metric between node and v, and r,t are hyperparameters (Krioukov et al.) 2010 Nickel Kiela 2017: Yan et al.) 2021). It is worth noting that. F can be fine-tuned by the temperature parameter 1: when i. is close to O, the function becomes more step-like and introduces higher non-linearity, while when & increases, the function becomes more linear and smooth. This flexibility can be useful in certain deep learning tasks where controlling the degree of non- non-linearity is desired.
D Experimental Details
D.1 Experimental Environment
The experiments are conducted on a server, which is powered by an Intel(R) Xeon(R) W-2123 CPU clocked at 3. 3.60GHz and is backed by 64 GB of RAM. The system is further enhanced with four Geforce RTX 2080 Ti GPUs, each with 11 GB of memory. On the software side, we utilize key packages for deep learning, with the main package versions being PyTorch 1.12.1, CUDA 11.3, and cuDNN 8. Additional dependency roquirements are specified within the source code.
D.2 Datasets
Synthetic Datasets In the synthetic experiments, we utilize random graphs, commonly referred to Erdös-Réme Rényi graphs or binomial graphs (ERDaS & R& 1959. Gilbert 1959.. These graphs are character- ized by their edge selection process: for a given graph, each potential edge is independently chosen with a predefined probability denoted as The generation of the graphs was conducted using the hyperparameters specified in Table 0
Real-world Datascts Real-world datasets include ogbn-arxiv, ogbl-ddi, and Protcin-Protein Interaction networks (PPI). Both the arbn-arxiv and ogbl-ddi datasets are part of the Open Graph Benchmark (OGB) (u et al. 2020). OGB is an extensive collection of benchmark datasets, data loaders, and evaluators.
18

---

#Edges Published in Transactions on Machine Learning Research (04/2024)
Table 6: Hyperparameters utilized for the generation of random graphs.
Graph
#Nodes
G1
1000
0.007
G2
2000
0.005
G3
5000
0.002
specifically designed for graph machine learning. The PPI dataset is derived from the research paper by Zitnik & Leskoved (017). The PPI dataset comprises positional gene sets, motif gene sets, and immunological signatures. These various sets act as features, with total count of 50. Additionally, the dataset includes gene ontology sets which serve as labels, numbered at 121 in total. For summary of the fundamental characteristics of these datasets, invite readers to consult Table 7 Further detailed information about these datasets is available in the original sources ZZinikk & Leskovec 2017 Hu el al. 2020
Table 7: Summary of real-world datasets.
Dataset
# Graphs
#Nodes
Task
Metric
ogbn-arxiv ogbl-ddi PPI
169,343
1,166,243
Node Classification
Accuracy
4,267
1,334,889
Link Prediction
Hits@20
20
2,245.3
61,318.4
Link Prediction
AUROC
D.3 Hyperparameters
Filtrations As discussed in Subsection 5.1 the filtration mechanism utilized in synthetic experiments is characterized by the dimension of simplices discerned within each subgraph. Precisely, the filtration function designates vertices with a value of 0, edges with 1, and 2-simplices with 2. This filtration approach is instrumental identifying proximal triangles to a given vertex, primarily because edges and 2-simplices concurrently manifest in Vietoris-Ripe filtrations when hop distance employed. For empirical investigations in real-world scenarios, we employ Victoris-Rips filtration, as introduced in Subsection 4.2
Experimental Hyperparameters In this section, delineate the hyperparameters critical for replicat- ing the findings of our main study. Specifically, the symbol H is utilized to represent the maximal hops within each local subgraph. Concurrently, D signifies the threshold for degrees within the framework of the rPLH algorithm. Additionally, the resolution indicates the size of the persistent image.
Table 8: Hyperparameters. In synthetic experiments, the threshold parameter D is set to oo adhering to the standard PLH algorithm's configuration.
Experiment
H
D
Resolution
#Ephocs
# #Runs
syuthetic
06
100
20
ogbn-arxiv
500
ogbl-ddi
2
16
200
10
PPI
2
16
2500
20
19


Reviews:
[{"review_id": "OUbif9qYpO", "reviewer": "Reviewer_XuSs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This article is very well written and easy to follow, and the application of topological descriptors to graph data is an important one in machine learning. My main concern however is that I struggle to understand the actual added value of looking at punctured and annular subgraphs rather than simply taking the persistent homology of regular subgraphs. I understand Figure 1 and Table 1, but I think one could make a symmetric argument: it is easy to build examples where regular local subgraphs are different (in terms of homology groups), but annular local subgraphs are the same. For instance, take the following graphs (described with their edges): (v_0, v_1), (v_0, v_2), (v_0, v_3), (v_1, v_2), (v_2, v_3), (v_0, v_4), (v_0, v_5), (v_0, v_6), (v_4, v_5), (v_5, v_6) and (v_0, v_1), (v_0, v_3), (v_1, v_2), (v_2, v_3), (v_0, v_4), (v_0, v_6), (v_4, v_5), (v_5, v_6).\n\nThen the annular subgraphs (around the v_0 vertices) with parameters r=1 and s=2 are the same (betti 0 = 2, betti 1 = 0), while the regular subgraphs are different (betti 1 = 4 (up) and 2 (bottom)). My criticism also extends to the experiments: as far as I understand, on the synthetic data, the goal is to predict the structures of the annular subgraphs around the vertices, so it is not surprising that the persistent homology of annular subgraphs work better than the persistent homology of regular subgraphs, it feels like a circular (empirical) demonstration. On actual data, in particular Table 4, it is not obvious that annular subgraphs work systematically better than regular ones, sometimes they do, sometimes not, but results are overall quite similar. Hence, given that the stability result is just an application of a known theorem, I have difficulties to see where the contribution is. It would be nice to provide data sets where the prediction goal is oblivious to the types of subgraphs, and on which annular subgraphs are more efficient than regular ones.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this article, the authors propose to use local persistent homology for machine learning on graphs. More precisely, they show that, instead of considering the Vietoris-Rips persistence diagrams of subgraphs (as it is currently done in the literature on local persistent homology), one can rather look at punctured and annular subgraphs, that is, subgraphs made of the vertices which are at distance at least r and at most s from a given vertex v (r,s are parameters). In fact, these subgraphs can be seen as generalizations of the link of v, whose reduced homology is the same as the (mathematical) local homology group of v, that is, the homology group of the whole space X relative to X without v. Motivated by this connection, the authors provide a stability result for the persistent homology of these local annular subgraphs, and demonstrate their usefulness by applying it on several node classification tasks, where they show positive comparison of their approach over both persistent homology on ordinary subgraphs and over non-topological baselines (on synthetic data), or positive comparison of their approach combined with persistent homology on ordinary subgraphs (on real-world graph data).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "---Would it be possible to prove an approximation quality result for rPLH? Something like an upper bound (that depends on D) for the bottleneck distance between the persistence diagrams of regular and annular subgraphs? Typically, this upper bound would decrease as D increases. I think this would further motivate the use for rPLH, in addition to better running times.\n\n---I would recommend to introduce punctured subgraphs as special cases of annular subgraphs where the r parameter is between 0 and 1. Right now, it is a bit weird to see the notation with epsilon for punctured subgraphs, as it is not clear before seeing the notation of annular subgraphs, which appear later in the text.\n\n---It would be good to be explicit about the r and s parameters that are used to compute the annular subgraphs in Figure 1.\n\n---It would be nice to also provide the bandwidth parameters used for the persistence images in Section D.3, as this parameter is also very important.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Tbkm7fZLpB", "reviewer": "Reviewer_17y1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- The contribution is relatively novel, representing one of the first works applying PLH for graphs --- leveraging PH on annular local subgraphs.\n- The paper is very well-written and easy to follow; \n- The proposed method is simple and flexible --- it can be easily integrated into different GNNs.\n- The paper reports experiments on artificial and real-world datasets and includes an ablation study.\n\n**Weaknesses** \n- The paper relies on a few examples to motivate the applicability of PLH with punctured local subgraphs. In this regard, can't we also create examples of graphs that are distinguishable via local subgraphs but not via the punctured ones? Overall, I found this motivation weak, and I think the paper would benefit from a theoretical analysis of the expressiveness of these approaches;\n\n- The description of the rPLH method could be improved, for instance, by: i) discussing the motivation underlying the use of node degree as (node) importance measure; ii) clarifying why the computational analysis only relies on 0-dim and 1-dim simplices while the paper considers filtrations that result in higher-order simplicial complexes; iii) describing more precisely the pseudo-code --- e.g., using math notation instead of 'top-D i-th edge layer vertices' and indicating the variable r before using it). It would also be helpful to say that the subgraph induced by the sets of vertices (output of the procedure) defines the local subgraph used to obtain the filtration.\n \n- Overall, the empirical gains do not seem statistically significant (see Table 4 -- PH vs PLH). Also, the experiments on real-world data (Table 3) do not report results for PH-based baselines.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work applies persistent local homology (PLH) to graph-structured data. The proposed method leverages Rips complexes built based on shortest-path distances in punctured local subgraphs. To alleviate the computational cost, the paper introduces a greedy pruning scheme to the local subgraphs based on node degrees--- the resulting method is called reduced PLH (rPLH). Vectorizations of the persistence diagrams are combined with GNN embeddings to obtain node- or edge-level predictions. Experiments on node classification and link prediction show the efficacy of the proposal.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Since I am inclined to accept the paper in its current form, I have only minor suggestions:\n\n- Section 4.2: 'F as the selected filtration function' --- F is the filtration itself\n- Section 4.1:  In the fragment \"the punctured local subgraph ... is obtained by excluding the central vertex v from ..., where $0 < \\epsilon < 1$ thus ...\", it is not clear the role of epsilon here;\n- Paragraph PLH-GNN Model: \"we transform the node features into edge features by applying operations such as elementwise sum, difference, squared difference, or just concatenation\" --- Since the paper only mentions undirected graphs, shouldn't this operation be order-invariant?\n- Figure 2 is not clear, especially the path plh_v --> plh_{uv} (the same for h).\n- In many applications, we are given graphs with edge features (or without them) instead of edge weights. Could you describe the Vietoris-Rips Filtration in this more general case?\n- In Table 4, the baseline that doesn't use topological features achieves higher numbers than those from Table 3b. Could you explain why?", "broader_impact_concerns": "I have no concerns regarding broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "c23KcXaA7X", "reviewer": "Reviewer_gHvS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is very well written. The authors provide a clear position and sufficient background to understand the proposed PLH. \n2. The more expressiveness of PLH is justified by a clear example.\n3. Some practical problems such as PLH computation have been taken care empirically. \n4. The experiments should some effectiveness of PLH. \n\nWeaknesses:\n1. The expressiveness of PLH is justified by just showing examples and compared with PH. Is it possible to add some quantitative justification of expressiveness, such as motif counting capability?  Also, how does it compare with WL tests?\n\n2. The experiments are weak in this work. \nFor link prediction, can the authors use larger graphs from OGB for evaluation such as, PPA, COLLAB? The used DDI is small and dense, which often presents some properties different from common link prediction tasks. Also, when comparing methods over PPA, COLLAB, can the authors include the methods based on labeling tricks [1] as the baselines, such as SEAL. I noticed that the authors used SEAL for PPI but it is unfair to some extend because SEAL does not leverage node features, while for PPI,  node features are crucial. For PPA and COLLAB, as the node features here are not that important, the capability of capturing structure features, as what PLH aims to do, is more important. In particular, I do not think the current definition of PLH may address the node ambiguity issue as discussed in [1] for link prediction. I expect the authors may comment on this aspect. Also, whether PLH is scalable enough for these larger graphs is also a interesting question to investigate. \n\nFor node classification, the experiment is also weak, which just adopts one dataset. More datasets are suggested to be included. \n\n\n[1] Labeling trick: A theory of using graph neural networks for multi-node representation learning, NeurIPS 2021, Zhang et al.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This works proposes to use persistent local homology for graph learning. Persistent local homology is defined for the subgraph around each node within a radius d while the center node and its neighborhood within a radius r get removed. This work proposes this definition and also uses an example to show the more expressiveness of PLH than the traditional PH. The work also discusses who to simplify PLH by sub-selecting high-degree nodes. Some real world data experiments have been provided to verify the value of PLH.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The requested changes are the answers to the weaknesses listed as above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers found the paper interesting and  well written but had  few comments and questions. The authors addressed those comments and updated the paper to reflect them. The reviewers acknowledged and appreciated those discussions and changes that made the paper stronger. 

Despite one reviewer that found the contribution to be limited,  all reviewers agree that the claims have been demonstrated theoretically and empirically. Since the paper is technically sound and the results presented in this paper are of interest to the community, the paper fits all acceptance criteria and I recommend acceptance.
Decision: Accept (poster)