The Flood Complex: Large-Scale Persistent Homology on Millions of Points
Authors: Florian Graf
Paolo Pellizzoni
Martin Uray
Stefan Huber
Roland Kwitt
Venue: NeurIPS 2025 poster ()
Keywords: persistent homology
topological data analysis
Primary area: theory
TL;DR: We propose a novel simplicial complex that enables computing accurately persistent homology on large scale Euclidean point clouds.

Abstract: We consider the problem of computing persistent homology (PH) for large-scale Euclidean point cloud data, aimed at downstream machine learning tasks, where the exponential growth of the most widely-used Vietoris-Rips complex imposes serious computational limitations. Although more scalable alternatives such as the Alpha complex or sparse Rips approximations exist, they often still result in a prohibitively large number of simplices. This poses challenges in the complex construction and in the subsequent PH computation, prohibiting their use on large-scale point clouds. To mitigate these issues, we introduce the Flood complex, inspired by the advantages of the Alpha and Witness complex constructions. Informally, at a given filtration value $r\geq 0$, the Flood complex contains all simplices from a Delaunay triangulation of a small subset of a point cloud $X$ that are fully covered by the union of balls of radius $r$ emanating from $X$, a process we call flooding. Our construction allows for efficient PH computation, possesses several desirable theoretical properties, and is amenable to GPU parallelization. Scaling experiments on 3D point cloud data show that we can compute PH of up to dimension 2 on several millions of points. Importantly, when evaluating object classification performance on real-world and synthetic data, we provide evidence that this scaling capability is needed, especially if objects are geometrically or topologically complex, yielding performance superior to other PH-based methods and neural networks for point cloud data.

Source code and datasets are available on GitHub: https://github.com/plus-rkwitt/flooder

The Flood Complex
Large-Scale Persistent Homology on Millions of Points
Florian Grafl
Paolo Pellizzoni M Martin Uray 13, Stefan Huber Roland Kwitt!
Universityy of Salzburg, Austria
Max Planck Institute of Biochemistry, Germany
Josef Ressel Centre for Intelligent and Secure Industrial Automation, University of Applied Sciences. Salzburg, Austria
Abstract
We consider the problem of computing Persistent Homology (PH) for large-scale Euclidean point cloud data, aimed downstream machine learning tasks, where the exponential growth of the most widely-used Vietoris-Rips complex imposes serious computational limitations. Although more scalable alternatives such as the Alpha complex or sparse Rips approximations exist, they often still result in prohibitively large number of simplices. This poses challenges in the complex construction and in the subsequent PH computation, prohibiting their use on large-scale point clouds. To mitigate these issues, we introduce the Flood complex, inspired by the advantages of the Alpha and Witness complex constructions. Informally, at given filtration value O, the Flood complex contains all simplices from a Delaunay triangulation of a small subset of a point cloud X that are fully covered by the union of balls of radius r emanating from X, process we call flooding. Our construction allows for efficient PH computation, possesses several desirable theoretical properties, and is amenable to GPU parallelization. Scaling experiments on 3D point cloud data show that we can compute PH of up to dimension on several millions of points. Importantly, when evaluating object classification performance on real-world and synthetic data, provide evidence that this scaling capability is needed, especially if objects are gcometrically or topologically complex. yielding performance superior to other PH-based methods and neural networks for point cloud data. Source code and datasets are available on ? https: //ts:://iit /gibthu...... www.hhu..ooopppee com/plus rkwitt/flooder.
Introduction
Throughout the past years, topological data analysis (TDA) tools and, in particular, persistent homology (PH) [1, 21, 42, 54), have found widespread application in machine learning [39]. Applications range from graph classification [10, 28, 29], and time series forecasting [14, 51] studying representations [2. 38, 48] and generalization of neural networks [7, 18), and developing novel regularizers or loss functions [13, 30J. The central pillar of most of these works is the power PH to reveal and concisely summarize topological and geometrical information from a finite sample of points. In particular, within this pipeline, one first constructs a simplicial complex together with a filtration that encodes the underlying topological structure across scales. Once built, one then computes stable summary called a persistence barcode or persistence diagram.
Importantly, however, the unfavorable computational complexity of the algorithmic pipeline for PH computation has, far, largely limited the scope of topological approaches to studying connectivity
f "quul contribution
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

properties only. For this reason, efficient approaches to the computation of PH have been a goal for the field for some time, as emphasized in a recent position paper [39, Section 4].
When taking a closer look at how such simplicial complexes are typically built, we immediately identify potential scalability issues. In particular, when the input data is point cloud, one often chooses the simplicial complex whose k-simplices are all subsets of cardinality (k + 1). For example, the Vietoris-Rips and the Cech complex at filtration value consist of all subsets of the point cloud with diameter less than r and all subsets that can be enclosed in some ball of radius r, respectively, Hence, at high filtration values, their number of simplices becomes exponentially large, rendering memory consumption and persistent homology computation impractical for large point clouds. Simple mitigation strategies include computing the complex and homology only up to some degree, only up to some filtration value, or only on a subsample of the point cloud. More advanced methods, such as sparse approximations [44] and collapsing strategies [8], reduce the Vietoris-Rips complex to a smaller one with (approximately) equivalent topology. However, for (very) large point clouds, one may need to "sparsify" so aggressively that topological features and approximation guarantees no longer apply, while the resulting complex may still be too large for practical computation.
The natural way avoid such scalability problems is to work with smaller complexes. Specifically, in low dimension (e.g., three as in our experiments), filtrations on the Delaunay triangulation of the point clouds are used, such as the Alpha complex equivalent to Cech), or Delaunay- Rips [36] complex. However, in true large-scale settings, even the benign scaling of the Delaunay triangulation can be challenging, not in terms of memory consumption, but in terms of subsequent PH computation time of these filtered complexes, as the latter comes at worst-case cubic complexity (in the complex size) using the standard matrix reduction algorithm [21].
[19], Delaunay-Cech complex [4] (both homotopy
To further reduce the size of the complex, one can resort to subsampling strategies. In subsampling [9, 11], the key idea is to repeatedly draw small subsets of the full point cloud, execute the PH pipeline, and then aggregate the resulting persistence diagrams [9], or an appropriately vectorized representation of the latter [1]]. Both approaches come with theoretical guarantees but, depending on the data, may require sufficiently large subsets, a large number of random draws, and a computationally expensive aggregation step (as in [9]). Crucially, once the subsamples from the point cloud are chosen, the complex construction is agnostic of the original data. Because of this, topological features that are smaller than the distance between samples are irreversibly lost.
The Witness complex construction [16], which is most similar to our approach, builds a simplicial complex in data-driven manner on top of reduced landmark set. In particular, simplices appear in the complex if they are witnessed, i.e., if there exists a single non-landmark point that satisfies a distance condition to the simplex. Similar to subsampling approaches, small topological features can be lost. Moreover, the construction of the Witness complex can be fragile, as it entails carefully controlling a distance cut-off to avoid truncating genuine topological features while taming the running time, which, in many cases, renders this type of construction impractical on large point clouds.
Contribution(s). We seek to mitigate the discussed scalability issucs via the Flood complex, i.c., new filtered simplicial complex for Euclidean point cloud data. Being built on top of a small subsample of the point cloud at hand, its size is orders of magnitude smaller not only than the Vietoris-Rips complex but also the Alpha complex, facilitating efficient PH computation. Moreover, as its simplices are endowed with filtration values that are tied the entire point cloud, the topological approximation quality of the Flood complex is considerably better compared to subsampling strategies. The computation of the Flood complex is designed for execution on GPUs, enabling efficient exploitation of specialized hardware and software libraries frequently used in contemporary machine learning research. We provide (I) initial theoretical guarantees on the approximation quality of PH computed on the Flood complex, stability results, and guarantees for approximation steps. Further, we (2) demonstrate scalability to point cloud sizes that were previously impossible to process, and eventually (3) present strong empirical evidence that this scalability is needed and useful when seeking to classify geometrically complex 3D point cloud data.
2 Preliminaries
We study finite point sets X in Euclidean space Rd in terms of the topology of the union of balls X, Urex (x) at varying radii 2 O, with (x) = (y e Rd: d(xx,) z r) and metric d(.,)). The topology of X, and, in particular, its homology, can be computed from combinatorial object
2

---

called a simplicial complex. An (abstract) simplicial complex Σ over a set S is collection of non-empty, finite subsets o C S such that for every non-empty subset T C a also r L. Moreover, or is called a k-simplex if it has cardinality k I, and simplex T c or is called a face of or
As we study X, for different r 2 O, need simplicial complex Σ, at each radius Analogously to S implying X, C X,, we want Σ c Σ, A sequence of simplicial complexes {E, r 2 0) satisfying this property called a filtration or filtered simplicial complex. In particular, a function f: Io - R that fulfills certain consistency properties induces a filtration via Σ ( /)).
Informally, when increasing r, the shape of X, will gradually change from the points Xo- X themselves to X = Rd. During this process, we can study X, by means of the homology groups Hą of an associated simplicial complex Σ, and their evolution over r. Specifically, Ho encodes connectivity information, H1 information about loops, H2 information about 3-dimensional voids (and subsequent homology groups encode higher dimensional topological information). As grows, these homological features appear and disappear, and we summarize this information in the form of a persistence diagram dgm, (E), i..., a multiset of tuples (b, d) E R2, where b denotes the minimal value r such that a feature exists in HE,) and d denotes the maximal such value. Informally, the feature is born at time and dies at time d. Two persistence diagrams D1 and D2 can be compared via their bottleneck distance dD(D,, D2) := inf DD: sup peD, Ip - 77p)) il where the infimum is taken over all bijections 1j 1)1 - D2, considering each diagonal point (b, b) with infinite multiplicity. Importantly, if for two filtered complexes Σ, and Σ,, there exists > 0 such that h Σ C Eytc for all r 2 0, then dg(dgm(2) (2), dgm( ()) S e, see [15].
A particularly relevant family of simplicial complexes over point clouds X are Alpha complexes [19] Alpha, (X), which form a filtration of the Delaunay complex Del(X) on X. They are naturally embedded Rd with each simplex o represented by its convex hull conv(or) == (Exer dxx Exeo d2 = 1, 2 0). Denoting by |Alpha,1 := U Alpha conv(or) Rd, we have that |Alpha, c X, and that both are homotopy equivalent [19]. This relates back to the very first point, i.e., guarantees that X, can be studied in terms of (X).
3 The Flood complex
As discussed, given a finite point cloud X C CR,, idcally we would want to compute the PH of its (filtered) Alpha complex. The latter can be computed from a filtration of the Delaunay complex Del(X) which has, for |X| = at most O (nld/21) simplices (and thus much fewer than the 2 1 simplices of the Vietoris-Rips complex). However, the computation of PH will still be challenging if becomes very large. While, of course, one could compute the Alpha complex on only subset L c X, one may lose valuable information when doing so. We therefore propose a filtration on Del(L) that is aware of the entire point cloud X.
Informally, at a given filtration value 2 O, our novel complex contains all simplices Del(L) that are fully covered by balls of radius emanating from X, a process we call flooding. We refer to the resulting complexes Flood, L.) c De)(L) as Flood complexes and, in alignment with the terminology of witness complexes, we will refer to L. as landmarks. We often select L as subset of X, but doing so is not necessary, and the theoretical results in Section 3.2 do not require this assumption. Definition 1. For r 2 O, the Flood complex Flood, (X, L) at flood radius r is the simplicial complex
Flood,(X = for E Del(L): conv(o) c U B,(()) xeX
Whenever 0 s S 1, we have Flood, (X, I.) C. Flood, (X, I.) from X, c X,, which yields a genuine filtration, i.e., nested family (Flood, (X, r)) which we refer to the filtered Flood complex. By construction, if L C X, then all O-simplices are already in the complex at time r = 0 and vice versa. For brevity, we will refer to the entire nested family of Flood complexes Flood X, L).
3.1 Intuition
Figure |illustrates a point cloud X, a subset L C X, and the construction of the filtered complexes (L) and Flood(X. L.). We argue that Alpha, (L), which is homotopy equivalent to the union of balls of radius r centered on I., can be a poor representation of the topology of X,, while the filtration function of the Flood complex makes it more aligned to the topology of the underlying data.
3

---

