Persistent Homology for High-dimensional Data Based on Spectral Methods
Authors: Sebastian Damrich
Philipp Berens
Dmitry Kobak
Venue: NeurIPS 2024 poster (2024)
Keywords: persistent homology
spectral methods-sequencing
topology
topological data analysis
curse of dimensionality
effective resistance
diffusion distance
single-cell RNA
Primary area: other
TL;DR: Traditional persistent homology and its standard extensions fail on high-dimensional data, but persistent homology with spectral distances works well.

Abstract: Persistent homology is a popular computational tool for analyzing the topology of point clouds, such as the presence of loops or voids. However, many real-world datasets with low intrinsic dimensionality reside in an ambient space of much higher dimensionality. We show that in this case traditional persistent homology becomes very sensitive to noise and fails to detect the correct topology. The same holds true for existing refinements of persistent homology. As a remedy, we find that spectral distances on the k-nearest-neighbor graph of the data, such as diffusion distance and effective resistance, allow to detect the correct topology even in the presence of high-dimensional noise. Moreover, we derive a novel closed-form formula for effective resistance, and describe its relation to diffusion distances. Finally, we apply these methods to high-dimensional single-cell RNA-sequencing data and show that spectral distances allow robust detection of cell cycle loops.

Persistent Homology for High-dimensional Data Based on Spectral Methods
Sebastian Damrich
Philipp Berens
Dmitry Kobakt$
Hertie Institute for Al in Brain Health, University of Tübingen, Germany
Tübingen Al Center, Germany
IWR, Heidelberg University, Germany (sebastian damricamihhh chh phtpaa...aaiiii...hp.ppppppp berens, dmitry
Abstract
Persistent homology is popular computational tool for analyzing the topology of point clouds, such as the presence of loops or voids. However, many wooldw datasets with low intrinsic dimensionality reside in an ambient space of much higher dimensionality. We show that in this case traditional persistent homology becomes very sensitive to noise and fails to detect the correct topology. The same holds true for existing refinements of persistent homology. As remedy, we find that spectral distances on the d-nearest-neighhor graph of the data, such diffusion distance and effective resistance, allow to detect the correct topology even in the presence of high-ddmensional noise. Moreover, we derive a novel closed-form formula for effective resistance, and describe its relation to diffusion distances. Finally, apply these methods to high- high-dimensional single-cell RNA- -NA-sequeniing data and show that spectral distances allow robust detection of cell cycle loops.
Introduction
Algebraic topology can describe the shape continuous manifold. In particular, can detect manifold has holes, using its so-called homology groups [39]. For example, cup has a single one-dimensional hole, or loop (its handle), whereas a football has single two-dimensional hole, or void (its hollow interior). These global topological properties are often helpful for understanding an object's overall structure. However, real-world datasets are typically given as point clouds, a discrete set of points sampled from an underlying manifold. In this setting, true homologies are trivial, as there one connected component per point and no holes whatsoever; instead, persistent homology can be used to find holes in point clouds and to assign an importance score called persistence to each 25 90)
Holes with high persistence are indicative holes in the underlying manifold. Persistence homology has been successfully applied in machine learning pipelines, for instance for gait recognition (48]
instance segmentation [44), and protein binding [84, as well as for neural network analysis [67
Persistent homology works well for low- oww-dimesioonl data 778 but we find that it has difficulties in high dimensionality. If data points are sampled from a low-dimensional manifold embedded in high-dimenn nigh-dimensional ambient space (manifold hypothesis), then the measurement noise typically affects all ambient dimensions. In this setting, traditional persistent homology is not robust against even low levels of noise. On dataset as simple as circle in TR500 persistent homology based on the Euclidean distance between noisy points can fail to identify the correct loop as clear outlier the persistence diagram (Figure D. The aim of our work is to find alternatives traditional persistent homology that can robustly detect the correct topology despite high-dimensional noise.
We were inspired by visualization methods i-SNE 799 and UMAP (53) that are able to depict the loop the same noisy dataset (Figure Td.e). They approximate the data manifold by the nneghost-neighhr (kNN) graph [76] 70
5 41 56 Therefore, we suggest to use persistent homology with spectral
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Representative loops an 2D PCA
Persistence a= 0.25
Loop delection
1.0
Death
0.8
Loop detection score
0.8
0.4
d
UMAP
I-SNE
Deaf
02-
Euclidean
E Effactive resistance
Effective
resistance
0.0 0.0
Bithh
0.1
0.2
025 0.3
Noise std
Figure I: a. 2D PCA of a noisy circle (o = 0.25, radius 1) in R Overlaid are representative cycles of the most persistent loops. b. Persistence diagrams using Euclidean distance and the effective resistance. Loop detection scores of persistent homology using effective resistance and Euclidean distance. d, e. UMAP and t-SNE embeddings of the same data, showing the loop structure in 2D.
distances on this kNN graph, such as the effective resistance 24 and the diffusion distance 120 Effective resistance successfully identified the correct loop in the above toy example (Figure We also found spectral distances to outperform other distances in detecting the correct topology of several synthetic datasets as well as finding the cell eycles in single-cell RNA-sequencing data.
Our contributions are:
1. analysis of the failure modes of persistent homology for noisy high-dimensional data;
2. a closed-form expression for effective resistance, explaining its relation to diffusion distances;
3. a synthetic benchmark, with spectral distances outperforming state-of-the-ar alternatives;
4. an application to a range of single-cell RNA RNA-sequencing datasets with ground-truth cycles.
Our code is utttpps//gghhbb.cco//eeeaaaa//// http:////oooooaaaaaaaa/aa/e//e/r
2 Related work
Persistent homology has long been known to be sensitive to outliers [15 and several extensions have been proposed to make more robust. One recurring idea is to replace the Euclidean distance with different distance matrix, before running persistent homology. Bendich et al. [6] suggested to use diffusion distances (0),, but their empirical validation was limited a single dataset 2D. Anai et al.
2 suggested to use the distance-to to-tttoommaeeee (DTM) [15] and Fernández et al. [26 proposed to
Fermat distances [34]. Vishwanath et al. (80] introduced persistent homology based on robust kernel density estimation, an approach that itself becomes challenging in high dimensionality. All of these works focused on oin-sineni datasets (<10D, mostly 2D or 3D), while our work specifically addresses the challenges of persistent homology in high dimensionality.
The concurrent work of Hiraoka 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. Hiraoka al.]s theoretical description of the curse of dimensionality is similar to ours (Appendix B) in that it analyses how distance concentration with high-dimensional noise impairs persistent homology, but is more general. Practically, Hiraoka al. propose normalized PCA mitigate the curse of dimensionality. However, this approach assumes the true dimensionality of the data to known, which is not realistic in real-world applications, and performs worse than suggestions (Appendix C).
is the most relevant related work. Their treatment
Below, we recommend using effective resistance and diffusion distances for persistent homology in high-dimensional spaces. Both of these distances, as well as the shortest path distance, have been used combination with persistent homology to analyze the topology of graph data [62 37 77
11 55 23
Shortest paths the &NN graph were also used by Naitzat et al. [60] and Fernández
al. 26 Motivated by the performance of UMAP (53) for dimensionality reduction, Gardner et al.
31 and Hermansen et al. [40] used UMAP affinities to define distances for persistent homology.

---

Effective resistance is a well-established graph distance (24 29) A correction, more appropriate for large graphs, was suggested by von Luxburg et [8] 83 When speaking of effective resistance, we mean this corrected version, if not otherwise stated. It has not yet been combined with persistent ho-
mology. Conceptually similar diffusion distances (20] have been used in single-cell RNA-sequencing
data analysis, for dimensionality reduction [56], trajectory inference [35]. feature extraction [16], and
hierarchical clustering, similar to OD persistent homology 99 46].
Persistent homology has been applied to single-cell RNA-sequencing data, but only the concurrent work of flores-Bautista and Thomson 277 applies directly the high high-dimensional data. Wang et al. 885 used a Witness complex on PCA of the data. Other works applied persistent homology to derived graph. e.g., a gene regulator network [52] or a Mapper graph [73] 688. In other biological contexts, persistent homology has also been applied to a low- -owddimensional representation of the data: 3D projection of cytometry data [58], 6D PCA of hippocampal spiking data [31), and 31) PHATE embedding of calcium signaling [57]. Several recent applications of persistent homology only computed OD features (i.e. clusters) 37 45 61 which amounts to doing single linkage clustering (33) Here we only investigate the detection of higher-dimensee dimensoai (ID and 2D) holes with persistent homology. The dimensionality of the data itself, however, is typically much higher.
Background: persistent homology
Persistent homology computes topo- logical invariants of a space at dif- ferent scales. For point clouds, the different scales are typically given by growing ball around each point (Fig- ureZhh, and letting the radius r grow from 0 to infinity. For each value of T, homology groups of the union of all balls are computed to find the holes, and holes that persist for longer time periods are considered more promi- nent. At T R 0, there are no holes as the balls are non-over overlapppi,, while at T - Do there are no holes as all the balls merge together.
Deeth
Score Pl
Pi-P2
T2
Ta
Birth
Figure 2: a. Persistent homology applied to noisy circle (n = 10) in 2D tracks appearing and disappearing holes as balls grow around each datapoint. Dotted lines show the graph edges that lead to the birth / death of two loops (Section 3 b. The corresponding persistence diagram with two detected ID holes (loops). Our hole detection score measures the gap in persistence between the first and the second detected holes (Section)
To keep the computation tractable, in- stead of the union of growing balls. persistent homology operates on a so-called filtered simplicial complex (Figure 2b) A simplicial complex is hypergraph containing points as nodes, edges between nodes, triangles bounded by edges, and so forth. These building blocks are called simplices. At each time т, the complex encodes all intersections between the balls and suffices to find the holes. The complexes at smaller values are nested within the complexes at larger T values, and together form filtered simplicial complex, with being the filtration time. In this work, we only use the Vietoris- Ripss complex, which includes an r-simplex (vo, vi...... vn) at filtration time r if the distances between all pairs U/ are at most T. Therefore, to build a Vietoris-Rips complex, it suffices to provide pairwise distances between all pairs of points. We compute persistent homology via the ripser package 4 to which we pass distance matrix.
Persistent homology consists of a set of holes for each dimension. We limit ourselves to loops and voids. Each hole has associated birth and death times (T,, ra), i.e., the first and last filtration value 7 at which that hole exists. Their difference p- Td Tr is called the persistence of the hole and quantifies its prominence. The birth and death times can be visualized as scatter plot (Figure (2)), known as the persistence diagram. Points far from the diagonal have high persistence. This process illustrated Figure? 2 for a noisy sample of n = 10 points from circle 5 C R22, At TI, a small spurious loop is formed thanks to the inclusion of the dotted edge, but it dies soon afterwards. The ground-truth loop is formed at 72 and dies at 73, once the hole is completely filled by triangles. Both loops (one-dime -imeninnnnio holes) found in this dataset are shown in the persistence diagram.
3

---

Euclidean d' = 2
b d'= 20
Euclidean
Euclidean d'= 50
Eudidean
Resist.
Diffusion
dma
Death
0.25
a- 0.2
0.1
MDS 50, a 025)
Birth
Birth
Birth
Figure 3: a-c. Persistence diagrams of noisy circle in different ambient dimensionality and with different amount of noise. Ideally, there should be one feature (point) with high persistence, corresponding the circle. But for high noise and dimensionality that feature vanishes into the noise cloud near the diagonal. d-f. f. Multidimensional scaling of Fuclidean, effective resistance, and diffusion distances for noisy circle in 1550 Color indicates the distance to the highlighted point.
4 The curse of dimensionality for persistent homology
While persistent homology is robust to small changes in point positions [19], the curse of dimen- sionality can still severely hurt its performance. To illustrate, consider the same toy setting as in Figure we sample points from 5 C IRd, and add Gaussian noise of standard deviation a to each ambient coordinate. When d 2, higher noise does not affect the birth times but leads to lower death times (Figure 33, because some points get distorted to the middle of the circle and the hole fills up earlier т. When we increase the ambient dimensionality
20, higher noise leads to later birth times (Figure (b)) because in higher dimensionality distances get dominated by the noise dimensions rather than by the circular structure. Indeed, in Corollary B.5 we prove that for any two points 24, Tr; E R and two isotropic, multivariate normal noise vectors E1, ~ No, o oLIa) the ratio - | + (I2 + #2) + in probability as d + co. Finally, for d 50 both the birth and the death times increase with a (Figure Be. Corollary B.7) and the ground-trun hole disappears the cloud of spurious holes. Applying MDS the Euclidean distances obtained with d 50 and 0.25 yields 2D layout with almost no visible hole, because all distances have become similar (Figure Bt). See the concurrent work of Hiraoka al. 42 for a more detailed treatment.
Therefore, the failure modes of persistent homology differ between low- and high-dimensional spaces. While in low dimensions, persistent homology susceptible outlier points in the middle of the circle, in high dimensions, there are no points in the middle of the circle; instead, all distances become too similar, hiding the true loops. See Appendix N for more details on the effect of outliers.
Spectral distances are more robust
Many modern manifold learning and dimensionality reduction methods rely the l- d-ncarcst-neighhoo (kNN) graph of the data. This works well because, although distances become increasingly similar in high-dimensional spaces, nearest neighbors still carry information about the data manifold. To make persistent homology overcome high-dimensional noise, we therefore suggest to rely on the symmetric ANN graph, which contains edge ij if node i is among the k nearest neighbors of j or vice versa. A natural choice is to use its geodesics, but, as we show below, this does not work well, likely because single graph edge across circle destroy the corresponding feature too early. Instead, we propose to use spectral methods, such as the effective resistance or diffusion distance. Both methods rely on random walks and thus incorporate information from all edges.
For a connected graph G with n nodes, c.g., the symmetric kNN graph, let A be its symmetric, adjacency matrix with elements d;j 1 if edge ij exits in G and agj degree matrix D is defined by = diag (d where d; = ΣØ Oiy are the node degrees. We define x vol(G) Σi= d, Let Haj be the hitting time from node i to j. i.e., the average number of edges it takes random walker, that starts at node randomly moving along edges, to reach node j. The naive effective resistance defined as d: (Hi, + H)j:/vol((r (o). This version is known be unsuitable for large graphs (Figure $20) because it reduces to d: ~ 1/d, 1/d; Luxburg et al. 81'ss corrected version
otherwise. The
8 Therefore, used von
Cff 1/ds 1/d, + 2aug/(ddd) an/d azj/d3.
(I)

---

Geodesic
Effeclive resistance
0000
dmax
Figure 4: Robustness of effective resistance. We sampled n = 1 000 points from a noisy circle in 2D with Gaussian noise of standard deviation 0.1, constructed the unweighted symmetric 15-NN graph, and optionally added 10 random edges (thick lines). Node colors indicate the graph distance from the fat black dot. a. The geodesic distance severely affected by the random edges. b. The effective resistance distance is robust to them.
Diffusion distances also rely random walks. The random walk transition matrix is given by P D-1A. Then 1, the i-th row pt, holds the probability distribution over nodes after steps of random walker starting at node i. The diffusion distance is then defined as
dyy(t) / (ol Pf,)D=
(2)
There are many possible random walks between nodes and j if they both reside in the same densely connected region of the graph, while it is unlikely for random walker to cross between sparsely connected regions. As result, both effective resistance and diffusion distance are small between parts of the graph that are densely connected and are robust against single stray edges (Figure 4 This makes spectral distances on the kNN graph the ideal input to persistent homology for detecting the topology of data in high-dimensional spaces. Indeed, the MDS embedding of the effective resistance and the diffusion distance the circle in ambient 1850 both clearly show the circular structure (Figure Be.f).
6 Relation between spectral distances
We show in Section 7 that spectral methods excel input distances to persistent homology for high-dimensional data. But first, we explain the relationships between them. Laplacian Eigenmaps distance and diffusion distance can written as Euclidean distances in data representations given by appropriately scaled eigenvectors of the graph Laplacian. In this section, we derive similar closed-form formula for effective resistance and show that effective resistance aggregates all but the most local diffusion distances.
Let A D Dー AD- and L Laplacian matrix. We denote the eigenvectors of I by u1,...s and their eigenvalues by M,
A be the symmetrically normalized adjacency and
Un in increasing order. For a connected graph, ln 0 and (1, 1) Vv)
The d-dimensional Laplacian Eigenmaps embedding is given by the first nontrivial eigenvectors: 1 (d = (d) e (d)il, where e! _.F (12 "(81)))))
The diffusion distance after t diffusion steps is given by 20
((1 (2) 12) u
(1 Mn) Unns)
ci (t)
vvll(G) (t) (ftf (t) where elif((t)
(t)
Vd
The original uncorrected version of effective resistance is given by [1 Jell || 1 where 2. (w2,s/
/p /dg.
(5)
In Appendix we prove that the corrected effective resistance can also written in this form: Proposition 6.1. The corrected effective resislance distance can be computed by
Est llestt egft 112, where eqfh
(1
H2
U2 is
1 Pnx unit
/Va..
(6)
u22
5

---

8
Spectra
Decay
o= 0.1
Ef. resistance
Rolative decay
0.8
Ef. res, nalve
Egenvakis
10"
0.8
Diflusion 64
10
2
0.0
0.4
Lap Big d
0.1
0.2
DPT
10"
o=
0.25
10
100
1000
0.0
0.5
1.0
10
100
1000
10
100 1000
10 100 1000
Eigenvalue index
Eigenvalue
Eigenieector index
Eigenvector index
Eigenvector index
Figure 5: Eigenvalue spectra of the kNN graph Laplacian for the noisy circle in ambient 1R500 for noise levels o {0.0, 0.1, 0.25). b. Decay of eigenvector contribution based on the eigenvalue for effective resistance, diffusion distances and DPT. c-e. Relative contribution of each eigenvector for eff. resistance, diffusion distance, Laplacian Eigenmaps, and DPT for various noise levels (Section
It has been known 154 that the uncorrected effective resistance can be written in terms of diffusion distances as d:h Et=o ( (t/2)² 22)2/voll /Vo) see Proposition G.1 Here, based on Proposition 6.1
we derive similar result for the corrected effective resistance (proof in Appendix G
Corollary 6.2. IfG is connected and not bipartite, we have
d
d
and hence
d:
deft
d (0) (0) + d + (1/2))) /vo(GG) (7)
In words, the corrected effective resistance combines all diffusion distances, save for those with the shortest diffusion time. These most local diffusion distances form exactly the correction from naive corrected effective resistance. While the effective resistance is squared Euclidean distance, omitting the square amounts to taking the square root of all birth and death times, maintaining the loop detection performance of effective resistance (Figure $20). Therefore, the main difference between the spectral methods is in to how they decay eigenvectors based on the corresponding eigenvalues.
The naive effective resistance decays the eigenvectors with 1/vP5, which is much slower than diffusion distances' (1- p4) for i E [8, 64]. Corrected effective resistance shows intermediate behavior (Figure 5b). When represented as a sum over diffusion distances, it contains all diffusion distances with t 1, making decay slower than diffusion distances with t 8 or 64, but does not contain the non-decaying little for S IR50 in the absence of noise, when the first eigenvalues are much smaller than the rest and dominate the embedding (Figure 51,c) but becomes important as the noise and consequently the low eigenvalues increase (Figure dde)). As the noise increases, the decay for diffusion distances gets closer to a step function preserving only the first two non-constant eigenvectors, sufficient for the cireular structure. In contrast, Laplacian Eigenmaps needs the number of components input (Figure 5 [
term, so it decays faster than its naive version. The correction matters
7 Spectral distances find holes in high-dimensions spaces
nigh-ddimessionl data is ubiquitous, but traditional persistent homology can fail detect its topology. Here, we benchmark the performance of various distances as input to persistent homology.
Distance measures We examined twelve distances as input persistent homology, beyond the Euclidean distance. Full definitions are given in Appendix ! First, there are some state-of-ther thetherrrt approaches for persistent homology in the presence noise and outliers. Fermat distances (26 aim to exaggerate large over small distances to incorporate the density of the data. (DTM) ( aims for outlier robustness by combining the Euclidean distance with the distances from each point to its l nearest neighbors, which are high for outliers. Similarly, the core distance used in HDBSCAN algorithm [0. 21 raises each Euclidean distance least to the distance between
Difffusion pseudotime (DPT) 36 has very similar expression as corrected effective resistance, using the scaling (1 - pt//Ms. /a. see Appendix H This means that DPT decays eigenvalues faster than both versions of effective resistance (Figure 5). We prove analogous statement to Corollary 6.2 for DPT in Proposition H.I

---

Loop dctoction sconee
0.5
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
Noise sld
Noise std d
Noise std
Noss sid dr
Fermat p =
Geodesics = 100
UMAP K= 15
Effective resistance k
100
DTM 4,
UMAP greph k 100
I-SNE p 30
Diffusion - 15, c-
1-SNE graph p 30
Euclidean
Lap. Eig. 15,
Figure 6: Loop detection score for persistent homology with various distances on noisy circle in IRS", The best hyperparameter setting for each distance is shown. Methods are grouped into panels for visual clarity. Recommended methods in bold.
incident points and their k-th nearest neighbors. We evaluate these methods here with respect to Gaussian noise in nigh-dimensional ambient space, a different noise model than the one for which these methods were designed. Second, we consider some non-spectral graph distances. The geodesic distance on the &NN graph was popularized by Isomap [76] and used for persistent homology by Naitzat et al. 60). Following Gardner et 31 we used distances based on UMAP affinities, and also experimented with 1-SNE affinities. Third, we computed (-SNE and UMAP embeddings and used distances the 2D embedding space. Finally, we explored methods using the spectral decomposition of the ANN graph Laplacian, see Section effective resistance, diffusion distance, and the distance in Laplacian Eigenmaps' embedding space.
All methods come with hyperparameters. We report the results for the best hyperparameter setting on each dataset (Appendix K) but found spectral methods be robust these choices (Appendix D
Performance score The output of persistent homology is a persistence diagram showing birth and death times for all detected holes. It may be difficult to decide whether this procedure has actually detected hole in the data, or not. Ideally, for dataset with m ground-truth holes, persistence diagram should have m points with high persistence while all other points should have low persistence and lie close to the diagonal. Therefore, for m ground ground-truth features, our hole detection score 8m E [0, 1] is the relative gap between the persistences Pm and Pm++1 of the m-th and (m + 1)-th most persistent features: 8m = (pm 1m++1//mm This corresponds to the visual gap between them in the persistence diagram (Figure 2b). Rieck and Leitte [66] well Smith and Kurlin 744 used similar quantities to find important features. We prove a continuity property of sm in Appendix and consider alternative scores in Appendix
In addition, we set 8m if features in the persistence diagram have very low death-to-birth ratios Ta/TB < 1.25. This handles situations with very few detected holes that die very quickly after being born, which otherwise can have spuriously high 8m values. This was done everywhere apart from the qualitative Figures] 1 and in Figure $25
We call this heuristic thresholding.
Note that the number of ground-truth topological features was used only for evaluation. We report the mean over three random seeds; shading and error bars indicate the standard deviation.
7.1 Synthetic benchmark
Benchmark setup In our synthetic benchmark, we evaluated the performance of various distance measures in conjunction with persistent homology on five manifolds: circle, pair of linked circles, the eyeglasses dataset (a circle squeezed nearly to figure eight) (26), the sphere, and the torus. The radii of the circles, the sphere, and the torus' tube were set to the bottleneck of the eyeglasses was 0.7, and the torus' tube followed circle of radius 2. In each case, we uniformly sampled n = 1 000 points from the manifold, mapped them isometrically to Rd for d [2, 50). and then added isotropic Gaussian noise sampled from (0, o²I,) for E [0. 0.35). More details can be found in Appendix(] For each resulting dataset, we computed persistent homology for loops and, for the sphere and the torus, also for voids. We never computed holes of dimension 3 or higher.

---

Circle (1 loop)
Eyeglasses (1 loop)
Sphere (0 loops)
Torus (2 loops)
1.0
Detection score
0.1
0.3
0.00
0.05
0.10
0.2
0.1
0.2
Linked circles loops)
9
Sphere (1 vold)
h
Torus (1 vold)
Datectio score
1.0
Euclidean
Farmat
0.5
DTM
resist.
Diffusion
0.0
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
Noise sid
Noise std
Noise std
Figure 7: Loop detection score for selected methods synthetic datasets in ambient IR More experimental results can be found in Figures S23
S33
Recommended methods in bold.
Results on synthetic data On the circle dataset in 1250 persistent homology with all distance metrics found the correct hole when the noise level was very low (Figure 6 However, as the amount of noise increased, the performance of Euclidean distance quickly deteriorated, reaching at 0.2. Most other distances outperformed the Euclidean distance, at least in the low noise regime. Fermat distance did not have any effect, and neither did DTM distance, which collapsed at 0.15 due our thresholding (Figure [a). Geodesics, UMAP/-SNE graph, and core distance offered only a modest improvement over Euclidean (Figure(op) highlighting that many ANN-graph-based distances cannot handle high-dimensional noise. In contrast, embedding-bai based distances performed very well on the circle (Figure 66). but have obvious limitations: for example, a 2D embedding cannot possibly have void. UMAP with higher embedding dimension struggled with loop detection on surfaces and the torus' void (Appendix O). Finally, all spectral methods (effective resistance, diffusion, and Laplacian Eigenmaps) showed similarly excellent performance (Figure 6t).
In line with these results, spectral methods outperformed other methods across most synthetic datasets in 5.50 (Figure 7 DTM collapsed earlier than Euclidean but detected loops on the torus for low noise levels best by small margin. Fermat distance typically had little effect and provided a benefit over Euclidean only on the eyeglasses and the sphere. Spectral distances outperformed all other methods on all datasets apart from the torus, where effective resistance was on par with Euclidean but diffusion performed poorly. On more densely sampled torus, all methods performed better and the spectral methods again outperformed the others (Figure (3I). On all other datasets diffusion distance slightly outperformed effective resistance for large a. Reassuringly, all methods passed the negative control and did not find any persistent loops on the sphere (
As discussed in Section 4 persistent homology with Euclidean distances deteriorates with increasing ambient dimensionality. Using the circle data in Rd, we found that if the noise level was fixed at
0.25, persistent loop was found using Euclidean distances for d 2 30 (Figure 8). In the same setting, DTM deteriorated even more quickly than Euclidean distances. In contrast, effective resistance and diffusion distance were robust against both the high noise level and the large ambient dimension (Figure (h,c-e), See Figure for an extended analysis.
Loap delecaion score
1.0
0.25
Eudidean
DTM
Eff. resist
Difuusion
1.0
Loop deloction score
Eudlddean
0.85
0.5
DTM k 4, 2. -
100
Noise
0,25
-0.5
Diffusion
0.0
2 10 30
k
0.35
2 1020 90 50
2 10 20 3040
1020 so 4b
2 1020 30 40
Ambient dimension
Ambient dim.
Ambient dim.
Ambient dim.
Ambient dim.
Figure 8: a. Loop detection score of various methods on noisy circle depending on the ambient dimensionality. Noise 0.25. b-e. Heat maps for a E [0, 0.35) and d E [2, 50].
8

---

7.2 Detecting cycles in single-cell data
We applied our methods to six single-cell RNA-sequeniing datasets: Malaria [33]. Neurosphere and Hippocampus from 89]. HeLa2 [72]. Neural IPCs [8] and Pancreas [3] Single-cell RNA- sequencing data consists of expression levels for thousands of genes in individual cells, so the data high-dimensional and notoriously noisy. Importantly. all selected datasets are known to contain circular structures, usually corresponding to the cell division cycle during which gene expression levels cyclically change. As a result, we know how many loops to expect in each dataset and can therefore use them as real-world benchmark of various distances for persistent homology. In each case, we followed preprocessing pipelines from prior publications leading to representations with 10 to 156 dimensions. We downsampled datasets with more than 4 000 cells to 000 (Appendix J..
The Malaria dataset is expected to con- tain two cycles: the parasite replica- tion cycle in red blood cells, and the parasite transmission cycle between human and mosquito hosts. Follow- ing Howick et al. 43), we based all computations for this dataset (and all derived distances) on the correlation distance instead of the Euclidean dis- tance. Persistent homology based on the correlation distance itself failed to correctly identify the two ground- truth cycles and DTM produced repre- sentatives that only roughly approxi- mate the ground truth cycles (Fig- ure b). Both effective resistance and diffusion distance successfully un- covered both cycles with 82 0.9 (Figure Dc.d).
Correlation
DTM
Eff. resistance
Diffusion
Doan
Death
Death
Death
Birth
Birth
Birth
Birth
Figure 9: Malaria dataset. a a-d. Representatives of the two most persistent loops overlaid on UMAP embedding (top) and persistence diagrams (bottom) using four methods. Biology dictates that there should be two loops (in warm colors and in cold colors) connected as in figure eight.
Across all six datasets, the detection scores were higher for spectral methods than for their competitors (Figure TOp. Furthermore, manually investigated representative loops for all considered methods on all datasets and found several cases where the most persistent loop(s) was/were likely not correct (hatched bars in Figure TOP. Overall, found that the spectral methods, and in particular effective resistance, could reliably find the correct loops with high detection score. Persistent homology based on the I-SNE and UMAP embeddings worked average better than traditional persistent homology, Fermat distances, and DTM, but worse than the spectral methods.
8 Limitations and future work
In the real-world applications, it was important look at representatives of detected holes as some holes were persistent, but arguably incorrect. That said, each homology class has many different
Malaria 5156D
Neurosphere 20D
Hippocampus 20D
Neural 10D
HeLa2 20D
Pancreas 20D
Delecton score
1.0
0.75
0.5
0.25
Correlation
Fermat
M
GSNE
UMP
Efft resiet.
Diffusion lon
Lap. eig.
Eudidean
Formal GTM- :.NE UMP
Efft resiet.
Dirfus on
Lap. nig.
Eudideen
Fermal
DTM
::SNE UMMP
Etf. resist.
Dirtus on
Lap. nig.
Eugidean Fermal-
DTM :SNE UMMP
Efft resigt. Diffusion Lap. eg.
Eudideen Fermal
DTM-
I:SNE
UMMP
Eff. resist.
Diftus on
Lap. eig.
Eudideen Fermal
DTM
i-SNE
UMMP
Eff resist.
Diffusion
Figure 10: Loop detection scores six high-dimensional scRNA-seq datasets. Hatched bars indicate
implausible representatives. See Figure S34 for detection scores for different hyperparameter values.
Recommended methods in bold.

---

representative cycles, making interpretation difficult. Given ground-truth cycles, an automatic procedure for evaluating cycle correctness remains an interesting research question.
Persistent homology can only detect topology, which is often a useful global level of abstraction. However, it may therefore fail to distinguish some non-isomorphic point clouds [75] There exist
dedicated measures for detecting isometry 7 87 47).
Dimensionality reduction methods are designed to handle high-dimensional data. t-SNE and UMAP indeed performed well on many datasets, but on average worse than spectral distances on the real data. Moreover, UMAP struggled with the surface of the 3D toy datasets and the torus' void (Appendix O). Finally, they require the choice of an embedding dimension and are known to produce artifacts 49 12
85 c.g.. leading to poor scores in the noiseless setting in Figures SI7 S22 In contrast, spectral distances on the symmetric kNN graph worked well without a low-dimensional embedding (Section 7
Using effective resistance or diffusion distances is easy in practice as their computation time O(n²) is dwarfed by that of the persistent homology (S))le(S5). which scales as (nx36+11) for n points and topological holes of dimension 5 [59] This high complexity of persistent homology aggravates other problems of high-dimensional datasets as dense sampling in high-dimensional space would require prohibitively large sample size (recall that spectral methods needed a high sampling density for good performance on some of our datasets such as the torus). Combining persistent homology with -on-Euclidean distance measures could mitigate this problem via the approach of Bendich et al. (6), who performed subsampling after computation of the distance matrix. This is a particularly attractive avenue for future research.
Both effective resistance and diffusion distances require the choice of hyperparameters. However, effective resistance only needs single hyperparameter: the number of kNN neighbors. For this reason and due to its greater outlier resistance (Appendix N). we tend to recommend effective resistance over diffusion distances, but a principled criterion when to use which of the two is still missing.
Moreover, we do not have a theoretical proof that spectral distances mitigate the curse of dimen- sionality, Such a proof may be achieved in the future taking inspiration from the stability results in
77 and, more generally, spectral perturbation theory.
Our empirical results focus benchmarking which distances identify the correct topology in the presence of high-dimensional noise. Therefore, we only considered datasets with known ground-truth topology. The next step will be use spectral distances detect non-trivial topology in real-world exploratory contexts.
High- figh-diimessooal data and thus application areas for our improved topology detection pipeline becoming ubiquitous. Within biology, we see possible applications for our method in other single-cell omics modalities, population genomics, neural activity data [1 40). Beyond biology, we believe that our approach can improve the topological analysis of artificial neural network activations (60], and in general be used to detect topology of any gigh-immesiional data, e.g. in the climate sciences, in astronomical measurements, or wearable sensor data.
Conclusion
In this work asked how use persistent homology on high-dimensional noisy datasets which are very common in real-world applications even if the intrinsic data dimensionality is low. We found spectral methods to be the optimal approach. We demonstrated that, as the dimensionality of the data increases, the main problem for persistent homology shifts from handling outliers to handling noise dimensions (Section 4. We used a synthetic benchmark show that traditional persistent homology and many of its existing extensions struggle to find the correct topology in this setting. Our main finding is that spectral methods based on the INN graph, such as the effective resistance and diffusion distances, still work well (Section 7.1) Furthermore, we view it as an advantage that we noise. We
found existing methods that are able to handle the important problem of high-dimension derived an expression for effective resistance based on the eigendecomposition of the graph Laplacian, and demonstrated that combines all but the most local diffusion distances (Section 6). Finally, we showed that spectral distances outperform all competitors on single-cell data (Section
10

---

Acknowledgments and Disclosure of Funding
We thank Enrique Fita Sanmartin and Ulrike von Luxburg for productive discussions on effective resistance and persistent homology, and Benjamin Dunn, Erik Hermansen, and David Klindt for helpful discussions on combining persistent homology with other dissimilarities than Euclidean distance. Moreover, we thank Sten Linnarsson and Miri Danan Gotthold for sharing the scVI representation of their pallium data. Final thanks go to Bastian Rieck for feedback on the writing.
This work was funded by the Deutsche Forschungsgemeinschatt (DFG, German Research Foundation) via Germany's s Excellence Strategy (Excellence cluster 2064 "Machine Learning New Perspectives for Science",, EXC 390727645; Excellence cluster 2181 "STRUCTURES", EXC 390900948), the German Ministry of Science and Education (BMBF) via the Tübingen AI Center (01IS18039A) the Gemeinnützige Hertie Starti-Si and the National Institutes of Health (UM I MHH 119909.1). The content solely the responsibility of the authors and does not necessarily represent the official views of the National Institutes of Health.
References
[1] M. E. Aktas, E. Akbas, and A. E. Fatmaoui. Persistence homology of networks: methods and applications. Applied Network Science, 4(1):1-28, 2019.
[2] H. Anai, Chazal, M. Glisse, Y. lke, H. Inakoshi, R. Tinarrage, and Y. Umeda. DTM--asee filtrations. In Topological Data Analysis: The Abel Symposium 2018, pages 33-66. Springer, 2020.
[3] A. Bastidas-Ponce, S. Tritschler, L. Dony, K. Scheibner, M. Tarquis-Medina, C. Salinno, S. Schirge, I. Burtscher, A. Böttcher, F. Theis, et al. Comprehensive single cell mRNA profiling reveals a detailed roadmap for pancreatic endocrinogenesis. Development, 146(12): dev173849, 2019.
[4] U. Bauer. Ripser: efficient computation of Vietoris- persistence barcodes. Journal of Applied and Computational Topology, 5(3), 2021.
[5] M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in Neural Information Processing Systems, volume 14, pages 585-591, 2002.
[6] P. Bendich, Т. Galkovskyi, and J. Harer. Improving homology estimates with random walks. Inverse Problems, 27(12):124002, 2011.
[7] M. Boutin and G. Kemper. On reconstructing n n-point configurations from the distribution of distances areas. Advances in Applied Mathematics, 32(4):709-735, 2004.
[8] E. Braun, M. Danan Gotth-l L. Borm, K. W. Lee, E. Vinsland, P. Lönnerberg, L. Hu, X. Li. X. He, Ž. Andrusivová, al. Comprehensive cell atlas of the first-trimester developing human brain. Science, 382(6667)xcadf1 126,, 2023.
[9] N. Brugnone, A. Gonopolskiy, M. W. Moyle, M. Kuchroo, D. van Dijk, K. R. Moon, D. Colon- Ramos, G. Wolf, M. J. Hirn, and S. Krishnaswamy, Coarse graining of data via inhomogeneous diffusion condensation. In 2019 IEEE International Conference on Big Data (Big Data), pages IEEE, 2019.
[10] R. J. Campello, D. Moulavi, A. Zimek, and J. Sander. Hierarchical density estimates for data clustering, visualization, and outlier detection. ACM Transactions on Knowledge Discovery from Data (TKDD), 10(1):1-51, 2015.
[11] M. Carrière, F. Chazal, Y. Ike, T. Lacombe, M. Royer, and Y. Umeda. Perslay: A neural network layer for persistence diagrams and new graph topological signatures. In International Conference on Artificial Intelligence and Statistics, pages 2786-2796. PMLR, 2020.
[12) Chari and I.. Pachter. The specious art of single-cell genomics. PLOS Computational Biology, :9(8);e 101 1288, 2023.
11

---

[13] B. Charlier. J. Feydy, J. A. Glaunès, F.-D. Collin, and G. Durif. Kernel operations on the GPU, with autodiff, without memory overflows. Journal of Machine Learning Research, 22(74):1-6, 2021.
[14] F. Chazal and B. Michel. An introduction to topological data analysis: fundamental and practical aspects for data scientists. Frontiers in Artificial Intelligence, 4:108, 2021.
[15] F. Chazal, D. Cohen-Steiner, and Q. Mérigot. Geometric inference for measures based on distance functions. Foundations of Computational Mathematics, 11(6):733-751, 2011.
[16] Chew, H. Steach, S. Viswanath, H.-T. Wu, M. Hirn, D. Needell, M. D. Vesely, S. Krish- naswamy, and M. Perlmutter. The manifold scattering transform for high-dimensional point cloud data. In Topological, Algebraic and Geometric Learning Workshops 2022, pages 67-78. PMLR, 2022.
[17] F. R. Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
[18] L. Clarté, A. Vandenbroucque, G. Dalle, B. Loureiro, Krzakala, and L. Zdeborová, Analysis of bootstrap and subsampling in high-dimensional regularized regression. arXiv preprint ..X.:22402.13622 2024.
[19] D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Stability of persistence diagrams. In Pro- ceedings of the twenty-first annual symposium on Computational geometry, pages 263-271, 2005.
[20] R. R. Coifman and S. Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5-30, 2006.
[21] D. Damm. Core-distance-weighhed persistent homology and its behavior on tree-shaped data. Master's thesis, Heidelberg University, 2022.
[22] S. Damrich and F. A. Hamprecht. On UMAP's true loss function. In Advances in Neural Information Processing Systems, volume 34, pages 5798-5809, 2021.
[23] T. Davies, Z. Wan, and R. J. Sanchez-Garcia. The persistent Laplacian for data science: Evaluating higher-order persistent spectral representations of data. In International Conference on Machine Learning, pages 7249-7263. PMLR, 2023.
[24] P. G. Doyle and J. L. Snell. Random Walks and Electric Networks, volume 22. American Mathematical Soc., 1984.
[25) Edelsbrunner, Letscher, and Zomorodian. Topological persistence and simplification. Discrete Computational Geometry, 28:511-533, 2002.
[26] X. Fernández, E. Borghini, Mindlin, and Groisman. Intrinsic persistent homology density-based metric learning. Journal of Machine Learning Research, 24(75):1-42, 2023.
[27] E. Maattes-auuista and M. Thomson. Unraveling cell differentiation mechanisms through topological exploration of single-cell developmental trajectories. bioRxiv, pages 2023-07, 2023.
[28] F. Fouss, A. Pirotte. J.-M. Renders, and M. Saerens. Random-wald computation of similarities between nodes of graph with application collaborative recommendation. IEEE Transactions on knowledge and data engineering. 19(3):355-233 369, 2007.
[29] F. Fouss, M. Sacrens, and M. Shimbo. Algorithms and Models for Network Data and Link Analysis. Cambridge University Press, 2016.
[30] I. Gareía-Redondo, A. Monod, and A. Song. Fast topological signal identification and persistent cohomological cycle matching. Journal of Applied and Computational Topology, pages 1-32, 2024.
[31] R. J. Gardner, E. Hermansen, M. Pachitariu, Y. Burak, N. A. Baas, B. A. Dunn, M.-B. Moser, and I. Moser. Toroidal topology of population activity in grid cells. Nature, 602(7895): 123-128 2022.
12

---

[32] F. Göbel and A. Jagers. Random walks on graphs. Stochastic processes and their applications, 2(4):31,-336, 1974.
[33] J. C. Gower and G. J. Ross. Minimum spanning trees and single linkage cluster analysis. Journal of the Royal Statistical Society: Series C (Applied Statistics), 18(1):54-64) 64, 1969.
[34] P. Groisman, M. Jonckheere, and F. Sapienza. Nonhomogeneous Euclidean first-passage percolation and distance learning. Bernoulli, 28(1):255-276, 2022.
[35] L. Haghverdi. F. Buettner, and F. J. Theis. Diffusion maps for high- dimensional single-cell analysis of differentiation data. Bioinformatics, 31(18):2989-299 2015.
[36] L. Haghverdi, M. Büttner, F, A. Wolf, F. Buettner, and F. J. Theis. Diffusion pseudotime robustly reconstructs lineage branching. Nature Methods, 13(10):845-88) 848, 2016.
[37] M. Hajij, B. Wang, C. Scheidegger, and P. Rosen. Visual detection of structural changes in time-varying graphs using persistent homology. In 2018 IEEE Pacific Visualization Symposium (pacifievis), pages 125-134. IEEE, 2018.
[38] P. Hall, J. S. Marron, and A. Neeman. Geometric representation of high dimension, low sample size data. Journal of the Royal Statistical Society Series B: Statistical Methodology, 67(3): 427-444, 2005.
[39] A. Hatcher. Algebraic Topology. Cambridge University Press, 2002.
[40] E. Hermansen, D. A. Klindt, and B. A. Dunn. Uncovering 2-d toroidal representations in grid
cell ensemble activity during 1-d behavior. Nature Communications, 15(1):5429, 2024.
[41] G. E. Hinton and S. Roweis. Stochastic neighbor embedding. In Advances in Neural Information Processing Systems, volume 15, pages 857-864, 2002.
[42] Y. Hiraoka, Y. Imoto, S. Kanazawa, and E. Liu. Curse of dimensionality on persistence diagrams. arXiv preprint arXiv:2404. 18/94, 2024.
[43] V. M. Howick, A. J. Russell, T. Andrews, H. Heaton, A. J. Reid, K. Natarajan, H. Butungi, T. Metcalf, L. H. Verzier, J. C. Rayner, et al. The malaria cell atlas: Single parasite transcriptomes across the complete Plasmodium life cycle. Science, 365(6455))eaaw2261, 2019.
[44] X. Hu, F. Li, D. Samaras, and C. Chen. Advances in Neural Information Processing Systems, 32, 2019.
deep image segmentation.
[45] J. Jia and L.. Chen. Single-cell RNA sequencing data analysis based on non-uniform neighborhood network. Bioinformatics, 38(9):2459-245) 2022.
[46] M. Kuchroo, M. DiStasio, E. Song, E. Calapkulu, L. Zhang, M. Ige, A. H. Sheth, A. Majdoubi, M. Menon, A. Tong, et al. Single-cell analysis reveals inflammatory interactions driving macular degeneration. Nature Communications, 14(1):2589, 2023.
[47] V. Kurlin. Polynomial-time algorithms for continuous metries on atomic clouds of unordered points. MATCH Commun. Math. Comput. Chem., 91:79-108, 2024.
[48] J. Lamar-León, F. B. Garcia-Reyes, and R. Gonzalez-Diaz. Human gait identification using persistent homology. In Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications: 17th Iberoamerican Congress, CIARP 2012, Buenos Aires, Argentina, September 3-6, 2012. Proceedings 17, pages 244-251. Springer, 2012.
[49] P. S. Landweber, E. A. Lazar, and N. Patel. On fiber diameters of continuous maps. The American Mathematical Monthly, 123(4):392-377, 2016.
[50] R. Lopez, J. Regier, M. B. Cole, M. I. Jordan, and N. Yosef. Deep generative modeling for single-cell transcriptomics. Nature Methods, 1553211053-- 2018.
[51] L. Lovász, Random walks graphs. Combinatorics, Paul Erdōs is Eighty, 2(1-46):4, 1993.
13

---

[52] H. Masoomy, B. Askari, S. Tajik, A. K. Rizi, and G. R. Jafari. Topological analysis of interaction patterns in cancer-specific gene regulatory network: Persistent homology approach. Scientific Reports, 11(1):16414, 2021.
[53] L. McInnes, Healy, and J. Melville. UMAP: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv:1802.03326, 2018. 8.
[54] F. Mémoli. personal communication, 2023.
[55] Mémoli, Z. Wan, and Y. Wang- Persistent Laplacians: properties, algorithms and implications. SIAM Journal on Mathematics of Data Science, 4(2):858 884, 2022.
[56] K. R. Moon, D. van Dijk, Z. Wang. S. Gigante, D. B. Burkhardt, W. S. Chen, K. Yim, A. Elzen, M. J. Hirn, R. R. Coifiaa, et al. Visualizing structure and transitions in high-dimensional biological data. Nature Biotechnology. 37(12):1482-1444 2019.
[57] J. L. Moore, D. Bhaskar, F. Gao, C. Matte-Martone, S. Du, E. Lathrop. S. Ganesan, L. Shao, R. Norris, N. Campamà Sanz, et al. Cell cycle controls long-range calcium signaling in the regenerating epidermis. Journal of Cell Biology, 222())=e003302095 2023.
[58] S. Mukherjee, D. Wethington, T. K. Dey, and J. Das. Determining clinically relevant features in cytometry data using persistent homology. PLoS Computational Biology, 1009)91, 2022.
[59] A. D. Myers, M. M. Chumley, F. A. Khasawneh, and Munch. Persistent homology of coarse-grasd coarse-grained state-space networks. Physical Review E, 107(3)0034303, 2023.
[60] G. Naitzat, A. Zhitnikov, and L.-H. Lim. Topology of deep neural networks. Journal of Machine Learning Research, 21(1):7503-7542, 2020.
[61] A. Petenkaya, F. Manuchehrfar, C. Chronis, and J. Liang. Identifying transient cells during reprogramming via persistent homology. In 2022 44th Annual International Conference of the IEEE Engineering in Medicine & Biology Society (EMBC), pages 2920-2923 IEEE, 2022.
[62] G. Petri, M. Scolamiero, I. Donato, and F. Vaccarino. Networks and cycles: a persistent homology approach to complex networks. In Proceedings of the European Conference on Complex Systems 20/2, pages 93-99. Springer, 2013.
[63] P. G. Poličar, M. Stražar, and B. Zupan. openTSNE: A modular python library for t-sne dimensionality reduction and embedding. Journal of Statistical Software, 109:1-30, 2024.
[64] Y. Reani and O. Bobrowski. Cycle registration in persistent homology with applications in topological bootstrap. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(5): 5.59-55599 5593, 2022.
[65] A. J. Reid, A. M. Talman, H. M. Bennett, A. R. Gomes, M. Sanders, C. J. Illingworth, O. Bil- Iker, M. Berriman, and M. K. Lawniczak. Single-cell RNA-seq reveals hidden transcriptional variation in malaria parasites. eLife, 7:c33 105, 2018.
[66] B. Rieck and H. Leitte. Agreement analysis of quality measures for dimensionality reduc- tion. In Topological Methods in Data Analysis and Visualization IV: Theory, Algorithms, and Applications VI, pages 103-117. Springer, 2017.
[67] B. Rieck, M. Togninalli, C. Bock, M. Moor, M. Horn, T. Gumbsch, and K. Borgwardt. Neural persistence: complexity measure for deep neural networks using algebraic topology. In International Conference on Learning Representations, 2018.
[68] A. H. Rizvi, P. G. Camara, E. K. Kandror, T. Roberts, I. Schieren, T. Maniatis, and R. Rabadan. Single-cell topological RNA-seq analysis reveals insights into cellular differentiation and development. Nature Biotechnology, 35(6):551-566 2017.
[69] M. Robinson and A. Oshlack. scaling normalization method for differential expression analysis of RNA-seq data. Genome Biology, 11(3):1-9,2014 2010.
14

---

[70] S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323 2226, 2000.
[71] B. Roycraft, J. Krebs, and W. Polonik. Bootstrapping persistent Betti numbers and other stabilizing statistics. The Annals of Statistics, 51(4):1484-150 2023.
[72] D. Schwabe, S. Formichetti, J. Junker, M. Falcke, and N. Rajewsky. The transcriptome dynamics of single cells during the cell cycle. Molecular Systems Biology, 16(1 I :ee946, 2020.
[73] G. Singh, F. Mémoli, G. E. Carlsson, et al. Topological methods for the analysis of high dimensional data sets and 3D object recognition. PBG @ Eurographics, 2:091-100, 2007.
[74] P. Smith and V. Kurlin. Skeletonisation algorithms with theoretical guarantees for unorganised point clouds with high levels of noise. Pattern Recognition, 115: 105:10790,, 2021.
[75] P. Smith and V. Kurlin. Generic families of finite metric spaces with identical or trivial 1- dimensional persistence. Journal of Applied and Computational Topology, pages 1-17, 2024.
[76] B. Tenenbaum, V. De Silva, and C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, (0055500)2231--2233 2000.
[77] Q. H. Tran, Y. Hasegawa, et al. Scale-variant topological information for characterizing the structure of complex networks. Physical Review E, 100(3):032308, 2019.
[78] R. Turkes, G. F. Montufar, and N. Otter. On the effectiveness of persistent homology. Advances Neural Information Processing Systems, 35:35432 -354488 2022.
[79] L. van der Maaten and G. Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, (11):2579-2605 2008
[80] S. Vishwanath, K. Fukumizu, S. Kuriki, and B. K. Sriperumbudur. Robust persistence diagrams using reproducing kernels. Advances in Neural Information Processing Systems, 33:21 1900- 21911, 2020.
[81] U. von Luxburg. A. Radl, and M. Hein. Getting lost in space: Large sample analysis of the resistance distance. Advances in Neural Information Processing Systems, 23, 2010.
[82] U. von Luxburg, A. Radl, and M. Hein. Hitting and commute times in large graphs are often misleading. arXiv preprint arXiv: 1003. 1266, 2010. version from Mar 05 2010.
[83] U. von Luxburg, A. Radl, and M. Hein. Hitting and commute times in large random neighbor- hood graphs. Journal of Machine Learning Research, 15(1)1155) 2014.
[84] M. Wang, Z. Cang, and G.-W. Wei. A topology- based network tree for the prediction of protein-prect protein binding affinity changes following mutation. Nature Machine Intelligence, 2(2): 116-123, 2020.
[85] S. Wang, E. D. Sontag, and D. A. Lauffenburger. What cannot be seen correctly in 2D) visualizations of single-cell 'omics data? Cell Systems, 14(9):723-731 2023.
[86] L. Wasserman. All of nonparametric statistics. Springer Science & Business Media, 2006.
[87] D. Widdowson and V. Kurlin. Recognizing rigid patterns of unlabeled point clouds by complete and continuous isometry invariants with no false negatives and no false positives. In Proceedings of the IEEF/VV Conference on Computer Vision and Pattern Recognition, pages 1275-1284, 2023.
[88] F. A. Wolf, F. K. Hamey, M. Plass, J. Solana, S. Dahlin, B. Göttgens, N. Rajewsky, L. Simon, and F. J. Theis. PAGA: graph abstraction reconciles clustering with trajectory inference through a topology preserving map of single cells. Genome Biology, 20:1-9, 2019.
[89] S. C. Zheng, G. Stein-O' Brien, J. Augustin, J. Slosberg, G. A. Carosso, B. Winer, G. Shin, H. T. Bjornsson, L. A. Goff, and K. D. Hansen. Universal prediction of cell-cycle position using transfer learning. Genome Biology, 23(1):1-27, 2022.
[90] A. Zomorodian and Carlsson. Computing persistent homology. In Proceedings of the twentieth annual symposium Computational geometry, pages 347-356, 2004.
15

---

A Broader impact
The goal of our paper is to advance the field of machine learning. Our comprehensive benchmark required a lot of compute. However, we expect that the lessons learned will save compute for researchers applying persistent homology their high-dimensional data. Beyond this, we do see any potential societal consequences of our work that would be worth specifically highlighting here.
B Noise in high-dimensional spaces eventually dominates structure
In this section, we rigorously prove the intuitive result that the Euclidean distances and thus the traditional persistence diagrams - eventually get dominated by noise as the number of ambient dimensions grows (assuming homoscedastic noise). The main results Corollary [B.3 and Corol- lary B.7 Our analysis is similar to the concurrent work of Hiraoka et al. 42). Their analysis extends ours in that they consider an arbitrary noise distribution, the Cech complex, and make more precise statements on how persistent homology gets impaired by high-dimensional noise.
We begin with some helpful lemmata.
Lemma B.1. Let {E,,a) and {$2,a} be two sequences of d-dimensional multivariate normally distributed random variables Ei,d ~ NN La)... For fixe d, we have 1, 2 Moreover, the sequence {Ilēi,a 2,,ll/ converges /2a almost surely.
Proof. All entries E 2 are i..dd Gaussian random variables with zero mean and variance 2o The squared Euclidean distance the sum of the squared entries the vector, which implies the first statement. By the strong law of large numbers, ||=i,d E /d converges almost surely to
20². By the continuous mapping theorem, this implies almost sure convergence of ||Ei, - &2.a Vd to 22a.
Lemma B.2. Let {Xa} be sequence of random variables with finite means and variances. If (Xaa) converges to a constant e and Var(Xa) + 0 as d - oc, then {Xa} converges to in squared mean, i.e, E((xa - c))) -
Proof. We have
E( c) = =E(X3) 2x + c²
= IB(X3) E(Xa)² + 2 2cB(Xa) = Var(Xa) + - +
- + - 20 + 2
(8)
Lemma B.3, Let {Xa} be a sequence of random variables which converges in squared mean to random variable X. Then also converges X in probability.
Proof. This is an application of Markov's inequality. Let > 0. Then
P(IXa X > s) = P(( -) &?) < B((Xa x)2)/6²
for d + by convergence in squared mean.
Now we show that for sufficiently many noise dimensions the distance between any two points gets dominated by the noise. This follows from the Pythagorean theorem, because most noise dimensions are orthogonal to the difference of the noise-free points. A similar result can be found in Hall et al.
38
Proposition B.4. Let I1 and vn be two points in Rdd Let {Ea} be sequence of isometries ld : de -> Rdd for 2 d' Let (Ei,)) and (E2.a) be two sequences of d-dimensional multivari- normally distributed random variables Ei, NNO, daLa) starting sequence of Euclidean distances between (a(x1) + Ei,d and ta(xz) + E2 Then { ( dd converges 20 in squared mean.
d'. Let & (Da) be the
16

---

Proof. Denote the distance of the embedded points by 8 = || - x2ll Il(a(a1)) 1 - (2(2)) We have
= = ((((21) + Fi,d (4a(x2) + E2.a) || = (1(((211) + E1,d - E2,d) La (2(2))l
So instead of the setting where both points get noised, we can just consider the case where only the first point gets noised by d-dimensional multivariate normally distributed variable of double variance Sa (0, 2a) We denote ||eall by L. We will drop the use of now and just write T2 E F- in slight abuse of notation.
Let be the angle that Ea makes with the vector 22 I1. Then, by the law of cosines,
A = 13 + 8² 28 cos(())..
Since Ed is isometrically distributed, we can assume that 2/2 - 21 is parallel to (1,0, ........ 0) without loss of generality. Then cos(a))l 5', where e (0, 2 is the first entry of Ea. Thus, E(A)) = 20dd + 82 by Lemma B.1 and B(A + 2n for d + 0o.
For the variance, we obtain
Var Var(I2 - (d Var(s + Var(s"2 28E').
The first term contains the variances all the directions orthogonal to ø2 21. Since E is isotropic, all directions are independent and we can simply add up the individual variances. The second term contains the variance in direction 22
ø1. We have
Var(s"²) = 3 40 40
80
(10)
Var(E"2 28Ee) E(5"t 13 + 402 2 E(s - 20s')²
-120* +0 86" 40
+8 682
(11)
Together, we have
Var A3/(43/d)= = ((d 1)80² + 80 - 802 36200)//d
80 (do² /d
0
(12)
d co. By Lemma
B.2
conclude that (A3/d) converges to 20 in squared mean.
The next corollary generalizes Proposition B.4 to an arbitrary arrangement of n points, Independent of their structure, noise will dominate all distances for sufficiently high dimensionality.
Corollary B.5. Let I1, "i.....,7p Fn be n pairwise distinct points TRd"". Let {1a} be a sequence of isometries La Rdd - Rd for d 2 d'. Let further (Ei.a)..... {En,a} } be sequences of multivariate normally distributed random variables Es,d ~ o"Aa in dimensions. Let Aija be the sequence of random variables of Euclidean distances between va(x;) + Ei,d and ta(x)) + Sj,d- Then each sequence (Aija/ vd converges /2a in probability as p + co. The sequence Allei,d- EEj Aija) converges to 1 in probability and thus the joint vector (I E -iall/ with entries for each pair + converges the vector of all ones probability
Proof. Proposition B.4 Lemma B.3 and the continuous mapping theorem imply that Aija// Vd converges to V2o in probability p and that vd/ j.d. which is well-defined up of measure zero, converges (v2o)-1 in probability. By Lemma B.l and since almost sure convergence implies convergence in probability, we have that |leud - Ealll/ / converges to /2a in probability as well. Since convergence in probability is preserved under multiplication, we obtain that ||ei,d - Sj.al//Asjj. converges
probability. Finally, convergence probability of two sequences implies joint convergence in probability.
17

---

Corollary B.6. Consider the setting of Corollary B.5 and choose some >> O. Then we have that
P(min A j.ja/ aala/vdd Vd > V2a =).
(13)
P(min A A /adiaa/Ve < V20 +,),
(14)
bd
P(max Aisa/Vd V20 8). and
(15)
P(max A.s.a/Vd < -20 +
(16)
if
all go to one as d + oc.
Proof. Since max and min are continuous maps, the continuous mapping theorem and Corollary B.5
imply convergence of the sequences {max, A i Vd) and {ming,, Aij.a/ /d) to /2a in proba-
bility. The claim follows since the terms [3 and 15 (16) are lower bounded by
P( min Aij.a/ Aig.a/dd /d 22 8) and IP( max Asga/Vd -22 > E),
(17)
respectively.
The next corollary shows that for sufficiently high ambient dimension d, increasing the noise level will increase birth and death times and thus drive persistent homology with high probability.
Corollary B.7. Consider the setting of Corollary B.5 but for different noise levels a > d' > O. Let Bd and ōá. be the minimal birth and death times among all least mineinnnsio homological features at that noise level and ambient dimensionality, Similarly, let Ba,a and Da,a be the maximal birth and death times among all at least one-dimensional homological features. Then P(3a, > Da.or)) and hence also (33,, >> Ba,e.) ), (p > Da.or) converge to one as - 0o.
Proof. Denote the distance between the noised d-dimensional points i, with noise level by A.jiddo. The main idea is that Sd, 2 min.,j A.j.d. and Dd, I max.,j A.j.d.o. We prove P(Ba, Dd.or) + The other statements follow from Bá,o < Bd, and óa,0 Bá,a.
Choose any 0 < < (a o')/V/ Then /2a => /20' Furthermore, we have
PP(ba, > Da.or) 2 P P(baa > (V2o - s)Vd and (V20' + +e)vd > Da
By Corollary B.6 have for d that
P(bu, (V20 v) 2 PP
min A Aijdo (V20 =)Vdd +1.
1.j
Similarly,
P(Da < (V2o'+e)VD) +elvo) P max
Aijdo (V20'+e)VV +e)vo)
igj
As result,
1 P(ba,o > (V2o Vd and (V20' + +e\Vd> Da + 1, and hence P(bs,o Ds.or) + for + c0.
These statements show that noise will eventually dominate the Euclidean distances and drive tradi- tional persistent homology if the ambient dimension is large enough. In Figure 8 we saw empirically that tens ambient dimensions already severely impact traditional persistent homology, while spec- tral distance offer more noise robustness. This also holds true in hundreds to thousands of ambient dimensions. Compared to the Fuclidean distance, spectral distance can detect the correct topology in more than order of magnitude higher dimensionality. before they eventually fail too (Figure S1
18

---

Loop dolectoon score
1.0
0.0
1.0
Loop detectoon sooiee
0.05
DTM
0.5
p-2, 0-2
0.2
-0.5
resist
0.25
k- 100
0.35
100
1000
k 100,0 c
Diflusion
8
2000
5000
Ambient
Figure S1: Extension of Figure 8 of various methods on noisy circle depending on the ambient dimensionality. Due to the higher dimensionalities,
to higher ambient dimensionalities. a. Loop detection scores
here the noise with standard deviation = 0.125, one half compared to Figure Sh. b-e. Heat maps for a E [0, 0.35] and E [50, 000). Spectral methods are much more noise robust, but eventually also fail to detect the correct topology.
C Persistent homology with PCA
42 recommend combating the curse of dimensionality by performing a normalized PCA before applying persistent homology. We explore this approach here our setting.
Hiraoka et al.
Let X (Ii...., ........a. )n,"= E Raxd be the centered data matrix with each data point as a row. Let USVT be the singular value decomposition of X with U and V orthogonal matrices and $ E Raxd diagonal with decreasing non-negative values the diagonal. PCA reduces the dimensionality to dimensions by considering the first columns of US, while normalized PCA instead considers the first k columns of U.
We ran experiments on the ID datasets for both versions with varying number of principal components (PCs) (Figure SS2). Normalization provided no consistent benefit. The performance was worse for higher number of PCs more noise remained after PCA. Using fewer PCs than the dataset's true dimensionality (Figure S2 j) also led to poor performance. Knowing the true dimensionality of true dimensionality is typically not available in
the data is therefore crucial for this approach, real-world applications. Effective resistance outperformed PCA preprocessing on the linked circles and eyeglasses dataset and showed similar performance on the circle.
D Continuity of the hole detection score
In this section we prove that our hole detection score is continuous map, as long as the persistence diagrams have sufficiently many points. This means that small changes in the persistence diagram result in small changes of the hole detection score, a desirable property for a performance measure.
Eff. resist.
PCA
Normalized PCA
Best hyperprameee
0.60
0.25
0.00
0.0
0.1
02
0.3
0.0
0.1
0.3
0.1
02
0.0
0.1
02
0.8
k
0
0.00
0.05
0.10
0.15
0.00
0.35
0.10
0.15
0.00
0.25
0.10
0.16
0.00
0.05
0.10
0.15
std
Noise
Euciidian
Eudidean
nomwired
PCs normelized
Eflocive resistance
3 PCs not nommalzed
PCs normalized
Euclddaan
nomaitzed
PCs normalized
Eff.
Effective
normalized
POs nomatized
resistance k= 100
POu not normalzed
20 PCs nomellzzd
Narmalzed PCA
Figure S2: Loop detection score for effective resistance and PCA on three ID toy datasets.
19

---

To state our result formally, we recall some definitions from Johen-Steinet et al. [1]
Definition D.I (Multiset). A multiset is set in which each element has a multiplicity in N5o U co.
Definition D.2 (Persistence diagram). A persistence diagram is multiset with elements from {(b, d) E (RR U (-00, x)2 b < d) counted with multiplicities, together with the diagonal ((b,b) E (RU{- (RO 0o)) oo)) counted with infinite multiplicity.
Since we build persistence diagrams only for distances-based Vietoris-Rips complexes and do not consider O-dimensional homologies in this paper, no birth times will be -oo. Moreover, since we do not consider infinite distances (Appendix Db. no death times will be infinite either. Therefore, in the following, will treat persistence diagrams multisets with elements in IR?
Definition D.3 (Bottleneck distance). Let D and T) be persistence diagrams. Then the bottleneck distance between them is given by
dD, = inf sup | ()))) 'DD-DD' rD
where the infimum is over the bijections between the multisets D and D'.
bijection y realizing the bottleneck distance between persistence diagrams has three types of paired points: Pairs with both points off the diagonal, pairs with exactly one point off the diagonal, and pairs with both points equal and on the diagonal. Intuitively, the bottleneck distance matches the off-diagonal points between each other. However, the second type of pairs is needed in case the persistence diagrams do not have the same number of points off the diagonal. This is why the full diagonal with infinite multiplicity is considered to belong to each persistence diagram. The third type of pairs does not contribute to the bottleneck distance.
We can now proceed with our proofs. Let 'D be the space of all persistence diagrams with finitely many points off the diagonal, endowed with the topology induced by the bottleneck distance dp.
Lemma D.4. For any m E N, the map Pm. + Rzo assigning to a diagram m-th largest persistence value is continuous.
Proof. For persistence diagram D D and a feature f= [-(,, Ta) E D we denote by p(ʃ) Ta Tu the persistence of f. Note that for two features f. in a persistence diagram, we have (P(f) - p(f') S - -
We need to show that for any s > 0 and any D E D, we can choose some 8 > 0 such that Ipm (D') - Pm (D) < for all D' whose bottleneck distance from D is at most 6, i.e. D' e B3 (D). Recall that in this setting, by definition of the bottleneck distance, there is bijection (of multisets) 17: + D' such that for all f E D we have Il. (f) 8.
Continuity of Pm is easier to demonstrate at diagrams E D for which all off-diagonal points have different persistences. We discuss this case first. Assume D) has off-diagonal points. Denote by fk the feature with k-th largest persistence.
Let 8 min (f(x) - 1(fx+1) | k S 1) and min ((/(222) Consider D' E (D)... By the choice of 6, we have that [p(n([=)) (acl))-p((fa) -(((a) < 8/2, so that the values (((ff))))..,,(((((()) 0 are all distinct and strictly decreasing. As result, for all m S 1 we have pm (D') p(n(mm)) and thus
Ipm (D') Pm
pm (D) (p((((m)) - p(fm) < 220 <.
For m >> 1, we have Pm (D) = 0 and any I' E D' with pm (D' = p(J") is paired with a point on the diagonal of D under v). Hence
Ip (D') - Pm ( - 0 < /26 <
The case where might contain off-diagonal points with identical persistence follows the same overall argument, but requires more careful bookkeeping. Assume D has l off-diagonal points. Let
j = min (Dp)(D) Pk+1 (D) & < (}{(0)) Let
8 = min (8/(222)
20

---

Set
F = ( = PD))
for k < and Fi+. equal the diagonal. These multisets all contain at least one element. We have Pr. Pa(D) (D) = Pk+1 (D) if and only Fk = Fk+1-
As result, for all k S I, we have I Fil = if and only if Fi + Fx+1 which in turn holds if and only pk (D) + (D).
For any f. D with p(f) p(f) have
-(n(f))-p(n(d - p(n(f)) = p(n(f)) - p(f) + +((f) - +(f)+ + - p(n(f)) p - -p(f) - (I(n(()) - (101-1P(1) p(((f))
p(f) -p(f) - 20,
(18)
so p(n(f)) p(n(f)). We will now show that if and f D' such that pm (D') p(f'). then (f) E Fm.
Let be the highest number below such that Fa F Fm Then
Un(oy = Ü F
and Ui-1 (F.)) contains the m features of D' with smallest persistence. In particular, "f') & F.
Let be the largest number such that FA Fm. By a similar argument, Uh (FF)) contains the b 2 m features in D' with largest persistence, including f'. Thus, n (f(()) E Ubzat1 F.. But by choice of a and b, we have Fat1
Fm Fb. so 17 11 Fm.
Thus,
IDm(D') Pm (D) lp(f") p(n (())) V211 - (f')l <E.
For m > 1, we have pm (D) = 0 and Fm is the set of points on the diagonal of D. Moreover,
U R = 1- Ü (F..) i=1
k=1
so that any f' E D' with Pm (D') p(f') must be in the image of the diagonal under ry and we can proceed as in the case of unique positive persistences.
Our hole detection score is continuous score if there are at least points in the persistence diagram, and not continuous otherwise:
Proposition D.5. Let 'D be the space of all persistence diagrams with funitely many points off the diagonal, endowed with the topology induced by the bottleneck distance dg. Let m E E and define D' as the subset of D with at least m points off the diagonal. Then the map 8m D > R20 continuous at all diagrams in D' but is discontinuous at all diagrams in D D'D'.
Proof. The discontinuity of 8m at diagrams with less than m points happens when adding the mn-h point to diagram. Let D be persistence diagram with < points off the diagonal. Let 0 and define D' as the persistence diagram obtained by adding m - copies of (0, s /2). Then 8m 8m (D) = and sn (D') 1, because D' has exactly off-diagonal points, but (D, < Thus, sm is not continuous at D.
For the continuity part, we write sm as the composition of two continuous maps. The map q: R50 R20 + R2o, (I, v) + (a v)/x is continuous. Furthermore, since each diagram in D' has at least points off the diagonal, Pm (D) E RR for all D E D'. By lemma D.4 the map Pm Pm++1 D > R20 x Rgo is continuous. Finally, 8m D' - RRz0 factors as g (pm x Pm++1). 1) showing its continuity.
21

---

In other words, on persistence diagrams with sufficiently many points our hole detection score is continuous. This makes our score robust against small perturbations in the persistence diagram, property expected for reliable score.
In the typical case, where the persistence diagram contains a noise cloud of many points close the diagonal and, possibly, some outliers far away from the diagonal, the requirement on the number of points is satisfied. Only the case where we expect a large gap after the m--hh feature, but the diagram does not even have m features, can there be sudden jump in our hole detection score.
E Alternative performance scores
While our hole detection score corresponds to an intuitive visual assessment of persistence diagrams and is continuous (Appendix D) in this section we discuss two alternative performance scores. We argue that both of them are less suited for our benchmark.
E.1 Widest gap score
natural way to interpret a persistence diagram is to deem all features above the widest gap in persistence values true features and the as noise, i.e., infer that diagram has true features if a argmax, (Po- P.++1)
We considered the binary score which is equal to 1 if the number of features above the widest gap equals the number of ground truth features and otherwise. We call it the widest gap score.
Note that our hole detection score can be lower than 1 even if the persistence diagram clearly shows the correct number of outlier features (e.g. 8m 0.5 for a 0.2 in Figure 3p). In contrast, the widest gap score is equal to in this case.
On the other hand, the binary nature of the widest gap score leads to instability in case of nearly equisized gaps. For instance in Figure Dd. a small perturbation could make the gap after the most persistent feature the widest, dropping the widest gap score from to O. In contrast, our 82 R 0.9 correctly reflects the two clear outlier features.
We evaluated several distances the three ID datasets using the widest gap score in Figure S3 The binary nature of the widest gap score led to high-variance results even though we increased the number of random seeds from to 10. Spectral methods still performed better than Euclidean, Fermat, and DTM distances. However, the widest gap score led to some false positives. For example, for the Fermat distance and 0.3 for the circle dataset, in of 10 trials the widest gap appeared after the first feature. However, all persistence diagrams looked like noise clouds and cases the most persistent feature's representative cycle for the effective resistance there was always a clear outlier in the diagram and the representative did follow the ground-truth loop (Figure S3 g). Although the Fermat distance failed in this setting and the effective resistance performed well, their widest gap scores were both high.
clearly noise feature (Figure -3)-e). Conversely,
For these reasons, prefer hole detection score the widest gap score.
E.2 Cycle matching
The need to distinguish between signal and noise features in persistence diagram motivated Re- ani and Bobrowski [44] to develop cycle matching, a technique that quantifies the correspondence of features two persistence diagrams by prevalence score in [0, 1]. True signal corresponds to features that reappear with high prevalence in variations of the data obtained, e.g., via resampling.
This approach to detecting the true topology of figh--iimensional data is orthogonal to our exploration of different input distances. Indeed, cycle matching can be combined with any distance.
An important downside to cycle matching is the need for resampling. In an exploratory context, the true data distribution not known. Instead, Reani and Bobrowski (64) suggest to either bootstrap existing finite dataset or sample from kernel density estimate. Unfortunately, for high-dimensional data both approaches are problematic. Bootstrapping high-dimensional data error-prone [T8] and persistent homology of bootstraps is biased because repeated points effectively decrease the sample
22

---

Circle (1 loop)
Eyeglasses loop)
Linked dircles (2 loops)
Widess gap score
1.0
Fermat
DTM
Eff. resist.
Diffusion
0.0
0.1
0.3
0.00
0.05
0.10
0.15
0.0
0.1
0.2
0.3
Noise
Noise sid
Noise sld
d PD Fermat
Representative Fermat
f PD Eff Res
g Representative Eff Res
Doah
Doath
Birth
Birth
Figure S3: Top row: Widest gap score on the three 1D toy datasets. We used 10 random seeds here. Spectral methods outperformed Fermat, DTM, and Euclidean in this score. Bottom row: Example persistence diagrams and representatives for the toy circle with = 0.3 with Fermat distance and effective resistance illustrate that despite the high score for both, Fermat distance actually failed.
sigma: 0.1
sigma: 0.2
sigma: 0.25
sigma: 0.3
5 sigma: 0.35
1.0
manches <3 matches
provilence
0.6
0.
0.0
10
10
cycles
cysles
cycles
kyo 0s
matched cycles
Dodt
Death
Dealt
Bith
Bith
Bith
Birth
Birth
Figure S4: Results for cycle matching with the Euclidean distance noisy circle in R with noise level a. Top row: Prevalences of the most prevalent cycles. Means and standard deviation over three seeds. Color indicates whether the cycle matched for all three random seeds not. Second row: Persistence diagrams with the most prevalent features highlighted. Third row: Representative of the most prevalent feature overlaid 2D PCA of the data.
size 71]. Kernel density estimation requires a prohibitively large sample size in high dimensions 86 chapter 6.5).
Nevertheless, as a proof concept, we explored cycle matching with the relatively fast r ripser- implementation of Marcia-Redonde et al. [30]. The authors report runtime of about 90 minutes for a dataset of sample size n = 1000 (their Table 3) and in our experiments we experienced even longer run times. As the result, this implementation of cycle matching was about 450 times slower than approach (Table S5 For this reason, we only used three resamples.
Garcia-Redonde et al. [30 's implementation accepts datasets point clouds and implicitly assumes the Euclidean distance. Therefore, in this experiment we only used Euclidean distances and diffusion distances, which can be realized as Euclidean distances (Eq, 4.. We computed prevalences of matched cycles on the noisy circle with = 1000 points in R for Gaussian noise of standard deviations [0.1, 0.2, 0.25, 0.3, 0.35].
23

---

sigma: 0.1
sigma: 0.2
sigma: 0.25
sigma: 0.3
sigma: 0.35
1.0-
0.8
<5 matchha
provalenoe
Most prevalent
0.8
0.4
0.-
0.0
5
4
10
mutched sycles
manched cycles
matched cycles
matchedd eye 166
matcched cycles
Don
Duali
Deam
Deein
Duali
Birth
Birh
Bitth
Birth
Figure S5: Results for eycle matching with the diffusion distance (h: 15, 1 8) on a noisy circle in Re50 with noise level a. Top row: Prevalences of the 10 most prevalent cycles. Means and standard deviation over three seeds. Color indicates whether the cycle was matched for all three random seeds or not. Second row: Persistence diagrams with the most prevalent features highlighted. Third row: Representative of the most prevalent feature overlaid on a 2D PCA of the data.
Cycle matching with the Euclidean distance did not reliably identify the ground-truth feature for sigma 0.1 (Figure (S4). In all experiments with the Euclidean distance and 0.1, the feature with the highest prevalence did not correspond to the ground-truth loop.
For a 0.2, 0.25, we also checked the prevalences of the ground truth cycle. For a = 0.2 the ground truth cycle was not matched for any of the three resamples, leading to a prevalence of 0. For o = 0.25 the ground-truie truth eycle had the average prevalence of 0.1 + 0.1, much lower than the cycle with the highest prevalence.
One might hope that the cycles that do get matched for all resamples are true topological features, even if their prevalence values are low. Indeed, for a = 0.1 only the correct cycle was matched for all three resamples. However this heuristic did not work either because for a E {0.2, 0.25, 0.3) no cycle was matched for all three resamples, while for a = 0.35 there was a cycle matched for all three resamples (not shown in Figure S4 because it was not among the 10 most prevalent ones), but it did not encode the ground-truth feature (and its prevalence 0.1 + 0.1 was very low).
The fact that most cycles were not matched for all resamples led to high standard deviations of the prevalences. The reason for the high mean prevalences for a >> 0.1 was that some noise cycles got matched with very high prevalence (sometimes > 0.9) for one or two of the resamples. For the same reason, the prevalence of the ground truth cycle for a 0.1 was not much higher than the second highest prevalence. Increasing the number of resamples may help, but would make the procedure even more computationally expensive.
Overall, we conclude that cycle matching is not only very slow, but also does not alleviate the curse of dimensionality for persistent homology. In contrast, our spectral methods produced near-perfect loop detection score until a = 0.3 (Figure T
That said, cycle matching can serve as alternative performance score. We applied cycle matching to the diffusion distance (Figure S5) and found that
1. the maximal prevalences were larger than for the Euclidean distance for < 0.3,
2. the cycle with maximal prevalence always represented the ground truth loop,
clear outlier among all prevalences for < 0.3, 4. the cycle representing the ground truth feature was always matched for all three resamples and was the only one matched for all three resamples for < 0.3.
3. the prevalence of the correct cycle
This confirms the superior performance of spectral methods for detecting topology in high- dimensional settings.
24

---

Effective resistance as a spectral method
In this section, derive explicit spectral embedding realizing the square root of von Luxburg al. [81's corrected effective resistance. also show that is not necessarily a proper metric.
Let us recall the notation from Sections 5 6 extended to weighted graphs. Let G be a weighted connected graph with n nodes. We denote by A (atj)..f=1... the weighted adjacency matrix whose entries a:j azz equal the edge weight of edge ij if edge ij is part of the graph and zero otherwise. We further denote by D diag(d,) the degree matrix, where de = E3 Dij are the node
degrees. We define vol(G) E, di Let further A D AD and T, 1 A be the symmetrically normalized adjacency matrix and the symmetrically normalized graph Laplacian. Denote the eigenvectors of I by ui,....: Uh and their eigenvalues by M1.-... Mrn in increasing order. The cigenvectors and eigenvalues of A are .i,.... Un and - MI...., Pm.
Definition F.1. The naive effective resistance distance between nodes i and is defined as
jell 1
vol(G) (Hi + Hjz),
(19)
where Hi is the hitting time from i to j. i.e., the expected number of steps that random walker starting at node takes to reach node j for the first time.
The corrected effective resistance distance between nodes i and is defined as
1 dj
Oij d,d,
0g
a
+
(20)
dj
d
d3
The following proposition refines Proposition 4
81.
Proposition F.2. The corrected effective resistance distance d. between nodes i and j can be computed by di = l|egft est11 where
1
U2
1 - My
U2
unik
dz
12
Un
Proof. By the fourth step of the large equation in the proof of Proposition 2 in 82 we have
vol(G) Hij = dj + Abm - b.)) + (ASTi u A b,)),
(21)
where b, e D- è with é being the i-th standard basis vector.
Adding this expression for ij and ji and using the definition of d we get
Jell 1
1
d; d, Gol (Hij Hz²) d, d
(22)
(bj, A (b₃ b))) + (6, A (b:-b:) b;))
(23)
A Ti A - bz))
(24)
2=2 Mr
(A u. 1 b,))
(25)
(by 2=2 Hr
bi, A - -bi)
(26)
(A (b; - by), 24, Aby - b.))
(27)
2 Hr
25

---

For ease of exposition, we treat the two terms separately. By unpacking the definitions and using the symmetry of D, we get
(by bi, A
b.)) (D- : (ē) E,), A
D D- (ē; - Ex))
(28)
((ê, ē.), D AD- - -+,)
(29)
Ojj 2 Oij
+ au
(30)
d3 d,dj
df
Since the u, are eigenvectors of A with eigenvalue 1 - He and A is symmetric, we also get
(ASm(bs (b, - bi), ur u. A b;))
(31)
Mr
71
1
(b) - big (Asm (A up) T (b3 - b.)))
(32)
1
(bg bi, (1 1r) ((1 - pr)jer) T (b, bi))
(33)
Mr
pr T D 1 (e, - -
(34)
Vir
2
1
1 1- Hr uni
1 Mrr
Und
(35)
Vfr
2=2....
de
Pr
= lle;- - eil
(36)
Putting everything together yields the result
1 = jen
1
aij
0 aj
(37)
d
dj
d,d, di dz
Ojj
2
Oij
+
+
|1e
e:l1 + 2 Aij
0si
Oj
(38)
d3
d,dj
d
d.dj
d
df
=
(39)
The corrected version of effective resistance and diffusion distances are, in general, not proper metrics, unlike the naive effective resistance (32 Corollary 2.4.]. We show this by giving concrete examples of graphs where the metric axioms for these distances do not hold.
Proposition F.3. Neither corrected effective resistance nor diffusion distances beiween distinct points are necessarily positive. Moreover, corrected effective resistance does not always satisfy the triangle inequality.
Proof. Consider the unweighted chain graph with three nodes (Figure S6 left). The uncorrected effective resistance between the first and the last node is 2. So the corrected effective resistance between these distinct nodes is 2 - 1 - = O. On the same graph, the random walker is necessarily at node after one step, independent whether it started at node 0 or 2, so the diffusion distance with f t= between these two distinct nodes is zero.
Consider now an unweighted graph with 5 nodes, the first three of which form a triangle and the other two a chain connected to the triangle (Figure S6 right). Then
2
7
2
joft
aeft = 2; dfT
deff
(40)
02
3'
6
6'
3
We see that the triangle 0, 2, 4 violates the triangle inequality
2 + do +
rell =
xll
6
3
6
24-
26

---

2
3
4
Figure S6: Counterexample graphs for Proposition F33
The square root of corrected effective resistance does satisfy the triangle inequality and can also be used as input to persistent homology. This amounts to taking the square root of all birth and death times found with the corrected effective resistance as computing persistent homology commutes with strictly monotonic maps, and hence does not strongly affect the loop detection performance of corrected effective resistance (Figure S20). We therefore believe that it is not problem for our persistent homology application that corrected effective resistance fails to satisfy the triangle inequality.
G Effective resistance integrates diffusion distances
First, we describe the connection between diffusion distances and naive effective resistance commu- nicated to by Mémoli [54). To the best of our abilities, we could not find another reference. We use the same notation as in Section and Appendix [F]
Below, we speak of diffusion distances half-integer time points, although the random walk analogy does not extend to half-steps. What we mean is inserting a half-integer value of f Eq. (4)
Proposition G.1. The sum of the squared diffusion distances over all time points t/2 for t t= 0, 1, 2,... equals the naive effective resistance. Formally, if G is a connected and non-bipartite graph, we have
diff (t/2)²
jeft
(41)
GGl
Proof. This an application of the geometric series. Since not bipartite, the largest eigenvalue Nh, of its Laplacian Lymm is smaller than 2 [17 Lemma 1.7]. Recall that by Eq. 4 the diffusion distance for t diffusion steps is given by
1 Vd.
dij (t) vol c
(t) chill( (t)ll, where cttll (f)
((1 H2) u0'u2,. u2........ (1 Hen) J'un.))
(42)
and that the naive effective resistance is given by
Jost
25t 12,,
where 2:
1
( 1
u2,6
Und
(43)
Vd,
V122
V
We compute
diff (1/2)2
Σ
30
Σ
n
(1
2-1/2 22)
m1)
U1.5
U.
2
(44)
vol(G)
Vdl
v dj
1=
1=0 1
n
80
(1
m1)
(45)
Vd.
dd
1=0
M1,
W.
1
(46)
Vd
Vdz
(1 p4)
Uijj
2
(47)
14
VJ.
da
1=2
||
2 12
(48)
jell
(49)
27

---

The application of the geometric series is justified as E (0,2) for i = ....., by assumption on G, so that [1 prl
Similarly, we show the corresponding result for the corrected version of effective resistance. Corollary G.2. The sum of the squared diffusion distances over all time points f/2 t = 2.3.... equals the corrected effective resistance. Formally, if G is connected non-bipartit graph, we have
dift (t/2)² dij
(50)
Gol
and
plit (0)² 4
1 1 dj
Mitt (1/2)²
0g d?
4j
aij
(51)
GG)
di
vol
d²
d.dj
Proof. For x E (-1,1), 1), starting geometric series at the m-th term yields Zt=m Proposition
x²
1-x By
x
R2
we have
2
2
fff 1y
12)2
U1
U1 Vd.
(52)
Vdz
By the same argument in the proof of Proposition G.I this shows the first part of the Corollary.
The statement for diffusion distance after = steps is an easy computation from the original definition, Eq. (2):
pill dij
(0) vol (G) P))) u.s
= vo)
) D-0.5 0.5
1
vol(G)
(53)
d
d
where é is the i-th standard basis vector. The last part follows from the definition of the corrected effective resistance as
- - 1/d, + 2a.y/(d,d)) -aj//-aj/dd
(54)
and the expression of the naive effective resistance as full geometric series of squared diffusion distances in Proposition G.I
H Diffusion pseudotime
Diffusion pseudotime (DPT), ddl 36 also considers diffusion processes of arbitrary length. There dps
are several variants diffusion pseudotime [36 for
88
They are computed as d. = ||e dpi
{j
dpt -11
1
122
Pn
(55)
112
The difference is the ......, Un ss In the original publication (36), they were the normalized eigenvec- tors of the random walker graph Laplacian D L Dž. These given by D $ / DDD &ull- Wolf et al. (88) introduced a version using the eigenvectors of the symmetric graph Laplacian Lsym so that uy Closest to the corrected resistance distance is the case where ez = D- it are non-normalized. We refer these three versions as "rw", "sym" and "symd".
The only difference between the "symd" version of DPT and corrected effective resistance is that the former decays eigenvalues with (1 /4//11, while the latter decays it with (1 p1////i, (ii that DPT decays large eigenvalues more strongly than corrected effective resistance (Figure 5)
Similar to effective resistance, one can also write diffusion pseudotime in terms of diffusion distances. But for diffusion pseudotime the diffusion distances corresponding to higher diffusion times contribute more.
28

---

Proposition H.1. Let G be connected, non-bipartite graph. We can write the "symd" version of DPT as
d
(t/2)²
(56)
Gol
Proof. We will use that for a real number with [x| the derivative of the geometric series
tx
(1 - x)2
t=1
Multiplying with x², we get
x²
tx
Σ 1=2
(t - 1)x²
(57)
(1 x
1=1
By assumption on G, for all eigenvalues fn we have |1 - Wl < 1 for | = 2.... n. so that the above equation holds for all x fn with 2,..., n. Together with the "symd" expression for diffusion pseudotime, we compute
pi) 2
Ap
U1
Pi
d
/dj
1=2
1)(1 - -m)²
W1
W.
Vdz
vd
1=2
1=2
Σ 1-2
(1 1) Σ 11) 111 )1) 2.(1/2)
U1 Vdl
U1 dl
1=2
Σ (1
Mitf (1/2))
(58)
1=2
H.1 Performance of diffusion pseudotime and potential distance
Here we compare the spectral methods of our main benchmark to the three versions of DPT and potential distance.
For DPT, we used all three versions defined above and used k (15, 100) nearest neighbors.
The potential distance underlies the visualization method PHATE (66) and closely related to diffusion distance. It is defined by
(i.j) log( P!..) - log Pf,)
where the logarithm is applied element-wise. We used k E (15, 100) and / E (8, 64).
Overall, all spectral methods performed very similarly on the ID datasets circle, linked circles, and eyeglasses (Figures S7 S8). as well as on the single-cell datasets (Figure (S9).
I Details on the distances used in our benchmark
Let .I,..., Fn E RRd We denote pairwise Euclidean distances by dej = ||,, - syyl- the nearest neighbors of in increasing distance by Tig:..., Fi,, and the set containing them by distances rely on the symmetric k-nearest-neighhor (sANN) graph. This graph contains edge ij x;; among the & nearest neighbors of z, vice versa.
N,. Many
29

---

Potential
DPT
Eft resiet.
Diflusion
ei
0.25
9.00
1.00
Unted dades
0.00
0.0
Bygezees
0.75
0.50
0.2
0.00
0.06
0.10
0.15
0.00
0.06
0.10
0.15
0.00
0.05
0.10
0.15
Nolse sid
Nose sid o
Nolse std a
Nosse std #
Naise sid
DPT sym 15
sym
Difusion Diftusion 2- 15, 64
Potentid = 100,1
K
Potential k = 15
DPT symd km 100
15
15
Effective
Effective
resiilanio k-
Difuuiio -- 200, c- 64
Upp. Eig. 15,0
Eig.
Putential k 100.0 64
DPT nw w. 100
reststance = 100
Lap. Elg. 15, a
Figure S7: Comparison of all spectral methods the noised versions of the circle, the linked circles, and the eyeglassed dataset in R2:0
Circle
Linked circles
Eyeglasses
0.2
0.3
0.00
0.05
0,10
0.15
Noise
Diflusion k- 15,
Eusideen
DPT symd k 100
Polential k- 100, 1-0,t=8
Effective resistance k 100
Lap.
15, d=
Figure S8: Best hyperparameter choices for the methods Figure S7 very similar performance.
All spectral methods reach
Fermat distances
For p 2 the Fermat distance is defined as
d (iz) inf Σ
d
(59)
(uv)ET
where the infimum is taken over all finite paths from x; to 2, in the complete graph with edge weights dy.. As speed-up. Fernández et [26] suggested to compute the shortest paths only on the KNN graph, but for our sample sizes we could perform the calculation on the complete graph. For p 1 this reduces to normal Fuclidean distances due to the triangle inequality. We used p E 72,
DTM distances The DTM distances depend three hyperparameters: the number of nearest neighbors k one hyperparameter controlling the distance to measure p, and finally a hyperparameter & controlling the combination of DTM and Euclidean distance. The DTM value for each point is given by
E | [
Fú. lP/k if p oc else.
dtm;
(60)
These values combined with pairwise Euclidean distances to give pairwise DTM distances:
max(dtm; dtm,)
if [ - xzl S / /dmm - dimf
DTM (iz)
(61)
else,
30

---

$100
Malaria
Delection scare
0.75
0.5
0.25
0-
1.0
Neurosphere
Detection scom
0.75
0.25
0
9.0
Hippocampus
Delection scare
0.75
0.5
0.25
9.0
Neural JPCs
Dolection score
0.5
0.25
HeLa2
9.0
Delacioon scone
0.5
0.25
0
Pancreas
Deteclion scone
1.0
0.75
0.5
0.
Eucidean Carreaaton
DPT sym k 100
DPT symd == 15
DPT syma k 100
DPT rak = 15
DPT nw k 100
Effective recistance 1.00
Diffusion = 15, =
Difiaioo k 100, 8
Eig. = -=1 15,8=2 =
Lap Eg 15. 1-.0-5 8-5
== 10
Potentia 15, =
Patental k= 100, =
DPT sym =
Polaniial 100,
Effecive resistance
Difkaion 15,
Lap Ea ==151..0
Patenial
Diflusion
Figure 89: Comparison of all spectral methods the single cell datasets. They all achieve similar performance.
31

---

where 0 is the only positive root of V dum + v/B dum} = dej. We only considered the
values & E {1, (,), for which the there are closed-form solutions:
(dtm; + dtm, + dzj)/2
if Ç 1
0 == V ((dim; ((dim: d dit) d
((dtm, - dtm,)² 2 dit) (2dgz) (2des)
if g 2 if E
(62)
max(dtm;; dtm, dij/2)
We used & E {4, 15, 100). E {2, x)) and & E 2,
The original exposition of -TMdbased filtrations [2] only considered the setting p 2, while DTM has been defined for arbitrary p 2 1 [14). We explore an additional value, = oc, in order to possibly strengthen DTM. Indeed, in several experiments it outperformed the p 2 setting.
Moreover, Anai al. actually used a small variant of the Vietoris-Rij complex on the above distance d (k. {): They only included point in the filtered complex once the filtration value exceeds dim,- This, however, only affects the 0-th homology, which we do not consider in our experiments.
Core distance given by
The core distance is similar the DTM distance with oo and p oc and is
(ij) max(dej, ||,, Fig 1|,, Iza II)
(63)
We used & E (15, 1003.
t-SNE graph affinities
The t-SNE affinities are given by
Pily + Pjss
Vyli
exp (I 12,1-1,11180 22,12/(207))
if E N, else,
Pij
2n
POls
Ekps UNN"
Kyls
(64)
where σ; is selected such that the distribution Pjjs has pre-specified perplexity p. Standard implemen- tations of t-SNE use = 3p. We transformed t-SNE affinities into pairwise distances by taking the negative logarithm. Pairs i; and zy with Pıj = 0 (i.e. not in the &NN graph) get distance co. We used p E {30, 200, 333].
UMAP graph affinities
The UMAP affinities are given by
[ exp - (d,j - pi)/o:)
for fd. (65)
Mig - Mil + Pyle - Mayyslis
Pyle
0
else,
where 14 || z,, is the distance between 2; and its nearest non-identical neighbor. The scale parameter d; is selected such that
Σ exp ( (-dd(zz, po)/ = logg(k).
(66)
As above, to convert these affinities into distances, we take the negative logarithm and handle zero similaritics as for the t-SNE case. We used & e {100, 999]; one of the void-containing datasets.
15 resulted in memory overflow on
Gardner et al. [3 and Hermansen al. 40 first used these distances, but omitted μ4, which we included to completely reproduce UMAP's affinities.
Note that distances derived from UMAP and I-SNE affinities are not guaranteed to obey the triangle inequality.
Geodesic distances We computed the shortest path distances between all pairs of nodes in the SANN graph with edges weighted by their Euclidean distances. We used the Python function scipy wwwps/ssasseeesapa.....o wsgraph..sortesseeeeee shortest_pathh We used k {15, 100).
UMAP embedding We computed the UMAP embeddings embedding dimensions using 750 optimization epochs, sin_dist of 0, exactly computed & nearest neighbors. and PCA initialization. Then we used Fuclidean distances between the embedding points. We used UMAP commit a7606f2. We used & E {15, 100, 999).
32

---

t-SNE embedding We computed the t-SNE embeddings in 2 embedding dimensions using openTSNE [63] with default parameters, but providing manually computed affinities. For that we used standard Gaussian affinities on the skNN graph with k 3p. Then we used the Fuclidean distances between the embedding points. We used perplexity p E (8,30, 33.3).
For UMAP and t-SNE affinities as well as for UMAP and t-SNE embeddings we computed the SANN graph with PyKeOps [13] instead of using the default approximate methods. The UMAP and t-SNE affinities (without negative logarithm) were used by the corresponding embedding methods.
Effective resistance We computed the effective resistance on the s&NN graph. Following the analogy with resistances in an electric circuit, if the skNN graph is disconnected, we computed the effective resistance separately in each connected component and set resistances between components to co. The uncorrected resistances were computed via the pseudoinverse of the unnormalized graph Laplacian (2
J.ft = 21,, + 35'
(67)
where 21 is the ij-th entry of the pseudoinverse L of the unnormalized sŁNN graph Laplacian L == A- The pseudoinverse inverts all non zerozero eigenvalues. Denote the eigenvalue decomposition of L by L VAVT, where V (UI..... u,)) is the matrix of cigenvectors of L and A is the diagonal matrix of their eigenvalues A An- Then Lt VAtVT, where At is the diagonal matrix with entry 1/X; if X > 0 and 0 otherwise. We can use this to derive a similar coordinate expression as in Eq. [ but based on the unnormalized graph Laplacian (288) 4.B]). Let e; be the i-th standard basis vector
",,''
c.fy
= 11 21,, + +1,
= (ei (e)) -ej
(ei -e,) TAiV -e) (VAIVTe-VAA
(VAiIT a vAiVTe)) (VATTT)-AAVVT))
-1le5h egtl11 where
20ff
U2
Un
(68)
Ama
For the corrected version, we used
Juft
1 dj d,d, de
2
0ij
Ojj
(69)
For the weighted version of effective resistance, each edge in the skNN graph was weighted by the inverse of the Euclidean distance. We experimented with the weighted and unweighted versions, but only reported the unweighted version in the paper as the difference was always minor. We also experimented with the unweighted and uncorrected version and saw that correcting is crucial for high noise levels (Figure $20). We used k E (15, 100).
Both forms of the effective resistance can be written squared distances between certain embedding points (5). (6). Nevertheless, the uncorrected effective resistance is a proper metric [32 Corollary
2.4.J. The corrected version in general is not a proper metric (Proposition
Diffusion distance by equation (2), i.c.,
We computed the diffusion distances on the unweighted s&NN graph directly
dtt (i.j) (vol( - D
(70)
Note that our sKNN graphs do not contain self-loops. We used E (15, 100} and I. E (8, 64). It is clear from the above definition of the diffusion distance that it satisfies the triangle inequality, but it can fail be positive on distinct points (Proposition F3
Laplacian Figenmaps For an sNNN graph with K connected components, we computed the K + d cigenvectors ui,..., d of the normalized graph Laplacian y of the s&NN graph and discarded
33

---

Euclidean
Fermal
Core
Goodesics
I-SNE graph
dmax
UMAP graph
t-SNE
UMAP
Eff. resist.
k
Diffusion
Lap. eig.
Figure S10: Visualization of all distances on the noisy circle in R with 0.25. All scatter plots are the 2D PCA of the 50D dataset. The colors indicate the distance to the highlighted point.
Euclidean
Fermat
DTM
d
Core
Geodesics
t-SNE graph
dmax
UMAP graph
I-SNE
UMAP
j
Eff. resist.
Diffusion
Lap. eig.
Figure S11: Visualization of all distances on the noisy circle in 10 with o = 0.25. The scatter plots 2D multidimensional scaling embeddings using the respective distances. The colors indicate the distance to the highlighted point. For this random seed the t-SNE embedding tore the circle apart.
the first K cigenvectors Mi...., ukk which are coding for the connected components. Then computed the Euclidean distances between the embedding vectors ef = (ux+1,i, ((K+dd)a)
We used & = 15 and embedding dimensions d E {2, 5, 10).
Alternatively, one can compute Laplacian Eigenmaps using the un-normalized graph Laplacian L. We tried this normalization for but obtained very similar embeddings.
Diffusion pseudotime Diffusion pseudotime [36] also integrates the different time scales of the diffusion distance, but on the level of the transition matrices, rather than on the level of the distances themselves (Proposition G.2 There are multiple variants of diffusion pseudotime. They are all
computed as ddot ||e,00 Upt for
(1 112
pn
U2
Unzi
(71)
Pn
The difference the "i,..., Un 's. In the original publication 36), they the normalized eigenvec- tors of the random walker graph Laplacian + yym Dē. These are given by v; -D- = +u, &u:ll- Wolf et al. (88) introduced a version using the eigenvectors of the symmetric graph Laplacian L so that uy- Closest to the corrected resistance distance is the case where v; = D- fu; are non-normalized. We tested all three versions, which we refer as "rw". "sym" and "symd" version. We used & {15, 100} nearest neighbors.
34

---

Circle
Eyeglasses
Linked
Sphere
0
2
2
2
-1
-2.5
0
0.0
2.5
2.5
Figure S12: Synthetic, noiseless datasets with 000 points each.
0=0.0
0=0.5
0=0.1
0=155
0=02
0
h c=0.
0
m
p
q
d 50 MDS
Figure S13: Circle with Gaussian noise of different standard deviation a. a-i. Original data in ambient dimension d j-q. Multidimensional scaling of the Euclidean distance of the data in ambient dimension d = 50.
Potential distance The potential distance underlies the visualization method PHATE [56] and is closely related to the diffusion distance. It is defined by
d j) log(P!.) log log(( P1)))
where the logarithm is applied element-wise. We used & E (15, 100} and E {8, 64).
For all methods, we replaced infinite distances with twice the maximal finite distance to be able to compute our hole detection scores.
We illustrate the distances used the main benchmark in Figures STO and SII
J Datasets
J.1 Synthetic datasets
The synthetic, noiseless datasets with n = 000 points each are depicted in Figure S12
Noised
versions of the circle for ambient dimensions d 2, 50 are depicted in Figure SI3
Circle
The circle dataset consists of n points equidistantly spaced along a circle of radius 1.
Linked circles The linked circles dataset consists of two circle datasets of n/2 points each, arranged such that each circle perpendicularly intersects the plane spanned by the other and goes through the other's center.
The eyeglasses dataset consists of four parts: Two circle segments of arclength + 2.4 and radius r = centered units apart with the gaps facing each other. The third and fourth part are two straight line segments of length 1.06, separated by 0.7 units linking up the two circle segments. The circle segments consist of 0.425m equidistantly distributed points each and the line segments consist of 0.075m equispaced points each. As the length scale of this dataset is dominated by the bottleneck between the two line segments, we only considered noise levels a E [0, 0.15) for this dataset, at this point the bottleneck essentially merges in R
Eyeglasses
35

---

Sphere r r=
The sphere dataset consists of n points sampled uniformly from sphere S with radius
The torus dataset consists of n points sampled uniformly from a torus. The radius of the torus' tube was r I and the radius of the center of the tube was R = 2. Note that we do not sample the points to have uniform angle distribution along the tube's and the tube center's 's circle, but uniform on the surface of the torus.
Torus
High- digh--dimensional noise We mapped each dataset to IR for d E [2, 50] using random matrix V of size d x 2 or d x 3 with orthonormal columns, and then added isotropic Gaussian noise sampled from (0, (I)) for E [0, 0.35).
The orthogonal embedding in I does not change the shape of the data. The procedure is equivalent adding d or d 3 zero dimensions and then randomly rotating the resulting dataset in IR..
J.2 Single-cell datasets
We depict 2D embeddings all single-cell datasets in Figure S14
Malaria The Malaria dataset 43 consists of gene expression measurement of 5 156 genes obtained with the modified SmartSeq2 approach of Reid et al. [65] in n - 187 cells from the entire life cycle of Plasmodium berghei. The resulting transcripts were pre-processed with the trimmed mean of M-values method the pre-processed data from https: wwt http:///wwi.//aaaaaaaaaaaaaaaaaa
(69] We obtained
pnprressin_Matriceeee www__Matricsssssee htt.Maariicss//aaattaa////////// http://asasaeeooooooooooououttee www.ooooonns.ccoommmmmmmmommm csv. zzip The data is licensed under the GNU GPLv3 licence.
The UMAP embedding shown in Figure follows the authors' setup and uses correlation distance as input metric, & = 10 nearest neighbors, and a ain_dist of 1 and spread of 2. Note that when computing persistent homology with UMAP-related distances, used our normal UMAP hyperparameters and never changed min_miiimm dist or spread.
The Neural IPC dataset (8] consists of gene expressions of n = 26 625 neural IPCs from the developing human cortex. seVI 50 was used integrate cells with different ages and donors based on the 700 most highly variable genes, resulting in d = 10 dimensional embedding. Braun al. [8] shared this representation with for a superset of 297 927 telencephalic exitatory cells and allowed us to share it with this paper (MIT License). We limited our analysis to the neural IPCs because they formed particularly prominent cell cycle.
Neural IPCs
Neurosphere The Neurosphere dataset [89] consists of gene expressions for n = 805 cells from the mouse neurosphere. After quality control, the data was library size normalized and log, transformed. Seurat was used to integrate different samples based on the first 30 PCs of the top 2 000 highly variable genes, resulting in a 12 805 x 2 000 matrix of log, transformed expressions. These were subsetted to the genes in the gene ontology (GO) term cell cycle (GO:0007049). The 500 most highly variable genes were selected and PCA computed to d = 20. The GO PCA representation was downloaded from pattps://zenne http://ennoooorrrrrrrrreoooe licensed under CC BY 4.0.
is
Hippocampus
The Hippocampus dataset 89 consists of gene expressions for n 9 188 mouse hippocampal NPCs. The pre-processing was the same as for the Neurosphere dataset. The GO PCA representation was downloaded from httth:tt///teeeeee http://ooooogeeerr/////111111111 It is licensed under CC BY 4.0.
HeLa2 The HeLa2 dataset 722 89 consists of gene expressions for 2 463 cells from a human cell
line derived from cervical cancer. After quality control, the data was library size normalized and loga transformed. From here the GO PCA computation was the same as for the neurosphere dataset. The GO PCA representation was downloaded from htttp:///eenddoogg//eo//////1111
HeLa2. qs It is licensed under CC BY 4.0.
36

---

Malaria
Neurosphere
Hippocampus
HeLa2
Pancreas
Neural IPCs
Cell
Liver slage
Trophczoite
Female gamelocyye
Injected sporozolle
Male gametocyle
Oocyst
G2
G1.S
Merizoite
Bolus
Ring
Okineteloccyst
Schizont
Gland sporozolte
G2 M
NA
M.G1
Figure $14: 2D embeddings of all six single-cell datasets. f. UMAP embeddings of the Malaria 43 and the Neural IPC datasets [8]. We recomputed the embedding for the Malaria dataset using UMAP hyprrarrameters provided in the original publication, and subsetted an author-provided UMAP of a superset of telencephalic exitatory cells the Neural IPC. The text legend refers Malaria cell types. b-e. 2D linear projection constructed to bring out the cell cycle ('tricycle embedding" ' [8) of the Neurosphere, Hippocampus, HeLa2, and Pancreas datasets. We used the projection coordinates provided by Zheng et al. [89].
consists of gene expressions for 3 559 cells from the mouse endocrine pancreas. After quality control, the data library size normalized and log, transformed. From here the GO PCA computation was the same as for the neurosphere dataset. The GO PCA representation was downloaded from It is licensed under CC BY 4.0.
Pancreas The Pancreas dataset 3 89
K Hyperparameter selection
For each of the datasets and hole dimensions, showed the result with the best hyperparameter setting. For the synthetic experiments, this meant the highest area under the hole detection score curve, while for the single-cell datasets meant the highest loop detection score. Here, we give details of the selected hyperparamters.
For Figure we used effective resistance with A: 100 in Figure 6
For Figure 6 we specified the selected hyperparameters directly in the figure. For the density-based methods, they were p 3 for Fermat distances, k = 4, 2, = oo for DTM, and A: = 15 for the core distance. For the graph- methods, they
100 for the geodesics, k 100 for the UMAP graph affinities, and = 30 for t-SNE graph affinities. The embedding- based methods used k 15 for UMAP and p 30 for t-SNE. Finally, as spectral methods, we selected effective resistance with & = 100, diffusion distance with & = 100, 8 and Laplacian Eigenmaps with d 2.
The hyperparameters for Figure 7 are given in Table SI
In Figure 8 we specified the hyperparameters used. They were the same as for Figure 6 save for the diffusion distance, for which we used & = 100, / 8. This setting had better performance for d
and only marginally lower performance than 15, t in higher dimensionalities.
we selected DTM with & 15, 30, E oc, effective resistance with 15 and diffusion distance with A = 15, t = 64. They are the same for the Malaria dataset in Figure 10
For Figure 9
The selected hyperparameters for Figure 10 can be found in Table S2
The hyperparameters for Figures S10 and STT are the same as those used in Figure The hyper-
parameters for Figure S3 are given in Table S3 and those for Figure S16 in Table S4 All other
supplementary figures either not depend on hyperparameters or detail them directly in the figure or the caption.
37

---

Table S1: The optimal hyperparameters that were selected in Figure For torus and sphere, we consider the case of loop detection (H1 and void detection (H2) separately.
Dataset
Fermat
DTM
Eff. res.
Diffusion
Circle
3
k 4, p 2, =
k = 100
k 15, t = 8
Eyeglasses
p
h 100, 2.
k 15
15, t 64 k
Linked circles
p 7
k 15.p= 20, =1
k == 15
15, t = 8
Torus H1
p = 2
4,p 2, X
K 100
15, f
Sphere H1
p 2
k 100, 2
K == 15
K 100. t 64
Torus H₂
p 2
4.p 2, X
K
15, t
Sphere l12
p 2
& 4, 2,
K 100
K 100,
Table S2: The optimal hyperparameters that selected in Figure 10 For DTM report the best
setting without thresholding (because none of the DTM runs passed our birth/death thresholding, so all 8m scores for all parameter combinations are zero).
Dataset
Fermat
DTM
I-SNE
UMAP
Eff. res.
Diffusion
Lap. Eig.
Malaria
p == 2
15
p= = 8
k= 15
== 15
h: = 15
d=
p 0C
64
00
Neurosphere
= 2
100
30
k = 999
k = 15
h = 15
d= 2
p 2
= 8
Hippocampus
p
100
P 8
h: == 15
h: = 100
k 15
d=
=
8
2
Neural IPC
2
P 30
1: = 15
h: 100
k: = 15
d=
= XC
= 64
HeLa2
=
P 30
R: 100
h: 100
A 100
d=2
2
= 64
CO
Pancreas
7=7
100
P. 8
k 100
k: ==4
k 15
d=5
2
t = 64
& DO
Hyperparameter sensitivity
While all distances other than the Euclidean distance have hyperparameter' and we show results for the best hyperparameter setting in most figures, hyperparameter selection does not pose serious problem for diffusion distance and effective resistance. We only tuned hyperparameters very mildly for these methods (4 settings for diffusion distances. only for effective resistance, as opposed to 24 for the competing method DTM). Moreover, we conduced more fine-grained sensitivity analysis and found the performance of diffusion distances and effective resistances to be robust the exact value of their hyperparameters. For this sensitivity analysis we computed the area under the noise-level / detection score curves for the circle, the interlinked circles and the eyeglasses dataset in 50 ambient dimensions with
4, 15, 30, 45, 60, 75, 90, 105, 120, 135, 150 nearest neighbors and = 4, 8, 16, 32, 64, 128, 256 diffusion steps. For all but the most extreme hyperparameter values both effective resistance and diffusion distances strongly outperformed the Fuclidean distance (Figure (15). We observed trade-off between the optimal number of neighbors l and diffusion steps t for the diffusion distance, since both control how fast the diffusion can progress across the dataset.
38

---

Table S3: The optimal hyperparameters that were selected in Figure S3
Dataset
Fermat
DTM
Eff. res.
Diffusion
Circle
p
4,p - 2, k 100
k 15, (
Eyeglasses
7
-. 2, k == 15
k == 15, f = 8
Linked circles
p = 2.6 =1
k 100
15, t
Table S4: The optimal hyperparameters that were selected in Figure $16
Ambient dimension
Number of
Fermat
DTM
Effective resistance
Diffusion
outliers
2
0
p 2
k: 100, 00, 2
k 100
k 100, t 64
2
50
p = 7
k 100,p= oc, {
100
k 100, 64
2
100
p = 7
k 100. oc, = 2
k 100
K 100, t 64
2
200
p = 7
k 100. DC.
100
K 100, 64
50
0
p 3
& = 4, 2.
K 100
A: 100, / 8
50
50
p = 2
K 4.P = 2.
100
} 15, / = 8
50
100
p 2
& = 4,P 2. =
K 100
A 15, / = 8
50
200
== 2
& 4, p 2, < =
= 100
k 15, = 64
M
Implementation details
We computed persistent homology using the ripser project's representative--yylle. branch at commit 140670f to compute persistent homologies and representative cycles. We used coefficients in 2/22. 22. To compute &NN graphs, we used the PyKeops package [33] The rest our implemen- tation is in Python. Our code is available at wtttt::// http//gtttbbb.// com http://///eeereeaa/a/eeefpp....p neuri is2024)
Our experiments were run machine with an Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz with 64 kernels, 377GB memory, and an NVIDIA RTX A6000 GPU, The persistent homology computations only ever used single kernel.
Our benchmark consisted of many individual experiments. We explored 47 hyperparameter settings across all distances, computed results for 3 random seeds and 29 noise levels a. In the synthetic
1.00
0.75
Circle
AUC
0.50
Euclidean
Difuuion
B Diflusion =
Dirtusion
0.25
Eff. resistance
Diffusion 100
0.00
Linked cindes
0.75
AUC
0.50
0.25
0.00
1.00
Eyeglasses
AUC
0.00
15
45
75
90
105
120 135
15 30
60
75
90
105 1051201333 150
64
128 256
number neighbors
number of neighbors
diffusion steps
Figure S15: Diffusion distances and effective resistance are robust to their hyperparameters and outperform the Euclidean distance for most choices. We depict the area under the noise-level detection score curve for the three ID datasets circle, linked circles and eyeglasses in 5550
39

---

Table S5: Exemplary run times in seconds.
Dataset
n
Distance
Feature dim
Time distance [s]
Time PH [s]
Circle
1 1000
0.0
Euclidean
0.013 + 0.002
12.3 0.4
Circle
1 1000
0.0
Eff. res k = 100
0.17 = 0.04
12.0 + 0.2
Circle
2000
0.0
Euclidean
0.09 - 0.04
117
Sphere
1 1000
0.0
Euclidean
1
0.012 = 0.001
1.31 0.06
Sphere
1 000
0.0
Euclidean
0.017 0.002
4687 2501
Circle
1 100
0.35
0.016 + 0.001
5
Sphere
1 100
0.35
Euclidean
0.03 0.02
258 18
benchmark, we computed only 1D persistent homology for 3 datasets and both 1D and 2D persistent homology of 2 more datasets. So the synthetic benchmark with ambient dimension d = 50 alone consisted of 12 267 computations of ID persistent homology and 8 178 computations of both ID and 2D persistent homology.
The run time of persistent homology vastly dominated the time taken by the distance computation. The persistent homology run time depended most strongly on the sample size n, the dataset, and on the highest dimensionality of holes. The difference between distances was usually small. However, we observed that there were some outliers, depending on the noise level and the random seed, that had much longer run time. Overall, we found that methods that produce many pairwise distances of the same value (e.g., because of infinite distance in the graph affinities or maximum operations like for DTM with oo, & oo) often had much longer run time than other settings. We presume this was because equal distances led to many simplices being added to the complex the same time. We give exemplary run times in Table $5
As a rough estimate for the total run time, we extrapolated the run times for the circle to all ID persistent homology experiments for ambient dimension d' = 50 and the times for the sphere to all 2D experiments. both cases we took the mean between the noiseless (a = 0) and highest noise (a 0.35) setting in Table This way, we estimated a total sequential run time of about 60 days, we parallelized the runs.
N Effect of outliers
Persistent homology with the Euclidean distance is known to be sensitive to outliers. Methods such DTM were introduced to handle this issue. Here show that spectral methods also handle outliers well. Moreover, in high ambient dimensionality outliers are distributed over the large volume and hence are very sparse, making them less of problem.
We experimented with the noisy circle with n 000 points in ambient Idd for = 2, 50 and added 50, 100, or 200 outlier points. These were sampled uniformly from axis-aligned cubes around the data in ambient space. The size of the cube was set just large enough that contained the data even with the strongest added Gaussian noise.
In low dimensionality, Euclidean distance suffered in the low Gaussian noise setting already when only 50 outliers were added. Adding 100 or 200 outliers severely lowered the detection score for Euclidean distance across the entire range Gaussian noise strength. Fermat distances suffered from high random seed variability when adding outliers in low ambient dimension. Diffusion distance and effective resistance were much more outlier-resistant than the Euclidean distance and were only affected by 200 outliers. Even then they performed better than the Euclidean distance without any outliers. DTM excelled in this setting, being completely insensitive to outliers and achieving top score for all noise levels (Figure (ToaaeeSlaaa
The volume of the bounding box in d ambient dimensions is much larger and thus the same number of outlier points are distributed much more sparsely. In particular, it is much less likely that an outlier happens to fall into the middle of the circle. As result, even Euclidean and Fermat distances were very outlier-robust in d = 50 ambient dimensions (Figure(S16e.. performance did not change all in the face of outliers. However, all three methods suffered strongly from the nigh-dimensional Gaussian noise.
Similarly, DTM's
40

---

outliers
50 outliers
100 outliers
200 outliers
1.0
Euclideen
d=2
Loop deleccion
Femat
0.5
Eff, resist.
Diftusion
0.0
1.0
d 50 deleciion
0.0
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
Noise sid
Noise sid
Noise sid
Noise std
Figure S16: Loop detection performance of various methods on the noisy circle in the presence of outliers low- and high-dimensional ambient space. Outliers were sampled uniformly from an axis-aligned cube around the data. a-d. In low ambient dimension (d 2) adding outliers hurt performance of the Euclidean and Fermat distances, but barely affected the performance of spectral methods and not at all DTM's excellent performance. e-g. In high ambient dimensionality (d = 50) outliers did not further decrease the weak performance of non-spectral methods. Diffusion distance somewhat noise setting. Effective resistance performed best overall and was not very outlicr-sensitive
but could still detect the loop structure in the high Gaussian
As diffusion distance and effective resistance in our implementation rely on the unweighted ANN graph, they were somewhat more susceptible to outliers. Performance of diffusion distance decreased steadily with the number of outliers high ambient dimension. When outliers were present, performed worse than the Euclidean distance in the low Gaussian noise setting, but much better in the high Gaussian noise setting, even for 200 outliers. Effective resistance performed best overall, deteriorating only slightly in the low Gaussian noise setting when outliers were added. Both spectral methods clearly outperformed other methods the high-Gaussian noise regime even the presence of numerous outliers.
To sum up, effective resistance (and lesser extent diffusion distance) can handle both outliers and high-dimensional Gaussian noise, while other methods can handle at most one type of noise.
O UMAP with higher embedding dimension
Following the original publication 53 UMAP is typically used to embed data into two dimensions. This is an obvious issue for datasets sampled from manifolds which are not embeddable into two dimensions, such as the sphere or the torus. Therefore, we also experimented with the less common approach of higher embedding dimensionality (3. 5. 10) for UMAP. Save for the successful detection of the sphere's void with at least three embedding dimensions, we observed few consistent effects of the embedding dimension either on the toy (Figure $17 or on the real data (Figure (S19. Never- theless, on the linked circles dataset, which is not embeddable into two dimensions, we saw small improvement for UMAP when going beyond two embedding dimensions for the low noise setting.
Independent of the embedding dimension, UMAP struggled in the low-noise setting on the eyeglasses dataset for k- 15. Moreover, observed very poor performance both for loop and void detection on the torus. We believe the reasons may be UMAP's tendency to over over-fragmen the manifold [22 and UMAP's use of heavy-tailed kernel. We visualized diree-dimensional UMAP embeddings of the noiseless eyeglasses, sphere, and torus for & = 15 in Figure S18 UMAP left gap in the embedding of the eyeglasses dataset, so that the true loop only had the second highest persistence. Short Short-cutting at the bottleneck yielded the most persistent loop. For the torus, the surface of the embedding was very fragmented, preventing the detection of any void. While the main loop of the torus was detected well, the second most persistent detected loop was already in the noise cloud as the fragmented surface the embedding allowed for many fairly persistent loops. In a similar way, the surface of the sphere's embedding got fragmented, leading to many loops. Our score does not penalize this, because the detection score for m loop low as there nearly no gap in persistence between the most and the second-mos persistent loop. Higher levels of noise and also
41

---

Cirde (1 loop)
Eyeglasses (1 loop)
Sphere (0 loops)
Torus (2 loops)
Detecaion scare
1.0
0.0
0.1
0.2
0.3
0.00
0.05
0.10
0.15
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
Linked circles (2 loops)
Sphere (1 void)
h
Torus void)
Detection stare
1.0
0.5
0.0
0.0
0.1
0.2
0.0
0.1
0.2
0.3
0.1
0.2
0.3
Nosse sid
Noise sid
Naise sid
Eudlidean
Effeciive resistance k=
Effective
resistance k= 100
UMAP k 15,
UMAP k 15,
UMAP k 15, 8
UMAP 15
UMAP - 100
UMAP k 100, =
UMAP 100,
UMAP x 100,
UMAP 999, d-3
0
Figure S17: Hole detection scores in UMAP embeddings of the toy datasets in different embedding dimensions. Changing the embedding dimension only has small effect.
Eyeglasses
Sphere
Torus
Death
Death
Dealh
14
M4
Birth
Birth
Birth
Figure S18: Exemplary UMAP embeddings with 15 of the noiseless eyeglasses dataset, the sphere, and the torus into three dimensions. We show the persistence diagrams for loops and highlight the most persistent loops and superimposed them on the embedding. We strong framemeagmntttiion of the surfaces that challenges the loop detection and in the case of the torus the void detection (persistence diagram for the voids not shown).
higher & could overcome UMAP's over-fragment fremerragmnntaioon tendency for the eyeglasses dataset. This may be due to high-dimensional noise better matching UMAP's heavy-tailed kernel. However, did not resolve the framentagmnnnnooon for the torus.
The runtime of UMAP scales linearly with the embedding dimension, but typical t-SNE implemen- tations scale exponentially. In fact, the implementation we used here, TSen 63). does not implement embedding dimensions higher than two, which is why explored higher-dimenssonall embeddings only for UMAP.
42

---

Malaria
1.0
Delection spare soore
0.75
0.5
0.25
Neurosphere
1.0
Delecton soore
0.75
0.25
Hippocampus
Delectoon score
0.5
0.25
Neural IPCs
1.0
Dolection soore
0.75
0.25
HeLa2
1.0
Detecton soore
0.75
0.25
Pancreas
Deleciin goore
woare
0.75
0.5
0.25
Eudidean Correaatoo
UMAP 15
UMAP 999
UMAP k= 15,0=3
UMAP 100, 3=
UMAP == 999, 3
UMAP = 100, 8=
UMAP k 999,999,88 d=
UMAP == 15,8- 10
UMAP = 100, - 10
d= 10
Effediive resielance k- 15
Effedive steence K= 100
Lap. Eg == 15, 2
Lap Eg 15, aa5
Lap. Egg 15, 18-1-1 10
UMAP k-
UMAP k= 15,
Figure S19: Detection scores for UMAP with different embedding dimensions on the single-cell datasets with some other methods for reference. Changing the embedding dimension did have consistent effect on the detection scores, while higher embedding dimension usually hurt for Laplacian Eigenmaps.
43

---

P
Additional figures
Loop detection score
0.6
Eudiiden
Efi. res. weighted unsorrected k 15
Effective resislance k --1.
weighted unsorrected k 100
0.4
Effective resistance k 100
Effeclive resistance weighted k 15
res. 100 equare root
Effective resistance weighted k 100
0.3
Noise
Loop detection score on noisy S C IR:0 for various versions of effective resistance. There was little difference between using the weighted &NN graph, unweighted &NN graph, and using square root of effective resistance based on the unweighted &NN graph. The latter got filtered out for high noise levels. Using k 100 instead of k 15 helped only marginally in this dataset. The uncorrected (naive) version of effective resistance collapsed already at very small noise levels.
Figure S20:
a1D Pers. Diag.
Reprosentatives on 20 PCA
Doah
Death
Doah
Binth
Figure $21: Illustration for the random seed variability of effective resistance with h = 15 on the noisy eyeglasses dataset in R000 with a 0.075. This refers to Figure 7p. a. One-dimensional persistence diagrams for three random seeds. b. Representatives of the most two most persistent features superimposed on 2D PCA of the dataset. These always corresponded to the full shape and one of the two circle segments. For the first two random seeds, some points are distorted in such way that they form a bridge in the 2D PCA, while in the third there is not such bridge and the second most persistent feature is much less persistent. Note that this is just a 2D PCA. in particular, much of the noise in 50D not visible. A similar explanation applies for the diffusion distance in Figure 7p.
44

---

a= 0=0.0 0.0
b
a= 0.05
0=1.1
I-SNE
1D persistence
Birth
Birth
Birth
Figure S22: t-SNE embeddings with perplexity / p= 8 and 1D persistence diagrams of the embedding for a circle in ambient 1R500 with Gaussian noise of low standard deviation a. Perplexity P is rather small, such that each embedding point only feels attraction to very few other points. In the noiseless setting this very sparse attraction is only among immediate neighbors along the circle. This makes the embedding to have spurious curves. For higher noise, the sparse attraction pattern less regular and less local such that the spurious curves disappear. The more spurious curves the embedding has, the more high persistent features, given by bottlenecks in the curvy embedding, exist. This explains the dip for the t-SNE = 8 curve in Figure S23
Loop detection score
1.0
Fermat
Geodesics
ESNE
Eff. resist.
0.0
Fermat =2
Geodesics k= Geodesics k- 100
+NEE p=
Effective resistance = 15
Fermal 3
+NEE p 30
Effective resistance 100
Fermal
SNNE p 333
Fermat
Loop dotection score
DTM
I-SNE graph
UMAP
k
Diflusion
1.0
0.0
DTM 4,
HSN graph p
UMAP k- 15
Diffusion 15, r
2.
ESE graph - 200
Diffusion 100,
2
LNNE graph 333
UMAP 999
15,
Diffusion 100, 64
Loap delection score
Core
UMAP graph
Lap, eig.
0.5
0.0
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
Naise std
Noisa std
Noise sid
Core k 15
UMAP graph = 100
Lap. Eig. 15, 2=
Corn = 100
UMAP graph 999
Big 15, 0=
Eusidean
Big k= 15, 1=
Figure S23: Loop detection score for persistent homology with various distances on a noisy circle in ambient 50 Extension of Figure Spectral and embedding methods performed best. The reason for the dip for the low-perplexity i-SNE embedding is depicted in Figure S22
45

---

Loop delection score
Fermat
Geodesics cs
1-SNE
resist.
0.5
0.0
Fermal p =
Geodesics k= 100
1SNE p= B
Effective re sistaance 15 Effective re resietance k 100
Fermal 3
1SNE 30
p
p=
Fermat p 7
Loop deleciion score
DTM
graph
UMAP
Diffusion
0.5
0.0
DTM k 100, m,
I-SNE graph p 30
UMAP k- 15
Diftusion k 15,
DTM k- 15,
I-SNE graph 200
UMAP 100
Diftusion - 100,
graph
UMAP 999
Diffusion 15, = 64
Diflusion 100, 64
Loop dctection score
Core
UMAP graph
Lap. eig.
1.0
0.5
0.2
0.1
0.3
0.0
0.1
0.3
Noise
Noise
Noise
Core
UMAP 100
Lap. Eig. = 15,
Core k= 100
graph 999
Lap. Eig. 15, =5
Euclidean
Lap. Big 15, à
Figure $24: Loop detection score for persistent homology with various distances noisy circle in ambient R22 Our code for finding the geodesics for = 15 did not terminate. Nearly all methods performed near perfectly for most noise levels. Note the striking difference the 50D setting in Figure S23
46

---

Loop detection score
Fermat
Geodesics
1-SNE
Eff. resist.
1.0
0.5
Fermal p
1-NE p
Effective resistance
Formal p
100
1SE p= 30
Effective resistance 100
Fermat 5
1NNE 333
Fermal =
Loop delection soore
1.0
DTM
I-SNE graph
UMAP
k
Diffusion
0.5
p DTM p00
graph p-30
UMAP k 15
Diffusion 15, t
graph P
UMAP X 100
Diflusion 100, 8
DTM = 4,
5-NE graph p 333
UMAP k 999
Diflusion - 15, 64
Difiusion = 100, = 64
Loop deleciion score
Core
UMAP graph
Lap. eig.
0.5
0.0
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
Noise std
Noise std a
Noise sld a
Core =
UMAP graph k 100
Eig. k= 15,
Core k- 100
UMAP graph & 999
Big. k- 15, à
Lap. Big. k- 15, à 10
Figure $25: Loop detection score for persistent homology with various distances on a noisy circle in ambient 50 No thresholding used for this figure, in contrast to Figure|S2] Without thresholding, DTM had better performance, but not much beyond the level of Euclidean distance. Several issues such high random seed variability for Core k 100, t-SNE p 333 and artifactually increasing performance for several methods at very high noise levels can be visible here; this is why we used the thresholding procedure in the main text.
47

---

Loop dolection score
1.0
Fermat
d
Geodesics
S-NNE
Eff. resist.
0.5
Fermat
Grodesics k 15
ISNE p
Effective resistance =
Fermat p=
Geodesics = 100
1-SNE p
Effective resistance 100
Fermat p=
1-SNE p 333
Fermat p - 7
Loop delection score
DTM
t-SNE graph
h
UMAP
k
Diffusion
0.5
0.0
DTM 100, g
I-SNE graph 30
UMAP X 15
Difusion k- 15, 15,0=3
DTM 2-
I-SNE graph p
UMAP k 100
Diuusion k= 100, t
DTM -,p=2,-==
1-SNE graph o
UMAP k = 999
Difuusion k= 15, 64
Diftusion k 100, - 64
Loop detection score
Core
UMAP graph
Lap. eig.
1.0
0.0
0.10
0.05
0.05
Noise
std
std
UMAP graph
Lap. Big k 15,2
100
UMAP graph k 999
Lap. Eig 15
Eudlidaan
Lap. Big 15, 10
Figure $26: Loop detection score for persistent homology with various distances on the noisy eyeglasses dataset in ambient 50 Only Fermat distance, geodesics, t-SNE and UMAP, and spectral methods outperformed the Euclidean distance, but UMAP struggled in the low noise setting. The reason for the high random seed variability for effective resistance with k = 15 is depicted in Figure S21
48

---

bop delection score
Fermat
Geodesics
1-SNE
1.0
0.0
Fermat p 2
Geadesics == 15
I:SEE P 8
Effective resislacee
Fermat p=
Geodesice k= 100
LNNE =0
Elfective reeistance 100
Fermat
L-NE 333
p
loop deleccioon Sooe
DTM
I-SNE graph
UMAP
Diffusion
1.0
DTMK -
I-SNE graph p
UMAP k- 15
Diflusion k= c
DTM - 15, =,22
I-SNE graph p 200
1
DTMK - 15,
L-SNE graph 333
Diffusion 15,
k- 100,
2 loop detection score
Core
UMAP graph
Lap.
1.0
0.5
0.0
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
Noise std
Noise std
Noise std
Core k 15
UMAP graph k 100
Lap. Eig. K 15, 0
Core k 100
UMAP graph k
Lap. Eig. 15, à=
Eudideaa
15, 10
Figure S27: 2-loop detection score for persistent homology with various distances on two interlinked circles in ambient 50 Spectral and embedding methods performed best, but the latter sometimes had issues in the low noise setting.
49

---

Loop detection soore
Fermat
Geodesics
1-SNE
Eff. resist.
1.0
0.0
Fermat p
Geodesics
PNNE p 8
Effective
Fermat p
INNE p 30
Effective
100
Fermat p= 5
LNE 333
Fermat
Loop dctection score
DTM
t-SNE graph
UMAP
k
Diffusion
1.0
0.5
DTMK= p5,
graph p
UMAP
k- 15,
15
I-SNE graph p 200
UMAP 100
Diffusion k= 100,
DTM
L-SNE graph p 333
UMAP k 999
Diffusion == 15, 64
Diffusion k- 100, 64
Loop dctection scome
Core
UMAP graph
Lap. eig.
0.5
0.0
0.0
0.1
0.2
0.3
0.0
0.2
0.3
0.0
0.1
0.2
0.3
Noise std
Naise std
Noise sid a
Core k= 15
UMAP graph i 100
Eig. 15, à
Core = 100
UMAP graph i 999
Eig k= 15, à
Eudidean
Lap. Big k- 15, - 10
Figure $28: Loop detection score for persistent homology with various distances on a noisy sphere in ambient R000 Most methods passed this negative control.
50

---

Fermat
Geodesics
I-SNE
Void delection scare
1.0
0.0
Femaa 2
Geodesics k= Geodesics k 100
+SEE p
Effective resislance 15
Fernat 3
18N p= 30
Effective recistance 100
Format p
1SNE p
Fermat p
Void dctoction score
1.0
DTM
I-SNE graph
UMAP
Diffusion
DTM 1.--,,
PSNE graph p 30
UMAP X 15
Diffusin c
0TMK-4,p=a.6-
ESNE graph p 200
100,
D
ESE graph 333
Diflusion 15,
Void dcinction score
1.0
Core
UMAP graph
Lap. eig.
0.5
0.0
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
Noise std
Noise std
Noss std
Core k 15
UMAP graph k 100
Lap. Eig. k 15, d-2
Core k 100
UMAP graph
Lap. Eig. 15, à=
Eucldean
Big. k- 15, 10
Figure $29: Void detection score for persistent homology with various distances on noisy sphere in ambient R2 Methods relying on 2D embeddings not find the loop for any noise level. Spectral methods performed best.
51

---

2 loop detectton score
Fermat
Geodesics
I-SNE
Eff. resist.
0.5
0.0
Fermat
Geodesics 15
+NN
Effective resistance 15
Geodesics k 100
Effeclive resislance k 100
Fermat p
+SNE p
Feraat p
2 loop dciection score
DTM
t-SNE graph
UMAP
k
Diffusion
0.5
0.0
47MK=4,p=2,f22
UNE graph 30
UMAP À 15
Diffusion == 15,
D7M
SNE graph 200
UMAP X 100
Diftusin k- 1
D7M
graph
UMAP & = 999
Diffusion = 15, -
Diffusion 100, c= 64
2 bop delection score
Core
UMAP graph
Lap. eig.
1.0
0.5
0.3
0.2
UMAP greph UMAP graph k 999
Lap. Eig. k 15, -
Carn k 100
Lap. Eig. k 15, à
Euciidan
Lap. Eig. k- 15, 10
Figure S30: 2-1oop detection score for persistent homology with various distances noisy torus in ambient R550 All methods struggled here, and only DTM, core, t-SNE graph and UMAP graph improved noticeably over the Euclidean distance. On denser sampled torus effective resistance and diffusion distance outperformed other methods (Figure S3I). Using fewer diffusion steps improved the performance on the torus (Figure $32).
1000
5000
Loop detection scare
Euclidean
Eucidean
0.8
Farmat p 2
Fermal p
0.6
DTM k= 4.p 2.
DTM = 4, .
Effective
Effective maistanca k= 100
0.4
resistance k 100
Diffusion k r
Diffusion = 100,
0.0
0.0
0.1
0.2
0.3
0.1
0.2
0.3
Noise std
Noise std
Figure S31: 2-loop detection score for persistent homology with various distances noisy torus with different sample size n. For more points, all methods performed better as the shape of the torus gets sampled more densely. The difference in performance is particularly striking for the spectral methods which outperformed the others for n = 5 000 points, but did not for n = 000.
52

---

Eig. vec.
d
Eig. vec. 2
Eig. vec. 5
Eig. vec. 6
delection score
Rebative desay
2/1-
0.75
2 loop
0.50
0.5
IT
0.25
0.0
100
2m
2
2t
Noise
Elgervalue
Diffusion k- 100. t-
Diffusion k- 100, t-
Diffusion - 100. 64
Effective resistaice k 100
Euclideen
Figure S32: Diffusion distances failed on the torus with n 1000 because its eigenvalue decay suppressed the relevant eigenvectors, 2-loop detection score for the torus in d = 50 ambient dimensions. Diffusion distances with and Euclidean distance. b. Decay of eigenvalues in various spectral distances torus. Diffusion distances with 8, 64 only had contribution below 0.1 for the fifth and sixth eigenvectors, while effective resistance and diffusion distance with t 2 had substantial contributions from the first ~~10 eigenvectors. c-f. Eigenvectors of the symmetric graph Laplacian of symmetric (o0--eerest--iighhee
diffusion steps were on par with effective resistance
the noiseless
graph of the noiseless torus. Coordinates are the angles of each point along (ø) and around (#) the tube of the torus. The loop along the tube encoded in the first two eigenvectors, the loop around the tube in the fifth and sixth eigenvectors.
Void detection score
1.0
Fermat
Geodesics
t-SNE
Eff. resist.
0.5
Fermal
Geodesics
+NE p=
Effective
Fermat p 3
Geodesica k- 100
SNNE p= 30
Effective
100
Fermat p
SNN 333
Fermat
Void dotection score
1.0
DTM
t-SNE graph
UMAP
k
Diffusion
0.5
BSE graph
UMAP 15
Diffusion 15,
2,-
SNE graph p=
UMAP X 100
Diffusion 100, c-8
DTMK=4,p=2.E=
SNE graph p= 333
UMAP A 999
Diffusion = 15, r.. 64
Diffusion k = 100, = 64
Void deliciion scare
1.0
Core
UMAP graph
Lap. eig.
0.0
0.0
0.2
0.3
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
Noise std
Ncise eld a
Noise sid a
Core k
UMAP graph k= 100
Eig. 15, =
UMAP graph - 999
Lap. k 15, a
Lap. Big. k= 15, à 10
Figure S33: Void detection score for persistent homology with various distances on a noisy torus in ambient 50 Methods relying 2D embeddings did not find the void for any noise level. Only t-SNE graph and UMAP graph could reliably improve above the Euclidean distance and only for low noise levels. However, they had unstable behavior for higher noise levels, resulting in high uncertainties. We suspect that a higher sampling density would benefit effective resistance and diffusion distance (as
for loop detection in Figure (S3T), but the computational complexity of persistent homology makes such experiments difficult.
53

---

Malara
1.0
scons
0.75
0.5
0.25
0-
Naurosphere
1.0
0.78
0.5
0.20
0-
Hippocampus
1.0
Datectoo
0.5
Neural IPCs
1.0
Delection scaes
0.75
0.5
0.25
0-
HoL.2
1.0
8cone
0.75
0.5
0.25
0-
Pancreas
1.0
Dalection
0.5
Eusideani Correation
Fermell 2
Fammst p
Care k= 100-
Geodestos k 15
L-NEE praph = 30
SNE 200
UMAP guphik k 100
UMAP g 999
bSNE 0
L-SNE p= 30
sSNEpa 333
URJPP k- 15
UMAP k 100
UMPP 999
Effectva neliimaa k- 15
Effectvv resizanca k- 100
Difuaion 15.t=B
Diffusen k 100,
Diffisonn Diftison-- 15, 15. 64
Lap Bs. Bn.k=15,88 2=
15,005
Famest
gaph
Dimuson 100,
Figure S34: Detection scores for all hyperparameter settings for all six single-cell datasets. We omitted DTM as setting passed the thresholding any dataset. The black bar refers to correlation distance on the Malaria dataset and to Euclidean distance on the others. Extension of Figure [O] I-SNE graph and UMAP graph could perform very well, but were very hyperparannterr-deeeddeee Their embedding variants often performed well, but collapsed on some datasets. The spectral methods behaved similarly, but on average performed better.
54

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We describe contributions clearly in both the abstract and the introduction and explicitly list them at the end of the introduction. The failure modes of traditional
persistent homology are described in Section 4 with formal statements and proofs in Ap- pendix B We state our novel closed-form expression for effective resistance in Section 6 (proof Appendix F and use relate effective resistance to other spectral methods. Finally, Section 7 contains our experimental validation of the quality of spectral methods over alternative distances imput persistent homology.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We mention limitations of our work such the ambiguity inspecting repre- sentative cycles of detected topological features, persistent homology failing to distinguish non-isometric point clouds, the high computational complexity of any persistent homology computation, and sampling issues in high-dimensional spaces in the Limitations section R We also clearly state the need for selecting hyperparameters for our recommended meth- ods in Section 7 and acknowledge that spectral methods need more samples for a good performance on the torus in Section 7.1
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
55

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
We illustrate our claims about the failure of persistent homology with an example in Section 4 and provide full formal statements and proofs in Appendix [ The formal claims in Section 6 are rigorously shown in Appendices and G and appropriately cross-referenced.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We describe every aspect of our experiments in detail, ensuring repro- ducibility. Datasets, distance measures, and the performance score are described in Sec- tion 7 Additionally, we give more details on the used distances and datasets in Ap- pendices | and |
Further technical aspects of our experiments are described in the Ap- pendix " 'lmllemnntttion details" M Moreover, our code is publicly available at https //github. com/ httm/bbrnsslab//be eff wwtpppeeteeteeeeeeeeeeppee cree//euurps2222
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
56

---

While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We submit our entire codebase with this submission and will make it open access at the camera ready stage. The codebase contains README that explains how to setup the environment and which scripts to run to reproduce our experiments. Moreover, we detail which notebooks need to be run to reproduce each figure.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
mublic/guides /ttpd//eeooooodddisseeeeeeeeeeee wwweeoumiissiooooooooooooooooooo
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
wttpcccppppccccceeec.eeeeeec.cce wwwiii/gggee/eeeeeeeeeoo.eeissee wwweeoooiessss.soeooooa sosoiiiiiiiipocccccoccocooiipiic for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We describe implementation in Sections 3 and Moreover, we describe the explored hyperparameters Appendix Jand detail which hyperparameter values were chosen in Appendix K
Guidelines:
57

---

The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: For all experiments, report the mean performance across three random seeds and the standard deviation. We specify this just before Section 7.1
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix[MMedtee details the processor, memory, and GPU the machine on which experiments. Moreover, we report the times of individual experiments and an estimate for the total run time in this appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of http://pww/.eaapp..coooa/////aaa
58

---

Answer: [Yes]
Justification:
We read and conform with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We have a Broader impact section Appendix which also discusses potential negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML...
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
We do release any generative models or scraped datasets.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
59

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The persistent homology computation relies on the ripser package, which
we cite in Section [ and we give the commit version we used Appendix M We cite the original authors of all the datasets we use both in Section 7.2 and Appendix where we also state the licenses and include the URLs from which we obtained the data.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, papppswitthhaoooo thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We obtained the Neural IPC data directly from Braun et al. [8] who allowed us to share it with this work (MIT license). We documented this asset in Appendix
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
60

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
61


Reviews:
[{"review_id": "s2xWFw8OxX", "reviewer": "Reviewer_C1nu", "summary": "This paper attempts to mitigate the inadequate performance of persistent homology in high dimensional settings, in particular in the presence of noise. The authors investigate a number of distances and propose to use two kinds of spectral distances, such as diffusion distance and effective resistance, instead of Euclidean distance, and demonstrate that the proposed approach performs well in a number of synthetic and single-cell datasets.", "questions": "(Q1) In Figure 5, it seems that t-SNE and UMAP perform better than effective resistance in the presence of a lot of noise – why are they then not recommended? Could you please add an explanation?\n\n(Q2) Your recommended distances (mostly diffusion) fail to detect the 1 void and 2 loops in a Torus, could you please explain this?\n\n(Q3) Can there be a theoretical result demonstrating that your PH with your proposed spectral distances is capable of capturing loops in higher dimensions in the presence of noise? \n\n(Q4) Apart from the single-cell RNA-sequencing datasets, can you please suggest other datasets from other domains where your method could be used?\n\n(Q5) Have you considered using multiparameter persistence in order to avoid the noise issue, and how well do you expect it to work in the higher dimensional setting?", "limitations": "Yes, all limitations are addressed adequately by the authors in the paper", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "(S1)\tThe paper addresses a relevant problem\n\n(S2)\tDiverse experimental setup (both synthetic and very interesting real world datasets are used)\n\n(S3)\tThe paper is comprehensive and well-written", "weaknesses": "(W1) Lack of theoretical results explaining why the suggested distances work so well\n\n(W2) The advantages over the other methods in the literature are not very clear", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer C1nu,  \nwe 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.\n\n**W1 & Q3: Theoretical results on spectral methods for persistent homology:**  \nThe 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)].\n\n**Q1: Performance of UMAP and t-SNE:**  \nComputing 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.\n\nWe 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). \n\nMore 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\".\n\n**Q2: Failure of diffusion distances on the torus:**  \n\nFirst, 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).\n\nThird, 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.\n\n**Q4: Potential application domains:**  \nHigh-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.\n\n\n**Q5: Multiparameter persistence:**  \nMultiparameter 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).\n\nHowever, 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.\n\n**References:**  \n\nSzlam, Maggioni, & Coifman (2008). Regularization on graphs with function-adapted diffusion processes.\n\nRamakrishna,  Wai & Scaglione. (2020). A user guide to low-pass graph signal processing and its applications: Tools and applications.\n\nBenjamin, Katherine, et al. (2022) Multiscale topology classifies and quantifies cell types in subcellular spatial transcriptomics.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OUVupQHfC8", "reviewer": "Reviewer_aHMb", "summary": "This work studies a well-known phenomenon in persistent homology, which is that it performs poorly in the presence of noise in the settings of a high-dimensional ambient space.  Spectral and diffusion approaches are proposed as a workaround to this problem and shown in an extensive numerical study to perform well.  A new theoretical result is also provided alongside on effective resistance.", "questions": "The authors refer quite a lot to a very recent paper on the curse of dimensionality in persistent homology [1], which recently appears and which I am quite familiar with.  It seems to me that the submission, while providing a thorough experimental analysis, theoretically is only contributing yet another method for quite a well-known problem, which seems to me to have been more comprehensively and convincingly studied and solved in [1], especially in a context that would be a better fit for the audience of the conference.  How would the authors justify the importance of their contribution in relation to [1]?\n\nHow does the authors' approach compare to those of other approaches for cycle detection [2] that was not mentioned at all?\n\n[1] Curse of dimensionality on persistence diagrams, Hiraoka et al., arXiv April 2024.\n[2] Cycle registration in persistent homology with applications in topological bootstrap, Reani & Bobrowski, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.", "limitations": "I did not find any discussion of limitations of their work at all in the main body of the paper.  All discussions in the paper were devoted to superiority of the method, though presumably after such an extensive numerical experimental study, there must have been more to it, which may have been relegated to the appendix that I did not study in detail but given the requirement by the conference to be forthcoming with the limitations, these should have been stated clearly in the main paper.  This, together with my question above on how does this submission fit in with the curse of dimensionality paper, is a major weakness of the submission, as mentioned above.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Thorough and detailed experimental setup on synthetic as well as real data.\n\nOverall good presentation, with few errors and typos.", "weaknesses": "A major weakness is the lack of discussion on the limitations of the work.  The main paper only highlights the strengths and superiority over the proposed method to other existing ones.  While the work appears to have done a thorough and careful experimental treatment, I did not re-run the experiments myself to validate the findings, but I find it hard to believe that there is no limitation whatsoever of the work compared to existing methods to a well-known problem.\n\nAdditionally, it seems like not all approaches to this problem were studied.  Certainly some important recent approaches were not mentioned in the section on related work, which is another weakness of the work.  Please see the questions below.\n\nI also feel like a comprehensive discussion on spectral methods in persistent homology are lacking, especially when a lot of work has been done in this area, especially recently (see, for example, work by Mémoli and Sanchez-Garcia).  In general, spectral and diffusion approaches are not new to the field and so the approach proposed is not very surprising.  Additionally, the consideration of other distances for persistent homology is not surprising at all.  The theoretical contribution is nice, but it seems to be an accompanying theoretical result to the work rather than really adding any meaningful contribution to the problem that would be very useful to the TDA community, let alone the community of the conference.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer aHMb,\n\nthank 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.\n\n**Relation with Hiraoka et al. (2024):**  \nAs 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:\n\n> 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. [...]\n\nThat 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.\n\nSecond, 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 &#x010C;ech complex, and describing the effects on persistent homology in more detail.\n\nThird, 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. \n\nWe 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.\n\nTogether, 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). \n\nOur 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.\n\nWe will add a condensed version of this discussion and the PCA results in the revised manuscript.\n\n**Limitation section:**  \nThank 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 \n\n- our methods need hyperparameter choices (line 214),\n- spectral methods only outperform the Euclidean distance on a more densely sampled torus (lines 254-256),\n- interpreting cycle representatives is difficult (line 321-322),\n- persistent homology can fail to distinguish non-isometric point clouds (line 325),\n- and has a high run time (lines 334-336).\n\nNevertheless, we are happy to create a dedicated _Limitations_ subsection in the revision, also mentioning additional limitations. Please see the general comment for its text.\n \n**Comparison with Reani & Bobrowski (2023):**  \nTheir 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.\n\n**Spectral methods and persistent homology:**  \nIn 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.\n\n\n**References:**  \n\nDavies, Wan, & Sanchez-Garcia(2023). The persistent Laplacian for data science: Evaluating higher-order persistent spectral representations of data.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x3szsr5MLR", "reviewer": "Reviewer_QsUc", "summary": "The author(s) propose a metric that is based on combining nearest-neighbor graphs and spectral methods to analyze point clouds of high ambient dimension using Vietoris-Rips filtrations and persistent homology. They show experimentally that the proposed distance better detects the significant topological features. For that, they use both toy examples as a proof of concept as well as RNA-sequencing datasets.", "questions": "I do have one question about the claim that the representatives are sometimes not plausible (Fig 9). How is this determined in detail? Homology generators can sometimes be linear combinations of the \"natural\" representatives that one \"sees\" in low-dimensional pictures, and as far as I know, there is not much control about what ripser or any other persistence software will give you (except you do some post-processing to compute a \"good\" representative subsequently)", "limitations": "As this section is mandatory to fill, I will say that the work is certainly a proof of concept, as only datasets are studied for which the number of loops and voids is clear from the start. That makes sense, however, since how could one verify the results otherwise?", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper deals with a relevant problem as high-dimensional data (with low intrinsic dimension) indeed is a frequent application case in topological data analysis (or rather: there is potential for such applications if the right tools were available).\n\nThe experimental section is also well-written, taking a wealth of other methods into account, and applying the methodology on synthetic and real data.", "weaknesses": "I miss an explanation of why the loop detection score (sometimes also called hole-detection score) is the right measurement to compare the approaches. I understand it has been used before but I am not quite satisfied with that resoning. Also, there seems to be a score s_m for each integer m, and I fail to see which m is used.\n\nAs a minor weakness, the distance measure is defined in Section 5, but there is not too much intuition given of why this should be working better than other methods. When going through the appendix, it seems like there is more explanation given there but I cannot go through the appendix for the lack of time. I wish there would be a brief intuitive explanation of why this works so well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer QsUc,  \nmany 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.\n\n**Hole detection score:**  \nOur 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.\n\nFor 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.\n\nWe 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.\n\nThe 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. \n\nDuring 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. \n\n**Intuition for the success of spectral methods:**  \nThe 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. \n\nAs 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.\n\n\n**Analysis of representatives:**  \nIndeed, 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. \n\n**Limitations:**  \nWe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear reviewers and area chair,  
we cordially thank you for the effort invested in assessing our manuscript. We are glad that you found the tackled problem "relevant" (C1nu, QsUc), liked our presentation (C1nu, aHMb), and appreciated both the theoretical contributions (AC) and our experimental setup (C1nu, aHMb, QsUc). 


**Rebuttal figures:**  
Attached to this general comment, please find a page with three additional figures. 

**Dedicated Limitations section:**  
Following the comments of reviewers aHMb, QsUc, and the AC, we will include a dedicated _Limitations_ section, see below. It consists of passages formerly located in the Discussion section plus some additional content, highlighted below in italics. The remaining part of the Discussion section will be retitled _Conclusions_.



> **Limitations and future work:**  
> 
> In the real-world applications, it was important to look at representatives of detected holes as some holes were persistent, but arguably incorrect. That said, each hole homology class has many different representative cycles, making interpretation difficult. Given ground-truth cycles, an automatic procedure for evaluating cycle correctness remains an interesting research question.
> 
> Persistent homology can only detect topology, which is often a useful global level of abstraction. However, it may therefore fail to distinguish some non-iso*metric* point clouds [64]. *There exist dedicated measures for detecting isometry [Boutin et al. 2004, Widdowson et al. 2023, Kurlin 2024].*
> 
> Using effective resistance or diffusion distances is easy in practice as their computation time *($O(n^3$))* is dwarfed by that of the persistent homology (Table S4), which scales as $O(n^{3(\delta+1)})$ for n points and topological holes of dimension $\delta$ [51]. This high complexity of persistent homology aggravates other problems of high-dimensional datasets as dense sampling in high-dimensional space would require a prohibitively large sample size *and since spectral methods seem to need a high sampling density on some datasets like the torus for good performance*. Combining persistent homology with non-Euclidean distance measures could mitigate this problem via the approach of Bendich et al. [6], who performed subsampling after computation of the distance matrix. This is a particularly attractive avenue for future research. 
> 
>*Both effective resistance and diffusion distances require the choice of hyperparameters. However, effective resistance only needs a single hyperparameter: the number of $k$NN neighbors. For this reason and due to its greater outlier resistance (Appendix K), we tend to recommend effective resistance over diffusion distances, but a principled criterion when to use which of the two is still missing.*
> 
>*Moreover, we do not have a theoretical proof that spectral distances mitigate the curse of dimensionality. Such a proof may be achieved in the future taking inspiration from the stability results in [10, 36, 66] and, more generally, spectral perturbation theory.*
> 
>*Our empirical results focus on benchmarking which distances identify the correct topology in the presence of high-dimensional noise. Therefore, we only considered datasets with known ground-truth topology. The next step will be to use spectral distances to detect non-trivial topology in real-world exploratory contexts.*

**Continuity of our hole detection score:**  
Reviewer QsUc and the area chair had questions about our evaluation metric. During the rebuttal, we were able to prove the following desirable continuity result for our hole detection score $s_m$, which we will include in the revision. It states that on persistence diagrams with sufficiently many points our hole detection metric is continuous. This makes our metric robust against small perturbations in the persistence diagram, a property expected for a reliable metric. 

In the typical case, where the persistence diagram contains a noise cloud of many points close to the diagonal and, optionally, some outliers, the requirement on the number of points is satisfied. Only in the case where we expect a large gap after the $m$-th feature, but the diagram does not even have $m$ features, can there be a sudden jump in our hole detection score.


*Proposition*  
Let $\mathcal{D}$ be the space of all persistence diagrams with finitely many points off the diagonal, endowed with the topology induced by the bottleneck distance $d_B$. Then the map $s_m: \mathcal{D} \to R_{\geq 0}$ is not continuous for any $m$.  Here $R_{\geq 0}$ are the non-negative real numbers.

Let $m \in \mathbb{N}$ and define $\mathcal{D}'$ as the subset of $\mathcal{D}$ with at least $m$ points off the diagonal. Then the map $s_m: \mathcal{D}'  \to R_{\geq 0}$ is continuous.   
*Proof sketch*  
The discontinuity of  $s_m: \mathcal{D} \to R_{\geq 0}$ happens when adding the $m$-th point to a diagram.

For the continuity part, we split $s_m$ into two parts. The map $p_m: \mathcal{D} \to R_{\geq 0}$ that assigns its $m$-th persistence to a persistence diagram is continuous (details omitted for brevity).
The map $q: R_{>0} \times R_{\geq 0} \to R_{\geq 0}, (x, y) \mapsto (x-y)/x$ is continuous. Furthermore, we have $p_m(\mathcal{D}') = R_{> 0}$. Finally, $s_m: \mathcal{D}' \to R_{\geq 0}$ factors as $q\circ (p_m\oplus p_{m+1})$, showing its continuity. Q.E.D.


**References:**  

Boutin & Kemper (2004). On reconstructing n-point configurations from the distribution of distances or areas.

Widdowson & Kurlin (2023). Recognizing rigid patterns of unlabeled point clouds by complete and continuous isometry invariants with no false negatives and no false positives.

Kurlin (2024). Polynomial-time algorithms for continuous metrics on atomic clouds of unordered points.

Meta-review: This paper rigorously investigated the shortcomings of several past methods (dimensionality reduction and persistent homology), which are important to know for a broad audience in data science. 

All reviewers gave positive scores and sticked to them after the author's detailed rebuttal, though no reviewer provided decisive arguments.

Reviewer QsUc, who gave score 7, didn't participate in the discussion after acknowledging the rebuttal by saying "Thank you for the clarifications - I stick to my score". 

Reviewer C1nu, who gave score 6, was asked even before the rebuttal to clarify their comments with more details but didn't react and later only wrote that "I thank the authors for their efforts and the response. I have read the response and would like to stick with my score." 

Reviewer aHMb, who gave score 5, acknowledged that "I may have been harsh in my initial evaluation and while my overall impression has increased, I still maintain that is a borderline paper that could be accepted". 

The area chair champions this paper for the following reasons.

The key strength is the rigorous approach with theoretical results, e.g. Corollaries 6.1-6.2 proved in Appendices C-D. 

The main argument for accepting this paper is the practical demonstration of the curse of dimensionality for persistent homology, which wasn't previously known. 

The authors understood the major limitation of any dimensionality reduction, which is either discontinuous (makes close points distant) or collapses an unbounded region to a single point (loses an infinite amount of data) as proved in the paper at https://www.tandfonline.com/doi/abs/10.4169/amer.math.monthly.123.4.392.

This crucial limitation applies to all modern methods such as t-SNE and UMAP, whose optimization has no guarantees of a global optimum, as well as to classical methods such as PCA whose coordinates are analytically computable but can discontinuously change under perturbations of given points when some eigenvalues become equal.

Any justified analysis of high-dimensional data should be done in the original space, while low-dimensional projections to explicitly defined coordinates can help only to visualize, not to make rigorous conclusions.
Decision: Accept (poster)