Cover learning for large-scale topology representation
Authors: Luis Scoccola
Uzu Lim
Heather A. Harrington
Venue: ICML 2025 poster (2025)
Keywords: topological data analysis
cover
simplicial complex
topological inference
mapper
manifold learning
Primary area: general_machine_learning->unsupervised_and_semisupervised_learning

Abstract: Classical unsupervised learning methods like clustering and linear dimensionality reduction parametrize large-scale geometry
when it is discrete or linear, while more modern methods from manifold learning find low dimensional representation or infer local geometry by constructing a graph on the input data. More recently, topological data analysis popularized the use of simplicial complexes to represent data topology with two main methodologies: topological inference with geometric complexes and large-scale topology representation with Mapper graphs -- central to these is the nerve construction from topology, which builds a simplicial complex given any cover of a space by subsets. While successful, these have limitations: geometric complexes scale poorly with data size, and Mapper graphs can be hard to tune and only contain low dimensional information. In this paper, we propose to study the problem of learning covers in its own right, and from the perspective of optimization. We describe a method to learn topologically-faithful covers of geometric datasets, and show that the simplicial complexes thus obtained can outperform standard topological inference approaches in terms of size, and Mapper-type algorithms in terms of representation of large-scale topology.

Cover Learning for Large-Scale Topology Representation
Luis Scoccola
Uzu Lim? 2 Heather A. Harrington 3
Abstract
1. Introduction
Classical unsupervised learning methods like clustering and linear dimensionality reduction parametrize large-scale geometry when it is dis- crete or linear, while more modern methods from manifold learning find low dimensional represen- tation or infer local geometry by constructing a graph on the input data. More recently, topologi- cal data analysis popularized the use of simplicial complexes to represent data topology with two main methodologies: topological inference with geometric complexes and large-scale topology vi- sualization with Mapper graphs - central to these is the nerve construction from topology, which builds simplicial complex given a cover of a space by subsets. While successful, these have limitations: geometric complexes scale poorly with data size, and Mapper graphs can be hard to tune and only contain low dimensional informa- tion. In this paper, we propose to study the prob- lem of learning covers in its own right, and from the perspective of optimization. We describe a method for learning topologicalll-faithii covers of geometric datasets, and show that the simplicial complexes thus obtained can outperform standard topological inference approaches in terms of size, and Mapper-type algorithms in terms of represen- tation large-scale topology.
1.1. Context
We are concerned with the problem of learning a representa- tion of the large-scale structure of geometric datasets, such as point clouds. Classical instances of this problem are the clustering problem, linear dimensionality reduction, and manifold learning. More recently, building on tools from algebraic topology and computational geometry, topologi- cal data analysis (TDA) was born with the goal of learning and quantifying the topology of data beyond the discrete and linear cases. What distinguishes TDA from previous methodologies, such as classical manifold learning, is its explicit reliance (higher-dimensionaa) simplicial com- plexes, with the stated goal often being that of producing simplicial complex which recovers the topology of the underlying space from which the data was sampled.
Simplicial complexes (Appendix A. are specific type of hypergraph. and were originally used in topology model topological spaces combinatorially; see Figure 1 for an ex- ample. Recent applications include neuroscience (Gardner et al., 2022), biology (Benjamin et al., 2024), physics (Sale et al., 2023), and machine learning (Maggs et al., 2024).
The two main methodologies in TDA are topological infer- ence with geometric complexes, and large-scale topology visualization with Mapper graphs; we elaborate on the lim- itations of these in Section 2 and Appendix A.4. In this unified unsupervised
paper, propose cover learning learning procedure which can efficiently represent the large- topology of geometric data, and simultaneously address the limitations of these two methodologies.
We now give more context and motivation for cover learning, and then describe our contributions.
'Centre de Recherches Mathématiques et Institut des sciences mathématiques. Laboratoire de combinatoire et d'informatique mathématique de l'Université du Québee à Montréal, Université de Sherbrooke, Canada. "Queen Mary University of London, United Kingdom. 'Max Planck Institute of Molecular Cell Biol- ogy and Genetics, Dresden, Germany: Centre for Systems Biology, Dresden, Germany: Faculty of Mathematics, Technische Univer- sität Dresden, Germany: Mathematical Institute, University of Oxford, United Kingdom. Correspondence to: Luis Scoccola cluis.scoccolat coaiooll@@mmil.coom gmail.com>.
1.2. Learning simplicial complexes
A simplicial complex on a set X consists of a simplicial complex K together with a function K₂ + Parts(X) from the vertices of K to the set of subsets of X. the idea being that vertices represent groups of data points, and higher- dimensional simplices represent relationships between these. Simplicial complex learning is the process of constructing a simplicial complex on an input dataset, and it encom-
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Cover Learning for Large-Scale Topology Representation
passes standard constructions such as graphs in classical unsupervised learning (e.g., neighborhood graphs in Lapla- cian eigenmaps (Belkin & Niyogi, 2003), t-SNE (Van der Maaten & Hinton, 2008), and DBSCAN (Ester et al., 1996)), simplicial complexes in topological inference (e.g., geomet- ric complexes (Edelsbrunner Harer, 2022) and Mapper (Singh et al., 2007)), and meshes is surface reconstruction (Dey, 2006).
11 Slapper
1.3. Learning covers
cover of a set X a family {Ui)er of subsets of X, which cover the sense that X User Us. Cover learn- ing is the process of constructing cover of input dataset.
ShageDtsooeer
The nerve construction from topology (Definition A. takes as input a cover U of a set X and outputs a simplicial com- plex over X, denoted Ner( In words, the nerve of a cover has as vertices the sets of the cover, and as higher- dimensional simplices the non-empty intersections between these sets; see Figure for examples. Thus, the nerve con- struction allows to reduce simplicial complex learning to cover learning, and suggests the following goal:
Figure Two covers a human 3D point cloud, obtained with ShapeDiscover and ID Mapper, and the nerve of the covers. ID Mapper's ' nerve a graph, with no topological information above dimension 1. ShapeDiscover's nerve 2-dimensional simplicial complex, reflecting the fact that the human shape is hollow.
Goal (Informal). Given a geometric dataset, cover by local patches, in such a way that the nerve of the cover is faithful representation of the shape of the data. More precisely:
1.5. Contributions
We describe our four main contributions.
(M) The sets the cover should be small with respect to the size of the dataset.
1.
We identify the cover learning problem as a general pur- pose unsupervised learning problem. We observe that several methods from TDA are in essence cover learning algorithms, and review their strengths and limitations (Section 2).
(G) The sets in the cover should be regular with respect to the geometry of the data.
(T) The nerve of the cover should be faithful representation of the topology of the data.
2.
We give a formal interpretation of the cover learning problem from the viewpoint of geometry and topology (Goal 2), and derive principled loss function for cover learning (Optimization Problem 1), in the idealized sce- nario where the data consists of a Riemannian manifold. Our main theoretical result (Theorem 3.2) shows that the terms in our loss function can be either computed or bounded from above effectively with standard losses.
We formalize condition (M) using measure theory, condi- tion (G) using geometry, and condition (T) using topology, specifically, homology (Appendix A.2).
1.4. Cover learning vs. clustering
3.
We propose practical estimators for the terms in our loss function, in the case where the space is a weighted graph, and show that optimization is feasible using known op- timization tools, including (graph) neural networks and topological persistence optimization (Section 4).
The clustering problem can be understood the zero- dimensional case of the cover learning problem, in which the relevant geometry of the data is entirely determined by the connected components, with relevant topologi- cal information above dimension zero. Although the cover learning problem cannot be completely reduced to the clus- tering problem, our proposed method does rely on clustering for initialization; see Section 4.3.
4. We provide an implementation ShapeDiscover (Scoc- cola Lim, 2025), a cover learning algorithm based on our theory, and showcase on two sets of experiments:
2

---

Cover Learning for Large-Seale Topology Representation
quantitative one on topological inference, and qualita- tive one on large-scale topology visualization. In the first case, ShapeDiscover learns topologically correct simpli- cial complexes, on synthetic and real data, of smaller size than those obtained with previous topological inference approaches. In the second, we argue that ShapeDiscover represents the large-scale topology of real data better, and with more intuitive parameters, than previous TDA algorithms that fit the cover learning framework.
Algorithm 1 ID Mapper cover learning algorithm
Input: Data X, function f X + R. clustering algo-
rithm Cg. parameter(s) 0 for Co. cover {4 of R
Take pullback cover { (4:) of X
Let U, == Co(ff (I)) for 1 1 S Return The union U := 24
Algorithm Ball Mapper cover learning algorithm
1.6. Structure of the paper
E Input: Data X, 0
In Section 2, we overview related work, specifically algo- rithms in TDA that fit the framework of cover learning. In Section 3, we develop theory for cover learning based on optimization, which we use in Section 4 to design cover learning algorithm. Section 5 contains computational exam- ples showcasing our methods. Appendix A has background, and other appendices contain details about theory and ex- periments.
Build e-net {u, {u.) of X
Return The cover (B(y,,))
4. Unsuitability for higher-dimensional topological infer- ence. The nerve of the cover produced by ID Mapper 1-dimensional, and does not contain higher-dimensiona. information. We elaborate on this in Appendix F.
2. Related work: cover learning in TDA
Many strategies have been proposed to overcome the above limitations: here we overview some of these. In (Chalapathi et al., 2021), limitation (2) is addressed by automatically refining the initial cover of the range of the filter function using information-theorett criteria; limitation (3) it also partially addressed by automatically searching for param- eters for the clustering algorithm. Similarly, (Deb et al., 2018; Bui et al., 2020; Alvarado et al., 2024) aim at mak- ing the choice of initial cover of the range easier and more robust, by. e.g., using variations in data density, while (Rus- citti & Melnnes, 2024) exploits variations in data density to improve the pullback cover directly. Multiscale Mapper (Dey et al., 2016) addresses limitation (2), at the expense of producing a one-parameter family of covers of the data (rather than a single cover), which can be analyzed using persistence. Limitation (4) can be addressed, as proposed in the original paper (Singh al., 2007). by allowing the filter function to take values in higher- dimeen--iienii Euclidean space, which renders the choice of the initial cover {4:]+= of the codomain of the filter function R" sigmificantly more delicate; we refer to this as multidimensional Mapper.
Although the concept of cover learning algorithm is intro- duced in this paper (Section 1), several unsupervised learn- ing algorithms in TDA are in essence cover learning algo- rithms. Here, we overview some of these. For other related work, see Appendix F.
Cover learning algorithms with filter function. To the best of our knowledge, ID Mapper (Singh et al., 2007) is the first cover learning algorithm designed with the nerve construction in mind (see Algorithm 1 for the cover learn- ing algorithm underlying 1D Mapper). The advantages of 1D Mapper are its simplicity and flexibility: different choices of the function
X - R., known the filter function, can provide widely different outputs, reflecting the structure of the data as seen by the filter function. We now describe four of 1D Mapper's 's main limitations:
1. Dependence and choice of filter. The filter function can be hard to choose if there are no obvious candidates. Moreover, to the best of our knowledge, there are no general methodologies for understanding the dependence of ID Mapper on the filter function.
Recently, and closest to this paper, Differentiable ID Map- per (Oulhaj et al., 2024) was introduced to address (1) by using optimization to automatically search for a filter func- tion; this comes at the expense of having to choose loss function and parametric family of filter functions.
2. Dependence and choice of cover of range filter. The initial cover { of R (or, equivalently, of the range [min f, max f] of the filter function) is also difficult to choose. This requires choosing the number of intervals k; as well as their endpoints.
Many variations of Mapper exist, and Mapper in general has been shown to recover meaningful geometric structure in applications (Nicolau et al., 2011; Rizvi et al., 2017). However, we believe that the existence of suitable filter function a strong assumption, and that it is worth consid- cring alternative solutions to the cover learning problem.
3. Dependence and choice of clustering algorithm. The choice of clustering algorithm Ca and its parameter(s) 0 also has a big impact on the output, and is a difficult choice, as is familiar from cluster analysis.
3

---

Cover Learning for Large-Seale Topology Representation
Cover learning without filter function. The category of cover learning algorithms which do not rely on filter function (implicitly or explicitly) is remarkably small. To the best of our knowledge, there is a single TDA cover learning algorithm in this category: Ball Mapper (Dlotko, 2019a;b), described in Algorithm 2. Consistency results can be proven for Ball Mapper, which imply that, contrary to cover learning algorithms based on ID filter functions, Ball Mapper can be used to do higher-diment dinees--imensionll topological inference.
Goal 2. Find open cover (Ui of M such that:
(M) (U;) is small for all i.
(G) (aU)( is small for all i.
. (T) {Ui)ier is homology-good cover of M.
Where H6 is the E-dimensional Hausdorff measure.
3.2. Optimization over spaces of covers
Ball Mapper's ss main limitation is its reliance on a global distance scale E > O, which must be chosen by the user, does not allow for variations in density, and is susceptible to the curse of dimensionality. Of note is the fact that Ball Mapper essentially equivalent to the Witness complex (De Silva & Carlsson, 2004) with parameter = 0 (Appendix G).
Solving Goal 2 directly using optimization is difficult, as the set of covers of a space does not have a natural smooth structure (even worse, when the space is finite, as the case for finite data, the space of covers is discrete). We thus turn our focus to larger space: that of fuzzy covers, which is space of functions, and which is easier to parametrize.
In conclusion, the only two TDA cover learning algorithms that do not require the user to provide filter function are Ball Mapper and Differentiable Mapper, and the latter still requires a parametric family of filter functions.
3.2.1. FUZZY COVERS
Observe that a k-element cover of a set, i.e., a cover of the form {U:) is the same as a function g X + {0, 1) such that maxigisa g((z) 1 for all x E X. Here, the max operation is ensuring that every element belongs to some cover element. Indeed, the equivalence is given by mapping cover {U:) to the vector (XU) XU²): X + {0, 1].e of indicator functions.
3. Theory
For the purposes of deriving sensible loss function for cover learning, let us first interpret Goal in the case where the data consists of a compact d-dimensional Riemannian manifold M. In order to make optimization feasible, we later extend the optimization space from that of covers to that of fuzzy covers (a certain space of function on M).
In order to turn the space of covers into a continuous space, we replace the two-element set (0, 1} by the unit interval [0, 1]. and define
Short topology recap. We need three standard notions from topology: homology, homology-good covers, and the nerve theorem; references are given in Appendix A, but let us describe the basic ideas here, for convenience. The homol- ogy construction takes input a topological space X, and returns vector spaces (X)X) for each i E N. in such way that dim (H:(X) counts the number of i-dimensional holes in X; for example, (X) counts connected components, while H (X) counts essential loops. A homology- -ood open cover of a topological space is a cover {U.)er such that, for every J S I, the reduced homology of Niee Uy is zero. The nerve theorem says that if U a homology-good open cover of topological space X, then the homology of the nerve Ner(2() is the same as that of X.
r
P E 10,1]* max P: =1] s
R
(1)
The exponent is - 1 in I represents the topological di- mension of the space. This notation is consistent with the usual convention that denotes the standard simplex with k vertices by A k-1 (see also Section 4.2.
Definition 3.1. A k-element fuzzy cover of set X is function X + pk-1
In order to produce a single cover out of a fuzzy cover, one can threshold it, as follows. Given any function f X + [0, 1] and a threshold À [0, 1]. consider the suplevel set (f > A} = fz X f(x) cover g x - rk-1 and X E [o, 1]. we can threshold the
A}. Then, given fuzzy
fuzzy cover to obtain a cover of X, as follows:
3.1. Formal goal
= { {g. > A} } hiiis.
Condition (M) in Goal is formalized by requiring the cover elements to have small measure, condition (G) by asking that the cover elements have boundary of small measure, while condition (T) is formalized by asking the cover to be homology-godd which ensures that the nerve recovers the correct homology, by the nerve theorem.
The fact that {g > A} is indeed cover of X follows imme- diately from the max-condition in Equation (1).
Since this will be of use later, let us remark here that a fuzzy cover g : X + p gives rise to a filtered simplicial complex (Ner({g > {)))xe(o.1) (see Appendix D).
4

---

Cover Learning for Large-Seale Topology Representation
3.2.2. RANDOM COVERS FROM FUZZY COVERS
In the statement of Theorem 3.2, if ʃ X - 0, is function on topological space, we define II So dim H(L > r}) dr, the integral the dimension of the reduced homology of the suplevel sets of f. This quantity also known as the length of the barcode or total persistence: see Appendix A.3.4 for details. The important point here is that this quantity can be estimated and optimized for in practice thanks to the theory of topological persistence opti- mization, effectively turning the nerve theorem into a loss function. See Appendix B. for a proof of Theorem 3.2.
Suppose that g : X + 1 is fuzzy cover of X. By sampling threshold À E [0. 1] uniformly random, and considering {g ^}, we get random cover of X, so cach fuzzy cover 9 induces probability measure My on the space of covers of X. Formally, the probability measure Pe is the pushforward of the uniform measure on [0, 1] along the function À + {g > }] (see Appendix B.3 for details).
Random covers in the context of TDA were first considered in (Oulhaj et al., 2024), with the similar goal of producing cover of a dataset via optimization (Section 2). Their methodology, however, follows the ID Mapper pipeline, and relies on filter functions.
Regularization. For theoretical and practical reasons, we add an L'-regularization term to Optimization Problem I, in the form of R(g) == Σies | 9: 122- From the theoretical point of view, we believe that this is necessary to guarantee existence of minima; from the practical point of view, this deals with the curse of dimensionality inherent in optimizing over a space of functions the data.
3.3. The idealized loss function
Loss function for Riemannian manifold. Our idealized loss function for fuzzy cover learning is obtained by taking the expected value of the conditions in Goal 2 for a random cover distributed according to the probability measure Pg corresponding to a fuzzy cover g.
Homology-godd covers up to a dimension. In practice, one might be interested in a cover whose nerve recovers the homology of the underlying space only up to dimension E N. This can be accomplished using the notion of & homology-good cover (Definition A.4) and refined version of the nerve theorem (Theorem A.5). The loss T can also be relaxed accordingly to get a loss Te, which only accounts for homology up to degree E, and the upper bound of Theo- rem 3.2 can also be relaxed in this case; this is described in Appendix B.2. The upshot is that, if only homology up to certain dimension is relevant, then less computationally intensive topological loss can be used.
Optimization Problem 1.
min M-M-Pt-1
aM- -M() + ag G(g) + ar T(g)
smooth
M(g) = Σ
E (1))
==1
k
G(g)= = Σ
B 11 (aU.))
4. Practice
1=1
T(Ø) = ( (U.) is not homology-good
Our practical approach to cover learning relies on three main considerations: estimating the loss of Optimization Prob- lem 1 (Section 4.1), finding a suitable parametrization of the space of fuzzy covers (Section 4.2), and computing good initialization (Section 4.3). Other practical considerations are required to make optimization feasible and efficient (Sec- tion 4.4). Building on these, we describe the ShapeDiscover cover learning algorithm in Section 4.5.
{Ui)/ random cover with probability measure Pg
Next is our main theoretical result, which allows us to mini- mize the loss terms in Optimization Problem in practice.
Theorem 3.2. If M be compact Riemannian manifold and g: M + p a smooth fuzzy cover, then
4.1. Loss estimation
M(g) Σ
Let X be the input data (seen as a set), and let G be a weighted graph with X as its set of vertices, and with weight w(x. for (x, y) E G representing relationship strength between & and y. Let g X + [0. 1 (for example, y could be fuzzy cover). Based on Theorem 3.2, we define the following estimators for the losses:
iET
G(g) Σ
1
iE!
T(Ø) S
Σ JCI
min Fj
JEJ
H
k
where I= = = Moreover, in the third case, the left-hand side is zero if and only if the right- side is.
M(g) = '7M
Σ
Σ 9ı(2)) x
5

---

Cover Learning for Large-Scale Topology Representation
The simplest option let 0 be n-by-k matrix, and to set fo fo( Oz.j-
((g) T]G
Σ
w(x,y) (gi(()) g((0)]
(x.
If x C RN then we can let upp RN - R be a neural network and set fo(x;) = (o (2;).
Po(g)= = I/T
|| lif
==1
If X consists of the vertices of graph, then we can let
R(g) = TJR Σ 1=1 (x.g)eG
Σ
w(a, -9:(()) 92))))
Po : (R + (I*)x be graph neural network, let V E (IR))* consist of a data-dependent vector (such as the first N eigenfunctions of the graph Laplacian), and
where yj,, IJG, WT, fjn are normalization constants (depend- ing only on the graph) for the purpose of having the losses be in similar ranges; see Appendix H.1.
set so (a:) = se (v)....
4.3. Initialization
For the topological loss, we use the relaxation which only considers O-dimensional homology (Appendix B.2), since O-dimensional homology is more efficient compute than higher-dimensional homology, and still performs well in the examples (Section 5.
In order to make optimization fast and reliable, it is nec- essary to use a good initialization. Any clustering of a set is in particular a cover, and we propose to use a geometri- cally meaningful clustering (obtained by, e.g., k-means or spectral clustering) initial fuzzy cover.
4.2. Parametric fuzzy covers
4.4. Other implementation details
In order to make our approach flexible enough to be com- bined with standard machine learning models, we first de- scribe way of turning any parametric vector-valued model fo X + R on the input data X into one of the form go + p thus parametrizing the space of fuzzy cov- ers the data. See Section 4.2.2 for possible initial models fe. including neural networks and graph neural networks.
4.4. 1. SMOOTH PARAMETRIC FUZZY COVERS
As described in Section 4.2, if fo X + IR* is a paramet- ric vector-valued model, then Too softmax o fo X + A 5o p is parametric fuzzy cover. However, the operation To given by normalization by the co-norm is not smooth. We thus propose to replace Too with Tp for some E (0) during optimization, and to only use Too to obtain the final fuzzy cover; see Algorithm 3. We expect larger values of k to require larger values of p, but this ap- proximation does not seem to influence results significantly, and we let p in all experiments.
4.2. 1. PARAMETRIZING FUZZY COVERS WITH SOFTMAX
Let E [1, oo], and define
4
[0, : | = 1
so that, in particular, = and A the stan- dard (k- 1)-dimensional simplex. A function : X + AR-1 is called a partition of unity, since it consists of func- tions hı,-.., h4 X - [0. 1] such that Σ, h4 1. Note that, by definition of the standard softmax function, we have softmax R + A Thus, given any parametric model fe : X + Rt, we obtain a parametric partition of unity by simply postcomposing with softmax.
4.4.2. TOPOLOGICAL OPTIMIZATION
In order to optimize the loss To we use the topological opti- mization with big steps of (Nigmetov & Morozov, 2024); see Appendix A.3.4.
4.5. ShapeDiscover
See Algorithm 3 for a high-level description of the proce- dure; here we give details about the subroutines. For details about the software we use see Appendix I.I, and for compu- tational complexity see Appendix C.
Now, note that for every p E oc], there is function Tp Af- + A given by normalization, i..., by mapping x to x /|~ So if fe X + R is a parametric model, we get a parametric fuzzy cover as follows:
SUBROUTINE NeighborhoodGraphh
Too softmax o fo X
A n1
The simplest approach is to nearest neighbor graph, with weights equal to 1. This worked well in most of our experiments. However, to make the method more robust, our implementation uses the weighted neighborhood graph of the UMAP algorithm (see Section 3.1 of (McInnes et al., 1)); this is what we use the computational examples.
4.2.2. PARAMETRIC MODELS
Depending on the type of data X = {I1,.... Jn there are different choices for fo:
6

---

Cover Learning for Large-Scale Topology Representation
Algorithm 3 ShapeDiscover fuzzy cover learning algorithm
4.6.2. DEFAULT PARAMETERS
Input: Point cloud X C RR
In all experiments we fix the following default parame- ters: number of neighbors for the neighborhood graph n.neigh = 15, regularization parameter reg 10, num- ber of iterations for gradient descent n-epoch = 500, learning rate for gradient descent 1r = 0.1, and approxima- tion parameter for fuzzy cover = (Section 4.4).
Parameters: n. coc N, n.neigh E N, reg > 0
Optimization parameters: ir, n.epoch, p E (c)
G: = NeighbottoddGraapii(..aaaaaa.))
= FuzzyCorehnntaallatiooQC...o
h = ParamettridPatiitiooOOUnniii/
When a filtered simplicial complex is needed, we reindex the output of Algorithm by log to have it be indexed by [0, oc) standard topological inference algorithms (Ap- pendix D). When a simplicial complex is needed, we thresh- old with À = 0.5 E [0, 1]. by default.
0' = Initialize Parmttiiie (h.
( M + reg- G G f zeg. - (Tp o ho)
= Gradient GradientDescem 1r, init =
Return no hg
5. Experiments
See appendix for details about software (Appendix I.I), datasets (Appendix I.2), computation time (Table 4), com- putational complexity (Appendix C), well as an ablation study and parameter and noise sensitivity analyses (Ap- pendix I.9).
SUBROUTINE FuzzyCoverlnttalizatti
We use spectral clustering as initialization: We compute the first D_cov eigenvalues of the normalized Laplacian of G, and apply k-means with & = n.cov to get a clustering of X, which we then simply interpret as a fuzzy cover, as described in Section 4.4.
We use ShapeDiscover with default parameters in all experi- ments (Section 4.6). We only vary the maximum cover size (n cnccov E N) and threshold [0, 1] (but only in MNIST and C. elegans data, otherwise default À 0.5 is used).
SUBROUTINE
We use the simplest of the approaches deseribed in Sec- tion 4.2: we let & be X ---by-n.cov real matrix, and let fu X + R& be defined by So(ms)) و = Oi.-- Then, the
5.1. Topological inference
A. EFFICIENT TOPOLOGICAL REPRESENTATION
parametric partition of unity is defined as softmax fo.
X x-4 A
We compare ShapeDiscover the standard approaches to topological inference on four datasets: synthetic 2-sphere, synthetic 3-sphere, sample of the surface of human (which is topologically equivalent to a 2-sphere). and the dynamical system video data from (Lederman & Talmon, 2018) (which is topologically equivalent to 2-torus). We do not use Mapper since current implementations are not suitable for higher-dimensional topological inference (Ap- pendix 1.5). Each algorithm takes as input number of vertices, and the goal is find the smallest number of ver- tices that achieves a certain homology recovery quotient, quantified as the proportion of filtration values at which the correct homology recovered (see Appendix I.4 for the definition). For more details; see Appendix I.3. Results are in Tables and ShapeDiscover performs best, followed by Witness (u 1).
SUBROUTINE Initialize PraiiiiizePPrmmeeriMMMMdddd
Since very simple model, initialization is straight- forward, and it amounts to setting 0/,- g(z:);
SUBROUTINE Gradient
We train for n epoch (or convergence) using an Adam optimizer with learning rate 1r and default parameters.
4.6. Output and parameter selection
We elaborate on how to use ShapeDiscover's output, and on how we choose its parameters in the experiments. See also Appendix I.9 for ablation study and parameter and noise sensitivity analyses.
B. TOROIDAL TOPOLOGY IN NEUROSCIENCE
4.6.1. 1. OUTPUT
In Appendix 1.6, we describe experiment the toroidal topology of population activity in grid cells in the dataset of (Gardner et al., 2022). In it, Shape is able to learn this topology using simplicial complex with just 15 vertices (see Figure 6), task that Vietoris Retoris-Ripss is not able to accomplish with simplicial complex with 5000 vertices.
The output of Algorithm 3 is fuzzy cover. Using the nerve construction (Definition A) the fuzzy cover induces a filtered simplicial complex (Appendix D), indexed by [o, 1]. Given any À E [0, 1], the filtered simplicial complex can be thresholded single simplicial complex.

---

Cover Learning for Large-Seale Topology Representation
5.2. Visualization of large-scale structure
learning, and to clustering and dimensionality reduction specifically. This paper is only a first step towards the development of efficient and robust cover learning methods. We now elaborate on the limitations of our approach, and give further motivation for future research directions.
For plotting conventions, see Appendix 1.7.
C. HUMAN AND OCTOPUS
We compare ShapeDiscover to ID Mapper (height as filter function), Ball Mapper, and Differentiable Mapper on hu- man and octopus datasets (Figure 7). In Figures and 2, Sha- peDiscover recovers the large-scale topology. including the fact that the figures are hollow, with a small number ver- tices, while ID Mapper and Differentiable Mapper recover the 1-dimensional structure, but not the higher-dimeesional one (Section 2). In Figures 11 and 12, Ball Mapper has main parameter (s) that is hard to tune, and has hard time recovering the correct topology.
Robust cover learning. Covers produced by cover learning algorithms will often contain spurious intersections, which can render visualization difficult, and lead incorrect topol- ogy recovery. This motivates the developing of robust cover learning, and of reliable and interpretable layout algorithms for cover visualization.
Consistency. Standard topological inference algorithms come with topology recovery guarantees, egg., (Boissonnat et al., 2018; Kim et al., 2020), and here we have not pro- vided such guarantees for optimization-based cover learning procedures. As an avenue for future work, we observe that the nerve theorem can be used to formulate computable conditions for covers which, when satisfied, guarantee topo- logical correctness of the cover, regardless of how it was obtained.
In the final two examples, we are interested in cover learn- ing without extra information (e.g., filter function), so we experiment with Ball Mapper and Differentiable Mapper.
D. HANDWRITTEN DIGIT DATASETS
We run ShapeDiscover and UMAP on small handwritten digits dataset and on MNIST. In Figures 4 and 15 UMAP and Sispoorre capture similar structure, correspond- ing well to digits and their similarities. We did not obtain meaningful results with other algorithms (Figure 14 and Ap- pendix 188).
Efficiency: Topological persistence optimization is slow for few reasons, including the fact that the whole dataset is required at each iteration step, precluding the usage of mini- batch during optimization. It is an open problem to find methods for topological regularization (i.e., for enforcing trivial topology), which can be computed in small batches of the data. It may be possible to develop such methods using probabilistic, sample-bast based algorithms for topological estimation.
E. FLARE STRUCTURE IN BIOLOGY
We use the data from (Packer et al., 2019), consisting of the gene expressions of cells of the C. elegans worm, and known to have flare structure corresponding to single-cell trajec- tories. We project the data to 2 dimensions using UMAP, which clearly identifies the flare structure of 16 cell types (1-16); see Figure 16 and Table 3. ShapeDiscover identifies the same flare structure (Figure 5). We were not able to obtain meaningful results with other algorithms (Figure 17 and Appendix 1.8).
Other cover learning algorithms. Cover learning being general unsupervised learning problem (like clustering), there is no single, ultimate cover learning algorithm, and other approaches should be considered. In particular, one could simplify our pipeline, as suggested by the ablation study (Appendix 1.9).
Point cloud vectorization. Point clouds can be vectorized by constructing graph on the data and applying methods from graph machine learning. Cover learning can be used to build graphs on data that are of much smaller size than those built using classical methods such as h-nearest neighbors, effectively reducing the dimension of the learning problem.
6. Conclusions
Motivated by the problem of representing the large-scale topology of geometric data for the purposes of efficient topo- logical inference and visualization, we have developed theory for cover learning based on optimization, as well as practical implementation of these ideas with easy-to-tune pa- rameters. We demonstrated that cover learning can improve upon the two main TDA methodologies with a single ap- proach, by effectively addressing their main shortcomings: the sometimes prohibitive size of geometric complexes, and the difficulty in tuning and the lack of higher dimensional information in Mapper graphs.
Persistence-based clustering, A main difficulty with many clustering algorithms is that the final number of clus- ters needs to be chosen by the user. This difficulty can be addressed with methods from density-based clustering and persistence-basee based clustering (Campello et al., 2013; McInnes et al., 2017). Fuzzy cover learning naturally pro- duces a filtered graph (Section 4.6.1), which can then be used as input to persistence- based clustering methods such as (Chazal et al., 2013; Rolle & Scoccola, 2024).
We believe that cover learning is relevant to unsupervised
8

---

Cover Learning for Large-Scale Topology Representation
Table Rows correspond algorithms taking number of vertices and outpurting filtered complex. Columns correspond dataset and a homology recovery quotient. Entries are the minimum number of vertices (left) and total number of simplices (right) needed to get further details.
required homology recovery quotient; see Appendix
Algorithm
2-sph 0.25
2-sph 0.5
3-sph
0.25
3-sph 0.5
human 0.01
human 0.05
dynam 0.01
dynam 0.05
Rips
3.2c3
2.1c5
1.2c6
1.7c9
111
6.2c6
129
1.le7
257
1.8c8
283
2.7c8
+ Rips DMS
578
1.6c5
8.8c5
OOM
OOM
0OM
0OM
0OM
S + Rips edg.coll.
15
1.5e3
48
1.6e5
44
8.0e5
184
1.5e9
111
1.5e3
129
2.0e3
257
2.4e7
283
3.5e7
S sparse Rips (==.5)
17
3.2e3
48
1.6e5
44
1.2e6
OOM
111
4,4e5
129
6.5e5
305
6.2e5
283
4.9e7
sparse Rips (s=1)
16
970
35
4.8c3
1.0e5
OOM
61
1.8c4
211
1.655
257
4.2c7
297
6.3e5
Alpha
83
159
355
1.5e3
85
1.8e3
261
6.7e3
OOM
OOM
Witness (v=0)/ MS BMappe
15
1.9e3
48
2.1e5
1.2e6
184
1.7e9
46
1.8e5
193
5.7e7
52
2.9e5
60
5.2e5
Witness (u=2)
10
385
10
385
17
9.4e3
17
9,4e3
51
2.7e5
46
1.8e5
78
1.5e6
90
2.7e6
Witness (v=1)
6
56
6
56
218
17
9.4e3
26
1.8e4
26
1.8c4
62
6.0e5
82
1.8e6
ShapeDiseover (v0.1)
30
5
30
119
1.6e4
19
5.0e3
19
5.0e3
18
4.0e3
52
2.9e5
Table 2. We use the number of vertices required by ShapeDiscover achieve the homology recovery quotients of Table run main algorithms, and report the homology recovery quotient.
Algorithm
2-sph 3-sph
buman
dynam 32
S + Rips
0.03
0
0.01
Alpha
0.01
Witness (v=0)/ MS BMapper
0.08
0
0.04
Witness (e=2)
0
Witness (v=1)
0.65
0
StapeDiscover (VO.1)
0.74
0.51
0.7
0.38
Figure 4. ShapeDiscover (n. cov = 15, À = 0.8) (left) and UMAP (right) on MNIST; see Figure for ShapeDiscover's cover the UMAP projection. The algorithms capture similar structure; a main difference that ShapeDiscover isolates large subset of the digit 1 (vertex I). Note that only 10 of the 15 clements of ShapeDiscover's cover are non-empty.
Figure 2. ShapeDiscoverr cov = 20) (left) and ID Mapper
(right) octopus dataset. See Figs. 8.9 for corresponding
Figure 3. ShapeDiscover (n.cov = 15) (left) and UMAP (right) on the small digits dataset; see Figure cover the UMAP projection. We that both algorithms capture essentially the same structure: most the digits are clearly distinguished, except for 8 and 1. Note that only 11 of the 15 elements of ShapeDiscover's cover are non-empty.
ShapeDiscover's
Figure 5. ShapeDiscover (n.cov 100. À 0.6) elegans data, recovering most of the flare structure captured by UMAP (Figure 16 and Table 3); 53 elements the non-empty.

---

Cover Learning for Large-Scale Topology Representation
Impact statement
al. Multiscale topology classifies cells in subcellular spatial transcriptomics. Nature, pp. 1-7, 2024.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Boissonnat, J.-D. and Pritam, S. Edge collapse and persis- tence of flag complexes. In 36th International Sympo- sium on Computational Geometry, volume 164 of LIPIcs. Leibniz Int. Proc. Inform., pp. Art. No. 19, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020. ISBN 978-3 978-3-95977-143-66
Acknowledgments
We thank the amonymous reviewers at ICML 2025 for their helpful and knowledgeable comments. I.S thanks Matt Piekenbrock for discussions about graph layout al- gorithms and Tatum Rask for help source datasets. HAH gratefully acknowledges funding from the Royal Society RRGFFEA 2010044, UF150238 and EPSRC EP/Y028872/1 and EP/2531224/1. LS was supported by a Centre de Recherches Mathématiques et Institut des Sciences Mathématiques fellowship. UL was supported by Lever- hulme Trust Research Project Grant RPG-2023- 144, BMS Centre for Innovation and Translational Research Europe, and Korea Foundation for Advanced Studies. The authors were members of the UK Centre for Topological Data Anal- ysis EPSRC grant EP/R018472/1.
Boissonnat, J.-D., Chazal, F., and Yvinec, M. Geometric and topological inference. Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge, 2018. ISBN 978-1-108-41089-2; 978-1-108-41939-0.. doi: 10. 10.1017797811002299966 URL https: /doi. 0tt///..1117//7111003222
Brugnone, N., Gonopolskiy, A., Moyle, M. W., Kuchroo, M., van Dijk, D., Moon, K. R., Colon-Ramos, D., Wolf, G., Hirn, M. J., and Krishnaswamy, S. Coarse graining of data via inhomogeneous diffusion condensation. In 2019 IEEE International Conference on Big Data (Big Data), pp. 2624-2633 JEEE, 2019.
Bui, Q.-T., Vo, B., Do, H.-A. N., Hung, N. Q. V., and Snasel, V. F-mapper: A fuzzy mapper clustering algorithm. tems, 1891105107, 2020. ISSN 0950-7051. doi:
References
Knowledge-Basee Based Sys-
Aliprantis, C. D. and Border, K. C. Infinite dimensional analysis. Springer, Berlin, third edition, 2006. ISBN 978- 3-540-32696-0; 3-540-32696-0. A hitchhiker's guide.
URL http:://www.ccceeeddiccc. sccience/attiiclepp////00/00
Alpaydin, E. and Kaynak, C. Optical Recognition of Hand- written Digits. UCI Machine Learning Repository, 1998. DOI: http:://0oi.rrg/102444422
Campello, R. J., Moulavi, D., and Sander, J. Density-based clustering based hierarchical density estimates. In Pacific-Asia conference on knowledge discovery and data mining, pp. 160-172. Springer, 2013.
Alvarado, E., Belton, R., Fischer, E., Lee, K.-.,, Palande, S., Percival, S., and Purvine, E. g-mapper: Learning cover in the mapper construction, 2024. URL https: abs/ 2009. 06634.
Carrière, M., Michel, B., and Oudot, S. Statistical analysis and parameter selection for mapper. Journal of Machine Learning Research, 19(12):1-39, 2018. URL http: 291 html.
Bauer, U. Ripser: efficient computation of rietoris-ripp per- sistence barcodes. Journal of Applied and Computational Topology, 5(3):391-423, 2021.
/ //jmlr.org httpg//apsss//ll////
Carrière, M., Chazal, F., Glisse, M., Ike, Y., Kannan, H., and Umeda, Y. Optimizing persistent homology based functions. In 38th International Conference on Machine Learning (ICMI. 2021), volume 139, pp. 1294-1303. PMLR, 2021.
Bauer, U., Kerber, M., Roll, F., and Rolle, A. A uni- fied view on the functorial nerve theorem and its vari- ations. Expo. Math., Pa): No. 125503, 52, 2023. ISSN 0723-0869, (1108866,1188-0001 1878-0792. 2023.04.005. URL https: /ttp:/iooo/...000000//000 j. w...matth.2222 C05.
doi: 10.10166j.exmath.
Carrière, M., Theveneau, M., and Lacombe, T. Dif- feomorphic interpolation for efficient persistence-based topological optimization. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024. URL https: /wwpereveeeeeeeeeeeeeeeeee net/ forum? i id=gY idxzxxX1 BZzdx.
Belkin, M. and Niyogi, P. Laplacian eigenmaps for di- mensionality reduction and data representation. Neural computation, 15(6):1373-133) 2003.
Benjamin, K., Bhandari, A., Kepple, J. D.. Qi, R., Shang, Z., Xing, Y., An, Y., Zhang, N., Hou, Y., Crockford, T.
Chalapathi, N., Zhou, Y., and Wang, B. Adaptive covers for mapper graphs using information criteria. In 202/
10

---

Cover Learning for Large-Scale Topology Representation
IEEE International Conference Big Data (Big Data), pp. 3789-3800. IEEE, 2021.
Edelsbrunner, H. and Harer, J. L. Computational topology: introduction. American Mathematical Society, 2022.
Chazal, F., Guibas, L. J., Oudot, S. Y., and Skraba, P. Persistence-baset clustering in riemannian manifolds. Journal of the ACM (JACM), 1-(6) 2013.
Ester, M., Kriegel, H.-P., Sander, J., Xu, X., et al. A density- based algorithm for discovering clusters large spatial databases with noise. In kdd, volume 96, pp. 226-232222 231, 1996.
Chen, C., Ni, X., Bai, Q. and Wang, Y. A topological regularizer for classifiers via persistent homology. In Chaudhuri, K. and Sugiyama, M. (eds.), Proceedings of the Swenty-Second International Conference Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 2573-2582. PMLR, 16- 18 Apr 2019. URL https::////c https::tttttseeeeeeeeeeee /ttp///ooceennsseeeee mml.. press /vess/885 9/ chen1 9g. html.
Fomenko, A. Visual geometry and topology. Springer- Verlag, Berlin, 1994. ISBN 3-540- 53361-3. doi:
URL
/ttcps://bii-org.eppp2 werooxyyyeeeeeemm
neu. edu/00.
Translated from the Russian by Marianna V. Tsaplina.
Gardner, R. J., Hermansen, E., Pachitariu, M., Burak, Y., Baas, N. A., Dunn, B. A., Moser, M.-B., and Moser, E. I. Toroidal topology of population activity in grid cells. Nature, (02(7895):123-1288 2022.
Coskunuzer, B. and Akçora, C. G. Topological methods in machine learning: A tutorial for practitioners. arXiv preprint wwXiv:2409.029000 2024.
Ghrist, R. Barcodes: the persistent topology of data. Bull. Amer. Math. Soc. (N.S.). 45(1):61-75, 2008. ISSN 0273-0979,1088-944 50273-0979-07-0119913 URL httts: /ttotttopp///oooro//// 10.
De Silva, V. and Carlsson, G. Topological estimation using witness complexes. In Proceedings of the First Euro- graphics Conference on -oist- Graphics, SPBG' 04, pp. 157-166, Goslar, DEU, 2004. Eurographics Associa- tion. ISBN 3905673096.
doi: 10.1090/
Gillespie, P. A homological nerve theorem for open cov- ers, 2022. URL 00388.
Deb, B., Sarkar, A., Kumari, N., Rupela, A., Gupta, P., and Krishnamurthy, B. Multimapper: Data density sensitive topological visualization. In 2018 IEEE International Conference on Data Mining Workshops (ICDMW), pp- 1054-1061. IEEE, 2018.
bxggabs//220 2210.
Hagherg, A., Swart, J., and Schult, D. A. Exploring network structure, dynamics, and function using net- workx. Technical report, Los Alamos National Labo- ratory (LANL), Los Alamos, NM (United States), 2008
Deng, L. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6): 142-142, 2012.
Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg. S., Smith, N. J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M. H., Brett, M., Haldane, A., del Río, F, Wiebe, M., Peterson, P., Gérard Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., and Oliphant, T. E. Array programming with NumPy. Nature, 585(7885):357-362 September 2020. doi: 10. (038/s41586-000-264992 URL https: http:/doi.ooooo 10. 10.1038/68 000000//41586022000
Dey, T. K. Curve and surface reconstruction: algorithms with mathematical analysis, volume 23, Cambridge Uni- versity Press, 2006.
Dey, T. K., Mémoli, F., and Wang. Y. Multiscale map- per: topological summarization via codomain covers. In Proceedings of the Twenty-Seventh Annual ACM- SIAM Symposium on Discrete Algorithmss, SODA '16, pp. 997-1013, USA, 2016. Society for Industrial and Applied Mathematics. ISBN 9781611974331.
Hatcher, A. Algebraic topology. Cambridge University Press, Cambridge, 2002. ISBN 0-521-79160-X; 0-521- 79540-0.
Diotko, Ball mapper: shape summary for topological data analysis, 2019a. URL https://arxiv. abs 1tts/9901.0744
Hensel, F., Moor, M., and Rieck, B. A survey of topolog- ical machine learning methods. Frontiers in Artificial Intelligence, 4:681108, 2021.
Dlotko, P. BallMapper: The Ball Mapper Algorithm, 2019b. URL package=Ba 1Maaper....... package version 0.2.0.
org/
Hofer, C.,, Kwitt, R., Niethammer, M., and Uhl, A. Deep learning with topological signatures. In Proceedings of the 31st International Conference on Neural Informa- tion Processing Systems, NIPS'17, pp. 1633-1643, Red
Edelsbrumner, H. and Harer, J. Computational topology: an introduction. American Mathematical Soc., 2010.

---

Cover Learning for Large-Scale Topology Representation
Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Lam, S. K., Pitrou, A., and Seibert, S. Numba: a llmm- based python jit compiler. In Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC,
Hofer, C., Kwitt, R., Niethammer, M., and Dixit, M. Comnecivity-optinized representation learning via per- sistent homology. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Confer-
LLVM 11, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450340052. doi: 10. L145/2833 URL https: /tt///di.ooo/ org/ 10.1145/2833151 2833111..2883366 62.
ence on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2751-2760 PMLR, 09-
Lederman, R. R. and Talmon, R. Learning the geometry of common latent variables using alternating-diffusionn Appl. Comput. Harmon. Anal., 44(3):509-536, 2018. ISSN 1063-5203, 1063-5203,1096-6033X. 1096-6036. doi: 10.1016/j.acha.2211
15 Jun 2019, URL http:::/ppoceeeeeeeeeee press/ http//99//hofffe html.
mml..
Hofer, C., Graf, F., Niethammer, M., and Kwitt, R. Topolog- ically densified distributions. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Leurning Research, pp. 4304-4313, PMLR, 13- 18 Jul 2020a. URL https: httpp//roceeeiggs..oomm/// mml.. press/vill http://ofeeaaaaaee/e html.
002. URL https: http//oooooooooooooooooooooooooo 1016/1 aaca............a...... acch. 2015. 002.
Leygonie, J., Oudot, S., and Tillmann, U. A frame- work for differential calculus on persistence bar- codes. Found. Comput. Math., 22(4):1069-1131, 2022. ISSN 1615-3375.1615-3388 10208-021-09955 y. URL https: http:://ooo..oooo. 1000/s10200 021 09522-y.
doi: 10.1007/
Hofer, C., Graf, F., Rieck, B., Niethammer, M., and Kwitt, R. Graph filtration learning. In III, H. D. and Singh, A.
(eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4314-4325 PMLR, 13- 18 Jul 2020b. URL hwtps:ttt//otc...t. /ttpss////occeeedeeeeem mlr. press/vil www111/hhofrr0000 html.
Leygonie, J., Carrière, M.. Lacombe, T. and Oudot, S. A gradient sampling algorithm for stratified maps with applications to topological data analysis. Math. Program., 202(1-2):199- 2023. ISSN 0025-5610, 0e211,144364-0 1436-4666. doi: 10.1007/510107--03--019333 doi
URL https:/
Horn, M., Brouwer, D., Moor, M., Moreau, Y., Rieck, B., and Borgwardt, K. Topological graph neural networks. In International Conference on Learning Representations, 2022. URL https: http::///peeeeeeeeeeeeme httpr/iwwwweeeettrreeeeee id=oxxUMeFWEHH
Maggs, K., Hacker, C., and Rieck, B. Simplicial repre- sentation learning with neural k-forms. In The Twelfth International Conference on Learning Representations, 2024. URL https: wpw.reveeeeeeeeeeeeeeeeeeerrr..e net/ /oormm? id-DjwOXhjHZb.
Huguet, G., Tong, A., Rieck, B., Huang, J., Kuchroo, M., Him, M., Wolf, G., and Krishnaswamy, S. Time- inhomogeneous diffusion geometry and topology. SIAM Journal on Mathematics of Data Science, 5(2):346-372, 2023.
McInnes, L., Healy, J., Astels, S., et al. hdbscan: Hierar- chical density based clustering. J. Open Source Softw., (11):205, 2017.
McInnes, L., Healy, J., and Melville, J. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv: 1802.03466 2018.
Hunter, J. D. Matplotlib: A 2d graphics environment. Com- puting in Science & Engineering. 9(3):90-95, 2007. doi: 10.1009//SE22007.00
Mischaikow, K. and Nanda, V. Morse theory for fil- trations and efficient computation of persistent ho- mology. Discrete Comput. Geom, 50(2):330-333, 2013. ISSN 0179-5376, 1432..4444,, s00454-013-9529.66 URL https: /top:::/doiii /tw.///iii.oo org/0..
Jost, J. and Li-Jost, x. Calculus of variations, volume 64 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1998. ISBN 0-521-64203- 5.
doi: 10.1007/
Kim, J.. Shin, J., Chazal, F., Rinaldo, A., and Wasserman, L. Homotopy reconstruction via the Cech complex and the Vietoris-Rips complex. In 36th International Sympo- sium on Computational Geometry, volume 164 of LIPles. Leibniz Int. Proc. Inform., pp. Art. No. 54, 19. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020. ISBN 978-3 959-979977-..
Molchanov, I. Theory of random sets, volume 87 of Proba- bility Theory and Stochastic Modelling. Springer-Verlag. London, second edition, 2017. ISBN 978 4471--7777777 978- 778-1-4471-734944
Monocle3. tories.
Monocle3: Constructing single-cell trajec- gib.b..
12

---

Cover Learning for Large-Scale Topology Representation
io/ htt//ooocleee/dccssooeeooo http:///ee//ddeee/areeeerereeeee Accessed: 2025-01-29.
Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: cc / f hccp:pppee_filleeppppe/////////1 neurips. Tebcc228feeeTf22222taa3333/f pdf.
Moor, M., Horn, M., Rieck, B., and Borgwardt, K. Topologi- cal autoencoders. In International conference on machine learning, pp. 7045-7054. PMLR, 2020.
Paper..
Nanda, Perseus: the persistent homology soft- ware. https: http:://ppoplii camppe..mathe.. maths. ox. ac uk/ nanda/perseus/ 2012.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cour- napeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn Machine learning in Python. Journal of Machine Learning Research, 12:2825-22 2830,, 2011.
Nicolau, M., Levine, A. J., and Carlsson, G. Topology based data analysis identifies subgroup of breast cancers with a unique mutational profile and excellent survival. Proceedings of the National Academy of Sciences, 108 (17):7265-7270, 2011.
Perrone, G., Unpingco, J., and Lu, H.-m. Network visualizations with pyvis and visjs. arXiv preprint arXi::2006.0495/ 2020.
Nigmetov, A. and Morozov, D. Topological optimiza- tion with big steps. Discrete Comput. Geom., 72(1):
310-344, 2024. ISSN 0179-5376.1432-0444 10. 10.100776000444-02--006133 URL https::/t/// //doi. ptg/10.1007/s0045:2 00613-0.
doi:
Poulenard, A., Skraba, P., and Ovsjanikov, M. Topologi- cal function optimization for continuous shape matching. Computer Graphics Forum, 37(5):13 25, 2018
Oudot, S. Y. Persistence theory: from quiver representations to data analysis. Mathematical Surveys and Monographs, 209:218, 2015.
Reeb, G. Sur les points singuliers d'une forme de Pfaff complètement intégrable ou d' d'u fonction numérique. C. R. Acad. Sci. Paris, 222:847-849, 1946. ISSN 0001- 4036.
Oulhaj, Z. Mapper filter optimization. https: htttps://itthbb: com/ ZiyadOulhajii Htw.iaajj/aaPPe /appperr-rr- Opt imizziio, 2024.
Rizvi, A. H., Camara, P. G., Kandror, E. K., Roberts, T. J., Schieren, I., Maniatis, T., and Rabadan, R. Single-cell topological rna-seq analysis reveals insights into cellular differentiation and development. Nature biotechnology, 35(6):551-560, 2017.
Oulhaj, Z., Carrière, M., and Michel, B. Differentiable mapper for topological optimization of data representa- tion. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A. Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Proceedings of the 41st International Conference on Ma- chine Learning, volume 235 Proceedings of Machine Learning Research, pp. 19919-38933 PMLR, 21-27 Jul 2024. httpttss: /taptt:::://rrreeeee http://pooceeigeeeeeee ngs mlr, mll.press/ v235 2235/oulhaj24a.hhe
Rolle, A. and Scoccola,
Stable and consistent density-based clustering via multiparameter persistence. Journal of Machine Learning Research, 25(258):1-
74, 2024. URL hattp://jmlz: http:///ww...orrpppppessse/eee// 21-1185 21-1185.htm1.
Packer, J. S., Zhu, Q., Huynh, C., Sivaramakrishnan, P., Preston, E., Dueck, H., Stefanik, D., Tan, K., Trapnell, C., Kim, et al. A lineage-resolved molecular atlas of elegans embryogenesis at single-cell resolution. Science, 365(6459))ccax 19711, 2019.
Ruscitti, K. D. and McInnes, L.. Improving mapper's robust- ness by varying resolution according to lens-space den- sity, 2024. URL httpt: org/ abs 2410. 03862.
Sale, N., Lucini, B., and Giansiracusa, J. Probing center vortices and deconfinement in SU(2) lattice gauge theory with persistent homology. Physical Review D, 107(3): 034501, 2023.
Pascucei, V., Scorzelli, G., Bremer, P.-T., and Mascarenhas, A. Robust on-line computation of reeb graphs: simplicity and speed. In ACM SIGGRAPH 2007 papers, pp. 58-es. 2007.
Scoccola, L. and Lim, U. Shapediscover: Learning cov- ers with geometric optimization. https://github. com
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Rai- son, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, Pytorch: An imperative style, high- reehrmmeffrm deep learning library. In Wallach, H.,
2025.
Scoccola, L., Gakhar, H., Bush, J., Schonsheck, N., Rask, T., Zhou, L., and Perea, J. A. Toroidal coordinates: decor- relating circular coordinates with lattice reduction. In
13

---

Cover Learning for Large-Scale Topology Representation
39th International Symposium on Computatioonl Ge- ometry, volume 258 of L.Ples. Leibniz Int. Proc. In- form. pp. Art. No. 57, 20. Schloss Dagstuhl. Leibniz- Zent. Inform., Wadern, 2023. ISBN 978-3-95977-273-
F, Mulbregt, P., and SeiPy 1.0 Contributors. SeiPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020. doi: 10. 10.1038/44152--011 019-0686-2.
0. doi: 20442000ipiees.oe2222...7... URL ht https: //tpi.orgg////// 4230 socg. 2023.5 57.
Wolf, F. A., Hamey, F. K., Plass, M., Solana, J., Dahlin, J. S., Göttgens. B., Rajewsky, N., Simon, L.,, and Theis, F. J. Paga: graph abstraction reconciles clustering with trajectory inference through a topology preserving map of single cells. Genome biology. 20:1-9, 2019.
Scoccola, L., Setlur, S., Loiseaux, D., Carrière, M., and Oudot, S. Differentiability and optimization of multi- parameter persistent homology. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scar- lett, J., and Berkenkamp, (eds.), Proceedings of the 41st International Conference on Machine Learn- ing, volume 235 of Proceedings of Machine Learn- ing Research, pp. 43986-44011. PMLR, 21-27 Jul 2024. htt.lhtttssppprceeeeeeeee ppwppeedioggg..oco/ mlr. press// v235/scoccola24a html.
Zhao, Q. Ye, Z., Chen, C., and Wang. Y. Persis- tence enhanced graph neural network. In Chiappa, S. and Calandra, R. (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 2896-2906. PMLR, 26-28 Aug 2020. URL https: /ttp//peeeeeggs../// mlr press/ v1 01 zhwo20d. html.
Sheehy, D. R. Linear-size approximations to the Vietoris- Rips filtration. Discrete & Computational Geometry, 49 (4):778-796, 2013.
Singh, G., Memoli, F., and Carlsson, G. Topological Meth- ods for the Analysis of High Dimensional Data Sets and 3D Object Recognition In Botsch, M., Pajarola, R., Chen, B., and Zwicker, M. (eds.), Eurographics Symposium on Point-Ban Based Graphics. The Eurograph- ics Association, 2007. ISBN 978-3-905673-51-7. doi: 1102312/SPBCISP9GG770911-11
The GUDHI Project. GUDHI User and Reference Manual. GUDHI Editorial Board, 2015. URL http: /udhi.
gforge. wiw.ii..ii..m ftt.iaaff///oc/aassss...
Tralie, C., Saul, N., and Bar-On, R. Ripser.py: A lean persistent homology library for python. The Journal of Open Source Software, 3(29):925, Sep 2018. doi: 10.21105/joss.000 00925. URL httpttt://dd...rr////// 21 21105/joss 00925.
Van der Maaten, L. and Hinton, G. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
van Veen, J., Saul, N., Eargle, D., and Mangham, S. W. Kepler mapper: A flexible python implementation of the mapper algorithm. Journal of Open Source Soft- ware, 4(42):1315, 2019. doi: 10.21105/joss.013311 URL https: / /doi http//di..ggg///////// 21105, 05/ joss. 01315.
Virtanen, P.. Gommers, R., Oliphant, T. E.., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., der Walt, S. J., Brett, M., Wilson, J., Millman, K. J., Mayorov, N., Nelson, A. R. J., Jones, E., Kern, R., Larson, E., Carey, C. J., Polat, i., Feng. Y., Moore, E. W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, L., Quintero, E. A., Harris, C. R. Archibald, M., Ribeiro, A. H., Pedregosa,
14

---

Cover Learning for Large-Scale Topology Representation
A. Background
A.I. Simplicial complexes and nerve
A finite simplicial complex consists a finite set Kg of vertices, together with a set K of subsets of Ko with the property that {x} E K for every z E Ko, and such that, for all a S T K, we have a E K. The elements of K are called simplices, the dimension of simplex a K is Jo| - 1 E N, and the dimension of a simplicial complex the maximum dimension of its simplices. For example, any finite, unoriented, simple graph G can equivalently be seen as 1-dimensional simplicial complex with O-dimensional simplices the vertices of G, with 1-dimensional simplices the edges of G, and with no higher- dimeessoiia simplices.
Definition A.1. Let = {Ui)er be a cover of a set X. The nerve of U, denoted Ner(2f), is the following simplicial complex on X. The underlying set of Ner(U) is and the simplices of Ner(()) are sets such that NsEo U3 A 0. The function Ner(2 + Parts(X) maps E I to U..
A.2. Homology, homology-good covers, and nerve theorem
Homology. It is beyond the scope of this paper give formal definition of singular homology of topological spaces; instead, we recall the basic ideas here, and refer the reader to (Hatcher, 2002; Fomenko, 1994) for introductions to homology with extensive visual examples from the point of view of mathematics, to (Edelsbrunner & Harer, 2022; Oudot, 2015; Boissomnat et al., 2018; Ghrist, 2008) for introductions to homology from the point of view of applied topology, and to (Hensel et al., 2021; Coskunuzer & Akçora, 2024) for surveys of applications of topology to machine learning.
We fix a field, which we omit from notation. The homology construction takes as input a topological space X, and returns a vector space (X) for each E N, in such way that dim(H,(X)) counts the number of i-dimensional holes in X; for example, Ho (X) counts connected components, while H1 (X) counts essential loops. When referring all homology groups at once, we write H(X).
As is standard, the homology H(K) of simplicial complex K' is taken to be either the homology of its geometric realization or equivalently its simplicial homology.
Homology is functorial, which in particular means that every continuous map between topological spaces X + induces a linear morphism (X) > (Y) of homology vector spaces.
Reduced homology. The ith reduced homology of a topological space X is the kernel of the linear map H(X) - H(*), where X is the only map from X to the one-point topological space. Definition A.2. An open cover Ut {Ut of a topological is homology-good we have H (N for every I.
Nerve theorem. The nerve theorem has many incarnations; see, e.g., (Bauer et al., 2023) for an overview of these. The version we use is the following:
Theorem A.3 (Nerve theorem). Letll= = (Uiher be an open cover of a topological space X. IfU is homology-good then H(X) = H (N))(
The above result standard, and it follows, for example, from the refined version of the nerve theorem (Theorem A.5, below).
Homology recovery up to dimension L. In many applications of algebraic topology, only homology up to a certain dimension is relevant. For example, if one is interested in the connected components of topological space, as is the case in clustering, only Ho is required. A general version of the nerve theorem, Theorem A.5 below, gives condition for recovery of homology only up to a certain dimension. We now abstract these conditions.
Definition A.4. Lettl (Ui)er be an open cover of topological space X, and let E N. The l is f-homology-good
if Hm (NEEJ U,) = 0 for every J S I with |J| < l + and 0 S m < f - |J|-1.
We can now state the refined nerve theorem (for proof, see, e.g., (Gillespie, 2022)). Theorem A.5. Let U be an open cover of topological space X, and let k E N. If U is hamoology-good then (x(X) a H; (Ner(U)) for every S i E k.
15

---

Cover Learning for Large-Scale Topology Representation
A.3. Topological persistence For references, see (Edelsbrunner & Harer, 2022; Oudot, 2015; Boissonnat et al., 2018; Ghrist, 2008).
A.3.1. FILTERED SIMPLICIAL COMPLEXES
Definition A.6. A filtered simplicial complex (K, consists of a simplicial complex K together with a function f : K + R from the simplices of K to the real numbers, with the property that if a S T are simplices of K, then f(o) S f(r).
filtered simplicial complex f) can equivalently be described as sequence [Kr)reR of simplicial complexes with the property that K2 C K, whenever S To see this, we define K, for E K f(o) S r] S K.
A.3.2. OTHER INDEXING POSETS
We remark that geometric complexes used in topological inference, such as the Vietoris-Riie complex (Appendix A.4) are often indexed by the non-negative real numbers. Another indexing poset of interest is ([0, 1|, which indexes the filtered simplicial complexes associated to fuzzy covers; see Appendix D.
A.3.3. THE BARCODE
Applying homology in dimension to a filtered simplicial (K, f) complex one gets family of vector spaces (H, (EER. and, by the functorial property of homology, we get linear maps H;(K,,) (K,)) whenever E IR. This collection of vector spaces together with linear maps, often denoted as H,(K, f). is known as persistence module, and fundamental result in persistence theory says that this persistence module can be described completely by a multiset of intervals in the
real line, known as the barcode of the filtered simplicial complex, and often denoted f) = {{ae. be) S hiee see, e.g., (Ghrist, 2008).
The same considerations hold if one applies reduced homology instead of homology, in the sense that there exists a reduced barcode B, (K, f). in the form of multiset of intervals of IR which completely describes the persistence module obtained by applying reduced homology to filtered simplicial complex (K,
A.3.4. THE LENGTH OF THE BARCODE
If the ith dimensional barcode (K f) of a filtered simplicial complex (K, f) is given by a multiset of intervals {las, be) S REEL, then its length (or total persistence) is given by the sum of the length of the intervals |B, K, f) = EtEz(be az).
When the simplicial complex filtered by a bounded function, say / K + [0, 1]. then the length is a finite number (B,, f)l e R. Remarkably, the length of the barcode can be differentiated with respect to the filter function f (Carrière et al., 2021), and this can be done efficiently using the methods in (Nigmetov & Morozov, 2024; Carrière et al., 2024).
It is a basic observation that the length of the barcode can be computed by integrating the dimension of the homology, that is: (K, f) = f dim H, (K,, dr. As one might expect, if one integrates the dimension of the reduced homology, then one obtains the length of the reduced barcode.
A.4. Topological inference and sparsification
Topological inference in a central topic in TDA; as its name suggests. the basic goal is to infer, from finite samples, topological properties (such as number of connected components or essential loops) of an underlying topological space. We refer the reader to books such as (Edelsbrunner & Harer, 2022; Boissonnat et al., 2018; Oudot, 2015) for an introduction. Arguably the most common construction for topological inference is the Vietoris-Rips complex, a particular kind of geometric complex that assigns, any finite metric space X (such as a point cloud) a filtered simplicial complex (i.e., nested sequence of simplicial complexes, see Definition A.6) (VR=(X)) T
with vertices the elements of X, and a simplex on vertices Ii at scale 8 if (I;, m,)== < for every i,j E (I,...,k).
The number of simplices in the Vietoris-Rip complex grows extremely fast with the size of X, as it contains (([X]4+1) d-dimensional simplices. For this reason, several sparsification techniques are commonly used, in particular: constructing the complex on a subsample of the data, reducing the complex using discrete Morse theory (Mischaikow & Nanda, 2013)
and edge collapses (Boissonnat & Pritam, 2020), and approximations (Sheehy, 2013).
16

---

Cover Learning for Large-Scale Topology Representation
A.5. Topological persistence optimization
There is extensive literature on the optimization of losses based on topology (Carrière al., 2021; Leygonie al., 2023; 2022; Hensel et al., 2021). with applications such as classification (Hofer al., 2017; Poulenard al., 2018; Hofer et al., 2020b; Horn al., 2022; Zhao et al., 2020) representation learning (Hofer et al., 2019). and regularization (Chen et al., 2019; Hofer et al., 2020a; Scoccola et al., 2024; Moor et al., 2020). Of particular importance to this paper is the idea of topological optimization with big steps introduced in (Nigmetov & Morozov, 2024), which addresses the sparsity of gradient in vanilla topological persistence optimization, making gradient descent convergence significantly faster than previous approaches (for another, recent approach see (Carrière et al., 2024)). For more details, see Appendix A.3.
B. Details about theory
B.1. Computation of the loss function
Lemma B.1. Let f -M- - [0, 1] be a smooth function on a d-dimensional Riemannian manifold M. Then,
[ H (B) da
=1lflh-
Proof. We simply compute
S( H.l (L {1) dd
S / 1(52)) dr yp
[xElO.I/DEM FEM
= -I -JEM / (xE|o.1) (()>)) dd dr
J f(x) dz IIfll..
JEEM
where in the second equality we used Fubini's theorem.
Lemma B.2. Let: f : + IR be smooth function on Riemannian manifold. If f does not vanish on {f = A}. then =
Proof. The left-to-right inclusion follows immediately from the fact that is continuous:
au OU-A--CAAN--NGUAAAMN
For the right-to-left inclusion, it suffices to prove that = Xf AJ. So, given {f A} must show that every open neighborhood U of x intersects {f > Λ). Towards contradiction, assume that there exists an open neighborhood U of x entirely contained in { < A}. Then x is a maximum of restricted to U, and thus V vanishes on x, a contradiction.
Lemma B.3. f M - R is a smooth function on a Riemannian manifold, then
S H 1 (0(5> dd ||//
Proof. We claim that ( A) 1 for almost every À E R; the statement of the lemma follows from this claim and the coarea formula, which in this case says that fo - = xJ)dx> = || (see, e.g., Appendix of (Jost Li-Jost, 1998), for proof of the coarea formula). So us prove the claim. By Saard's 's theorem, the of critical values of f has measure zero. This implies that V does not vanish on almost every level set {f A}. which implies our claim, thanks to Lemma B.2.
Proof of Theorem 3.2. Let yp be function which takes as input cover and outputs real number. Then, if random cover W4 is distributed according to the probability measure Ag. we have that ((((()) = fo p([g > X}) dA. This is simply because Hy is the pushforward of the uniform measure on [0, along the function À +> {g > A}.
17

---

Cover Learning for Large-Scale Topology Representation
Then, the first equality follows from Lemma B.I, while the second follows from Lemma B.3.
For the inequality, note that P (14 is not homology- -ooogyyy-oooo-oooo E(brr), where du is 0 is U is good, and otherwise. By the considerations in the first paragraph, it follows that
P. (l4 is not homology-good, = L. P(a2Aa) Yd
2
s L Σ dim H
n {gj > t}
jEJ
> 2)) Yp
dim
H
[JJ] 9j
>
JCI
Σ JCI
min
9j
JEJ
where in the inequality simply used the fact that if cover is not homology-good then the dimension of the reduced homology of one of the intersections must be at least 1, by definition. Moreover, cover is not homology-good if and only if the homology of one of the intersections is least (also by definition), so the probability of U not being good is zero if and only if the upper bound zero.
B.2. Relaxation of the topological loss
Let .M- - p be fuzzy cover, and let 4 = {U)) be random cover distributed as Pgg, as in Optimization Problem 1. Let = [1,...,k} Fix a maximum homology dimension & E of interest. Then, the topological loss T(g) = P ({U+} is not homology-good ) can be relaxed to a loss Te(g) = P ([U+} is not é-homology-good) ), using
Definition A.4. A derivation analogous to that in the proof of Theorem 3.2 shows that
2-111-1 Σ
Te(9) S
Σ
min JEJ
JCI
m==
H...
which, in the case where g: K + pk-1 is a fuzzy cover of simplicial complex, leads us to define the following estimator
é -1-1
i((0)= = Σ
min Jj
JCI
mmm
JEJ
Hm
In particular, we have
to(9) = Σ 119.1110.
E
which only depends on the 1-skeleton of the simplicial complex, and thus makes sense for graphs.
B.3. The probability measure associated to a fuzzy cover
If X is a finite set, the space of k-element covers of X is discrete and can be endowed with the discrete o-algebra. g: > r*-1 a fuzzy cover, then the map sending À E [o, 1] to the cover {g > >} is measurable since X only admits finitely many k-element covers, and for any k-element cover 14 of X, the set fr E [o, 1] {g > r} = U}} is empty or half-open interval. If X is compact metric space (e.g., compact, connected Riemannian manifold), then its set of subsets can be endowed with the Hausdorff metric, which then gives o-algebra structure to the set of subsets, and thus to the set of k-element covers.
There is a more general theory of random sets, which deals with this type of situation; see, e.g., (Molchanov, 2017) or Chapter 18 (Aliprantis & Border, 2006). Here, we shall not go into details, since the functionals of the random covers we are interested in can be expressed as explicit integrals which do not involve random sets; see Theorem 3.2.
18

---

Cover Learning for Large-Scale Topology Representation
C. Computational complexity
The bulk of ShapeDiscover's computation time is spent on optimization, that is, on executing the Gradient method in Algorithm 3, so let us analyze its computational complexity.
Let X be the input point cloud. The neighborhood graph G built on X has size |G] = O(n_neigh |X]) From the loss estimation formulas (Section )), we see that M, G, and R can be computed ( |Gl) time. bit more interestingly, the loss To. which involves the zero-dimensional persistence of a filtered graph, can be computed in (( |G] log (Gl) time, by sorting edges and using the elder rule (Edelsbrunner & Harer, 2010); see, e.g., Section 5.3.3 in (Rolle Scoccola, 2024). The overall time complexity is thus:
O n_eeochh n_cov nh |X] log [X]
The space complexity depends on maintaining the neighborhood graph G and the parameters of the model implementing the fuzzy cover. In the case of the model simply being an |X|-by-n cov real matrix, as in Section 5, the space complexity is O (In_co++ + n.neigh) [X]).
D. The filtered simplicial complex associated to fuzzy cover
Let X be a set, let g X + p C [0, 1]& be fuzzy cover, and let I = [l,...,k).
For each E (0, 1] we define the simplicial complex (erx = Ner({g > 사}), using the nerve construction, recalled in Section 1.
Note that, if X, then the cover {g > X) refines the cover (g }}. which means that there is an inclusion of simplicial
complexes Nerx (g) S Nerx(g) (g). In particular, (e) is simplicial complex filtered by ((0, 1], 2), where the order on (0, 1] is the opposite of the standard one, since, as stated below, if A < X, then the cover {g > X² refines the cover {g > A).
Standard rescaling. In order to put this filtered complex in the same footing as geometric complexes, which are usually indexed by the non-negative real numbers [0, x)), we apply the following standard rescaling. Consider the isomorphism of posets
00),00) 5) - (0.1), 2) - exp(-ppp -r),
with inverse given by A log(A).
Then, given a fuzzy cover g X + p we obtain filtered complex indexed by the non-negative real numbers by considering (Ner
E. Cover learning as a coarse-graining method
Cover learning can be interpreted coarse-graining method, in the sense that it provides a coarse representation of geometric data. This connects our work with methods other than those in Section 2, and here comment this.
In (Brugnone et al., 2019) and (Huguet et al., 2023), coarsening is done by simplifying the global structure of the point cloud; for instance, by emphasizing cluster structure. The main difference with cover learning is that cover learning produces a graph (or simplicial complex) which encodes the global structure the point cloud, and which does not have the data points as vertices (but rather groups of data points).
(Pascucci al., 2007) uses technique based on the Reeb graph, which is also the main motivation for Mapper, but unlike Mapper it operates simplicial complex (or mesh). The main difference with general cover learning is that, since they approximate a Reeb graph, they produce one-dimensional simplicial complex, and thus, like Mapper (and as explained in Section 2 and Appendix F) it cannot be used to do higher dimensional topological inference.
In (Wolf et al., 2019), the authors present an and-to-end method for single-cell RNA-seq: the relevant part of their method is described in their section "Graph partitioning and abstraction" (pp. 7), where they explain how they coarsen an initial knn graph smaller graph; this is done by computing a clustering of the original graph, and then adding edges between
19

---

Cover Learning for Large-Scale Topology Representation
clusters using a measure of connectivity between different clusters. For visualization purposes, their output serves very similar purposes ours (e.g., Figure 5). Since it is not goal of theirs, their method is not suitable for higher dimensional topological inference.
F. Unsuitability of ID Mapper for higher-dimennional topological inference
We give two explanations for this:
The initial cover {4,}/=1 of used by ID Mapper typically does not have triple-iterssections (only pairwise intersecting intervals are used). Hence, the pullback cover (f- does also not have riple-intersections The cover used by ID Mapper is refinement of { (T))(E)) and a refinement of have triple-intersections. However, the refinement is given by partitioning each cover element f=) into disjoint subsets (since it is clustering), which guarantees that the cover used by ID Mapper does not have triple-intersections, which in turn implies, by definition, that the nerve does not have k-dimensional simplices for any k 2 2.
with no triple-intersections could in principle
There exist consistency results for 1D Mapper, which imply that, under suitable assumption, the nerve of the 1D Mapper cover converges to the Reeb graph (Reeb, 1946) of an underlying manifold M with respect to a function : M - IR see, e.g.. Thm. 7 (Carrière et al., 2018). A Reeb graph a graph, and hence does not contain higher dimensional information.
What this means that the nerve of the ID Mapper cover, by design, only contains 0- and I-dimensional information, that is, it can detect cluster structure and loops data, but cannot be used to, e.g., estimate higher-dimensional homology.
G. Witness complex and Ball Mapper
Let X be finite metric space, and let Y C X be a subset. The witness complex with parameter e = 0, introduced in (De Silva & Carlsson, 2004), is filtered simplicial complex (Woo ()) with vertices the elements of Y, and a simplex on vertices ,.,..., yk at scale if there exists x E X such that (J6, x) S for every i E fi.....kk).
Proposition G.1. Let X be finite metric space, let 2 O, and let Y C X be s-net of X. Then the nerve of the Ball Mapper cover constructed using the s-net Y is equal to W (Y)
Proof. The two simplicial complexes have the same set of vertices. By definition, there is a simplex in WY, (Y) on vertices y1,...,, 1/ E Y if and only if there exists x E X such that dx (yi, x) S & for every E {l,..., k), which is equivalent to n (y,, =) * 0, and this is equivalent to there being simplex on the same vertices in the nerve of the Ball Mapper cover.
Thus, the filtration output by the multiscale Ball Mapper algorithm of (Dlotko, 2019a) consists of a finite set of filtration values of the Witness complex with parameter 0.
H. More on loss estimation
H.I. Loss normalization
Let W E(enee w(x,y) y) be the total edge weight, and define
7M =
1o |X
1
G6
W2
1
1/
ko |X|
k- W
20

---

Cover Learning for Large-Scale Topology Representation
H.2. Regularization bounds geometry loss
In our experiments, the geometry loss G usually plays little role, in the sense that results are very similar with without it. We believe that this is because the regularization R is sufficient to ensure geometric regularity; here we give weak evidence of this, by showing that G I R.
Let X finite set, let G be weighted graph with X vertex set, let be the set of edges G, and let W ='EE w(e)
be the total edge weight. If F + I. then
2 1
1 W
Σ w(cc F(e)
w((e)- -(e)², ((e)),
(2)
CE
by Jensen's inequality.
If X + - is fuzzy cover, letting F(x, y) 19)(x) ge(v) and summing over 1 S < gives ((g) s R(g). by Equation (2).
I. More on implementation and examples
L1. Software
I.1.1 IMPLEMENTATION
Our implementation ShapeDiscover (Scoccola Lim, 2025) is in PyTorch (Paszke al., 2019), and we rely on Numpy (Harris et al.. 2020), Scipy (Virtanen et al., 2020), Numba (Lam et al., 2015), Scikit-learn (Pedregosa al., 2011) and Gudhi (The GUDHI Project, 2015).
Visualizations are done with Matplotlib (Hunter, 2007), Networkx (Hagberg al., 2008), and Pyvis (Perrone et al., 2020).
1.1.2. EXPERIMENTS
We compute Vietoris-Rips filtrations using the Python frontend (Tralie et al., 2018) for Ripser (Bauer, 2021). For edge collapse and sparse Vietoris-Rip we use the implementations in (The GUDHI Project, 2015), and for discrete Morse theory on filtered complexes we use Perseus (Nanda, 2012). We use the KeplerMapper implementation of the Mapper algorithm (van Veen al., 2019).
All experiments were run MacBook Pro with Apple MI Pro processor and 8GB of RAM.
1.2. Datasets
Synthetic data. These consist of 2000 point uniform samples of the unit 2- and 3-spheres. For the topological inference example, the Betti numbers to be recovered are (1, 0, 1), and {1, 0, 0, 1), respectively.
Human in 3D. This consists of a 9508 point sample the surface of a human figure in three dimensions (see Figure 7), Topologically, it is thus equivalent to 2-sphere, and in the topological inference example the Betti numbers be recovered are 1..
Video dynamical system. The dataset is from (Lederman & Talmon, 2018), and consists of video of two figurines rotating at different speeds. When interpreting it as a dynamical system, the state space consists of two independent circular coordinates, and thus a topological 2-torus; this confirmed in (Scoccola et al., 2023) using persistent homology. use the same preprocessing as (Scoccola et al., 2023), which results in a point cloud with 2022 points in 10 dimensions. For the topological inference example, the Betti numbers to be recovered are {1, 13.
Population activity in grid cells data. The dataset is from (Gardner et al., 2022), and we follow their preprocessing steps to obtain a point cloud with 10000 points in 6 dimensions. As is confirmed in (Gardner et al., 2022) using UMAP and persistent homology, the point cloud concentrated on a topological 2-torus, so the Betti numbers to be recovered are (1,25 (1,2,17 1).
21

---

Cover Learning for Large-Scale Topology Representation
Table 3. Correspondence between labels in Figures and 16 and the cell types of (Packer et al., 2019).
10
11
13
14
tye
ADF
ADL
ADB
AFD
ASB
ASER
ASE.pu
ASG
ASH
ASI
A5J
ASK
ADA
AWA
AWB
ANC
other
Octopus in 3D. This consists of 7812 point sample of the surface of an octopus figure three dimensions (see Figure 7).
Small handwritten digits datset. This is the dataset of (Alpaydin & Kaynak, 1998), consisting of 5620 handwritten digits encoded as vectors in 64 dimensions.
MNIST. This is the classical dataset of (Deng, 2012). We use the training data, which consists of 60000 handwritten digits encoded as vectors in 784 dimensions.
C. elegans data. This the dataset of (Packer et al., 2019), which we preprocess using Monocle as in (Monocle3). This results in point cloud with 6188 points 50 dimensions. There are 28 cell types. To help visualization, we keep 16 cell types (those whose flare structure is clearly identified by UMAP's 2D projection; see Figure 16), which we label from to 16, and label the rest of the cell types by O; see Table 3.
Other comments. In the topological inference experiments, scale datasets that the sparsification parameter for sparse Vietoris-Rips can be fixed.
I.3. Details efficient topological representation experiment
We compare ShapeDDiscover the following approaches topological inference:
(S + Rips) Furthest point subsample + Vietoris-Rips.
(S+ + Rips) Furthest point subsample + Vietoris-Rips discrete Morse theory on filtrations (Mischaikow & Nanda, 2013).
(S + Rips edg.coll.) Furthest point subsample Vietoris-Rips edge collapse (Boissonnat & Pritam, 2020).
(S + sparse Rips) Furthest point subsample sparse Vietoris-Rips (Sheehy, 2013).
(S+ + Alpha) Furthest point subsample Alpha complex (Boissonnat et al., 2018).
(Witness) Witness complex (De Silva & Carlsson, 2004). Recall from Appendix G that, when = 0, the Witness complex is essentially equivalent to multiscale Ball Mapper (Dlotko, 2019a) (MS BMapper).
Furthest point subsampling refers the strategy for building a subsample of a point cloud (or finite metric space) given by choosing initial point and iteratively choosing the point that maximizes the (minimum) distance to the points already chosen.
OOM means out of memory. The implementation of discrete Morse theory on Vietoris- complexes we use (Nanda, 2012) runs out of memory on larger datasets; this implementation also does not report number of vertices of the final simplicial complex, hence the """ the table. Alpha complexes do not scale well with ambient dimension, which is reflected the fact that runs out of memory in the dynamical system dataset, which has ambient dimension 10.
L.4. Homology recovery quotient
This is a simplified version of the quotient used to quantify topological recovery (De Silva & Carlsson, 2004). Given a filtered simplicial complex K [Kr), we endpoint of bars in the barcode of IK. Then, given target Betti numbers {Bu...., BB,). the homology recovery quotient of IK defined
(resp. TR) the smallest (resp. largest), finite, left (resp. right)
Hr R dim H, H,,,) Br, 44 < i n]
where in the numerator we are taking the Lebesgue measure.
22

---

Cover Learning for Large-Scale Topology Representation
I.5. Why not use Mapper in the topological inference experiment
As explained in Section and Appendix ID Mapper does not contain higher-dimensional information. Higher-dimensional extensions of Mapper exist, but the parameters difficult to tune, and require higher- digher-dimensional filter functions. Mapper is also static, that is, it produces single simplicial complex. In order to produce sequence of simplicial complexes, and thus barcode that can be compared with standard approaches to topological inference, one would need to use multiscale Mapper. But to the best of our knowledge there is no implementation of a multiscale, higher-dimensionall Mapper. We expect the parameters of such a procedure to be very hard to tune; this could be alleviated by using the framework of (Oulhaj et al., 2024), to produce a differentiable, multiscale, higher-dimensional Mapper.
L6. Details on toroidal topology in neuroscience experiment
Result. We run ShapeDiscover on the data of (Gardner et al., 2022) (see Appendix 1.2 for details), with n_cox = 15; resulting in a filtered complex with 15 vertices. The barcode thus obtained in Figure 6, and the homology recovery quotient is 0.2, which is remarkable given that we only used cover with 15 elements.
Comparison to Vietoris-Rips. We also run furthest point subsaple + Vietoris-Rips on the dataset. our experience, not possible uncover the toroidal topology by directly using Vietoris-Rips: we subsampled 5000 points and computed the Vietoris-Rips barcode, which resulted in homology recovery quotient of 0, that is, in filtration which no point has toroidal topology. This agrees with the methodology of (Gardner et al., 2022), where the toroidal topology was uncovered with persistent homology only after non-linear dimensionality reduction step using UMAP.
Comparison to other torvidal topology dataset. In our other experiment toroidal dataset (the dynamical system data of Section 5. ShapeDiscover required a cover with 52 elements to clearly recover the torus. We believe this is because, in that dataset, the aspect ratio of the torus is highly skewed, since one of the figurines is significantly larger than the other one (see Fig 2 (Lederman & Talmon, 2018)), which implies that, in the state space of the dynamical system, one of the two circular coordinates is metrically larger than the other one.
1.7. Plotting the nerve of a cover
We plot the nerve of a cover {Ui)ee with the following conventions:
The size of vertex corresponding to U, is proportional to log( [U] 1).
The thickness of an edge corresponding to U₁ n U, is proportional to log([U, 0 U5| + +1).
The length of an edge corresponding to Uy is proportional to 1/}U,
When the data has labels, the vertex corresponding to U; is plotted as a pie chart, which shows the proportion of elements of each class in U, (note that labels are not used to produce the cover). This is a standard practice in for Mapper graphs, see, e.g., (Chalapathi al., 2021; Zhao et al., 2020).
I.8. Differentiable Mapper on visualization experiments
We experimented with the implementation of Differentiable Mapper (Oulhaj et al., 2024) provided in (Oulhaj. 2024) on the digits and C. elegans data, but we were unable to obtain meaningful results. As parametric family of filter functions, we used a linear projection, as used in (Oulhaj et al., 2024). Lack of success could be due to the difficulty of learning a filter function which properly reflects the structure of the datasets, and it remains a possibility that a more sophisticated parametric family of filter functions (as suggested in the conclusions of (Oulhaj et al., 2024)) with finer parameter tuning will lead good results.
I.9. Other analyses
See Table for an ablation study, Figure 18 for a parameter sensitivity analysis, and Figure 19 for noise sensitivity analysis.
23

---

Cover Learning for Large-Scale Topology Representation
2
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
Figure 6. The barcode of the tiltered simplicial complex obtained by running ShapeDiscover with with 15 elements the dataset of (Gardner et al., 2022). The toroidal topology is apparent between scales 1.25 and 2, and the homology recovery quotient 0.2. Compare with Fig 1 (Gardner al., 2022).
Figure 7. Human and octopus datasets projected to two dimensions. Figures taken from (Oulhaj et al., 2024).
K
0
Figure 8. Cover of the octopus data obtained with ShapeDiscore with default parameters and n_cov = 20.
24

---

Cover Learning for Large-Scale Topology Representation
K
Figure 9. Cover of the octopus data obtained with Mapper.
Figure 10. Differentiable Mapper on human and octopus data. Figures taken from (Oulhaj et al., 2024).
Figure I.. Ball Mapper human data with parameter (left-to-right): 0.25, 0.2, 0.15. The cover sizes 18, 26, 48. respectively. We see that the parameter depends significantly on the data, and is hard to tune. The underlying topology (that of 2-sphere) is also hard recover: none of the simplicial complexes have the underlying topology, which agrees with the findings Table (row "Witness (v = 0) / MS BMapper").
25

---

Cover Learning for Large-Scale Topology Representation
Figure 12. Ball Mapper on octopus data with parameter (left-to-right): 0.2, 0.175, 0.15. The cover sizes are 51, 68, 80, respectively. The same conclusions as in Figure 11 hold.
Figure Left. 2D projection the digits data obtained with UMAP. Right, Cover the digits data obtained with ShapeDiscover, plotted on the 2D projection of the data obtained with UMAP.
Figure 14. Ball Mapper on digits data with = 45, which results in cover of size 19. The (1-skeleton) of the nerve of the cover (left), and the cover plotted the 2D projection the data obtained with UMAP (left); see Figure 4, We that different digit are mostly mixed up, and there cover elements overlap with many others, presumably due to the curse of dimensionality.
26

---

Cover Learning for Large-Scale Topology Representation
A
Figure 15. Left. 2D projection of MNIST obtained with UMAP, Right. Cover of MNIST obtained with ShapeDiscover, plotted the 2D
projection of the data obtained with UMAP.
Figure 16, C. elegans data projected with UMAP. Labels are described in Table 3.
27

---

Cover Learning for Large-Scale Topology Representation
Figure 17. Ball Mapper on C. elegans data with = 70, which results in a cover of size 51. There is a large, independent, cover element tiny, independent
with contains most points. In order to break it apart, must make smaller, but this results in more and elements. The flare structure is not recovered.
Table Times (in seconds) taken to run ShapeDiscover on datasets the examples. Columns correspond to datasets together with the n_cov paramcter of Table 1. Rows correspond to ShapeDiscover's subroutines. We see that the bulk of the time is taken by the optimization step, and that the topology loss accounts for a large proportion of this.
Discoorsc subroutine 2-sph 5
3-sph 19
human 19
dynam 52
grid cell octopus 20
digits 15
MNIST C Cellgans 100
Preprocessing
0.05
0.04
0.13
0.05
0.17
0.12
0.05
4.37
0.27
Clustering
0.04
0.04
0.32
0.10
0.31
0.55
0.04
2.96
0.94
Optimization
1.74
4.33
3.95
2.38
4.31
2.56
2.13
206.04
77.24
Opt. w/o topology loss
1.05
1.55
1.18
0.66
1.51
0.82
0.61
50.03
19.83
Table Rows correspond to datasets together with the n_cov parameter Table Columns correspond to components of the pipeline that turned off. Entries the output homology recovery quotient. We observe that the measure and regularization losses essential, The initialization using clustering is also essential, at least for real datasets. The geometry loss has no substantial effect, at least for these datasets. The topology loss has effect, but only when the initialization random.
Dataset
full pipeline meas. loss geom. loss top. loss
reg. loss random init. random init. top, loss
2-sph 5
0.74
0
0.72
0.74
0
0.59(0.1)
0.1(0.03)
3-sph 19
0.51
0.52
0.51
0.16(0.03)
0.03(0.01)
human 19
0.7
0.71
0.69
0
dynam 52
0.38
0
0.41
0.38
0
0
28

---

Cover Learning for Large-Scale Topology Representation
1.99
0.721
8.333
3.10
01312
00:54
10-
1094
234
2333
15-
1435
137
1.22
0.98
EXT1
23-
10.0
0.50
1385
1.22
0.06
23-
2.400
20
neighh
neigh
(a) 2-sph
(b) 3-sph
0/23
6322
0.703
0006
0.25
HLCOOR
TV. PLO0WW!
2337
0.70
8735
0.70
0.40
64
0:53
30-
0.71
0.744
22-
4.4
1001
10
15
10g
10g
(c) 2-sph
(d) 3-sph
Figure 18. We run ShapeDiscover on the 2- and 3-sphere datasets, with parameters as in Table 1, except for the ones being displayed on the and compute homology recovery quotient (entries).
horoo ogg rerovery quotients
hooenology
2.4
noise level
noise lovel
(a) 2-sph
(b) 3-sph
Figure 19. We ShapeDiscover on the 2- and 3-sphere datasets, with parameters in Table and compute homology recovery quotient. Data is normalized to exactly fit in unit hypercube. Noise is additive, meaning that each coordinate of each data point is perturbed by a uniform random number in j0, 1]. We display mean and standard deviation 10 runs for each level of noise.
29


Reviews:
[{"review_id": "iobfEAKXKQ", "reviewer": "Reviewer_mPj7", "summary": "This paper focuses on learning a representation of the large-scale structure of geometric datasets, and specifically this is achieved by learning the cover of the geometric datasets. The performance of existing methods such as the 1D Mapper or Differentiable Mapper is sensitive to the choice to hyper parameters. To tackle this issue, the author proposed a non-convex optimization program with a new loss function that does not involve the filter function anymore. The new loss consists of three terms that try to ensure the resulting cover learned are satisfying from different aspects. Empirical results demonstrate the proposed method is able to output meaningful and competetive cover compared to SOTA.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback!\n\n- About most of the results being visualizations: Three out of five experiments concern visualizations.\nWe just want to emphasize the fact that the two other experiments concern topological inference, with experiment A being a quite thorough comparison with the main competitors based on sparse simplicial complexes.\n\n- About evidence on initialization being important:\nThis will be addressed in the ablation study and sensitivity analysis.\nPlease see \"Main comment A\", below.\n\n- About comparing initialization and output after optimization:\nThis will be addressed too.\nPlease see \"Main comment A\" below.\nPlease also see \"Main comment B\", below, about differences between the clustering used for initialization and our output cover.\n\n- About using different weights for the loss components:\nPlease see \"Main comment A\", below\n\n- About downstream tasks:\nPlease see \"Main comment C\", in the response to reviewer 5NTw.\n\n**Main comment A: Ablation study and sensitivity analysis**\n\nWe will add the requested ablation study and sensitivity analysis.\nWe now outline our preliminary findings, and please see below for a sample experiment supporting these.\nWe also emphasize that, in the paper, our default parameters work well in a wide range of datasets.\n- Initialization (random vs clustering).\nIn terms of quality of output, this does not play a big role for small datasets (eg 2-sphere), but it does for larger data (eg MNIST). In terms of convergence speed, clustering initialization always leads to faster convergence (order of x10 or more for large datasets).\n- Ablation.\n    - Measure loss and Regularization loss: These are required for obtaining reasonable results.\n    - Topological loss: When using random initialization, it is required. When using a good clustering as initialization, the topological loss does not play a big role, and good results can be obtained without it.\n    - Geometry loss:\n    In our experiments thus far, it does not play an important role.\n    We believe that regular geometry is already enforced by the regularization loss; this is explained in Appendix F.2.\n- Sensitivity to parameters.\n    - Number of cover elements: The algorithm is robust to this choice.\n    This parameter is just an upper bound, since the algorithm is allowed to return empty cover elements which are just discarded.\n    If one wants to force more cover elements to be non-empty, one can increase the weight of the measure loss (since measure loss enforces many small sets as opposed to few large ones).\n    - Regularization weight: The algorithm is robust to this choice.\n    A large value will enforce larger cover elements, which can be used to have larger intersections between cover elements, in case the output is too disconnected.\n    - Number of neighbors for nearest neighbor graph: The algorithm is robust to this choice, as is usually the case with this parameter in unsupervised learning algorithms.\n    - Threshold (lambda):\n    This parameter is only required for producing a single graph (or simplicial complex), for, eg visualization, and it is not fixed for topological inference.\n    The algorithm is sensitive to this parameter, and the number of edges (intersections between cover elements) can change significantly when going from lambda = 1 to lambda = 0.\n    The default 0.5 usually leads to good results, but sometimes there might be too many intersections for easy visualization; in that case the solution is to increase lambda (as in Fig. 4 and Fig. 5).\n\nSample experiment (the experiments in the paper will be more thorough): We run our method on the 2- and 3-sphere datasets and quantify topology recovery as in Table 1\n- Initialization and topology loss:\n    - Results can be reproduced with clustering initialization and without topology loss.\n    - With random initialization and no topology loss, topological recovery always fails.\n    - With random initialization and topology loss, recovery is successful most of the times (>80%).\n- Geometry loss: The results in Table 1 can be reproduced without the geometry loss.\n- Number of cover elements: Topology recovery is still successful for much larger values than the ones used in the Table (>30).\n- Regularization weight: Results are replicated with smaller and larger values (5, 10, 20).\n- Number of neighbors: Results are replicated with smaller and larger values (8, 15, 30).\n\n**Main comment B: About the clustering used at initialization**\n\nAlthough initialization plays an important role for large datasets, it does not, by itself, solve the cover learning problem: There are no intersections between the clusters in a clustering, so the nerve is discrete and contains no topological information (above dim 0), meaning that a clustering by itself wouldn't be useful for topological inference (experiments A and B) or visualization of interesting geometric structure (eg flare structure in Fig. 5).", "claims_and_evidence": "Yes. All the claims are supported by either empirical result or theoretical analysis.", "methods_and_evaluation_criteria": "I think the proposed method appears to be sound and effective, as supported by several experiments on different datasets.", "theoretical_claims": "I didn't check the correctness of the theoretical claims but they appear to have no issue.", "experimental_designs_or_analyses": "The current result looks to be sound. However, as most of the results are visualization of the output from different methods, there are several extra experiments (apologize if I missed something) that could be further investigated to enhance the soundness of the proposed algorithm:\n\n1. As the author stated that initialization is important, could we provide more evidence on this, e.g. what are the results with/without a good initialization, or with different clustering methods for initialization\n2. Similarly, can we have some plot that compares the embedding g at initialization and after the optimization? In experiments I feel there are some cases (e.g. MNIST) where spectral clustering is already able to provide a very meaningful result. \n3. As in table 4, looks like the topology loss contributes most to the runtime, could we have some comparison on the output with different weights on the loss function components, which can further help us understand the significance of these proposed components. \n4. Besides visualizing the output, is there anyway to perform some downstream tasks, e.g. clustering based on the optimized embedding (representation) to further showcase the strengths of the proposed methods.", "relation_to_broader_scientific_literature": "The key contribution of this paper is proposed a new topology representation learning method, which could benefit various downstream tasks such as clustering and synchronization.", "essential_references_not_discussed": "I don't aware there are any outstanding missing reference in the manuscript", "other_strengths_and_weaknesses": "Overall, I think this paper is well-written and easy to follow. The proposed method appears to be novel and sound. My main concern is on the experiments which has been elaborated in previous sections.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AbSyT1CzVw", "reviewer": "Reviewer_Wjc2", "summary": "The paper aims to generate topologically faithful simplicial complexes for geometric datasets by reducing the problem to cover learning. By formally defining a set of three goals for cover learning, extending to the space of fuzzy covers (“softening” the inclusion of an element in a subset, which allows them to be parametrized by functions over real numbers), and demonstrating a way to estimate these goals as standard loss functions, the authors develop a framework through which these goals can be optimized with standard neural networks. Based on this idea, they implement a cover learning algorithm, ShapeDiscover, which outperforms other models quantitatively by requiring less vertices and simplices to achieve the same homology recovery quotient on synthetic geometric datasets. This model also provides more intuitive topological representations than previous cover learning approaches.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback!\n\n- About missing references: We will include them in the paper and comment on similarities and differences.\nHere are the main ideas we took from the papers (please correct us if we have misinterpreted something):\n    - (Huguet et al. 2023)(Brugnone et al. 2019): Coarsening is done by simplifying the global structure of the point cloud (for example, by emphasizing cluster structure).\n    The main difference is that our method produces a graph (simplicial complex) which encodes the global structure of the point cloud, and which does not have the data points as vertices (but rather groups of points).\n    - (Pascussi et al. 2007): The technique is based on Reeb graph, which is also the main motivation for Mapper, but unlike Mapper it operates on a simplicial complex.\n    The main difference is that, since they approximate a Reeb graph, they produces a one-dimensional simplicial complex, and thus, like Mapper (and as explained in Sec. 2 and App. D) it cannot be used to do higher dimensional topological inference.\n    - (Wolf et al. 2019): This paper presents an end-to-end method for single-cell RNA-seq; the relevant part of their method is described in their section \"Graph partitioning and abstraction\" (pp. 7),\n    where they explain how they coarsen an initial knn graph to a smaller graph; this is done by computing a clustering of the original graph, and then adding edges between clusters using a measure of connectivity between different clusters.\n    For visualization purposes, their output serves very similar purposes as ours (eg our Fig. 5), and is thus very related.\n    Since it is not a goal of theirs, their method is not suitable for higher dimensional topological inference.\n    - (Moor et al. 2020): This is an autoencoder-based dimensionality reduction algorithm, with the novelty being the usage of a topological loss on top the classical reconstruction loss.\n    Two connections to our work:\n    One is producing a coarsened representation of the data; here the difference is that they output an embedding in low dimensional space, while we output a graph (simplicial complex) with groups of data points as vertices.\n    The second one is the usage of a persistence-based loss; the main difference with our usage is that we use it purely as regularization (we enforce trivial local topology, motivated by the nerve theorem), whereas they use it to directly enforce the topology of the low dimensional representation to be similar to that of the original data.\n    This work will also be mentioned in our section \"A.5. Topological persistence optimization\".\n\n- About our method being a coarse-graning/sketching method:\nThis is a good interpretation.\nWe want to emphasize the fact that our coarsening strategy serves two distinct purposes: topological inference (via homology) and visualization.\nIn particular, we compute homology directly on the coarse representation (small simplicial complex), as opposed to computing homology of a large initial graph that then is coarsened only for visualization.\nMoreover, our strategy builds on the nerve construction (standard in topology), which lends itself to further theoretical analysis (eg consistency of covering algorithms, addressed in future work).\n\n- About ablation study: This will be implemented.\nPlease see \"Main comments A and B\" in the response to reviewer mPj7 for what we will include, as well as preliminary findings.\n\n- About the number of cover elements parameter:\nThe parameter is fixed, and in our experiments we simply retrained the model for each choice each case.\nTwo comments:\nFirst, in practice, the chosen number is just an upper bound for the number of cover elements: gradient descent can converge to solutions in which some cover elements are empty; this a feature as it simplifies the choice of the parameter.\nSecond, if an l-element cover is already available, we can use it as initialization to optimize for a (l+n)-element fuzzy cover (eg set the new cover elements uniformly at random and normalize to get a fuzzy cover).\n\n- About different resolutions of covers:\n(We believe we understand what you mean, but please let us know if the following does not address your question.)\nIndeed! And this is what the method does.\nAs described in Section 3, paragraph \"Fuzzy covers\", optimization is done over the space of fuzzy covers, which is just a different name for a persistent/multiresolution/multiscale cover, ie a family of nested covers, in our case indexed by [0,1].\nThis is very much in line with persistent topology/TDA, and is what allows us to perform the quantitative experiment A, in which we show that our method compares favorably to all (to our knowledge) TDA approaches to topological inference based on persistent homology.\nThe question might be about other applications of the fact that we have a multiscale cover, since, for example, we don't leverage this in the visualization examples.\nThis is something we are actively working on.", "claims_and_evidence": "The paper supports all of its mathematical claims with sufficient proofs, either included in the main body or the appendix. Its claims on improvements to visual representation, while less rigorous, are supported by sufficient experimental evidence.", "methods_and_evaluation_criteria": "The defined goals are reasonable for the problem of cover learning; generating a cover with measure-theoretically small sets, geometrically regular sets, and a homologically faithful nerve are all well-defined and meaningful objectives in cover learning.", "theoretical_claims": "All theoretical claims are supported with correct proofs.", "experimental_designs_or_analyses": "I think the proposal here is at the end of the day a kind of coarse graining or sketching of the graph used to compute homology etc. Gie this they should be comparing to other coarse graining methods like diffusion topology from (Huguet et al. 2023 SIAM, brugnone et al. IEEE big data 2019) , also Reeb graph method like Pascussi et al. ACM Trans on graphics, also PAGA from Wolf et al. 2019.", "relation_to_broader_scientific_literature": "The contributions of the paper are highly relevant to topological data analysis, and can be used alongside recent methods which utilize simplicial complexes to draw geometric insights from data, including [Maggs et al. 2024] published in ICLR 2024. To the best of my knowledge, no previous methods have enabled the parameterization of cover learning under traditional machine learning frameworks.", "essential_references_not_discussed": "All of the ones mentioned in this review:\nHuguet et al. 2023\nWolf et al. 2019\nBrugone et al. 2019 \nPascussi et al \nAlso topological encoders from Moore et al. 2020", "other_strengths_and_weaknesses": "Strengths: the paper is very well-structured and intuitive to follow. The initial definition of three main goals in cover learning using words, followed by concise mathematical expressions for each aim, allows for a clear derivation for the paper’s resulting loss function. Representing sets in covers as vertices over a k-dimensional simplex, and representing fuzzy sets as all points contained in this simplex allows for a clean parameterization for these covers using softmax. \n\n\nWeakness: A lack of ablation studies and comparisons; an interesting study would be to exclude certain components of the loss function and observe impacts on performance. In addition, it would be interesting to see the performance of just the “FuzzyCoverInitialization” using spectral clustering, and see how much further this is optimized after gradient descent.", "other_comments_or_suggestions": "None.", "questions_for_authors": "1. From my understanding, the number of vertices (i.e. the number of subsets in the cover) is a fixed parameter; is this correct? For the results in Table 1, does the model have to be completely trained from scratch to test each vertex number 1, 2, … k until the desired homology quotient is achieved? \n2. Would this method yield more fruitful results if it used different resolutons of covers in keeping with the topological theme/", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Z0SDu9amey", "reviewer": "Reviewer_5NTw", "summary": "This paper proposes a novel algorithm for learning subset cover of a dataset with respect to its geometric and topological properties. The authors develop a gradient optimization procedure for learning the fuzzy cover of a dataset with required properties; fuzzy cover induces a simplicial filtration (by grade of membership), and by thresholding it at certain pre-defined level, they obtain the desired (crisp) cover. Experiments on different datasets show that the proposed approach yields better covers than other existing algorithms.\n\n## update after rebuttal\n\nI think that with the proposed changes this paper will be an interesting contribution to the research area. I will keep my original score (of 4).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback!\n\n- About time and memory complexity:\nOn Table 4 in the Appendix, we report the times it took to run our experiments.\nSeparately to this, we will include a complexity analysis in the paper.\n\n- About practical applications: please see \"Main comment C\", at the end of this response.\n\n- About other applicable quality metrics for Tables 1 and 2:\nOur goal was to do topological inference with small simplicial complexes (much smaller than SOTA), and we do not know of other standard ways of quantifying simplicial complex size besides number of simplices.\nPlease let us know if there are other measures we can compute.\n\n- About dependence on initialization:\nWhen our method is initialized with a good clustering, results are stable across runs, and, for experiment A, there is indeed no variance.\nWhen the method is initialized with a random fuzzy cover, the results can vary across runs.\nThis will be addressed in the ablation study/sensitivity analysis we will perform.\nPlease see \"Main comment A\" in the response to reviewer mPj7 for what we plan to include, as well as preliminary findings.\n\n**Main comment C: Applications and downstream tasks**\n\nWe start by explaining the rationale behind our choice of applications.\nA main selling point of cover learning is that it improves upon the two main TDA methodologies with a single approach, by effectively addressing their main shortcomings: the sometimes prohibitive size of geometric complexes, and the difficulty in tuning and the lack of higher dimensional information in Mapper graphs.\nThe two applications in the paper (sections 5.1 and 5.2) were chosen to demonstrate this.\n\nThe effectiveness in downstream tasks (eg shape classification) of the TDA methodologies we are improving upon has been established in the literature, so we decided to limit the scope of the paper to emphasize the theory we develop (Section 3), and the computational methods to make optimization feasible (Section 4).\nLet us also mention that, besides machine learning, topological inference has had significant scientific applications such as (Gardner et al., Nature 2022) and (Benjamin et al., Nature 2024), and that Experiment B shows that our method (re)discovers the main finding of the former paper with ease.\n\nIn addition to the above, here are further applications we are actively exploring, and will be happy to mention in the paper:\n- Point cloud vectorization:\nTypically, point clouds ought to be vectorized in a permutation-invariant way.\nOne way to do this is to construct a graph on the point cloud (eg knn graph) and then apply methods from graph machine learning.\nLarge point clouds result in large graphs, from which the global geometry is hard to extract (due to high dimensionality of the learning problem).\nOur method provides much smaller graph/simplicial complex representations of point clouds, which can potentially simplify the learning step (eg by requiring less training data).\n- Local+global dimensionality reduction:\nPopular modern dimensionality reduction algorithms such as tSNE and UMAP operate essentially locally, in the sense that they optimize embedding using interactions between few data points (typically two); with these algorithms, the preservation of global structure happens as a by-product of the preservation of global structure.\nWe believe that a local optimization procedure, as above, could be combined with a global one which is tasked with ensuring preservation of global topology, as captured by a small simplicial complex given as the nerve of a cover learned from the data.\n- Simplifying parameter selection in clustering:\nA main difficulty with many standard clustering algorithms (eg k-means) is that the number of final clusters needs to be chosen by the user.\nAn l-element cover gives rise to a graph with l vertices, and if the cover is good, the connected component of this graph represent the large scale cluster structure of the data, and give rise to a clustering of the data. So the chosen number of cover elements l is just an upper bound for the number of output clusters, and the final clustering (and the number of clusters) depends on the intrinsic geometry of the data, and not on the arbitrarily chosen number l.\n- Input for simplicial neural networks:\nCover learning produces a compact simplicial complex on geometric data, and can thus be combined with simplicial neural networks, such as\n(Roddenberry et al, ICML 2021),\n(Chen et al, AAAI, 2022),\n(Maggs et al, ICLR 2024),\n(Gurugubelli, Chepuri, ICLR 2024).", "claims_and_evidence": "Main claims of the paper are supported with enough evidence.", "methods_and_evaluation_criteria": "The proposed algorithm is adequate for the problem of cover learning.", "theoretical_claims": "All mathematics statements are given with valid proofs.", "experimental_designs_or_analyses": "Seems reasonable.", "relation_to_broader_scientific_literature": "The task of cover learning is relatively unexplored at Topological Data Analyses, but something similar was previously covered in other works; however, the problem setting and the approach proposed here are highly novel. All related works are cited in the paper.", "essential_references_not_discussed": "None, as far as I know.", "other_strengths_and_weaknesses": "Strengths:\n1. Solid theoretical part.\n2. Large number of experiments of diverse collection of datasets.\n3. Extensive background information provided in Appendices introduces reader to mathematical concepts that are used in the paper.\n\nWeaknesses:\n1. Some uncertainty about potential practical applications of the proposed method.", "other_comments_or_suggestions": "Can you provide some information on time and memory complexity of the proposed algorithm (theoretical or empirical estimations)?", "questions_for_authors": "1. Are there any other applicable quality metrics, aside from number of vertices and simplices reported in Tables 1 and 2?\n2. Can the cover constructed by the optimization procedure be influenced by initialization? If so, can you provide the mean and variance for values in Tables 1 and 2?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4ssWIyWkKk", "reviewer": "Reviewer_kSTd", "summary": "This paper introduces \"cover learning,\" an innovative unsupervised learning method designed to represent the large-scale topological structure of geometric datasets. It extends and addresses limitations present in traditional Topological Data Analysis (TDA) methods, specifically those relying on geometric complexes and Mapper graphs. The authors identify the fundamental optimization challenge of learning topologically-faithful covers and provide theoretical grounding for optimizing such covers using fuzzy covers, which facilitate gradient-based optimization. The paper proposes ShapeDiscover, a practical algorithm utilizing fuzzy cover optimization, which outperforms standard TDA methods in both quantitative topological inference and qualitative topology visualization.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback!\n\n- W1: This will be addressed in the ablation study/sensitivity analysis we will perform.\nPlease see \"Main comment A\" in the response to reviewer mPj7 for what we plan to include, as well as preliminary findings.\n\n- W2:\nWe will include this.\nIn our experience so far, the algorithm is robust to noise for both visualization and topological inference purposes, when noise is additive, or not too many outliers are present.\nWe will assess this methodically, and see how much and what type of noise is required to break the algorithm.\n\n- W3: We are actively working on this; please see \"Main comment C\", in the response to reviewer 5NTw.\n\n- W4:\nIt is true that topological persistence optimization is computationally intensive, and hasn't been tested on exceptionally large data.\nWe want to point out that 0-dimensional persistence optimization is feasible on medium size data.\nIn the MNIST experiment, we are running the topology loss on the full dataset, and on 15 cover elements (ie 15 independent times), for ~250 iterations, which effectively means that we run the topology loss 250 * 15 = 3750 times on a dataset with 60,000 points, and this took ~150 seconds.\nWe expect scalability to larger data to not pose a big problem, since the (0-dimensional) topological loss has complexity O(n log n) (n being vertices + edges in the knn graph which is in O(nk)).\nThere is an easy way to reduce computation time significantly: Run the topology loss stochastically, say every ~10 iterations, which would cut down topology optimization to 15 seconds, in the above example\n(since we use topological optimization with big steps, the gradient of the topological loss is not sparse, so running the loss even a few times does achieve the desired effect).\nAlthough we have experimented with this, we do not mention it the paper since we want to focus on the main message, and leave further tuning, optimization, and other approaches to cover learning for future work.\nHaving said this, higher-dimensional persistence optimization is, at this point in time, significantly less efficient, but we believe there is hope; please see our response to Q1.\n\n- Q1:\nExperiments A and B have examples in which the method uncovers the underlying 0-, 1-, 2- and 3-dimensional homology with many fewer simplicies than the main (to our knowledge) approaches to homological inference, even though our topological loss only ensures connectivity (as it only uses 0-dimensional homology).\nSo our method is good at higher-dimensional homological inference even if the topological loss is only 0-dimensional; we believe that this is because small measure, plus regular geometry, plus topological connectivity, in practice, is forcing the cover elements to be contractible, but at this point this is a conjecture.\nUsing higher dimensional homology in the topological loss would be computationally more expensive; we expect that, with several standard computational shortcuts (mostly subsampling and topological optimization with big steps), 1-dimensional homology could be added to the loss and have the algorithm run in the order of minutes on datasets of ~10,000 points.\nMoreover, we believe there is hope for faster approaches:\nAs we mention in the conclusions, topological regularization only seeks to simplify topology, and thus one does not need to compute, e.g., a full persistence diagram, it is enough to find a persistent feature and to produce a gradient that will make it less persistent;\nwe hope that probabilistic algorithms, sparse spectral methods, or ideas like the ones in (Chen, Kerber, Computational Geometry, 2013) could be used for this.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "To the best of my knowledge, the proofs are correct.", "experimental_designs_or_analyses": "**W1.** It seems that the experiments mainly use default parameters and vary only two parameters (maximum cover size and threshold $\\lambda$). A systematic sensitivity analysis would help in clarifying how sensitive the performance of ShapeDiscover is to variations in parameters, providing more guidance on parameter tuning.\n\n**W2.** While diverse datasets are considered, there is no explicit analysis of how ShapeDiscover performs in the presence of noise, which is a critical consideration for practical data analysis. Please include experiments (or theoretical results) with varying levels of artificial noise and assess the robustness and stability of the inferred topological structures.\n\n**W3.** A valuable avenue not explored is the integration of ShapeDiscover-generated topological representations with downstream machine learning tasks, especially deep learning. For example, investigating how ShapeDiscover’s topological representations could enhance the performance of neural networks on classification tasks (e.g., MNIST) would substantially broaden the practical relevance of this work.", "relation_to_broader_scientific_literature": "The paper situates itself within the broader scientific domain of TDA, explicitly addressing limitations of established methods such as geometric complexes and Mapper graphs. It connects to foundational concepts in computational geometry and algebraic topology, especially the nerve theorem and persistence theory (Edelsbrunner & Harer, 2022; Oudot, 2015). Moreover, by employing fuzzy covers and optimization frameworks common in modern machine learning, the paper bridges classical topology with contemporary computational methods, facilitating broader applicability.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "Strengths:\n\n**S1.**\tThe paper introduces a robust theoretical framework linking cover learning to fuzzy cover optimization, grounded firmly in geometry, topology, and optimization theory.\n\n**S2.** ShapeDiscover demonstrates superior performance in recovering accurate topological structures with fewer simplices compared to traditional methods like Vietoris–Rips and Mapper.\n\n**S3.** ShapeDiscover is capable of handling larger datasets more efficiently compared to existing methods, making it practical for real-world applications in large-scale topology visualization.\n\nWeakness:\n\n**W4.** Despite improvements, the topological persistence optimization remains computationally intensive, potentially limiting scalability for exceptionally large datasets.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "**Q1.** The algorithm primarily utilizes 0-dimensional homology for computational efficiency, how well does it generalize to higher-dimensional homology inference?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes an optimization method to learn a topological cover of to represent the large-scale topological structure of geometric datasets. It addresses the constraints of previous Topological Data Analysis (TDA) method such as Mapper graph, which explicitly requires a hand-picked filter function and other parameters. The proposed method learns a fuzzy cover through optimization, with theoretical guarantees, and outperforms standard TDA methods in both quantitative topological inference and qualitative topology visualization. Reviewers are satisfied with the rebuttal although their request for downstream applications was not addressed well.
Decision: Accept (poster)