Landmarks
F
Flood.(X.
(Lp
Figure 1: Schematic overview of the Flood complex Flood, (X, (top). the Alpha complex subsample Alpha, (L) (bottom), and their accordance with union of balls at different radii r. The point cloud marked by e, the landmarks X by e, and identify the balls radius r.
For example, the points v E X are in the same connected component of X as illustrated in the second column of Figure 1. This is faithfully encoded Flood,, (X, L) which already contains the edge {u, v). because conv (u, v)) C Xr. However, in the Alpha complex, and will be in the same connected component much later, i.e., only after 13. Similarly, radius r2, there are two cycles in X which are recognized by Flood,, (X, L) but not by Alpha, (L). Specifically, the rightmost cycle in X, less persistent in the Alpha filtration, as is born only much later in Alpha( L) at filtration value and dies shortly afterwards. For the leftmost cycle this effect is even more pronounced. Similar considerations apply to higher order simplices, such as, for example, the triangle (x. y, z), which missing from Alpha(L)) even at filtration value f4.
is worth mentioning that since Flood( X, L) defined by a filtration on the Delaunay triangulation only on L instead of X, there are natural limitations to its resolution. Most notably, every k-simplex in Del(L) can detect most one k-dimensional hole. Still, if the number of landmarks sufficiently large and they are well-placed, then Flood, (X, L) will be able to capture the relevant homological information of X,, as shown in the next subsection.
3.2 Theoretical results
The Flood complex satisfies certain beneficial properties (proofs can be found in Appendix C). First, it is stable with respect to the point cloud X. This means that if the point cloud X is perturbed by little, then the PH of Flood(X, L) changes only bit, quantified as follows.
Theorem 2. The Flood complex is bottleneck stable with respect to its first argument, i.e., given L, X'
X' c Rd, holds that Vi N
dg (lgm,(Flood(X, L)),
L))) S dx.X''))
(2)
second desirable property satisfied by the Flood complex is that recovers the topology of the union of balls X, when the landmarks L are chosen as the whole point cloud X. Theorem 3. Let R be a finite subset of points general position. Then, |Flood, (X, X)] homotopy equivalent to X, for any 2 O.
While, at the moment, our proof only covers the case X c R2, conjecture that similar arguments work for higher dimensions, and we leave the proof for future work. Nevertheless, because homotopy equivalent spaces have the same homology. Theorem 3 directly implies that the persistent homology of Flood(> X, X) equals that of Alpha(X) X). Moreover, in combination with Theorem 2 and the classic Hausdorff stability of Čech and Alpha complexes [15], we get the following approximation guarantee. Corollary Let I., X c: IR? be fimite subsets of points in general position. Then, it holds that Vi E N
dn (dgm, (Alpha( X)), dgg, (Flood X, L))) & 2d (X, L.)
Essentially, if we want d (dgm, (Flood( X, I.)). dgm, (Alpha & 2e, suffices to select such that (X, e. In particular, if L X, finding the optimal landmark positions is just the metric

---

k k-center problem, and greedy selection strategies, such as farthest point sampling (FPS), achieve factor 2- aapproximationn of the optimal covering radius [26]. Thus, (
is achieved once [1.] 2 O(E landmarks are selected, where D is the intrinsic dimension of x. Similar guarantees hold with high probability
a random sample and its first [4_] points are used as landmarks [34].
Moreover, Corollary 4 implies that the persistence diagrams of the Flood complex are stable with respect to the landmarks L, albeit with a multiplicative constant of 4. Still, in case L is perturbed only slightly such that its Delaunay triangulation is preserved, then there is direct proof that dø (dgm, (Flood X, L)), dgm, (Flood(Xo L))) s (L.LL)
4 Computational aspects
We next discuss the computational aspects of constructing the Flood complex. Note that the set of simplices, i.e., Delaunay triangulation of the landmark set L. can be computed in ((L]|(d/21) [12], and efficient implementations can be found in libraries such as CGAL [45] or qhull [3].
4.1 A Approximation
The definition of the Flood complex entails calculating the filtration value f((r) of each simplex Del(X). This filtration value f(o)) max min xx d(p.x) x) is the minimal radius r such that conv(or) C Xr. or equivalently, the directed Hausdorff distance between conv(ar) and X. Since computing the directed Hausdorff distance a nonconvex problem, finding f((r would be inefficient. Hence, in our implementation, we replace each convex hull conv(ar) by finite subset Pa C conv(ar, resulting in the simplicial complex
Flood, (X, L, P) (or e Del(L): Pr C X, Vr
(4)
are in Flood, (X, L, P). By construction, Flood,(X, L) L)) c Flood, (X, P)) because conv(or) being flooded implies that Po is flooded. Moreover, if the (directed) Hausdorff distance hetween each pair P., and conv(or) satisfies (P conv(rr) < <, then Flood, (X, I., P) c Floodr+e (X, L.). We get the following guarantee. Theorem 5. Let X, L E Rd and let P = (Po: o Del(L)) with Po C conv(ar for all o e Del(L). Then, it holds that Vi E N dB (dgm, (Flood(X, L)), dgm, (Flood L, P))) s max du(Po. conv(r))
Specifically, Flood, (X, L, P) iff P is flooded and all its faces
(5)
orDeelL)
We can select the sets Po in various ways, e.g., by explicitly enforcing a small Hausdorff distance to conv(or), taking a random sample, or based on an evenly spaced grid of barycentric coordinates.
Lemma 6. Given m N and k-simplex o = (vo...., VK), let Po {p = El Apv:: oi A;
1, m. N) c conv(ar) be a grid of simplex points induced by evenly spaced barycentric coordinates. Then, it holds that
Σ |1 1
S m
Notably, the bound decays with 1/mm, where m the number of grid points on each edge. The shape of the simplices enters in form of the square root term, which scales with O ((dia((o)), A similar scaling behavior can be observed when P.r selected randomly, see Lemma 9.
Thanks to the finite set P.r. the optimization problem can be solved directly by iterating over the points in Per and X. However, the number of points in P.r required for good approximation is large, this approach does not scale to large point clouds if implemented naively. As the problem entails finding the nearest neighbor in for each point in Po., it can be efficiently solved using a data structure such as a k-d tree [5] or cover tree [6]. Building such a data structure can, however, incur significant computational overhead. To avoid this issue, we compute the directed Hausdorff distance using custom GPU algorithm, paired with a principled masking procedure, which is presented below.
4.2 Masking and GPU acceleration for the flooding process
Since the filtration value maxper, mingex d(p,.x) of the simplex or depends only on a single pair of points (p,xx) xx), we want to ignore points x that are far from or. In fact, if I. X, then we can precompute for each simplex subset of X that must be considered.
5

---

17.
death time
12.5
deatt time
7.5
50
Alphe
Alptu Flood PTi Alptul PH
Flood 251
Alphal PH
RV-A89
000
100 1b vis
Leptoseris paschalensis
birth time
birth time
Figure 2: Exemplary hexbin plots of persistence diagrams of RV-A89 (left) and the Leptoseris paschalensis coral (right). Gray corresponds to Alpha PH of the full point cloud, blue Flood PH with 10k landmarks and orange to Alpha" PH with 75k points. Point clouds are visualized via small spheres colored by distance to their bounding box center (for RV-A89) by elevation (for the Leptoseris paschalensis coral). Best viewed in color.
Lemma 7. Let C Rd be a finite set in general position, and or C be a set of k S d +++ points. Ifc E Rd and > 0 are such that a C (c), i.e., such that B, (c) is enclosing ball of then
f(o)= max min(d(p.x): X]= max min {d(p,x): x X E B B5 (c)) pecuns(er)
(6)
peconv(
In practice, we compute the enclosing balls (c) using a variation of Ritter's heuristic [41], i.e., we set the center of the longest edge of o and use radius v2 max d(c, vy). This can be done in (dd) time and is highly parallelizable on GPUs. case or itself an edge, it suffices to set the radius to half its diameter, i.e., without the factor V2.
Once centers and radii have been computed for all simplices Del(L), checking whether the points X belong to B By2,(C (c) can be done with [De(( |X] distance evaluations, yielding a Boolean masking matrix of shape [Del(L] XX] Since the mask be computed independently for each (simplex, point) pair, computation the masking matrix can be efficiently parallelized. Eventually, the masking matrix together with the points in X and the sets P.r are fed to a custom Triton [47] kernel, which computes the directed Hausdorff distance; for specifics of this kernel, see Appendix A.
Experiments
We validate the applicability and relevance of the Flood complex follows: in Section 5. we use it to compute PH on point clouds for which existing approaches require an impractical amount of computational resources; in Section 5.2, we study the scalability of the Flood complex, and, in Section 5.3, we show that PH computed on the Flood complex (in short, Flood PH) improves predictions downstream machine learning tasks compared to simpler approaches such as subsampling.
In our experiments, we often compare the Flood complex and its PH to the Alpha complex on the entire point cloud and the Alpha complex to Flood PH at the given number of landmarks and discretization level of simplices. Specifically, discretize to 30 points per edge in Sections 5.1 and 5.2 and 20 points per edge in Section 5.3. We denote the former by Alpha PH (full) and the latter by Alpha PH. For PH computation and the construction of Alpha complexes, use Gudhi [46].
subset of size selected so that runtime is similar
5.1 Persistent homology on large-scale point clouds
First, we showcase the approximation capabilities of the Flood complex on two exemplary real-world point clouds from different scientific disciplines, one (12M points) based cryo-clectron microscopy of a rhinovirus (RV-A89) from [49], the other (10M points) based on a 3D-scan of a Leptoseris paschalensis coral from the Smithsonian 3D Digitization initiative. Additional information about the point clouds can be found in Appendix A.4. We compute zero-, one-, and two-dimensional PH using the Alpha complex, which can be thought of as the ground truth. Notably, this requires more than 15 minutes of runtime per point cloud and more than 90 GB of RAM. We then compare its PH to that of the Flood complex and to that of the Alpha complex computed
subsample.
visual inspection of the persistence diagrams, see Figure 2, shows that Flood PH mitigates the shift of (birth, -eath))-tpplss along the diagonal (that is characteristic for subsampling methods), resulting

---

Ho
H1
in H2
Bottleneck distance da
10
15
Hausdortf distance du
100
100
#Landmuks (Flood PH)
20%
225k
80
10k
APoiiEs (Alpha PH)
10
17%
60
60
2k
4
40
40
125k
20
20
500
200
75k
10
20
30
10
20
30
10
20
30
Runtime (in s)
Runtime (in 5)
Runtime (in s)
Figure 3: Approximation quality of Flood PH and Alpha PH on RV-A89. The (left) panel shows bottleneck distances to Alpha PH (full) in Ho. H1 and H2 when varying the number of landmarks for Flood PH and the subsample size for Alpha PH. The (middle) panel shows the Hausdorff distance between the full point cloud and the landmarks, resp., the points in subsample. The (right) panel shows the color coding used all the plots.
in better approximation of birth and death times compared to Alpha PH. Moreover, the persistent Hi features the RV-A89 virus become scattered for Alpha' PH but remain close together for Flood PH.
For a quantitative comparison between Flood PH and Alpha PH on subsamples, we consider bottleneck distances to Alpha PH (full) on the RV-A89 point cloud. Results are presented in Figure 3; for results on the Leptoseris coral, we refer to Appendix B.2. As expected, the approximation quality of Flood PH improves with the number of landmarks. Notably, the randomness the landmarks, caused by different starting points for FPS, mainly affects H2. Beyond 500 landmarks, bottleneck distances are significantly smaller in dimensions 0 and I, and similar in dimension 2, when comparing Flood PH to Alpha PH at the same runtime budget. A comparison between landmark selection using farthest point and uniform random sampling reported in Appendix B.3.
5.2 Runtime and scalability
Breakdown of runtimes. In Table 1, we report the runtime share of different parts of Flood PH. Specifically, we consider one point cloud from the swi sscheese dataset (1M points) and one from the RV-A89 (12M points), see Section 5.1. We compute filtration values for each simplex from a grid with 30 points per edge and use FPS for landmark selection (2k and 10k). Al- though the (relative) runtimes inevitably depend on the configuration of the Flood complex and the shape and size of the point clouds, several trends can be observed: the majority of time is spent computing filtration values, followed by landmark selection and masking; the runtime of the remaining parts, i.e., triangulating the landmarks, PH computation and other overhead (e.g., computing grid points and enclosing balls of simplices) mainly depends on the number of landmarks. On RV-A89 and [Z] = 2k, this overhead negligible.
Table Relative runtime breakdown (in %) Flood PH on one point cloud from two datasets.
swi swihssee
RV-A89
#Points [X]
1M 2k
12M
12M
#Landmarks [L]
2k
10k
Landmark select.
13.3
15.8
18.1
Delaunay triang. Masking
6.0
0.8
2.9
3.7
3.2
7.7
Filtration PH computation
69.5
79.3
68.2
3.0
0.2
1.0
Other
0.6
2.1
Scalability. We assess the scaling behavior of the Flood complex on point clouds constructed in the same manner the swi sscheese dataset. Specifically, study its scaling wrt. (a) the number |X] of points in the point cloud, (b) the number [4] of landmarks, and (c) the ambient dimension. We always compare to Alpha PH computed from subsamples of the same size [X]. As can be seen in Figure 4 (a), both methods exhibit an increase in runtime with [X]. However, while for [X] < 10*, the Flood PH runtime is similar Alpha PH (likely due the overhead of landmark selection), for larger point clouds, Flood PH requires consistently one to two orders of magnitude less time than Alpha PH. Figure (b) presents the runtime of Flood PH as a function of [L] (with |X| = 1M fixed). general, we observe a linear scaling behavior that is aligned with the typically linear growth [22] in the number of simplices in the Delaunay triangulation of L. Finally, Figure (c) shows the impact the ambient dimensionality d E (2,3. 4, when keeping |X| 1M and |4| 1k fixed. Here, runtimes increase with d for both methods, as number of simplices in the Delaunay triangulations grows. Notably, Flood PH consistently remains at least one order of magnitude faster than Alpha PH.
7

---

(0)
10
Flood PH
10
104
Alpha PII
10
10a
Runtine
10a
10a
Alpha
10a
10
10
101
109
109
109
10
10
10a
10
10
10
Number [X] of points
Number [L]
landmarks
Dimension
Figure 4: Runtime (in s) of Flood PH and Alpha PH for skisscheese-like point clouds: (a) in R², varying the point cloud size [X] with [4] = 1k landmarks; (b) in R², varying the number of landmarks [L] with [X] IM
points; (c) varying the dimensionality with [X] = IM and [L] lk.
5.3 Object classification
We run classification experiments five datasets, including three real-world datasets, i.e., modelnet10, mcb-c and the self-curated corals, which come the form surface meshes with varying number of vertices and varying object "complexity". In terms of the latter, the number of vertices and triangles is good proxy (especially
the CAD-based models mcb-c), as, e.g., representing helical geared motor requires a finer mesh than representing taper pin. To create point clouds, we uniformly sample |X] points from the mesh surfaces (as, e.g., done [17]), which mitigates artifacts from irregularly spaced vertices. We also create two topologically challenging 3D synthetic datasets, i.e., swisscheese and rocks. Dataset details are provided in Appendix A.4, We random 80/20% training/testing splits, with 10% of the training data reserved for validation.
Parametrization of the Flood complex & classifier. Unless otherwise stated, we select |4| 2k landmarks from |X| 1M points using FPS. To compute filtration values, discretize each simplex based on an equally spaced grid barycentric coordinates with 20 points per edge (resulting in 210 points per triangle and 1540 points per tetrahedron); cf. Section 4.1. We vectorize persistence diagrams (Ho, H1 and H2) using [27] with (exponential) structure elements, parametrized as follows: locations are set to 64 k-means++ centers, computed from the (birth, death) tuples of all diagrams in the training data, scales are chosen as in ATOL [43, Eq. (2)), and the vectorization's 's stretch parameter percent lifetime quantile (based on the validation data); this yields
set to either the one, five, 64-dim. vectorizations per diagram which, upon concatenation, are fed as 192-dim. feature vectors to LGBM [31] classifier (except for corals, where Hyperparameters are tuned on the validation data using FLAML [50] and a time budget of 10 minutes.
f ferreuuari logistic regression).
Baselines. Our primary TDA baseline is Alpha PH, i.e., persistent homology computed from subsample size chosen such that the runtime is similar to Flood PH, i.e. 1% the rocks point clouds and otherwise 20k points. Persistence diagrams processed in the same manner described above. Importantly, we do not account for the vectorization time when choosing the subsample size for Alpha" PH, although persistence diagrams obtained from Alpha complexes can become very large and require substantially more time for vectorization than those obtained from Flood PH. We also compare averaged persistence diagram vectorizations []. denoted Alpha PH (avg.). obtained from Alpha PH five point cloud subsamples of accordingly reduced size. Unfortunately, methods such Witness complexes [16], sparse Rips filtrations [44], adaptive approximations [25], which might at first glance seem natural competitors to the Flood complex, proved to be infeasible on large-scale point clouds. For example, computing lazy Witness complex with 100 landmarks and IM witnesses required more than 20 minutes on our hardware (using the Gudhi [46] implementation).
Moreover, compare to three neural network methods, designed for point cloud data: PointNet++ [40], PointMLP [35], and PVT [52] (with network width and depth as in the reference implementations). We train all models on point clouds subsampled to 2k points by minimizing cross-entropy (or MSE for the regression task on rocks) over 200 epochs using Adam [33] with a cosine annealing schedule and batch size 64. We select the initial learning rate, weight decay, and early stopping period based on the validation data. On the real-world datasets, we use random scaling and shifts as data augmentation.
For classification tasks, we report the mean balanced accuracy over training/test- ing splits + standard deviation on all datasets (to account for class imbalances). For the regression task on rocks, report the mean of mean squared errors (MSE) over splits standard deviation.
Evaluation metries.

---

Table 2: Classification results synthetic data. Runtime (in is given per point cloud (averaged over all point clouds in dataset); Acc denotes balanced accuracy (averaged over all ten splits). We do not runtimes for neural networks (bottom part), as they are not directly comparable. Further, there is only one Runtime column for rocks, as the classification and regression task use the same persistence diagrams. @ indicates that results cannot be computed within 48- -8-hour time budget (runtime for rocks is estimated).
swisscheese (2)
rocks (2)
rocks (reg)
Acc 1
Runtime |
Acc |
MSE
Runtime 1
Flood PH
0.98 0.01
1.1 = 0.1
0.88 = 0.03
0.5 = 0.2) le-3
7.0 2.9
Alpha² PH
0.85 0.04
1,8 + 0.0
0.78 + 0.03
( (1.5 = 0.3) x le-3
9.1 + 4.2
Alpha" PH (avg.)
0.80 + 0.02
0.9 + 0.0
0.76 + 0.04 O
(20.9 + 1.3) x le-3
6.9 + 3.1
Alpha PH (full)
0.94 0.02
134.3 # 15.8
O
1490 680
PointNet++ [40]
0.49 0.03
0.01
(18.6 + 2.8) le-3
PointMLPP [35]
0.51 0.02
0.51 + 0.03
( 8.8 = 1.0) le-3
PVT [52]
0.50 0.02
0.51 + 0.04
(31.4 # 3.4) 1c-3
Flood PII 10a
0.9
Accuracy
Rontime
0.8
0.7
10
Flood
Alpha PH
0.6
0.5
1100
1111001
1.111
10a
10
10
10
10
10*
10a
10
Point cloud with 10 holes
Number [X] of points
Number [X] of points
Figure 5: Comparison of classification of accuracy (on swi swisseeesse) and runtime (in s) between Flood PH (2k landmarks) and Alpha PH when the latter has access to increasing number of points in X. The leftmost panel shows an example a swisscheese point cloud with 10 holes.
5.3.1 Synthetic data
Swiss cheese. We create synthetic dataset of 3D point clouds by uniformly sampling 1M points in 53 and removing & disjoint balls with random radii (in [0.1, 0.5)) and centers. We set k e {10, 20) and seek to distinguish point clouds by their number of voids (i.e., a binary problem). An example (with k= = 10 voids highlighted in red) is shown in Figure 5 (left). The motivation for creating this dataset to demonstrate that any approach based solely on subsampling the data for computational reasons (either in the context of computing PH, or for training neural network models) will perform poorly, as the class-specific topological characteristics (i.e., the voids in H2) will be difficult to identify.
Table 2 confirms that all neural network baselines fail on this problem. Moreover, the classification performance of Alpha PH is worse than that Flood PH. most likely because Alpha PH provides less information. To examine the latter, we compare Flood PH with Alpha PH on increasingly larger subsampled point clouds in Figure 5. As expected, the classification accuracy increases with the subsample size. However, surprisingly, it never matches the accuracy of Flood PH, but reaches its maximum 94% at 1M points, i.e., at the entire point cloud. We hypothesize that the remaining gap to Flood PH can be attributed to the very large size of the resulting persistence diagrams, making the vectorization. Furthermore, we observe an
difficult to represent the relevant information approximate linear increase in runtime for Alpha PH with increasing point cloud size, resulting in more than 24 hours runtime for computing PH on the entire dataset when all 1M points are used.
Rocks, Extending the ideas underlying the swi sscheees data, we generate more difficult dataset that mimics porous materials. Its point clouds contain up to 16M points and are extracted from Boolean voxel grids of size 256 produced using two different generators (blobs and fractal noise) available as part of the PoreSpy library [23]. We evaluate classification accuracy wrt. the data generating method (i.e., a binary problem) and regression accuracy wrt. the surface area computed from the voxel grid. From Table 2, it is apparent that PH, and particularly Flood PH, excels on this dataset, achieving an average classification accuracy of 88%, whereas neural networks are only marginally better than random guessing. Similarly, on the regression task, Flood PH performs by far the best, with all neural networks yielding MSEs more than one magnitude larger than Flood PH.

---

Table 3: Classification results real world data. Runtime (in s) is given per point cloud (averaged over all point clouds in dataset); Ace denotes balanced accuracy (averaged over all ten splits). We do not runtimes for neural networks (bottom part), as they are not directly comparable. O indicates that results cannot be computed within a 48-hour time budget.
corals (2)
mcb cccb-cul (11)
modelnet1 (10)
Acc 1
Runtime J
Ace 7
Runtime
Acc 1
Runtime
Flood PH
0.77 0.09
1.8
1.2
0.02 0.74
1,5 0.5
0.72 0.02
0.8 0.2
Alpha' PH
0.58 + 0.13
1,7 0.3
0.66
0.03
1.8 + 0.2
0.64 * 0.01
1.6 + 0.1
Alpha" PH (avg.)
0.52 0.08
1,4 0.1
0.69 = 0.03
1.1
0.66 0.02
1.3
Alpha PH (full)
0.44 0.07
153.4 16.8
119.1 +
107.3 5.9
PointNet++ [40]
0.53 0.10
0.76 0.02
0.93 + 0.01 0.01
PoinLMLP [35]
0.59 0.15
0.74 0.03
0.93 = 0.01
PVT [52]
0.56 + 0.11
0.77 0.03
0.94 = 0.01
5.3.2 Real-world data
ModelNet10. modelnet 10 subset of the larger ModelNet40 [53] corpus, containing geometrically rather simple objects with few characteristic topological features. Considering the latter, unsurprisingly, all neural network baselines perform much better (by more than 20 percentage points) than any purely PH-based approach, regardless of the simplicial complex. Nonetheless, observe that all PH-based approaches yield accuracies notably higher than the =54% reported in [17] (on the same benchmark data) for method that predicts vectorized persistence barcodes via neural network.
Mechanical Components Benchmark (MCB). As a slightly more challenging dataset, we selected a (1I-class) subset of meshes, dubbed mcb-c, from the publicly available MCB corpus [32], focusing on objects with more geometrically and topologically interesting features, see Appendix A.4. Comparing the neural network results of Table with the results in [32, Table 5] (mostly >90% on the fill dataset of 68 classes), we see that the increased object complexity (of our 11 Iclclss subset) manifests as a drop in classification accuracy. Notably, Flood PH is competitive with the neural networks and achieves significantly better balanced accuracy than Alpha' PH and Alpha' PH (avg.)
Coral mesh dataset. Finally, we curated challenging dataset of 3D point clouds by uniformly sampling IM points from surface meshes of corals from the Smithsonian 3D Digitization initiative. Our results on the binary classification problem of distinguishing corals by genus show that Flood PH yields (by far) the best result, suggesting that capturing fine details in the surface structure is mandatory for extracting discriminative information. Similar Figure 5, we observed that the large number of points in the persistence diagrams of Alpha PH variants (compared to the leaner diagrams produced by Flood PH) tends confound the persistence diagram vectorization technique, leading to drops in downstream performance. Moreover, all neural network baselines achieve only balanced accuracy of less than 60% with a high variance across splits.
Discussion
We introduced the Flood complex, a novel simplicial complex designed to address the long-standing computational challenges of PH on large-scale point clouds. By combining careful subsampling and GPÚ parallelism, the Flood complex enables efficient computation of accurate PH approximation on point clouds with millions of points within seconds, offering speed increases of up to two orders of magnitude over the widely used Alpha complex. The Flood complex opens up several research questions for future work, including strengthening its theoretical guarantees and developing even more efficient algorithms. Specifically, we anticipate that the theoretical guarantees can be extended to Euclidean spaces of arbitrary dimension, and that more direct proof's, yielding tighter bounds on approximation quality and stability with respect to landmarks, are possible. Moreover, exploring additional real-world applications that require computing PH on large point clouds would further highlight the value of the Flood complex as a lightweight tool, and we envision that the Flood complex will facilitate a more widespread use of PH in machine learning applications that have, so far, been limited by computational constraints.
10

---

Acknowledgments
This work was supported by the Federal State of Salzburg within the EXDIGIT project 20204- W1SS/263/6-6022 and projects 0102-F1901 166- KZP, 2020-WW1S7225/117-2009 the Austrian Science Fund (FWF) under project 10.55776DDFH479 124 (REVELATION), M. Uray and Huber were supported by the Christian Doppler Research Association (JRC ISIA), the Austrian Federal Ministry for Digital and Economic Affairs and the Federal State of Salzburg.
The authors also thank the anonymous reviewers for the valuable feedback during the review process, and Karsten Borgwardt and the Max Planck Institute Biochemistry for providing access to the computing infrastructure.
References
[1] S. Barannikov. The Framed Morse complex and its invariants. Adv. Sov. Math., 21:93-116. 1994.
[2] S. Baramnikov, Trofimov, N. Balabin, and E. Burnaev. Representation topology divergence: A method for comparing neural network representations. In ICMI,, 2022.
[3] C. B. Barber, D. P. Dobkin, and H. Huhdanpaa. The quickhull algorithm for convex hulls. ACM Trans. Math. Softw., 22(4):469-445 483,, December 1996. ISSN 0098-3500.
[4] U. Bauer and H. Edelsbrunner. The Morse theory of čech and delaunay complexes. Trans. Am. Math. Soc., (6 2017.
[5] Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):009-517, September 1975. ISSN 0001-0782. doi: 10. 10.1145/361002.3310000 5, 14
[6] A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for nearest neighbor. In ICML, 2006.
[7] Birdal, A. Lou, L. Guibas, and U. Şimşekli. Intrinsic dimension, persistent homology and generalization in neural networks. In NeurlPS, 2021.
[8] J.-D. Boissonnat, S. Pritam, and D. Pareek. Strong collapse and persistent homology. J. Topol. Anal., 15(01):185-213, 2023. 2
[9] Y. Cao and A. Monod. https://arxiv org/ abs//2/4.2222 09155. arXiv.
Approximating persistent homology for large datasets, 2022. URL
[10] M. Carriere, F. Chazal, Ike, T. Lacombe, M. Royer, and Umeda. Perslay: A neural network layer for persistence diagrams and new graph topological signatures. In ATSTATS, 2020.
[11] Chazal, B.T. Fasy, F. Lecci, B. Michel, A. Rinaldo, and L. Wasserman. Subsampling methods for persistent homology. In ICML, 2015. 2,8
[12] B. Chazelle. An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom., 10(4):377-40,, 1993. 5
[13] C. Chen, Ni. X., Q. Bai, and Y. Wang. A topological regularizer for classifiers via persistent homology. In AISTATS, 2019.
[14] Y. Chen, I. Satooiaa-Dminguez.. B. Coskumuzer, and Gel. TAMP-s2GCNets: Coupling time-aware multipersistence knowledge representation with spatio-supra graph convolutional networks for time-series forecasting. ICLR, 2022.
[15] D. Cohen-Steiner, H. Edelsbrunner, and Harer. Stability of persistence diagrams. Discrete Compul. Geom,, 3731):003-10,, 2007. ISSN 1432-0444. 3, 4, 19, 20
[16] V. Silva and G. Carlsson. Topological estimation using witness complexes. In Eurographics Symposium Point- Based Graphics, 2004. 2,

---

[17] Т. de Surrel, F. Hensel, M. Carrière, T. Lacombe, Y. lke, H. Kurihara, M. Glisse, and F. Chazal. RipsNet: general architecture for fast and robust estimation of the persistent homology of point clouds. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning. 2022. 8, 10
[18] N. Dupuis, G. Deligiannidis, and U. Şimşekli. Generalization bounds with data-dependent fractal dimensions. In ICMI,, 2023. 1
[19] H. Edelsbrunner. The union of balls and dual shape. In SCG, 1993. 3, 24
[20] H. Edelsbrunner and J. Harer. Computational Topology an Introduction. American Mathemat- ical Society, 2010. 22
[21] H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete Comput. Geom., 28:51 11-33,, 2000. 1,2
[22] Erickson. Nice point sets can have nasty Delaunay triangulations. Discrete Comput. Geom., 30(1):109-132, May 2003, ISSN 1432-0444. 7
[23] J.T. Gostick, Z.A. Khan, T.G. Tranter, M.D. Kok, M. Agmaou, M. Sadeghi, and R. Jervis. Porespy: A python toolkit for quantitative analysis of porous media images. J. Open Source Softw., 4(37): 2019. 9, 16
[24] A. Hatcher. Algebraic Topology. Cambridge University Press, 2002. 21
[25] M. Herick, M. Joachim, and J. Vahrenhold. Adaptive approximation of persistent homology. Appl. Comput. Topol., (8))23327-253 2366, Dec 2024. ISSN 2367-1734. 8
[26] Dorit Hochbaum and David B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2):180-18) 184, 1985. ISSN 0364765X, 15265471. 5
[27] C. Hofer, R. Kwitt, and M. Niethammer. Learning representations of persistence barcodes. JMLR, 20(126): 2019. 8
[28] C. Hofer, F. Graf, B. Rieck, M. Niethammer, and R. Kwitt. Graph filtration learning. In ICML. 2020.
[29] M. Horn, F. De Brouwer, M. Moor, Y. Moreau, B. Rieck, and K. Borgwardt. Topological graph neural networks. In ICLR, 2022.
[30] X. Hu, Li, D. Samaras, and C. Chen. Topology-preserving deep image segmentation. In NeurlPS, 2019. 1
[31] G. Ke, Q. Meng. T. Finley, T. Wang, W. Chen, W. Ma, Q. Ye, and T.-Y. Liu. Lightghm: A highly efficient gradient boosting decision tree. In NeurIPS, 2017. 8
[32] S. Kim, H.-G. Chi, X. Hu, Q. Huang, and K. Ramani. A large-scale annotated mechanical components benchmark for classification and retrieval tasks with deep neural networks. In ECCV, 2020. 10, 16
[33] D.P. Kingma and L.J. Ba. Adam: method for stochastic optimization. In ICLR, 2015. 8
[34] S.R. Kulkarni and S.E. Posner. Rates of convergence of nearest neighbor estimation under arbitrary sampling. IEEE Transactions Information Theory, 41(4):1028- 1039,, 1995. doi: 10.1109/18.39 0119//88.99148... 5
[35] X. Ma, C. Qin, H. You, H. Ran, and Y. Fu. Rethinking network design and local geometry in point cloud: A simple residual MLP framework. In ICLR, 2022. 9,
[36] A. Mishra and F.C. Motta. Stability and machine learning applications of persistent homology using the Delaunay-Rips complex. Front. Appl. Math. Stat.,, 9:1-18 2023.
[37] M. Mitzenmacher and E. Upfal. Probability and Computing - Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. 20
12

---

[38] M. Moor, M. Horn, B. Rieck, and K. Borgwardt. Topological autoencoders. In ICML, 2020. 1
[39] T. Papamarkou, T. Birdal, M.M. Bronstein, G.E. Carlsson, J. Curry, Y. Gao, M Hajij, R. Kwitt, Lio, P. Di Lorenzo, V. Maroulas, N. Miolane, F. Nasrin, N.K. Ramamurthy, B. Rieck, S. S.arddapane, M.T. Schaub, P. Veličković, B. Wang, Y. Wang, G. Wei, and G. Zamzmi. Position: Topological deep learning is the new frontier for relational learning. In ICML, 2024. 1,2
[40] C.R. Qi, L. Yi, H. Su, and L.J. Guibas. Pointnet++: Deep hierarchical feature learning on point
sets in metric space. In NewrIPS, 2017. 8, 9, 10
[41] H. Ritter. An efficient bounding sphere, page 301-303. Academic Press Professional, Inc., USA,
1990. ISBN 0122861695.
[42] V. Robins. Towards computing homology from finite approximations. Topology proceedings, 24(1):503-532 1999.
[43] M. Royer, F. Chazal, C. Levrard, Umeda, and Y. Ike. Atol: Measure vectorization for automatic ropolggicall--orintee learning. In AISTATS, 2021. 8
[44] D.R. Sheehy. Linear-size approximations to the vietoris-rip rips filtration. Discrete Comput Geom, 49(4):778-77) 796, 2013. ISSN 1432-0444. 2,8 8
[45] The CGAL Project. CGAL User and Reference Manual. CGAL Editorial Board, 6.0.1 edition, 2024.
[46] The GUDHI Project. GUDHI User and Reference Manual. GUDHI Editorial Board, 2015. URL http::/gudhi..gforee inria. farraa.r/doo
6,
[47] P. Tillet, H. T. Kung, and D. Cox. Triton: An intermediate language and compiler for tiled neural network computations. In Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, pages 10-19. ACM, 2019. ISBN 978-1-4503-6719-6 6, 14
[48] I. Trofimov, D. Cherniavskii, E. Tulchinskii, N. Balabin, E. Burnaev, and S. Barannikov. Learning topology-preserving data representations. In ICLR, 2023.
[49] Wald, Goessweiner-Moht A. Real-Hohn, D. Blaas, and C. Marlovits. DMSO might impact ligand binding, capsid stability, and RNA interaction in viral preparations. Sci. Rep., 14 (1):30408, Dec 2024. 6, 16
[50] C. Wang, Q. Wu, X. Liu, and L. Quintanilla. Automated machine learning & tuning with FLAML. In KDD, 2022.
[51] S. Zeng, F. Graf, C. Hofer, and R. Kwitt. Topological attention for time series forecasting, In NeurlPS, 2021.
[52] C. Zhang, H. Wan, S. Liu, X. Shen, and Z. Wu. PVT: Point-voxel transformer for 3d deep learning, 2021. URL httttt/////axi/ org/ abs/2108. 06076. arXiv. 9, 10
[53] W. Zhirong, Song, Khosla, Y. Fisher, Z. Linguang, Xiaoou, and J. Xiao. 3D ShapeNets: A deep representation for volumetric shapes. In CVPR, 2015. 10, 16
[54] A. Zomorodian and G. Carlsson. Computing persistent homology. Discrete Comput. Geom., 33 (2):249-274, 2005.
13

---

Supplementary Material
In followiin supplementary parts to the main manuscript, we discuss implementation details & provide dataset descriptions (in Appendix A), some additional experiments (in Appendix B), and all proofs (in Appendix C) for our theoretical results.
A Additional details
A.1 Implementation details of masking and flooding procedures
In this section, we provide an algorithm for computing the musking and (approximate) flooding process tailored to modern GPU architectures.
First, recall that we compute for each simplex o Del(L) its (approximate) filtration value f(o) = maxper,, min d(p.x) with P.r C conv(ar) finite set of points on the convex hull of or,
As described in Section to avoid computing all Deeeell |Pal- |X] pairwise distances d(p.x), we identify for each simplex or a subset points from X over which the minimum min d(p,x) is achieved. Specifically, this set is B V5r (cor) n X, where (cor an enclosing ball of computed using a variation of Ritter's heuristic. CCecking for all simplices or E Del( which points x X are within V2rr (cor) requires [Del(X) |X distance evaluations. In fact, by presorting X along one coordinate axis, we can compute, for each simplex ar, a slice X, of X enclosing the ball Br, (co) via two binary searches, leading an O |Xol [X] log X + |Del(L) L)) log (X|) complexity, which is usually much faster than doing all [Del(L) |X| distance evaluations. The distances d(co. x) can then be computed independently, and are therefore straightforward parallelize, yielding Boolean masking matrix of shape [De(()) x |X].
To be more precise, in implementation, also presort the simplex centers ca along the same coordinate axis. This allows for efficient selection a common bounding slice 8n for an entire batch of simplices to compute masking matrix of shape b Xa, where b = |B] is the batch size. The non-zero indices of the masking matrix are then, together with the points in X₁ and the sets io B, input to custom Triton [47] kernel, which efficiently computes the directed Hausdorff distances f(r)).
We first initialize (with infinity) an array A of shape b x |Pol in shared memory which collects the The kernel is then launched
minimal distances min x(p.x) ) for all E PB == (Por....,PPry a grid of multiple independent programs, each scheduled multiprocessors. Each program receives the points in the slice XB and a chunk of simplex points Po all from the same simplex Moreover, it receives chunk of non-zero (a.xx) index pairs of the masking matrix, where we ensure that, for one chunk, all pairs correspond to the simplex ar. It then computes the minimal distances min, d( p)x,,, where the minimum is taken over all in the chunk, and finally writes these values to A via an atomic min operation. Once all programs terminate, the filtration value fa) of each simplex in the batch is computed by taking the maximum of row of A.
the GPU's streaming
In fact, when representing each simplex or by discrete set Po defined in terms of barycentric coordinates as described in Section 4 (or any other discrete set P., such that P, C Par for all faces T C o"), we can directly extract the filtration values its faces by taking the maximum along the rows over appropriately selected column indices. It therefore suffices to perform the masking and distance computation only on batches of maximal simplices.
We additionally support CPU implementation based on k-d tree [5] data structure. Avoiding the masking step, we directly build k-d tree on the points X and compute the (global) minimal distance matrix A (of shape [X] PPr)) using nearest-neighbo queries for each (oreDelt) Pa.
14

---

A.2 Source code
Flooder source code. We provide the full source code for constructing the Flood complex with subsequent PH computation at
Furthermore, for easy use, practitioners can install (including dependencies) our Python package flooder" (which is available on PyPi) via
pip install flooder
Below minimal working example (MWE) of how to compute Flood on 1M points sampled from the surface of torus. Other examples, including timing experiments, can be found in the examples folder the GitHub repository listed above.
from flooder import (
flood_compledd generate_landmarke
)
DEVICE "cuda"
nnps 1.000 000 # Number of points to sample from torus
nlmms 1_000
# Number of landmarks for Flood complex
pts generate_noisy.toossppoiii 3ddnndddss
lms generate_landnarks(ptts, n_lms)
stree flood_ cond_ecopss lms, return_simplex_tree-Tuue
stree. compute_persisteence
diags
for r3nge(3)]
Datasets. addition to the Flood complex implementation, the flooder package provides all point cloud datasets used for the object classification experiments in Section 5.3. These datasets ready-to-use, with all pre-processing steps already applied and come with pre-defined splits to ensure reproducibility. These topologically challenging datasets can serve standardized benchmark for future research in topological data analysis and machine learning on point clouds in general. Below is minimal working example (MWE) of how to load a dataset.
from flooder. datasets import CoralDataset, MCBDataset, RocksDataset, Modealeet10Datsset,, SwisscheeseDataset,,
dataset CoralDataset(' l/coral_ //coral_attaset") for data in dataset:
print (data. x. shape, data.y)
Experiments code. Experiments can be reproduced using the following repository:
A.3
Computing infrastructure
The main experiments
SUSE Linux Enterprise Server 15 SP6 system with AMD EPYC 9554 64-Core Processors, 1024 GB of main memory, and NVIDIA H100 80GB HBM3 GPUs.
all experiments with flooder (v1.0rc5)
15

---

A.4 Dataset details
In the following, we provide a more detailed description of the used datasets and their properties.
Corals. We collected and curated a challenging 3D point cloud classification dataset by uniformly sampling IM points from surface meshes of corals obtained from the Smithsonian 3D Digitization initiative". In particular, this dataset is subset of all coral meshes that are available under CCO license, classified by genus. We label the corals according to their genus, and only use classes that have at least 30 instances. Overall, this yields a binary classification problem with a total of 83 available coral meshes. Specifically, there are 31 corals with the genus Acroporidae and 52 with Poritidae. On average, the meshes have = 900k vertices (ranging from 2 29k (with 18 884450 vertices) is shown in Figure 6. In particular, the coral Leptoseris paschalensis (USNM 53156), which is the mesh with the most vertices the collection, also used to showcase the capabilities of the Flood complex in computing PH on large point clouds; see Section 5.1.
Figure 6: One example of Poritidae coral.
10M with median 500k). A rendered example
Mechanical Components Benchmark (MCB). We used a subset, dubbed mcb-c, of the publicly available MCB-A dataset [32] assess the classification performance on geometrically and topologi- cally challenging objects. We filter MCB-A by (1) mesh size and (2) class size. In particular, we only take meshes with more than 10k vertices and then keep classes with more than 30 remaining instances. Here, the vertex count of a mesh serves as proxy of geometrical complexity. with the intuition that object meshes with a larger number of vertices tend be geometrically more complex. After filtering. 1.745 meshes split into 1l classes remain (out of 68 original classes), with x 34.5k vertices on average. Finally, we uniformly sample 1M points from each mesh surface to obtain our training/testing point clouds.
ModeINet10. modelnet10' is subset of the larger ModelNet40 benchmark [53] with 10 object categories (bathtub, toilet, table, etc.) distributed across 4,899 surface meshes. Originally, we have 3,591 training and 1,308 testing instances. We aggregate all meshes and then create ten random 80/20% training/testing splits. On average, we have x 9.5k vertices per mesh. Overall, this dataset contains geometrically rather simple objects with few characteristic topological features. From each surface mesh we uniformly sample 250k points.
This point cloud is obtained from cryo-electron- protein structure of RV-A89* The raw (density) data is provided as voxels, which we first smooth out by applying 3D average pooling (with kernel size stride and padding 1). We then transform it into a point cloud by taking the centers of the voxels that pass the provided density threshold (of 0.151). This results in | x 12.3M points.
Rhinovirus.
reconstruction [49] of the
Rocks. We created a point cloud dataset mimicking porous materials using the PoreSpy library [23]. In particular, create 1k Boolean voxel grids of size 256², whose true values define the point clouds. In addition, we compute the surface area of a voxel grid as the sum over all voxels of the differences between the voxel grid and its shift by 1 along axis. Following this strategy, we create 500 voxel grids using the fractal noise data generator and 500 using the blobs generator. In both cases, we select the porosity hyperparameter from uniform distribution on [0.05, 0.95], resulting in point cloud sizes between 800k and 16M. The hyperparameters that affect the surface area (i.e., frequency for fractal noise and "blobiness" for blobs) are empirically tuned that wide range of (porosity, surface) tuples is approximately uniformly covered, see Figure 7. For details, we refer to the source code.
B
Additional experiments
B.1 Runtimes on different GPUs
We compare the runtime for computing Flood PH using different GPU architectures. Specifically, we report runtimes (in s) on an NVIDIA GeForce RTX 2080 Ti, a GeForce RTX 3090 and H100 NVL
available at https://3d. /d. si. edu/corals
avviilable at https://modelnet cs. princeton. edu
available at http:///www.emattreesrrreeee 00w.///550.////-0000.00
16

---

Fracial Nuse Bllas
1.2
Suriac Anet
110
2.5
12.5 15.0
points
Figure 7: Two point clouds from the rocks dataset with similar porosity and surface area, created using the blobs generator (left) one using the fractal noise generator (middle). right panel shows the number points plotted against surface area (i.e., the regression target) for both generators. The black square O indicates the location of the two examples.
card. As in Section 5.2, we evaluate on the vertices of the meshes used for generating the corals dataset and show results in Figure 8.
RTX
RTX 3090
Relative runtime
Runtime (in s)
H100 NVL
10
Number of points (in M)
Number of points (in M)
Figure 8: Absolute (left) and relative (right) runtimes of Flond complex construction plus persistent homology computation the vertices of coral meshes different GPUs. Hyperparameters were 2048 landmarks, 1024 random points and batch size 256.
B.2 Additional results on large-scale point clouds
We present additional results to Section 5.1. Figure 9 extends Figure 2 and shows all persistence diagrams from the RV-A89 virus and the Leptoseris paschalensis coral. Figure 10 shows bottleneck distances to Alpha PH the full coral point cloud for varying numbers of landmarks. When comparing to Figure 2, one notices the much larger runtimes Flood PH on the coral point cloud, which is increased by factor of around when many landmarks
used, e.g., 27 versus 14 seconds when using 5k landmarks and 35 versus 17 seconds when using 10k landmarks. On closer inspection, this is caused by the masking step of Flood PH being more successful for the latter, resulting in only around half of the distance comparisons that need to be done for computing the filtration values.
B.3 Effect of landmark selection method
In Table 4, compare the bottleneck distances between Alpha PH the full large-scale point clouds from Section 5.1 when landmarks are selected using either farthest point sampling (FPS) or uniform random sampling (abbr. Rand). We report results obtained when using 1 landmarks and filtration values are computed from grid with 30 points per edge. Specifically, we report mean and standard deviations from 25 runs, where the randomness in FPS comes from different initial points. As expected, FPS achieves a better coverage of the point clouds, resulting in lower Hausdorff distances between landmarks and the point cloud, and consequently lower bottleneck distances the persistent homology of Alpha PH (full).
17

---

Persistence diagrams of RV-A89 point cloud
Hg
F4
17.5
250
15.0
200
125
150
7.5
7.5
100
05
100
5.0
Alpha PH (full)
2.5
2.5
Alphal
0.9
0.0
0.0
255
5.0
7.5
10.0
12.5
15.0
17.5
20.0
Persistence diagrams of Leptoseris coral point cloud
in Hi
1/
17
Sogo
Alpha PH (full)
2
2
Alphal
01
Figure 9: Hexbin plots of persistence diagrams of the RV-A89 and Leptoscris coral point clouds. Gray is Alpha PH on the full point cloud, blue Flood PH with 10k landmarks, orange is Alpha subset of size 175k.
Bottleneck distance da
20
20
A #Landmarkss (Flnod PH)
275k
10k
3
3
3
225k
#Poonns (Alpla:
10
10
2k
175k
Hausdurll
1k
125k
200
75k.
10
20
30
10
20
30
20
30
Runtime (in s)
Runtime (in s)
Runtime (in
Figure Appreximation quality of Flood and Alpha on Leptoseris paschalensis coral. (left) panel shows bottleneck distances to Alpha PH (full) in Hg. H₃ and H2 when varying the number landmarks for Flood PH and the subsample size for Alpha PH. The (middle) panel shows the Hausdorff distance between the full point cloud and the landmarks, resp., the points in the subsample. The (right) pancl shows the color coding used in all the plots.
Table Comparison of bottleneck distances (dz) between Alpha PH (full) and Flood PH when selecting landmarks using FPS and uniformly random (Rand) sampling on the large-scale point clouds from Section 5.1.
RV-A89
Leptoseris Paschalensis FPS
FPS
Rand
Rand
Hausdorff distance dir (L,(L, X)
44.7 # 0.2
79.1 + 4,0
8.2 + 0.1
20.0 + 3.3
Boutlenec distance d in Ho Bottlenck distance dø in Hh Bottleneck distance dg in Hh
1.7 0.1
3.2
0,9 # 0.1
0.9 0.1
3.9 0.8
0.5
1.0 0.1
1.2 0.2
5.7
5.4
1.2 0.2
2.6 3.2
18

---

C Theory
C.1 Proofs
For E Rd and bounded set X c Rd, we define d(p,X) ) = minxex d(p,x). We recall the definition of the directed Hausdorff distance
max min d(x,y) max d(x, F) du (X,Y)
(7)
xex yey
xeX
for bounded sets X, c Rd..
For completeness, we include a proof that the directed Hausdorff distance satisfies a triangle inequality. Lemma 8. Let (X, d) be a metric space and let A, B, C C be compact. Then,
d(a, C) max d(a, B)
d(b, C)
(8)
aeA
aeA
bEB
Proof. Fix do E A. Since A, B, are compact, there are by e B such that d(as, B) = d(as, bo) and co C such that d(bo. C) d(bo, co). Hence,
d(ag, C) = inf d(as, c) s d(as. cp)
cEC
s d bo) d(bo, ca) = d(ag, B) d(bo. C)
max d(a, B) + max d C) aeA
bEB
Since ag was arbitrary, we conclude
max d(a, C) s max d(a, B) + max d(b, C) acA
acA
8
Proof of Theorem
Proof. Letor e Del(L) and denote by ; :Dl(L) - R* the filter functions that define Flood L) and Flood(X', L), respectively. Observe, that is the directed Hausdorff distance between conv(er) and X, which satisfies the following triangle inequality (see Lemma 8),
f(o) p
d(p,X) S
d(p,X') + max d(x', (X) f' d(x', X): x'eX
pecoov((r))
x'eX"
and therefore f(r) - f' S max d(x',X) As, similarly, (' f(o) s maxxex d(x, X'), conclude
(s(0) f'()) s max max d(x, X'), max d(x', x) dın(X,'))
xxeX
x'ex
The main stability theorem from [15] then implies Eq. (2) which concludes the proof.
Proof of Corollary
Proof. Upon combination of Theorems 2 and 3, and Hausdorff stability of Alpha complexes, immediately get Vi N:
d (dgm, (Alpha XX), (Flood L)))
s dp (dgm, Alpha(X)), (Alp + da (dgm, (Alphaa)))) (gg ())
s dx L) + dh L) (X,
19

---

Proof of Theorem
Proof. To prove the theorem, we need show that dgm; (Flood L)) and DaXL) d conv(cr) interleaved. As already mentioned, Flood, (X. L) c Flood, (X, L, P). Consequently, suffices show that Flood, (X, L, P) Flood,+e (X, L) for any r and < maX dn or, conv(or)). (o)))))on())))
L. P)) are
To this end, assume that e Flood,(X, P), i.e., Po c Uxex (x),,, and let max (L)
By assumption, for each q E conv(or), there is a point p E Po such that d(q.) p) e. Moreover, since Flood, (X, P), for each p Po there exists a point Xp E X with xp) s r. Hence,
d(g.X) S d(q.xp) S d(g. p) + d(p.xp) s
(10)
and thus Flood, (x, I., P) c Flood,+e (X, L.. Eq. (5) then follows from [15].
Proof of Lemma
Proof. Let o = (vo...., } c Rd a k-simplex and let Po = {p = Ei E: Σ 4; q o uivi E conv(or) there exists a point = div; E Po such that 1u; A/1 s 1/m for every i = O.....k. k. Now, let ó; == - 2; and observe that Σ 6; = O. It follows that
m. E N} c conv(ar) be the grid points. For any
2 2 911 = 2
Σ
6iv
= 2
Σ
6v.,(v).)))
1=0
1,1
2
Σ
_ 5, Σ 5ellval1 -Lo, E
1.
Σ 0;0; (Iv:Il +11v,11 2((vvv)))
Σ
61ō,[1v; -v,11
and therefore that
llp q112
Σ 6,ō vyl1 21155
1 m²
Σ
(11)
Since this holds for any q E conv(cr), we conclude (P (oooPoooo)) s 1 m Eiss 1lv;
1ll
similar result holds with high probability for randomly sampled points as shown next.
Lemma 9. Let Po c Rdd be set of independently drawn points from uniform distribution co)v(or of size Ō(e D(e=dIn((/))) In(1/)). Then, with probability of at least 1 (over the choice of Par), we have
du( ( conv(rr) S < <diam(or)
(12)
Proof. Let O, and let Q, (Q 2m) be partition of into sets of diameter at most F == e diam(or), which can be obtained, e.g., by taking a covering of or with balls B, of radius 7/2 and letting
2 e
k=1
Note that m is smaller than the covering number of conv(o) for radius r/2, and therefore m s (4 dr) (4e)d_ By standard balls in bins argument [37], we obtain
P
max d(p, P.)) diam( (r) =F max d(p, Po)) peo
& Pljj n. = s me IPa.l/m
pEo
Taking | 2 (4 In (4/))+In(Va)) m In(m (5) yields (maxxerr d(x, Po) > ediam(o)) s 5 which establishes the claim.
20

---

Proof of Lemma?
Proof. Let o [Vo...... v and let p= Eii day; e conv(ar), i.e. Σ d; with A; > 0. Since X, 2 arg min x(,xx implies d(2. p) & ((p.v;) for each E (l....,ke k). therefore suffices to minimize x(p.x) over E Bmin d(p.)) N
Below, will show that if (c(c) is an enclosing ball of 0,, then for any p conv(or) holds that min, ((p.s)( c (c),(c), and therefore that maxpecom) min d(p.x) maxpecom((rr een (c) x(p.x).
First, consider an arbitrary point E Rd. Observe that
|| cll |lv; pll + llp cll² 2(v; p.p pc) c)
for each vi E or, and therefore
Σ A|l = Σ Fn0
A cll
Σ 1=0
A [|lviiplf pP
(d( = -1p-cc A A
1=0
1=0
1=0
where the last equality follows from Σ d = and Σ dv, p. particular, B, (c) is an enclosing ball of o (and therefore conv(or)), then
cll
Σ 1=0
A1lv, cl1
& - pl1 s 2² min Σ 2=
11v - -pl?
i=0
Hence, if Bmin; d(p. v) (p), i.e., ||2 - pll - 1pp - vyll. then
|| cll z min ||v; - pll + ||p - cll
s min [lv; - pll + 1² - I|V; - pll
max s v/2 - 52
OsrSr
V2r
C.2 Proof of Theorem
In this section, we cover the homotopy equivalence between Flood, (X, and the union of balls Uxex B, (x). Specifically, we show that |Flood, (X, X)] is homotopy equivalent |Alpha, (X),, which, according to the nerve theorem [24, Corollary 4G.3), is homotopy equivalent to Uxex (x).
C.2.1 Background tools
Let us first collect some tools and background information on Voronoi diagrams and Delaunay triangulations which, in arbitrary dimensions, express themselves combinatorial complex.
Voronoi complex. Consider X Rd be finite point set. Then, a Voronoi complex tessellates Rd into closest-neighhor cells around the points x. That is, we define by VC(x, X) = (p E Rd: x(p,x) s d(p, {)) the Voronoi cell of w.r.t. X. Below some facts regarding Voronoi cells:
A Voronoi cell is d-dimensional convex polyhedron, i.c., the intersection of half spaces. A Voronoi cell is unbounded if and only x on the convex hull of X: in other words, the Voronoi cell is convex polytope if x is in the interior of the convex hull of X.
As a convex polyhedron, the Voronoi cell itself possesses combinatorial complex structure, i.e., its lower-dimensional faces are convex polyhedra again, and so are the non-empty intersections.
The Voronoi diagram Vor(X) (X) usually defined geometrically as the union of the boundaries of the Voronoi cells. From combinatorial perspective, it is more convenient to define the Voronoi diagram
21

---

Vor(X) as the union of the Voronoi cells as complexes, and Vor(X) ) is then itself a complex of convex polyhedra. To emphasize this, we speak of the Voronoi complex and refer to the components of the Voronoi complex, (.) as Voronoi faces.
Any k-dimensional Voronoi face f from Vor(X) is characterized by d k points x1..... Xd-k of X as follows: any point f is equidistant to .I.....Idd-.. d(x.x;) s X) and, if x is from the relative interior relintf of f. then we even have d(x,x;) d(x, X (x).....dd))))). We call Ad- the defining points of f.
Delaunay complex. We can naturally dualize a k-dimensional Voronoi face by the simplex o formed by its defining points x....... -d If we do this for the entire Voronoi diagram Vor(X), we obtain the Delaumay complex D).(X). We distinguish between the combinatorial simplex o = ..I......d-.. and its geometric realization |o|| conv(or). It will be convenient to denote as |0||
Note that |orl² and |or| are orthogonal, however lorl* might not intersect |or|. So, let us denote by aff |or|" the affine hull of Jor!". i.e., the smallest affine subspace supported by |or| (e.g.. in case of lor being a line segment, aff |or would be an infinite line). Then, if dim |o|| < d. the point |or| n aff larl is the closest equidistant point to the defining points of or. Also note that the distance function d(-. has no further local minima on aff |or|" and, in fact, is convex on aff |or|* (the Euclidean distance from given point is convex on any affine subspace). In particular, if aff |or is of dimension I, then walking along this line away from |or| n aff [or]* increases the distance to or, and walking towards |or| i aff |arl* decreases this distance.
Simplicial collapses. Given an abstract simplicial complex Σ, it is often possible to simplify its structure while preserving the homotopy type its geometric realization |Σ] using simplicial collapses. Specifically, if (T, E Σ are pair of simplices such that T C a is face of a, dim o dim T + and has no other cofaces, then the removal of the pair (r, or) from is called an elementary collapse. Similarly, if dim or > dim r and all cofaces of U r of are faces v C or of oT, then (starting from the top) there a sequence of elementary collapses removing all such simplices v, including r and o. Such sequence is called a (simplicial) collapse, and simplex satisfying the assumption is called a free face of Σ. Importantly, simplicial collapses induce a deformation retraction between the geometric realizations of the complexes before and after the collapse, and therefore preserves the homotopy type. Consider filtered complex (E, r 2 0} that stays constant between filtration values i i+ 1 but changes at i when simplex is added. If, at r i 1, a simplex is added, resulting in a change of the homotopy type between Σ, and Σ,+1, then we call the addition of critical event. If instead multiple simplices are added at + 1 but their removal is simplicial collapse from Ei+1 to Σ, then we call their addition a regular event.
Alpha complexes. The Alpha complex Alpha, with radius on a set X X is defined as the nerve of (VC(x, X) n (x)x): x E X}, i.e., C X is a simplex of Alpha, if and only if 0. By the nerve theorem, IAlpha, Uxex Br (x). Moreover, as a subcomplex of the Delaunay triangulation Del(X), it is naturally embedded in Rdd An equivalent definition of Alpha complexes is given by the filtration function
Axeo-VVCx X)
n (,))
homotopy equivalent to
SAlpha Del(X) - R, o inf (
0: 0: (VC (x)) #
(13)
X
Lemma 10. Let X c Rd be in general position. A simplex r Del(X) is a free of Alpha (a if and only (rl O relint/r|* = 0.
0. Then, the point q E |r| that is closest to r is on the boundary 0| Hence, q is also closest to other points x X i.c.. there are o with & E |arl* and fo) = (T) = d(q. r). Sorting these cofaces in descending order by their degree, we get a sequence of elementary collapses which will eventually remove т. For details, refer to standard textbooks such as [20].
Proof. Assume that
Conversely, assume [4] |r| n relint|z|". Then 4 is the closest equidistant point to and therefore SAlpha (T) = d(g. r). Moreover, since 4 E relint|r|?, there is no or r with q E |or|*, and hence, no coface of r is added at filtration value fAIpha(T). Hence, T is not free face of Alpha (r))
22

---

[r]
B
1rl
H
Figure 11: The existence of p e VC(x, X) n (B n H) implics that x is on the circular are that bounds the tiled region, and therefore x H.
C.2.2 Properties of the Flood filtration
Throughout this and the subsequent section, we will only consider Flood complexes whose landmark set L is the entire point set X. In this situation, the filtration function given by
fFood Del(X) R.
max X): e |or])
(14)
It is worth mentioning that the point p |oi| that realizes f = d(p, X) cannot be in the interior of a Voronoi region VC(x, X) of some point E X.
Lemma 11. Let c R² in general position. A simplex T & Del(X) is a free face of Flood (ranl()) if and only [r| O relint/r!* 0.
Proof. Let {q} = |r] O aff Since is the unique point on |T| that is equidistant to r. it is the point of |r| that is contained in X, the latest, ie.. only after the largest radius r. Consequently, q E |r] implies fFlood()) = d(q. r). Moreover, E relint/r| implies that every coface or C r contains point q' E |or with d(q', or) d(q, T). Therefore, froood (o) > froood (T), and is not a free face.
|T|* that is closest to T is on the boundary 0|r|". Hence, q is also closest other points x E X \ i.e., there are = T with q |or|". In fact, since X E R2, |T] must be an edge and |o|| = |r [v}] must be a triangle with additional vertex v. To show that 7 is free face, we need show that or has the same filtration value, i.e., that the point o E |ol that realizes (o)) = d(o. X) satisfies o E |T]. To this end, denote by H the closed half-space bounded by a that contains |ar], and denote by B := Bulg.or)(q) the ball whose boundary is the circumeircle of |or|. Observe that o must be on a Voronoi edge, and thus, we need to show that d(-, X)|1ar increases along the Voronoi edges towards |r]. The latter true, every I-simplex y E Del(X) whose Voronoi edge ly|* intersects |or] satisfies (i) y C H, and (ii) the point of l with minimal distance to y is outside the interior relint|or| (because d(. y) is convex on Ixl²).
Assume that [T| n relint/r|* = 0. Then, the point
We first show y H. In fact, we show the (slightly) more general result that for any x X, VC(x, X) n B H) # 0 implics x E H. Obviously, the latter is true, if E T. Hence, from now on we assume x E X \ r, as illustrated in Figure 11. By assumption, there is point p VC(x, X) n (Bn H). Since E VC(x, X), it holds that == d(p,x) < d(p. T). Further, circular segment of B defined by [r]. In particular, p is contained in the subset of H that orthogonally projects onto |r] Hence, the circle C, (p) with center and radius 7 intersects the affine hull | only in a subset of the segment [T]. As |T| a chord of B, this implies that (,(p) \ B H. Since also x E (p) \ B, we conclude x H.
B n H, i.c., is in the minor
To finish the proof, we need to show that the point affly|* that minimizes the distance to y is not in the interior of |or]. But this point c is simply the midpoint of ly|, and therefore c E ly|- Hence, E relint|or| would imply that ly| intersects relint|or|, which contradicts that [Del(X) is well-defined geometric realization, i.c., that realizations of simplices only intersect in a common face.
23

---

Lemma 12. Let X C C. in general position and let o E Del(X). Then, ( & fAlpha(O) with equality if and only if |or |orl* * 0.
Proof. Denote by the center of the minimal enclosing ball of c. observe that e |or|, and that (o)) & d(c, or). Assume that SAlphu = r. Then, |o n Ixco (x) * 0, and therefore C nxxer (x) # 0. In particular, E Exxe (x), and thus fFl S d(c,or) S f Herein, equality holds if and only if lorl n Exo (x) {c). The lemma then follows because c E |or and | O |or| is either empty or a singleton {c).
C.2.3 Proof of the theorem
Lemma 13. Let X c. RR2 be in general position and let or e Del( ()). The addition of o to Alpha( X) a critical event if and only if the addition of a to (X)od(X) a critical event. Moreover, both are true, then, frooo (r) = (o))
Proof. Let o E XX), The addition of o to Flood or (X) is a regular event if and only if o is free face coface free face in Flood frima or Alpha Alpha (or) respectively. By definition, the addition of a is a critical event if it is not regular. The lemma then follows directly from Lemmas 10 to 12.
Theorem 14. Let X 2 be in general position. Then, Flood, (X, Alpha, (X) and Uxex Br (x) have the same homotopy type for any 2 O.
Proof. The homotopy equivalence between Alpha, and Uvex (x) follows directly from the nerve theorem, see also [19] for the construction of particular deformation retraction. Hence, suffices to show the homotopy equivalence between Flood, (X, X) and Alpha, (X), To this end, we will construct a sequence of simplicial collapses from Flood, (X, X) onto Alpha, (X) for each where each collapse is an elementary collapse of an (edge, triangle) pair.
to 11 < 1 exists with ( = 1; or fAlpha (or) = f, We prove by induction on the 4,-
be the ordered list of filtration values for which simplex or Del(X)
Induction hypothesis. For any there exists sequence of simplicial collapses from Flood, (X, X) to Alpha, (X).
Induction start. At filtration value fn = 0, it holds that Floodo (X, X) = X Alphaa (X).
Induction step. Assume that there exists sequence of collapses from Flood,, XX onto Alpha, (X). We will modify this sequence to get a sequence of collapses from Flood,.,, (X, X) onto Alpha (X).
For brevity, will denote F, Flood, (X, X) and A, := Alpha, (X).
Given a filtration value [++1 there are three non-exclusive possibilities:
(i) There is Del(X) such that (c)) f2+1 but fAlpha I+1.
(ii) There is Del(X) such that fAlpha (cr = 1:+1 but ( f+11
(iii) There is Del(X) such that ( f/+1 falpha(or).
For now, assume that at each filtration value li+1 only one case is true.
Case (i). By Lemma 13, the addition of each such to Flood, (X, X) is regular event. Specifically, Fr.. = Fr, U fildod ((i+1)), and the removal of ((tiii)) from Fu,, is a simplicial collapse. Thus can simply prepend this collapse to the existing sequence of collapses given by the induction hypothesis.
((1+1))
Case (ii). Similarly as above, Lemma 13 implies that the addition of or to A,, is regular event and does not change its homotopy type. Specifically, A = Ar, U SAipas ((t+1)) and the removal of SAipaal ((t+1)) from Aç., is simplicial collapse. Since F, c A, for any r the pair /Alpaa ((r.1) was already added to Flood, at previous filtration time, thus (see (i)), its removal must be in our sequence of simplicial collapses from F,, onto Ar. Thus, the obvious candidate for sequence from
24

---

FiL: onto A is to take the existing sequence of collapses but to omit collapsing /Aipha ((1++1)) Note that collapsing AAlpha ((f++1)) can only create free faces that are in AG, so the collapses in our sequence from Fr, onto Ar are not affected by skipping the former. Thus, we have constructed a well-defined sequence of collapses from Fi.. onto As,.!
Case (iii). The last case is FiL \ Fu = A AA, =: -o The candidate sequence of simplicial collapses from Fi... onto A is the sequence Fr, onto A,, given by the induction hypothesis but applied f This is well defined, if any free face of Fú, whose removal is in the existing sequence of collapses is still free after the addition of frigua ((1+1)) } to Fr. However, be such free face r A,, so by the assumption that Fi.. Fr, A A,, no coface is added to Fú, filtration value f++1-
Fr, can only
To finish the proof, we need to discuss the case when the filtration values are non-unique. By slightly changing the filtration values of the regular events, we get two new filtered complexes Flood', Alpha' с (X)(X) with homotopy equivalences Flood, (X, X) Flood, and Alpha; Alpha, for all 2 0 that satisfy the previously made assumption that cases (i) (iii) are exclusive.
C.3 Example: the Flood complex of a circle
Herein, we will calculate Flood(X, L) when X == [x E R²: ||I||| = 1}, i.e. the entire unit circle, and L is selected using farthest point sampling (FPS). We will see that the deviation from the (persistent homology of) the thickenings X, depends only on curvature via the sagittas of circular ares. In contrast, for Alpha complex computed on L,, the deviation depends on the slope via their chord lengths. This geometric difference manifests in the different decay of the approximation error in bottleneck distances: linear in the number of L for the Alpha complex, but quadratic for the Flood complex, enabled by the additional information it can extract from X.
cost
Flood(X, L)
Alpha(L)
Figure 12: Flood(X X, L.) (left) and Al) (right) for the unit circle and [Z.] 12 landmarks (+) selected using FPS. The Flood complex matches the underlying topology already at lower filtration values.
Landmark selection. Without loss of generality, we assume that the initial point for FPS is at (1, 0) corresponding the angular coordinate of O. FPS then proceeds in stages, where in the k-th stage all points with angular coordinate 2/T/2* are selected (in arbitrary order), if they have not been selected selected, the resulting Delaunay triangulation on L. is
an earlier stage. Once all |z.| landmarks not unique. More specifically, it always contains [/.| edges along the circle connecting each landmark the landmark with next lower and next higher angular coordinates, but the remaining [Z] edges (across the circle) are arbitrary.
Structure of persistence diagrams. The persistent homology of Flood(X, L) does not depend on the choice of Delaunay triangulation. In fact, the lifetimes in Ho are just the lengths of the edges along the circle, which always in Del( (). Similarly, the only feature in H1 is born these edges are included in Flood, (X, L), and dies as soon as the entire convex hull of is flooded, which always occurs at filtration value 1.
as all
Filtration values of edges. We will compute the filtration values of the edges that are relevant for persistent homology, i.c., of those along the circle. Their filtration values are just the distance from an
25

---

edge's midpoint to the circle X, i.e., the sagitta of the corresponding are. Denoting the are length by 4, this just c Finally, we observe that there are exactly m := 2() 211og:(121))) short ares of length & := x/2 [/2110)((()) and [L] - m long ares of length 26. This is because if [L] is a power of 2, then all |z] arcs have length 2xt and adding any further landmark splits one long and into two short ones, see Figure 12. We conclude that
(0, cos( (/2))
m-times
(14) - m) m)-times }]
dFoo(Flood, (),
(0, 1 cos(
(15)
(0)
once
dgm,(Flood, L)) ([(1 cco((()s ()), 1)))
(16)
Bottleneck distances. We compare the persistent homology of the Flood complex with that of the thickenings (Xr )r) which (by slight abuse of notation) we denote as dX),(X). It is straightforward to that
dgm (X) = (000000)) and dgm (X) = (O, 1)]
(17)
(18)
Hence, bottleneck distances are just
1
dn (dgm(()) X), (FlooFl (X, L))) 7 cos( dy ( dgm, (X), (Flood, L)) =1 cos(d))
(by matching to the diagonal).
(19)
(20)
In particular, since 2z / L], we conclude that all bottleneck distances are smaller e if 2 arccos(1 | - <), i.e., if we use |L] 2nr /ar/arcco(1111 c) 2x 2x/ /2e landmarks.
Comparison with Alpha complex. We discard the additional information available through X and simply compute an Alpha complex on I.. Specifically, the arguments regarding the structure of persistence diagrams still apply, but now filtration values are not the sagitta of an are, but half the chord length. Hence,
dæ dgm (X), dgm (Alpha, d dgm, (X), dgm, (Alpha, (L))) =sin())
sin(Φ)
(21)
(22)
and [|]] 2x/aresin(e)) 2n/e are necessary.
26

