Local Distance Preserving Auto-encoders using Continuous k-Nearest Neighbours Graphs
Authors: Nutan Chen
Patrick van der Smagt
Botond Cseke
Venue: Submitted to ICLR 2023 (2023)
Keywords: manifold learning
representational learning
generative models

Abstract: Auto-encoder models that preserve similarities in the data are a popular tool in representation learning. In this paper we introduce several auto-encoder models that preserve local distances when mapping from the data space to the latent space.  We use a local distance-preserving loss that is based on the continuous k-nearest neighbours graph which is known to capture topological features at all scales simultaneously. To improve training performance, we formulate learning as a constraint optimisation problem with local distance preservation as the main objective and reconstruction accuracy as a constraint. We generalise this approach to hierarchical variational auto-encoders thus learning generative models with geometrically consistent latent and data spaces.  Our method provides state-of-the-art or comparable performance across several standard datasets and evaluation metrics.

Under review as a conference paper at ICLR 2023
LOCAL DISTANCE PRESERVING AUTO-ENCODERS US- ING CONTINUOUS K-NEAREST NEIGHBOURS GRAPHS
Anonymous authors Paper under double-bling review
ABSTRACT
Auto-encoder models that preserve similarities in the data are a popular tool in representation learning. In this paper introduce several auto-encoder models that preserve local distances when mapping from the data space to the latent space. We use local distance-preserving loss that is based on the continuous k-nearest neighbours graph which is known to capture topological features at all scales simultaneously. To improve training performance, we formulate learning as constraint optimisation problem with local distance preservation as the main objective and reconstruction accuracy as a constraint. We generalise this approach to hierarchical variational auto-encoders thus learning generative models with geometrically consistent latent and data spaces. Our method provides state-of- the-art comparable performance across several standard datasets and evaluation metrics.
INTRODUCTION
Auto-encoders and variational auto-encoders (Kingma & Welling 2014 Rezende et al., 2014)
often used in machine learning to find meaningful latent representations of the data. What constitutes meaningful usually depends the application and the downstream tasks, for example, finding representations that have important factors of variations in the data (disentanglement) (Higgins et al. 2017: Chen al.] 22188,, have high mutual information with the data (Chen et al.) (016)), or show clustering behaviour w.r.t. some criteria (van der Maaten & Hinton, 2008). These representations are usually incentivised by regularisers or architecturallstrruuurr choices.
One criterion for finding a meaningful latent representation is geometric faithfulness to the data. This important for data visualisation or further downstream tasks that involve geometric algorithms such as clustering kNN classification. The data often lies in a small, sparse, low-dimensional manifold in the space it inhabits and finding a lower dimensional projection that is geometrically faithful to can help not only in visualisation and interpretability but also in predictive performance and robustness (c.g. Karl et al. (2017: Klushyn et al. (021). There are several approaches that implement such
projections, ISOMAP (Tenenbaum al. 2000 LLE (Roweis & Saul 2000), SNE/1-SNE (Hinton & Roweis 2002 van der Maaten & Hinton 2008 Graving & Couzin (0220) and UMAP (Meinnes et al.
2018 Sainburg 2022) aim preserve the local neighbourhood structure while topological auto-encoders (Moor et al. (020).. witness auto-encoders (Schönenberger et al., (2020), and (Li et al. 202T) use regularisers auto-encoder models learn projections that preserve topological Teatures
or local distances.
The approach presented (Moor al.) 2020), uses persistent homology computation to define local connectivity graphs over which to preserve local distances. One can choose the dimensionality of the preserved topological features, however, preserving higher-dimensional topological features comes at additional computational cost. In this paper we propose to use the continuous k-nearest neighbours method (Berry Sauer 2019) which based on consistent homology and results in significantly simpler graph construction method; it is also known to capture topological features at all scales simultaneously. Since AE and VAE methods are usually hard to train and regularise (Alemi et al. 2018 Higgins et al. 2017: Zhao al. 2018 Rezende & Viola 2018). to improve learning we formulate learning as a constraint optimisation with the topological loss as the objective the reconstruction loss constraint. In addition, we adapt the proposed methods VAEs with

---

Under review as a conference paper at ICLR 2023
learned priors. This enables us to learn models that generate data with tupologically/goomerricaall consistent latent and data spaces.
METHODS
In this paper we address (i) projecting i..dd data X = { with x E R into lower-dimensional representation 2 E R (m < n)) using auto-encoders and (ii) learning an unsupervised (bierarchical) probabilistic model that can be used not only to encode but also generate data similar to X. Auto- encoder models are typically learned by minimising the average reconstruction loss [ree (0, Φ; X) E (fo (x))) w.r.t. (0, Φ), where I(:,-) is a positive, symmetric, non-decreasing function and the mappings f and go are called the encoder and the generator, respectively. Due to consistency with distance preserving losses, we only use as reconstruction loss the Euclidean distance ((x, x') || - x11... The expectation is taken w.r.t. the empirical distribution p(x) (1/N) E, 5(x 22) and training is performed via stochastic batch gradient methods.
Unsupervised probabilistic models are typically learned by maximum likelihood method w.r.t. 0 on Po( = II, , Po (ax] 22) (2;) dz;, where po (a1z)) is the likelihood term corresponding to the gener- ator (z) and pe (z) ())j is the prior distribution/densityy of the latent variables z. The distribution pa (=()) is either chosen a product of some standard univariate distributions or learned via empirical Bayes. In practice, learning the prior is often included in the maximum likelihood optimisation. Since the inte- grals Jg (x, (2) (2)o ational Bayes (Kingma & Welling, 2014 Rezende et al. (014)) resulting in the evidence lower-bound (ELBO) approximation log po ) max { (e:e)) [log po [=]= (2; [[)p)==)] The re- sulting go 2:) is approximation of the posterior distribution po (=(2]=) (2) =)pp (2) (2)pp((()) (2) and can be viewed as corresponding to the encoder fo(r). For notation simplicity, we use 0 for all model parameters, and á for all encoder parameters. In this paper we will deviate slightly from the ELBO approach to fit the parameters 0 and é because of practical considerations but the general modelling ideas will be similar nonetheless.
(2)dd dz are usually intractable, log Pa (z) is often approximated using amortised vari-
2.1 LOCAL DISTANCE PRESERVATION
Auto-encoders are popular models for dimensionality reduction and thus they are often extended with regularisers or constraints that impose various types of inductive biases required by the task at hand. One such inductive bias is local distance preservation, that is, two data points x; and x close in the data-space at distance (2, xzy) should be mapped into points 2, = (a;) and 2j = (x,) at distance ydz (2t, 22) ~ (x 2.). This distance preservation can help to retain the topology of the data X in the encoded data Z = {z+ fe(x:)) Since the the data X is often hypothetised to lie on a sub- manifold of R", give or take some observation noise (Rifai et al. 2011), one expects that the encoded data Z will be lower-dimensee dineessonnii...l topologically faithful representation of X.
In this paper we mainly consider local distance preservation where locality or closeness in the data manifold is formulated via (neighbourhood) graph structures constructed based on topologi- cal/geometrical considerations. We present the graph construction methods we use in Section 2.3 Let us assume that we have constructed two graphs with the same method, a graph Gx based on data/batch and another graph Gz based on the encoding of the data/batch. Given these graphs and the distance measures in both spaces, we define the local distance-preserving loss defined similarly as in (Sammon 1969 Lawrence & Quinonero-Candee
2006 Moor et al. 2020).
Tropo X, = Σ
(dx(x;, ydz (2i, 2,)1
(1)
(L))E&XUSZ
Here, in case of auto-encoder models we have Z =2, = fo(x,)), while in case of generative models we have Z = {2 q(2; [ The scaling factor y is a learned variable and is introduced to help with the scaling issues one might encounter in VAE models. In case of generative models one also consider the generative counterpart for Z' po(2), X' po(-1 For models and training schedules we considering in this paper this did not bring any additional benefit because a good auto eectodnn and a well fitted prior already ensures small value for this additional term.
There are several other options for loss functions that are designed to incentivise auto-encoders to preserve locality structures. SNEASNE construct a probability distribution of connectedness for each
2

---

Under review as a conference paper at ICLR 2023
data point both in the data and latent spaces and compare these using the Kullback-Leible divergence. UMAP uses a formally similar method on a symmetrised k-nearest neighbours graph (see Section 2.3 albeit based on different theoretical considerations.
2.2 INFERENCE AND LEARNING VIA CONSTRAINED OPTIMISATION
Probabilistic generative models (VAEs) are often hard to train because they can converge to sub- optimal local minima (Sønderby et al. 2016), moreover, it has been shown in several papers that higher ELBO values do not necessarily correspond to better prediction performance or informative latent spaces (Alemi et al. 2018 Higgins al. 2017). For this reason, several annealing schemes have been proposed that slowly ly "turn on" the Kiverieeeeence term in the ELBO to avoid an over-regularisation of qá. In particular, scheduling schemes derived from constrained optimisation approaches (Rezende & Viola 2018) can significantly improve training in hierarchical generative models (Klushyn et al. 2019p. For this reason, we propose two constrained optimisation methods train auto-encoders and generative models.
In case of auto-encoders, we formulate the optimisation problem as min Ex,=p(x) Looo (Ø; Xb, fo
(2a)
0,0
s.t. Ex)= [1 (X,, 99 (fo (Xx))) S Erec
(2h)
where <h denotes a baseline reconstruction error, a hyper-paramater that is mostly influenced by the model architecture. To emphasise that we use batch training and that Lropo is computed on pair of data batch Xs. we overload the notation of the respective mapping and densities with this set notation.
In case of (hierarchical) generative models, we formulate the constrained optimisation problem [KT (o5 Xx)l po (2))
min Exar((x) 0,0
(3a)
s.t. F (aar(((r))
[Ezo log po [x]] S Erec
(3b)
Exax
(-X66) [Teapa (0); X6, [b]]] I Étopa:
(3c)
where, when a Gaussian Pa (x)22 N N( (rrgge(( (2), o2. is used, we replace equation with an equivalent
reconstruction constraint Ex.~((a) Es
|| 9o (Z+)) < &ree- The optimal parameter
of can be computed at the end of training as the average square reconstruction error. The KL is
overloaded represent averaging over Xx. Zg. The Lagrangian of the optimisation problem (3a
has similar form as an ELBO objective and thus resembles models in (Rezende & Viola 2018).
(Higgins al.) 2017) and (Klushyn et al. 2019) albeit with two constraint terms. In our experience the constraint optimisation approach leads to better training performance than simple regularisation when one has to fit objectives with different scales. In principle any of the three losses or weighted combinations of some/all can be considered as the main objective. To have automatic "weight tuning" via Lagrange multipliers it is reasonable to have one loss as objective and the rest as constraints. We have made the above choices, because it is relatively easy to come up with constraint boundary candidates: for the topological one we are informed by the distances in the data space, while for the reconstruction one by the reconstruction error.
To solve the optimisation problems 2b) and 33 3c), we define the corresponding Lagrangians and optimise them via gradient quasi-ascent-descent. We use the exponential method of multipli- ers (Bertsekas) 2003) for the Lagrange multipliers Arec and Xtopo corresponding to (2b 3b) and T
equation 3c correspondingly. This reads as X X exee (Li Erec]} } and Moooo =
Σtopo)}, ). where we use first order moving averages Liee and Li to dampen fast variations due to batch training (Rezende & Viola 2018). There are several other options to fit Azec, Atopo such various gradient methods
Xopo (xp{Thopo
their logs. In addition simple tricks to maintain numerical stability: (i) we clip the multipliers at 10a-10a (ii) we set the objectives to 0 until all constraints are first satisfied. The pseudocode of the training algorithm can be found in Algorithm I
use the following
2.3 BACKGROUND
In this section we present the local distance and/or topology preserving graph construction methods and losses propose and compare to.
3

---

Under review as a conference paper at ICLR 2023
Stochastic neighbourhood embedding (SNE/ISNE) Instead of preserving topological structures, SNEASNE (Hinton & Roweis 2002; van der Maaten & Himton| (008) proposes to preserve a distribution of distancee/similartiiss for each data point x; and its encoding 2; w.r.t. all/some other data points and encodings, respectively. This formulation allows the authors to use multi-modal encodings, however, in most applications SNEASNE is still used with unimodal encoding.
For each data point 2, E Xb, SNEASNE defines the probability of z being a potential neighbour of 2y as Pij: = k(z,, //)/ A(z,, m2)). where k(.,-) is some distance or dissimilarity based kernel function, (i) set or possible neighbours according to some neighbourhood graph G. In this paper we use fully connected graphs. Although several methods using sparse graphs have been developed for large datasets, using full matrix is feasible in stochastic batch gradient setting. To compute the probabilities we use the Student/Cauchy kernel k( 22) ) = 1/(1 + 8 |2, - =))l²) proposed in (van der Maaten & Hinton (008). The probability distributions in the latent space defined similarly (0) = k(zi, 2/)/(2
zj)), where, in case of auto-encoder models (E)EN(()) k(zz; /))/(_/
we have 2, = =(xx;, E f(x;), while in case of generative models we have ((2;zy). Unlike in (van der Maaten & Hinton 2008), based on practical considerations, here we the use symmetrised KL instead of symmetrised probabilities, and define the loss as L(Ø; X Z,)
q(2; ((z; 2j
(KL (Ip, (6)] + (L(p), IP:.D
Uniform manifold approximation and projection (UMAP) UMAP (Melnnes et al. 2018 Sainburg jet al.] 2021) follows similar approach as SNEASNE in the sense that it constructs weighted sparse graph and defines a corresponding cross entropy based loss between the weights corresponding to the data X,, and its encoding Zb. The cross-entropy computed via negative sampling and it only takes into account the graph constructed based on the data Xz. The authors prove that their weighted graph captures the underlying geometric structure of the data in a faithful way by using concepts from category theoretic approaches to geometric realisation of fuzzy simplical sets (Spivak 2009). The graph in the data space is constructed using symmetrised weighted kNN graph. UMAP assigns the weights waj ag exp{ max(0, d(z,, xz) - min, d(z;, xz))} where the scaling o, is defined such that E, Waj = log, (k) in a kNN graph. This weight matrix is then symmetrised according to vi = Wieg + Wye W.y W.. The weights for the encodings Z₁ are then computed similarly, albeit using W,y 1/(1 + alle; - 2, (|2b) with a, b fitted based on theoretical assumptions. Due to the special edge-based batching schedule and loss computation of the parametric UMAP method in (Sainburg) ct al. 202T), we did not implement this method but used the open-source implementation instead.
Vietoris-Rips complex (VR) Moor et al. (2020) propose the regulariser in equation f an auto- encoder model. The graph construction they propose is based on persistent homologies of Vi- etoris- complexes (VR). A VR complex R. (Xs) associated with the data points in X, at length scale is the set of all folne-con components of the graph constructed based on pairwise e-ball connectivity. As increases the set (X,,) contains more and more fully-connected components sat- urating when finally the whole graph is included. The authors apply persistent homology calculation on R. (X,) to obtain persistence diagrams and persistent pairings based on which one can identify simplices that create or destroy topological features.
It is shown that the for O-dimensional topological features (connected components) the minimum spanning tree corresponding to the data X,, and distance measure dx contains all the topologically relevant edges. The authors show that their method works for higher-dimennional topological features (e.g. cycles, voids) but opt to use only O-dimensional topological features and thus define the graphs 9x, and Gz, as the corresponding minimum spanning trees. We used their publicly available implementation compute these graphs. The method in (Moor et al.) (0220) provides a principled way to define a loss/regulariser that incentivises a topologically faithful encoding of the data together with choice of complexity (dimension of topological features).
2.4 CONTINUOUS K-NEAREST NEIGHBOURS (CKNN)
In contrast to persistent homology where different topological features arise at different length parameters e, [Berry& & Sauer (2019) propose consistent homology showing that it is possible to construct a single unweighted graph from which all topological information of the underlying manifold can be extracted. They propose the continuous k-nearest neighbours graph (CkNN), graph that captures topological features at multiple scales simultaneously. They prove that the unique unweighted graph construction for which the graph Laplacian converges spectrally
4

---

Under review as a conference paper at ICLR 2023
Laplace- Laplace-Beltrami Beltrami operator on the manifold in the large data limit. The method is applied to clustering and image pattern detection via PCA. To the best of our knowledge we are the first to adapt to the context of deep generative models and stochastic batch gradient learning.
Let re(;; k Xx) be the index of the k-th nearest neighbour of x in Xg. Then the CKNN graph over the set Xg is defined via the connectivity (Berry & Sauer 2019)
(x, k) = {i..)) dx (T;, S 8 d(z;, xx)) d(zz, (x(e,,kk))) 24, E X In other words, for 8 = 1, two points are connected if their distance is smaller than the geometric mean of they KNN radius/distance. Using a kNN-based approach has the benefit that it takes into account the local density of the points instead of the e-ball approach that works well only for data uniformly distributed the manifold. In fact it is known for kNN that | (x,kk,, oc p(z) ((z))1/m) 1/m, where p(z) is the sampling density and m is the intrinsic dimension of the data.
As result, CKNN is an instance of broader class of graph constructions for where connectivity is defined by d(z, x' 8lp (o(rr)((z') -1/2mm and has the advantage that one does not have estimate m, see (Berry & Sauer 2019) for further details. This connection is specially interesting in the context of generative models where we learn the latent space and data distributions po(z) and po (z). respectively.
An additional advantage of CkNN is that it seems to be significantly faster to compute when compared to VR. For VR the computation of the minimum spanning tree is required on the (full) distance matrix resulting in On log Obatch)) while for CkNN we only need to compute the smallest & distances for each node, this is only O (n log k) and is also highly paralleliseable. In Figure 1 we show how the wall-clock speeds of the latter two operations compare w.r.t. batch size.
2.5 LEARNING THE PRIOR
To define the prior models po(z) we consider several known approaches with different degree of complexity and computational cost.
The realNVP prior The computationally simplest way to model a prior is to define the latent variable z as an invertible transformation = h((e) of a factorising Gaussian or uniform variable E Rm This allows us to compute log (2 = log (c())) + log |dct(Oc(z)/04)
and therefore
to approximate the KL divergence in equation Ba using a few Monte Carlo samples. Dinh et al. 2k+1
(2117) define z = h(e) as a sequence of K invertible transformations 21:d = 21:d 2f
,.6+1
1a @ exp(s(2()*) + )), (d < m. with lower-triangule 0c(z)/Oz and thus (ogpo(2) can be computed efficiently. Note that & and é need to have the same dimensionality, therefore, in order for the computations to behave well, one should ideally chose latent dimensions for which the encoded data does not need to further projection to lower-dimensional manifold.
2k
The VAMP prior Tomezak & Welling (018) define learned prior in VAE model starting from the observation that the optimal empirical Bayes prior is p" (=) = Epcz) [g)(())));;; which holds for our objective in equation 3a as well. Based on this observation they propose the prior (2( Σn (z( 2; yk.) K with K learnable pseudo-data parameters ./..... ..K. This approach allows us to compute logP)(2) efficiently and thus, to approximate the KL-divergence via sampling as mentioned above. The disadvantage of this definition is that we can only learn priors that can be well modelled with a few elliptical components.
The hierarchical prior VHP A more general approach to learning the prior is to use another hierarchy to model it (Klushyn et al. 2019). that is, to use p=(2) = Po (2(cc) (c(c) de. This makes log po(2) intractable, however, we can further approximate it by using an importance-weighted bound (Burda et al., 2016) on (z(2) like in (Klushyn et al. 2019). This results in replacing KL-divergence also minimise with the same methods. This model is the most flexible choice of prior, however, it is more expensive to fit than the realNVP or the VAMP prior due to the additional level of hierarchy and the resulting bounding and inference step.
objective in equation Bal with upper bound that
3 EXPERIMENTS
Datasets We evaluate our models on the following datasets. Swiss roll and Coil20 are classic datasets for manifold learning. The Human Motion Capture dataset includes both periodic motion (walking
5

---

Under review as a conference paper at ICLR 2023
Jon diteso to
ste momeess wwll
5
VR
CON
KNN
-22
3.04 1400
Figure 1: Top row: (left) the Swiss roll data (3d) with encoding result (2d) from CKNN-NVP, (middle) the KNN distance for the data and the encoding and prior samples resulting from CKNN-NVP model, the distances are plotted w.r.t. the distance along the main axis on the manifold (right) illustrating a bridging vs correct graph construction by plotting the shortest path on the manifold vs in the CKNN graph. Bottom row: graphs construction examples for CKNN with & = 9 and ò = 0.9, KNN with & = 4. (Bottom- right) computation time of Ltopo with the distance matrix input and without back- prckapropagation on batches from Coi120 (32 x 32 pixels). We show the mean 20 runs.
and jogging) and line motion (balancing). from which we can easily observe and identify the topology of the data. Cifarl0 (in the Appendix) is another type of dataset that can be used to evaluate our models in the general case, not limited to known manifolds.
Models The AE-VR and VAE-VR are the models from (Moor al. 2020), and VAE-SNE from (Graving & Couzin 2020). trained with methods in Section 2.2 For comprehensive legend of model labels please check Table in the Appendix.
Evaluation metrics To evaluate our methods, we compute standard metrics on Swiss roll, CMU human motion, and Coil datasets. We use four metries from (Moor et al., (020) to evaluate the models, i.e., MRRE,- MRRE trustworthiness and continuity that are defined as follows. (i) MRRE, (Moor et al. 2020) measures the changes between distance rankings as the data is encoded. The baseline ranking is computed w.r.t. the kNN graph (k = 9) in the data space. (ii) MRRE, (Lee & Verleysen 2009) is the same measure but with the baseline ranking computed w.r.t. the kNN graph of the encodings. trustworthiness Venna & Kaski (2006) evaluates the preservation the i nearest neighbours during encoding while (iv) continuity (Venna & Kaski (006) evaluates for the decoding. Note that all measures are based exclusively the & nearest neighbours and thus might disadvantage somewhat SNE and UMAP. We choose 9 for all experiments. Additionally, since we have the ground truth of the Swiss roll dataset, we compute the linear correlation between the shortest path on the data manifold and Euclidean distance on the latent space. For the Coil20 dataset, the neighbours of an image of an object is given by the camera angles, we compute the linear correlation between the input data and the latent encodings based on this neighbourhood during evaluation. Standard deviations on metrics are computed on 50 MC samples from (2(()))
Table 1: MRRE, MOCAP, smaller better.
Table 2: MRRE,-,; MOCAP, smaller better.
VHP
VAMP
VAE
NVP
VAMP
CINN
0,005
0001)0000)
(L008/0.00))
0.013/0.000
0.004
0.00900000)
0.01
0.006)0.000)) 0.012/0.000 (00)
VR 0,007
000710.000 0.088000000 0.018(0.000) 0.012/0.000)
0.004
0.110000000
0.015 000) 0.06600.00) 0.009(0.000)
SNE
0.007 000110000) 0.027(0.000 0.02((0.000) 0.025(0.000)
0.005
0.04600.01)) 0.03200.011> 0.027(0.000) 0.030/0.000)
UMAP
0.008
UMAP 0.005
Table 3: continuity MOCAP, larger better.
Table 4: trustworthiness on MOCAP, larger better.
VHP
VAMP
VAE
YAMP
CANN
0.997
0,99200 000)
(DO)
( 0.08000 (1995)0.00))
0.999/0000)
(.99X8L000) 0.983/0 (00)
0.996
0.987000 (00)
0.98600 (D0)
01985(0L000)
0.592/0.000)
0,993
0.984/0000)
0.55400.00 (00))
0.983(0.000)
0.99000.000
SNE
0.996
001))0000))
01969)0000))
0.974(0.000)
(0.00
0.994 0.965(0.001) 0.97460.000)
0.976/0.000)
0.972/0.000)
UMAP
0.996
0.993

---

Under review as a conference paper at ICLR 2023
Table 5: Results on Coil20
AE:
AE:
AE:
VAE-
NVP. CENN
VHP- CENN
VAMP.
VAE-VR
NYP-AR
VHP-VR
VAMP-VR
CKNN
VR
SNE
CENN
CENN
MRRF2
0.010
0.048
0,009
0.03110.000 0.017/0.000)
000)
(102)/0000)
01022000000 (0044/0000)
00076/00000
MRRE
0,004
0.010
0.011
0.007/0.000) 0.00510.000)
0,008000000 0.007(0.000)
000)
0,00800 (60) 0.008 (0.000)
0.00900 000)
0.008 (OO)
continuity
0,994
0,988
0.08910.000)
0.992(0.000)
0.98900.00)
0,991 000)
0,991
08900
0,99000.000
trustwort thinesa
8.983
0.940
0,988
0.952(0.000) 0.970(0.000)
0.954(0.000)
(.955/0000)
0.968/0 (00)
0.95000)000)
0.95000 0O0)
0.250(0000))
Hyperparameters We consider as general hyper- parameters the batch size, encoder, decoder and prior architectures, the constraint bounds free and Étopo the annealing rate 17, and a switch variable whether turn on the main objective only after the first constraint satisfaction occurred. Furthermore, for CkNN we consider as hyper-paramett while for t-SNE the length scale. We use the ADAM optimiser (Kingma & Ba 2015) with learning rate 0.001 as implemented in PyTorch (Paszke et al. 2019). For each dataset, we use the same encoder, decoder and prior architectures across on all methods. In the Swiss roll latent space experiment, VR-AE requires larger batch size than the VR-VAE Ee-VAE-basee --sed and CkNN- based models.
the length scale 6, and the number of the neighbours le
Illustrative example: Swiss roll The Swiss roll dataset e.g. (Pedregosa et al.) 2011] is a standard artificial dataset used in non-linear dimensionality reduction and data visualisation which has several properties that can illustrate the benefits and pitfalls of various algorithms. The data is sampled as st ~ M/xx/22 / 3x] x ((0221) and transformed via rff, s) = (t cos(t), s. sin())). It has two properties that are particularly interesting to us: (i) the data is not uniformly distributed on the manifold defined by /3T//2, 3x] x [0, 21] because the density decreases with increasing t; and (ii) the periodic functions give rise to a folding with increasing radius thus confusing nearest neighbour methods when we do not use enough data. The latter manifest itself through the graph constructions choosing connections that "bridge" the manifold.
In the top-middle panel of Figure I we show the kNN distances for each data point and encoding (top and middle) as well as from the learned prior (bottom) when plotted against the main axis of the manifold and the main axis of the 2-d encoding, respectively. We can see that the encoding not only preserves the local distances but also, as a consequence, the density of the data along the main axis. The prior samples also show similar pattern proving that latent space samples have similar KNN characteristics (see appendix A.2 for visualisations of the learned prior). To detect bridging we can compare the shortest path in the graphs to the true shortest paths on the manifold, an example is shown in the top-right panel of Figure | for a low batch size. We compute the true shortest paths by solving numerically the boundary value problems resulting from the corresponding Euler-Lagraage equations. On this dataset CkNN and VR perform similarly well with CkNN performing slightly better. The rest of the methods are unable to recover correctly the 2D manifold. Due to the shape of the manifold they recover this might be due to the bridging effects/too many edges, see AE-SNE results in appendix A.2 As one can expect, the performance of the models is dependent on the chosen batch size. In Figure 5 in the Appendix the Swiss roll dataset using various batch sizes. The higher connectivity of CkNN seems to lead to better performance for smaller batch sizes.
compare the auto-encoder model with VR and CkNN on
We use the Human Motion Capture dataset with 33 sequences of various lengths representing five movements, i.e., walking, jogging, punching, balancing and kicking
Human Motion Capture dataset
Ihttp://mccal cs. cmu. edu.). ). The dataset includes 50-dimensional joint angles following the data-preprocessing in (Chen et al. 2015) and the data is scaled the range [0, 1]. In total, there are 13355 configurations of joint angles which we consider as our dataset. From this dataset, we uniformly select 80 % for training and 20 % for testing. For the training data, we add a Gaussian noise of a 0.03. For this dataset, we use a batch size of 512, & = 9, and for each model, we varied as tlpper-paramett Grees Stopo. 8, and the annealing rate v7.
Tables 3 andFaare the results on human motion dataset. We sample the data from latent space 50 times and obtain the stochastic results in the tables. Generally, we can observe the following. (i) Learning generative models has typically lead to worse metrics than in AE models. We expect that this is due to the additional regulariser arising from learning the prior. (ii) Results for VAEs and hierarchical VAEs comparable with clear advantages only in case of SNE. (iii Generally, CkNN leads to improved metrics when compare to other graph construction methods and losses (SNE and UMAP). The latent representation and the learned priors are shown in the Appendix.
7

---

Under review as a conference paper at ICLR 2023
VR.AE
SNE-AE
VR-NVP
CANN-NVP
SNE-NVP
CKNN-NVP
SNE-NVP
Real world datasets and 2d encodings. Top: the panels show examples form the Human Motion Capture (left) and the Coil-20 (right) datasets. Bottom: Two dimensional projections of samples from the datasets when computed using the shown methods. For the human motion dataset, the models preserves topology walking (magenta) and jogging (yellow) as circles and balancing (green) as lines. For the Coil20, some round objects have no obvious difference with different camera angles, so that they are distributed in small regions. Cars and cuboids similar each other, and distribute next to each other. Note that topological consistency for periodic motions/structures requires closed non-intersecting loops, necessarily circles.
Figure 2:
Coil-20 dataset We use Columbia Object Image Library with 20 objects (Coil-20) (Nene et al. 1996). We sample the data from latent space times and obtain the stochastic results the table. The dataset consists of 72 images of each object that were taken for by uniformly rotating the camera around the object. This results 1440 images in total. The backgrounds were pre-processed to be black, and the images were cropped to 32 32 pixels with grey scale. Since the dataset is small, we use the maximum possible batch size of 1440, = 9, and for each model, we varied Erecs Étopos and the annealing rate 17.
In Table 3 we show the results on Coil-20. We can observe that NVP-CKNN performs generally the best and from the AE models. The round objects which have small amount of pixels changed with different camera angles distribute quite small in the latent space of CkNN-AE. However, more than half of the objects in SNE-AE latent space have obvious size difference. Some objects (e.g.. cuboids) are two circles in the latent space, since they have similar images between the back and front sides. It is reasonable that an object locates into big circle even though they are not similar, since the space there is large enough.
4 RELATED WORK
Manifold learning Manifold learning encompassed large variety of dimensionality reduction methods designed with a different guiding principle compared deep generative models that use an auto-encoding view of Bayesian inference. The methods in manifold learning generally search for neighbourhood structures or define the affinities between points and aim to embedd high-dimensional data into low-dimensional space while conserving some of these properties/aftinttess Methods include, e.g., Locally Linear Embedding (LLE) (Roweis & Saul 2000). Local Tangent Space Alignment (LTSA) (Zhang & Zhal 2004), clutt-diimetioonll Scaling (MDS) (Carroll & Arabie 1998). t-distributed Stochastic Neighbour Embedding (tSNE) (van der Maaten & Hinton] [2008), Uniform Manifold Approximation and Projection (UMAP) (Mcinnes et al. 2018), and Isometric
8

---

Under review as a conference paper at ICLR 2023
Mapping (ISOMAP) (Teeebbaum et al. 2000). Deep generative models generally do not explicitly encode neighbourhood information, however, such properties often emerge. Several follow-up studies combine VAEs and manifold learning. Topo-AE (Moor al.) 2020) and Comnectivity-Optimzzz Representation Learning (Hofer et al., 2019) construct graphs using persistent homology, which preserves the topology between data and latent spaces. In (Schönenberger al. (020) different graph construction method based on witness complexes (Silva & Carlsson] (004) is presented. Their model uses an additional dataset witness dataset for graph construction and non-identical graph construction methods in the data and latent space, respectively Based on Topo-AE, (Li et al. 2021) define local distance preserving invertible encoder-decoder models, VAE-SNE (Graving & Couzin 2020) optimises pairwise similarity between the distributions of the data and latent spaces to preserve the local neighbourhood. Parameterised UMAP (Sainburg et al. 2021 adapts the original UMAP algorithm (projection only) to an AE framework by using neural networks. Neighbourhood Reconstructing Auto-encoder (NRAE) (Lee et al.) 202I) proposed to preserve the neighbourhood structure by minimising the distances between the output of data point on the gradient direction of the decoder and its neighbours.
Constraint optimisation for VAEs VAE models are typically challenging to train due to the difficulty of balancing the reconstruction and compression (KL) term during training (Sønderby et al.. 2016 Alemi al. 2018). Several non-adaptive annealing schedules have been proposed slowly turn on the Kl.-ferms during training e.g. (Sønderby et al., (016) or that anneal according to a task- specific utility function (Higgins al. 2017). Taming VAE (Rezende & Viola 2018) propose to use an annealing scheme derived from a constrained optimisation approach. VaHiPrior (Klushyn al. 2019) adapted (Rezende & Viola 2018) to (two level) hierarchical generative models. In (Zhao et al. 2018) 8) the authors study the constrained optimisation approach in several of VAEs and GAN models establishing formal similarities between ELBO/GAN losses with information theoretic regularisers/constriie
(adapting/fixing the Lagrange multipliers depends on the connection they aim to establish). In our work, we propose a simple (fully fitted) constrained optimisation with the reconstruction and topological losses as constraints. In our experience, this approach significantly improved training performance compared to various combinations of regularisers (fixed multipliers) and KL. annealing schedules.
Learning priors for VA Gaussian prior for VAEs can often lead to over-regularizzttion There- fore, various flexible priors were developed. In (Dilokthanakul et al.) 2016) Gaussian mixture is proposed as the prior. Variational Mixture of Posteriors prior (VampPrior) Tomezak & Welling (2018) learns a prior that is defined based on the optimal empirical Bayes prior using learned pseudo-data. Klushyn et al. (2019) recast learning the prior as learning an equivalent (two level) hierarchical VAE model. We implement a choice of priors with various degree of complexity representing a range of flexibility vs computational complexity tradc-offs.
5 CONCLUSION AND FUTURE WORK
In this paper we propose the CKNN graph construction method for local distance preserving auto- encoder and hierarchical variational auto-encoder models. The CkNN graph is not only inexpensive to compute but it also leads to comparable results when compared to the persistent homology (VR). SNE, and UMAP as shown in Section 3 The additional hyper-parameters and 8 that CKNN requires are typically easy to tune and hence CkNN can represent a viable alternative option. To improve training and to achieve a good balance between different loss terms, we use a constraint optimisation framework that results in syper-parameter (constraint bounds) that are easier to tune than weight parameters in a regularisation setting. Based on the experiments presented in Section 3 conclude that CKNN-AE performs on average better than other AE-based models. CkNN performs well in models with no clear separation of clusters/no clusters in data (e.g. Swiss-roll). CkNN based generative models have an overall good performance among generative models. Flexible priors significantly improve the results of SNE-based models, while they seem to have lesser impact on the metrics in other models. Additionally, the CkNN computation is typically faster than VR. especially for large batch sizes even if it comes with two hyper-parameee that, as we experienced, are easy to fit.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
A. Alemi, B. Poole, I. Fischer, V. Dillon, Saurous, and K. Murphy. Fixing broken ELBO. ICML, 2018.
Berry and T. Sauer. Consistent manifold representation for topological data analysis. Foundations of Data Science, 1(1),1338, 2019.
D. P. Bertsekas. Nonlinear Programming: Second Edition. Athena Scientific, 2003.
Y. Burda, R. B. Grosse, and R. Salakhutdinov. Importance weighted autoencoders. ICLR, 2016.
J. D. Carroll and P. Arabie. Multidimensional scaling. Measurement, judgment and decision making, pp. 179-250, 1998.
N. Chen. J. Bayer, S. Urban, and P. Van Der Smagt. Efficient movement representation by embedding dynamic movement primitives in deep autoencoders. In IEEE-RAS Humamoids, pp. 434-444444 2015.
R. T. Q. Chen, X. Li, R. B. Grosse, and D. K. Duvenaud. Isolating sources of disentanglement in variational autoencoders. In Advances Neural Information Processing Systems, volume 31, 2018.
Xi Chen, Yan Duan, Rein Houthooft, John Schulman, llya Sutskever, and Pieter Abbeel. InfoGAN: Interpretable representation learning information maximizing generative adversarial nets. NeurlPS, 2016.
N. Dilokthanakul, P. Mediano, M. Garnelo, M. Lee, H. Salimbeni, K. Arulkumaran, and M. Shanahan. Deep unsupervised clustering with gaussian mixture variational autoencoders. arXiv preprint 1rXiv:1611.02666 2016.
L. Dinh, Sohl-Dickstein, and S. Bengio. Density estimation using real NVP. ICLR, 2017.
J. M. Graving and I. D. Couzin. Vac-sne: deep generative model for simultaneous dimensionality reduction and clustering. BioRxiv, 2020.
L Higgins, L. Matthey, A. Pal, C. Burgess, X. Glorot, M. Botvinick, S. Mohamed, and A. Lerchner. Beta- MAE: Learning basic visual concepts with constrained variational framework. ICIR, 2017.
G. E. Hinton and S. Roweis. Stochastic neighbor embedding. Advances in neural information processing systems, 15, 2002.
C. Hofer, R. Kwitt, M. Niethammer, and M. Dixit. commeetivity-opiimized representation learning via persistent homology. In International Conference Machine Learning, pp. 2751-2760, 2019.
M. Karl, M. Socich, J. Bayer, and P. van der Smagt. Deep Variational Bayes Filters: Unsupervised Learning of State Space Models from Raw Data. In International Conference on Learning Representations, 2017.
D. P. Kingma and J Ba. Adam: A method for stochastic optimization. In International Conference Learning Representations, 2015.
D. P. Kingma and M. Welling, Auto-encoding variational Bayes. ICML, 2014.
A. Klushyn, N. Chen, R. Kurle, B. Cseke, and P. van der Smagt. Learning hierarchical priors in VAEs, Advances in Neural Information processing Systems, 32, 2019.
A. Klushyn, R. Kurle, M. Soelch, B. Cseke, and P. van der Smagt. Latent matters: Learning deep state-space models. In Advances in Neural Information Processing Systems, volume 34, pp. 10234- 18844-00255,,0 2021.
A. Krizhevsky, G. Hinton, al. Learning multiple layers of features from tiny images. 2009.
N. D. Lawrence and J. Quinomero-Candela. Local distance preservation in the gp-lvm through hack constraints. In Proceedings of the 23rd international conference on Machine learning, pp. 513-520, 2006.
J. A. Lee and M. Verleysen. Quality assessment of dimensionality reduction: Rank-based criteria. Neurocomput- ing.
2009.
Y. Lee, H. Kwon, and F. Park. Neighborhood reconstructing autoencoders. Advances in Neural Information Processing Systems, 34, 2021.
S. Li. H. Lin, Z. Zang. L. Wu, and Stan Z Xia. Jand Li. Invertible manifold learning for dimension reduction. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 713-728, 2021.
10

