Neural Approximation of Graph Topological Features
Authors: Zuoyu Yan
Tengfei Ma
Liangcai Gao
Zhi Tang
Yusu Wang
Chao Chen
Venue: NeurIPS 2022 Accept (2022)
Keywords: Persistent Homology
Topological Data Analysis
Neural Execution
Graph Nerual Networks

Abstract: Topological features based on persistent homology capture high-order structural information so as to augment graph neural network methods. However, computing extended persistent homology summaries remains slow for large and dense graphs and can be a serious bottleneck for the learning pipeline. Inspired by recent success in neural algorithmic reasoning, we propose a novel graph neural network to estimate extended persistence diagrams (EPDs) on graphs efficiently. Our model is built on algorithmic insights, and benefits from better supervision and closer alignment with the EPD computation algorithm. We validate our method with convincing empirical results on approximating EPDs and downstream graph representation learning tasks. Our method is also efficient; on large and dense graphs, we accelerate the computation by nearly 100 times. 

Neural Approximation of Graph Topological Features
Zuoyu Yan
Tengfei Ma
Wangxuan Institute Computer Technology Peking University yanzuoyu3@pku. eewpppuuuuduuee..m edu.cn cn
IBM T. J. Watson Research Center
tengfei mam.:11@1mmmm ma1@ibm... com com
Liangcai Gao
Zhi Tang
Wangxuan Institute of Computer Technology Peking University glcêpku. hemplu..dd..coo
Wangxuan Institute of Computer Technology Peking University
tangzhi@pku edu.
Yusu Wang
Chao Chen'
Hahcroğlu Data Science Institute
Department of Biomedical Informatics
University of California
Stony Brook University chao. chen. 10stonybrook. edu
yusuwang@ucsd, edu
Abstract
Topological features based persistent homology can capture high-order struc- tural information which can then be used to augment graph neural network methods. However, computing extended persistent homology summaries remains slow for large and dense graphs and can serious bottleneck for the learning pipeline. Inspired by recent success in neural algorithmic reasoning, we propose a novel graph neural network to estimate extended persistence diagrams (EPDs) on graphs efficiently. Our model is built on algorithmic insights, and benefits from better supervision and closer alignment with the EPD computation algorithm. We val- idate method with convincing empirical results approximating EPDs and downstream graph representation learning tasks. Our method is also efficient; on large and dense graphs, we accelerate the computation by nearly 100 times.
Introduction
Graph neural networks (GNNs) have been widely used in various domains with graph-structured
data 45
27
22
42 Much effort has been made understand and improve graph representation
28 An intuitive solution is to explicitly inject high order information, such as graph /tptrogaall/struuturall information, into the GNN models [51 26 To this end, persistent homology
power 47
30
3
[S] 4. which captures topological structures (e.g., connected components and loops) and encodes them summary called persistence diagram (PD), have attracted the attention of researchers. Indeed, persistence has already been injected to machine learning pipelines for various graph learning tasks [55] 56 16
been found helpful to use the so-called extended persistence diagrams (EPDs) 100 which contain richer information than the standard PDs.
4 8 55) In particular,
Despite the usefulness of PDs and EPDs, their computation remains a bottleneck in graph learning. In situations such as node classification (56] or link prediction [50], one has to compute EPDs on vicinity graphs (local subgraph motifs) generated around all the nodes or possible edges in the input graph. This can be computationally prohibitive for large and dense graphs. Take the Amazon
"Conrespondence to Chao Chen, Yusu Wang, and Liangcai Gao
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

O-dim persistence point
246
death time
persistence point
I-dim extended
E5
146
Eg
14
1/4
36
15
E4
4
C
13 34
24
Uig
E3
[3
4
122
02
C2a
G25
4
11
11
C1.
C1
C1g
hirth time
(a)
(b)
(c)
(d)
Figure 1: An explanation of extended persistent homology and its computation. The seiggt-funnttinn based filtration is only for illustration purposes. (a) The input graph is plotted with given filter function. (b) the extended persistence diagram of (a). Commonly speaking, the persistence points on
the diagonal (uncritical points) should not be plotted. We plot these points for a clearer illustration. (c) and (d) are examples of finding the loops the input graph.
Computers dataset [37] an example. To compute EPDs vicinity graphs take several seconds on average, and there are 13381 nodes. So to compute all EPDs with a single CPU can take up to a day, This is not surprising as, while theoretically EPD for graphs can be computed in On log n) time (2), that algorithm has not been implemented, and practical algorithms for computing PD take quadratic time in worst case [50]
These computational difficulties raise the question: can we approximate the expensive computation of EPDs using an efficient learning-bused approach? ? This is challenging question due to the complex mathematical machinery behind the original algorithm. First, the algorithm involves a reduction algorithm of the graph incidence matrix. Each step of the algorithm a modulo-2 addition of columns that can involve edges and nodes far apart. Such algorithm can be hard to be approximated by a direct application of the black-box deep neural networks.
The second challenge comes from the supervision. The output EPD is a point set with an unknown cardinality. The distance between EPDs, called the Wasserstein distance [9] [1] involves a complex point matching algorithm. is nontrivial to design a deep neural network with variable output and to support supervision via such Wassserstein distance. Previous attempts [8] 29 directly use black-box neural networks to generate length vectorization of the PDs/EPDs and use mean squared error cross-entropy loss for supervision. The compromise in supervision and the lack of control make it hard to achieve high-quality approximation of PDs/EPDs.
In this paper, propose novel learning approach approximate EPDs graphs. Unlike previous attempts, we address the aforementioned challenges through a carefully designed learning framework guided by several insights into the EPD computation algorithm.
In terms of model output and supervision, we observe that the computation of EPDs can be treated as an edge-wise wise prediction instead of whole-graph groph prediction. Each edge in the graph is paired with another graph element (either vertex or edge), and the function values of the pair are the coordinates of a persistence point in the EPD. This observation allows to compute EPDs by predicting the paired element for every edge of the graph. The Wasserstein distance can naturally decomposed into supervision loss for each edge. This element-wise supervision can significantly improve learning efficiency compared with previous solutions, which treat PDs/EPDs as a whole- -aalhgggahhhh representation and have to use whole-graph grole representation pooling.
Another concern is whether and how a deep neural network can approximate the sophisticated EPD algorithm. To this end, we redesign the algorithm so that it is better aligned with algorithms that are known to be learnable by neural networks. Recall we observe that computing EPDs can be decomposed into finding pairing for each edge. We show that the decomposition is not only at the output level, but also at the algorithm level. The complex standard EPD computation algorithm can indeed be decomposed into independent pairing problems, each of which can be solved exactly using a classic Union-Fit Find algorithm [12.. To this end, we draw inspiration from recent observations that neural networks can imitate certain categories of sequential algorithms graphs [4 46). We

---

propose carefully designed graph neural network with specific message passing and aggregation mechanism to imitate the Union-Find algorithm.
Decomposing the algorithm into Union-Find subroutines and approximating them with a customized GNN provide better alignment between our neural network and the EPD algorithm. A better alignment can lead to better performance [48]. Empirically, we validate our method by quantifying its approximation quality of the EPDs. On two downstream graph learning tasks, node classification and link prediction, we also show that our neural approximations are as effective as the original EPDs. Meanwhile, on large and dense graphs, our method is much faster than direct computation. In other words, the approximated EPDs do not lose accuracy and learning power, but can be computed much more efficiently. Finally, we observe that our model can be potentially transferred unseen graphs, perhaps due to the close imitation of the Union-Fing subroutine. This is encouraging as we may generalize topologiaal computation to various challenging real-world graphs without much additional effort.
In summary, we propose an effective learning approach approximate EPDs with better supervision and better transparency. The technical contributions are as follows.
We reformulate the EPD computation as edge-wise prediction problem, allowing better supervision and more efficient representation learning. We show that the EPD computation can be decomposed into independent pairing problems, each of which can be solved by the Union-Find algorithm.
we design a novel graph neural network architecture to learn the Union-Find algorithm. The closer algorithmic alignment ensures high approximation quality and transferability.
Inspired by recent neural algorithm approximation works 43 46
2 Background: Extended Persistent Homology
We briefly introduce extended persistent homology and refer the readers to 10 14] for more details.
Ordinary Persistent Homology. Persistent homology captures O-dimensional (connected com- ponents). I-dimensional (loops) topological structures, as well as high-dimensional analogs, and measures their saliency via a scalar function called filter function. Here will only describe it for the graph setting. Given a input graph G = (V, E). with node set V and edge set E, we call all the nodes and edges simplices. Denote by X V E the set of all simplices. We define filter function on all simpices, f X + IR. In the typical sublevel-set setting, f is induced by a node-valued function (e.g., node degrees), and further defined on edges f f(w)) = (far((((), fw))..
Denote by X, the sublevel set of X, consisting of simplices whose filter function values S a, (x X- of growing spaces, called an ascending filtration of X: 0 X- C ... C X = X. As X, increases from 0 to X, new topological structures gradually appear (born) and disappear (die). For instance, the blue square persistence point at (12, ta) in Figure I (b) indicates that the connected component U2 appears at X12 and is merged with the whole connected component at Xtx.
E [xx) S a). As the threshold value increases from -x to co, we obtain sequence
Applying the homology funetor to the filtration, we can more precisely quantify the birth and death of topological features (as captured by homology groups) throughout the filtration, and the output the so-called persistence diagram (PD), which a planar multiset of points, each of which (b, d) corresponds to the birth and death time of some homological feature (i.e., components, loops, and their higher dimensional analogs). The lifetime dd is called the persistence of this feature and intuitively measures its importance w.r.t. the input filtration.
Extended Persistent Homology. In the ordinary persistent homology, topology of the domain (e.g., the graph) will be created at some time (has a birth time), but never dies (i.c., with death time being equal to +00). We call such topological features essential features. In the context of graphs, the importance of 1D essential features, corresponding to independent loops, are not captured via the ordinary persistence. To this end, an extended persistence module is introduced in 10 0 H(X + ... H(x,) - ... H(X) H(X, Xxx) + + ((XXX*) +
X
where Xa = (5 X 2 a) is superlevel sei of X at value a. We say that the second part H(X, H(X - ... H(X Xa) -.... H(X, x is induced by descending filtration. If we inspect the persistence diagram induced by this extended sequence, as H(X, X X X- is trivial, all the loop features created will also be killed in the end, and thus captured by persistence points whose
3

---

birth happens in the ascending filtration and death happens in the descending filtration. In what follows, we abuse the notation slightly and use ID EPD to refer to only such persistence points (i.e.. born in ascending portion and death in descending portion) in the persistence diagram induced by the extended module" We use OD PD to refer to the standard ordinary OD persistence diagram induced by the ascending sequence. Our goal is to compute/approximal
the union of OD PD and 1D EPD.
Specifically, in the graph setting, at the end of the ascending filtration, some edges, which are the so-called negative edges (as they kill homological features), are paired with the vertices. These correspond to points the OD PD, capturing the birth and death of connected components in the ascending filtration. Those unpaired edges, called posirive edges, will create independent loops (ID homology for graphs) and remain umpaired after the ascending filtration. The number of such unpaired edges equals to the 1st Betti number 3n (rank of the 1st homology group). These edges will then be paired in the descending part of the persistence module and their birth-depth times give rise to ID EPD. An example is given in Figure [b). Note that since our domain is a graph, 81 equals the number of independent loops, which also equals to 81 [ - V + 1 for a connected graph. Hence we also say that ID EPD captures the birth and death of independent loop features. The birth and death times of the loop feature correspond to the threshold value a's when these events happen. In general, the death time for such loop feature is smaller than the birth time. For example, the red triangle persistence point in Figure (b) denotes that the red cycle in Figure [ (a) appears at Xts in the ascending filtration and appears again at X 4 in the descending filtration.
Finally, PDs live in an dimeniiiadme space equipped with an appropriate metric structure. such as the so-called p-th Wasserstein distance [11] or the bottleneck distance (9. They have been
combined with various deep learning methods including kernel machines [34 25 5, convolutional
neural networks [8] 20 44 [57), transformers [53] connectivity loss 7 17 and GNNs [50 8 50
55 16 4]. During learning, there have been many works in the literature to vectorize persistence
diagrams for downstream analysis. Among these works popular choice is the persistence image []]
3 Algorithm Revision: Decomposing EPD into Edge- Wise Paring Predictions
In this section, we provide algorithmic insights into how the expensive and complex computation of EPDs can be decomposed into pairing problems for edges. And each pairing problem can be solved exactly using a Union-Find algorithm. The benefit is two-folds. First, the decomposition makes it possible to train the neural network through edge-wiss wise supervision. Thiss allows to adopt the popular and effective edge-predictte the Union-Find and sequential algorithms which are known to be imitable by neural networks. This gives us the opportunity to design a special graph neural network to imitate the algorithm accurately, and to approximate EPDs accurately.
GNN for the goal. Second, we observe the similarity between
Decompose the EPD Computation into Pairing Computations. Recall that our goal is to compute the OD PDs and ID EPDs PDo and PD, The reason for not estimating OD EPDs (or not including the global max/min pair that corresponds to the whole connected component) is that (1) the global max/min value is easy to obtain, and does not need an extra prediction; (2) in our setting, the global max/min pair will not be paired with any edge in the ascending filtration. In the later section, the estimation of EPDs denote the estimation of PDo and PD1.
We observe that on these diagrams, each point corresponds to a unique pairing of graph elements (vertex-edge pair for PDo, edge-edge pair for PD:). Each pair of elements are essentially the "creator" and "destroyer" of the corresponding topological feature during the filtration. And their filtration values are the birth and death times of the topological feature. For example, the persistence point located at (42, 12) in Figure (b) denotes that the edge U243 is paired with u2. We consider the following "unique pairing" for all edges in the graph: Consider each edge in the ascending filtration: the edge is a destroyer the ascending filtration, it will be paired with a vertex. Otherwise, this edge is creator in the ascending filtration and will be paired during the descending filtration with another edge e'. We note that this is not in conflict with the fact that the PDs/EPss are often sparse. Many pairings are local and only pair adjacent elements. They correspond to per-ppersitennce points living in the diagonal of the diagrams.
We note that in standard terminology, extended persistence diagram will also contain persistent points born and destroyed both in the descending sequence.

---

Algorithm/ Sequential algorithm
1: Input: graph G (V. F.,, filter function f.
5: Q.pop-min()
2: Initialise-Nodes(,
6: for E Geiighoors( do
3: Q Sort-Queue V)
7: Relax-Edge(u, v,
4: while Q is not empty do
8: end for
9:
end while
Algorithm 2 Computation of EPD
Input: filter function f. input graph G EV)
f(C,)) f(i), , E, Li {(i,i)} [(C;,:
2: E.E sV. f)
8:
end for
3: PDg = Ohion-FFndd( , E, f),) PD1 =
9:
PD
Union-Find-step(V + C.
4: for E V do
(i), J.C.
5: C:
(i E (() > f()),
10:
PD PD
Fg F
11:
end for
6: for C₁ E, do
12: Output: PDo, PD
Algorithm& 3
(Sequential)
1: Input: V. f. C,
14:
prgmaaappu.aauuepppaaa po.value)
2: PD = =0
15:
l.root =
3: for Vo
16:
if pu C, and pu E C₁ then
4: v.value f()), v.root =
17:
PD + ((u.value,
5: end for
18:
end if 19: end if
6: Q = Sort V), Q = Q- (v) < f(i))
G (Q. Eq} where Eq EUQ
20: end for
7: while Q is not empty do
21: end while
8: u = Q-pop-min()
22: Function: Find-Root(u)
9: for E (neighbors(w)) do
23: pu u
10:
24: while pu & pu.root do
11:
puu pv Find-Root(u)) Find-ooooo
25: pu.root = (pu.root),roof, pu pu.root
12:
pu + pu then
26: end while
13:
crrginnpu.valuue
value)
27: Return: pm
This pairing view gives us the opportunity transform the computation of EPDs into pairing prediction problem: for every edge in the graph, we predict its pairing element. This will be the foundation of our design of the GNN in Sec. | Meanwhile, we observe that the decomposition is not only at the output level. The original algorithm of EPD, a sequential modulo-2 matrix reduction algorithm, indeed be rewritten into set of independent algorithm subroutines, each for the computation of one pairing, Each subroutine is Union-Find algorithm. This new decomposed EPD algorithm has not been reported before, although the idea follows from existing work 22). For completeness, we will provide a proof of correctness of the algorithm.
Description of Algorithm 2. The pscudocode for ID EPD computation is shown in Algorithm 2 We leave the algorithm for OD PD to the supplementary material For simplicity presentation, we assume that all vertices have distinct function values f V value equals to finding the pairing. To compute the EPD, we traverse all nodes in the vertex set and find their extended persistence pairing. Combining the persistence pair from all nodes, the final EPD. The algorithm complexity analysis is provided in the supplementary material.
Therefore finding the persistence
obtain
Finding persistence pairing for nodes. For node u; V, we can call Algorithm 3 to identify the corresponding persistence pair. In particular, the algorithm first sorts the graph elements according to an input scalar function, then does the edge operation by finding the roots of the corresponding nodes and merging these nodes. See Figure for a simple illustration. For node U1 there are three upper edges: Uj u3, Uj U4, and U Ug. We put each such edge u,u, in different component C,, call this upper-edge splitting operation - and start to sweep the graph in increasing values starting at (u:). Then, the first time any such components merge will give rise to new persistence
'The algorithm needs a single run of Union-Find 44 and very similar to Algorithm which subroutine used by A
WWe can add jitter to the original filter function. The output EPDs will only have minor changes
5

---

(1,
N2
(b,,d,)
PDGNN
MLP
Compute Pl
(Optional)
App
(b d(p)
Input Graph
(b) Node Embedding
(c) Persistence Diagram
Figure The basic framework.
point in the 1D EPD. For instance, C1, and C1, first merge ugs and this will give rise the brown loop in Figure I a with (tq. f1) as its persistence point. While in Figure (d), the two connected components, C2 and C2, (originated from U2) will not be united. Therefore, node ug will not lead to any persistence point in the EPD.
Correctness. The idea behind Algorithm to compute the extended pairing for essential edges appears to be folklore. For completeness, we provide a proof of its correctness (stated in Theorem We provide sketch of the proof here, leaving the complete proof to the supplementary material.
Theorem 3.1. Algorithm
2 outputs the same ID EPDs as the standard EPD computation algorithm.
Proof sketch. To compute the ID EPDs, we simply need to find the pairing partner for all edges. Therefore, to prove that the two algorithms output the same ID EPDs, we need to prove that the output pairing partners are the same (or share the same filter value). We prove this by showing that both the standard EPD computation algorithm and Algorithm find the "thinnest pair", i.e, the paired saddle points are with the minimum distance in terms of filter value, for all edges.
Neural Approximation of Union-Find. In the previous paragraph, showed that the computation of ID EPDs can be decomposed into the parallel execution of Union-Find algorithms, which share a similar sequential behavior. This gives us the opportunity to approximate these Union-Find algorithms well, and consequently approximate EPDs well.
Approximating algorithms with neural networks is very active research direction 52 24
33
35
49]. Within the context of graph, GNNs have been proposed to approximate parallel algorithms (c.g.. Breadth-First-Seare and sequential algorithms (c.g.. Dijkstra) 43 41 46). Particularly relevant to us the success in approximating the category of sequential algorithms such as Dijkstra. These sequential algorithms, as generally defined in Algorithm [ sort graph elements (vertices and edges) according to certain function, and perform algorithmic operations according to the order. As described in previous paragraphs, the Union-Find algorithm also contains these steps, and can be expressed in sequential-like form (Algorithm Therefore we propose a framework to simulate the algorithm.
4 A Graph Neural Network for EPD Approximation
Previous section establishes the algorithm foundation by showing that we can decompose EPD computation into edge pairing prediction problems, each of which can be solved using a Union-Find algorithm. Based on such algorithmic insights, we next introduce our neural network architecture to approximate the EPDs on graphs. Our main contributions are: (1) transform the EPD computation into an edge-wise prediction problem, and solve it using a GNN framework, inspired by the GNN for link prediction; (2) we design new backbone GNN model PDGNN to approximate the Union-Find algorithm, with specially designed pooling and message passing operations.
4.1
EPD computation as edge-wise prediction problem
We have established that computing PD, and PD, can be reduced into finding the pairing partners for all edges. We transfer the problem into edge-wise prediction problem. We predict the persistence pairing for all edges. This very similar to standard link prediction problem [6] 50), in which one predicts for each node pair of interest whether it is real edge of the graph not.

---

Inspired by standard link paee-iccctiion GNN architectures 50), we propose our model (see Figure 2 as follows. (1) For an imput graph G EV and a filter function f. we first obtain the initial filter value for all the nodes: X = f(V) E R R and then use specially designed GNN model which later we call PDGNN G to obtain the node embedding for all these vertices: H = g()) E R (2) Subsequently, MLP (Multi-layer perceptron) W is applied to the node embeddings to obtain two dimensional output for each edge (u, v) E E., corresponding to its persistence pairing. Formally, we use PP W W( + hn])) E R as the persistence pair. Here, lt, and h2 denote the node embedding for node u and U; and + represents the concatenation of vectors.
In Algorithm 2 the Union-Find-stee should be implemented on all edges to obtain ID EPDs. Hence ideally we would need a large GNN model with node features proportional to the graph size so as to simulate all these Union-find-ster practice. On the other hand, there are many overlapping or similar computational steps between the Union-Fine Fand--Fin--eeeppp procedures on different vertices. Hence in practice, we only use bounded-siz node features.
in parallel simultancously. However this would be expensive in
4.2 PDGNN
In this section, we explain how to design the backbone GNN to approximate the Union- Find algorithm. Note the Union-Find is similar to known sequential algorithms but with few exceptions. We design specific pooling and message passing operations to imitate these special changes. These design choices will be shown to be necessary in the experiment section.
Recall a typical GNN learns the node embedding via an iterative aggregation of local graph neighbors. Following 477. we write the k-th iteration (the k-th GNN layer) as:
h = AGG (LMSG (AMMSG(())))
N()),, )
where hi is the node features for node u after k-th iterations, and Nuu) is the neighborhood of node u. In our setting, h. = zu initialized to be the filter value of node u. Different GNNs have different MSG and AGG functions, e.g., in GIN [47], the message function MSG is a MLP followed by an activation function, and the aggregation function AGG is a sum aggregation function.
We now describe our specially designed GNN, called PDGNN (Persistence Diagram Graph Neural Network), Compared with the Sequential algorithms (Algorithm I [46). our Union-Find algorithm (Algorithm 3 differs in: (1) the find-Root algorithm which needs to return the minimum of the component, (2) additional edge operations such as upper-edge splitting. To handle these special algorithmic needs, our PDGNN modifies standard GNNs with the following modules.
A new aggregation due to the Find-Root function. Finding the minimum intuitively suggests using a combination of several local min min-aggregations. Considering that the sum aggregation can bring the best expressiveness to GNNs (47, we implement the root-finding process by concatenation of sum aggregation and min aggregation as our aggregation function. To be specific:
AGG (.) (.) + MIN(.)
classic GNNs are not effective in "executing" Relax-Fdge subroutines. Furthermore, in Algorithm 2 we also need the upper-edge splitting operation for each vertex. In other words, the information of the separated components C2, are formed by the information from both nodes u; and uj. To this end, we use edge features and attention to provide bias using edges. Specifically, we propose the following message function in the k-th iteration:
Improved edge operations. As shown in 43 46
MSG (n- = 0² (a (h
A--
(3)
where k is an activation function, R is a MLP module, and o is the edge weight for uv. We adopt PRELU as our activation function, and the edge weight proposed in [42]
edge weight.
Training PDGNN. We use the 2- 2-Wasserstein distance between the predicted diagram and the ground truth EPD as the loss function. Through optimal matching, the gradient is passed to each predicted persistence pair. Since we have established the one-to-one correspondence between pairs and edges, the gradient is then passed to the corresponding edge, and contributes to the representation learning.
7

---

Table 1: Approximation error on different vicinity graphs
Datasel
Cora
Citeseer
PubMed
Photo
Computers
Evaluation
W2
W2
PIE
W2
PIE
W
PIE
W2
PIE
GIN_PI
5.03e-1
2.17e-1
4.08e-1
5.53
2.70
GAT PI
1,43e-1
1.95c-1
1.60
20.98
44.50
GAT
0.655
2,46e-2
0.431
4.04e-2
0.697
3.5e-1
1.116
1.09
1.145
2.21
GAT (+MIN)
0.579
1.53e-2
0.344
1.02e-2
0.482
4.60e-2
0.820
1.35
0.834
0.64
PDGNN (w/new)
0.692
2.77e-2
0.397
2.24e-2
0.666
9.01e-2
2,375
6.47
18.63
27.35
PDGNN
0.241
4.75e-4
0.183
4.43e-4
0.256
8.95e-4
0.224
4.33e-3
0.220
6.20e-3
Table 2: Classification accuracy on various node classification benchmarks
Method
Cora
Ciieseer
PubMed
Computers
Photo
CS
Physics
GCN
81.5.10.5
70.9-0.5
79.0.0.33
82.611244
91.2.11.2
91.1100.5
92.8.1.0
GAT
83.0:10.7
0,75-0.7
79.020.3
78.0
85.1=20.3
90.510.6
92.510.9
HGCN
78.0=1.0
68.0=0.6
76.5=0.6
82.140.0
90.5+0.0
90.5 = 0.0
91.340.0
PEGN (Truc Diagram)
82.7=004
71.900.5
79.4=0.7
86.6+0.6
92.7:00.4
93.3-00.3
94.3+0.1
PEGN (GIN_L PI)
818810.1 1
65.7-2.1
77.7-0.9
82.410.5
88.310.77
92,610.33
93.710.55
PEGN (PDGNN)
82.0+0.5
70.8=0.5
78.720.6
86.710.99
92.2:00.2
93.2-0.2
94.240.2
Experiments
In this section, thoroughly evaluate the proposed model from different perspectives. In Sec- tion [. we evaluate the approximation error between the predicted diagram and the original diagram and show that the prediction is very close to the ground truth. Even with small approximation error, we still need to know how much does the error influence downstream tasks. Therefore, in Section 5.2 evaluate the learning power of the predicted diagrams through 2 downstream graph representation learning tasks: node classification and link prediction. We observe that the model using the predicted diagrams performs comparably with the model using the ground truth diagrams. In Section (5.3 we evaluate the efficiency of the proposed algorithm. Experiments demonstrate that the proposed method much faster than the original algorithm, especially on large and dense graphs. Source code is available at https://gituub.compp hwtm///kuyyy/iia TEte//LLL--NNNN
Datasets. To compute EPDs, we need set the input graphs and the filter functions. Existing state-of-the-art models on node classification [56] and link prediction (50) mainly focus on the local topological information of the target node(s). Following their settings, for given graph G = (V, E), we extract the k-hop neighborhoods of all the vertices, and extract [V] vicinity graphs. In our experiments, is set to or (details are provided in the supplementary material).
In terms of filter functions, we use Ollivier-Rice curvature 31. heat kernel signature with two temprature values 39 19 and the node degred For input vicinity graph, compute 4 EPDs based on the 4 filter functions, and then vectorize them to get 4 peristence images [ Therefore, we get 4 V EPDs in total. The input graphs include (1) citation networks including Cora, Citeseer, and PubMed [6]; (2) Amazon shopping datasets including Photo and Computers [7;; (3) coauthor datasets including CS and Physies (37] Details available in the supplementary material.
Folllowing the settings in (56 50). we adopt the Ollivier Riccii curvature as the graph metric, and the distance to target node(s) as the filter function; Following the settings in (4), we set the temparature = 10 and 0.1 and adopt these two kernel functions as the filter functions; Node degree is used as the initial filter function in 16
Table 3: AUC-ROC score on various link prediction benchmarks
Method
Cora
Citeseer
PubMed
Photo
Computers
GCN
90.5+ 0.2
1.,6+1.9
89.6+3.77
91.8++0.0
87.8+0000
GAT
72.81 0.2
74.811..
80.310.0
92.910.33
86.4-1.0
HGCN
93.8100.1
96.6.10.1
96.3110.0
95.4.10.0
93.6.10.0
P-GNN
74.1
73,9+2.6
79,6+0.55
90,9++0.7
88.3+10
SEAL
91.3
89.8-12.3
92,4-11.2
97.8
96.8
TLC-GNN (True Diagram)
94.94-0.4
95.1 0.7
9..0
98.241..1
97.910.1
TLC-GNN (GIN PI)
93.51:0.2
93.3110.6
96.3 + 0.2
95.81 1.0
96.241..3
TLC-GNN (PDGNN)
95.0+-0.3
95.6++0.4
97.0++0.1
98.4++0.66
98.2-+0.3

---

Table 4: Time evaluation on different datasets (seconds)
Dataset
Cora
Citeseer
PubMed
Photo
Computers
CS
Physics
Avg. N/E
38/103
16/43
61/190
797/16042
1879/47477
97/431
193/1315
Fast [50
0.95
0.39
2.15
362.60
1195.66
5.72
24.14
Gudhi [40
0.44
0.21
1.00
583.55
8585.50
3,00
26.58
Ours
5.21
4.72
4.78
6.67
7.32
5.18
5.42
5.1 Approximation Quality
In this section, we evaluate the approximation error between the prediction and the original EPDs.
Evaluation metries. Recall that the input of our model is graph and a filter function, and the output is the predicted EPD. After obtaining the predicted EPD, we vectorize it with persistence image [I] and evaluate (1) the 2-Wasserstein (W2) distance between the predicted diagram and the ground truth EPD; (2) the total square error between the predicted persistence image and the ground truth image (persistence image error, denoted as PIE). Considering that our aim is estimate EPDs on graphs rather than roughly approximating persistence images, we use the W2 distance as the training loss, while the PIE is only used an evaluation metrie. Given an input graph (e.g., Cora, Citeseer, etc.) and filter function, we extract the k-hop neighborhoods of all the vertices and separate these vicinity graphs randomly into 80%/20% as training/test sets. We report the mean W2 distance between diagrams and PIE on different vicinity graphs and 4 different filter functions.
Baseline settings. PDGNN denotes our proposed method, that is, the GNN framework with the proposed AGG function and M function. Its strategy is to first predict the EPD, and then convert the persistence image. To show its superiority, we compare with the strategy from (8 29 i.e.,
directly approximate the persistence image of the input graph, as a baseline strategy. GIN and
GAT PI denote the baseline strategy with GIN 47 and GAT [42 as the backbone GNNs.
To show the effectiveness of the modules proposed in Section we add other baselines with our proposed strategy. GAT denotes GAT as the backbone GNN. GAT (+MIN) denotes GAT with the new AGG function. Compared with PDGNN, it exploits the original node feature rather than the new edge feature in the MSG function. PDGNN (w/o ew) denotes PDGNN without edge weight. Further experimental settings can be found in the supplementary material.
Results. Table Trports reports the approximation error, we observe that PDGNN outperforms all the baseline methods among all the datasets. The comparison between GAT and GAT PI shows the benefit of predicting EPDs instead of predicting the persistence image. Comparing GAT and GAT (+MIN), observe the advantage of the new AGG function, which shows the necessity of using min aggregation to approximate the Find-Root algorithm; Comparing GAT (+MIN) and PDGNN, effectiveness of using the new MSG function to help the model capture information of the separated connected components. The comparison between PDGNN (w (w/o ew) and PDGNN shows that edge weights help the model focus on the individual Relax-Edde Edge sub-algorithm operated on every edge.
observe the
5.2 Downstream Tasks
In this section, we evaluate the performance of the predicted diagrams 2 graph representation learning tasks: node classification and link prediction. We replace the ground truth EPDs in state-of- the-art models based persistence [56] 50] with our predicted diagrams and report the results.
Baselines. We compare our method with various state-of-the- methods. We compare with popular GNN models including GCN [22]. GAT 422 and HGCN (6) For link prediction, we compare with several state-of-the-an methods such as SEAL [54] and P-GNN [51]. Notice that GCN and GAT are not originally designed for link prediction, therefore we follow the settings in 66 50 that is, to get the node embedding through these models, and use the Fermi-Diras decoder 23 32 to predict whether there is link between the two target nodes. In comparison with the original EPD, we also add PEGN [56] and TLC-GNN [50] as baseline methods. Furthermore, to show the benefit of directly predicting EPDs, also add the baseline methods PEGN (GIN PI) and TLC-GNN (GIN_PI), which replace the original persistent homology feature with the output from GIN_PP
Evaluation metries. For node classification, our setting is the same 22 train the GNNs with 20 nodes from each class and validate (resp. test) the GNN on 500 (resp. 1000) nodes. We run the GNNs on these datasets 10 times and report the average classification accuracy
42 56
To be specific, we

---

and standard deviation. For link prediction, our setting is the same as 66 50]. To be precise, we randomly split existing edges into 85/5/10% for training, validation, and test sets. An equal number of non-existent edges are sampled as negative samples in the training process. We fix the negative validation and test sets, and randomly select the negative training sets in every epoch. We run the GNNs on these datasets 10 times and report the mean average area under the ROC curve (ROCAUC) scores and the standard deviation.
Results. Table 2 and Table summarize the performance of all methods on node classification and link prediction. We observe that PEGN (PDGNN) and TLC-GNN (PDGNN) consistently perform comparably with PEGN and TLC-GNN, showing that the EPDs approximated by PDGNN have the same learning power as the true EPDs. Furthermore, PEGN using the approximated EPDs achieve better or comparable performance with different SOTA methods.
We also discover that PEGN (GIN_P) and TLCC-NN (GIN_ __) perform much inferior to the original models using the true EPDs. It demonstrates that the large approximation error from GIN_PI lose much of the crucial information which is preserved in PDGNN.
Transferability. One appealing feature of our method is its transferability. Training on one graph, our algorithm can estimate EPDs well another graph. This makes it possible to apply the computationally expensive topological features to a wide spectrum of real-world graphs; we can potentially apply pre-trained model to large and dense graphs, which direct EPD computation is infeasible. The experiments are provided in the supplementary material.
5.3 Algorithm Efficiency
In this section, evaluate the efficiency of our proposed model. For a fair and complete comparison, we compare with algorithms from Gudhi [40] and from [50]. We select the first 1000 nodes from Cora, Citeseer, PubMed, Photo, Computers, CS, Physics, and then extract their 2-hop neighborhoods. With Ollivier-Ricei curvature as the filter function, we compute the EPDs and report the time (seconds) used to infer these diagrams.
Results. We list the average nodes and edges of these vicinity graphs in the first line of Table 4 As shown in Table 4 although our model is slower on small datasets like Cora or Citeseer, it is much faster on large and dense datasets. Therefore we can simply use the original algorithm to compute the EPDs on small graphs, and use our model to estimate EPDs on large graphs. The model can be applicd to various graph representation learning works based on persistent homology.
6 Conclusion
Inspired by recent success on neural algorithm execution, we propose a novel GNN with different technical contributions to simulate the computation of EPDs on graphs The network is built on algorithmic insights, and benefits from better supervision and closer alignment with the EPD computation algorithm. Experiments show that our method achieves satisfying approximation quality and learning power while being significantly faster than the original algorithm on large and dense graphs. Another strength of our method is the transferability: training on one graph, our algorithm can still approximate EPDs well on another graph. This makes it possible to apply the computationally expensive topological features to wide spectrum of real-world graphs.
Acknowledgements. We thank all anonymous reviewers for their constructive feedback very much. This work of Zuoyu Yan, Liangcai Gao, and Zhi Tang is supported by the projects of National Key R&D Program of China 2019YFB1406303) and National Natural Science Foundation of China (No. 61876003), which is also a research achievement of Key Laboratory of Science, Technology and Standard in Press Industry (Key Laboratory of Intelligent Press Media Technology).
References
[1] Henry Adams, Tegan Emerson, Michael Kirby, Rachel Neville, Chris Peterson, Patrick Shipman, Sofya Chepushtanova, Eric Hanson, Francis Motta, and Lori Ziegelmeier. Persistence images: stable vector representation of persistent homology. Journal of Machine Learning Research,
18, 2017.
10

---

[2] Pankaj K Agarwal, Herbert Edelsbrunner, John Harer. and Yusu Wang. Extreme elevation on 2-manifold. Discrete Computational Geometry, 36(4):553-57 575,5 2006.
[3] Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang, Nina Otter, Guido Montufar, Pietro Liò, and Michael M Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. ICML, 2021.
[4] Mathieu Carrière, Frédéric Chazal, Yuichi lke, 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, pages 9786-2796 PMLR, 2020.
[5] Mathieu Carriere, Marco Cuturi, and Steve Oudot. Sliced wasserstein kernel for persistence diagrams. International conference on machine learning, pages 673. PMLR, 2017.
[6] Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. Advances in neural information processing systems, 32:4868-444 4879, 2019.
[7] Chao Chen, Xiuyan Ni, Qinxun Bai, and Yusu Wang. A topological regularizer for classifiers via persistent homology. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2573-2582. PMLR, 2019.
[8] Yuzhou Chen, Baris Coskunuzer, and Yulia Gel. Topological relational learning on graphs. Advances Neural Information Processing Systems, 34, 2021.
[9] David Cohen-Steines Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & computational geometry, 3701):103-120, 2007.
[10] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Extending persistence using poincaré and lefschetz duality. Foundations of Computational Mathemttccs 91):79-1033, 2009.
[11] David SteineSt Herbert Edelsbrunner, John Harer, and Yuriy Mileyko. Lipschitz functions have p-stable persistence. Foundations of computational mathematics, 10(2):127-139, 2010.
[12] Thomas H. Cormen, Charles E. Leiserson, Ronald L.. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009.
[13] Tamal K. Dey and Yusu Wang. Computational Topology for Data Analysis. University Press, 2022.
Cambridge
[14] Herbert Edelsbrunner and John Harer. Computational topology: an introduction. American Mathematical Soc., 2010.
[15] Herbert Fdelsbrunner, David Letscher, and Afra Zomorodian. Topological persistence and simplification. In Proceedings 4/st annual symposium foundations of computer science, pages 454 463. IEEE, 2000.
[16] Christoph Hofer, Florian Graf, Bastian Rieck, Mare Niethammer, and Roland Kwitt. Graph filtration learning. In International Conference Machine Learning, pages 4314-4323, PMIR, 2020.
[17] Christoph Hofer, Roland Kwitt, Mare Niethammer, and Mandar Dixit. Connectivity-optiiizz representation learning via persistent homology. In International Conference on Machine Learning, pages 2751-2760. PMLR, 2019.
[18] Christoph Hofer, Roland Kwitt, Mare Niethammer, and Andreas Uhl. Deep learning with topo- logical signatures. In Proceedings of the 31 International Conference on Neural Information Processing Systems, pages 1633-1643, 2017.
[19] Nan Hu, Raif M Rustamov, and Leonidas Guibas. Stable and informative spectral signatures for graph matching. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2305-2312, 2014.
[20] Xiaoling Hu, Fuxin Li, Dimitris Samaras, and Chao Chen. Topelogy- deep image segmentation. Advances in Neural Information Processing Systems, 32:5657-5668, 2019,
11

---

[21]
Lukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. In Yoshua Bengio and Yann LeCun, editors. 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
[22] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICIR), 2017.
[23] Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná. Hyperbolic geometry of complex networks. Physical Review F,, 82(3):031106 2010.
[24] Karol Kurach, Marein Andrychowicz, and Ilya Sutskever. Neural random-accers machines. In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Represen- tations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings. 2016.
[25] Genki Kusano, Yasuaki Hiraoka, and Kenji Fukumizu. Persistence weighted gaussian kernel for topological data analysis. In International Conference Machine Learning, pages 2004-2013, PMLR, 2016.
[26] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Neural Information Processing Systems (NeurIPS), 2020.
[27] Yao Ma and Jiliang Tang. Deep learning on graphs. Cambridge University Press, 2021.
[28] Haggai Maron, Heli Ben- Ham-H Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 2156-2167, 2019.
[29] Guido Montufar, Nina Otter, and Yu Guang Wang. Can neural networks learn persistent homology features? In NeurlPS 2020 Workshop on Topological Data Analysis and Beyond, 2020.
[30] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4602-4609, 2019.
[31] Chien-Chun Ni, Yu-Yao Lin, Jie Gao, and Xianfeng Gu. Network alignment by discrete ollivier- ricci flow. In International Symposium on Graph Drawing and Network Visualization, pages 447-462. Springer, 2018
[32] Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical represen- tations. Advances in neural information processing systems, 30:6338 1166338-3477, 2017.
[33] Scott E. Reed and Nando de Freitas. Neural pnogrammer-interpreeer In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
[34] Jan Reininghaus, Stefan Huber, Uliic Bauer, and Roland Kwitt. A stable multi-scale kernel for topological machine learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4741 4748, 2015.
[35] Adam Santoro, Ryan Faulkner, David Raposo, Jack Rae, Mike Chrzanowski, Theophane Weber, Daan Wierstra, Oriol Vinyals, Razvan Pascanu, and Timothy Lillicrap. Relational recurrent neural networks. Advances in Newral Information Processing Systems, 31:7299-7310, 2018.
[36] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
[37] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arX1v:1811.05888, 2018.
12

---

[38] Anirudh Som, Hongjun Choi, Karthikeyan Natesan Ramamurthy, Matthew P Buman, and Pavan Turaga. Pi-net: deep learning approach to extract topologiaal persistence images. In Proceedings of the IEEF/CVE Conference on Computer Vision and Pattern Recognition Workshops, pages 834-835,00 2020.
[39] Jian Sun, Maks Ovsjanikov, and Leonidas Guibas. A concise and provably informative multi- scale signature based on heat diffusion. In Computer graphics forum, volume 28, pages 1382-1392.
Wiley Online Library, 2009.
[40] The GUDHI Project. GUDHI User and Reference Manual. GUDHI Editorial Board, 2015.
[41] Petar Veličković, Lars Buesing, Matthew Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell, Pointer graph networks. Advances in Neural Information Processing Systems, 33:2232-2244, 2020.
[42] Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[43] Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In International Conference on Learning Representations, 2019.
[44] Fan Wang. Huidong Liu, Dimitris Samaras, and Chao Chen. Topogan: A topology-aware generative adversarial network. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part III 16, pages 118-136. Springer, 2020.
[45] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. comprehensive survey graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-244 2444-44222 2020.
[46] Louis-Pascal Xhonneux, Andreea- Ioana Deac, Petar Veličkovié, and Jian Tang. How to transfer algorithmic reasoning knowledge to learn new algorithms? Advances in Neural Information Processing Systems, 34, 2021.
[47] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[48] Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanic Jegelka. What can neural networks reason about? In International Conference on Learning Representations, 2020.
[49] Yujun Yan, Kevin Swersky, Danai Koutra, Parthasarathy Ranganathan, and Milad Hashemi. Neural execution engines: Learning to execute subroutines. Advances in Neural Information Processing Systems, 33, 2020.
[50] Zuoyu Yan, Tengfei Ma, Liangcai Gao, Zhi Tang, and Chao Chen. Link prediction with persistent homology: An interactive view. In International Conference on Machine Learning, pages (1659-16669, PMLR, 2021.
[51] Jiaxuan You, Rex Ying, and Jure Leskovec. Position-awarc graph neural networks. In Interna- tional Conference on Machine Learning, pages 7134-7143. PMLR, 2019.
[52] Wojeiech Zaremba and Ilya Sutskever. Learning to execute. arXiv preprint 1rXiv:1440..444 2014.
[53] Sebastian Zeng, Florian Graf, Christoph Hofer, and Roland Kwitt. Topological attention for time series forecasting. Advances in Neural Information Processing Systems, 34, 2021.
[54] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in Neural Information Processing Systems, 31:5165-5175. 2018.
[55] Qi Zhao and Yusu Wang. Learning metrics for persistence-based summaries and applications for graph classification. Advances in Neural Information Processing Systems, 32:9859-9988 9870, 2019.
13

---

[56] Qi Zhao, Ze Ye. Chao Chen, and Yusu Wang. Persistence enhanced graph neural network. In International Conference on Artificial Intelligence and Statistics, pages 2896-2906. PMLR, 2020.
[57] Songzhu Zheng. Yikai Zhang, Hubert Wagner, Mayank Goswami, and Chao Chen. Topological detection of trojaned neural networks. Advances in Neural Information Processing Systems, 34, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] It is discussed in the supplemen-
tary material.
(c) Did you discuss any potential negative societal impacts of your work? [No] The work
does not seem to have any negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (cither in the supplemental material or as a URL)? [No] The data and provided in Section 5 and the supplementary material. We will release the code once accepted.
the experimental details
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes] It is illustrated in Section 5 in the paper and in the supplementary material.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] Table and Table examples.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] It is provided in the supplementary material.
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] is mentioned in the supplementary
material.
(c) Did you include any new assets either in the supplemental material URL? [No] We do not release new assets.
(d) Did you discuss whether and how consent was obtained from people whose data you're 're
using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "xnH12FGqyn", "reviewer": "Reviewer_5254", "summary": "In this paper, the authors propose an efficient learning framework to estimate extended persistence diagrams (EPD). It decomposes a reformulated version of EPD as an edge-wise prediction task into independent pairing problems. The authors use GNN architecture to learn the union-find algorithm which can solve the pairing problems.", "questions": "1. Can such EPD decomposition be extended to simplicial complexes (with 2-simplices, 3-simplices and more) apart from graph representations as simplicial complexes? If so, it would be interesting to also apply the proposed framework on some real-world higher-order data.\n2. How is the value of k (k-hop) chosen when extracting the |V| vicinity graphs?\n3.  The authors claim that their estimation method is much faster on large and dense datasets. Is there a threshold value of average N/E or degree to decide which method is the fastest to compute/estimate the EPD? Some additional experiment on real-world or synthetic graphs and a plot of computation time vs graph density may give an answer to this. The efficiency experiment is based on 2-hop neighborhoods. Does the value choice of k-hop affect such results?", "limitations": "See question 1.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n1. The EPD approximation method is examined on varying datasets and achieves the best performance.\n2. The proposed method is efficient on large and dense graphs.\n3. The paper is well written and easy to follow.\n\nCons:\n\n1. I suggest the authors check this related paper on using PD to learn graph representation and consider it as a baseline: https://openreview.net/forum?id=yqPnIRhHtZv \n2. Large scale real-world graphs are usually sparse such as the brain connectome etc. However, in this paper the large graphs are mostly denser than the smaller ones. The authors claim that their estimation approach of EPD is faster than other methods on large and dense graphs, it would be worthwhile to check the performance on large sparse graphs, which are more common in real-world complex systems. The proposed method is actually slower when the graph is sparse (citation networks). \n3. The major contribution of this paper is the efficient estimation of EPD using decomposition and GNN architecture to learn the reformulated edge prediction task. Downstream tasks in section 5.2 are more like an indirect way to examine the approximation accuracy. As long as the EPD approximation error is low, PEGN/TLC-GNN (True Diagram) and PEGN/TLC-GNN (PDGNN) will have similar performance. Therefore I recommend the authors to focus more on the EPD estimation experiments. For example, the author could further discuss and analyze why indirectly estimating the persistence image (PI) by estimating the EPD is better than directly estimating the PI to explain their experiment result presented in table 1. Another thing worthy to look at is the choice of filter functions. Ablation study or discovery of other graph metrics such as clustering coefficient, centrality can help to make the experiment complete.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "H6J1IL71S0A", "reviewer": "Reviewer_8ijg", "summary": "The extraction of topological features (called persistence diagrams - PDs) from structured data (such as graphs, point clouds, time series, etc.) is a promising approach to develop new machine learning methods but suffers from high computational complexity (among other things) to be faithfully used in learning pipelines. This happens mostly because the computation of PDs relies on combinatorial algorithms (roughly, sparse matrix reduction) that do not scale well with the size of the considered data. \n\nFollowing a recent line of development, this article proposes to bypass the exact computation of topological features via combinatorial algorithms and to instead approximate it using neural networks. The difference with previous approaches is that instead of brutaly computing PDs using an ad-hoc architecture, authors decompose the (extended) PD computation in different algorithmic steps, which roughly rely on running a Union-Find. It invite them to design a Graph Neural Network (GNN) capable of learning to reproduce this sub-routine that they call PDGNN, essentially based on an adapted aggregation function (mixing a minimum and a maximum). \n\nThey showcase the benefits of the proposed approach on different experimental tasks. ", "questions": "# Questions \n\n1. In line 271, it is said that the training loss was the $W_2$ metric rather than the L2 norm between some vectorization such as persistence images. Given that the $W_2$ requires to compute a matching to retrieve a gradient, doesn't it involve some computational burden in practice?\n2. (related to 1.) In line 49, it is said that \"The Wasserstein distance can be naturally decomposed into supervision loss for each edge (...) improve learning efficiency\" ; while I guess that I understand the underlying idea in an informal way, could you elaborate on this? In concrete terms, how is the training loss implemented and how does it benefits from the \"edge decomposition\" properties of your approach?\n3. Given that Persistence Images should be stable wrt the $W_2$ metric, isn't it somewhat \"redundant\" to use the PIE as a second evaluation metric? \n\n# Suggestions\n\n- The works _Learning persistent homology of 3D point clouds_ and _RipsNet: a general architecture for fast and robust estimation of the persistent homology of point clouds_ are also learning to produce topological features (on top of point cloud this times) and may be referenced along PI-Net and _Can Neural Networks learn persistent homology features_ in the introduction (line 38).", "limitations": "I think the limitations of the work have been properly addressed (for instance the authors aknowledge that their approach is only beneficial on large graphs --- exact computation may be more efficient otherwise). \n\nI do not identify potential negative societal impact _specific to this work_. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- [Originality] While not being entirely novel for either the TDA nor the ML communities, the approach proposed in this paper is quite fresh and promising. At least from the TDA perspective, I think that the idea of \"learning to produce topological descriptors **by approximating the inner-algorithms** in a relevant way\" was somewhat in the minds, but this paper is the first one to do so in a convincing manner to the best of my knowledge. \n\n- [Clarity] The paper is well written an pleasant to read.\n\n-  [Significance] The approach developed in this work seems quite promising and may be a source of inspiration for future works in TDA, in particular showcasing the potential of GNN when it comes to extract topological information from data. \n\n- [Quality] I think this paper is of great quality overall. Aside from the interesting approach, I also like the experimental evaluation methodology which covers the important questions (i) Is our model capable of producing outputs similar to ground truth PDs (Sec. 5.1), (ii) are our approximated PDs still relevant as topological features in downstream tasks, (iii) what are the computational benefits/drawbacks of using this approach in terms of running time. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2CY8u2vKqw", "reviewer": "Reviewer_cEes", "summary": "In this paper, the authors propose a mechanism to reduce the computation time, which is a major bottleneck of the extended persistence diagram that has recently been proven effective for graph structure learning tasks. The authors analyze the calculation algorithm of EPD, describe the key Union-Find algorithm in seqential, and approximate it with GNN to simplify the calculation. In their experiments, the authors evaluated the effect of EPD on graph analysis, the impact of pride of place, and computation time, and showed that EPD can analyze graphs efficiently and accurately, especially for large graphs.", "questions": "Can you clarify the following two points?\n- Provide evidence that EPD is more effective than other TDA methods.\n- Discussion on whether there is any other research on EPD acceleration. Also, there are other speed-up methods for TDAs that are not EPD, such as [Cufar], etc. Can you mention why these methods cannot be used for EPD?\n\n[Cufar] MATIJA ČUFAR AND ŽIGA VIRK, FAST COMPUTATION OF PERSISTENT HOMOLOGY REPRESENTATIVES WITH INVOLUTED PERSISTENT HOMOLOGY, https://arxiv.org/abs/2105.03629\n\nAlso, instead of approximating part of the algorithm with a GNN as an approximate computation of the diagram or PI, one could directly approximate the entire flow with a GNN or NN, but what is the reason for approximating only part of it? I know there is a trade-off between approximate performance and computation time, as well as the amount of data required, but is there anything you can mention? Please mention any that you can, although they may be related to issues to be considered in the future.", "limitations": "The authors have clearly defined the application, clearly described the performance, and adequately addressed the limitation of their work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n- Algorithms to improve the efficiency of PED calculations were precisely constructed by analyzing the structure of PED calculations.\n- The authors evaluate the effect of PED and the speed-up effect of this algorithm, as well as the accuracy of the speed-up.\n\nWeakness\n- Although the subject is to improve the efficiency of EPD calculations, there are insufficient references to other acceleration methods.\n- This method is an EPD-only speed-up method, assuming that EPD has high performance, but there is no mention of whether EPD is superior to other graph-oriented TDA methods. If EPD is inferior to other TDA methods, the method is less valuable from an AI perspective, i.e., for graph analysis.\n\nOverall, the effect of graph EPD on non-traditional TDA-based methods and the speedup of EPD are accurately described, and the contribution is significant. On the other hand, the evaluation is based on a limited set of assumptions that favor the proposed method and can be viewed as unfair.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept