Stable Vectorization of Multiparameter Persistent Homology using Signed Barcodes as Measures

Persistent homology (PH) provides topological descriptors for geometric data, such as weighted graphs, which are interpretable, stable to perturbations, and invariant under, e.g., relabeling. Most applications of PH focus on the one-parameter case -- where the descriptors summarize the changes in topology of data as it is filtered by a single quantity of interest -- and there is now a wide array of methods enabling the use of one-parameter PH descriptors in data science, which rely on the stable vectorization of these descriptors as elements of a Hilbert space. Although the multiparameter PH (MPH) of data that is filtered by several quantities of interest encodes much richer information than its one-parameter counterpart, the scarceness of stability results for MPH descriptors has so far limited the available options for the stable vectorization of MPH. In this paper, we aim to bring together the best of both worlds by showing how the interpretation of signed barcodes -- a recent family of MPH descriptors -- as signed measures leads to natural extensions of vectorization strategies from one parameter to multiple parameters. The resulting feature vectors are easy to define and to compute, and provably stable. While, as a proof of concept, we focus on simple choices of signed barcodes and vectorizations, we already see notable performance improvements when comparing our feature vectors to state-of-the-art topology-based methods on various types of data.

Paper

References (89)

Scroll for more · 38 remaining

Similar papers

Peer review

Reviewer csyn8/10 · confidence 5/52023-06-25

Summary

In this paper, the authors are addressing a very critical need in topological data analysis (TDA), vectorization of multiparameter persistence (MPH). Persistent homology (PH) is the key method in TDA, but in its current form, it allows only a single function to use in its key process, filtration. By enabling multiple functions, MPH is a natural generalization of (PH) with much finer information, however, there are several mathematical obstructions to use them effectively in applications. In this paper, the authors propose an effective way to vectorize the barcode information in the MP module by sacrificing some to keep the computation feasible and process practical. They offer two versions of MP vectorizations where one being kernel and the other being direct vectorization, both can be effective in different settings. The authors made extensive experiments in several settings, including point cloud, graph classification, and virtual screening to compare their model with other MP vectorizations and SOTA models. Their model consistently outperforms existing MP vectorizations.

Strengths

The authors use a recent idea of signed barcodes cleverly to obtain practical vectorizations. There is a significant need to employ MPH idea with good and feasible vectorizations, and this paper makes a valuable contribution in this direction. They propose two versions of their vectorizations, a kernel (MP-SW) and a direct vectorization (MP-C). In the past years, depending on the domain, we see that one can perform better than the other from our experience with the applications of single persistence. So, this versatility of outputs is very valuable for ML applications. Computational time is significantly better than existing MP vectorizations. Combining with its good performance, this might be the most important contribution of the paper from ML perspective. Their extensive experiments in various settings show that their model consistently outperforms the existing MPH vectorizations.

Weaknesses

The main weakness is that the paper might be too technical for non-experts and ML audience. However, considering the depth of the problem, I can see that the authors did an enormous effort to make this important subject accessible to a wider audience. While new vectorizations consistently outperform the existing MP models in point cloud settings, the performance is not as strong in graph classification and specifically, virtual screening cases (TODD also uses a version of MPH). As MPH is an involved process, hyperparameter tuning might need serious expertise in TDA in real life applications.

Questions

This is more of a question/remark. A low-hanging fruit might be to combine (concatenate) Hilbert functions (MP-H) with MP-HSM-C (or MP-ESM-C) as you already compute MP-H during the process if I understand the process right. Considering the closeness of the performances in graph classification and virtual screening, this combined vectorization might perform better.

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.

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

3 good

Contribution

4 excellent

Limitations

As mentioned in weaknesses, the main limitations are scalability and hyperparameter tuning which could be very tricky, especially choosing the right grid size. Hence, performance vs. computational feasibility can be a problem in large datasets.

Reviewer VRYZ4/10 · confidence 4/52023-07-06

Summary

The paper vectorizes data descriptors coming from multiparameter persistent homology for classifying point clouds and measuring similarity between graphs extracted from databases of times series and molecules.

Strengths

The paper includes rigorous definitions and proves (in the appendices) three theorems from section 4.

Weaknesses

