Adaptive Topological Feature via Persistent Homology: Filtration Learning for Point Clouds

Summary

In this manuscript, the authors develop a special module that can adaptively learn a suitable filtration function for persistent homology (PH) and its downstream tasks. In particular, their learning module is specially designed, so that resulting persistent homology is isometry invariant. Their model has been tested on two datasets for protein classification and CAD data classification. The model is novel and very interesting!

Strengths

It is a novel approach to use machine learning to learn a suitable filtration function! It has also demonstrated the advantage over traditional approaches.

Weaknesses

Missing important references for related works. The test examples have limited data points. The model may suffer from over-fitting issues.

Questions

1. One of the key point for the submission is to "propose a novel framework to obtain adaptive topological features for point clouds", as mentioned in Page 3, line 71. However, the submission seems to only focus on learning "weight function" using "different radii"! In fact, many other works have been done for designing special filtration process based on data properties, such as local homology, weighted homology, element-specific homology, cohomology (incorporated with special weights), etc. These works can all be viewed as learning (unsupervisedly) "adpative topological features". For instance, (a) local homology: Bendich P, Cohen-Steiner D, Edelsbrunner H, Harer J, Morozov D (2007) Inferring local homology from sampled stratifed spaces. In foundations of computer science, 2007. FOCS’07. 48th Annual IEEE symposium on, IEEE, pp. 536–546 (b) element-specific homology & special distance matrices: Cang ZX, Mu L, Wei GW (2018) Representability of algebraic topology for biomolecules in machine learning based scoring and virtual screening. PLoS Comput Biol 14:e1005929 Cang ZX, Wei GW (2017) TopologyNet: Topology based deep convolutional and multi-task neural networks for biomolecular property predictions. PLoS Comput Biol 13:e1005690 (c) Weighted simplicial complexes: Zhenyu Meng, D Vijay Anand, Yunpeng Lu, Jie Wu, and Kelin Xia, "Weighted persistent homology for biomolecular data analysis." Scientific Report, 10 (1), 1-15 (2020) (d) Topological antoencoders: Moor, Michael, Max Horn, Bastian Rieck, and Karsten Borgwardt. "Topological autoencoders." In International conference on machine learning, pp. 7045-7054. PMLR, 2020. Further, "adaptive topological features for point clouds" can also been achieved through different types of simplicial complexes or hypergraphs. For instance, the topological features of Rips complexes are dramatically different from Dowker complexes, Neighborhood complexes, Hom-complexes, etc. Xiang Liu, Huitao Feng, Jie Wu, and Kelin Xia, "Dowker complex based machine learning (DCML) models for protein-ligand binding affinity prediction." PLOS Computational Biology, 18(4), e1009943 Xiang Liu, and Kelin Xia, "Neighborhood complex based machine learning (NCML) models for drug design." In Interpretability of Machine Intelligence in Medical Image Computing, and Topological Data Analysis and Its Applications for Medical Data, pp. 87-97. Springer, Cham (2021). Xiang Liu, Huitao Feng, Jie Wu, and Kelin Xia, "Hom-complex-based machine learning (HCML) for the prediction of protein–protein binding affinity changes upon mutation", Journal of Chemical Information and Modeling, 62 (17), 3961-3969 (2022) 2. The discussions of vectorization of PH are not proper. In particular, “The idea to learn vectorization of persistent homology was pioneered by Hofer et al. (2017” is incorrect. To learn statistic or combinatorial properties (unsupervised) from persistent diagram or persistent barcodes is a common approach. For instance, Bubenik, Peter, and Peter T. Kim. "A statistical approach to persistent homology." Homology, homotopy and Applications 9, no. 2 (2007): 337-362. Chung, Moo K., Peter Bubenik, and Peter T. Kim. "Persistence diagrams of cortical surface data." In Information Processing in Medical Imaging: 21st International Conference, IPMI 2009, Williamsburg, VA, USA, July 5-10, 2009. Proceedings 21, pp. 386-397. Springer Berlin Heidelberg, 2009. Bubenik P (2015) Statistical topological data analysis using persistence landscapes. J Mach Learn Res 16:77–102 Chi Seng Pun, Si Xian Lee, and Kelin Xia, "Persistent-homology-based machine learning: a survey and a comparative study." Artificial Intelligence Review, (2022) Dey, Tamal Krishna, and Yusu Wang. Computational topology for data analysis. Cambridge University Press, 2022. 3. In the test examples, the data sizes seem to be relatively small, i.e., less than 2000 datapoints. But the learning module has multiple fully connected layers. In this way, overfitting can easily be a problem. The authors are suggested to do some ablation studies to address the issue. Further, some more details for PH analysis are needed. For instance, filtration sizes for the data, vectorization of persistent images, etc.

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

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

It will be great if the authors can use more realistic examples and compare with state-of-the-art models.

Summary

The paper develops a neural network to learn weights of given points in addition to other internal parameters to classify 3D clouds of unlabeled points on several public datasets.

Strengths

The authors should be highly praised for a rigorous approach to an important problem of point cloud classification by using isometry invariants from persistent homology. The paper is generally well-written.

Weaknesses

Questions arise already when reading the abstract in line 11: "to make the resulting persistent homology isometry-invariant, we develop a neural network". For standard filtrations such as Vietoris-Rips, Cech, or Delaunay complexes on a point cloud, the persistent homology is already an isometry invariant of a given cloud of unlabeled points because constructions of all complexes above depend only on inter-point distances. The main drawback of persistent homology is its weakness as an isometry invariant, which should have been clear to all experts in computational geometry many years ago but was demonstrated only recently. The paper by Smith et al (arxiv:2202.00577) explicitly constructs generic families of point clouds in Euclidean and metric spaces that are indistinguishable by persistence and even have empty persistence in dimension 1. Though Topological Data Analysis was largely developed by mathematicians, the huge effort over many years was invested into speeding up computations, rather surprisingly, instead of trying to understand the strengths and weaknesses of persistent homology, especially in comparison with the much simpler, faster, and stronger invariants of clouds under isometry. Persistence in dimension 0 was actually extended to a strictly stronger invariant mergegram by Elkin et al in MFCS 2020 and Mathematics 2021, which has the same asymptotic time as the classical 0D persistence and is also stable under perturbations of points. A SoCG 2022 workshop included a frank discussion concluding that there was no high-level problem that persistent homology solves. In fact, persistence as an isometry invariant essentially tries to distinguish clouds up to isometry, not up to continuous deformations since even non-uniform scaling changes persistence in a non-controllable way. On the other hand, the isometry classification problem for point clouds was nearly solved by Boutin and Kemper (2004), who proved that the total distribution of pairwise distances is a generically complete invariant of point clouds in any Euclidean space. The remaining singular cases were recently covered by Widdowson et al in NeurIPS 2022 and CVPR 2023.

Questions

Are there any theoretical guarantees that the output of the proposed neural network distinguishes infinitely many (almost all?) point clouds as pairwise distances do? What theoretical results in the paper are stronger than the past work by Widdowson et al in CVPR 2023? In subsection 5.1, what is the dataset size relative to the Protein Data Bank? In subsection 5.2, how representatives are "subsampled 128 points" (line 302) for objects such as "beds, chairs, and desks" (line 298). For example, can humans distinguish between a bed and a desk by looking at 128 randomly sampled points? What is the asymptotic complexity (in the number of points in a given cloud) of the algorithm described in section 3? What was the actual running time for training and testing, and what are the technical specifications of the used machine?

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.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The very last paragraph on limitations only discusses talks about future work, for example about "generalizing our framework to include a wider class of weighted filtrations" (line 342). Yes, there are numerous papers that go even further and include a given point cloud as a raw input without computing any justified invariants. Since the authors have written detailed and accurate mathematical proofs in the appendix, they could probably agree that *examples prove nothing* because counter-examples can still exist, especially when all possible data (as for point clouds) fill a continuous space. For continuous data, a continuous parametrization or metric can be more suitable than a discrete classification, which practically cuts a continuous space into disjoint pieces. Since all tables of experimental results include accuracies of at most 84% in table 1 (maximum 75% in table 2), the best and certainly publishable contribution seems to be Theorem 4.1. Can a mathematical venue be more suitable for this important result? To help the authors with future submissions, the key insight from "AlphaFold2 one year on" https://www.nature.com/articles/s41592-021-01365-3 exposes the major limitation of all brute-force predictions, not only for AlphaFold. What resources (money, people, even electricity and water) are needed not only to get the first predictions but to annually update predictions with new training data? Is it really sustainable in the long term?

Summary

A neural network that learns the filtration for persistent homology on given point cloud data is introduced, theoretically justified, and evaluated experimentally on 2 data sets.

Strengths

(S1) If this is indeed the first work that considers learning filtrations on point clouds, I find the idea very relevant. (S2) The filtration learning approach is very nicely motivated and described (Lines 185 – 196).

Weaknesses

(W1) The need for learned filtrations should be better motivated. Think of an example point cloud where some other learnable filtration is more meaningful than Rips or DTM, visualize all three filtrations and their PDs. For example, we know that DTM is more suitable than Rips in the presence of outliers, but when is another filtration better than Rips and DTM? This would provide guidance to readers when it would make sense to use your approach, instead of relying simply on the Rips and DTM filtration. From Table 1 results, it seems that some answers might lie in the protein data set you consider. (W2) [1] and [2] seem to be related work, but are not referenced? (W3) The improvement with a learned filtration is good for protein classification, but it is for sure not convincing for the 3D CAD data (whereas it is much more complicated and computationally difficult). It would therefore be useful to provide more information about the data (including visualizations), and more detailed insights. I took a look at Appendix C, but this does not provide answers to these questions. Negative insights are also meaningful, i.e., that learning a filtration might not be useful for a lot of problems, and that relying on Rips or DTM filtration is good enough. (W4) You write: “… the classification accuracy is better when our method was concatenated with DeepSets/PointNet compared to using DeepSets/PointNet alone. The accuracy when we combine our method and PointMLP is not higher than that of PointMLP. This would mean that concatenating the topological feature is effective when the number of parameters of a DNN-based method is relatively small.” I find this argument extremely flawed, since the number of parameters for PointNet and PointMLP is very comparable? [1] Zhang, Simon, Soham Mukherjee, and Tamal K. Dey. "GEFL: Extended Filtration Learning for Graph Classification." Learning on Graphs Conference. PMLR, 2022. [2] Horn, Max, et al. "Topological graph neural networks." arXiv preprint arXiv:2102.07835 (2021).

Questions

(Q1) PH wrt some filtrations (e.g., height, useful to distinguish MNIST digit 6 from digit 9) is not isometry-invariant, so why do you impose this condition? (Q2) Figure 1: Comment more why this approach is meaningful, since 2 holes are not recognized with 1-dim PD for any of the two point clouds? Consider plotting (next to) more reasonable weights. (Q3) You never mention simplicial complexes, so that it remains unclear why the filtration discussed on lines 143-144 is Rips, and not Čech? (Q4) How does your weighted Rips filtration compare to the weighted Rips filtration discussed in [3] (Proposition 3.5), where point cloud point x appears according to its filtration function value (weight) f(x), and an edge (x, y) appears when f(x), f(y) and distance d(x, y) satisfy certain properties? (Q4) Related to (Q3) and (Q4), do all point cloud points immediately appear in your filtration? In particular, if a point has a really large weight, the balls centered at this point will expand very late in the filtration, but will the point (ball with radius 0) be there from the beginning? This is important e.g. if the point is an outlier, since we commonly want to ignore such a point. (Q5) “Although (a) and (b) can be learned together since the output of the resulting feature is differentiable with all parameters, it would make the optimization unstable.” Why, can you explain more? (Q6) In Section 5, can you provide more intuition on what is captured with DistMatrixNet? Other minor comments: - The homology is persistent (not persistence homology), but we talk about persistence landscapes and images (not persistent landscape or image), rephrase throughout the paper. - Line 86: Explicitly mention DeepSets. - Line 142: “one can take function S defined by” -> “one can take S to be the distance to point cloud, defined by” - Line 156: “which can also [add: be] computed only by distance matrices”. Do you not need the weights too? - Line 168: What is function u, where is it used? - Line 169: “we can vectorize persistent a persistent diagram”. Rephrase. - Line 234: Do topological features and DNN features have to have the same dimension L? - Line 251: “we can approximate any continuous function on X x [0,1]^m can be approximated”. Rephrase. - Line 253: Cite specific Appendix. - Line 283: “we replaced our topological featured replaced”. Rephrase. - Line 285: “Note that we use DistMatrixNet not for the computation of filtration weights.” This sentence seems weird, what do you mean? - Table 2 caption: “concatenated the feature” -> “concatenated with the feature”? - Mention explicitly that the code is made publicly available. - References: Check capitalization of acronyms in paper titles (e.g., Dtm, Perslay, Ripsnet, Toposeg, Homcloud, Pointnet, 3d, Pointet++, Pi-net, 3d shapenets, Sgmnet, …), and be consistent between capital case vs. lower case for journal names. [3] Anai, Hirokazu, et al. "DTM-based filtrations." Topological Data Analysis: The Abel Symposium 2018. Springer International Publishing, 2020.

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

2 fair

Presentation

3 good

Contribution

3 good

Limitations

Some limitations and corresponding future research directions are mentioned, but they do not address the lack of insights on when a learned filtration can be expected to be beneficial (compared to e.g. Rips and DTM filtrations).

Summary

This paper investigates the extraction of global topological features using the framework of persistent homology. The authors have proposed a neural network architecture to learn the filtration weights for each point in an end-to-end and data-driven manner, which is later supported by an approximability theorem. Additionally, a two-phase training procedure is introduced to further improve the performance of the proposed architecture. The proposed framework is then applied to different tasks such as protein 3D CAD classifications.

Strengths

1. [Originality] The filtration weight is usually constructed without considering the label information, e.g., a constant for VR complex and k-NN info for DTM. The authors proposed a framework to learn the weights for each point from the label using a neural network. 1. [Quality] Being able to provide an approximability theorem to support/motivate the choice of the neural network architecture is nice. 1. [Clarity] Great overview on the persistent homology as well as the limitations of the current framework. The author laid out the contribution in the very beginning of the introduction which can help present the novelty of this work. Overall, a well-written paper. 1. [Significance] TDA framework has long been suffered from the topological noise issue. Being able to propose a way to automatically learn a weight function to suppress the noises is an important contribution to the field.

Weaknesses

1. It looks like there are two contributions in this paper: 1) propose a way to learn the weighted filtration as per Section 3.1, with theoretical guarantee in Section 4; and 2) Section 3.2 in the ability to approximation with composite function. The contribution in 1) is more related to filtration learning as it learns a weighting function, but 2) is a more general use case. However, by looking at the experimental results, it is not clear which contribution is more significant, i.e., the performance gain in Table 1 comes from 1), but the gain in Table 2 comes from 2). It would be nice to consolidate the comparisons between different experiments and provide some discussions. That way, the readers can get a better understanding of the interplay between different contributions. 1. It is not clear to me from reading the main text on how you choose the hyper-parameters for DTM. From reading the appendix, it looks like the parameters are not chosen by cross-validation (Section C.2). Is there any specific reason to not choose this parameter end-to-end using cross-validation? How will a different $q$ and $k$ affect the prediction performance in the protein datasets? 1. It looks like Theorem 4.1 suggests the function can be approximated, but it does not mention whether it can be recovered. Will it be possible to get some results regarding the convergence (i.e., with $n \to \infty$, will the $\epsilon$ shrink?) and/or whether $\psi_1$ and $\psi_2$ can be estimated by the proposed architecture (i.e., how close $\psi_1$ and $\psi_2$ to $h$ and $\phi^{(6)}$, respectively). 1. Related to #4, can we support Theorem 4.1 by running a synthetic example? Specifically, can we show that the true weighting function $f$ can be recovered by the $f_\theta$ in Figure 2?

