Reduction Algorithms for Persistence Diagrams of Networks: CoralTDA and PrunIT
Authors: Cuneyt Gurcan Akcora
Murat Kantarcioglu
Yulia Gel
Baris Coskunuzer
Venue: NeurIPS 2022 Accept (2022)
Keywords: graph decomposition
persistent homology

Abstract: Topological data analysis (TDA) delivers invaluable and complementary information on the intrinsic properties of data inaccessible to conventional methods. However, high computational costs remain the primary roadblock hindering the successful application of TDA in real-world studies, particularly with machine learning on large complex networks.


Indeed, most modern networks such as citation, blockchain, and online social networks often have hundreds of thousands of vertices, making the application of existing TDA methods infeasible. We develop two new, remarkably simple but effective algorithms to compute the exact persistence diagrams of large graphs to address this major TDA limitation. First, we prove that $(k+1)$-core of a graph $G$ suffices to compute its $k^{th}$ persistence diagram, $PD_k(G)$. Second, we introduce a pruning algorithm for graphs to compute their persistence diagrams by removing the dominated vertices. Our experiments on large networks show that our novel approach can achieve computational gains up to 95%. 

The developed framework provides the first bridge between the graph theory and TDA, with applications in machine learning of large complex networks. Our implementation is available at https://github.com/cakcora/PersistentHomologyWithCoralPrunit.