The paper seems to over-advertise the strengths of persistence. Lines 1-2 claim that "Persistent homology (PH) provides topological descriptors for geometric data, such as weighted graphs". If the authors really meant a topological classification of graphs, this classification has been known to Euler in the 18th century, so there is no need to re-invent topological invariants of graphs by using persistence. Lines 22-23 claim that "TDA methods usually require the sole knowledge of a metric or dissimilarity measure on the data". In fact, the definition already of persistence requires a choice of filtration of simplicial complexes on given data points, which seriously affects the resulting persistence whose further analysis requires many more extra parameters, see lines 351-352: " Our pipelines, including the choice of hyperparameters for our vectorizations, rely on the cross validation of several parameters, which limits the number of possible choices" Examples 1-3 are definitions or comments, not illustrative examples that could help the readability. The questions and limitations below include further concerns about experiments and comparisons with past work.

Questions

Lines 14-15 claim that "The resulting feature vectors are easy to define and to compute". If this is true, could the authors write a full easy definition of these vectors in a few lines? Concerning the computation, line 245-256 seem more honest: "We discretize the computation of the sliced Wasserstein kernel by choosing directions {θ1, . . . , θd} ⊆ Sn−1 uniformly at random". Are there any theoretical guarantees for this approximate computation and what is the asymptotic cost in the size of the input? The authors correctly highlight the importance of stability (Lipschitz continuity) under noise. However, the practical experiments in section 4.2 use discrete grids, which makes all features discontinuous under perturbations of times series or point clouds. Is it possible to avoid this discretization? Section 4.3 discusses datasets of graphs coming from social networks, biology, and medicine. How can edges be justified in these experimental graphs? In social networks, friendships or other links between people have different strengths and are always subjective. In molecules, even the strongest covalent bonds between atoms have no strict definitions and only abstractly represent inter-atomic interactions, so there are physical sticks or strings between them. That is why most databases of molecules and materials such as QM9 contain only atomic positions but no links between them. Which of the invariants in Appendix B are provably Lipschitz continuous under perturbations of points, sat in the bottleneck distance on the persistence diagram? Which of these invariants are faster or stronger than the isometry invariants from Widdowson et al (CVPR 2023)? Which (dis)similarity functions mentioned in the paper satisfy all metric axioms? The importance of metric axioms including the triangle inequality was theoretically justified in the paper arXiv:2211.03674, which should be cited in every work on clustering and metric distances because any clustering based on non-metrics is not trustworthy.

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 main limitation of the 1-parameter persistence 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. These examples can be easily extended to more than one parameter at least for some filtrations. 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 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. Is there such an ultimate problem for multi-parameter persistence? In fact, persistence as an isometry invariant essentially tries to distinguish clouds of unlabeled points 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.

Reviewer cn3Z6/10 · confidence 3/52023-07-07

Summary

The authors introduce first vectorizations of multiparameter persistent homology (MPH) via signed barcodes, that are easy to compute and shown to be stable. The two proposed vectorizations often outperform the state of the art MPH methods on a variety of data sets.

Strengths

(S1) The paper is clearly organized and written, it reads really well. (S2) The experiments are rather extensive and the results seem convincing.

Weaknesses

I did not identify major weaknesses in this work, besides some confusion about the experimental settings addressed in question (Q2) below. I am open to raising my score if this issue is properly addressed.

Questions

(Q1) The proposed approach is theoretically weaker than some other (Appendix A, Proposition 1), but it outperforms them. This should be at least briefly commented/discussed. (Q2) It seems that the two and three filtrations used respectively in Sections 4.2 and 4.3 for the calculation of proposed MPH featurizations are not the same as the other considered MPH approaches from the literature? How is the comparison fair/reasonable then? (Q3) Can you comment on why MP-HSM-SW is much better for some, whereas MP-ESM-C performs significantly better for other data sets? Other minor comments: - Definition 6: Name the introduced notion K * \mu. - Line 81: Briefly summarize the conclusions of the runtime assessment, i.e. that your pipeline is much faster than the other topological baselines, by several orders of magnitude (Appendix D.2, Table 3). - Theorems and Propositions: For better readability, it would be useful to name the theoretical results. - Section 4.1: Describe the data and filtration. - Line 301: “As one can see from the results in Table 2, MP-HSM-SW is quite efficient”. Rephrase, since Table 2 does not show the computation times, but accuracy. - Table 4 caption: MP-HSM-C -> MP-ESM-C? - References: Be consistent between capital case vs. lower case for journal names, and also between full and shortened names, e.g. Journal of Machine Learning Research or J. Mach. Learn. Res. (similarly, Discrete Comput. Geom, Found. Comput. Math, …). Correct 2d, Xgboost, ucr, betti, Tudaset.

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

