Persistent Homology for High-dimensional Data Based on Spectral Methods

Dear reviewer QsUc,
many thanks for your review. We are happy that you consider the problem we tackle relevant and our experimental section well-written. We will address your concerns in the following.

Hole detection score:
Our hole detection score $s_m = (p_m -p_{m+1})/p_m$ captures the size of the gap after the $m$-th most persistent feature. A clear gap in a persistence diagram is an indication that the features above the gap are important, while the ones below the gap are likely noise. If we know that a dataset has $m$ holes, it is therefore reasonable to require the gap after the $m$-th most persistent feature to be large. This is what our metric measures.

For each dataset in our experiments the value of $m$ simply corresponds to the ground-truth number of holes in each dimension. For instance, the interlinked circles have $m=2$ 1D holes (i.e. two loops), while the sphere has $m=1$ 2D hole (i.e. one void). Note that we only use datasets with known ground-truth throughout the paper.

We call our metric hole detection score, when the dimensionality of the hole is not specified. When speaking of loop detection score, we mean that we apply the metric to 1D holes, i.e., loops.

The area chair (AC) suggested an alternative metric based on the widest gap in the persistence diagram, rather than the gap after the $m$-th most persistent feature. We discuss it in the reply to the AC's comment, see also rebuttal figure R1. If you have another suggestion for a metric, we would be happy to try it.

During the rebuttal, we were able to prove continuity properties of our hole detection score, see general comment. Continuity is clearly a desirable property for a metric.

Intuition for the success of spectral methods:
The key idea is that spectral methods aggregate information over all edges in the graph. This makes them focus on dense connections and robust against single stray edges possibly formed due to the high-dimensional noise. They can therefore be viewed as a denoising technique. In contrast, the geodesic distance is brittle as it can change drastically in the presence of a single short-cut edge. See lines 153-159 in the paper for more details.

As an additional illustration, we included rebuttal figure R3. It contrasts the brittle behavior of the geodesic distance in the presence of artificially added noise edges with the robust behavior of effective resistance in a 2D toy setting. We will add this figure to the revised version of the manuscript. For more intuition, we visualized all distances in Figures S6, S7 in the appendix.

Analysis of representatives:
Indeed, the interpretation of representatives is difficult, as we acknowledged in lines 319-322. We only flagged results as dubious when the representatives of the $m$ most persistent features did not at all align with additional metadata describing the topology of the single-cell datasets (Figure S10). Here, $m$ is the number of ground-truth loops in the dataset. Since $m=1$ for all our scRNAseq datasets apart from the Malaria, there is no possibility of non-trivial linear combinations. The Malaria dataset has a "figure 8" shape, with two loops. We took care of linear combinations and considered both the case where the representatives followed the two small loops and the case where one representative followed the outer loop and the other one inner loop as correct. We did not post-process the representatives.

Limitations:
We have extended the limitations section, following reviewer aHMb's and the AC's suggestion, see the general comment. Inspired by your remark, we also added that our work is limited to validation of topology detection methods, and that topology inference on datasets without ground-truth remains our future work.

Dear reviewer C1nu,
we thank you for your review and appreciate that you find the problem we tackle relevant, our experimental setup diverse, and the paper well-written. We will address your concerns in the following.

W1 & Q3: Theoretical results on spectral methods for persistent homology:
The lack of a theoretical guarantee on the performance of spectral methods with persistent homology in high dimensionality is a limitation of our work and likely difficult to address. For this reason, we focused on an extensive empirical validation. We will state this more clearly in a revised Limitations section (see general comment), and plan to address it in future work taking inspiration from the stability results in [10, 36, 66] and, more generally, spectral perturbation theory. The key steps will be that highly persistent loops are a low-frequency feature of a (graph representing a) point cloud and that diffusion distances and effective resistance are denoising / low-pass filters [18, Szlam et al. (2008), Ramakrishna et al. (2020)].

Q1: Performance of UMAP and t-SNE:
Computing the topology of a high-dimensional dataset in a 2D t-SNE or UMAP plot can indeed be very effective (for loops), which we acknowledged, e.g., in lines 300-301 and 325-326. Nevertheless, across the large set of our experiments, diffusion distance and effective resistance outperformed UMAP and t-SNE.

We summarized our reasons for not endorsing UMAP or t-SNE more strongly in the Discussion (lines 326-330). Of particular importance is the choice of the embedding dimension. Clearly, the embedding dimension limits the dimension of topological features that can be found. t-SNE and UMAP are primarily visualization methods, and are mostly used for 2D embeddings, making it impossible to detect any voids. In contrast, using diffusion distances and effective resistance in some sense performs an implicit, data-dependent, soft choice of the embedding dimension (Section 6), and directly arrives at a denoised distance matrix, without intermediate low-dimensional embedding. We devoted Appendix L to exploring the performance of UMAP with higher embedding dimension, where we found it to struggle with the surface of the 3D toy datasets and the void detection of the torus (Fig S14 b, c). Both t-SNE and UMAP sometimes fail for topology detection even in the noiseless setting (Figs. S14 a, S18).

More generally, t-SNE and UMAP have been severely criticized in recent literature, especially in computational biology, e.g., by Chari and Pachter [11] and Wang et al. [74], because they can strongly distort the data (see also the AC's comment about this). In fact, Wang et al. explicitly recommend persistent homology instead of UMAP or t-SNE embeddings for single-cell data analysis. In this work, we wanted to offer alternatives to t-SNE and UMAP, to separate "visualization" from "topological analysis".

Q2: Failure of diffusion distances on the torus:

First, we would like to emphasize that effective resistance performs on par with the Euclidean distance on the torus. Second, prompted by your question, we investigated the failure of diffusion distances and found that with $t=8, 64$ they failed to find the smaller loop of the torus with high persistence. This was because the eigenvectors that encode this loop contribute little to the distance for $t=8, 64$ (Section 6). We ran an additional experiment with $t=2$, so that these eigenvectors contribute more. Now, diffusion distances performed on par with the effective resistance. This aligns with our recommendation of effective resistance over diffusion distances because it does not have the hyperparameter $t$ (lines 315-317).

Third, we described in lines 257-258 that diffusion distances with $t=8, 64$ fail on the torus due to a sampling issue. On a more densely sampled torus both the effective resistance and the diffusion distance clearly outperform the competitors (Fig. S27). The reason is that the eigenvalues of the eigenvectors that encode the small loop are now more similar to those encoding the large loop, so the diffusion distance with $t=8$ does not overly decay them.

Q4: Potential application domains:
High-dimensional data and thus application areas for our improved topology detection pipeline are becoming ubiquitous. Within biology, we see possible applications for our method in other single-cell omics modalities, population genomics, or neural activity data [26, 34]. Beyond biology, we believe that our approach can improve the topological analysis of artificial neural network activations [52], and in general be used to detect topology of any high-dimensional data, e.g. in the climate sciences, in astronomical measurements, or wearable sensor data. We are happy to add this outlook to the discussion section.

Q5: Multiparameter persistence:
Multiparameter persistence is an interesting method and might offer benefits in the high-dimensional setting. It has been employed to spatial transcriptomics data by Benjamin, Katherine, et al. (2022).

However, its output is not as readily interpretable as the persistence diagrams in single-parameter persistent homology, which is why we limited out study to this more established method.

References:

Szlam, Maggioni, & Coifman (2008). Regularization on graphs with function-adapted diffusion processes.

Ramakrishna, Wai & Scaglione. (2020). A user guide to low-pass graph signal processing and its applications: Tools and applications.

Benjamin, Katherine, et al. (2022) Multiscale topology classifies and quantifies cell types in subcellular spatial transcriptomics.

Dear reviewer aHMb,

thank you for your review! We are pleased that you find our experimental setup "thorough and detailed". As the main weaknesses, you listed our discussion of Hiraoka et al. (2024) and our discussion of limitations. We will address these in detail below as well your other concerns.

Relation with Hiraoka et al. (2024):
As you mention, this relevant paper is "very recent" and it did not influence our work in any way. In fact, it appeared on arXiv about one month before the NeurIPS deadline (on 28/04/2024) so that the NeurIPS rule on contemporaneous work applies:

Contemporaneous Work: For the purpose of the reviewing process, papers that appeared online within two months of a submission will generally be considered "contemporaneous" in the sense that the submission will not be rejected on the basis of the comparison to contemporaneous work. [...]

That said, we are happy to discuss Hiraoka et al. (2024) in more detail. First, their treatment of the curse of dimensionality of persistent homology is mostly theoretical, while ours has an empirical focus. The two works are thus complementary to each other.

Second, our own theoretical treatment in Appendix B aligns with Hiraoka et al. chapter 3 in the key steps: High-dimensional noise leads to distance concentration (our Prop. B.4, their Prop 3.1) which makes persistent homology uninformative (our Cor. B.7, summarized in Thm 3.19 in Hiraoka et al.). Hiraoka et al.'s theoretical treatment is more general, covering non-Gaussian noise, the Čech complex, and describing the effects on persistent homology in more detail.

Third, practically, Hiraoka et al. propose normalized PCA. However, this approach assumes the true dimensionality of the data to be known, which is not realistic in real-world applications. Moreover, the strongest property of normalized PCA that Hiraoka et al. show is that the Hausdorff distance between the persistence diagram of the unperturbed data and that of the normalized PCA is eventually bounded in probability (Thm 4.20). While achieving this formal statement is impressive, it does not guarantee that any information of the original persistence diagram is preserved. In fact, the Hausdorff distance between any two non-empty, deterministic persistence diagrams is eventually bounded in probability by simply using their Hausdorff distance as bound.

We ran experiments with both the normalized and non-normalized PCA on the 1D toy datasets, see rebuttal figure R2. We observed that knowing the dimensionality of the data is crucial, as too few PCs can miss important structure (Fig R2 f,j), while an excessive amount of PCs is also detrimental, and that neither the PCA version outperforms the effective resistance.

Together, this shows that normalized PCA does not "solve" the curse of dimensionality for persistent homology. Hiraoka et al. seem to acknowledge this: "[...] normalized PCA still can not eliminate the curse of dimensionality on persistence diagrams completely" (p. 41).

Our extensive empirical investigation offers crucial complementary insights to Hiraoka et al's theoretical work. First, it provides clear guidance for practitioners. Second, it shows empirically that the curse of dimensionality appears not only for Euclidean distances, but also for many derived distances, not covered by Hiraoka et al.. Third, Hiraoka et al.'s negative results are asymptotic statements. Our experiments provide concrete insight on how early the curse of dimensionality sets in: in tens of dimensions, see Figs. 7, 9.

We will add a condensed version of this discussion and the PCA results in the revised manuscript.

Limitation section:
Thank you for pushing for more transparency regarding limitations. However, we did discuss limitations of our method in the main paper. In particular, we acknowledged that

• our methods need hyperparameter choices (line 214),
• spectral methods only outperform the Euclidean distance on a more densely sampled torus (lines 254-256),
• interpreting cycle representatives is difficult (line 321-322),
• persistent homology can fail to distinguish non-isometric point clouds (line 325),
• and has a high run time (lines 334-336).

Nevertheless, we are happy to create a dedicated Limitations subsection in the revision, also mentioning additional limitations. Please see the general comment for its text.

Comparison with Reani & Bobrowski (2023):
Their method for distinguishing topological signal from noise does not fit well into our benchmark (which already compares 13 different methods!). First, they need to resample data, using either the true data distribution or kernel density estimation; none of this is suitable in a high-dimensional exploratory context (see line 52). Second, their approach uses the coupled alpha complex, while our setup deals with the more common Vietoris-Rips complex. Third, our study compares different distances while Reani & Bobrowski pursue the conceptually very different approach of cycle matching. We will include this reference in the revision.

Spectral methods and persistent homology:
In the related work section, we did acknowledge that spectral methods have been applied in the context of persistent homology (lines 56-59), also citing Mémoli et al. [47]'s work on Persistent Laplacians. We are happy to add a reference to the follow-up work of Davies, Wan, and Sanchez-Garcia (2023). However, none of these works either deals with the correction of effective resistance [71,72], crucial for good performance (Fig. S16), or addresses the high-dimensional setting. Pointing out the curse of dimensionality for persistent homology and combatting it with spectral methods is therefore our novel and original contribution.

References:

Davies, Wan, & Sanchez-Garcia(2023). The persistent Laplacian for data science: Evaluating higher-order persistent spectral representations of data.

Dear area chair,
thank you very much for the additional feedback! We are happy you appreciate the rigor of our approach and the theoretical contributions. We respond to your comments below.

Precision:
We will rephrase as

persistent homology [...] can fail to identify the correct loop as a clear outlier in the persistence diagram

Dimensionality reduction:
We fully agree that dimensionality reduction introduces artifacts. We mentioned this for t-SNE and UMAP in line 329 which we will strengthen with the reference to Landweber et al. that you provided. It also applies to the normalized PCA approach from [36] suggested by reviewer aHMb.

Neither effective resistance nor diffusion distance perform dimensionality reduction. Both can be exactly expressed only in $n-1$ dimensions, where $n$ is the number of points. Instead, they should rather be considered denoising methods. Therefore, our recommendations align with your criticism of dimensionality reduction.

Hole detection score:
Stability
Indeed, our hole detection score $s_m = (p_m - p_{m+1}) / p_m$ can be unstable for small $p_m$. While this is mitigated by the numerator also getting small for small $p_m$, we did observe some instability if there are only few points in the diagram. As described in lines 223-226, we handled this by setting $s_m=0$ in case all death-to-birth ratios are small (compare also Figs S19, S21). During the rebuttal, we proved a desirable continuity property for our hole detection score, see general comment.

Some normalization of the gap width is necessary to compare different distances, because their values are on different scales. Our hole detection scores always lies in $[0, 1]$.

Widest gap metric
We use our hole detection score to validate if a method identifies the correct number of ground-truth holes, $m$. It always considers the gap in the persistence diagram that needs to be large so that the correct number of holes appear as outliers. Building a metric based on the widest gap in the persistence diagram is an interesting suggestion. We now implemented and tested the binary metric which is 1 if the number of features above the widest gap equals the number of ground-truth features and 0 otherwise ("widest gap metric").

Note that our metric can be lower than 1 even if the persistence diagram clearly shows the correct number of outliers (e.g. $s_m\approx 0.5$ for $\sigma = 0.2$ in Fig. 3b). The widest gap metric would assign a score of 1 in this case.

On the other hand, the binary nature of the widest gap metric leads to instability in the case of nearly equisized gaps. For instance in Fig. 8d, a small perturbation could make the gap after the most persistent feature the widest, dropping the widest gap metric from 1 to 0. In contrast, our $s_2\approx 0.9$ correctly reflects the two outliers.

The binary nature of the widest gap metric leads to high-variance results even though we increased the number of random seeds to 10 (rebuttal Fig R1). Spectral methods still performed better than Euclidean, Fermat, and DTM distances. The widest gap metric can lead to false positives. E.g. for the Fermat distance and $\sigma=0.3$ in 9 of 10 trials on the circle the widest gap appeared after the first feature. However, all 9 persistence diagrams looked like noise clouds and in 8 cases the most persistent feature's representative was clearly a noise feature. We plot this for one seed in Fig R1 d-e. Conversely, for the effective resistance there was always a clear outlier in the diagram and the representative did follow the ground-truth loop (Fig R1 f-g). Although the Fermat distance failed in this setting and the effective resistance performed great, their widest gap metrics were both very high.

For these reasons, we prefer to stick to our hole detection score. We will add the above discussion including Fig R1 to the appendix. Moreover, we will cite Smith and Kurlin (2021) as additional inspiration for our hole detection score in line 222.

Limitations:
Runtime complexity
Following reviewer aHMb, created a dedicated Limitations section (see general comment). It contains our existing discussion of the high complexity of persistent homology (line 331), adding the cubic complexity $O(n^3)$ in the number of points $n$ of effective resistance.

Isometry invariant
We already mentioned that persistent homology can fail to distinguish non-isometric point clouds (line 324). We will add the references on finer invariants you provided (see general comment). That said, we believe that persistent homology being a coarser invariant is not a grave disadvantage for exploratory data analysis. The topology of a point cloud provides an intuitive, high-level description of the data.

References:
Landweber et al (2016). On fiber diameters of continuous maps.

Smith & Kurlin (2021). Skeletonisation algorithms with theoretical guarantees for unorganised point clouds with high levels of noise.