Reduction Algorithms for Persistence Diagrams of Networks: CoralTDA and PrunIT
Cuneyt G. Akcora Department of Computer Science University of Manitoba cuneyt. a akcora umani toba.
Yulia R. Gel Department of Mathematical Sciences University of Texas Dallas National Science Foundation
ygl@ut.dalla, las edu
Murat Kantarcioglu Department of Computer Science University of Texas at Dallas muratk@ut dallas edu
Baris Coskunuzer Department of Mathematical Sciences University Texas at Dallas @askunuz@ut dallaaldallsss edu
Abstract
Topological data analysis (TDA) delivers invaluable and complementary infor- mation on the intrinsic properties of data inaccessible conventional methods. However, high computational costs remain the primary roadblock hindering the successful application of TDA in real-world studies, particularly with machine learning on large complex networks.
Indeed, most modern networks such as citation, blockchain, and online social networks often have hundreds of thousands of vertices, making the application existing TDA methods infeasible. We develop two new, remarkably simple but effective algorithms to compute the exact persistence diagrams large graphs to address this major TDA limitation. First, we prove that (k + 1)-core of graph G suffices to compute its k persistence diagram, (9). Second, we introduce a pruning algorithm for graphs compute their persistence diagrams by removing the dominated vertices. Our experiments on large networks show that our novel approach can achieve computational gains up 95%.
The developed framework provides the first bridge between the graph theory and TDA, with applications in machine learning of large complex networks. Our imple- mentation available at www.:///wwccooor////sseeeeeeeeee
WithCoralPrumit
Introduction
Topological data analysis (TDA) has emerged powerful machinery in machine learning (ML), allowing us to extract complementary information on the observed objects, especially, from graph- structured data. particular, TDA has become quite popular in various ML tasks, ranging from
bioinformatics 38 44], finance 339 2 material science
33
biosurveillance [51] [9]. network
analysis [54 [6), as well as insurance and agriculture [56 (see the literature overviews [7]
and the TDA applications library (77). Recently there has emerged highly active research area that
combines the PH machinery with geometric deep learning (GDL. methods 30 57 31
Persistent homology (PH) is key approach in TDA, allowing us to extract the evolution of subtler patterns in the data shape dynamics multiple resolution scales, which conventional, non-topological methods [5). The main idea is to construct nested sequence of topological spaces (filtration) induced from the data, and record the evolution of topological features in this sequence. In other words, the extracted patterns, or homological features, along with how
accessible more
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

long such features persist throughout the considered filtration of a scale parameter. convey a critical insight into salient graph characteristics and hidden mechanisms behind system organization.
PH has been very effective in many graph machine learning tasks, such as graph and node classifica-
tion 49 14 58 29). link prediction 66 (55) and anomaly detection [12 47].
Nevertheless, while PH has shown promise in various graph learning applications, prohibitive computational costs of PH constrain its wider usage. Indeed, most PH studies are limited to small graphs with a few thousand vertices at most. The problem is that the complexity of the standard PH algorithm is cubic in the number of simplices [48], so needs to limit homology computations to O-th and 1-th levels only. Computation of higher-level persistence for relatively large graphs can take days weeks.
In this paper, we aim to address this fundamental bottleneck in the application of TDA to large networks by introducing two new efficient algorithms which significantly reduce the cost of computing persistence diagrams (PD) for large real-world networks: CoralTDA and PrunfT.
Co Algorithm: Based on our observation that many vertices in large real-world networks have low degrees and do not contribute PDs in higher dimensions, we developed the CoralTDA algorithm (Theorem 2 where we prove that (A + 1)-core G of a graph G is enough to compute the htth
PD of the graph, i.e (G) = (
Using this property, with much smaller core graph gk+1, compute the exact higher persistence diagram PD (G) losing no information. Our experiments show that even for lower dimensional topological features, such as k (See Figure 4. Our findings show that many real-life data sets exhibit nontrivial second and third persistence diagrams, facilitating various classification problems. On the other hand, our reduction reaches 100% for the third or higher dimensions in several networks, implying that higher PDs are trivial for these datasets.
we reduce the graph order by up to 73% for some datasets
As a result, our reduction approach improves our understanding of the existence of higher-order dimensional holes and their role in the organization of complex networks.
We further develop a topologically simple but highly efficient algorithm to facilitate computations of PDs of graphs for any dimension. In particular, for a graph G = (V, E) and filtration by clique complexes, we show that removing (pruning) a dominated vertex from the graph does not change PDs at any level, provided that the dominated vertex enters the filtration after the dominating vertex (Theorem 7
PrunIT Algorithm:
Our experiments indicate that the new algorithm is highly efficient in PD computations of broad category of large graphs from 100K to 1M vertices, and it can reach 95% vertex reduction (see Table D.
Further, when we combine Co and PrunIT algorithms, can significantly reduce the graph sizes for the computation of PDs (Figure
We summarize the key novelty of our contributions as follows:
We show that the graphs' (k: + 1)th and higher persistence diagrams only depend on their k-cores.
We introduce a highly effective pruning algorithm that significantly reduces the graph size without changing any persistence diagram the original graph.
Our experiments in large datasets and large graphs show up to 95% reduction in the graph size for the computation of persistence diagrams.
With our reduction algorithms, highly successful TDA methods can be applied very large graphs and large datasets where previously its use was constrained by prohibitive computational costs.
2
Related Work
There are mainly two settings in practice where we use PH to obtain topological fingerprint of dataset. The first one is the point cloud setting, where the datasct comes as point cloud in an

---

ambient space R". Then, we define PH by constructing a sequence of simplicial complexes induced by the pair-wise distances of data points Fieps filtration) and keeping track of the topologiaa changes in this sequence 5 23 The second one is the network setting where the typical PH construction uses a filtering function on the network. By construction, while the principal identifier to define PH in the point cloud setting is the pair-wise distances of points, the principal identifier in the network setting is the filtering function. Because of this, PH machinery works differently in a network setting, as explained in Section 3
There are several works in the point cloud setting to reduce the computational costs and run-time of the persistence diagrams. Malott and Wilsey used the idea of data reduction and data partitioning [41]. Mischaikow and Nanda brought the discrete Morse Theory of geometric topology to the combinatorial setting 43 In [46] (20) 21 24], the authors studied the same problem with different approaches in
the point cloud setting.
While several works improve the run-time of PH in the point cloud setting, only a few of them could reduce the computational costs of persistent homology in the network setting. An idea is to use discrete Morse Theory to capture the topological features occurring during the process [36] by applying the techniques developed in 43
the network setting.
While the computational complexity of h persistence diagram (PD) is Onn)) where n is the number of k-simplices [48], [43] achieves O(m² x nol n) where is the number of critical ls s-mimlliess. With the additional time to find the critical k-simplices in each filtration step, the computational complexity Om?² log n) is not scalable for very large networks.
3 Persistent Homology
This part provides a background on the theory of persistent homology. Homology (X) is an essential invariant in algebraic topology, which captures the information of the k-dimensional holes (connected components, loops, cavities) in a topological space X. For example, a connected component in graph zero-dimensional hole, whereas a graph loop is a 1-dimensional hole. Persistent homology is a way to use this invariant to keep track of the changes in a controlled topological space sequence induced by the original space X. For basic background on persistent homology, see [23 22).
There are several ways to use PH in network setting, such as power filtration or using different complexes (c.g.. Vietoris-Ripe Rips, Čech complexes) construct the filtration for given filtering function 33. We focus on the most common methods to define PH for graphs: sub/superlevel filtrations obtained by filtering function and the clique (flag) complexes. Sub/superievel filtrations are the most common methods because one can inject domain information into the PH process if the chosen filtering function comes from the network domain (e.g., atomic number in protein networks, transaction amount for blockchain networks). Note that our results can be generalized to the persistent homology defined with a filtering function for different complexes.
Throughout the paper, we use the terms gruph and network interchangeably. Let & be a graph with vertex set V = {1,}) and edge set = {,re), i.e. ere E & if there is an edge between the vertex o, and E. in G. Let f : V + R be a filtering function defined on the vertices of G. Let = {at} be threshold set with ag ein f(er)= < 01 ... < am max,, f(v,). For a E I, let V. = [u, E V f(u,) S ). Let G, be the induced subgraph of G by V,, i.e. G; = (V,, &,) where E, = fere E E Ur, U. E V. Let G. be the clique complex of G.. A clique complex is obtained by filling in all the (k + 1)-comleete subgraphs with k-simplices. In other words, if the vertices (Urg Ur...., Fr. C Gi are pairwise connected by an edge in G, then the clique complex S. contains k-simplex a = [Urg "r....,, "ru]- This simplicial complex G, obtained by filling in all complete subgraphs is called the clique complex of G, This construction induces nested sequence of high dimensional simplicial complexes:
Go c 9 C C... C..
filratttt for G. Superlevel filtrations can This sequence of simplicial complexes is called the sublevel filtration
be defined similarly by considering the generating sets (f(x,) 2 a:} instead of [f(x,) S ag above. Here, G. can be taken as the different simplicial complexes induced by G. which gives different
3

---

types of filtrations 13. After obtaining the filtration, one considers the homology groups H2 (G:) of each simplicial complex G. The homology group (x) keeps the information of k-dimensional topologiaa features in the simplicial complex X.
Persistent homology keeps track of the topoloiial changes in the sequence {9.} by using the homology groups (H)) When k-dimensional hole o (a connected component, loop or cavity) appears in (G,), Hg, by merging with another feature or by being filled in. Then, we mark d, aj as its death time. Hence, we say that persists along the interval [b, dz), i.e. [ay, az). The longer the interval (d, - b,), the more persistent the feature a.
mark b, a, its birth time. The feature can disappear at later time in
The multi-se set PD, f) {(b.. d,) l (9:) for by Si d is called the t persistence diagram of (G. f) which is the collection of 2-tuples marking the birth and death times of k- dimensional holes {o} in {G.). In particular, PD₃ (G, f) represents the 1thh PD of the sublevel filtration, induced by the filtering function f=V + R. For brevity, we suppress f and use PDx(9) throughout the text.
4 CoralTDA Reduction and Higher Persistence Diagrams
A k-core 9 of a graph G is the subgraph of G obtained by iteratively deleting all vertices (and edges connected to it) with degree less than [52]. other words, g is the largest subgraph of 9 where all the vertices have degree of at least k.
Figure shows a graph with its core structure. Here, vertex belongs to O-core as it is disconnected from the graph. Vertex colors indicate shared coreness. When we use vertex degree as the filtering function and allow graph cliques of size three at most, the only one-dimensional hole (shown with the red circle) appears at degree 4 for vertices 4, 6, 8, and 9. Vertices 3, and 7 can only contribute to O-dimensional holes because their degree is 1. Similarly, 8 can only contribute to 0 and 1-dimensional holes because its degree is 2.
10
9
8
Zucar
The k-core decomposition is fundamental operation in many areas such as graph similarity matching (45) graph cluster- ing 25 network visualization (26). anomaly detection [53
J-aaa
5
7
and robustness analysis 13
K-core decomposition of graph 10 vertices. Vertex I no edges and belongs to the Oth-core. one-dimensional hole of vertices 4, 6. 8, and 9 shown with a red circle.
Figure 1:
A naive implementation of k-core iteratively deletes vertices whose degree falls below a until deletes all vertices from the graph. The implementation has a computational complexity of Om log n),, where and are the number of edges and vertices in the network, respectively. Batagelj and Zaversnik reduce the complexity Om + n)) "by keeping an in in-memory array of all possible degree values and keeping track of bin boundaries" [5]
4.1 Relation between 9, and O.t
Our main idea is to compute high-dimensional persistence features their associated graph cores. Note that a k-clique in graph theory corresponds to (A: - 1)-simplex in PH; a k-clique (complete subgraph of order k) in & induces (k - 1) simimepe in ğ.
The clique complex is a simplicial complex of dimension K - 1 where K denotes the degeneracy of G, i.e. K max [k| g* + 6). That is. 9 contains (k: 1)-simplex if and only if its k-core gk is not empty.
For any i, k. we have the h-core of G; contained in G. by construction, i.c. G C. G.. This implics that the same holds for their clique complexes, i.e. G c G. On the other hand, if one restricts the original filtering function f V + IR to the vertices V* of the k-core of G. we have f D* - R. By

---

using the same thresholds for f: : Vk - I. we obtain the filtration 9 will induce the persistence diagram PD, (g+) for any dimension r.
c C6
C 0 C... C T
This
Since for any i, ki J C Ge. we have the following diagram.
c g
c 9h
c
n
n
(I)
Go
C 9
C
C 9m
Notice that for any j k 1. if there is a j-cycle a living in Cy( then we have C Cj C),))) as Jt G.. In the following, we show that for these cycles, the converse also true, and show the equivalence in the homology level.
Remark [Restriction of f to ydj Notice that the filtering function f V R on V* the vertices of g is defined directly by restricting values of f: V - IR to the subset y C V. In particular, f:V. V lk function coming from the graph attributes (such as vertex degree), then f y* IR may not be the same function coming from the graph attributes induced by the graph G For example, let be the degree function on V. the vertices of G. Then, for any w V** f(w) the degree of w in G, not its degree in g While the k-core graph g changes, we do not update the values of on ye according to its attribute definition in g but we keep the same values in the original function f: IR for the remaining vertices in k V. In graph terms, this corresponds to computing vertex filtering (activation) values on the original graph but using the edges of the reduced graph to extract simplices.
4.2 CoralTDA Reduction
Our CoralTDA technique shows that lower degree vertices do not affect higher persistence diagrams, Le., CoralTDA yields exact results. Note that in the following result, even though the graph size changes, we keep the same filtering function f V - I with the original values. See Remark foo further details. We give the proof of the following theorem in Appendix.
Theorem 2. Let G be an unweighted connected graph. Let f V + R be filtering function on G. Let Pg. f) represent the t persistence diagram for the sublevel filtration of the clique complexes. Let Č be the k-core gf Then, for any j 2 k
PD PD, .)).
Ouiline of the proof: We show that for any nontrivial k-homology class a in the original clique complex G. a generating k-cycle S in this homology class also lives in a much smaller subcomplex: the clique complex of the (k + co-r ( (G++1). That is, we prove that any vertex in the k-cycle S must have a degree least & + where this degree count comes only from the k-simplices of S, and removing the lower degree vertices from G has no effect on the existence of such S. We give the proof of the theorem in Appendix.
The above result indicates that 4tth persistence diagram information can be obtained by only consider- ing the (k + 1)-core of graph. CoralTDA an effective tool for reducing computational costs to compute higher persistence diagrams. See Figure 4 for reduction results for various datasets.
0.00
0.20
2.50
075
0.0
0.20
Clusering
50
0.00
0.25
Clusering
2.50
0.0
222
Clustrrigg cooff
2.53
075
Figure 2: Clustering coefficients numher of topological features in Facebook and Twitter datasets. Fach data point a graph instance. We observe hundreds of higher topological features these datasets which can be highly useful for various graph learning tasks.
Remark [Higher PDs in Random Networks vs. Real-Life Networks] Note that by Kahle's seminal result (35). to observe nontrivial Betti numbers for higher dimensions in Erdós-Rén Rényi graphs G(n, p).
5

---

the average degree must be very high. In particular, for graph G(n,p), p), in order to have nontrivial h homoloyy in its clique complex, Kahle proved that for n a should be between -1 /k and -1/(k+ + 1). In terms of average degree n X p. this means the average degree should be between (( and (/(+1))) For instance, for dimension k = the average degree should be between v and Vn². For a graph order of 1000, this implies that the average degree should be between 31 and 100 to have nontrivial second homology in random networks. However, in real-life networks, our results show that higher Betti numbers are prevalent in much sparser graphs (see fig. 2 and appendix fig. [0). These findings can be further used to derive enror bounds and the associated loss of topological information when G(n,p) p) employed to approximate real- weal-world network phenomena, for instance, in the case of synthetic power grid networks and other cyber-physica, systems.
In the following, we give another effective method reduce the size of a graph without affecting the persistence diagrams (g) for any dimension 2 0.
5 PrunIT Algorithm
This section introduces another effective reduction technique for computing persistence diagrams of graphs induced by a filtering function. In particular, we show that for graph G, and filtering function f - R. removing (pruning) specific vertices from the graph does not change the persistent homology at any level. The result is valuable because the algorithm may reduce the vertex set considerably (Table Furthermore, as our experiments show, the reduced vertex set can significantly lower the simplex count, leading to much shorter computational times for persistent homology (see Figure 4 and appendix Figure().
In algebraic topology. homotopy is very effective tool to compute topological invariants like homology, and fundamental group (28). These topological invariants are homotopy invariant, meaning that if two spaces are homotopy equivalent, then their corresponding topological invariants are the same, e.g., X Y + H2(X)= HY).. We give a very natural homotopy construction to simplify a graph in the following.
For a given filtering function f V + IR, let G. be the clique complex of G, which induces the sublevel filtration Go Gr G2 C ... Gm. Let PDx f) represent the Athh persistence diagram
for the sublevel filtration { as described above.
Now, we define dominated vertices in g. Define the neighborhood of un as N ((u)) = { (uo U fo V Cupp E E). In particular, N(wo) C V is the set of all vertices adjacent to uo, and ug itself.
Definition 4. A vertex u is dominated by the vertex v in G if (uu) C Nu). If there is such a vertex U, we call u a dominated vertex of G (see Figure 3).
Removing a vertex u from graph G creates the natural subgraph of G obtained by removing the vertex u and all adjacent edges from G, i.e. g - {u} = G = (V", where V = =V- {u), and E' = E few E E} for any w.
1
2
4
We can alternatively express these via the star notion. The star St(u) of vertex u is the union of all simplices which contains u. Then, is dominated by v if St(u) C St(w). Similarly, removing a vertex u from G corresponds to removing St(u) from the clique complex G. i.c. -- St(u)= g'. A useful result is that removing a dominated vertex does not affect the homotopy type of the corresponding clique complexes.
3
5
6
Figure 3: Vertex 3 dominates vertices 1 and because all or 3 are neigh- bors of 3. There are no other dominated vertices.
neighbors
Lemma 5. Let u be dominated vertex in G. Let - (u). Then the clique complexes ② and G' are homotopy equivalent. i.e. ÿ G
Proof: Notice that g' is subgraph of G, and hence 9' is subcomplex in G. Let be dominated by in G. Then, we can write a deformation retract from I to g' by pushing the edge eue starting from u toward v. In other words, by using the simplicial coordinates, one can define homotopy F : G I + & which is identity on g and pushing all the faces in G - g' to the corresponding faces

---

in g'. This gives a homotopy equivalence :~ق O. To visualize, in Figure 3 one can push vertex 1 in the clique complex & towards vertex 3 along the edge between them. After the push, the 2-simplices [1,2.3] and [1,3,4] are pushed to the edges [2.3] and [3.4] respectively. See [ 7 and Lemma 2.2] for details.
Remark 6. [Collapsing] Note that this collapsing operation is adaptation of a well-known notion called deformation retract in algebraic topology in simplicial complex setting (28) This operation keeps the homotopy type the same, and hence the homology does not change with this reduction. In μА this is called folding (G folds onto G - {u]} or strong collapse. In these papers, the algorithm reduces simplicial complexes in the filtration one by one so that its associated clique complex keeps the same homotopy type. Our contribution here is to adapt this operation to the graph filtrations and define a smaller subgraph before the filtration step so that the induced simplicial complexes are homotopy equivalent. Since we prune the graph at the beginning of the process, our algorithm significantly reduces the computational costs for the induced persistence diagrams.
In the following, we introduce the PrunIT Algorithm by showing that removing dominated vertex does not change the persistence diagrams of the graph. We give the proof in Appendix C
Theorem 7. Let G (V, be an unweighted graph, and f V - T be filtering function. Let E V be dominated by v E V and f(u)= Z f(V). Then, removing u from 9 does not change the persistence diagrams for sublevel filtration, i.e. for any k 2 0
PD) PD fu).f).
Outline of the proof: The main idea is to employ the collapsing idea in the simplicial complexes of the filtration Go c G1 c Gr C ... C Fm in a suitable way. In particular, the lemma above shows that if vertex is dominated by a vertex v in G. then removing St(u) from G. does not change the homotopy type. Hence, if we ensure that when first appears in the filtration (Gi). the dominated vertex v is already there, then u can be removed from all the simplicial complexes in the filtration; removing u from the original graph before building the simplicial complexes does not affect the homotopy type of complexes in the filtration. The condition f()) 2 f(e) makes sure that whenever exists in { the dominant vertex is already there, and u can be removed from all simplicial complexes, and hence from the graph G. We give the proof of the theorem in Appendix C
Notice that the primary condition to remove dominated vertices from the graph ensures that the dominated vertex enters the filtration after its dominating counterpart. With the PrunIT' Algorithm. we show that removing the dominated vertex does not change the homotopy type of the simplicial complexes in the filtration. As homotopy equivalence implies the equivalences of homology groups at all levels, the reduction with this algorithm works in all dimensions. Furthermore, while coral reduction works above the corresponding dimension (j k), the PrunIT algorithm works any dimension.
Remark 8. [Superlevel Filtration] The same proof applies to the superlevel filtration by changing the condition f(u) Z (() to f(u) S f(v) in the theorem. In particular, if PG) f) represents the tth PD for superlevel filtration, then with the condition f(u) S f(v), we would have (G. f) (G - {u], f) for any & 2 O. Notice that if one takes f to be the degree function and uses the superlevel filtration, then the theorem automatically holds for any dominated vertex as deg(u) s deg(v) when u is dominated by v.
Remark 9. [Detecting Dominating Vertices] The dominating vertices can be computed by using the following approach (Algorithm is given in appendix Section B). Let AA = (asz) be the adjacency matrix for graph G. Given Vig V. consider all j's with digj =I Check if U2g is dominated by vj by comparing the rows Ri and Ry. i.e. for any le + j with 0ip. = 1, check whether aj. = 1. If this holds, tyy dominates U Removing 4 row R2, and iaA column C, from A corresponds to removing 2% from G. Essentially, vertex Us, is compared to each neighbor ey by checking whether Us, is already a neighbor of each of vy's neighbors. These checks require iterating over each vertex, searching vertex neighbors in the graph and getting the neighbors of each neighbor. The computational complexity is therefore O(V) x d²) where d is the average degree in the graph.
While our main focus is the most common method, sublevel/superlevel filtration, in the application of PH graph setting, our PrunIt algorithm works perfectly well with another common method, power filtration (3), as well, i.c. removing dominated vertex does not change persistence diagrams.
7