---

D
Changelog
D.1 Camera ready revisions / changes from arXiv version v1 v2
We make the point cloud datasets used for the object classification experiments in Section 5.3 available as part of the flooder package. These datasets differ from the previous versions only (except for mcb-C C and modelnet 10, see below) in that they use different seeds for sampling the point clouds and also different daining/validationtee splits. For reproducibility, we reran all experiments on the now public datasets and updated Tables 2 and 3 accordingly. On the swisscheese, rocks and corals datasets, the new results are (up statistical uncertainty) in line with our initial results.
In the previous version of the manuscript, we selected a subset of mcb by joining MCB-A and MCB-B. This introduced duplicate point clouds (up scaling and translation) in the dataset, however, with distinct labels. We now use only subset of MCB-A. For modelnet1l we reduced the point clouds from 1M to 250k points reduce the file size and facilitate sharing the data, and normalized point clouds to have coordinates in [-1. I]. Moreover, we used different hardware for training the LGBM classification model, which uses the given training- budget of 10 minutes more effectively. As result, on mcb-c and modelnet 10. balanced accuracies of the PH methods improved significantly while the neural network baselines are still consistent.
27

---

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 provide, as claimed, both theoretical results (Section 3) and an experimental validation (Section 5).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 or 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 to other settings.
It is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Limitations are discussed in the conclusions and in separate section in the appendix.
Justification:
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 a 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 (c.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 a 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.
applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 important role 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 complete (and correct) proof?
28

---

Answer:
[Yes]
Justification:
The proof of all lemmas and theorems are reported in the appendix.
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 to provide intuition.
Inversely, any informal proof provided the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental 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 not)?
Answer: [Ye]]
Justification: We provide all details for the implementation of the complexes and training of the models. Moreover, we provide our source code.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be 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 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, 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 hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (c.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 case 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 should possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
29

---

Question: Does the paper provide open access to the data and code. with sufficient instructions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Code will be publicly available on GitHub, and we provide it to reviewers.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c/
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 NeurIPS code and data submission guidelines (https://nips. ccppiiissccpuuuuee ctcccc//pbbbb
for more details. The authors should provide instructions 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. If 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 supplemental material (appended to paper) 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 (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Hyperparameters and optimizers are described in the main part of the paper. Further details can be found in the appendix and the provided source code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented 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, 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 classification experiments and ablation studies, report averages with one standard deviation error bars and specify that they are with respect to cross cross-validene validation runs.
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, confidence 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, or overall with given experimental conditions).
30

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors). should be clear whether the error the standard deviation or the standard error of th mean.
It is 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 figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer:
[Yes]
Justification: Computing infrastructure is detailed in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, 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 the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:/
Answer: [Yes]
Justification:
The research conforms to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have 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 sure to preserve anonymity (e.g., if there is a special consideration due laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no direct societal impact the work performed.
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 or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses
(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.
31

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 out 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 as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses 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 by 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.
We recognize that providing effective safeguards is challenging, and many papers do not 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: Creators or owners of assets are properly credited in the main part of the manuscript. License terms specified in the supplementary material and license terms al always respected.
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 dataset.
The authors should state which version of asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi twcoiehhooe.. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
32

---

For existing datasets that are re- pa-akaaedd, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset'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: All newly introduced assets are carefully documented, i.c., details of the method are described in Sections 4 and 5 of the manuscript. Furthermore, source code is attached to the submission and will be released publicly in case of acceptance (including datasets used in this work as well as a documentation).
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/codd/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 was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an 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 details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution 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 Ethics, workers involved 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
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
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 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.
33

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The core method development in this research does involve LLMs.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components. ccCnnnfeeeeeeccss/2223 /LLM)
Please refer to our LLM policy for what should should not be described.
34


Reviews:
[{"review_id": "36Ox3dkk5v", "reviewer": "Reviewer_kVdM", "summary": "This paper introduces a novel construction called the Flood Complex, designed for efficient computation of PH on large-scale Euclidean point clouds. The key idea is to construct a filtered simplicial complex over a small set of landmark points by checking whether the convex hulls of Delaunay simplices are fully “flooded” (i.e., covered) by balls centered at the full dataset. This construction approximates the Alpha complex, while being orders of magnitude faster and scalable to millions of points. The authors provide theoretical guarantees (stability, approximation bounds), GPU-accelerated implementation, and extensive experiments showing state-of-the-art performance on both synthetic and real-world classification tasks.", "questions": "Please see my comments in the part of Strengths and Weaknesses.", "limitations": "Maybe yes.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n+ The Flood complex is a creative and non-trivial extension of Alpha/Witness complexes, enabling scalable topological analysis on massive point clouds.\n+ It tackles one of the central bottlenecks in Topological Data Analysis: applying PH at scale.\n\nWeaknesses:\n- In fact, I am completely unfamiliar with this direction. So, I don't know if it has any disadvantages.", "was_revised": true, "final_justification": "All my concerns are resolved. Hence, I recommend acceptance.", "rebuttal": "*Thank you for your overall positive feedback and recognizing the creativity and the relevance of our work.*\n\n> Weaknesses:\nIn fact, I am completely unfamiliar with this direction. So, I don't know if it has any disadvantages.\n\n▶ We understand that the paper is somewhat technical in parts. Yet, your summary very well captures the essence of our work, i.e., computing PH for low-dimensional Euclidean point cloud data at scale. We agree that this is, at the moment, one of the key limitations for ML practitioners when seeking to distill topological information out of data. Our approach is a first step towards mitigating this limitation in the low-dimensional regime.\n\nFurther, thank you for giving your best effort. We appreciate your perspective and, aside from technicalities, we would be grateful if you would point us to any potentially unclear points so that we can make our work more accessible to a broader audience (outside the topological and geometric deep learning communities)."}, {"review_id": "9JO7kXjTSN", "reviewer": "Reviewer_ruYk", "summary": "This paper focuses on the central problem of the computational expense of persistent homology.  The paper proposes a new complex that is able to handle large scale point clouds and thus make the computation of persistent homology on some datasets that have so far not been possible.  Some theoretical guarantees are given and a nice, complete experimental study is carried out.\n\nWhile I would not classify the contribution of the work to be under \"AI\", it does make persistent homology a viable tool to then be used to study problems in AI.", "questions": "Some comparisons are carried out wrt the alpha and witness complexes, for example, which I suppose provides a satisfactory (but somewhat underwhelming) \"guarantee\" of the performance of the method, but an important outstanding question that does not seem to be addressed is the correctness of the result, more specifically, the correctness of the algorithm (which was not detailed in the submission, I imagine that it probably appeared the appendix which was not submitted).  In the experiments, persistent homology was computed on massive datasets where it was to date not possible: how can we be sure that the resulting barcodes are indeed the correct barcodes?  If correctness cannot be proven, then some theoretical results on convergence of the method to the \"true\" barcode is a really important missing theoretical result.  Are there details on this in the missing appendix?  If so, they should be moved to the main body of the paper.", "limitations": "Limitations were discussed briefly in the main body of the paper, but given the potential impact of the work, I would like to see a more honest, sober analysis and ablation study of the contribution.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 1, "strengths_and_weaknesses": "The problem that the paper studies is undoubtedly one of the most important problems in computational persistent homology and, in my view, one of the main limitations of the approach in applications: persistent homology simply does not scale well and there are serious problems with applying it to datasets that are common in current application areas and other fields, and definitely machine learning.  The contribution of this submission has the potential to overcome this and expand the potential and applicability of persistent homology as a tool.\n\nA limitation of the work that I see is that it still relies on considering smaller subsets of the data, which is a natural/classical approach and takes away from the originality but nevertheless, the contribution of the work is definitely very important.  Additionally, proposing another complex is not very original, but again, nevertheless, a solid way to workaround the problem.  However, the biggest weakness I see and most problematic aspect is that it appears that the appendix was not submitted and so I could not check details (and would have liked to), which I see as quite a serious oversight.  This is the main reason for my borderline assessment of the paper.", "was_revised": true, "final_justification": "As discussed with the authors, although I do not find the approach original (especially after reading the rebuttal and realizing that their proposed new complex is homotopy equivalent to a very classical existing one), I do believe that the computational advantages offered are important and will have significant potential for impact in the field of topological data analysis. For these reasons, I have decreased the originality score but have increased my overall recommendation to accept the paper.", "rebuttal": "*We thank you for the valuable feedback and for recognizing the importance of our work. \nBelow, we address all weaknesses (W) and questions (Q) point by point, enumerated as in the review. We specifically clarify the **availability** of the appendix as part of the supplementary material ZIP file.*\n\n> **Summary** While I would not classify the contribution of the work to be under \"AI\", it does make persistent homology a viable tool to then be used to study problems in AI.\n\n▶ We understand your point, but respectfully disagree with the assertion that our work lies outside the (broad) domain of AI. In fact, we address (and remove) a key barrier to the adoption of TDA methods in modern AI/ML research, namely the inability to compute persistent homology at scale. By facilitating PH computation on millions of points, our approach allows the extraction of stable, interpretable features at practical scales for tasks where data comes with a complex geometric structure. The latter has direct implications for domains such as robotics and 3D vision, but also generative modeling (e.g., to ensure global structural fidelity) or biomedical AI (e.g., molecule analysis). From our perspective, Flood PH advances the computational and algorithmic foundations necessary to apply a theoretically rich tool (PH) in precisely these settings.\n\n> **W1** A limitation of the work that I see is that it still relies on considering smaller subsets of the data, which is a natural/classical approach and takes away from the originality but nevertheless, the contribution of the work is definitely very important. \n\n▶ We want to clarify that our method consists of *two* building blocks: (1) the Delaunay complex on a *subset* of the data, i.e., the landmarks, and (2) a filtration on it that depends on the *entire* set of points. Contrary to simply considering only a subset of the point cloud (which is typically done in practice), in our construction, *all* points contribute to the filtration values. This is beneficial as it retains information that would otherwise be lost. On the `swisscheese` data (Appendix, Table 2), for example, we very clearly see that Flood PH allows to distinguish the two classes, while (even) repeated subsampling and computing Alpha PH fails to extract class-specific discriminative information due to insufficient subsample size.\n\n> **W2** Additionally, proposing another complex is not very original, but again, nevertheless, a solid way to workaround the problem. \n\n▶ We understand the criticism. However, we observed that the existing complexes, even when paired with efficient/optimized PH computation (such as the ones provided by Gudhi or Ripser variants), are unable to compute PH beyond dimension 1 for large-scale problems, or for datasets with thousands of point cloud instances, as common in ML tasks. Given the unfavorable computational complexity for computing PH on large (in terms of #simplices) filtered simplicial complexes, the only viable solution is to introduce a new complex that is (1) small enough (achieved via the landmarks) to precisely control computational complexity of subsequent PH computation, and (2) amenable to construction on dedicated GPU-computing hardware. The proposed Flood complex realizes both of these points.\n\n> **W3** However, the biggest weakness I see and most problematic aspect is that it appears that the appendix was not submitted and so I could not check details (and would have liked to), which I see as quite a serious oversight. This is the main reason for my borderline assessment of the paper.\n\n▶ The appendix (as well as the code) is available in the supplementary material (i.e., a ZIP file in our case), downloadable at the top of this page. Therein, we provide proofs for *all* theoretical statements, as well as additional details and experimental results. \n\n> **Q1** Some comparisons are carried out wrt the alpha and witness complexes, for example, which I suppose provides a satisfactory (but somewhat underwhelming) \"guarantee\" of the performance of the method, \n\n▶ We primarily present experiments with the Alpha complex (including subsampling experiments in the Appendix). From a computational perspective, Alpha PH is the only viable competitor given the point cloud sizes in our experiments. Even publicly-available Witness complex implementations (e.g., in Gudhi) cannot be computed at that scale unless the number of landmarks is extremely low (around 100); see tables in our reply to reviewer **Sf3t**.\n\n> **Q2** ... an important outstanding question ... is the correctness of the algorithm. In the experiments, persistent homology was computed on massive datasets where it was to date not possible: how can we be sure that the resulting barcodes are indeed the correct barcodes? If correctness cannot be proven, then some theoretical results on convergence of the method to the \"true\" barcode is a really important missing theoretical result. Are there details on this in the missing appendix? If so, they should be moved to the main body of the paper.\n\n▶ In Secs. 3.2 and 4.1, we present several approximation guarantees for our method. Specifically, we show (Theorem 3) in $ℝ^2$, that the Flood complex is topologically (homotopy) equivalent to the Alpha complex, if the landmark set $L$ is the entire point cloud $X$. Moreover, if $L\\subset X$, then the (bottleneck) distance between the persistent homology of the Alpha and Flood complex is bounded by the Hausdorff distance between $X$ and $L$, see Cor. 4. We hope that our clarification on the availability of the appendix (and all proofs therein) as part of the supplementary material ZIP file clarifies this issue.\n\n> **Limitations** were discussed briefly in the main body of the paper, but given the potential impact of the work, I would like to see a more honest, sober analysis and ablation study of the contribution.\n\n▶ In Appendix A.1., we specifically address limitations. We will (1) move the key elements of this section (e.g., homotopy equivalence only proven in $ℝ^2$) to the main part of the manuscript and (2) extend it by consolidating our sensitivity analysis - requested by multiple reviewers - to provide the reader with a clear picture of how the Flood complex behaves with varying parameters."}, {"review_id": "XKNI8VlMk0", "reviewer": "Reviewer_Sf3t", "summary": "This paper proposes the Flood complex to efficiently compute Persistence homology on large-scale point cloud data. Flood complex on a set of landmarks L contains all such simplifies of the Delaney complex on L that are covered by balls of radius r originating from data points X. Theoretical results shows that flood complex is an approximation of Alpha complex on X (alpha(X)), contains less simplifies than alpha(X), and due to efficient GPU implementation of computing filtration values it results in scalable and faster alternatives to alpha(X).", "questions": "1. In Figure 2, why Flood(X, L) total time the same as the Construction time? Does that mean the PH computation time is negligible? The same question for Fig. 4(a). Could you provide a more detailed breakdown of the total time in a table? \n\n2. Can the Flood complex be extended to non-Euclidean data, e.g., graphs?\n\n3. What is the computational complexity of Flood filtration construction?\n\nI am willing to adjust my score based on a satisfactory resolution of Weaknesses 1-4 with experiments.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The Flood complex is efficient to compute and scales to large-scale point clouds. \n2. The Flood complex results in better point cloud classification accuracy than the  alpha complex on the landmarks in a reasonable time. \n\nWeaknesses:\n1. **Limited consideration of Baselines:** Baselines are limited to alpha complex and sparse rips complex only. There several recent subsampling/landmark based PH approximation methods such as [1,2] that construct filtration for scalability, yet they have not been considered in the experiments. \n\n[1] Adaptive approximation of persistent homology, Journal of Applied and Computational Topology, 2024\n\n[2] Topological Data Analysis with $\\epsilon$-net Induced Lazy Witness Complex, International Conference on Database and Expert Systems Applications, 2019\n\n2. **Sensitivity analysis:** The authors do not study the sensitivity of Flood Complex with  respect to the choice of Landmarks. \n\n3. **Tradeoff between \\#landmarks and Approximation quality:** It is important to understand the tradeoff between the number of landmarks and PH approximation quality. Although the authors empirically studied it in Figure 4(d), the paper does not give a recipe for how many landmarks are enough for some user-specified approximation quality in terms of bottleneck distance. As a result, it is hard to determine how many landmarks someone should use when they deploy Flood complex for their own datasets. \n\n4. **Experimental results:** \n\n(a) The authors should report the tradeoff between #Landmarks and Acc. of Flood complex across various datasets in Table 1. \n\n(b) In Table 1, the improvement in Acc. (Due to Flood Complex) is negligible compared to Alpha+. \n\n(c) Similarly, in Figure 3, it seems the accuracy of alpha(X) with 100k landmarks is almost the same as Flood complex with 500k landmarks. Does that mean that if someone uses alpha(X) with more landmarks, one could obtain better results than Flood complex? Perhaps the author can extend the x-axis to 500k points to clarify this. \n\nd) In Figure 4, explain why Alpha is slower than the Flood complex? Is it due to using Gudhi, which is a CPU-based implementation in contrast to the Flood complex, which is GPU-based? Or is it because the Alpha complex is computed on the entire point cloud rather than on landmarks? Also, why is the dimension 2 column in Fig. 4(b) missing? \n\n5. **Better clarification on the role of GPU in Flood complex construction:** Referring to the supplementary material, I noticed the flood complex construction is not entirely based on GPU, the authors still need to (1) select landmarks on CPU and (2) construct alpha complex on the landmark on CPU. Hence, the authors should clarify the reason for the faster running time of the Flood complex and exactly what rolethe  GPU plays there.", "was_revised": true, "final_justification": "All my concerns are resolved. Hence, I recommend acceptance.", "rebuttal": "*We thank the reviewer for the constructive/positive feedback and the time spent. We address all weaknesses (W) and questions (Q) point by point enumerated as in the review and will adjust the paper accordingly.*\n\n> **W1** Limited consideration of Baselines:\n\n▶ Thank you, we will acknowledge both references. In fact, [1] and [2] are conceptually closer to the Rips than to the Alpha complex. [1] presents a method to compute a distance matrix between equivalence classes of points on which a Rips complex is built. [2] proposes a method to select landmarks for a lazy witness complex. Due to the underlying simplicial complex (which is much larger than an Alpha complex) in both works, the PH computation takes very long even on a few points.\n\nTo mitigate this issue, we use edge collapses as in [Boissonnat & Pritam. \"Edge Collapse and Persistence of Flag Complexes\", SoCG '20], but *still* the number of landmarks / equivalence classes that can be used is limited, and we face additional problems, briefly described below. \n\nIn case of [1], the selection strategy requires building a Delaunay triangulation on the *entire* point cloud, i.e., the very step we try to avoid with the Flood complex. To achieve a reasonable runtime, we first run FPS to obtain 2k points as input to their selection process. Balanced classification accuracies are ~50% on `swisscheese` and `corals`, and 45% on `MCB`.\n\nIn case of [2], when constructing lazy witness complexes (in Gudhi), only computing filtration values already takes long. E.g., for 100 landmarks on 10k witnesses from the `swisscheese` data, complex construction takes ~20s., and for 1M witnesses ~20min.\nHowever, in the former setting, we again obtain only 50% acc. on `swisscheese`.\n\n> **W2** Missing sensitivity analysis wrt choice of Landmarks.\n\nWe evaluate the sensitivity wrt the *landmarks selection* on the data from Sec. 5.1 in terms of the bottleneck distance $d_B$ to Alpha PH of the entire point cloud $X$. We compare FPS to (uniform) random selection (Rand). To isolate the effect of landmark selection, we compute the flooding radii based on a evenly spaced grid (instead of random, see response to **b9wn**) of points on each simplex. For reference, we also list results for **Alpha**† (on 75k points). \n\nVirus|FPS|Rand|Alpha†\n-|-|-|-\n$d_H(X,L)$|33.6|62.0 ± 2.3|26.2 ± 1.0\n$d_B-ℍ_0$|1.9|3.3 ± 0.1|3.6 ± 0.6\n$d_B-ℍ_1$|2.8|3.2 ± 0.4|7.3 ± 0.3\n$d_B-ℍ_2$|2.4|9.1 ± 2.1|7.9 ± 0.6\n\nCoral|FPS|Rand|Alpha†\n-|-|-|-\n$d_H(X,L)$|6.1|15.5 ± 3.2|5.3 ± 0.4\n$d_B-ℍ_0$|0.65|0.69 ± 0.07|1.16 ± 0.09\n$d_B-ℍ_1$|0.79|1.23 ± 0.06|0.93 ± 0.04\n$d_B-ℍ_2$|0.71|2.22 ± 0.38|2.01 ± 0.13\n \nBottleneck distances (the metric of interest)  of Flood PH (FPS) are significantly smaller than for Flood PH (Rand). The same applies to Alpha†, notably despite Hausdorff distances  of Alpha† are *larger*.\n\n> **W3** Tradeoff between #landmarks and Approximation quality\n\n▶ Approx. quality is upper bounded by the Hausdorff distance $d_H$ between $L$ and $X$, see Cor. 4. The latter decreases monotonically with #landmarks selected by FPS. For an empirical evaluation of #landmarks vs bottleneck distance in $ℍ_2$ on a `swisscheese` point cloud, we refer to Fig. 4 column (d). Further, we computed $d_B$ between diagrams of $\\text{Flood}(X,L_{\\text{FPS}})$ and $\\text{Alpha}(X)$ on the two point clouds from Sec. 5.1. using $10^k$ Landmarks for $k\\in \\{2.75,2.875,...,3.5\\}$.\n\n**Virus**\nLandmarks|562|749|1000|1333|1778|2371|3162\n-|-|-|-|-|-|-|-\n$d_H(X,L)$|56.7|50.3|44.8|39.8|35.7|31.6|28.3\n$d_B-ℍ_0$|1.8|1.7|1.9|1.9|1.6|1.7|1.3\n$d_B-ℍ_1$|6.9|5.1|3.6|3.8|2.7|2.7|2.7\n$d_B-ℍ_2$|7.6|5.5|4.3|4.2|4.2|4.2|2.9\n\n**Coral**\nLandmarks|562|749|1000|1333|1778|2371|3162\n-|-|-|-|-|-|-|-\n$d_H(X,L)$|10.7|9.3|8.3|7.3|6.5|5.7|5.0\n$d_B-ℍ_0$|1.2|1.0|1.0|0.8|0.8|0.7|0.6\n$d_B-ℍ_1$|1.0|1.1|0.9|0.7|0.8|0.8|0.6\n$d_B-ℍ_2$|2.1|1.7|1.3|1.0|0.6|0.4|0.5\n\n> **W4a** Tradeoff between #Landmarks and Acc. of Flood complex across various datasets in Table 1.\n\n▶ Below, we list classification acc / mse as a function of the #landmarks. As **b9wN** requested another dataset, the table includes two *new* columns for `rocks`, i.e., one binary classification task (cls) and a surface area regression task (reg). For a description of the dataset, please see our comments to **b9wN**.\n\n#Landmarks|cheese|rocks (cls)|rocks (reg)|corals|MCB|Modelnet10\n-|-|-|-|-|-|-\n20|0.81 ± 0.03|0.56 ± 0.07|0.068 ± 0.002|0.53 ± 0.12|0.51 ± 0.02|0.52 ± 0.02\n100|0.95 ± 0.01|0.67 ± 0.04|0.021 ± 0.001|0.64 ± 0.10|0.58 ± 0.03|0.57 ± 0.02\n500|0.98 ± 0.01|0.81 ± 0.03|0.0009 ± 0.0002|0.75 ± 0.11|0.61 ± 0.03|0.59 ± 0.01\n1000|0.99 ± 0.01|0.84 ± 0.06|0.0006 ± 0.0001|0.76 ± 0.10|0.63 ± 0.03|0.59 ± 0.02\n2000|0.98 ± 0.01|0.90 ± 0.04|0.0005 ± 0.0002|0.80 ± 0.10|0.67 ± 0.03|0.61 ± 0.02\n\n> **W4b** In Table 1, the improvement in Acc. (Due to Flood Complex) is negligible compared to Alpha+.\n\n▶ Our Table 1 results show a small but *consistent* improvement over Alpha†, including on the new (requested by **b9wN**) `rocks` data (see table above). \nOn closer inspection (via a paired t-test, as we evaluate on the *same* splits), the difference in mean between Flood PH and Alpha† PH is *statistically significant* (at 5%) on `swisscheese`, `MCB` and `rocks`, while on `corals` and `Modelnet10` it is not.\n\nNotably, for fair comparison, the #points used for Alpha† PH hinges on the runtime of Flood PH. In case of the latter, small implementation tweaks such as (1) allowing for larger batch sizes during Triton kernel computation (by transposing the computation grid), (2) implementing a Triton kernel for masking (see Sec. 4.2), and (3) adjusting block sizes for the GPU arch., yielded substantial runtime improvements (cf. Q1). Under these circumstances, the #points available to Alpha† decreases drastically and then **all** results clearly favor Flood PH (e.g., Alpha† on `corals` reduces to 0.63).\n\n> **W4c** Similarly, in Figure 3, it seems the accuracy of alpha(X) with 100k landmarks is almost the same as Flood complex with 500k landmarks...\n \n▶ While it is true that the accuracy of Alpha(X) on 100k points is close to that of Flood(X,L), the latter is *much* faster (2 vs. 11s). One might expect better performance of Alpha PH with more points, but this is *not* necessarily the case. In fact, existing vectorization methods (including the one we use) suffer from *oversmoothing* effects as the number of points in the diagrams increases, resulting in less discriminative vectorizations and a drop in downstream performance. On `swisscheese` Alpha PH on all of $X$ yields 93% ± 2% (at 70s/point cloud) and on `MCB` 60% ± 3%  (at 200s).\n\n> **W4d** In Figure 4, explain why Alpha is slower than the Flood complex?\n\n▶ Flood complex construction (1s) is faster than Alpha complex construction (90s) for *both* reasons you mention, and even a pure CPU-based implementation (which we offer in our code) is much faster (17s).\nThe complex construction uses only a subset of the points, and the rest of the data is used only for the (computationally) cheap flooding process. Our GPU implementation of the latter then yields a notable speedup over the CPU-only variant. \n\n> Dim. 2 column in Fig. 4(b) is missing.\n\n▶ Thank you for pointing this out; we will add the values to Fig. 4(b). For the Flood complex, runtime is 0.2s. For the Alpha complex, it is 1.3s (0.8s for construction and 0.5s for persistence).\n\n> **W5** Better clarification on the role of GPU in Flood complex construction...\n\n▶ For landmark selection using FPS and the Delaunay triangulation of the landmarks, CPU-based implementations are efficient when using dedicated data structures such as $k$-d trees.\n\nIn terms of runtime, the bottlenecks are (1) the pre-selection of relevant points per simplex and (2) the distance computations, see Sec. 4.2. Both steps are speed up when done on the GPU. That being said, we support a full ($k$-d tree based) CPU version (not submitted) to compute filtration values. For a typical case of 1M points and 2k landmarks in 3D, runtimes are around 17s, compared to 1s on GPU.\n\n▶ **Q1** *That is correct*. PH computation time is negligible (usually, <0.1s), as PH is computed from a filtration of a comparably small complex, i.e., the Delaunay complex on the landmarks. \n\n> Could you provide a more detailed breakdown of the total time in a table?\n\n▶ We report relative runtimes (in %) of landmark selection (FPS), complex construction, and PH computation on the *vertices* (ranging from 28k to 5.3M) of the coral meshes and on the `swisscheese` dataset (always 500k points) when using 1k and 2k landmarks. Avg runtimes are bout 1.3s (1k) and 1.8s (2k) on coral vertices,  and 0.7s and 1.2s on cheese.\n\n| |Corals (1k)|Corals (2k)|Cheese (1k)|Cheese (2k)|\n|-|-|-|-|-\n|FPS |6.8 ± 3.0|5.1 ± 2.3|11.3 ± 0.4|7.9 ± 0.2|\n|Complex|92.1 ± 2.6| 93.4 ± 2.0|86.3 ± 0.5|89.0 ± 0.2|\n|PH|1.0 ± 0.5|1.4 ± 0.5|2.3 ± 0.1|3.2 ± 0.1|\n\nWhen #landmarks is fixed, the share of time spent on complex construction increases with the point cloud size. When increasing #landmarks, the runtime of complex construction and PH computation increases more than that of FPS sampling.\n\n▶ **Q2** The idea of a flooding process on a triangulation of a subset of a point cloud can be extended to different metrics in $R^n$, but guarantees (if there are any) are harder to show without the Voronoi-Delaunay duality. For (non-Euclidean) graphs, extending the Flood complex is difficult, as the flooding idea relies on distances between $X$ and points in the *convex hull* of vertices, and therefore on an ambient space.\n\n▶ **Q3** As pointed out on `l198` of the paper, an upper bound is given by iterating, for each of the $m=O(|L|^{d/2})$ simplices, over the random points in $P_σ$ and the points in $X$, for a total of $O(m|P_σ||X|)$. With masking, one has $O(m|X|)$ distance computations to build the balls (see `l216`), and then for each simplex $O(|P_σ||\\tilde X|)$, where $\\tilde X\\subset X$ is the set of points inside the masking ball. We will clarify this!"}, {"review_id": "gU0o0zPyXg", "reviewer": "Reviewer_b9wN", "summary": "This paper proposes a novel filtration for point clouds the *Flood Complex*,\nthat approximates the well known Alpha complex, by using a smaller point cloud,\ne.g., a subsample, while still preserving geometric information from the\noriginal point cloud.\n\nThe paper provides theoretical approximation guarantees, as well as details to\ncompute an approximation and relaxation for a GPU implementation, which further\nmotivates this construction.\nIt finishes with an experimental section, showcasing the efficiency of the\nalgorithm as well as the statistical performances of the homology of this\nfiltration, which shows the practical the informativeness of this approach.", "questions": "- Can you comment on why the Flood complex performs better than the (more\n geometrically accurate) Alpha complex (when Alpha is computable) ?\n - Can you comment on the stability of the approach w.r.t. $L$ ?\n - Up to some proper quotient / filtrations, I feel that there is  a link between the\n perisistence image (c.f., [Persistent Homology for Kernels, Images, and\n Cokernels, 2009]) of the inclusion map of the Delaunay complex on $L$ into the\n alpha complex of $X$ and the persistent homology of your filtration.\n I wasn't able to formalize this, but I'm interested if you have the answer of\n this. This would also allow to define the Flood complex PH on other\n filtrations, e.g., Rips.\n - In Lemma 6. Isn't there a better (deterministic / entrop maximizing) way of\n putting the points in a simplex to better optimize this bound ? A similar\n statement can be said for (a,b)-standard measures [cuevas, 2004], but that's\n not very important.", "limitations": "yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n - This filtration is intuitively reasonable.\n - The approximations guarantees are a must-have.\n - The relaxation to a GPU-friendly approach is very positive. This kind of\n optimization making TDA practical is very important for general applications\n in modern machine learning.\n - The proofs are sound.\n - This paper is very well written. Figure 1 gives a good intuition.\n - Experiments. The gain w.r.t. the full Alpha complex is very motivating.\n\n\n## Weaknesses\n - Choice of $L$. Although the paper treat it by refering to fpsample, there\n are no guarantees given w.r.t this choice. There are some existing work on\n Witness complex that recovers some simplices of the delaunay complex for\n instance.\n - Choice of $L$ 2. The accuracies seem to reflect that this choice is not too\n impactful, but the paper do not provide an analysis on this choice. It would\n be interesting to see what (theoretically, and in practice) happens when we\n choose $L$ as a random (possibly non-uniform) subsample of $X$, and under some\n reasonable assumptions on the sampling measure of $X$. Such rates of\n convergence would allow to understand the tradeoff that we make when choosing\n the size of $L$.\n - Code. I installed the code and had issues with fpsample, so I couldn't run\n it. I manually checked the code, and it looked simple enough so that I could\n quickly read it. This is not a terrible issue, as this approach seems very\n easily implementable.\n - Code2. Unless I missed something, the code for the experiments is not given.\n - This is not fully on the GPU since a Delaunay complex is still needed in the\n end. This can be problematic in higher dimensions or if $L$ is too large (but\n is still better than the full Alpha complex).\n - It seems to me that this filtration is differentiable w.r.t. the initial\n point cloud, but this is not the case for its approximation on GPU.\n - Experiments. I was expecting to see bootstrap methods (e.g., Expected\n persistence diagrams / landscapes) or witness / sparse filtrations to be in\n the main body of the paper are they are natural competitors.\n - Experiments 2. I feel that they are too few datasets in the experiments. \n For instance, the only time the alpha complex could run was on an experiment\n in which it looses against the (less geometric informative) Flood complex.\n - Scope. I feel that the main contribution of this paper is in the field of\n computational geometry. I don't know how pertinent this work is to the NeurIPS\n audience.\n - Theorem 3. It would be very nice if this was true for any Euclidean space.", "was_revised": true, "final_justification": "All of my concerns were dealt with by the rebuttal and the following discussions. I'm keeping my score (accept).", "rebuttal": "*We thank the reviewer for the very positive feedback and the time spent. We address all weaknesses (W) and questions (Q) point by point, enumerated in the order they appeared in the review.*\n\n> **W1** Choice of $L$. Although the paper treat it by refering to fpsample, there are no guarantees...\n\n▶ Thank you for pointing this out. We will remark that when using FPS, the Haussdorf distance between the landmarks $L$ and the point cloud $X$ decreases monotonically #landmarks increases. In fact, the landmarks, if selected this way, are an $\\epsilon$-net of $X$, with $\\epsilon$ the min. distance between the last selected landmark to any other landmark.\n\n> **W2** Choice of $L$. The accuracies seem to reflect that this choice is not too impactful, but the paper do not provide an analysis on this choice. It would be interesting to see what ...\n\n▶ Our approx. guarantee (Cor. 4) wrt the full Alpha complex depends on the Hausdorff distance between $L$ and $X$. For an empirical study, we kindly refer to our response to **Sf3t**. In terms of theoretical aspects, we do not have a full answer yet. Still, if a sequence $(X_1,\\dots,X_n)$ is drawn iid from a probability measure on a totally bounded subset of any metric space $(𝒳, d)$, then the minimal distance $d_n=\\min_{i<n}d(X_i,X_n)$ satisfies $ℙ[d_n>\\epsilon]\\le𝒩(\\epsilon/2)/(2n)$, where $𝒩$ denotes the covering radius of that subset. This result (and others) is proven in [Kulkarni et al. \"Rates of convergence of nearest neighbor estimation under arbitrary sampling\", In: IEEE Trans. on Inf. Theory '95]. In our setting, this means that if $X$ is an iid sample from a measure on a bounded subset of Euclidean space (and $L$ is considered as the first #landmarks points), then $ℙ[d_H(X,L)>\\epsilon]\\le 𝒩(\\epsilon/2)/(2|L|)$, where $𝒩(r)$ scales as $r^{-d}$ where $d$ is the intrinsic dimension, i.e., $d=2$ for a surface (mesh) and $d=3$ for a volume. Stronger guarantees are possible if the point cloud geometry is taken into account.\n\n> **W3** ...issues with fpsample, so I couldn't run it...\n \n▶ We are sorry to hear you had issues; `fpsample` worked on all of our test systems. If you still want to try out our code, you could use torch_cluster's FPS implementation as a replacement (or select $L$ randomly).\n\n> **W4** ...the code for the experiments is not given.\n\n▶ You are correct, only a few examples were provided with our code. Unfortunately, we are not allowed to upload (or link to) additional material for the rebuttal. However, we will release the *full* code with all necessary parts for reproducibility after the reviewing phase. \n\n> **W5** This is not fully on the GPU since a Delaunay complex is still needed in the end. This can be problematic in higher...\n\n▶ We agree. The Flood complex is designed for low-dim. point clouds as an efficient alternative to the Alpha complex. We want to add, however, that there is currently no viable option to compute large-scale PH in high dimensions. E.g., computing PH (up to dim. 8) of only 100 uniformly distributed points in the 8-dim. unit cube already takes ~1min when using an Alpha or a sparse Rips complex with sparsity parameter 1 (theoretical guarantees require <1) on our hardware. \n\n> **W6** It seems to me that this filtration is differentiable w.r.t. the initial point cloud, ... Would you be more specific in this point...\n\n▶ The (approx.) filtration function is given by $f(σ)=\\max_{p\\in P_σ}\\min_{x\\in X}d(p,x)$, which is differentiable unless there are multiple minimizers (similar to max-pool. layers or L1 regularization). In practice, the Triton kernel prevents differentiability, as we did not implement the derivative function (*yet*). This will be done in the final release version.\n\n> **W7** Experiments. I was expecting to see bootstrap methods (...) or witness / sparse filtrations to be in the main body of the paper...\n\n▶ You likely have seen it; we compare to averaged persistence vectorizations in our appendix (Table 2) and can move them to the main part. We also compare to sparse Rips in Fig. 2. Regarding witness complexes, these methods shine in higher dimensions (as does the Rips complex) but are neither competitive to the Alpha nor to the Flood complex in the low-dim. regime. To the best of our knowledge, there are no sparse versions of the Alpha complex.\n\n> **W8** Experiments 2. I feel that they are too few datasets...\n\n▶ For our comparison to the Alpha complex, we consider two settings: one (Alpha-full) where the available information is the same, i.e., Alpha on $X$, and one (Alpha-†) where the available *runtime budget* is equal. However, in case of the former, runtime of the Alpha complex is prohibitive. Still, for the rebuttal we ran classification experiments using Alpha-full on `swisscheese` (93% ± 2%, 70s per point cloud) and `MCB` (60% ± 3%, 200s). Using more points does not improve accuracy, likely because of oversmoothing effects during vectorization. Moreover, the latter becomes slow and difficult to tune for large point clouds, e.g., vectorizing all Alpha-full diagrams from `MCB` takes 30min per split.\n\nTo address your datasets concern, we generated a 2nd synthetic dataset using the `porespy` library [Gostick J et al. \"PoreSpy: A Python Toolkit for Quantitative Analysis of Porous Media Images\". JOSS, 2019. ]. Point clouds in this dataset (abbr. as `rocks`) are extracted from boolean voxel grids of shape (256,256,256) that were constructed from *two* different generators (blobs and fractal noise), yielding point clouds of varying size up to 16M points. We evaluate (1) classification accuracy wrt the data generating method (i.e., 2 classes) and (2) regression accuracy wrt the surface area computed from the voxel grid. Please see our results in response to **Sf3t**.\n\n> **W9** Scope. I feel that the main contribution of this paper is in the field of computational geometry. I don't know how pertinent this work is to the NeurIPS audience.\n\n▶ We understand your point, but emphasize that our approach represents a critical advancement for the ML community, especially in domains where understanding data topology at scale is crucial. From our perspective, Flood PH facilitates TDA at modern data scales and thereby offers a way to integrate *global geometric reasoning* (via PH) into ML pipelines, which has been largely underutilized  due to computational constraints. Further, from a practical perspective, our work aligns well with what is prominently mentioned in a recent ICML position paper [Papamarkou et al. \"Position: Topological Deep Learning is the New Frontier for Relational Learning\". In: ICML 2024] in terms of availability of *efficient* TDA methods and software for ML problems.\n\n> **W10** Theorem 3. It would be very nice if this was true for any Euclidean space\n\n▶ Yes, this would be great. So far, we only have a proof in 2D where things can easily be illustrated, but we conjecture the theorem to hold in higher dimensions as well. Most of the building blocks for the general result are already there. The only extension missing is of Lemma 10, i.e., that *\"a simplex $𝜏\\in\\mathrm{Del}(X)$ is a free face of $\\mathrm{Flood}_{f\\_{\\mathrm{Flood}(𝜏)}}$ iff $|𝜏|\\cap\\mathrm{int}|𝜏|^\\dagger=\\emptyset$.\"*\n\n▶ **Q1** When Alpha is computable (which it is given enough time budget), one reason we identified is the inability of existing *vectorization strategies* to deal with massive persistence diagrams. Essentially, we observed over-smoothing effects (e.g., due to a large number of summations in the method we selected, but this similarly holds for other strategies) that confound the vectorization quality and thus negatively impact downstream classification performance. The rather small persistence diagrams of Flood PH are advantageous in this regard.\n\n▶ **Q2** In 2D, the Flood complex is stable wrt $L$, which follows directly from Col 4. Admittedly, the multiplicative constant of 6 is quite large and a more direct proof (also in higher dimensions) would be more satisfying. The difficulty when studying stability wrt $L$ is that the resulting filtrations are defined on two different simplicial complexes, i.e., on $\\mathrm{Del}(L)$ and $\\mathrm{Del}(L')$. We tried using a common subdivision, but were unable to link the difference in filtration values to the Hausdorff distance between the landmark sets.  \nIn the special case that there is a bijection $L'\\ni l_i'=l_i+\\epsilon_i$ such that $\\{l_i,\\dots,l_k\\}\\in\\mathrm{Del}(L)$ iff \n$\\{l'_i,\\dots,l'_k\\}\\in\\mathrm{Del}(L')$ it can be shown that $\\mathrm{Flood}_r(X,L)\\subset\\mathrm{Flood}\\_{r+\\epsilon}(X,L')$\n and vice versa, and therefore $d_B(\\mathrm{dgm}(\\mathrm{Alpha}(X)),\\mathrm{dgm}(\\mathrm{Flood}(X,L))<\\epsilon$ with $\\epsilon=\\max_i\\epsilon_i\\le d_H(L,L')$.\n\n▶ **Q3** Extending the Flood filtration to other complexes such as Rips would be great. Unfortunately however, there is no natural inclusion $\\mathrm{Del}(L) \\hookrightarrow \\mathrm{Alpha}(X)_r \\subset\\mathrm{Del}(X)$, unless no point of $X$ is inside a circumsphere of a simplex in $\\mathrm{Del}(L)$, which can be considered an unlikely boundary case. (On the contrary, we would like $L$ to sample $X$ \"well\".)\n\n▶ **Q4** You are correct regarding the uniform sampling. However, for efficiency reasons, it is not viable to optimize the point selection for each simplex separately based on its geometry. However, it is possible to select an evenly-spaced grid on the standard 3-simplex with $m$ points per edge (obtained from $\\{(i,j,k,l)\\in ℕ^4\\colon i+j+k+l=m\\}$) and use that as the barycentric coordinates of the simplex points. This approach has the benefit that filtration values of the faces can directly be computed from the 3-simplices by taking the max. over a subset of simplex points. We already used this *deterministic* approach to isolate the effect of landmark selection for the sensitivity analysis wrt the landmarks (see response to **S3ft**) and will support it in the upcoming code release."}]

Author rebuttal:

Meta-review: This paper addresses the problem of the computational cost of computing the persistent homology. To overcome the issue (i.e., computing PH is general is expensive), the authors of the paper propose a new complex that is able to handle large scale point clouds and demonstrate its usefulness by computing the PH using their method on some datasets that have so far not been possible. The theoretical guarantees are supported by comprehensive experimental evaluations.

The paper is technically very strong and its contribution is believed to be impactful to the TDA community. However this is its weakness as well, as it's not clear how this is connected to the NeurIPS community. But as there have been TDA papers published at NeurIPS, this seems to be a minor issue.

All the reviewers agree that this is a strong paper with nice technical contributions. Therefore, it would be beneficial for the research community to have this paper presented at the conference.
Decision: Accept (poster)