The limitations and future work are discussed in detail.

Reviewer 61ca6/10 · confidence 3/52023-07-08

Summary

This work promote the use of signed barcodes for feature generation, and proposed the feature generation pipeline based on the signed bar codes, a. the work introduces two general vectorization techniques for signed barcodes; b. the authors prove Lipschitz-continuity results that ensure the robustness of the proposed entire feature generation pipeline c. the practical performance of the proposed pipeline is compared to other baselines in various supervised and unsupervised learning tasks. All of my questions are fully addressed by the rebuttal. I am satisfied with the explanations. I think the work is solid and promising.

Strengths

This work generalizes the single parameter bar codes to multi-parameter bar codes, introduces general vectorization techniques for signed barcodes, and prove Lipschitz-continuity results to ensure the robustness of the proposed pipeline. The theoretic results are important and convincing. The paper is well written, the key concepts are explained thoroughly, the proofs of the main theorems are clear and in details. The experimental results are analyzed in details.

Weaknesses

The motivation for multi-parameter persistent homology could be further emphasized. From theoretical point of view, it is unclear what extra-information can multi-parameter PH bring compared to single-parameter PH. It will be helpful to add some experiments to validate the stability theorems, and estimate the Lipschitz-constant. The definition of the Kantorovich-Rubinstein norm for point measures in proposition 1 is inconsistent with that in definition 3. The definition 3 allows point mass splitting, namely one source point can be mapped into multiple target points, hence \psi is a transportation scheme; but in proposition 1, each source point is mapped to a single target point, \gamma is a transportation map. This needs to be clarified.

Questions

1. Whether single-parameter persistent homology is equivalent to multi-parameter persistent homology ? What extra-information can multi-parameter PH contributes? 2. The Kantorovich-Robinstein norm in Definition 3 is inconsistent with that in proposition 1, under what conditions are they equivalent in general ? 3. The generalization of theorem 1 to higher dimension is open, is the difficulty intrinsic or just technical ?

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

2 fair

Contribution

2 fair

Limitations

The authors have adequately addressed the limitations, which are helpful for practical applications.

Area Chair rsfV2023-08-18

Dear reviewer, Please **briefly acknowledge the rebuttal** by the authors and consider updating your score—we want to avoid borderline scores for reviews, and the discussion phase will close soon. If you have any additional questions to the authors please ask them **now**. Thanks,\ Your AC

Reviewer VRYZ2023-08-12

remaining questions

Thank you for the reply. >efficacy of PH, which is well-established given the vast amount of existing applications in ML ([Hensel, Moor, Rieck, 2021] and references) The strong claim about efficacy requires serious justifications not by including a vast amount of papers but by quoting rigorously proved theorems. The widely cited stability of persistence gives only an upper bound under perturbations. Such a Lipschitz upper bound is straightforward for many easier and faster invariants, for example, the total distribution of pairwise distances. The key ignored difficulty was the lack (actually, impossibility) of a lower bound, because the persistence doesn't change or even remains trivial (fully empty) under all perturbations for a generic family of point clouds, even in the plane. While Theorems 1-3 prove upper bounds, can the left hand sides of these inequalities be zeros for different functions and measures? Could the authors please specify exact places, where the paper [Hensel, Moor, Rieck, 2021] discusses efficacy of PH? The Frontiers Media is actually known for the facts of controversial reviewing https://en.wikipedia.org/wiki/Frontiers_Media#Controversies > persistence allows one to incorporate much richer information into topological descriptors by using filtrations derived from the weights. How does persistence incorporate topological descriptors if the persistence changes even under non-uniform scaling, much worse under more flexible topological deformations? >The fact that our method has hyperparameters does not prevent it from being applicable in arbitrary metric spaces or weighted graphs. One can resort to default choices as in Section 4.4. What choices were called default here: "grid size of k = 1000 for all methods" in line 336? How is this number 1000 justified? >"Which of [...] persistence diagram?" We are not sure to understand this question: since the invariants being referred to are invariants of multiparameter persistence modules, there is, a priori, no persistence diagram. Which of the invariants in Appendix B are provably Lipschitz continuous under perturbations of given points? >[Curry, Mukherjee, Turner. Trans Amer Math Soc Ser B, 2022] shows that several one-parameter filtrations, taken together, can uniquely characterize simplicial complexes in Euclidean space up to action of the orthogonal group. Main Theorem 7.14 in this paper is proved only for complexes in general position. A reconstruction in general position was proved for the harder case of point clouds (without any edges or simplices) by Boutin and Kemper "On reconstructing n-point configurations from the distribution of distances or areas" in Advances in Applied Mathematics (2004) by using the much simpler distribution of pairwise distances without any slower persistence. Do the words "up to action of the orthogonal group" mean that the persistence-based objects from the paper above should be compared by rotations? To check if original complexes are rigidly equivalent, it's easier to fix their centers of mass at the origin and rotate given vertices, see Alt et al "Congruence, similarity, and symmetries of geometric objects" in Discrete and Computational Geometry (1988) and Brass et al "Testing congruence and symmetry for general 3-dimensional objects" in Computational Geometry (2004).

Authorsrebuttal2023-08-13

We thank you again for the discussion. - *"The strong claim about efficacy requires [...]"* [Hensel, Moor, Rieck, 2021] is about the diversity of "existing applications in ML". Efficacy is not only about theoretical results but also about practical performances, especially in an ML venue such as this one. In this regard, a number of TDA works have been published every year at NeurIPS since 2019 (e.g., [Zhao, Wang. NeurIPS 2019], [Hu, Li, Samaras, Chen. NeurIPS 2019], [Kim, Kim, Zaheer, Kim, Chazal, Wasserman. NeurIPS 2020], [Carrière, Blumberg. NeurIPS 2020], [Vishwanath, Fukumizu, Kuriki, Sriperumbudur. NeurIPS 2020], [Chen, Coskunuzer, Gel. NeurIPS 2021], [Birdal, Lou, Guibas, Simsekli. NeurIPS 2021], [Zheng, Zhang, Wagner, Goswami, Chen. NeurIPS 2021], [Demir, Coskunuzer, Gel, Segovia-Dominguez, Chen, Kiziltan. NeurIPS 2022], [Akcora, Kantarcioglu, Gel, Coskunuzer. NeurIPS 2022], [Turkes, Montufar, Otter. NeurIPS 2022]). - *"While Theorems 1-3 prove upper bounds, can the left hand sides of these inequalities be zeros for different functions and measures?"* We believe that there may be lower bounds for theorem 2 for point measures with bounded number of masses, and for theorem 3 only locally and also for point measures with a bounded number of masses. A lower bound for theorem 1 is probably not possible in full generality. Yet, the experiments in our paper show that the invariants are still expressive enough in a variety of contexts. - *"How does persistence incorporate topological descriptors [...] deformations?"* Persistence is known to be a homeomorphism invariant of filtered topological spaces, in that the composite of a homeomorphism with a filtering function has the same persistence barcode as the filtering function. How this general invariance translates to transformations of the data depends on the (application dependent) construction that turns data into filtered spaces. In any case, we don't mean that persistence "incorporate topological descriptors" as you write, but rather that it turns a topological descriptor, such as homology, into a richer descriptor that encodes additional information captured through the filter function. Note also that multiparameter persistence is what naturally arises when considering multiple filter functions. - *"What choices were called default here [...]"* To avoid the parameter $k$, one can proceed as outlined in the response to one of your previous questions, by noticing that the distance between the vectors returned by our vectorizations has a closed form solution. To simplify the implementation, we simply chose a grid that is as fine as possible, given our computing resources. - *"Which of the invariants in Appendix B [...]"* The invariants in Appendix B are for persistence modules. How the persistence modules are constructed from the data, and thus, how they vary with respect to perturbations of the data, is application dependent. We note, however, that the papers that introduce some of the invariants of Appendix B (e.g., persistence landscape and its multiparameter versions, and multiparameter persistence kernel) prove stability results, usually in terms of the interleaving or matching distance between multiparameter persistence modules. - *"[Curry, Mukherjee, Turner. [...]"* We mentioned this paper as one particular example of a difficult practical problem that can be addressed using multiple parameters/directions. The references you provided, and the discussion about their relationship to the paper we mentioned, are very interesting. However, we believe this discussion is outside the scope of this rebuttal, since it is only tangentially related to our submission. Based on your feedback and the references you have provided so far, we propose to add a clarification in Section 4.2, explaining that, in that application, we are not trying to do point cloud classification up to isometry (because of the possibility of outliers), a problem for which well-developed methods exist as you have pointed out.

Reviewer VRYZ2023-08-21

Thank you for the reply

Thank you for the reply. In lines 295-296, the paper chose to "compare against non-topological, state-of-the-art baselines: Euclidean nearest neighbor (B1), dynamic time warping with optimized warping window width (B2), and constant window width (B3)". Since the word "neighbor" appears only once in the whole paper with appendices, would it be possible to clarify please if B1 has only one distance from every point to its first nearest neighbor in a given cloud? On what proportion of the datasets in Table 2 have the methods MP-... outperformed all the chosen baselines B1, B2, B3? Why wasn't the much easier and more powerful baseline of all pairwise distances used? The distribution of all pairwise distances between m given points is computable in time O(m^2), Lipschitz continuous under perturbations and was proved to be enough for reconstructing any generic Euclidean point cloud by Boutin and Kemper in Adv. Appl. Math. (2004). >a number of TDA works have been published every year at NeurIPS since 2019 The last response contained even more citations without referring to specific results in these papers, though the request was to provide exact claims or page numbers. Has any of these papers compared persistent homology with the distribution of pairwise distances? At the same time, when another reference [Curry, Mukherjee, Turner...] was questioned, the authors "mentioned this paper as one particular example of a difficult practical problem that can be addressed using multiple parameters/directions" without even acknowledging the fact that this problem was solved not later than in 2004 by a much simpler invariant. >Efficacy is not only about theoretical results but also about practical performances The practical performance on a specific dataset is only an example, not a guarantee for other data beyond training sets. Here is a practical illustration. The prediction that any odd integer (greater than 2) is prime (has no divisors greater than 1) works well for 3,5,7, not 9 (an experimental error), 11, 13, hence achieving the accuracy of 5/6, more than 80%. One can easily improve the accuracy by forbidding multiples of 3 (greater than 3). Then the first counter-example will be 25=5*5 (or 35=5*7 if perfect squares are also excluded as obvious non-primes). One can easily continue forbidding multiples of 5, 7, and so on, making the accuracy nearly 100% on any finite data. Should we use such an algorithm for detecting primes in cryptography-based algorithms for financial transactions in the real world? No, because the infinite set of primes will always provide counter-examples. The modern world exists due to mathematically proved results, not due to unjustified perfomances. Examples prove nothing because (sometimes infinitely) many counter-examples can still exist.

Reviewer cn3Z2023-08-14

Thank you for the clarifications. Some final comments: - Thanks for running the experiments for the filtrations considered in the literature. In the final version of the paper, I suggest to include both these filtrations, as well as your original choice, since I assume that there is a reason you opted for those. In case you include at least a brief discussion on the choice of filtrations and some insights on how they influence the results, and as suggested, I will increase my rating of the paper. - Indeed, you understood my comment about the naming of definitions and theoretical results, I think it helps the readability, but this is a matter of style so I leave the final decision to you.

Authorsrebuttal2023-08-16

Answer to reviewer cn3Z

Thank you for the suggestions, which we will follow. We definitely agree with you that using the exact same filtrations is the way to go for a fair comparison and these are the results we will present to make the point that, in these applications, our vectorizations lead to improved performance compared to previous methods. The set of results that appears in our original submission will also be included (and they will be rerun for the convolution vectorization due to the implementation improvements mentioned in our previous response to you). Here we will include a discussion comparing the different choices, saying in particular that the performance gain could be attributed to the better stability properties of Rips, in the case of the UCR data, and to the larger number of parameters, in the case of the graph data. Specifically, we will include the two sets of experiments (improved original + rebuttal) in the paper, as well as a discussion like the following about how the choices influence the results (which in particular contains the motivation for the original choice of filtrations). "Note that for the UCR data, previous work in the literature used bifiltrations obtained with Alpha and DTM. In addition to these, in this article we also run experiments with (a) Rips instead of Alpha because Rips scales better with the embedding dimension of the point cloud (and thus allows for better generalization of the application of our method to point clouds with outliers), and (b) with KDE instead of DTM because KDE behaves similarly to DTM while being easier to fine tune as it is more standard and has been more studied theoretically. Note also that for the graph data, we also decided to experiment with using more than two parameters since our methods apply directly in this case, in contrast to methods from the literature (such as multiparameter persistence images and GRIL)." We will be happy to discuss any further questions or comments.

Program Chairsdecision2023-09-21

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC