A Framework for Fast and Stable Representations of Multiparameter Persistent Homology Decompositions

Summary

Persistent homology (PH) is the most important method in topological data analysis (TDA), and multiparameter persistence (MPH) is its natural generalization which is expected to significantly boost its performance. However, because of several mathematical roadblocks, MPH could not be effectively used in real life applications. In this work, the authors proposes a general framework to vectorize MPH. Their framework generalizes all the known existing work as special cases. Furthermore, they provide a subset of vectorizations which are stable. Finally, another obstruction to use MPH in real life applications was their computational costs. The authors new framework provides a much faster way to obtain these vectorizations.

Strengths

Framework provided is very general and it addresses a critical need in TDA. Stable MPH vectorizations, and their convergence studies are excellent contribution to the theory of TDA. Computationally feasible MPH vectorizations will finally enable to use MPH effectively in real life applications.

Weaknesses

Experiments section could be more detailed, and more in-depth analysis could have been provided for the performance of these vectorizations in real life applications. In particular, the authors compare the performance of their vectorizations only with respect to other TDA models, and some simple other models in point cloud setting. Instead, more thorough analysis could have been provided to compare these MPH vectorizations with respect to SOTA models from different domains. A performance evaluation in graph setting would be nice as it is another very important application area of PH.

Questions

From theoretical standpoint, stable vectorizations are always preferable, however, from ML side, when enforcing stability, we might be losing too much information and scarifying performance. With this in mind, can you also suggest a practical, computationally efficient T-CDR methods which potentially provide better performance?

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.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

As authors stated, one of the main limitation of the approach is coming from the generality/flexibility of their framework. For ML applications, there are several choices to make (hyperparameter tuning) to define a suitable vectorization for a given situation.

Summary

The paper investigated the persistent homology with multiple filtration parameters. The authors proposed a framework, T-CDR, which generalized the previous studies in multi-parameter persistent homology. They further presented stability and convergence guarantees on S-CDR, which is a special case of T-CDR introduced to ensure robustness. Third, their theoretical claim and contributions were supported by the empirical convergence studies as well as classification tasks on several immunohistochemistry datasets.

Strengths

1. [Originality] The proposed framework, T-CDR in Definition 1 not only generalized previous work in candidate decomposition (e.g., MPI) as well as approaches in rank-invariant (MPL, MPK). I believe that it opens up new research on ensuring different guarantees by varying parameters/operators in (1). 1. [Significance] The stability and convergence guarantee (Theorem 1 and (8)) of S-CDR, which is a special case of T-CDR, provides a more stable and useful multi-parameter persistent homology framework. 1. [Quality] The authors supplement the convergence rate claim with informative empirical convergence studies, showing a clear trend of error rate reduces with $~n^{-1/2}$ as $n$ grows matching eq. (8).

Weaknesses