Questions

1. TDA is also used as data-analysis/unsupervised purposes (e.g., in finding enclosing holes) [A-C], I am curious whether the learned filtration weight $f(X, \cdot)$ can reveal the true topological structures or if one can design some sort of loss function and learn the weight function accordingly? 1. How to correctly understand the connection between the architecture (in Figure 2) and Theorem 4.1? The weighting function $f_\theta(X, x_1)$ is a concatenation of $h(X)$ and $g_1(x)$, but in Theorem 4.1, the $f(X, x)$ can be approximated by a concatenation of $\varphi_1(X)$ and $x$ itself. 1. [Minor language issue] When I first read the paper, it is not clear what the “architecture” and “approximation result” in L12-13 meaning (original sentence: “Additionally, we theoretically show a finite-dimensional approximation result that justifies our architecture.”). Consider adding some details there to improve clarification. For instance, you might want to change it to something like this: “Additionally, we theoretically show a finite-dimensional approximation \textbf{of any filtration function}, which \textbf{justifies (or motivates) the proposed neural network architecture}.” --- [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

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

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

2 fair

Presentation

3 good

Contribution

3 good

Limitations

Authors have addressed the limitations of their work. Negative social impact statement is not necessary in this work, as the primary focus of this manuscript lies in its theoretical contribution.

Summary

This work proposes a novel framework to obtain adaptive topological features for point clouds based on persistent homology by introducing an isometry-invariant network architecture for a weight function and proposes a way to learn a weighted filtration. The work theoretically proves that any continuous weight function can be approximated by the composite of two continuous functions which factor through a finite-dimensional space. The experiments on public datasets shows the proposed method improves the accuracy in classification tasks. All of my questions are carefully addressed in the rebuttal. The work is theoretically solid and has potential.

Strengths

The idea of learning filtration by the weight function is novel. The approximation ability theorem is important. The architecture design is based on this theorem and the isometry-invariance, which is rigorous and interpretable. The experimental results are convincing. The paper is well written, all the concepts, math symbols, theorems are thoroughly explained. The deductions are clear and easy to follow. The experimental results are convincing.

Weaknesses

It is not clear why different weight functions affect the qualities of the topological features, and what are the criteria for the persistent diagrams. Some theoretical explanations and numerical demonstration will be helpful.

Questions

1. What are the criteria for good weight functions ? What are the theoretical explanations for them ? 2. For the purpose of classification, the extracted topological features improves the results. It is unclear how the loss functions are differentiable with respect to the topological features and in turn the weight functions. The homology is intrinsically discrete, the differentiability is not obvious. Some explanation will be helpful. 3. Are the weight functions affected by the point cloud quality ? For example, if the scanning quality is improved, how does that affect the weight function?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

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

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The work can be further improved by use more realistic examples and compare with state-of-the-art models.

DTM > Rips

Regarding your Comment 2: If the parameters of the DTM filtration are tuned properly, it should always obtain at least as good performance as Rips, for k = 0 and q = 2. Why is DTM underperforming for the protein data in your first table of results above, maybe you do not consider these parameter values? In any case, please make sure to explicitly specify the list of considered values for k and q.

further questions

Thank you for the reply. >Our aim is NOT to distinguish the point clouds up to isometry. Have you checked that all your input clouds from different classes are distinguished by persistent homology? If not, all further outputs for these indistinguishable clouds will be identical. > topological features extracted by persistent homology (PH) would be useful How can these features be called topological if PH changes even under non-uniform scaling, much worse under more flexible topological transformations? >PH has been shown to be effective for point cloud analysis and classification for material science [1, 2], biology [3, 4], and medical science [5, 6]. Could you please give exact references to rigorously proved theorems in the cited papers that show the effectiveness of PH? >Although it is isometry-invariant if the filtration is chosen to be isometry-invariant, the use of PH is NOT limited to distinguishing the point clouds up to isometry. If PH is not limited to distinguishing the point clouds up to isometry, under what other equivalence relation is PH an invariant? > If we do not force this network to be isometry-invariant, the resulting PH can be non-isometry-invariant. If the output is not an isometry invariant, does it have other theoretical guarantees? >This is why we make the network to be isometry-invariant. Have you compared the output with the much simpler and faster isometry invariants such as the total distribution of pairwise distances, which was proved to be complete for Euclidean clouds in general position by Boutine and Kemper in Adv. Appl. Math (2004)? > we created the protein dataset composed of 1,000 data by subsampling from 14 types of proteins. This is much smaller than the datasets in Protein Data Bank. Yes, the PDB started in 1971 with 7 structures and now has more than 200 thousands. >The computational complexity can be upper-bounded by O(N^9), where is the number of points. Where is this claim proved in the submission? Is it possible to explain the conflicting quotes from the rebuttal below and justify any claimed beliefs by rigorous arguments? Quote 1. "Due to the high computational cost of our method, we could not apply our method to large point clouds, which makes the accuracy lower." Quote 2. "We believe our method is effective for this task." Quote 3. "We did not claim that we had proposed a new and efficient method to analyze protein datasets."