Topologically Regularized Data Embeddings
Authors: Robin Vandaele
Bo Kang
Jefrey Lijffijt
Tijl De Bie
Yvan Saeys
Venue: ICLR 2022 Poster (2022)
Keywords: Embedding
Dimensionality Reduction
Topological Data Analysis
Persistent Homology
Optimization
Regularization

Abstract: Unsupervised feature learning often finds low-dimensional embeddings that capture the structure of complex data.  For tasks for which prior expert topological knowledge is available, incorporating this into the learned representation may lead to higher quality embeddings. For example, this may help one to embed the data into a given number of clusters, or to accommodate for noise that prevents one from deriving the distribution of the data over the model directly, which can then be learned more effectively. However, a general tool for integrating different prior topological knowledge into embeddings is lacking. Although differentiable topology layers have been recently developed that can (re)shape embeddings into prespecified topological models, they have two important limitations for representation learning, which we address in this paper. First, the currently suggested topological losses fail to represent simple models such as clusters and flares in a natural manner. Second, these losses neglect all original structural (such as neighborhood) information in the data that is useful for learning. We overcome these limitations by introducing a new set of topological losses, and proposing their usage as a way for topologically regularizing data embeddings to naturally represent a prespecified model. We include thorough experiments on synthetic and real data that highlight the usefulness and versatility of this approach, with applications ranging from modeling high-dimensional single-cell data, to graph embedding.

Published as a conference paper at ICLR 2022
TOPOLOGICALLY REGULARIZED DATA EMBEDDINGS
Robin Vandaele, Bo Kang, Jefrey Lijffitt, Tijl De Bie, Yvan Saeys
Ghent University, Gent, Belgium
ABSTRACT
Unsupervised feature learning often finds low-dimensional embeddings that cap- ture the structure of complex data. For tasks for which prior expert topologi- cal knowledge is available, incorporating this into the learned representation may lead to higher quality embeddings. For example, this may help one to embed the data into a given number of clusters, or accommodate for noise that prevents one from deriving the distribution of the data over the model directly, which can then be learned more effectively. However, a general tool for integrating different prior topological knowledge into embeddings is lacking. Although differentiable topology layers have been recently developed that can (re)shape embeddings into prespecified topological models, they have two important limitations for repre- sentation learning, which we address in this paper. First, the currently suggested topological losses fail represent simple models such clusters and flares in a natural manner. Second, these losses neglect all original structural (such as neigh- borhood) information in the data that is useful for learning. We overcome these limitations by introducing a new set of topological losses, and proposing their us- age way for topologically regularizing data embeddings to naturally represent a prespecified model. We include thorough experiments on synthetic and real data that highlight the usefulness and versatility of this approach, with applications ranging from modeling high- -igh--immnsional single-cell data, to graph embedding.
INTRODUCTION
Motivation Modern data often arrives in complex forms that complicate their analysis. For exam- ple, high-dimensional data cannot be visualized directly, whereas relational data such graphs lack the natural vectorized structure required by various machine learning models (Bhagat et al. 2011 Kazemi & Poole 2018 Goyal & Ferrara 2018). Representation learning aims to derive mathemati- cally and computationally convenient representations to process and learn from such data. However, obtaining an effective representation is often challenging, for example, due to the accumulation of noise in high-dimensinn such as community detection in social networks, graph embeddings struggle to clearly separate communities with interconnections between them. In such cases, prior expert knowledge about the topological model may improve learning from, visualizing, and interpreting the data. Unfortunately, a general tool for incorporating prior topological knowledge in representation learning is lacking.
biological expression data (Vandaele et al. 20215). In other examples
In this paper, we introduce such tool under the name of topological regularization. Here, build on the recently developed differentiation frameworks for optimizing data to capture topological prop- erties of interest Gabrieloa al. 2020 Solomon al. 202T Carriere et al., 2021). Unfor- tunately, such topological optimization has been poorly studied within the context of representation learning. For example, the used topological loss functions are indifferent to any structure other than topological, such as neighborhood, which is useful for learning. Therefore, topological optimization often destructs natural and informative properties of the data favor of the topological loss.
Our proposed method of topological regularization effectively resolves this by learning an embed- ding representation that incorporates the topological prior. As we will see in this paper, these priors can be directly postulated through topological loss functions. For example, if the prior is that the data lies on a circular model, we design a loss function that is lower whenever a more prominent cycle is present in the embedding. By extending the previously suggested topological losses to fit wider set of models, we show that topological regularization effectively embeds data according to a variety of topological priors, ranging from clusters, cycles, and flares, to any combination of these.

---

Published as a conference paper at ICLR 2022
Related Work Certain methods that incorporate topological information into representation learn- ing have already been developed. For example, Deep Embedded Clustering (Xie et al. 2016 si- multancously learns feature representations and cluster assignments using deep neural networks. Constrained embeddings of Fuclidean data on spheres have also been studied by Bai et al. (015). However, such methods often require extensive development for one particular kind of input data and topological model. Contrary to this, incorporating topological optimization into representation learning provides simple yet versatile approach towards combining data embedding methods with topological priors, that generalizes well to any input structure as long as the output is a point cloud.
Topological autoencoders (Moor et al. 2020) also combine topologiaal optimization with a data embedding procedure. The main difference here is that the topological information used for op- timization obtained from the original high-dimensional data, and not passed as a prior. While this may sound as a major advantage- and certainly can be as shown by Moor et al.] (2020) obtaining such topological information heavily relies on distances between observations, which are often meaningless and unstable in high dimensions (Aggarwal al. 2001). Furthermore, certain constructions such as the a-filtration obtained from the Delaunay triangulation-vve extensively and is further discussed in Appendix A are expensive to obtain from -isensiinn data (Cignoni et al. 1998), and are therefore best computed from the oow-dimesioonal embedding.
we will use
Our work builds on series of recent papers CabricSCnn al. 2020 Solomon et al. 2021
Carriere et al. 2021). which showed that topological optimization is possible in various settings and developed the mathematical foundation thereof. However, studying the use of topological op- timization for data embedding and visualization applications, as well as the new losses we develop therefore and the insights we derive from them in this paper, are the best of our knowledge novel.
Contributions We include sufficient background on persistent homology-the method behind topological optimization in Appendix A (note that all of its concepts important for this paper summarized in Figure [.. We summarize the previous idea behind topological optimization of point clouds (Section (. We introduce a new set of losses to model a wider variety of shapes in a natural manner (Section 2.2). We show how these be used to topologically regularize embedding methods for which the output a point cloud (Equation (T)). We include experiments on synthetic and real data that show the usefulness and versatility of topological regularization, and provide additional insights into the performance of data embedding methods (Section 3 Appendix[B) We discuss open problems in topological representation learning and conclude on our work (Section
METHODS
The main purpose of this paper is to present a method to incorporate prior topological knowledge into a point cloud embedding E (dimensionality reduction, graph embedding. ...) of a data set X. As will become clear below, these topological priors can be directly postulated through topological loss functions Crop- Then, the goal is to find an embedding that minimizes a total loss function
Leot (E = Lemb (E,X) + Xeop EE);
where the loss function Lemb aims preserve structural attributes of the original data, and Aoop controls the strength of topological regularization. Note that X itself is not required to be a point cloud, reside in the same space as E. This is especially useful for representation learning.
In this section, we focus on topological optimization of point clouds, that is, the loss function Ltop- The basic idea behind this recently introduced method-at as presented by [Brüel-Garrielsson et al. (220)) is illustrated in Section 2.1 We show that direct topological optimization may neglect im- portant structural information such as neighborhoods, which can effectively be resolved through (1) Hence, as we will also see in Section 3 while representation learning may benefit from topological loss functions for incorporating prior topological knowledge, topological optimization itself may also benefit from other structural loss functions to represent the topological prior in more truthful manner. Nevertheless, some topological models remain difficult to naturally represent through topo- logical optimization. Therefore, we introduce new set of topological loss functions, and provide an overview of how different models can be postulated through them in Section 2.2 Experiments and comparisons to topological regularization of embeddings through (T) will be presented in Section
2

---

Published as a conference paper at ICLR 2022
R=
a=5
a=
000
CCRR
ICLR
CLR
200
100
ICLR
I 75
100
40
25 90 75
25 50
75
60
100
Bich
200
200
(b)
Figure 1: The two basic concepts from persistent homology important for our method. (a) Persistent homology quantifies topological changes in a filtration, i.e., changing sequence of simplicial com- plexes ordered by inclusion, parameterized by a time parameter E Intuitively, the parameter determines the scale at which points become connected (see Definition A..0. in Appendix [A] for a formal definition of the a-complex). Various topological holes are either born or die when a in- creases. The filtration starts with one connected component per point (O-dimensional holes), which can only merge together (resulting in their death) when including additional edges. For larger a, observe the birth of cycles (I-dimensional holes, here, 'white spaces enclosed by edges'), ). which get filled in (and thus die) when a increases further. Eventually, one connected component persists indefinitely. (b) Persistent homology is commonly visualized through persistence diagrams. Here, two are plotted on top of each other (HO and HI). A tuple (b, d) marks a hole-here a connected component (H0) or cycle (Hl)-born time b that dies at (possibly infinite) time d in the filtration. Prominently elevated points (encircled in blue) capture important topological properties, such as the four clusters 'T, C'', 'L', and 'R' (HO), and the hole in the 'R', and between the 'C' and the 'L' (H1).
2.1 BACKGROUND ON TOPOLOGICAL OPTIMIZATION OF POINT CLOUDS
Topological optimization is performed through a topological loss function evaluated on one or more persistence diagrams (Barannikov) 19944 Carlsson 2009). These diagrams-obtained obtained through per- sistent homology as formally discussed in Appendix A summarize all from the finest to coarsest topological holes (connected components, cycles, voids.... in the data, as illustrated in Figure T
While methods that learn from persistent homology are now both well developed and diverse (Pun al., 2018), optimizing the data representation for the persistent homology thereof only gained al., 2020; Solomon et al.) 2021 Carriere et al.) 2021). Per- sistent homology has a rather abstract mathematical foundation within algebraic topology (Hatcher) 2002), and its computation is inherently combinatorial (Barannikov) 1994. Zomorodian & Carlsson, 2005 This complicates working with usual derivatives for optimization. To accommodate this, topological optimization makes use of Clarke subderivatives (Clarke (990), whose applicability to persistence builds on arguments from o-minimal geometry (van den Dries] 1998 Carriere et al.) Fortunately, thanks to the recent work of Briiel-Gabrieisoon
recent attention (Bbiiel-aariielsoon
2021.
al. (2020) and Carriere et al. 2202 powerful tools for topological optimization have been developed for software librarics such
as Py Torch and TensorFlow, allowing their usage without deeper knowledge about these subjects.
Topological optimization optimizes the data representation with respect to the topological informa- tion summarized by its persistence dsagram(s) D. We will use the approach by et al. 2020), where (birth, death) tuples (b, d, ), (b2, d2),..., (b D). dip)) in D are first ordered by decreasing persistence d₁ 62 The points (b, oo), usually plotted on top of the diagram such as in Figure Tb form the essential part of D. The points with finite coordinates form the regular part of D. In case of point clouds, one and only one topological hole, i.e., connected component born at time a 0. will always persist indefinitely. Other gaps and holes will eventually be filled (Figure D. Thus, we only optimize for the regular part in this paper. This is done through topologicul loss Junction, which for choice of i S j (which, along with the dimension of topological hole, will specify our topological prior as we will see below), and function g IR2 + RR is defined as
Loop
(br, dx),
where d, b, 2 d2 b2
turns out that for many useful definitions of g. Lrnp(() has a well-defined Clarke subdifferential with respect the parameters defining the filtration from which the persistence diagram D is ob-
3

---

Published as a conference paper at ICLR 2022
5 epochs
50 epochs
250 epochs
1000 epochs
60
60
80
50
50
> 50
50
40
40
40
40
30
60
30
25
25
75
25
75
25
75
optimized to have low total O-dimensional persistence. Points are colored according to their initial grouping along one of the four letters in the 'ICLR' acronym.
Figure 2: The data set in Figure la
tained. In this paper, we will consistently use the a-filtration shown in Figure (see Appendix for its formal definition), and these parameters are entire point clouds (in this paper embeddings) E E (IRd)" of size n in the d-dimensional Euclidean space. Lop can then be easily optimized with respect to these parameters through stochastic subgradient algorithms (Carriere et al. 2021).
As it directly measures the prominence of topological holes, let g: : - R: (b, + pld be proportional to the persistence function. By ordering the points by persistence, Ltop is finccionn of persistence, i.e., invariant to permutations of the points in (Carriere et al. 2021). The factor of proportionality E }1, indicates whether we want to minimize (μr 1) or maximize (μ = 1) persistence, i.e, the prominence of topological holes. Thus, μ determines whether more clusters, cycles, .... should be present (n -1) or missing (J+ = 1). The loss (2) then reduces to
Lrop E) = (D)
Σ (de bb),
where di - bi d2 b2
k=i,de<oo
Here, the data matrix E (in this paper the embedding) defines the diagram D through persistent homology of the a-filtration of E, and a persistence (topological hole) dimension to optimize for.
For example, consider 3 with (measuring the prominence of connected components) of the a-filtration. Figure 2 shows the data from Tigure[[optimizee for this loss function for various epochs. The optimized point cloud quickly resembles a single connected component for smaller numbers of epochs. This is the single goal of the current loss, which neglects all other structural structural properties of the data such its underlying cycles (e.g., the circular hole in the 'R') or local neighborhoods. Larger numbers of epochs mainly affect the scale of the data. While this scale has an absolute effect the total persistence, thus, the loss, the point cloud visually represents single connected topological component equally well. We also observe that while local neighborhoods are preserved well during the first epochs simply by nature of topological optimization, they are increasingly distorted for larger numbers of epochs.
2. oc, P 1. restricted to O-dimensional persistence
2.2 NEWLY PROPOSED TOPOLOGICAL Loss FUNCTIONS
In this paper, the prior topological knowledge incorporated into the point cloud data matrix em- bedding E is directly postulated through a topological loss function. For example, letting D be the o-dimensional persistence diagram of E (HO Figure [b]. and = 2. = oo, and Jr in (3). cor- responds to the criterion that E should represents one closely connected component, as illustrated in Figure Therefore, we often regard a topological loss as a topological prior, and vice versa.
Although persistent homology effectively measures the prominence of topological holes, topolog- ical optimization often ineffective for representing such holes in a natural manner, for example, through sufficiently many data points. An extreme example of this are clusters, despite the fact that they are captured through the simplest form of persistence, i.c., O-dimensional. This is shown in Figure 3 Optimizing the point cloud in Figure 3a for (at least) two clusters can be done by defining Ltop as in (3) letting D be the O-dimensional persistence diagram of E, = j 2, and lr -1. However, observe that topological optimization simply displaces one point away from all other points (Figure 3b). Purely topologically, this is indeed a correct representation of two clusters.
To represent topological holes through more points, we propose topological optimization for the loss Zrop E E [Cop ((x E
a random sample of E with sampling fraction fsl)]. (4) where Ltop is defined as in 3). In practice, during each optimization iteration, Zrop is approximated by the mean of Crop evaluated over ni random samples of E. Figure 3 shows the result for
4

---

Published as a conference paper at ICLR 2022
230
130
(a) Initial point cloud.
(b) Ordinary top. optimization.
(c) Optimization with
Figure 3: A point cloud topologically optimized for (at least) two clusters, without and with sam-
pling. Optimization with sampling encourages topological holes be represented by more points.
sampling fraction fs = 0.1 and repeats ns = 1. Two larger clusters are now obtained. An added benefit of (4) is that optimization be conducted significantly faster, persistent homology is evaluated on smaller samples (a computational analysis can be found at the end of Appendix A
In summary, various topological priors
be formulated through topological losses as follows.
k-dimensional holes Optimizing for k-dimensional holes (k: = 0 for clusters), can generally be done through (3) or 4 by letting DD be the corresponding k-dimensional persistence diagram. The terms and in the summation are used to control how many holes one wants to optimize for. Finally, j can chosen to either decrease (μ+ or increase (μ 1) the prominence of holes.
Flares Persistent homology is invariant to certain topological changes. For example, both linear Ttsttructueed model and a bifurcating "Y"-structured model consist of one connected component, and no higher-dimensionall holes. These models are indistinguishable based the (persistent) ho- mology thereof, even though they are topologically different in terms their singular points.
Capturing such additional topological phenomena is possible through refinement of persistent homology under the name of functional persistence, also well discussed and illustrated by Carlsson (204)). The idea is that instead of evaluating persistent homology
data matrix E, we evaluate it on a subset {a E E f(x)= S } for well chosen function f E + R and hyperparameter T.
Inspired by this approach, for a diagram D of point cloud E, propose the topological loss
(tp Lrop (1 E E fœ( S +)), informally denoted [Coop 1--00r1 (
where f is a real-valued function on E, possibly dependent on E-which changes during optimization-itsee hyperparameter, and Ctap is an ordinary topological loss as defined by In particular, we will focus on the case where equals the scaled centrality measure on E:
fE EE
gE max 9E
where g0(
Σ
y
For 2 1, Ltop EE)= = Ltop E). For sufficiently small 7 > O, Zrop evaluates Crop on the points 'far away' from the mean in the center of E. As we will see in the experiments, this is especially useful in conjunction with O-dimensional persistence to optimize for flares, i.e., star-structured shapes.
Conbinations Naturally, through linear combination of loss functions, different topological priors can be combined, e.g., if we want the represented model to both be connected and include a cycle.
3 EXPERIMENTS
In this section, we show how our proposed topological regularization of data embeddings ( leads to powerful and versatile approach for representation learning. In particular, show that
embeddings benefit from prior topological knowledge through topological regularization; conversely, topological optimization may also benefit from incorporating structural infor- mation as captured through embedding losses, leading to more qualitative representations: subsequent learning tasks may benefit from prior expert topological knowledge.
5

---

Published as a conference paper at ICLR 2022
show how topological regularization improves standard PCA dimensionality duction and allows better understanding of its performance when noise is accumulated over many dimensions. In Section 3.2, present applications to high-dimensional biological single-cell tra- jectory data as well as graph embeddings. Quantitative results are discussed in Section 3.3
In Section 3.1
Topological optimization was performed in Pytorch machine equipped with an Intel TM 17 processor at 2.6GHz and 8GB of RAM, using code adapted from Gabriel-on et al. (2020)
Tables & 2 summarize data sizes, hyperparameters, losses, and optimization times. Appendix B presents supplementary experiments that show topological regularization is consistent with earlier analysis of the Harry Potter network (Section B.1). domain application in cell trajectory inference (Section B.2 and how topological regularization reacts to different topological losses and hyperpa-
rameters (Section B.3). Code is available on github. www/robiiiiooooooocc wobiiiindddseeeo l e/toppebeedd ng.
3.1 SYNTHETIC DATA
We sampled 50 points uniformly from the unit circle in R2, We then added 500-dimensional noise to the resulting data matrix X. where the noise in each dimension is sampled uniformly from [-0.45, 0.45]. Since the additional noisy features are irrelevant the topological (circular) model, an ideal projection embedding X is its restriction to its first two data coordinates (Figure 4ap.
However, is probabilistically unlikely that that the irrelevant features will have a zero contribution to PCA embedding of the data (Figure 4b). Measuring the feature importance of each feature as the sum of its two absolute contributions (the loadings) the projection. we observe that most of the 498 irrelevant features have small nonzero effect on the PCA embedding (Figure 55. Intuitively, each added feature slightly shifts the projection plane away from the plane spanned by the first two coordinates. As result, the circular hole is less prominent in the PCA embedding of the data. Note that we observed this to be a notable problem for 'small n large p' data sets, as similar to other machine learning models, and also recently studied by Vandaele significantly accommodate for the effect of noise and result in a better embedding model on its own.
al. (2021a), more data can
We can regularize this embedding using topological loss function Lrop measuring the persistence of the most prominent 1-dimensional hole in the embedding (i = in (3). For simple Pytorch compatible implementation,
used Lemb (W, X) MSE (XWW) X). to minimize the reconstruction error between X and its linear projection obtained through W. To this, we added the loss 10 L. (W), where L1 (W) == W W J2ll2 encourages orthonormality of the matrix W for which we optimize, initialized with the PCA-loadings. The resulting embedding is shown in Figure 4d (here L1 (W) 0.03), which better captures the circular hole. Furthermore, we see that irrelevant features now more often contribute less to the embedding according to W (Figure
For comparison, Figure 4c shows the optimized embedding without the reconstruction loss Lemb- The loss L1 is still included (here L1 (W) ~ 0.2). From this and also from Figure we observe that W struggles more to converge to the correct projection, resulting in a less prominent hole.
(a) First two data coord.
(b) Ordinary PCA emb.
(c) Top. optimized emb.
(d) Top. regularized emb.
Figure 4: Various representations of the synthetic data, colored by ground truth circular coordinates.
type
denalty
pca
top opt. top reg.
8.00
21/5
feature Importance fIrelevant featuras only)
Figure 5: Feature importance densities of the 498 irrelevant features in the PCA embedding (blue), the top. optimized PCA embedding (orange), and the top. regularized PCA embedding (green).

---

Published as a conference paper at ICLR 2022
(a) Ordinary PCA embedding.
(b) Top. optimized embedding.
(c) Top. regularized embedding.
Figure 6: Various representations of the cyclic cell data. Colors represent the cell grouping.
(a) Ordinary UMAP embedding.
(b) Top. optimized embedding.
(c) Top. regularized embedding.
Figure 7: Various representations of the bifurcating cell data. Colors represent the cell grouping.
3.2 REAL DATA
Circular Cell Trajectory Data We considered a single-cell trajectory data set of 264 cells a 6812 2-dimeensional gene expression space (Cannoodt et al. 2018: Saclens al. 2019 This data can be considered a snapshot of the cells at fixed time. The ground truth is a circulan ar model connecting three cell groups through cell differentiation (see also Section B.2 It has been shown by Vandaele (020)) that real single-cell data derived from such model are difficult to embed in a circular manner.
To explore this, repeated the experiment with the same losses in Section 3.1 on this data, where the (expected) topological loss is now modified through (4) with fs = 0.25, and ns = 1. From Figure [6a] see that while the ordinary PCA embedding does somehow respect the positioning of the cell groups (marked by their color), it indeed struggles to embed the data in a manner that visualizes the present cycle. However, shown in Figure [6c| by topologically regularizing the embedding (here L1(W) ~ 4e-3) we are able to embed the data much better in a circular manner.
Figure 6b shows the optimized embedding without the loss Cemb. The embedding is similar to the one in Figure 6c (here [1(W) ~ 3), with the pink colored cell group slightly more dispersed.
Bifurcating Cell Trajectory Data We considered a second cell trajectory data set of 154 cells in 1770-dimensional expression space (Cannoodt al. 2018). The ground truth here is bifurcating model connecting four different cell groups through cell differentiation. However, this time we used the UMAP loss for the embeddings. We used topological loss Ltop Lcomn Lfaaree where Lcoan measures the total (sum of) finite O-dimensional persistence in the embedding to encourage connectedness of the representation, and Laare is as in (5). measuring the persistence of the third most prominent O-dimensional hole in (y E E Ez(y) < 0.75, where & is as in (6). Thus, Litare used to optimize for a 'flare' with (at least) three clusters away from the embedding mean. We observe that while the ordinary UMAP embedding is more dispersed (Figure 7a), the topologically regularized embedding is more constrained towards a connected bifurcating shape (Figure (c).
For comparison, conducted topological optimization for the loss Ltop of the initialized UMAP embedding without the UMAP embedding loss. The resulting embedding is now more fragmented (Figure 7b
We thus see that topological optimization may also benefit from the embedding loss.
Graph Embedding The topological loss in ( can be evaluated any embedding, and does not require a point cloud as original input. We can thus use topological regularization for embedding a graph G, to learn a representation of the nodes of G in Rd that well respects properties of G.
To explore this, we considered the Karate network (Zachary) 1977), a well known and studied net- work within graph mining that consists of two different communities. The communities are rep- resented by two key figures (John A. and Mr. Hi), as shown in Figure Sal To embed the graph, used DeepWalk variant adapted from Dagar al. 2020). While the ordinary DeepWalk em-

---

Published as a conference paper at ICLR 2022
bedding (Figure 8b well respects the ordering of points according to their communities, the two communities remained close to each other. We thus regularized this embedding for (at least) two clusters using the topological loss defined by (4), where Loo measures the persistence of the second most prominent O-dimensional hole, and is 0.25, ng = 10. The resulting embedding (Figure Dd nearly perfectly separates the two ground truth communities present in the graph.
Topological optimization of the ordinary DeepWalk embedding with the same topological loss func- tion but without the DeepWalk loss function creates some natural community structure, but results in a few outliers (Figure Scp. Thus, although our introduced loss 4 enables more natural topological modeling to some extent, we again observe that using this in conjunction with embedding losses, ie., our proposed method of topological regularization, leads to the best qualitative results.
(a) The Karate network.
(b) Ordinary Deep-
(c) Top. optimized bedding.
(d) Top. regularized bedding.
Walk embedding.
Figure 8: The Karate network and various of its embeddings.
3.3 QUANTITATIVE EVALUATION
summarrzess the embedding and topological losses we obtained for the ordinary embeddings, the topologically optimized embeddings (initialized with the ordinary embeddings. but not using the embedding loss), as well as for the topologically regularized embeddings. As one would expect, topological regularization balances the embedding losses between the embedding losses of the or- dinary and topologically optimized embeddings. More interestingly, topological regularization may actually result in more optimal, i.e., lower topological loss than topological optimization only, here in particular for the synthetic cycle data and Harry Potter graph. This suggest that combining topological information with other structural information may facilitate convergence to the correct embedding model, we also qualitatively confirmed for these data sets (see also Section B.1]. We also observe that there are more significant differences the obtained topological losses than in the embedding losses with and without regularization. This suggests that the optimum region for the embedding loss may be somewhat flat with respect to the corresponding region for the topological loss. Thus, slight shifts in the local embedding optimum, e.g., caused by noise, may result in much worse topological embedding models, which can be resolved through topological regularization.
Table 1: Summarization of the data, hyperparameters and optimization times for our experiments. The size format is #points x #dimensions for point clouds, and #vertices x #edges for graphs.
data
size
method
Ir
epochs
Atop
t w/o top
t with top
Synthetic Cycle
50 500
PCA
le-1
500
lel
<Is
5s
Cell Cycle
264 x 6812
PCA
5e-4
1000
1e2
<Is
35s
Cell Bifurcating
154 1770
UMAP
le-1
100
le1
<Is
8s
Karate
34 x 78
DeepWalk
le-2
50
5e1
29s
29s
Harry Potter
58 217
InnerProd
le-1
100
le-1
36s
34s
Table 2: Summary of the topological losses computed from persistence diagrams D with points
(bx. d+) ordered by persistence d2 by- Note that for O-th dimensional homology diagrams dj = co.
data
top. loss function
dimension of hole
fs
ns
Synthetic Cycle
(d) bi)
N/A
N/A
Cell Cycle
- (d1 b
0.25
1
Cell Bifurcating
_ by) dd. bu baleg 1 0.000075
0
0
N/A
N/A
Karate
(d2 6z)
0
0.25
10
Harry Potter
(di b1)
1
N/A
N/A
8

---

Published as a conference paper at ICLR 2022
Table 3: Embeeddinggrrcconsttuciion and topological losses of the final embeddings. Lowest in bold.
embedding loss
topological loss
data
ord. emb.
top. opt.
top. reg.
ord. emb.
top. opt.
top. reg.
Synthetic Cycle
6.3e
6.7e
6.6e
-..55
-..3
00.5
Cell Cycle
6.70
7.00
6.99
13.44
50.9
49.7
Cell Bifurcating
8576
9933
8871
117
23
63
Karate
2006
N/A
2112
-1.3
-28.5
-2.4
Harry Potter
0.20
1.11
0.23
-0.82
-2.37
3.05
Table 4: Embedding performance evaluations for label prediction.
Highest in bold.
data
metric
ord. emb.
top. opt.
top. reg.
Synthetic Cycle
r²
0.56 + 0.47
0.77 + 0.24
0.85 + 0.14
Cell Cycle
accuracy
0.79 0.07
0.79 + 0.07
0.81 + 0.07
Cell Bifurcating
accuracy
0.79 + 0.08
0.81 + 0.07
0.82 + 0.08
Karate
accuracy
0.97
0.91 0.14
0.97 0.08
We evaluated the quality of the embedding visualizations presented in this section, by assessing how informative they are for predicting ground data truth labels. For the Synthetic Cycle data, these labels are the 2D coordinates of the noise-free data on the unit circle in IR², and we used multi-ouput support vector regressor model. For the cell trajectory data and Karate network, we used the ground truth cell groupings and community assignments, respectively, and a support vector machine model. All points in the 2D embeddings were then split into 90% points for training and 10% for testing. Consecutively, we used 5-fold CV on the training data to tune the regularization hyperparameter C E (le 2, 1e 1, lel, 1e2)- Other settings were the default from SCIKIT-LEARN. The performance of the final tuned and trained model was then evaluated on the test data, through the r2 coefficient of determination for the regression problem, and the accuracy for all classification problems. The averaged test performance metrics and their standard deviations, obtained over 100 random train-test splits, are summarized in Table[4 Although topological regularization consistently leads to more informative visualization embeddings, quantitative differences can be minor, as from the figures in this section we observe that most local similarities are preserved with regularization.
4 DISCUSSION AND CONCLUSION
We proposed a new approach for representation learning under the name of topological regulariza- tion, which builds on the recently developed differentiation frameworks for topological optimization. This led to versatile and effective way for embedding data according to prior expert topological knowledge, directly postulated through (some newly introduced) topological loss functions.
A clear limitation of topological regularization is that prior topological knowledge is not always available. How to select the best from a list of priors is thus open to further research (see also Section B.3). Furthermore, designing topological loss functions currently requires some understanding of persistent homology. It would be useful to study how to facilitate that design process for lay users. From a foundational perspective, our work provides new research opportunities into extending the developed theory for topological optimization (Carriere et al., (202]) to our newly introduced losses and their integration into data embeddings. Finally, topological optimization based on combinatorial structures other than the a-complex may be of theoretical and practical interest. For example, point cloud optimization based on graph-apprn approximiiissss such as the minimum spanning tree (Vandaele eet al. 2021b), or varying the functional threshold 7 in the loss (5) alongside the filtration time (Chazal et al. 2009), may lead to natural topological loss functions with fewer hyperparameters.
Nevertheless, through our approach, we already provided new and important insights into the perfor- mance of embedding methods, such as their potential inability to converge to the correct topological model due to the flatness of the embedding loss near its (local) optimum, with respect to the topolog- ical loss. Furthermore, we showed that including prior topological knowledge provides a promising copplooical-leamiin
way to improve consecutive clusion, topological regularization enables both improving and better understanding representation learning methods, for which provided and thoroughly illustrated the first directions in this paper.
tasks (see also Section B.2). In con-

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The research leading these results has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013) (ERC Grant Agree- ment no. 615517), and under the European Union's ' Horizon 2020 research and innovation pro- gramme (ERC Grant Agreement no. 963924), from the Flemish Govermment under the "Onder- zoeksprogramma Artificiële Intelligentie (AI) Vlaanderen" programme, and from the FWO (project no. G091017N, GOF9816N, 3G042220).
REFERENCES
Aaron Adcock, Erik Carlsson, and Gunnar Carlsson. The ring of algebraic functions on persistence bar codes. arXiv preprint arXiv:1304.0530 2013.
Charu C Aggarwal, Alexander Hinneburg, and Daniel A Keim. On the surprising behavior of dis- tance metrics in high dimensional space. In International conference on database theory, pp- 420 434. Springer, 2001.
Nina Amenta, Dominique Attali, and Olivier Devillers. Complexity of delaunay triangulation for points on lower-dimensional polyhedra. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, pp. 1106-1113, 2007.
Shuanghua Bai, Huo-Duo Qi, and Naihua Xiu. Constrained best euclidean distance embedding sphere: a matrix optimization approach. SIAM Journal on Optimization, 25(1 (3(1):439449 2015.
Serguei Barannikov. The framed morse complex and its invariants. American Mathematical Society Translations, Series 2, 1994.
Smriti Bhagat, Graham Cormode, and S Muthukrishnan. Node classification in social networks. In Social network data analytics, pp. 115-148. Springer, 2011.
Jean-Daniel Boissonnat, Frédéric Chazal, and Mariette Yvinec. Geometric and topological infer- ence, volume 57. Cambridge University Press, 2018.
Rickard Brüie-Gabrielsson, Bradley Nelson, Anjan Dwaraknath, Primoz Skraba, Leonidas J Guibas, and Gunnar Carlsson. A topology layer for machine learning. In International Con- ference Artificial Intelligence and Statislics, pp. 1553-1563, PMLR, 2020.
Florian Buettner, Kedar N Natarajan, F Paolo Casale, Valentina Proserpio, Antonio Scialdone, Fabian J Theis, Sarah Teichmann, John Marioni, and Oliver Stegle. Computational anal- ysis of cell-to-cell heterogeneity in single-cell ma-sequencing data reveals hidden subpopulations of cells. Nature biotechnology. 33(2): 1512):155-160 2015.
Robrecht Cannoodt, Wouter Saelens, and Yvan Sacys. Computational methods for trajectory infer- ence from single-cell transcriptomics. European Journal of Immunology, 2016. ISSN 00142980.
nov wtt.:/ooggg...///eeeeeee.e
Robrecht Cannoodt, Wouter Saelens, Helena Todorov, and Yvan Sacys. Single-cell omics datasets containing a trajectory, October 2018. URL
1443566
Gunnar Carlsson. Topology and data. Bulletin of the American Mathematical Society, 46(2):255- 308, jan 2009. ISSN 0273-0979.
Gunnar Carlsson. Topological pattern recognition for point cloud data. Acta Numerica, 23:289-368, 2014.
Mathieu Carriere, Frédéric Chazal, Marc Glisse, Yuichi Ike, Hariprasad Kannan, and Yuhei Umeda. Optimizing persistent homology based functions, In International Conference on Machine Learn- ing, pp. 1294-1303. PMLR, 2021.
Frédéric Chazal, David Cohen-Steine Leonidas J Guibas, Facundo Mémoli, and Steve Y Oudot. Cromov-hausdonn stable signatures for shapes using persistence. Computer Graphics Forum, volume 28, pp. 1393-1403, Wiley Online Library, 2009.
10

---

Published as a conference paper at ICLR 2022
Paolo Cignoni, Claudio Montani, and Roberto Scopigno. Dewall: A fast divide and conquer delau- nay triangulation algorithm in ed. Computer-Aided Design, 30(5):333- 1998.
Frank H Clarke. Optimization and nonsmooth analysis. SIAM, 1990.
A. Dagar, A. Pant, S. Gupta, and S. Chandel. graph_nets, 2020. URL intttp:://gth/// com/ dsciitz/graph nets
Boris Delaunay al. Sur la sphere vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, 7(793-800):1-2, 1934.
Olivier Devillers and Charles Duménil. A poisson sample of a smooth surface is good sample. In EuroCG 2019-35th European Workshop on Computational Geometry, 2019.
Rex Dwyer. Higher-dimensional voronoi diagrams in linear expected time. Discrete Computa- tional Geometry, 6(3):343-367, 1991.
Palash Goyal and Emilio Ferrara. Graph embedding techniques, applications, and performance: A survey. Knowledge-HR Based Systems, 151:78-94, 2018.
Allen Hatcher. Algebraic topology. Cambridge University Press, 2002. ISBN 0521795400.
Seyed Mehran Kazemi and David Poole. Simple embedding for link prediction in knowledge graphs. In Advances neural information processing systems, pp. 4284-4295, 2018.
Giampaolo Luiz Libralon, André Carlos Ponce de Leon Ferreira, Ana Carolina Lorena, et al. Pre- processing for noise detection in gene expression classification data. Journal of the Brazilian Computer Sociery, 15(1):3-11, 2009.
Zehua Liu, Huazhe Lou, Kaikun Xie, Hao Wang, Ning Chen, Oscar M Aparicio, Michael Q Zhang, Rui Jiang, and Ting Chen. Reconstructing cell cycle pscudo time-series via single-cell transcrip- tome data. Nature communications, 8(1):1-9, 2017.
Michael Moor, Max Horn, Bastian Rieck, and Karsten Borgwardt. Topological autoencoders. In International conference on machine learning, pp. 7045-7054, PMLR, 2020.
Nina Otter, Mason A. Porter, Ulrike Tillmann, Peter Grindrod, and Heather A. Harrington. A roadmap for the computation of persistent homology. EPJ Data Science, 6(1):17, Aug 2017. ISSN 2193-1127.
Steve Y. Oudot. Persistence Theory: From Quiver Representations Data Analysis. Number 209
in Mathematical Surveys and Monographs. American Mathematical Society, 2015.
Chi Seng Pun, Kelin Xia, and Si Xian Lee. Persistent-homology--ee applications-a survey. arXiv preprint arXiv: 000.22 2018.
machine learning and its
Steffen Rendle, Walid Krichene, Li Zhang, and John Anderson. Neural collaborative filtering vs. matrix factorization revisited. In Fourteenth ACM Conference Recommender Systems, pp- 240-248, 2020.
Wouter Saelens, Robrecht Cannoodt, Helena Todorov, and Yvan Saeys. A comparison of single-cell trajectory inference methods. Nature Biotechnology, 37:1, 04 2019.
Yitzchak Solomon, Alexander Wagner, and Paul Bendich. A fast and robust method for global topological functional optimization. In International Conference on Artificial Intelligence and Statistics, pp. 107-117. PMLR, 2021.
Eashwar V Somasundaram, Shael E Brown, Adam Litzler, Jacob G Scott, and Raoul Wadhwa. Benchmarking r packages for calculation of persistent homology. The R Journal, 2021.
The GUDHI Project. GUDHI User and Reference Manual. GUDHI Editorial Board, 3.4.1 edition, 2021. WRRLatpps: /ttpp:://udhii http/iiiiiiiiaa....aaaaaaaaaaaia .irria...... fx/
Sttrr/iaafx///////3 doc/ 4.17
Csaba Toth, Joseph O Rourke, and Jacob E Goodman. Handbook of discrete and computational geometry. CRC press, 2017.
11

---

Published as a conference paper at ICLR 2022
Lou van den Dries. Tame topology and o-minimal structures, volume 248. Cambridge university press, 1998.
Robin Vandaele. Topological data analysis of metric graphs for evaluating cell trajectory data rep- resentations. Master's thesis, Ghent University, 2020.
Robin Vandaele, Yvan Saeys, and Tijl De Bie. Mining topologiaal structure in graphs through forest representations. Journal of Machine Learning Research, 21(215)1166, 2020.
Robin Vandacle, Bo Kang, Tijl De Bie, and Yvan Saeys. The curse revisited: When distances informative for the ground truth in noisy high-dimensional data?, 202
Robin Vandaele, Bastian Rieck, Yvan Saeys, and Tijl De Bie. Stable topological signatures for metric trees through graph approximations. Pattern Recognition Letters, 147:85-92, 2021b.
Robin Vandaele, Yvan Saeys, and Tijl De Bie. Graph approximations to geodesics on metric graphs. In 2020 25th International Conference on Pattern Recognition (ICPR), pp. 7328-7334, IEEE, 2021c.
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In International conference machine learning, pp. 478 487. PMLR, 2016.
W.W. Zachary. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33:452-473, 1977.
Ruoyu Zhang, Gurinder S Atwal, and Wei Keat Lim. Noise regularization removes correlation artifacts in single-cell ma-seq data preprocessing. Patterns, 2(3):100211, 2021.
Afra Zomorodian and Gunnar Carlsson. Computing Persistent Homology. Discrete & Compula- tional Geometry, 33(2):249-21) feb 2005. ISSN 0179-5376.
12

---

Published as a conference paper at ICLR 2022
A APPENDIX: INTRODUCTION TO PERSISTENT HOMOLOGY
In this part of the appendix, we provide a visual introduction to persistent homology and persis- tence diagrams that targets broad machine learning audience. Although the fundamental results leading to persistent homology are mathematically abstract (Hatcher 2002), its purpose and what it computes are rather easy visualize.
A custom case in data science for illustrating how persistent homology works, is that we have a point cloud data set X embedded in a Euclidean space IR (in the main paper, X is our embedding E). In particular, we will use the point cloud X that is visualized in the top left plot in Figure as a working example. Note that this is also the data set resembling the 'ICLR' acronym from the main paper, and that Figure iis identical to Figure Ia from the main paper. The task is now to infer topological properties of the model underlying X, by means of persistent homology.
Simplicial Complexes Looking X (Figure 9 Top Left), the only topologiaal information that can be deduced from it, is that it is a set of points. This is because no two point clouds of the same size can be topologically distinguished (at least not according to any metric defined them, which we assume to be the Euclidean distance metric here). Indeed, the displacement of isolated points in the Euclidean space, and more generally continuous stretchings and bendings, correspond to homeomorphisms, which are functions between topological spaces that preserve all topological information.
partial solution to this can be obtained by constructing a simplicial complex from X. In general, a simplicial complex can be seen generalization of a graph, where apart from nodes (O-simplices) and edges (1-simplices), it may also include triangles (2-simplices), tetrahedra (3-simplices), and so on, More specifically, the two defining properties of a simplicial complex A are that
* A is a set of finite subsets of some given set S; o' Co E A, then o' A.
Each element a in such a simplicial complex is called a face or simplex. If |o| = k + 1, it is also called a k-simplex, and i is called the dimension of a.
One should note that this is formally the definition of an abstract simplicial complex, and the term simplicial complex commonly refers to a geometrical realization of such complex. Such realiza- tion can be seen as continuous drawing of the complex in some Euclidean space Rd, such that the intersection of two simplices a and o' corresponds to a common face of a and o'. This similar to how planar drawing of graph (without intersecting edges) metric graph is geometric realization of a graph (Vandaele et al. 2021c). However, for simplicial complexes we also 'fill in' the 2- 2-simplices, 3-simplices, .... which is usually how visualize (abstract) simplicial complexes,
a =
a =
a = 10
70
CTR
70
CLR
60
60
60
50
50
50
40
40
40
30
30
30
25
50
75
25
50
75
25
50
75
a = 25
C. = 75
= Inf
70
CLR
70
70
60
60
60
50
50
50
40
40
40
30
30
30
25
50
75
25
50
75
25
50
75
X
X
X
Figure 9: An example of six simplicial complexes Aa (X) the a-filtration filtration of a point cloud data set X resembling the 'ICLR' conference acronym in the Euclidean plane. informally used to denote the complex that contains all simplices, which here equals the Delaunay
is
triangulation, and will necessarily be identical to A. (x (X) for some finite Ryo-
13

---

Published as a conference paper at ICLR 2022
Sometimes the term 'simplex' is only used to refer to geometric realizations of their discrete counterparts, and the discrete counterparts are only referred to as 'faces'. For the purpose of this paper, it is not an issue for one to mix up this terminology. i..., to identify simplicial complexes with their discrete counterparts, and we will often proceed to do this.
such as in Figure 9
The most important thing to be aware of, is that (persistent) homology is concerned with topologiaal properties of the 'continuous versions' (geometric realizations) of simplicial complexes, which are computed through their 'discrete" (abstract) counterparts. Compare this to how the connectedness of a graph (as graph, or thus, a finite combinatorial structure,) determines the connectedness of any of its geometric realizations (as a topological space containing uncountably many points).
The a-complex When given point cloud X (or in this paper an embedding E), we consider the a-complex (X) at 'time" o E R2o. This complex summarize topological information from the continuous model underlying the discrete point cloud X at the 'scale" determined by a. is subcomplex of the Delaunay triangulation (Delaunay et al. 1934) of X, as shown in Figure 9 The Delaunay triangulation equals the simplicial complex at the informally used time a = co. Note that the definition of the a-complex as subset of the Delaunay triangulation below (Boissonnal et al. 2018) can be more difficult to grasp than the definition of other simplicial complexes, such as the Vietoris-Rips complex (Otter et al.) 2017), that are not used in this paper. However, the exact definition is not required to understand the basic ideas presented in the main paper, and is mainly included for completeness. What is most important is that the a-complex aims quantify topological properties underlying X, as is illustrated in Figure and will be further discussed below. For good overview and visualization of how the a-filtration is constructed, we refer the interested reader to The GUDHI Project (202I), from which we obtained the following definition.
Definition A.0.1 (a-complex). Let X be a point cloud in the Euclidean space Rd, and A the Delaunay triangulation of X. For a = O, the a-complex (x))(X) of X simply equals the set of points of X (thus simplicial complex with only 0- O-simplicss). More generally, to every simplex in A. we assign a time value a, which equals the square of the circumradius of a if its circumsphere contains no other vertices than those in a, in which case a is said to be Gabriel, and as the minimum time values of the (la) + 1) 1)-simplices containing that make it not Gabriel otherwise. For a > O, the a-complex (x of X is now defined as the set of simplices in A with time value at most a.
Topological Holes and Betti Numbers Once we have constructed an a-complex (x from X. we can now infer topological properties that are more interesting than X being a set of isolated points. For example, in Figure 9 we see that 1 (X) captures many important topological proper- ties of the model underlying X, which consists of four disconnected components (one for each of the letters 'T, 'C', 'L', and 'R' in the conference acronym), and also captures the circular hole that is present in the letter 'R', HHomloog exactly quantifies such information by associating Betti numbers 3 to the simplicial complex. Be corresponds to how many k-dimensional holes there are in the complex. In this sense, a O-dimennionnl hole correspond a gap between two components, and So equals the number of connected components. A 1-dimensional hole corresponds to a loop (which can be seen as circle, ring, or a handle of a coffee mug), and 2-dimensional hole corresponds to a void (which can be seen as the inside of a balloon). In general, an n--dimensional hole corresponds to the interior of a re-sherre in R=+11 Note that no n-dimensional holes can occur in the Euclidean space Rd whenever d S and therefore (as well as for computational purposes) one often restricts the dimension l of the simplicial complexes that are constructed from the data.
Filtrations and a-Filtrations The difficulty lies in pinpointing an exact value for a for which (x( truthfully captures the topological properties of the model underlying X. For example, (x) still captures the hole in the 'R', but connects the points representing the letters 'L' and 'R' into one connected component. A75 (X) captures only one connected component, but also captures prominent hole that is composed between the letters "C' and 'R'. This larger hole can also be seen as a particular topological characteristic of the underlying model, though on a different scale. This is where 'persistent' homology comes into play. Rather than inferring these topological properties (holes) for one particular simplicial complex, the task of persistent homology is to track the change of these topological properties across a varying sequence of simplicial complexes
Do C A C ..... C CAn:
14

---

Published as a conference paper at ICLR 2022
which is termed a filtration. The definition of an a-simplex directly gives rise to such filtration, termed the a-filtration:
Indeed, for a < a', it follows directly from the definition of a-complexes that (x S (X). Note that in practice, for finite data, the simplicial complex across this filtration changes for only finitely many time values a, and we may indeed regard this filtration to be of the (finite) form Ao C A .... S A.. The time parameter is considered to parameterize the filtration, and is thus also termed the filtration time.
Persistent Homology When given filtration parameterized by a time parameter (e.g., f = a), one may observe changes in the topological holes when t increases. For example, as illustrated in Figure different connected components may become connected through edges, or cycles may either appear or disappear. When a topological hole comes to existence in the filtration, we say that it is born. Vice versa, we say that a topological hole dies when it disappears. The filtration time at which these events occur are called the birth time and death time, respectively. Simply put, persistent homology tracks the birth and death times of topological holes across a filtration. 'Ho- mology' refers to the topic within algebraic topology that considers the study and computation of these holes in topological models, and rests on (often abstract) concepts from mathematical fields such group theory and linear algebra. As it may distract one from the main purpose of persistent homology we aim to introduce in this paper, we will not provide an introduction to these topics here, but we refer the interested reader to Hatcher (2002). 'Persistent" refers to the fact that one tracks homology, or thus topological holes, across an increasing filtration time parameter, and that persis- tent holes-those that remain present for many consecutive time values t-are commonly regarded to be informative for the (underlying) topological model in the data. This is the interpretation of persistent homology maintained for topological regularization, as well as for designing topological loss functions, in the main paper. However, more recent work shows that also finer topological holes that persist for short time intervals can be effective for machine learning applications, for example, for protein structure classification (Pun et al. 2018).
Persistence diagrams are a tool to capture and visualize the information quantified through persistent homology of filtration. Formally, persistence diagram a set
Persistence Diagrams
DE = {(ta, 00) : siSS
CEiSNJU NJ
< tad J {(x, x) : x ERR
D
where la,, Idy. 1 SiiS 1. < M, correspond to the birth and death times of k- dimensional holes across the filtration. Points (ta.; oo), are usually displayed on top of the diagram. They correspond to holes that never die across the filtration, and form the essential part of the per- sistence diagram. In the case of a-filtrations, one always has that D = {0,, x))} and Di for k 2 1. This is because eventually, the simplicial complex in the filtration will consist of one con- nected component that never dies, and any higher dimensional hole will be 'filled in', as illustrated by Figure 9 Hence, during topological regularization of data embeddings, and discussed in the main paper, we cannot topologically optimize for the essential part of any persistence diagram of our embedding. The points (ta, tdd) in D& with finite coordinates to, < td, form the regular part D of the persistence diagram. These are the points for which we optimize with topological regu- larization. Finally, the diagonal is included in a persistence diagram, as to allow for a well-defined distance metric between persistence diagram, termed the bottleneck distance.
Definition A.0.2 (bottleneck distance). Let 'D and D' be two persistence diagrams. The bottleneck distance between them is defined as
ds (D, (D, = sup [|x (( E RRU(,))
x
where ip ranges over all bijections from D to D', and ranges over all points in D. By convention, we let oo- x = when calculating the distance between two diagram points. Since persistence diagrams include the diagonal by definition, [D] [D'| [R]. Thus, do (D, D') is well-defindd, as unmatched points in the essential or regular part of a diagram can always be matched to the diagonal.
15

---

Published as a conference paper at ICLR 2022
300
200
Dealh
50
A H1
50
100
200
300
Birth
Figure 10: The diagrams Do (black points, H0) and Di (red points, H1) for the a-filtration filtration of the point cloud data set Figure plotted on top of each other. The six highly elevated points (encireled in blue) identify the presence of four connected components (HO), corresponding to the 'T. 'C', 'L', and 'R' letters in the conference acronym, and two cycles (HI), corresponding to the hole in the letter 'R' (born earlier) and composed between the letters 'R' and 'C' (born later).
The bottleneck distance commonly justifies the use of persistent homology as a stable method for quantifying topological information in data, i.e., robust to small data permutations (Oudot 2013). Note that although the bottleneck distance is not used in the main paper, we can also conduct topo- logical optimization with respect to this metric (Carriere et al. )
Figure 10 shows the persistence diagrams Dn and Dj of the a-filtration for our considered point cloud data X in Figure | (plotted on top of each other, which is common practice topological data analysis). Note that all points in Do have O as first coordinate. This corresponds to the fact that all connected components are born at time a O in the o-filtration. At this time all points are added but no edges between them. Du also has exactly one point equal to (0, oc) plotted on top of the diagram. This quantifies that the simplicial complex eventually constitutes one connected component that never dies, as illustrated by Figure Birth times for points in Dj are nonzero, since edges are necessary for cycles to be present. They all have finite death-times, since they must be filled in at least at some point in time, as illustrated by Figure 9
We see that in the combined diagrams, there are six prominently elevated points (b, d) for which by the vertical distance d from the point to the diagonal-is signif-
the persistence-measuuee icantly higher than all other points (encircled in blue in Figure 10). These quantify the prominent topological features in the model underlying the data X which we discussed earlier. For Du, these are the four connected components, one for each one of the letters 'I', 'C', 'L', and 'R'. Note that the single point (0, oo) on top may give deceptive view that there is only one prominently elevated point in Do- However, there are as many points in Do as data points in X (which may be difficult deduce from Figure 10 due overlapping points), and the four encircled points in Do are indeed significantly more elevated. For D1, the two prominently elevated points quantify the hole in the 'R' and the hole between the letters 'C' and 'R'. Note that the birth time of the hole between the letters 'C" and 'L' is much later, as it occurs on a larger scale than the hole in the letter 'R'. The latter occurs at the scale where the four clusters, one for each letter, occur as well (Figures 9 10).
Computational Cost of Persistent Homology A remaining disadvantage of persistent homology its computational cost. Although it is an unparalleled tool for quantifying all from the finest to coarsest topological holes in data, it relies on algebraic computations which can be costly for larger sized simplicial complexes. In the worst case, these computations are cubic in the number of simplices (Otter et al. 2017).
For data set X C Rd of points, the a-complex has size and computation complexity O (n
(Otter et al. 2017 Toth et al., 2017 Somasundaram et al. 2021). However, this can be signifi- cantly lower practice, for example, if the points are distributed nearly uniformly on polyhedron (Amenta et al. 2007). Another popular type of filtration is the Vietoris -ipss filtration for which topological optimization is also implemented by GabiiesGo et al. (020)-whiee has size and computation complexity Ominn2"" =++1)), )). where d 2 i is the homology dimension of inter- est (Otter et al. 2017 Somasundaram al. 2021). In practice, the choice of k will also significantly
16

---

Published as a conference paper at ICLR 2022
reduce the size of the a-complex prior to persistent homology computation. However, the full com- plex, ie., the Delaunay triangulation, still needs to be constructed first (Boissonnat et al., 2018 This is often the main bottleneck when working with a-complexes of high-dimensional data.
In practice, a-complexes are favorable for computing persistent homology from low dimensional point clouds, whereas fewer points in higher dimensions will favor Vietoris-Rips complexes (Soma- sundaram et al. 2021). Within the context of topological regularization and data embeddings, we aim achieve a low dimensionality of the point cloud embedding. This justifies our choice for a-filtrations in the main paper.
Computational Cost of Topological Loss Functions When makes of sampling fraction 0 < fs S 1 along with ns repeats, the computational complexity of the topological loss function reduces to (ns (Jss))8f1) when using a- e-filtrations, where d the embedding dimensionality. The added benefit of sampling is that some topological models be even more naturally modeled, as shown in the main paper.
Nevertheless, as discussed above, the computational complexity may often be significantly lower in practice, due to constraining the dimension of homology for which we optimize, and that com- mon distributions across natural shapes admit reduced size and time complexities of the Delaunay triangulations (Dwyer) 1991 Amenta et al. 2007 Devillers & Duménil 2019).
Note that many computational improvements as well approximation algorithms for persistent homology are already available (Otter et al. 2017). However, their integration into topological optimization (and thus regularization) is open to further research.
B APPENDIX: SUPPLEMENTARY EXPERIMENTS
In this part of the appendix. we include additional experiments that illustrate the usefulness and ef- fectiveness of topological regularization. Section B.I includes an additional qualitative evaluation on the Harry Potter network, which shows that its graph embedding topologically regularized for a circular prior is consistent with earlier and independent topological data analysis of this network (Vandaele et al. (2020). In Section B.2, we show how including prior expert topological informa- tion into the embedding procedure may facilitate automated pseudotime inference in the real cyclic single-cell expression data presented in the main paper. Finally, in Section B.3 we show how topo- logical regularization reacts to different topological loss functions, either designed to model the same prior topological information, different and potentially wrong prior information.
B.1 ADDITIONAL QUALITATIVE EVALUATION ON THE HARRY POTTER NETWORK
We considered an additional experiment on the Harry Potter graph obtained from https: This graph is composed of characters from the Harry Potter novel (these constitute the nodes in the graph), and edges marking friendly rela- tionships between them (Figure IT]. Only the largest connected component is used. This graph has previously been analyzed by Vandacle et al. (2020), who identified a circular model therein that transitions between the 'good' and 'evil' characters from the novel.
github. www.cc/cc....... wwweee/caaratee-nettteee
To embed the Harry Potter graph, we used a simple graph embedding model where the sigmoid of the inner product between embedded nodes quantifies the (Bernoulli) probability of an edge occurrence (Rendle et al. 2020). Thus, this probability will be high for nodes close to each other in the embedding. and low for more distant nodes. These probabilities are then optimized to match the binary edge indicator vector. Figure 1 12a 2a model presented by Vandaale al. (2020). For clarity, character labels are only annotated for a subset of the nodes (the same by Vandaele et al. (2020)).
shows the result of this embedding, along with the circular
We regularized this embedding using a topological loss function Ltop that measures the persistence of the most prominent I I-dimensional hole in the embedding (see also Table the main paper). The resulting embedding is shown in Figure 12c Interestingly, the topologically regularized embedding now better captures the circularity of the model identified by Vandaele et al. (020)), and focuses more on distributing the characters along it. Note that although this previously identified model is included in the visualizations, it is not used to derive the embeddings, nor is it derived from them.
17

---

Published as a conference paper at ICLR 2022
For comparison, Figure 12b shows the result of optimizing the ordinary graph embedding (used as initialization) for the same topological loss, but without the graph embedding loss. We observe that this results in a sparse enlarged cycle. Most characters positioned poorly along the circular model, and concentrate near a small region. Interestingly, even though we only optimized for the topological loss here, it is actually less optimal, i.e., higher than when applied topological regu- larization (see also Table in the main paper). This is result from the sparsity of the circle, which constitutes larger birth time, and therefore overall a lower persistence of the corresponding hole.
Fiilfyy
Ar or
Lovegood
Dellby
Cedric DedricDiggory
Neville Loo ghottom
Hodwig
Rubeus
He Jermicae Cranger
Moan Myrtle
Barteming Crouch
Severt
Olymp Maxime
Wharge/WWasieyy bembledoe
Lord veldemort
Igor Karkaroft Sotter
Sr.
James Potter
Bartemiu crouch Sr.
Malloy
Mracy
Figure 11: The major connected component in the Harry Potter graph. Edges mark friendly rela- tionships between characters.
Lons Voldemert Vincent Crabbe
Luctus
Crouch St.
Herry Potter Bumbikddrr
Stafty New cars aod Hit Crogch Sr. cirappee Vinnieeeiingt Virogit
Lsty sadee lion Wersley
Rappley Sn.
Noeding Myrtie
ObymosiMaziine
JamesiPutteer
Basbemius Crouch ja Plutty
Severue Snape Albus Dumbledore
Lovegood
Whrre
eiggory
Dwbbit
sit Hecsmackk
Gearge
cedris Diggory
Langhettom
Luria Laavegood
Darteesius Croach Jr.
Hermione Granger
Ron Wessley
Olympe
(a) Ordinary graph embedding.
(b) Topologically optimized embedding (initialized with the ordinary graph embedding).
Viscent Grabbe
prang Maltoy
Lord Upillmort
Bartemiup Crouch
BartwmmssCrouch
Iluffy
Hedwig
Longbottom
Igor Karkaroff
Patter
Olympes
Masrilig Myrtie
cedtric Daggory Luns Lovegood
Andipg
Albus Dumblicdor Cesier Weaulpy 200
Sirila
uranger
(c) Topologically regularized embedding.
Figure 12: Various embeddings of the Harry Potter graph and the circular model therein.
18

---

Published as a conference paper at ICLR 2022
B.2 APPLICATION: PSEUDOTIME INFERENCE CELL TRAJECTORY DATA
Single-cell omics include various types of data collected on cellular level, such transcriptomics, proteomics and epigenomics. Studying the topological model underlying the data may lead to better understanding of the dynamic processes of biological cells and the regulatory interactions involved therein. Such dynamic processes can be modeled through trajectory inference (TT) methods, also called pseudotime analysis, which order cells along trajectory based on the similarities in their expression patterns (Saelens et al. 2019).
For example, the cell cycle a well known biological differentiation model that takes place cell as it grows and divides. The cell cycle consists of different stages, namely growth (GI), DNA synthesis (S), growth and preparation for mitosis (G2), and mitosis (M). The latter two stages are often grouped together in G2M stage. Hence, by studying expression data of cells that participate in the cell cycle differentiation model, one may identify the genes involved in and between particular stages of the cell cycle (Liu et al. 2017p. Pseudotime analysis allows such study by assigning each cell time during the differentiation process which it occurs, and thus, the relative positioning of all cells within the cell cycle model.
Thus, the analysis of single cell cycle data constitutes a problem where prior topological information is available. As the signal-to-noise ratio is commonly low in high-dimensional expression data (Libralon et al. 2209 Zhang et al. (021). this data is usually preprocessed through a dimensionality reduction method prior to automated pseudotime inference (Cannoodt al., 2016 Saclens al., 2019). Topological regularization provides a tool to enhance the desired topological signal during the embedding procedure, and as such, facilitate automated inference that depends on this signal.
To illustrate this, we used persistent homology for an automated (cell) cycle and pseudotime infer- ence method, with and without topological regularization during the PCA embedding of the data. The data we used for this experiment is the real cell cycle data presented in the main paper, also pre- viously analyzed by [Buettner et al. (2015). The topological regularization procedure we followed here is the same in the main paper, i.e., we regularized for circular prior (see also Tables I & & in the main paper). Our automated pseudotime inference method consists of the following steps.
23
10
129
129
122
200
(a) The representation of the most (b) Orthogonal projection of the The pseudotimes inferred from prominent cycle obtained through bedded data onto cycle represen- persistent homology.
the orthogonal projection, quanti- fied on a continuous color scale.
tation.
Figure 13: Automated pseudotime inference of real cell cycle data through persistent homology, from the PCA embedding of the data.
prime
23
30
(a) The representation of the most (b) Orthogonal projection of the em- prominent cycle obtained through bedded data onto the cycle represen- persistent homology.
(c) The pseudotimes inferred from the orthogonal projection, quanti- fied on continuous color scale.
tation.
Figure 14: Automated pseudotime inference of real cell cycle data through persistent homology, from the topologically regularized PCA embedding of the data.
19

---

Published as a conference paper at ICLR 2022
1. First, representation of the most prominent cycle in the embedding is obtained through persistent homology from the a-filtration, using the Python software library Diony- It can be seen
sus btttps://pypi.orgg// http:///soc.//oooossss/s/////// lar pnivesentation-diserrrtttt in edges between data points-of the point in the 1st- dimensional persistence diagram that corresponds the most persisting cycle (Figures 13a & [4a).
circu-
2. An orthogonal projection of the embedded data onto the representative cycle is obtained. This is intermediate step derive continuous pseudotimes from a discretized topologiaal representation, as earlier described by Saclens et al. (2019) (Figures 13b & [
3. The lengths between consecutive points on the orthogonal projection are used to obtain circular pseudotimes between 0 and 2 (Figures 13c & 14c
Note that within the scope of the current paper, we do not advocate this to be a new and generally ap- plicable automated pseudotime inference method for single-cell data following the cell cycle model. However, we chose this particular method because it illustrates well what persistent homology iden- tifies in the data, and what we aim optimize through topological regularization.
For example, we observe that the (representation of) the most prominent cycle in the ordinary PCA embedding is rather spurious, and mostly linearly separates G1 and G2M cells. Projecting cells onto the edges of this cycle places the majority of the cells onto a single edge (Figure 133). The resulting pseudotimes are mostly continuous only for cells projected onto this edge. whereas they are very discretized for all other cells (Figure [3c.. However, by incorporating prior topological knowledge into the PCA embedding. the (representation of) the most prominent cycle in the embed- ding now better characterizes the transmission between the G1, G2M, and S stages in the cell cycle model (Figure 14a). The automated procedure for pseudotime inference now also reflects a more continuous transmission between the cell stages (Figures 14b & 14c).
B.3 TOPOLOGICAL REGULARIZATION FOR DIFFERENT LOss FUNCTIONS
In its current stage, postulating topological prior information directly performed by designing a topological loss function. This requires some understanding of persistent homology. How to facilitate that design process for lay users is open to further research. A starting point for this is exploring how topological regularization reacts to different (and potentially even wrong) prior topological information and loss functions. This is the topic of this section.
Different Loss Functions for the same Topological Prior (varying fs, nts, or T) In the main paper, we have introduced new topological loss functions 4 and (5). It may be useful to investigate how topological regularization reacts to different choices of the hyperparameters that are used in these loss functions. These are the sampling fraction fs and number of repeats ng in (4). and the functional threshold T in (5). Note that although changing these hyperparameters may result in changing the geometrical characteristics that are specified, the topological characteristies may be considered to remain roughly the same with respect to the chosen topological loss function.
Varying is and ns Figure 15 shows the topologically regularized PCA embedding of the real single-cell data from the main paper that follows the cell cycle differentiation model (also discussed in Section 13ch for varying choices of the values fs and n.s The topological loss function and all other hyperparameters are identical to those in the main paper for this data (see also Tables & in the main paper).
We observe that by either increasing fs or nts the cycle tends to become more defined. More specifically, one can better visually deduce a subset of the data that represents and lies on a nearly perfect circle in the Euclidean plane. Nevertheless, we also conclude that using more data during topological regularization, i.e., higher values of fs does not necessarily result in more qualitative embeddings. Indeed, this gives higher chance of the topological loss function focusing on spurious holes during optimization, for example the hole illustrated in Figure 13a From Figure more difficult to deduce due to overlapping points-oa sult in slightly worse clustering, most notably dispersing the pink colored cells (or, as discussed in Section B.2 GI cells) more across the entire circular model instead of confided region.
although that higher values of fs generally
20

---

Published as a conference paper at ICLR 2022
6 = 025. =1
4= 0.25.,
0.25, 61% Sphtef
40
60
-90
-40
f-
fg 0.5. ng
Fg 0 5. nl
40
40
20
20
20
80
-20
-40
80
40
20
20
40
60
80
-60
40
-0
20
60
-50
25
26
75
fg
0. 75,
fg
75,
10
f- 0.75, 25
20
-20
-40
-50
75
f= 1,
4 1. ng
6 1,
40
40
20
-20
-20
-20
-40
-40
-40
-50
-25
50
75
-50
-25
50
75
Figure 15: The topologically regularized PCA embedding of the cell cycle data set from the main paper and Section B.2 for varying sampling hyperparameterss ss (the sampling fraction) and (the number of repeats). Note that the embeddings in the bottom row are all identical to ns = 1.
Embodding time by sampling fraction fz
Embodding time by number of repeats
1000
1000
F5
025
800
24
26
100
0.75
0.5
tome (N)
time (3)
0.3
0.5
0.7 0.9
1.0
25
Figure 16: Total computation time of the topologically regularized embedding in seconds (ran for 1000 epochs as in the main paper), by sampling fraction fs and number of repeats n.s. Note that for fs 1 unnecessary to consider ns > and the computation time is constant over ngs There- fore, computation times for fs 1 and ns 1 are also not included in the left plot, as they may give deceptive view. During each step the topologically regularized embedding optimization, the topological loss function is computed over 264/s points, repeatedly when specified so by
21

---

Published as a conference paper at ICLR 2022
I= 0.25
T= 0.5
t= 0.75
10.0
75
75
75
50
50-
25
00
-25
-25
-25
-500
-50
-15
-7.5
-10.0
-10.0
-10
-10
-10
Figure 17: The topologically regularized UMAP embeddings of the bifureating real single cell data presented in the main paper according (8), for various functional thresholds T.
An added advantage of our introduced topological loss function 4 which is approximated through sampling strategy, is that it increases computational efficiency. One can use lower sampling fractions fs not only to avoid optimizing for spurious holes, but also conduct this optimization significantly faster, as also discussed in our computational analysis in Section A This can be seen from Figure T6 which compares the computation time in seconds of the topologically regularized embeddings for different sampling fractions Is and number of repeats ni..
Varying r Figure 17 shows the topologically regularized UMAP emhedding of the real single-cell data following a bifurcating cell differentiation model from the main paper, for varying choices of the functional threshold т. Recall that 0 < r < 1 was threshold on the normalized distance of the embedded points to their mean as defined in 66) in the main paper. Intuitively, T specifies how close one looks to the embedding mean, with higher values of 7 allowing more points (thus closer to the embedding mean) to be included when optimizing for three clusters away from the center.
This is consistent with what we observe from Figure 17 While little differences can be observed 0.75 (which was the value chosen in
between 5 = 0.25 and r 0.5, we observe that for the main paper), points near the center of bifurcation are more stretched towards the leaves, i.c., endpoints, in the embedded model. This agrees with the fact that for higher values of T, more points close to the center are included when optimizing for three separated clusters.
Different Loss Functions for the same Topological Prior (varying g) For one particular type of prior topological information, one can design different topological loss functions by varying the real-valued function g evaluated on the persistence diagram points that used in the loss function 2
presented in the main paper. In particular, our topological loss function 3 in the main paper, where we let = by dr, is inspired by the topological loss function
dx (dh+ )
Ctop = Crop (D) = a Σ <om
(d+ 6b)²
where b1 2 22-2-00 b2
introduced by Brruel-Gabrielsoon et al. (2020), and more formally investigated within an algebraic setting by |Adcock et al. (2013). Here, and q are byperparameters that control the strength of penalization, whereas i and the choice of persistence diagram (or homology dimension) is used to postulate the topological information of interest. The choice of μ E (1,-1} determines whether one wants to increase (μ 1) or decrease cal loss function in the data is designed. The term (d+ - bx) can be used to control the prominence, i.e., the persistence, of the most prominent topological holes, whereas the term (detbe) can be used control whether prominent topological features persist either early or later the filtration.
the topological information for which the topologi-
Our topological loss function in the main paper is identical to 77) with the additional change that we sum to the hyperparameter, j instead of [Dres], which allows for even more flexible prior topological information. Note that this one of the most simple and intuitive, yet flexible, manners to postulate topological loss functions. Indeed, (d₃ (dg=b)))" directly measures the persistence of the k-th most prominent topological hole for chosen dimension of interest. The role of # is to be further investigated within the context of topological regularization and formulating prior topological information.
1 and O. and
22

---

Published as a conference paper at ICLR 2022
p
p=
p=
16.0
75-
75-
10
50
50-
000000
-25-
-50
-5.0
-5
-75
-10.0
-10.0
-10
-10
10
10
Figure 18: The topologically regularized UMAP embeddings of the bifureating real single cell data presented in the main paper according (8), for various values of p.
may already be clear that the same topological information can be postulated through different choices for > 0. To explore this, we considered two other topologically regularized UMAP em- beddings of the real bifurcating single cell data presented in the main paper, for the same topological loss function where only the parameter p is varied, i.e.,
Lrop E
(dx bx)p - [(ds bb) 1
(8)
k=2
Figure 18 shows the resulting embeddings for = 1 and p = 2, as well as the original embedding for p from the main paper for easy comparison.
In the first term of our topological loss function (8), higher values of p will more strongly penalize larger gaps between neighboring points. This can be seen in Figure [8] for the majority of the em- bedded points, which are more pulled towards the leaves (endpoints) of the represented topological model. However, this results in few more displaced points near the center of bifurcation, which try to remain connected as we simultaneously fit the UMAP loss function. Indeed, in the main pa- per we have seen that without the UMAP loss function, the model represented in the topologically optimized embedding will be more fragmented. Hence, in the current experiment, larger values of in the term Σin - (b)) seem to better motivate many smaller gaps (at the cost of a few larger gaps), whereas lower values appear motivate more evenly spaced points. The fact that more points are pulled from the center towards the leaves for larger values and not from the leaves towards the center, is consistent with the fact that in the original dimensimenii space, points are far away from each other and the center, than they are close. This has previously been analyzed for this particular data set by Vandaele (2020).
Nevertheless, although different values of p appear to affect the overall spacing between points, we that the embedded topological shape remains overall recognizable and consistent (Figure
Different Loss Functions for different Topological Priors (example for PCA) As user may not always have strong prior expert topological knowledge available, it may be useful to study how topological regularization reacts different topological loss functions that are designed to model weaker or even wrong topological information. Indeed, if the impact of topological regularization on embeddings may be too strong. the user might wrongfully conclude that a particular topological model is present in the data when it can be easily fitted according to any specified shape.
To explore this, we considered various additional topological functions topologically regularize the PCA embedding of the synthetic data set of points lying circle with added noise in high dimension, presented in the main paper. Note that here we know that there is exactly one topolog- ical model, i.c., circle, that generates the data. We performed the topologically regularized PCA embedding of this data for the exact same hyperparameters as summarized in Table [ in the main paper, but now for the three other topological loss functions that are summarized in Table 5 The intuition of these topological loss functions, in order of appearance in Table 5 is as follows.
The first topological loss function
be considered to specify weaker form of prior topological information than in the original embedding where we restricted to the term -(d, b1). Now, the topological loss function states that the sum of persistence of the two
23

---

Published as a conference paper at ICLR 2022
Table 5: Summary of the additional topological losses computed from persistence diagrams D with points (bg, dz) ordered by persistence dę bR, used to study the topologically regularized PCA
embedding of the Synthetic Cycle from the main paper for weaker or wrong topologiaal information.
top. loss function
dimension of hole
fs
TLS
(d1 b1) (d2 b2)
N/A
N/A
- (d2 - b2)
N/A
N/A
Enmz(de (ds bb) Ids bule 000,0.77
0-0
N/A
N/A
10-
0.4
100
05
0.0
0.-
0.0
-0.5
-0.
-0.5
-04-
-1.0
-0.5
0.0
0.5
100
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
10
Figure 19: Various topologically regularized embeddings of the 500-dimensional synthetic data X for which the ground truth model is circle, as presented in the main paper. (Left to Right) The topological loss function used for topological regularization of the PCA embedding equals the loss function formulated in Table 5 (Top to Bottom).
most prominent cycles in the embedding should be high. However, this does note impose that the persistence of the second most prominent cycle must necessarily be high.
The second topological loss function can be considered to specify partially wrong form of prior topological information. Here, we optimize for a high persistence of the second most prominent cycle in the embedding. Of course, this imposes that the persistence of the most prominent cycle in the embedding must be high as well.
Our third topological loss function can be considered to specify wrong prior topological information. Here, the topological loss function is exactly the one we used for the bifurcat- ing real single cell data presented in the main paper, thus, for Figure 18 (p- = 1) in the Appendix. Hence, this topological loss function is used to optimize for a connected flare with at least three clusters away from the embedding center.
Figure 19 shows the topologically regularized PCA embeddings for these topological loss functions in order. While we observe small changes between the embeddings, which somewhat do agree with their respective designed topological loss function, in all cases, the embeddings do not strongly deviate from the true generating topological model, which is one (and only one) prominent circle.
Different Loss Functions for different Topological Priors (example for UMAP) In case of an orthogonal projection, which we encouraged in Figure 19 as we did in the main paper, it may be difficult provide an embedding that well captures nontrivial topological models such in Figure 18 when they are not truthfully present. However, non-linear dimensionality reduction methods such UMAP may be more prone model wrong prior topological information, as they directly optimize for the data point coordinates in the embedding space. To explore this, we considered an experiment where we embed the real bifurcating single cell data for a circular prior through the topological loss function -(d, by) evaluated on the Ist-dimensional persistence diagram. Thus, we topologically regularized the UMAP embedding of this data set for the exact same topological loss function main paper). The result of topological regularization, using the exact same hyperparameters that originally used for the bifurcating cell trajectory data set as summarized in Table T in the main paper, is shown in Figure 20a
originally used for the synthetic data lying on circle (see also Figure 4 in the
We observe that when the embedding optimization is ran for 100 epochs (as the embedding in the main paper), a cycle indeed starts to appear in the embedding. To further explore this, we increased the number of epochs to 1000, which did not increase the prominence of the cycle much
24

---

Published as a conference paper at ICLR 2022
100 epochs (with UMAP loss)
250 epochs (with UMAP loss!
1000 epochs (with UMAP loss)
10.0
10.0
500
5.
-25
-25
-5.0
-7.
(a) The topologically regularized UMAP embeddings.
100 epochs (without UMAP loss)
250 epochs (without UMAP loss)
1000 epochs (without UMAP loss)
10.0
20
75
755
50
10
25
00
0.
-25
5
-75
-7.
-15
-30
-10
(b) Topologically optimized embeddings initialized with ordinary UMAP embedding from main paper. Here, the UMAP loss function is not used during topological optimization.
Figure 20:
Topologically regularized and optimized UMAP embeddings of the bifurcating cell data, using potentially wrong prior topological (circular) information.
further (Figure20s) However, by omitting the UMAP loss during the same topological optimization procedure of the embedding, we observe that cycle becomes much more prominently present in the embedding (Figure 20b). Hence, inclusion of the structural UMAP embedding loss function through topological regularization prevents the cycle to become prominently and falsely represented the entire data, and the eycle remains spurious in the embedding.
Naturally, higher topological regularization strengths Atop will more significantly impact the topo- logical representation the data embedding. Thus, caution will still need to be maintained when no prior topological information is available at all. Figure 21 shows the topologically regularized UMAP embeddings for the circular prior for different topological regularization strengths Atop- Here, we again ran for 1000 epochs to explore long-ten bon-term effects of topological regularization during the optimization.
App
Apy 10.0
Asp
1000 epochs (with UMAP loss)
1000 epochs (with UMAP loss)
1000 epochs (with UMAP loss)
10.0
10.0
7.
75
10-
50
25
25
00
-25
-5.0
-5.0
-30
-10.0
-75
-5.0
-2.5
0.0
25
50
75
-75
-5.0
-2.5
00
25
500
75
-20
-10
20
30
Figure 21: Topologically regularized UMAP embeddings the bifurcating cell data, using poten- tially wrong prior topological (circular) information, for various topological regularization strengths Atop- For Acop = 10, the plot-whice is included for easy comparison- is identical to the right plot
in Figure 20a
25

---

Published as a conference paper at ICLR 2022
Aspp
5400
emibedtiing ni (with top. meg topological twith UNAF
5000
ennbediing 1015
5000
Impsoggral
8600
0400
6200
1000
opoch
Alop
ensbediinng ng (with top, reg)
5200
topological Ewith UNAFI
enbediing 10e5
8800
8000
6200
1000
opoch
Appp emsbeddd rg (with top. rep)
5000
topelogical twith UNAP)
embbddiing 1d55
5000
tapolggcc
0000
8600
800
opoch
Figure 22: Evolution of the UMAP embedding and topological loss functions during optimization of the topologically regularized embeddings according to the number of epochs, for various topo- logical regularization strengths Atop The regularization strengths are not factored in the plotted topological loss functions for easy comparison. Thus, the topological loss functions directly equal the persistence of the most prominent cycle in each embedding.
When multiplying the original regularization strength Atop = 10 with a factor of 10, we see that the circular prior becomes much more prominently present in the topologically regularized UMAP embedding (Aoop 100). For lower topological regularization strengths, the topological prior strug- gles to become prominently represented the embedded (for Atop even appears to have no long-term effect on the embedding at all (for Atop = 1). This can also be observed from Figure [22] where the embedding and topological loss functions are plotted accord- ing to the number of epochs for the different topological regularization strengths Atop. We observe that for Atop E {1, 10), the topological loss functions eventually increase again and stagnate. For Atop 100, the topological loss function appears to decrease indefinitely, at the cost of the embed- ding loss function which already for smaller numbers of epochs increases again.
as also Figure 20ah. or
Finally, for all three cases we see that the incorrectly specified topological prior is not naturally rep- resented by the data embedding (Figure 2T). For example, for \top = 100, the cycle is prominently present, but the majority of points remain clustered together and neglect the circular shape that aim to model through the topological loss function. This artefact of topological optimization as well the evolution of the embedding and topological loss functions (which are generally applica- ble to higher dimensional embeddings) may provide some visual feedback to the user that the bias to the topological prior may be weak or too strong. How these observations can be quantified, to validate the passed topological prior and tune hyperparameters such as the topological regularization strength in an automated manner, is open further research.
26


Reviews:
[{"review_id": "oSlY4L0RKC", "reviewer": "Reviewer_fHUg", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1.\tTopological loss is used to regulate low-dimensional embedding method for incorporating prior topological knowledge\n2.\tSeveral novel topological loss functions are presented including k-dimensional holes and flares. And the combinations of these basic losses can be applied. \n\n\nWeaknesses:\n1.\tIt seems that the loss (1) is an incremental formulation by combining existing low-dimensional embedding methods and the simplified topological loss function (2). From (3), the topological loss of this paper is constructed from the embeddings instead of the input data. However, this may be thought as a straightforward extension. \n2.\tAuthors did not explain why only the regular part of (2) is used. It looks like only partial power of the topological optimization is considered by this work. Some explanation for choosing only the regular part is needed.\n3.\tThe claim that “a topological model that is naturally present in the data should be represented well by many subsets of the data” is not quite convincing. Taking the clustering problem as an example, this claim might not true if there are many small clusters when uniform sampling is used. Since it Is the key assumption for (4), authors might want to specify the limitation of the loss (4). Even for the experiments using (4), the analysis on the impact of f_s and n_s is not studied. \n4.\tExperiments are conducted on both synthetic data and real data, but only the very basic approaches are compared. It is more like the ablation study of the proposed model. Authors need to compare the results obtained by the proposed model with the state-of-the-art methods. At least, the results from the paper using the same real data should be reported as the most relevant baselines. \n5.\tFrom the visualization results, it seems that top. optimization embedding is very similar to the top. regularized embedding on most of the data sets expect Figure 7. Does it mean top. loss is sufficient enough to obtain relatively good results?\n", "summary_of_the_paper": "Authors of this paper aim to integrating different prior topological knowledge into low-dimensional embeddings, where new set of topological losses are introduced as the topological regularizations to regulate embedding models. ", "summary_of_the_review": "Authors proposed to joint optimize low-dimensional embedding and topological loss, but the proposed method might be thought as a straightforward extension of existing work. The experiments lack the relevant methods for comparisons and the proposed method seems not significantly better than one of simple baselines from visual perspectives. Some claims need to be clarified in detail.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "lrM_JcVnfYP", "reviewer": "Reviewer_8muq", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Positive aspects of the paper:\n- The family of loss functions introduced is a novel contribution that can lead to practical applications in areas that can benefit from better representation embeddings, provided that knowledge about the data topology is available and that easier ways to translate this knowledge into the loss functions described became available.\n\n## Concerns and points for improvement:\n- Certain topics and mathematical concepts considered in the paper are not familiar to a large audience of the machine learning community. Also, the paper does a poor job in explaining those concepts and I believe many readers in this community will have a hard time understanding it in its present form, due to lack of background. The authors acknowledged this by adding Appendix A, but many points are not sufficiently detailed in there either.\n- Considering that acquiring knowledge about the data topology as well as translating this knowledge into an adequate loss function can both be difficult tasks, I would like to see a more thorough evaluation of how misleading the obtained can be if any of these steps are not performed adequately. \n", "summary_of_the_paper": "This paper proposes a topological regularization method for incorporating topological prior knowledge for shaping data embeddings. This is achieved by introducing a new family of loss functions based on the characteristics of persistence diagrams. The results of the empirical evaluation suggest that the embeddings produced with the proposed method better capture the topological aspects of input data, by taking into account the prior topological knowledge.", "summary_of_the_review": "In its present form, I believe the paper should be rejected due to the lack of background information necessary for a large part of ICLR's audience to understand the paper and its contributions. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ki_YGE-Vjiq", "reviewer": "Reviewer_c3ai", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: The paper tackles an important and challenging problem faced in dimensionality reduction. The proposed method is simple and justified by existing research. The empirical results demonstrate the method improves qualitative results and emphasise that topological optimisation of the embedding space need not enforce any sensible separation of the data, an important consideration. \n\nWeaknesses: The paper is hampered by a lack of notational clarity in essential sections that makes it difficult to determine the full contributions and impact of the proposed method. The following are questions and suggestions to improve the clarity and content of the paper:\n1) The methodology rests on equation (2) which demonstrates how topological information is used by the regularisation term, but the notation is difficult to parse.\n\na) Do the i and j indices refer to indices of the elements of the ordered persistence diagram? It appears that they do, but this could be emphasised. There appear to be two sets of indices: those that are grouped as essential and those termed regular. The ordering is important for the method, but dropping the inequalities and describing containment would help: k \\in D^ess, k \\in D^reg.\n\nb) Relatedly, the summations in equation (2) could be reconstructed. The first summation appears unnecessary, as it is effectively neutralised by setting g_ess(.) = 0 for the remainder of the paper. Also, what is an example of this summation that has more than one term? The single connected component the embedding tends to is the only term mentioned. This could be expanded.\n\nc) This is an essential point because the choice of j in the summations appears to be a choice point for the method: how deep into the persistence diagram should we go? Ephemeral components that appear for only one step contribute to the loss, but should they? If these components are treated as appearing and disappearing in the same step, then with the chosen g_reg(.) function, they contribute nothing to the loss and could be excluded from the summation. \n\nd) The choice of j and choice of g_reg will be crucial to the results, but the default choices are not compared with alternatives either in section (2) or in the results. How sensitive is the method to changes in these selections?\n\ne) What is |D|? How is it determined? This is the number of points in the persistence diagram, but this should be expanded upon. Specifically, the discussion in the caption of Figure 1 should be moved to the main text and the terminology used there of (H0) and (H1) could be used to improve the clarity of subsequent sections (Section 2.2 par 1 line 3 refers to the 0-dimensional persistence diagram).\n\n2) What is the complexity of the method and how does it scale with the number of data points and type of persistence diagram? In an iterated procedure, is it the case that the digram must be updated with each update of the embedding?\n\n3) As conceded by the authors, the prior topological information is vital to the method, but it is unclear how it is discovered. Thus, it would be useful to see how the method behaves under situations where the prior information is misspecified, this could be included with the synthetic data experiments.\n\nMinor points:\n1) Motivation par 1 sentence starting ‘In other examples…’: this sentence seems to contradict itself and should be justified.\n2) Additional editing could improve clarity and make space for the expanded methodology section. ", "summary_of_the_paper": "The paper argues for including prior topological information about the structure between data points in some lower dimensional embedding space with the intention of improving the quality of the embeddings produced by tasks such as dimensionality reduction. The paper accomplishes this by adding a novel topological regularisation term to the standard embedding loss. The topological regularisation term incorporates the persistent homology of filtrations of the embedded data points. How this information is manipulated within the term encodes the prior knowledge the investigator wishes to use, such as the embedding should comprise a single cycle. The paper supports its method an array of qualitative and quantitative analyses on synthetic and real datasets. ", "summary_of_the_review": "As the paper stands, I suggest rejection. The method is interesting and I find the empirical results promising, but the methodology sections need large amounts of reworking to improve clarity and to fully justify and explain the choices made by the authors. The paper would benefit greatly from these changes.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JN-eR2gQ6gP", "reviewer": "Reviewer_ey6b", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper develops a way to construct low-dimensional embeddings that combine an embedding cost (e.g. PCA, t-SNE, UMAP, etc.) with the topological cost, where the latter forces the embedding to have a particular topological structure as represented by the persistent homology. As an example, one can construct a data embedding and force it to be a circle, or a figure-8, or have three clusters.\n\nThe paper is based on a series of several 2020-2021 papers, with which I am unfamiliar, so it was difficult for me to judge on the novelty. I found the paper interesting, and the method seems to work well. My biggest criticism is that the goal of the method appears somewhat artificial: low-dimensional embeddings are typically done for data exploration, but one does not want to enforce any particular structure for the purposes of data exploration, and the topological structure is typically not known a priori. That's why I am giving a borderline score.\n\nMost of my comments below are relatively minor requests for clarification.\n\nMAJOR ISSUES\n\n* All considered datasets are very small. Add some discussion or benchmarks of how the runtime scales with dataset size.\n\n* Related work subsection in the Introduction should explain what exactly is the novelty in this paper, compared to Gabrielsson2020, Solomon2021, Carriere2021.\n\n\nMEDIUM/MINOR ISSUES\n\n* I like Figure 1 and appreciate that the authors attempted to explain persistent homology in the main text. However, I think it could be made clearer. The following things could be briefly explained/mentioned in the text:\n\na) Panel A -- this looks like kNN graph for various values of k (perhaps alpha=k). I think it's not a kNN graph, but mention something about it.\n\nb) Panel A -- what gets filled in green? All triangles?\n\nc) Panel B -- should we see 4 clusters corresponding to the letters I,C,L,R? Where are they on the persistent homology? Maybe highlight them somehow.\n\nd) Panel B -- what are some prominent points on this plot? One triangle at death=200? A cluster of triangles in the upper-right corner? Would it make sense to annotate them?\n\ne) Panel B -- maybe it should be on the log-scale? Currently many points are clumped in the low-left.\n\n* Related: would it make sense to have some notation for k-dimensional persistence diagram? Like D_{(k)} or something. I was very confused, until I finally realized that there are several different D's. At least clearly mention on page 3 that there is one separate D object for each dimension up to the space dimensionality minus 1.\n\n* Page 3, \"these parameters are entire point clouds X\" -- should it be X or E? I think E. \n\n* Page 4: it isn't very clear how to set i,j,mu to achieve a desired result. It slowly becomes more clear as one reads further, but it could be great to explain it from the get go. Perhaps even show in Figure 2 what happens for different choices of i? E.g. can one have 4 clusters?\n\n* Particularly unclear is when mu should be 1 and when it should be -1.\n\n* Page 4: If i=j=2, mu=-1 enforces 2 clusters, then why does i=2,j=inf,mu=1 in the example above enforces 1 cluster?\n\n* Page 5, top line: what is n_S? Wasn't defined.\n\n* Section on \"flares\" -- define \"flare\".\n\n* Eq (6): very confusing notation in g_E : E -> R : x |-> ||...||\n\n* Figure 3 -- panel (c) looks good but actually the topological loss would be equally happy with any arbitrary splitting of points in two clusters. So the fact that blue points are separated from orange points in panel (c) has nothing to do with the topological loss... this makes this figure and the surrounding text somewhat misleading.\n\n* Page 6: \"better captures the circular hole (with L_\\bot(W)...\" -- but L_\\bot has nothing to do with holes, it's the orthogonality term. Should it be L_top? The same confusion appears several times in sections 3.1 and 3.2.\n\n* Section 3.2, 1st dataset -- if it's data on cell differentiation, then why should it be a circle?\n\n* Page 7, Figure 7b: why does Fig 7b look like it does? The topological loss enforces single cluster but here we see multiple clusters. That's confusing.\n\n* Harry Potter dataset should be mentioned in the main text, in Section 3.2.\n\n* Page 9: \"we repeated this entire experiment 100 times\" -- unclear where the variance comes from.\n\n* Page 9: \"we observe that topological regularization consistently...\" -- looking at Table 4, the difference between ordinary embedding and topological regularization is much smaller than the standard deviation over repetitions, for three out of four datasets. I think this should be acknowledged in the text.\n\n* Delaunay is consistently spelled wrong.", "summary_of_the_paper": "The paper develops a way to construct low-dimensional embeddings that combine an embedding cost (e.g. PCA, t-SNE, UMAP, etc.) with the topological cost, where the latter forces the embedding to have a particular topological structure as represented by the persistent homology. As an example, one can construct a data embedding and force it to be a circle, or a figure-8, or have three clusters.\n\nThe paper is based on a series of several 2020-2021 papers, with which I am unfamiliar, so it was difficult for me to judge on the novelty. I found the paper interesting, and the method seems to work well. My biggest criticism is that the goal of the method appears somewhat artificial: low-dimensional embeddings are typically done for data exploration, but one does not want to enforce any particular structure for the purposes of data exploration, and the topological structure is typically not known a priori. That's why I am giving a borderline score.", "summary_of_the_review": "The paper is based on a series of several 2020-2021 papers, with which I am unfamiliar, so it was difficult for me to judge on the novelty. I found the paper interesting, and the method seems to work well. My biggest criticism is that the goal of the method appears somewhat artificial: low-dimensional embeddings are typically done for data exploration, but one does not want to enforce any particular structure for the purposes of data exploration, and the topological structure is typically not known a priori. That's why I am giving a borderline score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes loss functions to encode topological priors during data embedding, based on persistence diagram constructions from computational topology.  The paper initially had some expositional issues and technical questions, but the authors did an exceptional job of addressing them during the rebuttal period----nearly all reviewers raised their scores (or intended to but didn't update the numbers on their original reviews).

The AC is willing to overlook some of the remaining questions. For example, concerns that topology isn't well known in the ICLR community (8muq) are partially addressed by the improved exposition (and it's OK to have technically sophisticated papers so long as some reviewers were able to evaluate them).  And, future work can address scalability of the algorithm, which indeed does seem to be a challenge here (ey6b).

In the final "camera ready," the authors are encouraged to address any remaining comments and to consider adding experiments/discussion regarding scalability to larger datasets.
Decision: Accept (Poster)