1. In the empirical convergence rate experiment, it was not clear to me what is the “ground truth” representation you are comparing against. For synthetic data in Figure 3, it makes sense that you can get access to the density $f$ (therefore $\mathcal F_{C, f}$ and $\mathbb M$) given that you generated the data from some probability distribution. How do you get the $\mathbb M$ for the immunohistochemistry data (as in Figure 4)? Provide more clarifications on this will be beneficial. 1. It seems like MPL runtime can be improved 25x-50x with the sparse implementation in Algorithm 4 (see, e.g., Row #2 of Table 2 vs. Rows #4 and #6 of Table 2); this suggests that the runtime win might be due implementation rather than faster algorithmic time complexity. The claim will be more convincing if the authors can provide more insights, justifications, or analyses of the time complexity as to why the proposed algorithm is more efficient than prior work. 1. What is the bifiltration parameters used for each experiments in Sections 4? Are they radius and co-density for Figure 3, and CD8 and CD68 for the immunohistochemistry data? Adding more explanation there will increase the clarity more. 1. In Sections 1-3, the function $f$ is used to define the multi-parameter filtration function; however, in Section 4, the notation is defined as the density (e.g., in L254). I would suggest to choose another notation to avoid confusion.

Questions

1. It looks to me most of Section 4.1 is a continuation of Theorem 1, is there any specific reason to put this in this section rather than in Section 3 (and make it a Proposition/Corollary)? 1. Empirically, how sensitive is the algorithm for the larger intrinsic dimension $d$? If I understand the experiments correctly, they all seem to have $d=2.$ I am curious about how the intrinsic dimension $d$ will impact convergence and/or performance. 1. I am also curious about how the proposed framework can be applied in higher-order homology descriptors (empirically). This is also related to Question #2 above. 1. TDA has been applied in numerous different domains such as galaxy, proteins, single-cell sequencing, 3D CAD point clouds, medical imaging [A-C] etc. I am curious if the proposed multi-parameters filtraion work can be expanded in fields outside immunohistochemistry. 1. How optimal/tight is the bound in (8)? Can we get a better convergence result if we choose op, $\omega$, and/or $\phi$ differently? 1. [Minor] Given that T-CDR is a generalization of both the rank-invraint and candidate decomposition method, should the name template “candidate decomposition” representation be modified to better reflect what it can be capable of? 1. [Minor/Typo?] Should the citation in L477 be [CB20] instead of the PersLay paper? --- [A] Wasserman, Larry. “Topological Data Analysis.” Annual Review of Statistics and Its Application 5 (2018): 501–32. [B] Chen, Yu-Chia, and Marina Meila. “The Decomposition of the Higher-Order Homology Embedding Constructed from the k-Laplacian.” Advances in Neural Information Processing Systems 34 (2021). [C] Wu, Pengxiang, Chao Chen, Yusu Wang, Shaoting Zhang, Changhe Yuan, Zhen Qian, Dimitris Metaxas, and Leon Axel. “Optimal Topological Cycles and Their Application in Cardiac Trabeculae Restoration.” In International Conference on Information Processing in Medical Imaging, 80–92. Springer, 2017.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Authors have addressed the limitations of their work. Negative social impact is not applicable because this work is a theoretical contribution.

Summary

As the title clearly suggests, a general representation of multiparameter persistent homology (MPH) is introduced. Unlike earlier representations that either yield a loss in information or are unstable, the proposed vectorization is strictly more informative, and is shown to be stable for a specific settings of the parameters in the general approach. The approach is evaluated on several real data sets.

Strengths

(S1) I do not have an overview of MPH literature, but assuming that the authors provide a complete and honest overview of earlier work, the contributions in this paper are substantial. (S2) Figure 1 and the discussion on Lines 170 – 185 clearly and nicely position the work in the existing literature.

Weaknesses

The main experimental results in Table 1 show that the proposed S-CDR approach is half of the time significantly outperformed by other existing methods.

Questions

(Q1) Looking at Figure 2, it does not seem as challenging, but rather straightforward to represent the plot in the middle with the image on the right? (Q2) You claim that S-CDR is strictly more powerful than MPK, but MPK achieves better scores on DPOC, PPTW, GPAS, GPMVF data sets (Table 1). This deserves at least a brief discussion. (Q3) Why do you exclude some data sets considered in [CB20] from your experiments (Table 1)? Are the filtrations used to calculate your S-CDR the same as the filtrations to calculate MPK, MPL and MPI in earlier works? Why do you not evaluate the running times also on the Table 1 data set, and compare it against the results in [CB20]? Other minor comments: - The order of Figures 1 and 2 should be reversed, since the latter is referenced first in the text? Similarly, Sections 4.2 and 4.3, or Table 1 and Table 2 should be reversed? - When listing the contributions, add “(Section 3)” after “statistical convergence of our representations”. The Outline paragraph soon below then becomes almost redundant. - Line 169, Line 177, Line 343: Perslay -> PersLay - Line 202: “the two following S-CDR”. I would remove “two,” as it might imply a diminished contribution, since you actually define an S-CDR for every p in N. - I would start every item in a list on Lines 194-195 and Line 204 on a new line, as this is important information that the reader should be able to find and read easily. If there are space limitations, you can sacrifice the Outline paragraph in Section 1, see one of the minor comments above. - Table 1: What is highlighted in red? - Line 314: “the same bifiltration as in the previous section”. Subsection? In this case too, the previous subsection does not contain any information on bifiltration. - Table 1: What does “P” denote for the last row in the table? - Line 326: “almost always outperform” is an overstatement. - Table 2: For better readability, only consider or s or ms, remove them from the individual cells and place in brackets in column titles. - Line 344: parameter -> parameters - References: Be consistent between capital case vs. lower case for the paper titles. Remove # from 2D, and remove double reference [CdGO15], [CdSGO15].

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

The limitations and future research directions are clearly presented in the final section.

Summary

The paper addresses topological data analysis in the multiparameter setting and focuses on the problem of representation of multiparameter persistent homology by vector space elements so that standard ML algorithms can be applied. The key advance in the paper is the leveraging of decomposition ideas in multiparameter settings to devise a representation framework that is shown to be theoretically stable with practical, efficient computation. The strengths in statistical convergence, accuracy and computational speed are validated in specific UCR classification datasets.

Strengths

Originality: The paper draws inspiration from past work on multiparameter persistent homology by Carriere et al. It offers a theoretical formulation that provides stability guarantees (e.g. statistical rates of convergence) and is a generalization of the past work. Quality: The paper is comprehensive including the appendix. I did not go through the details of the proofs and cannot comment on the theoretical correctness of the paper. Clarity: The paper is very clear with comprehensive references to the latest in the field. Significance: The paper appears to be of theoretical significance and will be of importance to researchers in Topological Data analysis.

Weaknesses

While the experimental results show the power of S-CDR on several datasets, It will be interesting to see how the method applied to more complex datasets (e.g. from imaging related applications). The experimental validation is limited but sufficient.

Questions

I could not follow the notation in table 1 as it is not clear why there are multiple highlighted numbers (I would assume that the red numbers correspond to the best classification results, but in both table 1 and in the appendix on time series classifications there are multiple flagged columns of relevance).

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

None

Satisfied with the rebuttal.

Thanks for the additional experiments and the revisions.