---

Under review as a conference paper at ICLR 2023
L. McInnes, J. Healy, and Melville. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. ArXiv e-prints, 2018.
M. Moor, M. Horn, B. Rieck, and K. Borgwardt. Topological autoencoders. In International conference machine learning, pp. 7045-7054, PMLR, 2020.
A. Nene, S. K. Nayar, and H. Murase. Columbia object image library (coil-20). 1996.
A. Paszke. S. Gross, F. Massa, Adam Lerer. James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf. Edward Yang. Zachary DeVito. Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Fang, Junjie Bai. and Soumith Chintala. PyTorch: An imperative style, pigo-performance deep lcarning library. In Advances in Neural Information Processing Systems, 8024-8035. 2019.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss,
V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 11-2825-2830 2011.
D. J. Rezende and F. Viola. Taming VAEs. CoRR, 2018.
D. J. Rezende, S. Mohamed, and D. Wierstra. Stochastic backpropagation and approximate inference in deep generative models. ICML, 2014.
Rifai, Y. N. Dauphin, P. Vincent, Y. Bengio, and X. Muller. The manifold tangent classifier. Neural Information Processing Systems, 17, 2011.
T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290 (5500):2323- 2326, 2000.
Sainburg, L. McInnes, and T. Q. Gentner. Parametric umap embeddings for representation and semisupervised learning. Neural Computation, (3(11):2881-2000 2021.
J. W. Sammon. A nonlinear mapping for data structure analysis. IEEE Transactions on computers, 100(5): 401 409, 1969.
T. Schönenberger, A. Varava, V. Polianskii, J. Chung, D. Kragic, and R. Siegwart. Witness autoencoder: Shaping the latent space with witness complexes. In NewrIPS 2020 Workshop Topologicul Data Analysis and Beyond, 2020.
V. de Silva and G. Carlsson. Topological estimation using witness complexes. In SPBG'04 Symposium on Point Based Graphics 2004, 2004.
T. Sønderby, C. K.and Raiko, L. Maalpe, S. K. Sønderby, and O. Winther. Ladder variational autoencoders. NeurlPS, 2016.
D. I. Spivak. Metric realization of fuzzy simplicial sets. 2009.
J. B. Tenenbaum, de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500), 2000.
J. Tomezak and M. Welling. VAE with VampPrior. In International Conference on Artificial Intelligence and Statisticy, pp. 1214-1223. 2018.
L. van der Maaten and G. Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9(11), 2008.
J. Venna and S.I Kaski, Visualizing gene interaction graphs with local multidimensional scaling, In ESANN, pp. 557-562, 2006.
7. Zhang and H. Zha. Principal manifolds and nonlincar dimensionality reduction via tangent space alignment. SIAM Journal on Scientific Computing, 331333333333, 2004.
S. Zhao, J. Song, and S. Ermon. The information autoencoding family: A Lagrangian perspective on latent variable generative models. UAI, 2018
11

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 IMPLEMENTATION DETAILS
Details of the baseline models The graph in AE-UMAP is built only in the data space and uses the whole training dataset. In this method the batch size refers to the number of pairs while other methods are the number of data points. Consequently, the batch size has small influence for the training. On the contrary. in other models the graph are built both in data- and latent- space; using a batch of data points. We use the same batch size for all methods. In Topo-AE in |Moor al. (2020), which we denote by (VR), we use the graph construction and topological loss computation code from https: / thub. com/ Borgwa http://owwaaaaaaa//aaaaaa www.aattttteeeoo logi
concesers In Moor et al. (2020). the topoloical regulariser is computed by summing the loss over the batch data. To avoid the balance between the reconstruction and the regulariser to be influenced by the batch size, we compute the loss by computing the mean over the graph edges. This results in having more informed choices for the constraint bound. The VR-based models count the intersection graphs twice as defined in Moor al. 2020), while our CkNN-based models count only once according Equation (1). This assigns a slightly higher weight to the symmetric difference of the graphs and has no negative effect on training. In the evaluation, except Cifar10, we use the whole test dataset as batch to compute the metrics. In the tables, bold and bold indicates the best results in the AE-based and VAE- based models, respectively. The hyper-parameet search is carried out on a Nvidia DGX (Tesla V100 GPUs, 8 Gbs for each GPU) using Polyaxon 0.6.1 | Our code is implemented using PyTorch 1.9.1. Each experiment uses one GPU.
In Table 6 we show references of the models. All of these models are trained with the methods presented in Section 2.2 except (Sainburg et al. (021). They are identical from the original papers.
Table 6: Models.
AE
VAE
NVP
VHP
Kingms Welling
2014
CLNN
this PoENT
this puper this puper this poper
VR
Mour
X000
Mour et
2020
this paper
SNE
Graving
puper paper
UMAP
Sainburg et al
3021
A.2 SWISS ROLL ON LATENT SPACE
Computing shortest path on the manifold Since for this artificial dataset the manifold is defined by (a(t), yss), xt)) = (t cos(()), s, sin(t)), (t, U337/2357 Mp.211. we can compute the shortest path between two points So) and (1) by finding the functions (((u),s(u)) u E [0, 1] that minimise the functional
((.. = S/' du [i(((T))² + +((()))+
By taking the variation of F w.r.t. s(u) and t(u) and setting them to 0, we obtain two independent differential equations s(u) and t(u)t(u)²+ + (1 (1++2 t(u))((u)
The optimal function s(u) is linear passing through so and 81. We did not find an analytic solution to the equation for ((u) and thus we solved the corresponding boundary value problem numerically (with boundaries 4g and (,).
Dataset We randomly generate 20 training data by sampling t and s. For testing we sample 2048 points, and for the distance comparison we sample 1024 points. We use a batch size Ubatch = 256.
Latent space As shown in Figure 3 AE-CKNN achieves the geometrically most faithful projection of the original manifold across all AE-based models. generative models, CkNN and VR show a consistently faithful projection of both the shape and density of the original manifold. VR-AE models do not achieve a good projection but increasing the batch size can improve the performance. We trained VR-AE with batch size 512, and we have achieved similar results like the best performing models (see Figure 5). Using VAES with learned priors seems to improve the SNE models when compared to VAE-SNE, while the learning the prior has less significant effect on other models.
https://polyaxonn com
12

---

Under review as a conference paper at ICLR 2023
Table 7: MRRE,-22 on Swiss roll, smaller better.
Table 8: MRRE on Swiss roll, smaller better.
AE
VAE
NVP
VHP
VAMP
AE
VAE
NYP
VHP
VAMP
CINN
0.000
0.00018.000)
0.000/0.000) (000)
0.00000.000)
0.08000000)
0.000
0.00000.000) 0.00000.000 (00)
0,000
0.000 (000)
VR
0,000
(L000))0001)
(L800)00000)
(L600V(L000)
(.000000000)
0,000
(U900N(L001)
0.000k0.000)
0.0000000000 0.051:0.001)
1.000:00000
SNE
0,000
0.036/0.00)
0.005(0.001)
0.035(0.001) (.035
0,000
0.009(0.001)
(.04100.001)
0.034(0.001)
UMAP
0.000
Table 9: continuity on Swiss roll, larger better.
Table 10: trustworthiness on Swiss roll, larger better.
AE
VAE
NVP
VII
VAMP
VAE
NVP
VII
YAMP
CKNN
1,000
1,0000.000)
1,000000000
1,0010.000)
1.08000.000
(00)
1,000000000)
(00)
1.00000000)
VR
1,000
L800000000)
1.000)0000) (.0000L000) (.000)))000)
1,000
1.00000000)
1. (.000)
1,000N
(L00))
1.000(1.000)
SNE
1,000
0.9G (.961(0001) (15000O0)) (L560()L
1,000
(U905)L001)
(1966)0000))
0.996500.00) (01) 0:967(0.001)
UMAP
1,000
1,000
Table 11: Linear correlation Swiss roll. Pearsonr linear correlation between the distance in the latent space and distance on the data manifold. 1 or I1 are completely correlated, 0 is not correlated. It is corresponding Figure
AE
VAE
NVP
VHP
VAMP
CINN
1,00
L0000.00 10000,00
1.000.000)
1.0000000)
VR
0.20
1.000.00)
1.000.00)
1.000.000
1.00/0.00)
SNF
0.32
0.46(0.1)
0.44000))
0.72/0.01) 0.85(0.00)
UMAP
0.99
AE-UMAP does reasonably well in recovering the shape but not the density- the width of the high density region (dark blue) distributes larger than the low density area (yellow). AE-UMAP and SNE-based models have distance preserving, therefore, is reasonable that they do not outperform other regularisers. In addition, two failure cases are shown in Figure
Priors Figure 4 shows that the learned priors match well the corresponding latent spaces (Figure 3) both in shape and density. For example, the upper (dark blue) region of Figure [3] has a higher density than the lower (yellow). A similar pattern is present in the data generated from the prior as shown in Figure 4a VHP and VAMP match the shape of the encodings better than NVP in the SNE experiments. Without turning off the KL before first satisfied, the VAMP prior is difficult to be learned, but VHP and NVP are not affected by this option.
Distance in the latent space Figure 6 shows the correlation between the Euclidean distances in the latent space and the distances on the manifold. A straight line in the figure shows that the two distances are correlated. AE-CKNN and VAE-based CkNN and VR models show the best results. AE-UMAP is slightly worse than the best models.
Metries Table 7 and 10 show the standard metrics on the Swiss roll dataset, and Table shows the numerical results of the linear correlation in Figure 6 We sample the data from latent space 50 times and obtain the stochastic results in the tables. CkNNs achieve the best results from all AE-based models, while VR and CkNN are the best in the VAE-based models. The distance correlation has been significantly improved by the learning the priors, although other four metrics of the learned prior for the SNE have similar results as the VAE-SNE.
A.3 LATENT SPACES AND PRIORS ON HUMAN MOTION DATASET
Figures 9 and g show the latent spaces and priors of the human motion experiments of Section 3 We observe similar results like the Swiss roll dataset. The fixed prior in VAE-SNE over-regularisse the posteriors, which results in, for instance, the jogging motion being hardly periodic in the latent space. On the contrary, SNE with learned priors shows clear periodic patterns for walking and jogging, and lines for balancing. The priors have similar shapes and density like the posteriors-the walking density has a higher density than the jogging, since we have more walking samples in the dataset.
13

