Topological Autoencoders
Authors: Michael Moor
Max Horn
Bastian Rieck
Karsten Borgwardt
Venue:  (2020)
Keywords: Topology
Deep Learning
Autoencoders
Persistent Homology
Representation Learning
Dimensionality Reduction
Topological Machine Learning
Topological Data Analysis

Abstract: We propose a novel approach for preserving topological structures of the input space in latent representations of autoencoders. Using persistent homology, a technique from topological data analysis, we calculate topological signatures of both the input and latent space to derive a topological loss term. Under weak theoretical assumptions, we can construct this loss in a differentiable manner, such that the encoding learns to retain multi-scale connectivity information. 
We show that our approach is theoretically well-founded and that it exhibits favourable latent representations on a synthetic manifold as well as on real-world image data sets, while preserving low reconstruction errors.

Under review as a conference paper at ICLR 2020
TOPOLOGICAL AUTOENCODERS
Anonymous authors Paper under double-blind review
ABSTRACT
We propose novel approach for preserving topological structures of the input space in latent representations of autoencoders. Using persistent homology, a technique from topological data analysis, we calculate topological signatures of both the input and latent space to derive a topological loss term. Under weak theoretical assumptions, we can construct this loss in a differentiable manner, such that the encoding learns to retain multi-scale connectivity information. We show that our approach is theoretically well-founded and that exhibits favourable latent representations synthetic manifold as well real- woaldw image data sets, while preserving low reconstruction errors.
INTRODUCTION
While topological features, in particular multi-scale features derived from persistent homology, have seen increasing usage in the machine learning community (Carrière et al. 2019 Guss &
Salakhutdinov 2018 Hofer et al. 2017 [2019]|]] Ramamurthy et al. 2019 Reininghaus et al. [015] Rieck al. 2019a b). using topology directly constraint for current deep learning methods remains a challenge. This is due to the inherently discrete nature of these computations, making
backpropagation through the computation of topological signatures immensely difficult or only
possible in certain special circumstances (Chen et al. 2019 Hofer et al. 2019b Poulenard et al.
2018
In this work, we present novel approach that permits obtaining gradients during the computation of topological signatures. This permits employing topological constraints while training deep neural networks as well as building topology-preseee
autoencoders based on the following contributions:
1. We develop a novel topological loss term for autoeneoders that helps harmonise the topology of the data space and the topology of the latent space.
2. We prove that our approach stable on the level of mini-batches, resulting in suitable approximations of the persistent homology of data set.
3. We empirically demonstrate that our novel loss term aids in dimensionality reduction by preserving topological structures in data sets; in particular, the learned latent representations are useful in that the preservation of topological structures can aid interpretability.
2 BACKGROUND: PERSISTENT HOMOLOGY
Edelsbrunner & Harer 2008) is a method from the field of computational topology, which develops tools for analysing topological features (connectivity- based features such as connected components) of data sets. We first need to introduce the underlying concept of simplicial homology. For simplicial complex R. i.c. a generalised graph with higher-order connectivity information such as cliques, simplicial homology employs matrix reduction algorithms to assign ń family of groups, the homology groups. The dh homology group ( of Å contains d-dimensional topological features, such as connected components (d = 0), cycles/tunnels (d = 1). and voids (d = 2). Homology groups are typically summarised by their ranks, thereby obtaining a simple invariant "signature" of a manifold. For example, a circle in IR" has one feature with d = 1 (a cycle), and one feature with = (a connected component). In practice, the underlying manifold IM is unknown and we are working with point cloud X := {II...., Fn) S Rd and metric dist: X x X + R such as the Euclidean distance. Persistent homology extends simplicial homology to this setting: instead of approximating IM by means of single simplicial complex, which would
Persistent homology (Barannikoy) 1994

---

Under review as a conference paper at ICLR 2020
(a)
(b)
(c)
(d) D3
Figure 1: The Vietoris-Rii complex R. (X) of a point cloud X at different scales eo. c1 and 62. As the distance threshold increases, the connectivity changes. The creation and destruction of d-dimensional topological features is recorded in the th persistence diagram Da.
be unstable procedure due the discrete nature of X, persistent homology tracks changes in the homology groups over multiple scales of the metric. This is achieved by constructing a special simplicial complex, the Vietoris-Rips complex (Vietoris 1927). For 0 < oc, the Vietoris-Rips complex of X at scale e, denoted by Rt RX(X) (X), contains all simplices (i.e. subsets) of X whose elements {zo, .I.... } satisfy dist [z,, x2) < e for all i, j. Given matrix Aof pairwise distances of a point cloud X, we will use (A) and R. (X) interchangeably because constructing R, only requires distances. Vietoris-Rips complexes satisfy nesting relation, i.e. R,,()) C (X) for 6, S 6 making it possible to track changes in the homology groups as increases (Edelsbrunner et al.) 2002). Figure [ illlstrrae this process. Since X contains finite number of points, a maximum value exists for which the connectivity stabilises; therefore, calculating Ri is sufficient to obtain topological features at all scales.
We write (H)))())) for the persistent homology calculation of the Vietoris complex. It results in a tuple (fD1, .). [T1, pairings (2 component). The d-dimensional persistence diagram Da (Figure Id of (X) contains coordinates the form (a, b). where a refers to a threshold c at which a d-dimensional topological feature is created in the Vietoris-Rips complex, and b refers to threshold c' at which it is destroyed.
.) of persistence diagrams (1 component) and persistence
When d = 0, for example, the threshold indicates at which distance two connected components in X merged into one; this is related spanning trees (Kurlin 2015). The d-dimensional persistence pairing contains indices (i,.7) corresponding to simplices 8,.8, 8, E RX) that create and destroy the topological feature identified by (a, Da. respectively. Persistence diagrams are known to be stable with respect to small perturbations in the data set (Cohen- Steiner et al. 2007). Two diagrams inf,: D-DD' suP=E p || n)(=)])>. where 17: D - D'' denotes bijection between the points of the two diagrams, and ||- ol refers the Lox norm. We use D-X to refer to the of persistence diagrams of a point cloud X arising from (X)).
and D' can be compared using the bottleneck distance dp
3 PROPOSED METHOD
We propose generic framework for constraining autoencoders to preserve topological struc- tures (measured via persistent homology) of the data space in their latent encodings.
3.1 VIETORIS- RIPS COMPLEX CALCULATION
Given finite metric space S, we first calculate the persistent homology of the Pestoris-Ripa complex of its distance matrix AS. Typically, the usual Euclidean distance used calculate A but both the persistent homology calculation and our method are not restricted to any particular distance; previous research WWagner& & Dlotko 2014) shows that even similarity measures that do not satisfy the properties of metric can be used successfully with PH(.). Subsequently, let < := max A so that R. (A*) is the corresponding Vietoris-Rips complex as described in Section Given a maximum dimension of d IN obtain set of persistence diagrams DS and of persistence pairings S The th persistence pairing - contains indices of simplices that are relevant for creating and
'This means that we do not have consider higher-dimensional topological features, making the calculation efficient.
2

---