---

Theorem 10. [Prunlt for Power Filtration] Let G (V.E) be an unweighted connected graph. Let PG)(G) represent kAh persistence diagram of 9 with power filtratio... Let u. E V be dominated by any other vertex in V. Then, for any 2 1,
(9) PD (u)).
The proof of this result is given in appendix Section
C.2
Combining the CoralTDA and PrunIT Algorithms
Even though both algorithms are quite effective by themselves, we significantly reduce the computa-
tional costs (Figure 6 by combining them as follows. For given graph G = (V, E) and filtering function f V >> IR, one can start by trimming all dominated vertices with respect to f. and get smaller graph g'. We have already proven that (D) (G', Then, one take the k-core of this smaller graph g' to compute higher persistence diagrams of the original graph as before. In particular, by applying both reduction algorithms, for any & 2 O, we obtain
PDx(G) PDx(g)) = P
6 Experiments and Discussion
We apply our new approaches to three types of datasets. The details of datasets are provided in Table and appendix Table 2
Graph classification datasets consists of biological kernel 37 and ego networks from TWITTER
and FACEBOOK [42). Node classification datasets includes CITESEER and CORA (50 and Open
Graph Benchmark citation (paper cites paper) OGB ARXIV and OGB MAG 33 networks. Large
networks dataset contains 11 large networks of 100K-IM vertices from the Stanford Repository (40]
We used AMD Ryzen 5 2100 MHZ core computer in our R, Python and Java experiments.
We evaluate both algorithms by comparing vertex and edge sets and the total run time for the reduced graph with respect to the original graph. In the rest of this manuscript, we compute the vertex set reduction as 100 x (IV1 - VVI) [V]
where V" is the vertex count in the reduced graph. Edge and time reductions are computed similarly.
6.1 Reduction on Graph Classification Datasets
In this task, our goal is to evaluate the reduction of computational costs when the Co and PrunIT algorithms on datasets chosen from different graph classification tasks. We used one of the most commonly used functions in these experiments. the degree function with sublevel filtration.
100
100
Datanet
Detaset
Dataset TWITTER
ENrYMES
Firs DMSUU
CITESEER CORA
Buts
Budi
Suti
Beti dim
Figure 4: CoralTDA vertex reduction in graph and node classification datasets (higher is better). Reduction values averages from graph instances of the datasets (CORA and CITESEER node classification datasets contain a single graph instance only). FACEBOOK and TWITTER datasets are reduced by 20% k > whereas in other datasets graphs are reduced to empty sets.
show the vertex reduction when using CoralTDA for computations of PD+(G) for dimensions (Betti) 1: to 1o = 5. At dimension i = 4 and k = 5, CoralTDA reduces 10 datasets by 100%, i.e., these datasets have trivial PD) for k > 4. Even at smaller dimensions, CoralTDA can reduce the vertex set by 25%.75%.
In Figure 4
Figure 5a shows reduction percentages by the PrunIT algorithm. FIRSTMM and SYNNEW datasets are reduced by less than 10%; however the other 11 datasets are reduced by at least 35%. The lower reduction F FIRSTM and SYNNEW are due to stronger cores on the networks. SYNNEW is

---

Vertex reduction (%)
80
Dataset
OGB-ARXIV
OGB-MAG
100
80
Time reduction (%)
75
40
50
20
25
REDDITB
PROTEINS
CITESEER
ENZYMES
FB TWITTER
FIRSTMM
SYNNEW
MSRC
OHSU
CORA
DD
NGH1
0
Vertex count
500
1000
(a) Vertex reduction by PrunIT algorithm in the super-
(b) PrunlTT reduction in OGB node classification dataset. Each data point is ego network. Even for large networks, time reduction rates reach 75%.
level filtration. Results are averages of graph instances
from the datasets.
Figure 5: Prunlt vertex and time reduction in graph datasets.
synthetically created, but FIRS is created from 3d point cloud data and categories of various household objects. We believe that the physical proximity of similar objects (e.g., chairs are close to each other) in household creates a denser community structure the FIRSTMM dataset, which in turn results in strong cores.
We further report reductions in computational time (Figure 8 edge (Figure 9), and simplex count (Figure 7 in the Appendix.
6.2 Reduction on Node Classification Datasets
In this task, our goal is to compute the reduction of computational costs by using CoralTDA and PrunIT algorithms on datasets chosen from node classification tasks. The CoralTDA results are computed CITESEER and CORA networks and shown in Figure with more than 20% reduction for the first and higher dimensional persistence.
In node classification, topological features (such as Betti-0) and use the computed persistence diagram to classify the vertex. Such approach has yielded SOTA results with significant improvement in accuracy by using O-dimensional persistence [18. However, the computational costs of persistent homology non-negligible in large graphs, for O-dimensional features. For example, in Open Graph Benchmark datasets [32], one must compute persistence diagrams for each vertex in 100k to 11
also analyze the k-hop (k: 2 1) neighborhood of vertex with
vertex graphs.
We apply the PrunIT algorithm to two graphs, Arxiv and MAG, from the Open Graph Benchmark to compute time reduction in persistence diagram computations. We follow the approach in [18] and extract the 1-hop neighborhood of each ego vertex. We use the degree function as filtering function as before. In Figure 5b we show the reduction in computational time for O-dimensional persistence. We compute the time costs PrunIT by considering all the algorithm steps: finding and removing the dominated vertices, creating induced graph with the vertices, and running O-dimensional persistent homology on the graph by using vertex degrees as the filtering function. As Figure (5b) shows, we see more than 25% reduction in computation time in most graphs. Specifically, times of O-dimensional persistence on -ERX-AIVV networks are reduced by 37%, and those of OGB-MAC networks reduced by 23%. The results show that mitigate the computational costs of persistence homology by using the PrunIT algorithms.
average, computation
6.3 Reduction on Large Networks
Our goal is to combine PrunIt and CoralTDA algorithms to achieve the maximum vertex and edge reduction large networks in these experiments.
Table shows that on the biggest network of com-youtube, we eliminate 59% of the vertices when we only apply the Prunlt (on average 62% in all datasets). The reduction is as high as 95% (in ema i 1EaAll). Similarly, PrunIt creates significant edge reduction; 40% of all edges are removed on

---

Table Prunlt reductions number vertices and edges.
Dataset
|[V||
V|V Reduction (1)
||
| Reduction (1)
com-youtube
1134890
59%
2987624
25%
334863
37%
com dhip
317080
72%
1049866
65%
web-Stanford
emailEuAll
265214
95%
36448
94%
soc Epinions]
75879
57%
405740
14%
22pGmutella31
62586
46%
147892
20%
Brightkite_cdde
58228
48%
214078
21%
Eimai-Earred
36692
CAA. CondMat
23133
69%
93439
65%
oregon 010526
23409
average. Figure showws the reduction when we apply both CoralTDA and Prunlt on large networks. Even for low cores of and 3, the combined algorithms reach a vertex reduction of 78%. These results show that our algorithms can effectively reduce large networks to more manageable sizes.
Vertex Reduction (56
100
80
60
50
2
10
core
Figure Vertex reduction results for 11 large datasets after the application of Prunlt and CoralTDA algorithms. emailEuAle is the outlier for the 2nd and 3rd cores (shown with a crossed square).
7 Conclusion
We have proposed two new highly effective algorithms to significantly reduce the computational costs of TDA methods on graphs. While coral reduction is very effective for higher persistence diagrams, PrunIt is highly efficient, in general. Our experiments have showed that even for lower dimensional topological features, such as l = 1, for some datasets our methods can reduce graph order by up to 95%, which alleviates computational costs substantially. Furthermore, in most graph datasets reduce graph sizes by 100% for 3rd or higher dimensions. Our methods provides novel solution for efficient application of the powerful TDA methods large networks and build bridge between the graph theory and TDA, opening a pathway for broader applicability of topological graph learning in practice.
8
Acknowledgments
This material is based upon work sponsored by the Canadian NSERC Discovery Grant RGPIN- 2020-05665, NSF of USA under award number ECCS 2039701, OAC- 182C-18,467, DMS-1925346. 11S-2029661, OAC-2115094, ARO award W91 199-17777-1005 and Simons Collaboration Grant 579977. Part of this material is also based upon work supported by (while serving at) the National Science Foundation. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
References
[1] Michal Adamaszek. Clique complexes and graph powers. Israel Journal of Mathematics, 196(1):295-319 2013.
[2] Cuneyt Gurean Akcora, Yitao Li, Yulia Gel, and Murat Kantarcioglu. Bitcoinheist: Topolog- ical data analysis for ransomware prediction the bitcoin blockchain. In Christian Bessiere,
10

---

editor, Proceedings the Twenty-Ninth International Joint Conference on Artificial Intelligence. Ijcai.org, 2020.
IJCAI 2020, pages
[3] Mehmet E Aktas, Esra Akbas, and Ahmed El Fatmaoui. Persistence homology of networks: methods and applications. Applied Network Science, 4(1):1-28, 2019.
[4] Erik J Amézquita, Michelle Y Quigley, Tim Ophelders, Elizabeth Munch, and Daniel H Chitwood. The shape of things to come: Topological data analysis and biology, from molecules to organisms. Developmental Dynamics. 249(7):816-3))) 2020.
[5] Vladimir Batagelj and Matjaz Zaversnik. An o(m) algorithm for cores decomposition of networks. CoRR, Cs.DS/031 2003.
[6] Austin R Benson, Rediet Abebe, Michael T Schaub, Ali Jadbabaie, and Jon Kleinberg. Simpli- cial closure and higher-order link prediction. Proceedings of the National Academy of Sciences, 115(48):E1 1221--E1 1230, 2018.
[7] Jean-Daniel Boissonnat and Siddharth Pritam. Computing persistent homology of flag com- plexes via strong collapses. In Gill Barequet and Yusu Wang, editors. 35th International Symposium on Computational Geometry, SoCG 2019, June 18-21, 2019, Portland, Oregon, USA, volume 129 of LIPlcs, pages 55:1-55:15, matik, 2019.
Schloss Dagstuhl Leibniz-Zentrum Zentrum für Infor-
[8] Jean-Daniel Boissonnat and Siddharth Pritam. Edge collapse and persistence of flag complexes. In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry, SoCG 2020, June 23-26, 2020, Zürich, Switzerland, volume 164 of L/Plcs, pages 19:1-19:15. Schloss Dagstuhl- Leibniz- für Informatik, 2020.
[9]
Boissonnat, Siddharth Pritam, and Divyansh Pareek. Strong collapse and persistent homology. Journal of Topology and Analysis, pages 1 1-29, 2021.
[10] Coen Boot. Algorithms for determining the clustering coefficient in large graphs. B.S. thesis, Utrecht University, 2016.
[11] Romain Boulct, Etienne Ficux, and Bertrand Jouve. Simplicial simple-homotopy of flag
complexes in terms of graphs. European Journal of Combinatorics, 31(1):161-176, 2010.
[12] Paul Bruillard, Kathleen Nowak, and Emilie Purvine. Anomaly detection using persistent homology. In 2016 Cybersecurity Symposium (CYBERSEC), pages 7-12. IEEE, 2016.
[13] Kate Burleson-Lessee Flaviano Morone, Maria S Tomassone, and Hernán A Makse. K-core robustness in ecological and financial networks. Scientific Reports, 10(1):1-14, 2020.
[14] Chen Cai and Yusu Wang. Understanding the power of persistence pairing via permutation test. CoRR, abs/2001.06055 2020.
[15] Gunnar Carlsson. Topology and data. Bulletin the American Mathematical Sociery, 46(2):255-
308, 2009.
[16] Corrie Carstens and Kathy J Horadam. Persistent homology of collaboration networks. Mathematical Problems in Engineering, 2013, 2013.
[17] Frédéric Chazal and Bertrand Michel. An introduction to topological data analysis: Fundamental and practical aspects for data scientists. Frontiers in Artificial Intelligence, 4:667963, 2021.
[18] Yuzhou Chen, Baris Coskunuzer, and Yulia R. Gel. Topological relational learning graphs. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wort- man Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Confer- ence on Neural Information Processing Systems 2021, NeurlPS 2021, 1, December 6-14 14, 2021, virtual, pages 27029-27000 2021.
[19] Yuzhou Chen, Ignacio Segovia- DiaeriaaDDmnnuuez,, Baris Coskunuzer, and Yulia R. Gel. Tamp- s2genets: Coupling time-aware multipersistence knowledge representation with spatio-supra graph convolutional networks for time-series forecasting. In the Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net,
2022.

---

[20] Matija Cufar and Ziga Virk. Fast computation of persistent homology representatives with involuted persistent homology. arXiv preprint arXiv:2105.03629, 2021.
[21] Tamal K. Dey, Tao Hou, and Sayan Mandal. Persistent 1-cycles:
Definition, computation, and its application. In Rebeca Marfil, Mariletty Calderón, Fernando Díaz del Río, Pedro Real, and Antonio Bandera, editors, Computational Topology in Image Context 7th International Workshop, CTIC 2019, Málaga, Spain. January 24-25, 2019, Proceedings, volume 11382 of Lecture Notes in Computer Science, pages 123-136. Springer, 2019.
[22] Tamal Krishna Dey and Yusu Wang. Computational Topology for Data Analysis. Cambridge University Press, 2022.
[23] Herbert Edelsbrunner and John Harer. Computational Topology an Introduction. American Mathematical Society, 2010.
[24] Emerson G Escolar and Yasuaki Hiraoka. Optimal cycles for persistent homology via linear programming. In Optimization in the Real World, pages 79-96. Springer, 2016.
[25] Christos Giatsidis, Fragkiskos D. Malliaros, Dimitrios M. Thilikos, and Michalis Vazirgiannis. Corecluster: A degeneracy based graph elustering framework. In Carla E. Brodley and Peter Stone, editors, Proceedings of the Eiight AAAI Conference on Artificial Intelligence, July 27- -31, 2014, Québec City, Québec, Canada, pages 44-50. AAAI Press, 2014.
[26] Christos Giatsidis, Dimitrios M. Thilikos, and Michalis Vazirgiannis. Evaluating cooperation in communities with the k-core structure. In Proceedings of the International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2011, Kaohsiung, Taiwan, 25-27 July 2011, pages 87-93. IEEE Computer Society, 2011.
[27] Barbara Giunti. Tda applications library, httpp//ttt//////..etttototo 2425412/tda-ape www.iaaaiiiinnaaaaeeeeeaeaa
[28]
Allen Hatcher. Algebraic Topology. Cambridge University Press, 2002.
[29] Christoph D. Hofer, Florian Graf, Bastian Rieck, Mare Niethammer, and Roland Kwitt. Graph filtration learning. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 4314-4323 PMLR, 2020.
[30] Christoph D. Hofer, Roland Kwitt, Mare Niethammer, and Andreas Uhl. Deep learning with topological signatures. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1634-1644, 2017
[31] Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten M. Borgwardt. Topological graph neural networks. In Proceedings of the Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. Open- Review.net, 2022.
[32] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020.
[33] Takashi Ichinomiya, Ippei Obayashi, and Yasuaki Hiraoka. Persistent homology analysis of craze formation. Physical Review E, 95(1):012504 2017.
[34] Tian Jiang, Meichen Huang, Ignacio Segovia- DooiiiiaDD Nathaniel K. Newlands, and Yulia R Gel. Learning space-time crop yield patterns with zigzag persistence-based LSTM: toward more reliable digital agriculture insurance. In Proceedings of the Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, Virtual Event, February 22 March 1, 2022, pages -2244. AAAI Press, 2022.
12

---

[35] Matthew Kahle. Topology of random clique complexes. Discrete mathematics, 309(6):1658
1671, 2009.
[36] Harish Kannan, Emil Saucan, Indrava Roy, and Areejit Samal. Persistent homology of un- weighted complex networks via discrete morse theory. Scientific Reports, 9()::1118, 2019.
[37] Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neu- mann. Benchmark data sets for graph kerelss, 2016. http://graphherreels.co tu dwwtoord.udd..... de
(38) Violeta Kovacev-Nikolic, Peter Bubenik, Dragan Nikolić, and Giseon Heo. Using persistent homology and dynamical distances to analyze protein binding. Statistical Applications in Genetics and Molecular Biology, 15(1):19-38, 2016.
[39] Gregory Leibon, Scott Pauls, Daniel Rockmore, and Robert Savell. Topological structures in the equities market network. Proceedings of the National Academy of Sciences, 105(52)220589- 20594, 2008
[40] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http:::/ssaa..tannff.
peduuddaae June 2014.
[41] Nicholas O Malott and Philip A Wilsey. Fast computation of persistent homology with data reduction and data partitioning. In Big Data, pages 880-889 889. IEEE, 2019.
[42] Julian J. McAuley and Jure Leskovec. Learning to discover social circles in ego networks. In Peter L. Bartlett, Fernando C. N. Pereira, Christopher C. Burges, Léon Bottou, and Kilian Q Weinberger, editors, Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States, pages 548 1588556,44 2012.
[43] Konstantin Mischaikow and Vidit Nanda. Morse theory for filtrations and efficient computation of persistent homology. Discrete & Computational Geometry, 50(2):330-353, 2013.
[44] Jessica L Nielson, Jesse Paquette, Aiwen W Liu, Cristian F Guandique, C Amy Tovar, Tomoo Inoue, Karen-Amanda Irvine, John C Gensel, Jennifer Kloke, Tanya C Petrossian, et al. Topo- logical data analysis for discovery in preclinical spinal cord injury and traumatic brain injury. Nature Communications, 6(1):1-12, 2015.
[45] Giannis Nikolentzos, Polykarpos Meladianos, Stratis Limnios, and Michalis Vazirgiannis. A degeneracy framework for graph similarity. In Jérôme Lang, editor, Proceedings of the Twenty- Seventh International Joint Conference Artificial Intelligence, IJCAI 2018, July 13- 2018, Stockholm, Sweden, pages 2595-2601 ijcai.org, 2018.
[46] Ippei Obayashi. Volume-optimal cycle: Tightest representative cycle of a generator in persistent homology. SIAM Journal on Applied Algebra and Geometry, 2(4):508-53) 50344,444,,, 2018.
[47] Dorcas Ofori- Boateng, Ignacio Segovia- Davnriiaa- Cuneyt Gurean Akcora, Murat Kantar- cioglu, and Yulia R. Gel. Topological anomaly detection in dynamic multilayer blockchain networks. In Nuria Oliver, Fernando Pérez-Cruz, Stefan Kramer, Jesse Read, and José Antonio Lozano, editors, Machine Learning and Knowledge Discovery in Databases. Research Track European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings, Part I, volume 12975 of Lecture Notes in Computer Science, pages 788-804. Springer, 2021.
[48] Nina Otter, Mason A. Porter, Ulrike Tillmann, Peter Grindrod, and Heather A. Harrington. A roadmap for the computation of persistent homology. EPJ Data Sci., 6(1): 2017.
[49] Bastian Rieck, Christian Bock, and Karsten M. Borgwardt. A persistent weisfeiler-lehman procedure for graph classification. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 5448-5458, PMLR, 2019.
13