---

Under review as a conference paper at ICLR 2023
100
-000
-20
200
663
-50
201
AE-CKNN
(b) AE-VR
AE-SNE
(d) VAE-CKNN
(e) VAE-VR
(I) VAE-SNE
60
20
-00
40-
(g) NVP-CKNN
(h) NVP-VR
NVP-SNE
C0-
100
(i) VHP-CKNN
(k) VHP-VR
VHP-SNE
100
100
60
-200
00
10C
100
251
130
(m) VAMP-CKNN
(n) VAMP-VR
(o) VAMP-SNE
-20
(p) AE UMAP
Figure Latent space Swiss roll. The batch size is 256. The color represents rectangle latent space indicates that the model has learned intrinsic properties the Swiss roll. See more details in Section A.2
14

---

Under review as a conference paper at ICLR 2023
10
200
20
-20
20
-10
-10
(a) NVP-CKNN
(b) NVP-VR
(C) NVP-SNE
30
500
K0
50-
-20
-50
50
100
931
(d) VHP--CKN
VHP--V
VHP--SNE
100
100
400
60
-00
(g) VAMP-CKNN
(h) VAMP-VR
ii VAMP-SNE
Figure 4: Learned priors of Swiss roll dataset. The corresponding posteriors are shown in Figure See more details in Section A.2
10
-301
-1001
-50
(a) AE AE-CKNN, 128
(b) AE-CKNN, 256
(c) AEA-E-CNNN CRNN. 512
200
25
200
-121
20C
-00
2001
103
50
(d) AE-VR, 128
AE-VE.. VR, 256
AE-VR, 512
Figure 5: Latent space of Swiss roll with different batch size. Compared with the AE-CKNN, the AE-VR requires larger batch size learn the intrinscc properties of the Swiss roll.
15

