Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.  
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).

However, the paper suffers from two weaknesses.

First, 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.

Second, 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. 
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.

---Concerning running time comparisons: 

***What software was used for the (exact or reduced) persistence diagram computations? 

***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.

***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.

---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.

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?
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors give two methods for data reduction that do not alter the calculations needed for persistent homology. 
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.
questions: - How feasible/costly is the application of these algorithms in terms of computation time? It is unclear to me at this point.
- Figure 7 is unclear to me. Time reduction in what? Computation of PH?
- 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.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents a new method for calculating persistence diagrams,
i.e. topological descriptors, of *large graphs* in an efficient manner.
This is accomplished by two fundamental insights, the first one being
that only specific types of nodes can contribute to high-dimensional
topological descriptors, the second one being that some nodes are
essentially redundant for the calculation. More precisely, the first
insights necessitates simplifying the graph to its $k$-core, i.e. the
subgraph induces by all vertices whose degree is *at least* $k$. This
graph is shown to be sufficient for calculating topological descriptors
up to dimension $k-1$. The second insight necessitates removing specific
vertices (thus reducing the size of the graph) that are *dominated* by
other vertices in terms of a filtration, i.e. an ordering of the nodes
in the graph. Experiments demonstrate that the proposed method can often
reduce the size of graphs from real-world and benchmark data sets to
a substantial extent.

strengths_and_weaknesses: The main strength of the paper is that it derives a new, principled way
of reducing the size of graphs that are commonly used as inputs for
persistent homology algorithms. By demonstrating that certain
substructures of the graph can be ignored for higher-order persistent
homology calculations, the paper potentially opens the door towards
a more widespread adoption of these methods in practice. The fact that
the two tuning techniques proposed in the paper are easily to implement,
thus being readily deployable, is another strength of the paper. In
addition, I find the write-up easy to follow (with some minor issues in
terms of clarity, but more about that later).

The main weakness of the paper is that it does not make use of the
potential insights afforded by persistent homology when applied to the
reduced and pruned graphs. While I appreciate that large reduction or
compression ratios can be achieved for the graph data sets, it would
strengthen the paper if the methods were also used in a directed
application. For instance, suppose (for the sake of the argument) that
existing graph learning techniques reach a certain accuracy on one data
set, and it requires knowledge about higher-order topological features
to provide a better classification. If the paper could find a case in
which previous work did *not* rely on such higher-order features (as
most TDA works are wont to do because of computational concerns), but
higher-order features turn out to be crucial for good predictive
performance, a strong case for the proposed reduction schemes would be
made. I believe that even a single such example, which would be easy to
generate even within the review cycle, would add an enormous amount of
scientific value/utility to this paper.

In summary, I believe that with a few additional modifications, this
paper could be a very good contribution to the conference.

## Detailed Comments

- Consider citing Hofer et al., Deep Learning with Topological
  Signatures, as one of the earliest examples of how to combine
  topological concepts with machine learning concepts.

- In the introduction, a brief explanation of terminology such as
  'filtration' would be helpful to make the paper more accessible to
  non-expert readers.

- Please use the spelling 'Čech complex,' not 'Cech complex'

- For consistency reasons, the term 'filtration function' should be
  preferred instead of 'filtering function.'

- Section 4.2 requires a better introduction; it should be made clear
  that the filtration function does not change here; potentially, the
  section could also be rewritten to explain more clearly what CoralTDA
  actually entails.

- The `SYN` data set, unless I am mistaken, is broken in that it only
  consists of $n$ copies of the *same* graph. The `SYNTHETICNEW` data
  set has been created as the 'fixed' version of this data set.

- In Figure 5, change the scale to '%' for consistency (all other
  figures use '%' in their scales)

## Typos and minor comments

The paper is well written and clear (with some mild caveats concerning
the accessibility for non-experts). The authors are to be commended
here!

- '[...] it is higher Betti numbers are prevalent' --> 'higher Betti numbers are prevalent'

- '(See Figure 3 [...])' --> '(see Figure 3 [...])'

- 'in simplicial complex setting' --> 'in a simplicial complex setting'

- 'take $k$-core' --> 'take the $k$-core'

- The closing parenthesis ')' is somtetimes cut off in figures (such as
  Figure 6)
questions: 1. Could you briefly expand on the proof of Lemma 5? I do not understand
   how this homotopy equivalence is obtained.

2. How is the complexity in Remark 9 calculated? I do not understand
   this entirely; the remark seems to require operations that do not
   work in constant time but have a worst-case complexity of $O(n)$,
   with $n$ being the number of vertices, thus resulting in an overall
   complexity that is *at least* quadratic.

3. Would it be possible to couple this approach with filtration learning
   approaches, such as introduced in Hofer et al., 'Graph Filtration
   Learning'?

4. How long does the pruning process itself take? I realise that this
   depends on a specific machine but maybe some comparison numbers could
   be shown (such as the reduction time as a function of the graph size).

5. Are there any restrictions on the filtration function or does the
   proposed method support arbitrary filtrations? It is my understanding
   that the latter is the case, so potentially Vietoris--Rips complexes
   or 'weighted Rips' filtrations might also benefit form the method.
   Please clarify.
limitations: There are no specific negative societal impacts arising from this work;
in general, network analysis can lead to problematic results when the
applied to networks that influence social behaviour. The proposed
methods are of a generic nature, though, and other methods for scalable
network analysis exist, so the risk is mitigated.

That being said, the *algorithmic limitations* of the proposed pruning
schemes could be discussed better. I am in particular interested in
understanding whether the size of the graph becomes prohibitive for the
method at some point. Moreover, are there any specific limitations on
the filtration function (also asked above)?
review_title: null

Meta-review: metareview: This paper proposes a method of reducing the size of graphs that are commonly used as inputs for persistent homology algorithms. This addresses a fundamental scalability problem in the case of graphs, and is likely to enable further work in the area.

On the negative side, the paper is similar to the prior work on strong collapses. Also, the experimental results do not make a strong case that the proposed algorithms are actually effective in reducing the running time for computing persistent homology at dimensions more than 0. There is only one plot on time reduction improvement (Fig 4b), which provides results for only two datasets in homology dimension 0, which is not satisfactory given that 0-dimensional case is already known to be very efficient.

Given the above, my recommendation is a weak accept, and I urge the authors to address these issues in their final version: better clarify the connection with the prior work, and provide experimental evidence that the algorithm improves the efficiency of persistent homology computation at dimensions more than 0. 
confidence: Less certain
Decision: Accept