---

[50] Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In Blai Bonet and Sven Koenig, editors, Proceedings of the Twenty- Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA, pages 4292 4293. AAAI Press, 2015.
[51]
Ignacio Segovia-Domme Dominguez. Zhiwei Zhen, Rishabh Wagh, Huikyo Lee, and Yulia R. Gel. Tlife- Istm: Forecasting future COVID-19 19 progression with topologiaal signatures of atmospheric conditions. Kamal Karlapalem, Hong Cheng. Naren Ramakrishnan, R. K. Agrawal, P. Krishna Reddy, Jaideep Srivastava, and Tanmoy Chakraborty, editors, Proceedings of the Advances in Knowledge Discovery and Data Mining 25th Pacific-Asia Conference, PAKDD 2021, Virtual Event, May 11-14, 2021, Proceedings, Part I, volume 12712 of Lecture Notes in Computer Science, pages 201-212. Springer, 2021.
[52] Stephen B Seidman. Network structure and minimum degree. Social Networks, 5(3):269-287, 1983.
[53] M. Shanahan, V. P. Bingman, T. Shimizu, M. Wild, and O. Güntürkün. Large-scale network organization in the avian forebrain: a connectivity matrix and theoretical analysis. Frontiers in Computational Neuroscience, 7:89, 2013.
[54] Ann Sizemore, Chad Giusti, and Danielle S Bassett. Classification of weighted networks through mesoscale homological features. Journal of Complex Networks, 5(2):245-273) 2017.
[55] Zuoyu Yan, Tengfei Ma, Liangeai Gao, Zhi Tang, and Chao Chen. Link prediction with persistent homology: An interactive view. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 11659-11669, PMLR, 2021.
[56] Monisha Yuvaraj. Asim K Dey, Vyacheslav Lyubchich, Yulia Gel, and Vincent Poor. Topological clustering of multilayer networks. Proceedings of the National Academy of Sciences, 118(21):e019999411 2021.
[57] Qi Zhao and Yusu Wang. Learning metrics for persistence-based summaries and applications for graph classification. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alché-Bus Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Anmual Conference Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 9855-9866 2019.
[58] Qi Zhao, Ze Ye, Chao Chen, and Yusu Wang. Persistence enhanced graph neural network. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 2896-28222 20062900.... PMLR, 2020.
[59] Afra Zomorodian and Gunnar Carlsson. Computing persistent homology. Discrete Computa- tional Geometry, 33(2):249-277 2005.
14


Reviews:
[{"review_id": "xTEE4jS1PFz", "reviewer": "Reviewer_nLvc", "summary": "This paper presents a new method for calculating persistence diagrams,\ni.e. topological descriptors, of *large graphs* in an efficient manner.\nThis is accomplished by two fundamental insights, the first one being\nthat only specific types of nodes can contribute to high-dimensional\ntopological descriptors, the second one being that some nodes are\nessentially redundant for the calculation. More precisely, the first\ninsights necessitates simplifying the graph to its $k$-core, i.e. the\nsubgraph induces by all vertices whose degree is *at least* $k$. This\ngraph is shown to be sufficient for calculating topological descriptors\nup to dimension $k-1$. The second insight necessitates removing specific\nvertices (thus reducing the size of the graph) that are *dominated* by\nother vertices in terms of a filtration, i.e. an ordering of the nodes\nin the graph. Experiments demonstrate that the proposed method can often\nreduce the size of graphs from real-world and benchmark data sets to\na substantial extent.\n", "questions": "1. Could you briefly expand on the proof of Lemma 5? I do not understand\n   how this homotopy equivalence is obtained.\n\n2. How is the complexity in Remark 9 calculated? I do not understand\n   this entirely; the remark seems to require operations that do not\n   work in constant time but have a worst-case complexity of $O(n)$,\n   with $n$ being the number of vertices, thus resulting in an overall\n   complexity that is *at least* quadratic.\n\n3. Would it be possible to couple this approach with filtration learning\n   approaches, such as introduced in Hofer et al., 'Graph Filtration\n   Learning'?\n\n4. How long does the pruning process itself take? I realise that this\n   depends on a specific machine but maybe some comparison numbers could\n   be shown (such as the reduction time as a function of the graph size).\n\n5. Are there any restrictions on the filtration function or does the\n   proposed method support arbitrary filtrations? It is my understanding\n   that the latter is the case, so potentially Vietoris--Rips complexes\n   or 'weighted Rips' filtrations might also benefit form the method.\n   Please clarify.", "limitations": "There are no specific negative societal impacts arising from this work;\nin general, network analysis can lead to problematic results when the\napplied to networks that influence social behaviour. The proposed\nmethods are of a generic nature, though, and other methods for scalable\nnetwork analysis exist, so the risk is mitigated.\n\nThat being said, the *algorithmic limitations* of the proposed pruning\nschemes could be discussed better. I am in particular interested in\nunderstanding whether the size of the graph becomes prohibitive for the\nmethod at some point. Moreover, are there any specific limitations on\nthe filtration function (also asked above)?", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strength of the paper is that it derives a new, principled way\nof reducing the size of graphs that are commonly used as inputs for\npersistent homology algorithms. By demonstrating that certain\nsubstructures of the graph can be ignored for higher-order persistent\nhomology calculations, the paper potentially opens the door towards\na more widespread adoption of these methods in practice. The fact that\nthe two tuning techniques proposed in the paper are easily to implement,\nthus being readily deployable, is another strength of the paper. In\naddition, I find the write-up easy to follow (with some minor issues in\nterms of clarity, but more about that later).\n\nThe main weakness of the paper is that it does not make use of the\npotential insights afforded by persistent homology when applied to the\nreduced and pruned graphs. While I appreciate that large reduction or\ncompression ratios can be achieved for the graph data sets, it would\nstrengthen the paper if the methods were also used in a directed\napplication. For instance, suppose (for the sake of the argument) that\nexisting graph learning techniques reach a certain accuracy on one data\nset, and it requires knowledge about higher-order topological features\nto provide a better classification. If the paper could find a case in\nwhich previous work did *not* rely on such higher-order features (as\nmost TDA works are wont to do because of computational concerns), but\nhigher-order features turn out to be crucial for good predictive\nperformance, a strong case for the proposed reduction schemes would be\nmade. I believe that even a single such example, which would be easy to\ngenerate even within the review cycle, would add an enormous amount of\nscientific value/utility to this paper.\n\nIn summary, I believe that with a few additional modifications, this\npaper could be a very good contribution to the conference.\n\n## Detailed Comments\n\n- Consider citing Hofer et al., Deep Learning with Topological\n  Signatures, as one of the earliest examples of how to combine\n  topological concepts with machine learning concepts.\n\n- In the introduction, a brief explanation of terminology such as\n  'filtration' would be helpful to make the paper more accessible to\n  non-expert readers.\n\n- Please use the spelling 'Čech complex,' not 'Cech complex'\n\n- For consistency reasons, the term 'filtration function' should be\n  preferred instead of 'filtering function.'\n\n- Section 4.2 requires a better introduction; it should be made clear\n  that the filtration function does not change here; potentially, the\n  section could also be rewritten to explain more clearly what CoralTDA\n  actually entails.\n\n- The `SYN` data set, unless I am mistaken, is broken in that it only\n  consists of $n$ copies of the *same* graph. The `SYNTHETICNEW` data\n  set has been created as the 'fixed' version of this data set.\n\n- In Figure 5, change the scale to '%' for consistency (all other\n  figures use '%' in their scales)\n\n## Typos and minor comments\n\nThe paper is well written and clear (with some mild caveats concerning\nthe accessibility for non-experts). The authors are to be commended\nhere!\n\n- '[...] it is higher Betti numbers are prevalent' --> 'higher Betti numbers are prevalent'\n\n- '(See Figure 3 [...])' --> '(see Figure 3 [...])'\n\n- 'in simplicial complex setting' --> 'in a simplicial complex setting'\n\n- 'take $k$-core' --> 'take the $k$-core'\n\n- The closing parenthesis ')' is somtetimes cut off in figures (such as\n  Figure 6)", "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": "epkWT8vahTf", "reviewer": "Reviewer_BSUr", "summary": "The authors give two methods for data reduction that do not alter the calculations needed for persistent homology. ", "questions": "- How feasible/costly is the application of these algorithms in terms of computation time? It is unclear to me at this point.\n- Figure 7 is unclear to me. Time reduction in what? Computation of PH?\n- Some datasets are reduced from around 1M vertices to about 0.5M vertices. While impressive, this still seems out of the range of feasibility for a PH calculation. ", "limitations": "Yes, the authors have addressed limitations.", "rating": 5, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strengths of the paper are that the algorithms are straightforward and very general. The weaknesses are that the full computational complexity is not explored--it is not clear me how costly these algorithms are in the preprocessing step.", "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": "GHK0FerFW8i", "reviewer": "Reviewer_Xjqk", "summary": "In this work, the authors propose to combine two speedup techniques for significantly speeding up the computation of persistence diagrams on large graphs. The proposed approach first reduces the graph by strong collapsing every dominated vertex, and then further reduces the graph by computing its (k+1)-core (when dealing with k-dimensional homology). The authors prove that such operations preserve the persistence diagram, and then provide significant improvements over running times for various graph data sets.  ", "questions": "---If PrunIT is really just an application of strong collapses (as I said above), I think the experiment section should focus on CoralTDA. It would also make this section more clear and consistent if the authors used the same plots and methods for every data set, instead of showing vertex reduction in different forms (e.g., histograms, curves, box plots...), using different techniques (sometimes it is CoralTDA, sometimes PrunIT, sometimes both...), and showing running times for only two data sets.\n\n---Concerning running time comparisons: \n\n***What software was used for the (exact or reduced) persistence diagram computations? \n\n***Why do the authors not compare against the strong collapse method (in https://arxiv.org/abs/1809.10945)? This would make the use of CoralTDA more convincing.\n\n***Why do the authors only benchmark on persistence in dimension 0? PH in dimension 0 is known to be much easier to compute (almost linear complexity) so it would make more sense to also measure the improvements for persistence in higher dimensions.\n\n---Supplementary, l.625: \"none of the vertices of S are removed from G^i\": more details should be added because this statement is exactly what one wants to prove, and it is not very clear at first sight.\n", "limitations": "It would be good to discuss the fact that the proposed method is limited to flag complexes built from graphs. Can CoralTDA be extended to more general types of graph filtrations? ", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think the paper tackles an important question (since persistent homology is known to be hard to compute) and that its writing is very good and clear. The mathematical arguments are simple and easy to follow, making the paper mathematically sound (at least to me).\n\nHowever, the paper suffers from two weaknesses.\n\nFirst, some more efforts have to be put in the positioning. Although CoralTDA seems relevant and original, it is quite difficult to understand what are the differences between PrunIT and the method of strong collapses for computing the persistence of flag complexes (https://arxiv.org/abs/1809.10945). It really looks like that PrunIT is a mere application of an existing method to graph data.\n\nSecond, I think the experiments are nice, but are not that convincing since all of them show the reduction in the number of vertices and edges, but only a few actually display the running time improvements, which is the main motivation of this work. I think a more extensive comparison of running times is necessary. ", "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