---

Under review as a conference paper at ICLR 2023
60
distancs on manffold
80-
distances on manifold
60
600
distance on
12
0.0
2.5
50
300
1000) cistances latent space
distanees in lotent space
distances lotent spoce
(a) AE-CKNN
(b) AE-VEL BE-VR
(c) AE-SNE
diaaancee on manite
16
dusanccs marefed
distancee on manifeld
83
(00
19
0.0
2.5
5.0
0.0
2.5
6.0
datances latert
distarus latant
cistamus
latent
(d) VAE-CKNN
(e) VAE-VR
(l) VAE-SNE
Gieannss on moniald
18
Gistanccs manilld
Beances on monifld
50
01
30
250
500
2/0
dictncess
distancss
(g) NVP-CKNN
(h) NVP-VR
NVP-SNE
disaanes on manitad
diccmncs manifald
dezinss on mansflld
15
0-
100
10
spare
space
(i) VHP-CKNN
VHP-VR
VHP-SNE
distano on munitedd
distuaccss mansfald
distances manvield
90
50
15 80
ar
space:
disancos
SpAce
(m) VAMP-CKNN
(n) VAMP-VR
(0) VAMP-SNE
distanoss manttdd
18 83 8
distanees lotent
AE-UMAP
Figure 6: Comparison of the Swiss roll distances. Linear correlation between the distances indicates that the Euclidean distance in latent space is able to represent the distances the data manifold, The numerical results shown in Table IT See details Section A.2
16

---

Under review as a conference paper at ICLR 2023
3000
2000 2001
Sne-based methods
(b) Local distance preserving- saaeed methods
Figure 7: The latent space of failure cases of Swiss roll dataset. The SNE losses between twisted and untwisted latent spaces have no obvious difference. However, it has obvious difference in the local distance preserving loss. Therefore, even with the cases that the latent representation is difficult to be untwisted using local distance preserving, we can easily select the well trained model. See more details in Section A.2
20
100
(a) NVP-CKNN
(b) NVP-VR
(c) NVP-SNE
I0
(d) VHP-CKNN
VHP-VR
VHP-SNE
100
50-
-10
g VAMP-CKNN
(h) VAMP-VR
(i) VAMP-SNE
Figure 8: Learned priors of human motion dataset. The corresponding posteriors are shown in Figure See more details Section A.3
17

---

Under review as a conference paper at ICLR 2023
331
10
-22
-100
-60
-75
20c
-21
AE-CKNN
(b) AE-VR
AE-SNE
(d) VAE-CKNN
(c) VAE-VR
(f) VAE-SNE
16
-10
16
(g) NVP-CKNN
(h) NVP-VR
NVP-SNE
I
30
-23
VHP-CKNN
(k) VHP-VR
VHP-SNE
10
(m) VAMP-CKNN
VAMP-VR
VAMP-SNE
walking
balancing
-90
jogging
punching
kicking
(p) AE-UMAP
(q) Legend
Figure Latent space of human motion dataset. Except VAE-SNE, other models have clear boarders of the five classes and preserve the topology, i.c., walking and jogging as periodic and balancing as line latent representation. See more details Section A.3
18

---

Under review as a conference paper at ICLR 2023
A.4 RESULTS OF COIL20
In this section, we show additional results from the Coi120 experiments (Section 3). Figure 12 shows examples of the data reconstruction of the models. Figure T0 shows the latent spaces corresponding to the results shown in Table encodings/posseriors.
The learned priors (Figure IT] have similar distribution like the
100
1002
5007
400
-2
-11
(a) AE-CKNN
(b) AE- VR
(c) AE-SNE
21
150
1002
20
500
10
T0
-00
1003
3000
(d) VAE-CKNN
(e) NVP-CKNN
(I) VHP-CKNN
VAMP-CKNN
Figure 10: Latent space of Coil20 dataset. See more details in Section A.4
1300
33
-00-
-500
-50
(a) NVP-CKNN
(b) VHP--KNN
(c) VAMP-CKNN
Figure 11: Learned priors of Coil20 dataset. See the posteriors in Figure 10
See more details in Section A.4
ASVIZAARI
(a) Input data
(b) AE-CKNN
(c) AE-VR
(d) AE-SNE
(e) VAE-CKNN
(1 NVP-CKNN
& VHP-CKNN
(h) VAMP-CKNN
Figure 12: Input data and the reconstruction Coil20. See more details Section A.4
19

---

Under review as a conference paper at ICLR 2023
A.5
EXPERIMENTS ON CIFAR10
Table 12: AE-based models on Cifar10. The results are mean (STD).
AE
AE-CENN
AE VIR
AE: SNE
MRRE, 7X
0.01 (L001)0.000)
(L001(0.000)
0.00740.000)
LMKRE_A XZ
(101)))000)
(.001(0.000) (.001(0.000) 0,007(00000)
1.00000.000)
0.901/0.00
Lonrroothiiness
0.989(0000) 001)
1.000(0.000) 1.000(0.000)
0.903(0.000)
Table 13: VAE-based models Cifar10. The results are mean (STD).
VAB
VAI
NVNN
VII CENN
VAMP VAMP-CKNN
VAE-VE
NVP-VR
VHI-ARR
VAMP-VE
0:128(0:005)
(4002/0.000)
6.012/0.0000
(.00220.000)
0.001(0.000)
0.002/0.000
0.002/0.00)
0.002/00000)
LMRRE_XX NZ
0.0K2(0.004)
(.002(00000))
0.002/0.000)
0.001/0.000) 0.002/0.000)
0.00210.000)
0.001/0.000)
(002((0000))
(1002(00000)
continitty
0.9077000044)
(1.99().000)
(.999(0.00)
(1999/0.000)
0.99%/0.000)
0.999/0.00)
0.999/0.000) 0.999)0.001)
0.999)0.00)
Linsrwormaeess
0.999/0.000)
0.999/0.00)
0.999/0.000)
0.999(0.00))
0.999/0.000)
0.999/e.000)
0.999/0.000)
(a) Input data
(b) AE
(c) AE-CKNN
(d) AE-VR
(e) AE-SNE
VAE
(g) VAE-CKNN
(h) NVP-CKNN
(i) VHP-CKNN
(j) VAMP-CKNN
Figure 13: Input data and the reconstructions of C0far10 with latent dimensions. The reconstruction slightly blurry, we can recognise objects the images. Increasing the latent dimensions or using alternative encoder/generator architectures could reconstruct more accurately, but is not the focus of this paper. See more details in Section A.5
Cifar10 is a standard dataset for classification with 10 classes and 6000 images per class with size 32 32 (Krizhevsky al./ 2009). Here we only consider the image data ignoring the labels. We randomly select 80 % as the training data and the rest is the test data. The encoder and decoder architectures were taken from (https: ////:d//vvlll co--otebookke s. readthedocs i For this dataset,
batch size 512. latent dimension 128, k = 9, and for each model. we varied frec- Stopos 5, and the annealing rate 77.
We use batch size 1000 for evaluation, and obtain the mean and STD of the metrics over batches (see Table 12 and (3). The AEs with manifold constraint have significant better metrics than the vanilla AE, although the AE-SNE yields to the local distance preserved models. Similarly, VAE is not comparable to models with CkNN regulariser.
All models have reasonably good reconstructions (see Figure 13
20

---

Under review as a conference paper at ICLR 2023
(a) VAB
(b) VAE-CKNN
NVP-CKNN
VHP- CEP-CKKNN
(c) VAMP-CKNN
Figure 14: Samples from the prior of Cifarl0. See more details in Section A.5
Furthermore, we generate image samples from the priors using the generative models. Due to the topological regulariser, the posterior does not fit perfectly with the fixed prior (VAE-CKNN); therefore, is challenging to sample meaningful images from the prior (see Figure [4b]. However, NVP-CKNN and VHP-CKNN able to generate images (e.g., dog) which are not in the training dataset.
21

---

Under review as a conference paper at ICLR 2023
A.6 GRAPHS
In this section we show a few illustrative examples about graphs construction. In Figure 15 we show simple dataset with mixture of two uniform distributions; the artificial dataset definition is from (Berr& & Sauer 2019). The mixture distribution results in the two box-shapes having different densities. This gives nise bridging effect mentions in Section 2 of the main text; in standard kNN based approaches low density regions tend to connect to higher density ones due to the lack of close enough similar neighbours. VR constructs a spanning tree thus, as expected, there is only one bridging edge. Since CkNN uses local kNN distances for connectivity it helps to alleviate bridging. Another important property of graph construction is the resulting number of connected components. This can be relevant when we want compute shortest path interpolation in the latent space for visualisation purposes (see (Klushyn et al., 2019)). is often difficult to balance having good enough connectivity and avoid bridging effects. In experience CkNN often manages to find the right balance or is the easiest to tune w.r.t and 8. The results on the boxes and Swiss roll datasets are shown in Figure T6
(a) CKNN
(b) VR
(c) KNN
(d) UMAP
Figure 15: Graphs the two dataset 320 data points. KNN and UMAP graphs we chose = 4, while for CkNN we chose = and = 0.9. The CkNN represents the data structure more accurately and distinguishes the two densities better. Higher & values in kNN and UMAP lead to even more bridging connections while less components lead to more disconnected graphs. See more details in Section A.6
VR:
VI2
MNNYC
MWWC
Figure 16: (left) The umber of components the boxes dataset (see Figure 15) 100 times with random
batch size 320. (right) The number components Swiss roll data over 100 times with random data with batch size 256. See more details in Section A.6
22

---

Under review as a conference paper at ICLR 2023
A.7 ALGORITHM
Algorithm Training algorithm for the generative model (see Section 2
Hyper-parameters: Tebatch Eree: Stapos Trrec Ttopo, InitialPhaseKI, topological hyper-parameters e.g. 6, k:
Constants: Xzect Maopos Mmax maa a
Initialise =
Initialise Avec = Apes
Initialise Asopo X
1opp
Initialise InitialPaaseRec True
Initialise InitialPhaseTTope = True
Initialise InitialPhaseKLL (True or False as HPs))
while training do
Read current data batch X3, of size Thhatch
Sample from variational posterior Ze go(-IX))
Build graphs from X and Za. compute Liee (8, o; X6) and Liopo (0, 0; Xo, 2x)
Compute Cree Lree Free (batch average)
Compute Ctopo = Irtopo Stopo (batch average)
Gree <- (1 a) Grec + Cree. (Croe Crec)
Gropo < (1 a) 8copo + Cree. (ctopo
Croc)
if Croe 0 and haseellPaseeRec then InitialPaaseRec
False
end
Ccapo < 0 and InitialPhase Topo then InitialPhaseTTppo False end if InitialPhaseKI and -nitialPhaseTopo and -InitialPhaseTop Topo then SrriaalPhaseKI.. False
end if if T-InitialPhaseRee then
Aree + Arse exp (Trec Cred)
Arec + clip(Arec, Arec
end if
if InitiialPhaseToppp then
Atopo Atopo (fpop Etopa
Aiepo < clip()topos Atopee)
end if
Compute loss L(0, d)
(Lrec Erec + ALopo {ιopo)
if -InitialPhaseKL then Compute L(B, 6) L(B, KL[ga Xo) po (batch average)
end
update (0) using (0, (()
t <- t
end while
23

---

Under review as a conference paper at ICLR 2023
A.8 ARCHITECTURES
Table 14: AE (or VAE) architectures. FC represents a fully-connected layer. Conv2D and Conv2DT two-D convolution layer and transposed two-D convolution layer, respectively.
DATASET
ARCHITECTURE
SWISS ROLL
INPUT
LATENTS
fer (z(x)
(FC 512, RELU)x3 LAYERS
(x(2))
(FC 512, RELU) x2 LAYERS
HUMAN MOTION INPUT
50
LATENTS
2
fer 66 (z)x)
(FC 512, RELU)x3 LAYERS (FC 512, RELU) x2 LAYERS
9o.Po (x)))((())
Con.20
INPUT
32x32x1
LATENTS
fer (z (x.po(x(2)
(FC 256, RELU) x6 LAYers (FC 256, RELU) x6 LAYERS
CIFAR10
INPUT
32x32x3
LATENTS
128
Jor (2)x))
(CONv2D, GELU) X5 LAYERS, FC FC GELU, (CoNv2DT, GELU, CONv2D, GELU) x2, CONv2DT, TANH.
go, Po (x/z)
As shown in Table A.8 the same encoder and generator architectures used for all models of each dataset. Additionally, the NVP consists of six latent variables, and each variable has three hidden layers, 256 units and residual connections. To improve the performance of the realNVP, use gradient clipping, Softsign activation function, and non-linear output layer. We use three fully connected layers with 256 units and LeakyReLU for po(2|c) of VHP.
24


Reviews:
[{"review_id": "v_80mBGZLT", "reviewer": "Reviewer_n97h", "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": "", "summary_of_the_paper": "This paper introduces several auto-encoder models that preserve local distances when mapping from the data space to the latent\nspace. The proposed models use a local distance-preserving loss that is based on the continuous k-nearest neighbours graph which is known to capture topological features at all scales simultaneously. In order to improve training performance, the models formulate learning\nas a constraint optimisation problem with local distance preservation as the main objective and reconstruction accuracy as a constraint. The proposed method provides state-ofthe-art or comparable performance across several standard datasets and evaluation metrics.", "summary_of_the_review": "Based on the limited novelty and unclear presentation, I am willing to reject this paper.", "strength_and_weaknesses": "Strength: The paper is well written and easy to follow.\nWeaknesses:\n1. The novelty of the proposed method is limited, the proposed method just integrates the previous  local distance-preserving loss into auto-encoders;\n2. In the experiments, the detailed parameter settings of auto-encoders are not clearly introduced.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "NHoVjheLqE", "reviewer": "Reviewer_bRM4", "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": "", "summary_of_the_paper": "This paper proposes an extension of auto-encoder via incorporating the local distance preserving. Specifically, the local distance preserving is implemented by: \n\n(1) constructing two graphs (via CKNN) on the raw features and the learned representations; \n(2) comparing the two graphs via the pairs contained in both two graphs. \n(3) further proposing to optimize a contrained optimization problem for the generative models (e.g., VAE). \n\nThe authors also discuss several cases with different priors.  \n\nSufficient experiments are also reported in both main paper and appendix. \n", "summary_of_the_review": "The main concern is the novelty and some questions about some parts.\n\nI'd like to update my score after the discussion period. ", "strength_and_weaknesses": "## Strength\n\n- The paper is easy to follow. \n- The paper seems technically sound and the authors discuss different situations with diverse prior distributions. \n- The experiments are sufficient for me. \n\n## Weakness\n- My main concern is that the novelty seems not sufficient for me. The constrained optimization for generative models seems well-studied and the idea of local preserving seems widely used. Although this paper may emphasize that the preserving mechanism is built on *distance*, it not a significant contribution for me. Moreover, another key is the utilization of continuous k-nearest neighbors, which may be not a remarkable contribution of this paper. \n- In problem (1), the loss only considers the overlapped links. Should the different links between two graphs be also important for training auto-encoder? Could the author provide some explanations? ", "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": "2O2ifRhxcb", "reviewer": "Reviewer_1cQZ", "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": "", "summary_of_the_paper": "This work proposes a manifold learning strategy based on autoencoders (with a Euclidean distance reconstruction loss) and continuous k-nearest neighbor graphs (CkNN) (with a topological / local distance preservation loss between input and latent space). It implements a constrained optimization where topological loss is minimized such that the reconstruction loss is upper bounded.", "summary_of_the_review": "This is a simple and interesting manifold learning strategy that makes sense but novelty is limited, choices appear to be arbitrary, additional choices are not explored and experimental evaluation is weak.", "strength_and_weaknesses": "\nPros:\n- Paper is well written\n- Method is clear and simple\n- Experiments on a number of datasets\n\nCons:\n- Novelty is limited\n- Choices not motivated or ablated\n- Additional choices not explored\n- Experiments are weak\n\nThe paper is very well written and easy to follow, as a result the method and its evaluation are very clear. The method is simple and found to be effective on a number of datasets.\n\nThe novelty is limited, as the method is merely a combination of existing autoencoders, existing priors and an existing nearest neighbor graph definition.\n\nThe proposed strategy is presented as a fixed recipe, without motivating why the particular choices are made and without ablating either the algorithmic choices or the hyperparameters. The later must have been tuned but no results are given or discussed. This is important because it is unclear if hyperparameters have been also tuned for competitors. The choice of $k=9$ is given as an arbitrary choice, while for the length scale $\\delta$ not even a value is given.\n\nWhy is the topological distance minimized while the reconstruction loss posed as a constraint? Why not vice versa? Why not minimize a function of both?\n\nMore importantly, why use CkNN and why this way? Using CkNN is claimed as a main contribution (\"we are the first to adapt it to...\"). Fixing all other choices made, how would the behavior be affected by any other graph definition? For example:\n- CkNN uses the geometric mean of the kNN distances of x and y in defining an edge between x and y. Why not experiment with the generalized (power) mean, which subsumes the minimum/maximum, the RMS as well as the harmonic, geometric and arithmetic mean among others? Why not any other symmetric function?\n- If the graph definition is so important, why not a weighted graph, which would result in weighted loss terms in eq. (1)? Again, a number of functions could be candidate for the weights.\n\nExperiments are weak. In particular:\n- The datasets used are small (in fact, toy) and the metrics are near perfect if I am not mistaken (assuming perfect value 0 for two of the metrics and 1 for the other two). As a result, the differences between methods are tiny.\n- Tables use bold black and bold blue, which are not explained in the captions. Bold black must be the best but bold blue is unclear. This is misleading because bold blue is chosen for the proposed method.\n- In Table 5 (COIL), SNE is best under 2 of the 4 metrics and in Tables 1-4 (MOCAP) the difference is 0.1%.\n- In Fig. 9 (MOCAP), the latent space of UMAP looks excellent, while in most other cases UMAP is missing from the comparison with no explanation.\n- On Swiss Roll and CIFAR10, metrics are perfect and there is no benefit over VR.\n\nI would expect experiments on more realistic datasets used for unsupervised metric learning, for example CUB, Cars, SOP and InShop. These experiments should also use larger network architectures and include comparison with modern unsupervised metric learning methods.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject