Venue: NeurIPS 2022 Conference

Reviews:

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: 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.
strengths_and_weaknesses: Pros:

1. The EPD approximation method is examined on varying datasets and achieves the best performance.
2. The proposed method is efficient on large and dense graphs.
3. The paper is well written and easy to follow.

Cons:

1. 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 
2. 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). 
3. 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.
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.
2. How is the value of k (k-hop) chosen when extracting the |V| vicinity graphs?
3.  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.
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: 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.
strengths_and_weaknesses: Strength
- Algorithms to improve the efficiency of PED calculations were precisely constructed by analyzing the structure of PED calculations.
- The authors evaluate the effect of PED and the speed-up effect of this algorithm, as well as the accuracy of the speed-up.

Weakness
- Although the subject is to improve the efficiency of EPD calculations, there are insufficient references to other acceleration methods.
- 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.

Overall, 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.
questions: Can you clarify the following two points?
- Provide evidence that EPD is more effective than other TDA methods.
- 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?

[Cufar] MATIJA ČUFAR AND ŽIGA VIRK, FAST COMPUTATION OF PERSISTENT HOMOLOGY REPRESENTATIVES WITH INVOLUTED PERSISTENT HOMOLOGY, https://arxiv.org/abs/2105.03629

Also, 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

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

They showcase the benefits of the proposed approach on different experimental tasks. 
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. 

- [Clarity] The paper is well written an pleasant to read.

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

- [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. 
questions: # Questions 

1. 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?
2. (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?
3. 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? 

# Suggestions

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

I do not identify potential negative societal impact _specific to this work_.
review_title: null

Meta-review: metareview: A reasonably interesting paper on deep models to approximate a popular class of objects, extended persistence diagrams, in topological data analysis. This is both an important problem, since these can be used throughout various parts of graph machine learning, and is a challenging one that requires technical innovations. The authors deliver on this, introducing quite good results.

The reviewers (and I) are in agreement about the paper, and the additional results the authors provided in response to the reviews are convincing. For example, on large sparse graphs, the proposed algorithms maintain a big speedup advantage.

Perhaps the only question that came up is whether this work is more of a TDA-specific topic, but in general the paper clearly fits well within the machine learning community.
confidence: Certain
Decision: Accept