Under review as a conference paper at ICLR 2020
destroying d-dimensional topological features. We can consider each pairing represent edge indices, namely the edges that are deemed to be "topologically relevant" by the computation of persistent homology (see below for more details). This works because the Vietoris-Ripp complex is a clique complex, i.e. it is fully determined by its edges (Zomorodian, 2010).
For O-dimensional topological features, it is sufficient to look at the edge indices, i.e. the indices of "destroyer" simplices, contained in To. Each of these indices corresponds to an edge in the minimum spanning tree of the data set. This calculation is computationally efficient, having worst-case complexity of O(m² a (m²), where m is the batch size and ar-) denotes the extremely slow-growing inverse Ackermann function (Cormen et al. 2009 Chapter 22). For 1-dimensional features. where edges are paired with triangles, we obtain edge indicss by selecting the edge with the maximum weight of the triangle. While this procedure (and thus our method) generalises to higher dimensions, our current implementation supports no nigher-dimensional features. Since preliminary experiments showed that including 1 1-dimensional topological features merely increases runtime, we will focus only on O-dimensional persistence diagrams in the subsequent experiments. We thus use (DS, S)
to denote the O-dimensional persistence diagram and pairing of S, respectively.
3.2 TOPOLOGICAL AUTOENCODER
In the following, we consider mini-batch X of size from the data space X' point cloud. Furthermore, we define an autoencoder as the composition of two functions h where g: X - Z represents the encoder and h: Z + X' represents the decoder. We denote latent codes with Z := 9X).. During a forward pass of the autoencoder, we compute the persistent homology of the mini-batch in both the data as well as the latent space, yielding two sets of tuples, i.e. (Dx ) := PH(R, (X)) and (D² >) := (H, (Z)). The values of the persistence diagram can be retrieved by subsetting the distance matrix with the indices provided by the persistence pairings; to indicate that the diagram, which is a set, contains the same information
we write xx = A [xx]]
as the distances we retrieve with the pairing. We treat A [ as a vector in R!**), Informally speaking, the persistent homology calculation can thus be seen selection of topologically relevant edges of the Vietoris-Rips complex, followed by the selection of corresponding entries in the distance matrix. By comparing both diagrams, L. = L, Axx AZ, T x),, which we add to the reconstruction loss of an autoencoder, i.e.
construct topological regularisation term
C: (X, + +XC,
where À E is parameter to control the strength of the regularisation. Next, we discuss how to specify L: in our case, the PH calculation represents a selection of topologically relevant distances from the distance matrix. Each persistence diagram entry corresponds to a distance between two data points. We assume that the distances neighbourhood that only contains a single point. Given this fixed pairing and a differentiable distance function, the persistence diagram entries thus also differentiable with respect to the encoder parameter. Hence, the persistence pairing does not change upon a small perturbation of the underlying distances, thereby guaranteeing the existence of the derivative of our loss function. This, in turn, permits the calculation of gradients for backpropagation.
unique so that each entry in the diagram has an infinitesimal
A straightforward approach to impose the data space topology the latent space would be to directly calculate a loss based on the selected distances in both spaces. Such an approach will not result in informative gradients for the autoencoder, as merely compares topological features without matching the edges between (X)) and R. (Z). A cleaner approach would be to enforce similarity on the intersection of the selected edges in both complexes. However, this would initially include very few edges, preventing efficient training and leading to very biased estimates of the topological alignments between the s To overcome this, we account for the union of all selected edges in X and Z. Our topological loss term decomposes into two components, each
We use the term "matching" only to build intuition. Our approach does not calculate matching in the sense of bottleneck Wasserstein distance between persistence diagrams.
'When initialising a random latent space Z, the persistence pairing in the latent space will select random edges, resulting in only expected matched edge (independent of mini-batch size) between the two pairings. Thus, only one edge (referring to one pairwise distance hetween two latent codes) could he used to update the encoding of these two data points.
3

---

Under review as a conference paper at ICLR 2020
handling the "directed" loss occurring topological features in one of the two spaces remain fixed. Hence, Lt = xx +
-2 where
Lx~ 1 21
11 -
A
and Lz-x:= == A क
1
A 1 11
respectively. The key idea for both terms is to align and preserve topologically relevant distances from both spaces. By taking the union of all selected edges (and the corresponding distances), obtain an informative loss term that is determined by at least X distances. This loss can be seen as more generic version of the loss introduced by Hofer et al. (2019b). whose formulation does not take the two directed components into account and optimises the destruction values of all persistence tuples with respect to a uniform parameter (see also Section 4 for a brief discussion). By contrast, our formulation aims to to align the distances between X and 2 (which in turn will lead to an alignment of distances between X' and 2). If they are aligned perfectly, Lx = Lz- = because both pairings and their corresponding distances coincide. The converse implication is not true: if L. 0, persistence pairings (and their corresponding persistence diagrams) are not necessarily identical.
Letting A refer to the parameters of the encoder, we have
① Lx-2= 30 00
0Aa [
A
1
A
(A
[T
A²
A
(3)
2
00
SA [T
[=
-A
[T<]
(4)
00
where | denotes the cardinality of persistence pairing and A 7 refers to the zD entry of the vector of paired distances. This derivation works analogously for Lz-x (with π being replaced by x Furthermore, any derivative of A with respect to l must vanish because the distances of the input samples do not depend the encoding by definition.
These equations presume infinitesimal perturbations. In fact, the persistence diagrams change in a non-differentiable manner during the training phase but for given update step, a diagram robust to infinitesimal changes of its entries (Cohen-Steiner et al.] (007). As a consequence, our topological loss is differentiable for each update step during training. We make our code publicly available
3.3 STABILITY
With persistence diagrams being stable under small perturbations of the underlying space (Cohen Steiner et al. 2007). still have analyse our topological approximation the level of mini- batches. The following theorem guarantees that subsampled persistence diagrams are close to the persistence diagrams of the original point cloud.
Theorem 1. Let X be a point cloud of cardinality n and (m) be one subsample of X of cardinality m, i.e. X ((m) C X, sampled without replacement. We can bound the probability of the persistence diagrams of X (m) exceeding a threshold in terms of the bottleneck distance as
IP (d (Dx, D (DX(()))>)) >>)> s (m) >2e).
(5)
where du refers to the Hausdorff distance between the point cloud and its subsample.
Proof. See Section A.l in the supplementary materials.
For m > n, we have limm-on dh (X, (m)) = 0. Please refer to Section A.2 for an analysis of empirical convergence rates well discussion of worst-case bound. Given certain independence assumptions, the next theorem approximates the expected value of the Hausdorff distance. The calculation of exact representation is beyond the scope of this work, though.
otte http://wwwwoeeooooooaaoooaaeaaaa Ba
4

---

Under review as a conference paper at ICLR 2020
Theorem 2. Let E R be the distance matrix between samples of X and X(m), where the rows are sorted such that the first m rows correspond to the columns of the m subsampled points with random samples following
diagonal elements ag = 0. Assume that the entries Oij with i > a distance distribution FD with (fp)(fD) E R20- The minimal distances óg for rows with >> m follow distribution Fa- Letting 7. maxiçisu 6g with a corresponding distribution Fz, the expected Hausdorff distance between X and X (m)) for m < n is bounded by:
+o0 E dx, -Ez-Fy 12] 12| (1
to0
d2 < Fb(z)(m11)
( FD(2) (m(=)))(==m)) dz (6)
Proof. See Section
A.3 in the supplementary materials.
we obtain Eldn( xx)] 0 as m + n, so the expected value converges as the subsample size approaches the total sample size We conclude that our subsampling approach results in point clouds that are suitable proxies for the aarge-scale topological structures of the point cloud X.
From Eq. 6
4 RELATED WORK
Computational topology and persistent homology (PH) have started gaining traction in several areas of machine learning research. PH is often used as as post hoc method for analysing topological characteristics of data sets. Thus, there several methods that compare topological features of high-dimensional spaces with different embeddings to assess the fidelity and quality of a specific
embedding scheme (Khrulkov & Oseledets 2018 Paul & Chalup 2017 Rieck & Leitte 2015 2017; Yan et al. 2018). PH can also be used to characterise the training of neural networks (Guss & Salakhutdinov 2018 Rieck et al. 2019b), as well as their decision boundaries (Ramamurthy et al. 2019). Our method differs from all these publications in that we are able to obtain gradient information to update model while training. Alternatively, topological features can be integrated into classifiers to improve classification performance. |Hofer et al. (2017) propose neural network layer that learns projections of persistence diagrams, which can subsequently be used as feature descriptors to classify structured data. Morcover, several vectorisation strategies for persistence diagrams exist (Adams et al. 2017 Carrière et al. 2015), making possible to use them in kernel- based classifiers. These strategies have been subsumed (Carrière et al. 2019) in a novel architecture based on deep sets. The commonality of these approaches is that they treat persistence diagrams as being fixed; while they capable of learning suitable parameters for classifying them, they cannot adjust input data to better approximate a certain topology. Such topology-based adjustments have only recently become feasible. [Poulenard et al. (2018) demonstrated how optimise real-valued functions based on their topology. This constitutes the first approach for aligning persistence diagrams by modifying input data; requires the connectivity of the data to be known, and the optimised functions have to be based and scalar-valued. By contrast, our method works directly on distances and sidesteps connectivity calculations via the Vietoris-Rij complex. [Cen al. (2019) use a similar optimisation technique to regularise the decision boundary of classifier. However, this requires discretising the space, which can be computationally expensive. Hofer et al. (2019b), the closest work to ours, also presents differentiable loss term. They propose regularising the connectivity of the latent space by itself. Specifically, their formulation enforces a single scale on the latent space. The learned encoding is then applied to a classification task. By contrast, our directed loss term aims to preserve the data space topology in the latent space for dimensionality reduction.
5 EXPERIMENTS
Our main task is to learn a latent space in an unsupervised manner such that topological features of the data space measured using persistent homology approximations on every batch are preserved as much as possible.
For m n, the integrals switch their order m(n - m) < 1foor 1).
5

---

Under review as a conference paper at ICLR 2020
(a) PCA
(b) Isomap
(c) t-NN
(d) UMAP
(e) AE
(i) TopoAE
Figure Latent representations of the SPHERES data set. Only our method is capable of representing the complicated nesting relationship inherent to the data. TopoAE used a batch-size of 28. See Figure A.2 the supplementary materials for an enlarged version.
5.1 EXPERIMENTAL SETUP
Data sets We use SPHERES data set that consists of ten high-dimensiona 100-spheres living in 101 101-dimensional space that are enclosed by one larger sphere that consists the same number of points the total of inner spheres (please refer to Section A.4 3.4gr for more details). We also use three image data sets (MNIST,
and CIFAR I0), which are particularly amenable to topology-basee -base analysis because real-world images are known to lie near low-dimensional manifolds (Lee et al. 2003 Peyré 2009).
Baselines & Training We compare approach with several dimensionality reduction techniques, including UMAP (McInnes et al. 2018). t-SNE (van der Maaten & Hinton 2008). Isomap (Tenen baum al. 2000). PCA, well as standard autoencoders (AE). We apply proposed topological constraint to this standard autoencoder architecture (TopoAE). For comparability and interpretability. each method is restricted to two latent dimensions. We split each data into training and test- ing (using the predefined split if available; 90% versus 10% otherwise). Additionally, we remove 15% of the training split validation data set for tuning the hyperparameters. We normalised our topological loss term by the batch size in order to disentangle À from it. All autoencoders employ batch-nore norm and are optimized using ADAM (Kingma Ba 2014). Since t-SNE is not intended to be applied applying to previously unseen test samples, we evaluate this method only on the train split. In addition, significant computational scaling issues forced us to forgo running a hyperparameter search for Isomap on real-world data sets, so we only compare this algorithm on the synthetic data set. Please refer to Section A.5 for more details on architectures and hyperparameters.
Evaluation We evaluate the quality of latent representations in terms of (1) low-dimensional visu- alisations, (2) dimensionality reduction quality metrics (evaluated between input data and latent codes), and (3) reconstruction errors (Data MSE; evaluated between input and reconstructed data), provided that invertible transformations are available For (2), we consider several measures (please refer to Section A.6 for more details). First, we calculate KL,, the Kullback-Leibler divergence between the density estimates of the input and latent space, based on density estimates (Chazal et al.) Ry00 denotes the length scale of the Gaussian kernel, which is varied to account for multiple data scales. We chose minimising KLo.1 as our hyperparameter search objective. Furthermore, we calculate common non-lineat dimensionality reduction (NLDR) quality metrics, which use the pairwise distance matrices of the input and the latent space (as indicated by the "g" in the abbreviations), namely the root mean square error (E-MMSE), which despite its name is not
2011: 2014b). where
'nvertibll transformations available for PCA and all autoencoder-han hased methods.

---

Under review as a conference paper at ICLR 2020
(a) PCA
(b) I-SNE
(c) UMAP
(d) AE
(e) TopoAE
PC
(g) I-SNE
(h) UMAP
Ai)EE
i TopoAE
(k) PCA
(I) t-SNE
(m) UMAP
(n) AE
(0) TopoAE
Figure Latent representations of the FASHION- (top row), MNIST (middle row), CIFAR-10 (bottom row) data sets. TopoAE batch-sizes (same data set order): (95, 126, 82). Please
refer to Figures A.3 A.4 and A.5 in the supplementary materials for enlarged versions.
related to the reconstruction error of the autoencoder but merely measures to what extent the two distributions of distances coincide, the mean relative rank error (fMMRRE), the continuity (L-Cont), and the trustworthiness (L-Trust). The reported measures are computed on the testing splits (except for t-SNE where no transformation between splits is available, so we report the measures on random subsample of the train split).
5.2 RESULTS
Quantitative Results Table repport the quantitative results. Overall, we observe that our method shines in preserving the data density over multiple length scales (as measured by KT.). Furthermore, we find that TopoAF. displays competitive continuity values (f-Cont) and reconstruction errors (Data MSE). The remaining classical measures favour the baselines (foremost the train (!) performance of (-SNE). However, we will subsequently see that those classic measures fail at detecting the relevant structural information, as exemplified with known ground truth manifolds, such as the SPHERES data set.
Visualisation of latent spaces For the SPHERES data set (Figure method is capable of assessing the nesting relationship of the high-dimensional spheres correctly. By contrast, t-SNE "cuts open" the enclosing sphere, distributing most of its points around the remaining spheres. We see that the KL-divergence confirms the visual assessment that only our proposed method preserves the relevant structure of this dataset. Several classical evaluation measures, however, favour (-SNE, even though this method fails to capture the global structure and nesting relationship of the enclosing sphere manifold accounting for half of the dataset. On FASHION-MN -NIST (Figure (e) we see that, opposed to AE, which is purely driven by the reconstruction error, our method has the additional objective of preserving structure. Here, this constraint helps the autoencoder to "organise" the latent space, resulting in comparable pattern as in UMAP, which is also topologically motivated. Furthermore, we observe that t-SNE tends to fragment certain classes (dark orange, red) into multiple distinct subgroups. This is very likely not to reflect the underlying manifold structure, but constitutes an artefact frequently observed with this method. For MNIST, the latent embeddings (Figure 33 demonstrate that the non-linear competitors-mant by pulling apart distinct classes- some
observe that only
7

---

Under review as a conference paper at ICLR 2020
Table Multiple evaluation metries (Section 5.1
The hyperparameters all tunable methods were selected to minimise the objective KL..1. The winner is shown in bold and underlined, the runner-up in bold. Please refer Supplementary Table A.2 for more a scales and variance estimates.
Data set
Method
KLo.01
KLo.1
KL1
{-MRRE &-Cont E-Trust &-RMSE Data MSE
Isomap
0.181
0.420 0.00881
0.246
0.790
0.676
10.4
PCA
0.332
0.651 0.01530
0.294
0.747
0.626
11.8
0.9610
TSNE
0.152
0.527 0.01271
0.217
0.773
0.679
8.1
SPHERES
UMAP
0.157
0.613 0.01658
0.250
0.752
0.635
9.3
AE
0.566
0.746 0.016644
0.349
0.607
0.588
13.3
0.8155
TopoAE
0.085
0.326 0.00694
0.272
0.822
0.658
13.5
0.8681
PCA
0.356
0.052 0.00069
0.057
0.968
0.917
9.1
0.1844
TSNE
0.405
0.071 0.00198
0.020
0.967
0.974
41.3
F-MNIST UMAP
0.424
0.065 0.00163
0.029
0.981
0.959
13.7
AE
0.478
0.068 0.00125
0.026
0.968
0.974
20.7
0.1020
TopoAE
0.392
0.054 0.00100
0.032
0.980
0.956
20.5
0.1207
PCA
0.389
0.163 0.00160
0.166
0.901
0.745
13.2
0.2227
TSNE
0.277
0.133 0.00214
0.040
0.921
0.946
22.9
MNIST
UMAP
0.321
0.146 0.00234
0.051
0.940
0.938
14.6
AE
0.620
0.155 0.00156
0.058
0.913
0.937
18.2
0.1373
TopoAE
0.341
0.110 0.00114
0.056
0.932
0.928
19.6
0.1388
PCA
0.591
0.020 0.00023
0.119
0.931
0.821
17.7
0.1482
TSNE
0.627
0.030 0.00073
0.103
0.903
0.863
25.6
CIFAR
UMAP
0.617
0.026 0.00050
0.127
0.920
0.817
33.6
AE
0.668
0.035 0.00062
0.132
0.851
0.864
36.3
0.1403
TopoAE
0.556
0.019 0.00031
0.108
0.927
0.845
37.9
0.1398
of the relationship information berween clusters when comparing against proposed method or PCA. Finally, we observe that CIFAR-I0 10 (Figure 3k is challenging to embed in two latent dimensions in purely unsupervised manner. Interestingly y, method (repeatedly) identified linear substructure separating the latent space in two additional groups of classes.
DISCUSSION AND CONCLUSIONS
We presented topological autoencoders, a novel method for preserving topological information, measured in terms of persistent homology, of the input space when learning latent representations with deep neural networks. Under weak theoretical assumptions, we showed how our persistent homology (PH) calculations approximating PH on the level of mini-batches is theoretically justified.
be combined with backpropagation; moreover, proved that
In our experiments, we observed that method uniquely able capture spatial relationships between nested high-dimensional spheres. This is relevant, as the ability to cope with several manifolds in the domain of manifold learning still remains challenging task. On real-world data sets, we observed that our topological loss leads to competitive performance in terms of numerous quality metrics (such as a density preservation metric), while not adversely affecting the reconstruction emror In both synthetic and real-world data sets, we obtain interesting representations, as our method does not merely pull apart different classes, but tries to spatially arrange them meaningfully. Thus, do not observe mere distinct "clouds", but rather entangled structures, which consider to constitute a more meaningful representation of the underlying manifolds (an auxiliary analysis in Supplementary Section A.9 confirms that method influences topological features, measured using PH, in a beneficial manner).
Our topological loss formulation is highly generie; it only requires the existence of distance matrix between individual samples (either globally, or on the level of batches). As a consequence, our topological loss term be directly integrated into variety of different architectures and is not
8

---

Under review as a conference paper at ICLR 2020
limited to standard autoencoders. For instance, can also apply constraint to variational setups (see Figure A.7 for a sketch).
Employing generic constraint to more involved architectures will be exciting route for future work. One issue with the calculation is that, given the computational complexity of calculating H. (²).), for higher-dimensional features would scale progressively worse with increasing batch size. However, in our oowddimensional setup, we observed that runtime tends to grow with decreasing batch-size, i.e. the mini-batch speed-up still dominates runtime (for more details concerning the effect of batch sizes, see Supplementary Section (a.ciionA..).................... In future work, scaling to higher dimensions could be mitigated by approximating the calculation of persistent homology (Choudhary et
2018 Kerber Sharathkumar 2013), [Sheehy| (2013) or by exploiting recent advances in parallelising it (Bauer et al.
2014 Lewis Morozov 2015).
REFERENCES
Henry Adams, Tegan Emerson, Michael Kirby. Rachel Neville, Chris Peterson, Patrick Shipman, Sofya Chepushtanova, Eric Hanson, Francis Motta, and Lori Ziegelmeier. Persistence images: A stable vector representation of persistent homology. Journal of Machine Learning Research, 18(1):
218-252, 2017.
Serguei A. Barannikov. The framed Morse complex and its invariants. Advances Soviet Mathemat- ics, 21:93-115, 1994.
Ulrich Bauer, Michael Kerber, and Jan Reininghaus, Distributed computation of persistent homology. In Catherine C. McGeoch and Ulrich Meyer (eds.), Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 31 31-38. Society for Industrial and Applied Mathematics, 2014.
Adrien Bibal and Benoît Frénay. Measuring quality and interpretability of dimensionality reduction visualizations. Safe Machine Learning Workshop at ICLR, 2019.
Dmitri Burago, Yuri Burago, and Sergei Ivanov. course in metric geometry, volume 33 of Graduate Studies in Mathematics. American Mathematical Society, 2001.
Mathieu Carrière, Steve Y. Oudot, and Maks Ovsjanikov. Stable topological signatures for points on 3D shapes. Proceedings of the Eurographics Symposium on Geometry Processing (SGP), pp. 1-12, Aire-la-illle, Switzerland, 2015. Eurographics Association.
Mathieu Carrière, Frédéric Chazal, Yuichi Ike, Théo Lacombe, Martin Royer, and Yuhei Umeda. A general neural network architecture for persistence diagrams and graph classification. arXiv e-prints, art, 190400999009778.. 2019.
Frédéric Chazal, David Cohen-Steiner, Leonidas J. Guibas, Facundo Mémoli, and Steve Y. Oudot. Gromov-Hausdorff stable signatures for shapes using persistence. Computer Graphics Forum, 28 (5):1393-1403, 2009.
Frédéric Chazal, David measures, Foundations of Computational Mathematics, 116):733-751, 2011.
and Quentin Mérigot. Geometric inference for probability
Frédéric Chazal, Vin de Silva, and Steve Y. Oudot. Persistence stability for geometric complexes. Geometria Dedicata. 173(1):193-21) 2014a.
Frédéric Chazal, Brittany T. Fasy, Fabrizio Lecci, Bertrand Michel, Alessandro Rinaldo, and Larry Wasserman. Robust topological inference: Distance to a measure and kernel distance. arXiv e-prints, art. 1.XXv:1412.71999 2014b.
Frédéric Chazal, Brittany Fasy, Fabrizio Lecci, Bertrand Michel, Alessandro Rinaldo, and Larry Wasserman. Subsampling methods for persistent homology. Francis Bach and David Blei (eds.). Proceedings of the 32nd International Conference on Machine Learning (ICML), volume 37 of Proceedings of Machine Learning Research, pp. 2143 1143-2151. PMLR, 2015a.
Frédéric Chazal, Mare Glisse, Catherine Labruère, and Bertrand Michel. Convergence rates for persistence diagram estimation in topological data analysis. Journal of Machine Learning Research, 16:3603-3635, 2015b.

---

Under review as a conference paper at ICLR 2020
Chao Chen, Xiuyan Ni, Qinxun Bai, and Yusu Wang. A topologiaal regularizer for classifiers via persistent homology. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pp. 2573-2582. PMLR, 2019.
Aruni Choudhary, Michael Kerber, and Sharath Raghvendra. Improved topological approximations by digitization. arXiv e-prints, art. arXiv:1812.000 2018.
David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37(1):103-12) 2007.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT Press, Cambridge, MA, USA, 3rd edition, 2009.
Herbert Edelsbrunner and John Harer. Persistent homology- survey. In Jacob E. Goodman, János Pach, and Richard Pollack (eds.), Surveys discrete and computational geometry: Twenty years later, number 453 in Contemporary Mathematics, pp. 257-282. American Mathematical Society, Providence, RI, USA, 2008.
Herbert Edelsbrunner, David Letscher, and Afra J. Zomorodian. Topological persistence and simplifi- cation. Discrete & Computational Geometry, 28(4):511-53: 2002.
Antonio Gracia, Santiago González, Victor Robles, and Ernestina Menasalvas. A methodology to compare dimensionality reduction algorithms terms of loss of quality. Information Sciences, 270:1-27, 2014.
William H. Guss and Ruslan Salakhutdinov. On characterizing the capacity of neural networks using algebraic topology. arXiv e-prints, art. arviv: TrXXvv1802.006 802.04443, 2018.
Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 31355786):504-577, 2006.
Christoph Hofer, Roland Kwitt, Mare Niethammer, and Andreas Uhl. Deep learning with topological signatures. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 1633-1643. Curran Associates, Inc., 2017.
Christoph Hofer, Roland Kwitt, and Marc Niethammer. Graph filtration learning. arXiv e-prints, art. 1XXiv1995511096 May 2019a.
Christoph Hofer, Roland Kwitt, Marc Niethammer, and Mandar Dixit. Connecivitt-opiimizee representation learning via persistent homology. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.). Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2751-2760. PMLR, 2019b.
Michael Kerber and R. Sharathkumar. Approximate čech complexes in low and high dimensions. arXiv e-prints, art. arXiv: 2013..
Valentin Khrulkov and Ivan Oseledets. Geometry score: A method for comparing generative adver- sarial networks. Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2621-2629. PMLR, 2018
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rX2v 69800, 2014.
Vitaliy Kurlin. one-dimensional homologically persistent skeleton of an unstructured point cloud in any metric space. Computer Graphics Forum, 34(5):253-225 2015.
Ann B. Lee, Kim S. Pedersen, and David Mumford. The nonlinear statistics of high-contrast patches in natural images. International Journal of Computer Vision, 54(1-3)883-103, 2003.
John A. Lee and Michel Verleysen. Quality assessment of dimensionality reduction: Rank-based criteria. Newrocomputing, 1237)1143 2009. ISSN 0925-2312.
10

---

Under review as a conference paper at ICLR 2020
Ryan Lewis and Dmitriy Morozov. Parallel computation of persistent homology using the blowup complex. In Proceedings of the 27th ACM Symposium on Parallelism Algorithms and Architec- tures (SPAA), pp. 323-333 ACM, 2015.
Leland McInnes, John Healy, and James Melville. UMAP:
Uniform manifold approximation and projection for dimension reduction. arXiv e-prints, art. arXiv: 180..03466. 2018
Facundo Mémoli and Guillermo Sapiro. Comparing point clouds. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (SGP), pp. 32 32-40, New York, NY, USA, 2004. ACM
Rahul Paul and Stephan K. Chalup. A study on validating non-linear dimensionality reduction using persistent homology. Puttern Recognition Letters, 100:160-166, 2017.
Gabriel Peyré. Manifold models for signals and images. Computer Vision and Image Understanding, 113(2):249-260, 2009,
Adrien Poulenard, Primoz Skraba, and Maks Ovsjanikov. Topological function optimization for continuous shape matching, Computer Graphics Forum, 37(5):13-22 2018.
Karthikeyan Natesan Ramamurthy, Kush Varshney, and Krishnan Mody. Topological data analysis of decision boundaries with application to model selection. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5351-5360. PMLR, 2019.
Jan Reininghaus, Stefan Huber, Ulrich Bauer, and Roland Kwitt. A stable multi-scale kernel for topological machine learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4741 4744, 2015.
Bastian Rieck and Heike Leitte. Persistent homology for the evaluation of dimensionality reduction schemes. Computer Graphics Forum, 34(3):431-440, 2015.
Bastian Rieck and Heike Leitte. Agreement analysis of quality measures for dimensionality reduction. In Hamish Carr, Christoph Garth, and Tino Weinkauf (eds.). Topological Methods in Data Analysis and Visualization IV. Springer International Publishing, Cham, Switzerland, 2017.
Bastian Rieck, Christian Bock, and Karsten Borgwardt. A persistent Weisfeiler-Lehman procedure for graph classification. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5448-5458. PMLR, 2019a.
Bastian Rieck, Matteo Togninalli, Christian Bock, Michael Moor, Max Horn, Thomas Gumbsch, and Karsten Borgwardt. Neural persistence: A complexity measure for deep neural networks using algebraic topology. In International Conference on Learning Representations (ICLR), 2019b.
The hwtp::/www..............oooooooo
imi ze: v0.5.2, March 2018.
1207017
Donald R. Sheehy. Linear-size approximations to the Vietoris Rips filtration. Discrete & Computa- tional Geometry, 49(4))778-776, 2013.
Joshua B. Tenenbaum, Vin De Silva, and John C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 23115500):211-22222 2000.
Laurens J. P. van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE, Journal of Machine Learning Research, 9:2579-2605. 2008
Laurens J.P. P. van der Maaten, Eric O. Postma, and Hendrik J. van den Herik. Dimensionality reduction: A comparative review. Technical Report 2009-005, Tilburg University, 2009.
Jarkko Venna and Samuel Kaski. Visualizing gene interaction graphs with local multidimensionall scaling. In Proceedings of ESANN '6, 14th European Symposium on Artificial Neural Networks, pp. 557-562, d-side group, 2006.
11

---

Under review as a conference paper at ICLR 2020
Leopold Vietoris. Über den höheren Zusammenhang kompakter Räume und eine Klasse zusam- menhangstreuen Abbildungen. Mathematische Annalen, 97(1))454 472, 1927.
Hubert Wagner and Pawel Dlotko. Towards topoloiiaal analysis of high-dimensional feature spaces. Computer Vision and Image Understanding, 121:21-26, 2014.
Lin Yan, Yaodong Zhao, Paul Rosen, Carlos Scheidegger, and Bei Wang. Homology- preserving dimensionality reduction via manifold landmarking and tearing. arXiv e-prints, art. 2018.
Afra J. Zomorodian. Fast construction the Victoris Rips complex. Computers & Graphics, 34(3): 263-271, 2010.
12

---

Under review as a conference paper at ICLR 2020
d = 2
d = 5
bn(: (X, X(mm
4
d = 10
2
10 30
40
50
60
70
80
100
Figure A.I: Empirical convergence rate (mean) of the Hausdorff distance for subsample of size m of 100 points d-dimensional space, following a standard normal distribution.
A APPENDIX
A.1 PROOF OF THEOREM
Theorem 1. Let X be point cloud of cardinality and X ((m) be one subsample of X of cardinality m, ie, ((m) C X, sampled without replacement. We can bound the probability of X (m) exceeding threshold in terms of the bottleneck distance
IP db (Dx, :DX(IM) > S PP
(x,x(m)) =
>20)
(7)
where du refers to the Hausdorff distance between the point cloud and its subsample, i.e.
dn(X == max sup inf dist(x, v), sup inf dist(æ, 3) xxE yEY
(8)
DEY xeX
for a baseline distance dist y) such as the Euclidean distance.
Proof. The stability of persistent homology calculations was proved by CCazal et al. (2014a) for finite metric spaces. More precisely, given two metric spaces X and Y, we have
d, (Dx D S 2 (X,
where dGH (X, Y) refers to the Gromoy-Hausdorfe distance (Burago et al. 2001 254) of the two spaces. It defined as the infimum Hausdorff distance over all isometric embeddings of X and Y. This distance can be employed for shape comparison (Chazal et al.) 2009 Mémoli & Sapiro 2004). but is hard to compute. In our case, with X = X and Y X we consider both spaces to have the same metric (for Y, we take the canonical restriction the metric from X to the subspace Y). By definition of the Gromov-Hausdee leads to
distance, we thus have dGH Y) < dr(X, so Eq.
dp (Dx DV) s (d,(XX Y),
(10)
from which the original claim from Eq. follows by taking probabilities on both sides.
A.2 EMPIRICAL CONVERGENCE RATES OF du (X,
Figure A.I depicts the mean of the convergence rate (mean) of the Hausdorff distance for a sub- sample of size of 100 points in d-dimensional space, following standard normal distribution. We can see that the convergence rate is roughly similar, but shown on different absolute levels that depend the ambient dimension. While bounding the convergence rate of this expression is feasible (Chazal et al.) 2015a b), it requires more involved assumptions on the measures from which X and (mm) are sampled. Additionally, we can give a simple bound using the diame- ter diam(X) := (up(dis((a: y) x, E X}. We have dx(X, dx(XXX(()) (())) < diam(X) because the supremum is guaranteed to be upper bound for the Hausdorff distance. This worst-car bound does not account for the sample size (or mini-batch size) m, though (see Theorem 2 for an expression that takes into account).
13

---

Under review as a conference paper at ICLR 2020
A.3 PROOF OF THEOREM 2
Prior to the proof we state two observations that arise from our special setting of dealing with finite point clouds.
Observation 1. Since X S X, we have supxrex(m) infzex dist(x, (2,,=")))) 0. Hence, the Haus-
dorff distance simplifies to:
dh [X (x, sup inf dist(x,x')
(11)
='X='E""
In other words, we only have to consider a "one-sided" expression of the distance because the distance from the subsample to the original point cloud is always zero.
Observation 2. Since our point clouds of interest are finite sets, the suprema and infima of the Hausdorff distance coincide with the maxima and minima, which will subsequently use for easier readability.
Hence, the computation of ( (mm) can be divided into three steps.
Using the baseline distance dist((;;)), we compute a distance matrix A E Raxx between all points in and (m))
2. For each of the n points by extracting the minimal distance per row of A and gather all minimal distances in ô E RR.
we compute the minimal distance to the m samples of (m))
3. Finally, we return the maximal entry of 5 as du (m)).
In the subsequent proof, we require an independence assumption of the samples.
Proof. Using Observations and we obtain simplified expression for the Hausdorff distance, i.e.
du X, x(m)) = max i,1si5n
min (a.)) (.15ism
(12)
The minimal distances of the first m rows of A are trivially O. Hence, the outer maximum is determined by the remaining n m row minima (6, m < S with = min (aiz). Those
15ssm
minima follow the distribution Fa (y) with
F1 P(6, S = =1 p( =1 P
min Oij > y 15)5m
(13)
=1-P ( aij =1 -1-11-o(0)7 =
(14)
Next, we consider Z == maxigisn 8z. To evaluate the density of Z. we first need to derive its distribution Fz:
(n
Fz(z) = P(Z
22) P max 6, S = = msisn
n 8, S
(15)
meiSa
Next, approximate Z by Z' by imposing i.i.d sampling of the minimal distances 8, from Fa- This is an approximation because in practice, the rows m + to are not stochastically independent because of the triangular inequality that holds for metrics. However, assuming i.i.d., arrive
(2) (2(2)"=m)
(16)
Since Z' has positive support its expectation can then be evaluated as:
/ (1 Fa(=)=-m) dz
129
(1 (z)
(17)
0
0
t
too
1 Fb(z)ma(nm))
2z > /
1 FD(2)(n-11) dz
(18)
14

---

Under review as a conference paper at ICLR 2020
(a) PCA
(b) Isomap
(c) t-SNE
(d) UMAP
(e) AE
(l) TopoAE
Figure A.2: A depiction of all latent spaces obtained for the SPHERES data set. TopoAE used batch-size 28. This is an enlarged version of the figure shown in Section 5.2
The independence assumption leading to Z' results in overestimating the variance of the drawn minima 8,. Thus, the expected maximum of those minima, E|Z"). overestimating the actual expectation of the maximum E[Z], which is why Eq. 17 to Eq. 18 constitute an upper bound of (Xdn(X, X²) decreases monotonically since for a particular 77, we draw n m samples from the minimal distance distribution Fa. and their maximum determines the Hausdorff distance. In contrast,
E[Z], and equivalently, an upper bound of F. [[dd(XX (X, X mm }] When increasing
preliminary
upper bound on the left-hand side Eq. 18 forms downwards-facce facing parabola due to the quadratic form in the exponent. This indicates that tighter bound is achieved for F by using the minimal subsample size of m
A.4 SYNTHETIC DATASET
SPHERES consists eleven high-dimensional 100-spheres living in 101 dimennsooal space. Ten spheres of radius r = 5 are each shifted in random direction (by adding the same Gaussian noise vector per sphere). To this end, we draw ten d-dimensional Gaussian vectors following AO, va)) for d = 101. Crucially, to add interesting topological information to the data set, the ten spheres enclosed by an additional larger sphere of radius 5r. The spheres were generated using the library scikit-tda.
A.5 ARCHITECTURES AND HYPERPARAMETER TUNING
Architectures for synthetic data set For the synthetically generated dataset we use a simple Multilayer perceptron architecture consisting of two hidden layer with 32 neurons each both encoder and decoder and a bottleneck of two neurons such that the sequence of hidden-layer neurons is
32 32 2 32 32. ReLU con-linearities and batch normalization were applied between the layers excluding the output layer and the bottleneck layer. The networks were fit using mean squared enror loss.
15

---

Under review as a conference paper at ICLR 2020
(a) PCA
(b) L-SNE
(c) UMAP
(d) AE
(e) TopoAE (proposed)
Figure A.3: Latent representations of the FASHION-MNIST data set. TopoAE used batch-size 95. This is larger extension of the figure shown in Section 5.2
(a) PCA
(b) L-NE
(c) UMAP
(d) AE
(e) TopoAE (proposed)
Figure A.4: Latent representations of the MNIST data set. TopoAE used batch-size 126. This is larger extension of the figure shown in Section 5.2
Architectures for real world data sets For the MNIST, FASHION MNIST, and CIFAR- 10 datasets, we architecture inspired by DeepAE (Hinton & Salakhutdinov 2006). This architec- ture is composed of layers of hidden neurons decreasing size (1000 500 250) for the encoder part, bottleneck of two neurons, and sequence of three layers of hidden neurons in decreasing size
16

---

Under review as a conference paper at ICLR 2020
(a) PCA
(b) I-SNE
(c) UMAP
(d) AE
(e) TopoAE (proposed)
Latent representations of the CIFAR-10 10 data set. TopoAE used batch-size 82, This is larger extension of the figure shown in Section 5.2
Figure A.5:
(250 - 500 1000) for the decoder. In contrast to the originally proposed architecture, we applied ReLU mon-lineassties and batch normalization between layers as we observed faster and more stable training. For the non-linearities of the final layer, we applied the tanh non-linearity, such that the image
activation matches the range input images scaled between 1 and 1. Also here, we applied mean squared error loss.
All neural network architectures were fit using Adam and weight-decay of 10-3
Hyperparameter tuning For hyperparameter tuning we apply random sampling of hyperparam- eters using the scikit-opt iipoptimizzi ze library (scikit-optimize contributers 2018) with 20 calls per method on all datasets. We select the best model parameters in terms of kL on the validation split and evaluate and report it the test split. To estimate performance means and standard deviations, we repeated the evaluation on an independent test split times by using the best parameters (as identified in the hyperparameter search on the validation split) and refitting the models by resampling the train-validation split.
Neural networks For the neural networks we sample the learning rate log uniuorrforlly in the range 10-4 10-2 2, the batch-size uniformly between 16 and 128, and for the TopoAE method we sample the regularization strength log-uniformly in the range 10-1 3. Each model was allowed to train for most 100 epochs, whereas we applied early stopping with patience 10 based on the validation loss.
Competitor methods For t-SNE, we sample the perplexity uniformly in the range 5 - 50 and the learning rate ungforrfyylly in the range 10 1000. For Isomap and UMAP, the number of neighbors included in the computation was varied between 15 500. For UMAP, we additionally vary the min_dist parameter uniformly between and
A.6 MEASURING THE QUALITY OF LATENT REPRESENTATIONS
Next to the reconstruction error (if available; please see the paper for a discussion on this), we variety of NLDR metries to assess the quality of method. Our primary interest concerns
17

---

Under review as a conference paper at ICLR 2020
the quality of the latent space because, among others, it can be used visualise the data set. We initially considered classical quality metrics from non-linear dimensionality reduction (NLDR) algorithms (see [Bibal & Frénay (2019); Gracia et al. (2014); van der Maaten et al. (2009) for more in-depth descriptions), namely
(1) the root mean square ervor (4-RMSE) between the distance matrix of the original space and the latent space (as mentioned in the main text, this is not related to the reconstruction error),
(2) the mean relative rank error (f-MRRE), which measures the changes ranks of distances in the original space and the latent space (Lee & Verleysen 2009),
(3) the trustworthiness (e-Trust) measure (Venna Kaski 2006). which checks what extent the k nearest neighbours of a point are preserved when going from the original space to the latent space, and
(4) the continuity (é-Cont) measure (Venna & Kaski, 2006), which is defined analogously to E-Trust, but checks to what extent neighbours are preserved when going from the latent space to the original space.
All these measures are defined based on comparisons of the original space and the latent space; the reconstructed space is not used here. As an additional measure, we calculate the Kullbuck-Leibler divergence between density distributions the input space and the latent space. Specifically, for point cloud X with associated distance dist, first the distance to a measure density (1),2,,))))))))))))
estimator (Chazal et al. 2011 2014b), defined as f (z) := Eyex exp (-o dist(æ; v)²) where R represents length scale parameter. For dist, we use the Euclidean distance and normalise it between 0 and 1. Given a, evaluate KL, KL f22 ff²) which measures the similarity between the two density distributions. Ideally, we want the two distributions to be similar because this implies that density estimates in a low-dimensional representation are similar the ones in the original space.
A.7 ASSESSING THE BATCH SIZE
As we used fixed architectures for the hyperparameter search, the batch-size remains the main determinant for the runtime of TopoAE. In Figure[A.6] we display trends (linear fits) on how loss measures vary with batch size. Addtionally, we draw runtime estimates. As we applied early stopping, approximated the epoch-wise runtime by dividing the execution time of
for better comparability, run by its number of completed epochs. Interestingly, these plots suggest that the runtime grows with decreasing batch-size (even though the topological computation is more costly for larger batch-sizes)). In these experiments, sticking to 0 dimensional topological features we conclude that the benefit of using mini-batches for neural network training still dominate the topological computations. The few steep peaks most likely represent outliers (the corresponding runs stopped after few epochs, which is why the effective runtime could be overestimated).
For the loss measures, we see that reconstruction loss tends to decrease with increasing batch-size, while our topological loss tends increase with increasing batch-size (despite normalization). The second observation might be due to larger batch-size enabling more complex data point arrangements and corresponding topologies.
A.8 EXTENDING TO VARIATIONAL AUTOENCODERS
In Figure| A.7 we sketch preliminary experiment, where we apply our topological constraint to variational autoencoders for the SPHERES dataset. Also here, we observe that our constraint helps identifying the nesting structure of the enclosing sphere.
A.9 TOPOLOGICAL DISTANCE CALCULATIONS
To assess the topological fidelity of the resulting latent spaces, we calculate several topological distances between the test data set (full dimensionality) and the latent spaces obtained from each method (two dimensions). More precisely, we calculate (i) the 1st Wasserstein distance (W1). (ii) the 2nd Wasserstein distance (W2), and (iii) the bottleneck distance (W.c) between the persistence diagrams obtained from the test data set of the SPHERES data and their resulting 2D latent representa- tions. Even though loss function is not optimising this distance, observe in Table A. that
18

---

Under review as a conference paper at ICLR 2020
Decondtrction Lon
Pecoratrct on Lomn
2:11
Tepulaguu
816
A12
0.51
850
PARCOR
0.44
004
125
Butch Sec
Buton Six
(a) FASHION-MMN
MNIST
0.44
Obactive 11.0111
06
0.00
200
CIFAR-10
SPHERES
Figure A.6: From our hyperparameter searches we scatter batch-sizes against three measures of interest: Topological Loss, Reconstruction Loss, and KLo. 1. our objective for hyperparameter search. Additionally, we draw epoch-wise runtime estimates.
(a) VAE
(b) TopoVAE
Figure A.7: A depiction of latent spaces obtained for the SPHERES data set with variational autoen- coders (VAEs). Here, VAE represents a standard MLP-based VAE, whereas TopoVAB represents the same architecture plus our topological constraint.
19

---

Under review as a conference paper at ICLR 2020
Table A.I: Various topological distances calculated between the test data set and the corresponding latent space. For computational efficiency reasons, we used subsamples of size m 500 and repeated the process 10 times. Individual cells thus contain mean and standard deviation.
Method
W
W2
W oc
Isomap
4.32:+0.037
0.477=0.0045
0.165=0.00096
PCA
4.42:1:0053
0.406:1.0004
0.158=0.00108
I-SNE
4.38:10.038
0.478:10.0045
0.164=0.00094
UMAP
4.47=00042
0.478=000045
0.160=0.00092
AE
3.99::0.037
0.469+0.0055
0.154=0.00128
TopoAE
3.7310.076
0,459=1000055
0.152=0.00268
the topological distance our method ("TopoAE")) is always the lowest among all the methods. In particular, it is always smaller than the topological distance of the latent space of the autoencoder architecture; this true all distance measures, even though W. for example, is known to be susceptible to outliers. Said experiment serves as simple "sanity check" as it demonstrates that the changes induced by our method are beneficial in that they reduce the topological distance of the latent space to the original data set. For a proper comparison of topological features between the two sets spaces, a more involved approach would be required, though.
20

---

Under review as a conference paper at ICLR 2020
C
dg
d3
d2
d2
C
d1
d1 B
B
(a) X
Z
Figure A.8: An undesirable configuration of the latent space of three non-collinear points. Pairwise distances are shown dotted lines. This configuration results in equal persistence diagrams for X and 2. We prevent this by not explicitly minimising the distances between persistence diagrams but by instead including the persistence pairing information.
A. ALTERNATIVE LOSS FORMULATIONS
Our choice of loss function was motivated by the observation that only aligning the persistence diagrams between mini-batches of X and Z can lead degenerate or 'meaningless' latent spaces. As simple example (see Figure [A.8] for visualisation), imagine three non-collinear points in the input space and the triangle they are forming. Now assume that the latent space consists of the same triangle (in terms of its side lengths) but with permuted labels. A loss term of the form
L' = |
A 7
(19)
only measures the distance between persistence diagrams (which would be zero in this situation) and would not be able to penalise such a configuration.
21

---

Under review as a conference paper at ICLR 2020
Dann MSE
0,86183 + 000029
0.81545 + 0.00000
I 0.00744
di 0.00000
+: 000022
# 00002M
0,20269 + 0.00000
0 # 0.00000
E 0.00066
0000000
0.1975 E. 0100771
0.80812
0.16420
0
0.12071
0.1389
0.34166
E-RMNE
10.57 188 = 0.22866
11. 11.76402 = 000160
0.03177
13,30061 - 0.05198
0.0417
SU1512 & 0,000L
41 41225400 0.3871
2070662 # 3-5061
20.01 1222 = 0,932V6
1A17437 = 0.0016
2238961 I 0.2377
INAOS = 03H45
I 001812
00000
I 0LTISS
BOXTING
Table A.2: Extended version of the table from the main paper. showing more longth scales and variance estimates.
1344755
130893
17777
187150
1561099
3357785
3739914
E-1im
0.67643 = 0.00333
0.62577 = 0.0006
8500
0.5NA4 1 0.0007
0.04
0.91 & 0L000NSS
E 000099
- 00000
0.00
0000362
D 0.00 12
0-22L17 000002
DE 0000511
0100359
634983
05675
0.97418
0.90612
0.74556
0.96224
0.9399
0.928
0.3632
0.97
E-MRRE
0.24573 # 0.0055
0.77700 1 000040 0,29-00 + 000108
0217240 0.00072
024998 000094
0.34918 E 0.000033
I 001108
000001
010211
136 + CU0ESS
166533 + 0.0022
DOVE Σ 000129
0 + 000053
0.05SS3 E 0000
OLOORSS
0.102K + CU0O22
0112000 1 OLIORES
E. 0L002T
0,2239
0.05744
0
0111911
0.10899
2-Coon
0/79022 + 0.0004
0,7700 0.0011
0.73153 # 010360
0.50063 I 0.0188
I D.01BS
0.96777 J. 0L00001
(190340 + DOUST2
+ 0100994
+ 010001
021283 # 0100864
093200 I 0.00322
OUREN0 010000
RUSEENT + DLOKET
1 DLOOESS
099291 E DO0000
+
I
0.82200
0,97999
0,0004
0,22001
09335
KL
(U00N99 = 0.00000
0100166 3: 0,00000
010000
-E 0.00001
ALMNMIT 0,0000
EUMMMI 1 0,00000
010000
= 0.0000
0 = 0,00000
01000 3 0,00000
0X00
LUNNI DE 0,00000
ALOONID 0A0OO0
CUOOMI I (J0000
QIOOMI 0,00000
GAROED
EUMANO DE (L00000
000018
0.00117
GIXMII
KUMNNI
GUNANIZ
KL.1
# 0.00020
001330 E. 0.00000
0.1271 0.00005
0.00238
0.06644 E 0.001LS
I 0.00055
O. MANN 0.00000
0.00026
0.0017
0.0015
0,0060 + 0.0000L
0.002 H4 Σ 0.00011
0.00233
I 0.00000
0,ONI2E +. 0.0AN0
DLORITS E 0,00007
OLOGKSO 0.00001
0 E. 0.00022
0.0001
0,0038
0. 0.00674
BLOITUN
& 8000
0.00156
0. 0.001H
K4gg1
+ 010059
4 000256
010752
0.74588 + 0/0023
1 000080
0 J. OLAME
010079 + 000200
+ 0L0095S
0 16301 + 000059
I 00036
00030
I 001069
+ 0L000I
B.10014 + OLOIEES
0.02362 E B00001
0.18TT + (UARST
0-22448
0,63121
061338
0,32872
0.13266
0,15542
0.11012
0.0196
BAISESS
0118066 + 0025-77
0.3321 : 000652
0.00000
000899
: 002961
000270
1: QO001
009867
+ 00E2M4
0.38576 = 000146
0.27085 I 005266
I 003058
0AEEE + QU1427
QUEPRL
0.5562 + 00N4T2
KLg
0115877
0.5657
0.08
0,355M
0.393
061199
0.30099
0.59773
0.5009 # 0.0
0122445 2t 0.00091
0.002
0:01977
0,28432 1 0.02165
= 0:05415
0.00O01
0.1 1800
dE 0:0244
16754 + 0.00051
I 0:00100
000001
0.08500
E 0.03312
0.00014
0O00202
KLgg
0.77177 #
0.22799
0.4732
0.62766
PCA 0,22559
0000116
0.9
0,72144
0-44600
0332227
0.37220
1100954
(130877
Method
bsanap
PCA
TSNE
UMAP
TopoAE
Lopoλt:
PCA
TSNE
UMAP
TopoAE
PCA
TSNE
UMAP
TopoAE
AE
AE
AE
FASHION MNIST
MNIST
CIPAR
Data
22


Reviews:
[{"review_id": "r1xRaO5nYH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper shows how to train an autoencoder that preserves topologically\nrelevant distance across varying length scales.  It presents a new\ndifferentiable loss term for topological distance between input and latent\nspace.  The topological loss has a number of nice features: compatibility with\nminibatch training, and extension to higher input and latent space\ndimensionality fairly easily.\n\nSince this trainable topological loss can be applied in more general scenarios\nthan simply auto-encoders or visualization, I think this well-written article\nis of general interest and worth publishing.\n\nThe main ideas and related work are presented clearly in sections 1--4, and the\nexperiments compare TopoAE with a variety of low-dimensional visualization\nmethods.  Embedding quality is evaluated with a wide variety of metrics on real\nand synthetic datasets highlighting the preservation of global and local\ntopology.\n\nMy only real issue, easily fixable, was that after the minibatch stability\ntheory (Sec. 3.3), I really wanted to know what minibatch sizes were used in\nthe experimental figures, and spent twenty minutes before admitting defeat.\nPlease include the actual TopoAE minibatch size when presenting the\nvisualization figures in the article and appendices.\n\nThe appendices contain a wealth of useful reading and experiments, and the\nprovided source code was clearly organized and useful to browse.  I did not go\nline-by-line through the appendix proofs.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hkgf8QdnFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n-------------\n\nThe paper proposes an approach, based on persistent homology (PH), to preserve certain topological structures of the input in the latent representations learned by an autoencoder. This is realized via an additional (i.e., in addition to reconstruction) loss term (optimized over mini-batches) which requires differentiating through the PH computation. While this has been done before (e.g., Chen et al., Hofer et al.), the authors have certainly put an interesting spin on this. The theoretical part of the work deals with the issue of using mini-batches for PH computation and whether this computation is close to the computation on the full point cloud. Experiments and comparisons on multiple datasets are presented to demonstrate that the approach, e.g., preserves nesting relationships in the input. The paper is nicely written and the content is very well presented. There are questions here and there (see below), but I do think they can be answered.\n\nMajor comments/remarks:\n-------------------------------------\n\nMy first question relates to the issue that the loss only incorporates 0-dim. information. The authors do remark that higher-dim. features can be included, but the results were similar. However, after thinking about this issue quite some time, I am curious if it is possible to obtain \"zero\" of the topological loss (so this term is perfectly optimized), but the encoder introduces, e.g., cavities in the data which were not present in the input (e.g., 1-dim. holes).\n\nAlso, can you show formally (maybe this is trivial and I am not seeing it) that L_t = 0 would lead to 0 distance between the corresponding diagrams w.r.t. some common metric? A more formal treatment of the implications of the loss in Eq. (2) would certainly help.\n\nAnother question that immediately comes to mind is whether the computation of VR PH in the input space (e.g., CIFAR 10) makes sense, as the authors rely on ||.||_2 if I understood this correctly. I would argue that the topology of the input is basically unknown, especially for images and computing Euclidean distances among images, or vectorized images, does not make sense. For the nice results on the SPHERES data set it does, as the spheres are defined exactly using ||.||_2. If the VR PH in 0-dim. of the input is enforced upon the representations in the AE bottleneck, but the input topology is not captured well, then you might be enforcing something that you possibly do not want.\n\nApart from that, it is known that the Euclidean distance degenerates quickly in high dimensional spaces, e.g.,\n\nAggrawal et al.\nOn the Surprising Behavior of Distance Metrics in High Dimensional Space\n\nMaybe this is also contributing to the fuzzy visualization of CIFAR-10 in Fig. 3 (apart from the low-dim. of the bottleneck)?\n\nAlso, maybe the authors could work out (in greater detail) the differences between their results from Thm.1/2 and the results of Chazal et al., in \"Subsampling Methods for Persistent Homology\". In my point of view, the results in the paper only hold if you would consider just a single batch, right? I mean, if the loss is computed from the batch, and a gradient update is performend, Z^{m} will changes (as the encoder changes as a result of the update), while the input does not. \n\nFinally, how were the KL divergence measures in Table 1 computed, as you need a density estimate of the input as well, not just for the representation space, right? Is this not a very crucial issue in the input space? If so, how reliable are the numbers presented for KL_{0.01},etc., given that the differences are sometimes extremely small.\n\nMinor comments\n-----------------------\n\nSec. 6: We presented a topological autoencoders -> We presented a topological autoencoder\n\nOverall, I think this is a nicely done paper, but with quite some question marks at many places. I do think this is always the case for something new, though, and \nactually a good thing.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "B1l05Iwm5r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The basic premise of this work is that topological operators are increasingly adopted in machine learning models, but the literature lacks of general differentiable topological operators.\n\nThe main idea proposed in this work is to use the topological signature directly as a loss for autoencoders. The general aim is to preserve the topological properties of data while performing dimensionality reduction. \n \nThe proposed method computes the persistent homology of the 0-dimensional Vietoris–Rips by means of persistence diagrams and persistence pairing. The additional step is to computes the regularization loss, by posing the constraint that the persistent homology be similar between data space and latent space. The empirical analysis investigates the stability property with respect to the mini-batch sampling. \n\nThe extended experiments don't provide an empirical evidence of the added value of a topological AE. The results are quite controversial if we focus our attention on MSE measures. AE and TopoAE behave in a similar way and it is not clear whether such a difference is statistically significant. \n\nThe work is missing a mandatory comparison with Hofer et al. (2019b) that proposes a loss very similar to the one presented in Section 3, even though the authors remark that their formulation is more general. For example an interesting comparison could have been with the real-case application of classification for the images datasets (e.g. CIFAR, MNIST, ImageNet) where Hofer et al. (2019b) proves their claims.\n\nThe computational issues of the d-dimensional Vietoris-Rips with d > 0, limits the preservation of only simple structures in the point-cloud.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a new variant of autoencoders with an topological loss term.

The reviewers appreciated part of the paper and it is borderline. However, there are enough reservations to argue for it will be better for the paper to updated and submitted to next conference.

Rejection is recommended.  
Decision: Reject