Variational Diffusion Autoencoders with Random Walk Sampling
Authors: Henry Li
Ofir Lindenbaum
Xiuyuan Cheng
Alexander Cloninger
Venue:  (2020)
Keywords: generative models
variational inference
manifold learning
diffusion maps

Abstract: Variational inference (VI) methods and especially variational autoencoders (VAEs) specify scalable generative models that enjoy an intuitive connection to manifold learning --- with many default priors the posterior/likelihood pair $q(z|x)$/$p(x|z)$ can be viewed as an approximate homeomorphism (and its inverse) between the data manifold and a latent Euclidean space. However, these approximations are well-documented to become degenerate in training. Unless the subjective prior is carefully chosen, the topologies of the prior and data distributions often will not match.
Conversely, diffusion maps (DM) automatically \textit{infer} the data topology and enjoy a rigorous connection to manifold learning, but do not scale easily or provide the inverse homeomorphism.
In this paper, we propose \textbf{a)} a principled measure for recognizing the mismatch between data and latent distributions and \textbf{b)} a method that combines the advantages of variational inference and diffusion maps to learn a homeomorphic generative model. The measure, the \textit{locally bi-Lipschitz property}, is a sufficient condition for a homeomorphism and easy to compute and interpret. The method, the \textit{variational diffusion autoencoder} (VDAE), is a novel generative algorithm that first infers the topology of the data distribution, then models a diffusion random walk over the data. To achieve efficient computation in VDAEs, we use stochastic versions of both variational inference and manifold learning optimization. We prove approximation theoretic results for the dimension dependence of VDAEs, and that locally isotropic sampling in the latent space results in a random walk over the reconstructed manifold.
Finally, we demonstrate the utility of our method on various real and synthetic datasets, and show that it exhibits performance superior to other generative models.

Under review as a conference paper at ICLR 2020
VARIATIONAL DIFFUSION RANDOM WALK SAMPLING
AUTOENCODERS
WITH
Anonymous authors Paper under double-blind review
ABSTRACT
Variational inference (VI) methods and especially variational autoencoders (VAEs) specify scalable generative models that enjoy intuitive connection to manifold learning - with many default priors the posterior/likelihood pair ((=|=>\/(<[zz) can be viewed as approximate homeomorphism (and its inverse) between the data manifold and latent Euclidean space. However, these approx- imations are well-documented become degenerate training. Unless the sub- jective prior is carefully chosen, the topologies of the prior and data distributions often will not match. Conversely, diffusion maps (DM) automatically infer the data topology and enjoy rigorous connection to manifold learning, but do not scale easily or provide the inverse homcomorphism. In this paper, we propose a) principled measure for recognizing the mismatch between data and latent dis- tributions and b) a method that combines the advantages of variational inference and diffusion maps to learn homeomorphic generative model. The measure, the locally bi-Lipschitz property, is a sufficient condition for a homeomorphism and easy compute and interpret. The method, the variational diffusion auloen- coder (VDAE), is novel generative algorithm that first infers the topology of the data distribution, then models a diffusion random walk over the data. To achieve efficient computation in VDAEs, we use stochastic versions of both variational inference and manifold learning optimization. We prove approximation theoretic results for the dimension dependence of VDAEs, and that locally isotropic sam- pling the latent space results a random walk over the reconstructed manifold. Finally, we demonstrate our method various real and synthetic datasets, and show that it exhibits performance superior to other generative models.
INTRODUCTION
Recent developments in generative models such variational auto-encoders (VAEs, Kingma & Welling 2013)) and generative adversarial networks (GANs, Goodfellow et al. (2014) have made possible sample remarkably realistic points from complex high dimensional distributions low computational cost. While their methods are very different one is derived from variational inference and the other from game theory their ends both involve learning smooth mappings from a user-defined prior distribution to the modeled distribution.
These maps are closely tied manifold learning when the prior is supported over Euclidean space (e.g. Gaussian or uniform priors) and the data lie on manifold (also known as the Manifold Hypothesis, see |Nrayanan & Mitter (2010); /efferrann et al. (2016). This is because manifolds themselves are defined by sets that have homeonorphisms to such spaces. Learning such maps is beneficial to any machine learning task, and may shed light on the success of VAES and GANs in modeling complex distributions.
Furthermore, the connection to manifold learning may explain why these generative models fail when they do. Known as posterior collapse in VAEs (Alemi et al. al.] 2017 Zhao et al. 2017 He et al.) 2019 Razavi et al., 2019) and mode collapse in GANs (Goodfellow) 2017). both describe cases where the forward/reverse mapping to/from Euclidean space collapses large parts of the input to single output. This violates the bijective requirement of the homeomorphic mapping. It also results in degenerate latent spaces and poor generative performance. A major cause of such failings is when

---

Under review as a conference paper at ICLR 2020
Mx
2/
~ 20(211z)
x
V
Mz
[o(=|z))==N((ee)) (z
Mx)
Ca(2x)
R m
IR
Figure 1: A diagram depicting one step of the diffusion process modeled by the variational diffusion autoencoder (VDAE). The diffusion and inverse diffusion maps v eh-,, well the covariance C of the random walk on Mz, are all approximated by neural networks.
the geometries of the prior and target data do not agree. We explore this issue of prior mismatch and previous treatments of it in Section 3
Given their connection to manifold learning, it natural look to classical approaches in the field for ways to improve VAEs. One of the most principled methods is spectral learning (Schölkopf jct al. 1998; Roweis & Saul, 2000 Belkin Niyogi 2002) which involves describing data from manifold X C .Mx by the eigenfunctions of kernel on Mx. We focus specifically where Coifman Lafon (2006) show that normalizations of the kernel approximate very specific diffusion process, the heat kernel over MMx. A crucial property of the heat kernel is that, like its physical analogue, it defines a diffusion process that has a uniform stationary distribution - in other words, drawing from this stationary distribution draws uniformly from the data manifold. Moreover, Jones et al. (2008) established another crucial property of DMs, namely that distances in local neigh- borhoods the eigenfunction space are nearly isometric to corresponding geodesic distances on the manifold. However, despite its strong theoretical guarantees, DMs are poorly equipped for large scale generative modeling as they are not easily scalable and do not provide an inverse mapping from the intrinsic feature space.
DMs,
In this paper we address issues in variational inference and manifold learning by combining ideas from both. Theory in manifold learning allows us to better recognize prior mismatch, whereas variational inference provides method learn the difficult to approximate inverse diffusion map.
1) We introduce the locally bi-Lipschitz property, sufficient condition for homeomorphism, for measuring the stability of a mapping between latent and data distributions. 2) We introduce VDAEs, class of variational autoencoders whose encoder-decoder feedforward pass approximates the diffusion process on the data manifold with respect to a user-defined kernel k. 3) We show that deep neural networks networks approximating this process produce random walks that have certain desirable propertics, including well defined transition and stationary distributions. 5) Finally, of the VDAE framework on a set real and synthetic datasets, and show that they have superior performance and satisfy the locally bi-Lipschitz property where GANs and VAEs do not.
Our contributions:
capable of learning such diffusion processes, and 4) that
demonstrate the utility
BACKGROUND
Variational inference (VI. Jordan et al. (1999); Wainwright et al. (2088) is a machine learning method that combines Bayesian statistics and latent variable models to approximate some probabil- ity density p(z). assumes and exploits a latent variable structure in the assumed data generation process, that the observations p(x:) are conditionally distributed given unobserved latent vari-
2

---

Under review as a conference paper at ICLR 2020
ables z. By modeling the conditional distribution, then marginalizing over 2, as in
pe(x) po po(x=2))(()d)s
(1)
we obtain the model evidence, or likelihood that I could have instead been drawn from pe (z). Maximizing Eq. leads an algorithm for finding likely approximations of p(z). As the cost
of computing this integral scales exponentially with the dimension of 2, we instead maximize the evidence lower bound (ELBO):
log (og)o(z) 2 -DxL((()(=)ll(e)) + Bz-g(=la) [log pe pe (r|z)],
(2)
where ([=[æ) is usually an approximation of pe(z Optimizing the ELBO is sped up by taking stochastic gradients (Hoffman et al. 2013), and further accelerated by learning global function
approximator qø in an autoencoding structure (Kingma & Welling 2013).
Diffusion maps (DMs. Coifiman & Lafon (006)) on the other hand, are class of kernel methods that perform non-linear dimensionality reduction on a set of observations X S .Mx, where .Mx is the data manifold. Given a symmetrie and positive kernel k DM considers the induced random walk on the graph of X, where given 2, y E X, the transition probabilities p(y[æ) = p(r, y) are row normalized versions of k= y). Moreover, the diffusion map y embeds the data X R into the Euclidean space IR so that the diffusion distance is approximated by Euclidean distance. This powerful property, it allows the arbitrarily complex random walk induced by k on Mx to become an isotropic Gaussian random walk on ()Mx).
SpectralNet an algorithm introduced by algorithm in Shaham et (2018b) speed up the dif- fusion map. Until recently, the method t/ could only be computed via the cigendecomposition of K. As result, DMs were only be tractable for small datasets, or on larger datasets by com- bining landmark- (2018b) propose approximations of the function v itself in the case that the kernel k is symmetric. In particular, we will leverage SpectralNet to enforce our diffusion embedding prior.
estimates and Nystrom approximation techniques. However, (Shaham et al.)
Locally bi-lipschitz coordinates by kernel eigenfunctions. (Jones al. (2008)) analyzed the con- struction of local coordinates of Riemannian manifolds by Laplacian eigenfunctions and diffusion map coordinates. They establish, for all x E X, the existence of some neighborhood (zx) and d spectral coordinates given (xr) that define a bi-Lipschitz mapping from U (x) to Rd With smooth compact Riemannian manifold, (x)) can be chosen to be a geodesic ball with radius a constant multiple of the inradius (the radius of the largest possible ball around x without intersecting with the manifold boundary), where the constant is uniform for all v, but the indices of the spectral coordinates well the local bi-Lipschitz constants may depend on x. Specifically, the Lips- chitz constants involve inverse of the inradius at æ multiplied again by some global constants. For completeness we give simplified statement of the Jones et al. (2008) result the supplementary material.
Using the compactness of the manifold, one can always cover the manifold with m many neighbor- hoods (geodesic balls) on which the bi-Lipschitz property in Jones et al. (2008) holds. As a result, there are total of spectral coordinates, < md (in practice D is much smaller than md, since the selected spectral coordinates in the proof of Jones al. (2008) tend to be low-frequency ones, and thus the selection on different neighborhoods tend to overlap), such that on each of the m neigh- borhoods, there exists a subset of d spectral coordinates out of the D ones which are bi-Lipschitz on the neighborhood, and the Lipschitz constants can be bounded uniformly from below and above.
3 MOTIVATION AND RELATED WORK
Our proposed measure and model is motivated by degenerate latent spaces and poor generative performance in variational inference framework arising from prior mismatch: when the topologies of the data and prior distributions do not agree. In real world data, this is usually due to two factors: first, when the dimensionalities of the distributions do not match, and second, when the geometries do not match. It is easy to see that homeomorphisms between the distributions will not exist in either case: pointwise correspondences cannot be established, thus the bijective condition cannot be met. As a result, the model has poor generative performance for each point not captured in the pointwise correspondence, the latent generated distribution loses expressivity.
3

---

Under review as a conference paper at ICLR 2020
Though the default choice of Gaussian distribution for p(z) is mathematically elegant and computa- tionally expedient, there are many datasets, real and synthetic, for which this distribution is ill-suited. It is well known that spherical distributions are superior for modeling directional data (Fisher al. Mardia 2014), which can be found in fields as diverse as bioinformatics (Hamelryck et al., 2006 geology PPee al. 200T), material science (Krieger Lassen et al., (994), natural image pro- cessing (Bahlmann, 2006). and simply preprocessed datasets" Additionally observe that no home- omorphism exists between & and 8 for any k. For data distributed on more complex manifolds, the literature is sparse due to the difficult nature of such study. However, the manifold hypothesis is well-known and studied (Narayanan & Mitter 2010; Fefferman et al. 2016).
1993
Previous research on alleviating prior mismatch exists. Davidson et al. (2018); Xu & Durrett (2018)
consider VAEs with the von-Mises Fisher prior, a geometrically hyperspherical prior. (Rey et al,, 2019) further model arbitrarily complex manifolds as priors, but require explicit knowledge of the manifold (i.e. its projection map, scalar curvature, and volume). Finally, (Toezzk & Welling (2017) consider mixtures of any pre-existing priors. But while these methods increase the expressivity of the priors available, they do not prescribe a method for choosing the prior itself. That responsibility still lies with the user.
Convserly, our method chooses the best prior automatically. To our knowledge, ours is the first to take data-driven approach to prior selection. By using some data to inform the prior, we not only guarantee the existence of a homeomorphism between data and prior distributions, we explicitly define it by the learned diffusion map v).
4 METHOD
In this section we propose VDAEs, variational inference method that, given the data manifold Mx, observations C Mx, and a kernel k, models the geometry of X by approximating a random walk over the latent diffusion manifold Mz ((M))). The model is trained by maximizing the local evidence: the evidence (i.e. log- log-likelihood) of each point given its random walk neighborhood. Points generated from the trained model by sampling from x, the stationary distribution of the resulting random walk.
Starting from some point E X, of three functions: 1) the approximate diffusion map vhe : MMx Mz. 2) a sampling procedure from the learned diffusion process z' (='lx)) (1)e( C+) on Mz, and 3) the learned inverse diffusion map wi-1 .M + MM that produces x' ~ p(a'|z') = (1 1 (z'), el) where the constant is user-defined and fixed.
roughly deseribe one step of the walk the composition
We rely crucially on three advantages of our latent space dh (X): : a) that it is well-defined (given the first D eigenvalues of k are distinct), b) rell-approximated (given SpectralNet) and e) that Euclidean distances in Mz approximate single-step random walk distances on Mx (see Secction and Coifman & Lafon (2066)) Thus the transition probabilities induced by k can be approximated by Gaussian kernels in M2.
Therefore, to model a diffusion random walk over Mz, we must learn the functions the 3i C that approximate the diffusion map, its inverse, and the covariance of the random walk on Mz, at all points 2 E Mz. SpectralNet gives the To learn Jo and Co, we variational inference.
4.1 THE LOWER BOUND
Formally, let us define Ua, := Ba(a, 8) to d(.,),, the diffusion distance on Mz. For each æ E X, we define the local evidence of x as
n Mx, where Ba(x, 8) as the d-ball around with respect
E Eesel(l/) log (e [r),
I Any dataset where the data points have been normalized be unit length becomes subset of hyper- sphere.
Importantly, note that the choice of Gaussian kernel in the latent space is not dependent on the choice of kt. We have this invariance due to the aforementioned property of diffusion embeddings.
4

---

Under review as a conference paper at ICLR 2020
where p(r'(æ))lu, is the restriction of p(a1(z)) to Ug. The resulting local evidence lower bound is:
log po (2 2 - -D (
+ (etrng((s"la) log pa p=)
(4)
divergence of random walk distributions
neighborhood reconstruction error
Note that the neighborhood reconstruction error should be differentiated from the self reconstruction eπror that is in VAEs. Eq. produces the empirical loss function:
LOVAE - DKL (=' [>)) (=)(==)()))))))))))))))))))))( + log pe (x'|=(),
(5)
where oं = (1, G). G (N I)- 9s.e is the deterministic, differentiable function, depending on vie and Ci,, that generates 2o by the reparameterizatioon trick (Kingma & Welling 2013).
Algorithm VDAE training
θ, 0 <- Initialize parameters
Obtain parameters θ for the approximate diffusion map the by Shaham al. (2018b) while not converged do
A Random minibatch from X
for x E A do
z' ~ ( (z))
Take one step of the diffusion random walk
f- arg min (e (v) =
Find approximate nearest neighbor(s)
g J V s. log pa (x)(xz)
Compute gradients of the loss, i.e. Eq. equation
Update o, using g
4.2 THE SAMPLING PROCEDURE
Here we discuss the algorithm for generating data points from p(æ). Composing qa(2' (r) po(2'(<r) (r)) with (x²1²²²) gives us an approximation of (x(((x). Then the simple, parallelizable, and fast random walk based sampling procedure naturally arises: initialize with an arbitrary point
on the manifold æo .Mx, then pick suitably large N and for n 1,...,N draw Fn ~ p(r -1)) Eventually, our diffusion random walk converges on stationary distribution æ. By Coifman & La- fon (2006), this is guaranteed to be the uniform distribution on the data manifold. See Section 6.2 for examples of points drawn from this procedure.
4.3 A PRACTICAL IMPLEMENTATION
We now introduce practical implementation VDAEs, considering the case where ve(x)), (3 and 2=('22²') are neural network functions, as they are in VAEs and SpectralNet, respectively.
The neighborhood reconstruction error. Since (=(2'(a:) models the neighborhood of (x),
we may sample qo to obtain z' (the neighbor of in the latent space). This gives po pa (x)
J (q)(2((x)) where 1-- exists due to the bi-Lipschitz property. We can efficiently approximate r' Mx by considering the closest embedded data point ( E Mz to z' (e(a') This is because Euclidean distance on Mz approximates the diffusion distance on Mx. In other words, x' po(allan (x)) -- (qo(=1lx)) which we approximate empirically by
x' = arg min aig DEΛ
(V))))), ~'~ "~
where X the training batch.
On the other hand, the divergence of random walk distributions - -Drr(gs (z' (=)x=)]lo=(()))))) can be modeled simply as the divergence of two Gaussian kernels defined on Mz. Though (= is intractable, the diffusion map vi gives the diffusion embedding Z, which is approximation of the true distribution of pe (z' [x) in a neighborhood around = (x). We estimate the first and
Thoough g depends on e and θ we will use go qo.a be consistent with existing VAE notation and to indicate that not learned by VI.
5

---

Under review as a conference paper at ICLR 2020
second moments of this distribution in RD by computing the local Mahalanobis distance of points in the neighborhood. Then, by minimizing the KL divergence between (=(22(2)) and the one implied by this Mahalanobis distance, obtain the loss:
a
Dxx (xxx(<<2/|=>)1l (=)(==) log
+ d tr(((aL))-CC.h
Cs
where Ca a neural network function, (x) (ov(Ba()(1)) n Z) is the covariance of the points in a neighborhood of 2 (x(x) Z. and a is scaling parameter. Note that Cz(x) does not have be diagonal, and in fact most likely not. Combining Eqs. [ 7 we obtain Algorithm
Now we consider the sampling procedure. Since we use neural networks to approximate (o(2'|z)) and po (a' [=)==",, the generation procedure is highly parallelizable. We empirically observe the random rapid mixing properties it does not take many iterations of the random walk to sample from all of Mz This leads to Algorithm 2
walk enjoys rapid
Algorithm VDAE sampling
Xo Initialize with points Xo X & -+0 0
while p(Xp) # π do for E X, do
2+ Po (2((211)(>x)))))) T1 po 21
Take one step of the diffusion random walk Map back into input space
THEORY
We theoretically prove that the desired inverse map 1 from spectral coordinate codes back to the manifold can be approximated by decoder network, where the network complexity is bounded by quantities related to the intrinsic geometry of the manifold. This section relies heavily on the known bi- bi-Lisschitz property of DMs Jones et al. 2208), which we approximating with the VDAE latent space without the need for regularization.
5.1 THEOREMS
The theory for the capacity the encoder to map M to the diffusion map space (MM has already been considered in (Shaham al. (2018a) and Mishne al. (2017). We instead focus the decoder, which requires a different treatment. The following theorem proved in Appendix A.3 based upon the result in Jones al. 2008).
Theorem 1. Let Mx C. R be smooth d-dimensional manifold, (MMx C. R be the diffusion map for D 2 large enough to have a subset of coordinates that are locally bi-Lipschitz. Let X = [X,, ... Xm) be the set of all m extrinsic coordinates of the manifold. Then there exists sparsely-connected ReLU network fN, with 4DC nodes in the first layer, 8dmN nodes in the second layer, and 2mN nodes in the third layer, and m nodes in the output layer, such that
[((b(a)) (x(((())))
S //CC//N
(8)
where the norm is interpreted as ||FI == [[II Here Cy depends on how sparsely X (v(x))),, can be represented in terms of the ReLU wavelet frame on each neighborhood U. and CM on the curvature and dimension of the manifold Mx.
Theorem is complementary to the theorem in Shaham al. (2018)) which provides guarantees for the encoder, as Theorem [ demonstrates similar approximation theoretic argument for the decoder. The proof built on two properties of ReLU neural networks: 1) their ability split curved domains into small, almost Euclidean patches, 2) their ability to build differences of bump functions
Forr all experiments in Section 6 the number of steps required draw from is less than 10.

---

Under review as a conference paper at ICLR 2020
VDAE
SVAE
VAE
GAN
Figure 2: Reconstructed images from the rotating bulldog example plotted in the latent space of VDAE (left). Spherical VAE (SVAE, left-middle) and VAE (right-middle), and GAN (right) on each patch, which allows one to borrow approximation results from the theory of wavelets on spaces of homogeneous type. The proof also crucially uses the bi-Lipschitz property of the diffusion embedding Jones et al. 2008). The key insight of Theorem [ is that, because of the bi-Lipschitz property, the coordinates of the manifold in the ambient space RT can be thought of as functions of the diffusion coordinates. We show that because each of coordinates function X, is Lipschitz function, the ReLU wavelet coefficients of X; are necessarily f², This allows us to use the existing guarantees [Shhham et al. (2018)) to complete the desired bound.
We also discuss the connections between the distribution at each point in diffusion map space, g0(2|z)) and the result of this distribution after being decoded through the decoder network (2) for = ~ go (= Similar to Singer & Coifman (2008), we characterize the covariance matrix (o)(fx(z)) == E2 ELEnn(s/=)]f (eeentt)))lll(())((((()))) The following theorem is proved in Appendix A.3
Theorem Let SN be a neural network approximation to X as in Theorem such that approximates the extrinsic manifold coordinates. Let C E Rmxm be the covariance matrix Let (s(2|z) ~ (V(()),)) E) with small enough Σ that there ex- ists patch U'o .M around zo satisfying the bi-Lipschitz property Jones et al. (208)), and such that Pr(z ~ (2(2) & (UU2z)) < e. Then the number of eigenvalues of C greater than e is at most d, and C = EJ + O(e) where Jon is the m x D Jacobian matrix at 20-
C- (E=eg_)st:lllx(()fxee))
Theorem 2 establishes the relationship between the covariance matrices used in the sampling pro- cedure and their image under the decoder fN to approximate e e- Similar to Singer & Coifman 2008), we are able sample according to multivariate normal distribution in the latent space. Thus, the resulting cloud in the data space is distorted (to first order) by the local Jacobian of the map fN. The key insight of Theorem is from combining this idea with the observation of Jones ct al. 2008) that vi depends locally on only d of the coordinates in the D dimensional latent space.
6
EXPERIMENTAL RESULTS
6.1 VIDEO OF ROTATING FIGURE
We consider the problem of generating new frames from a video of rigid movement. We take 200 frames of a color video (each frame is 100 x 80 x 3) of a spinning bulldog [Lederman & Talmon 2018 Due to the spinning of figure and the fixed background, this creates a low-dimensional approximately circular manifold.
We compare our method to VAE, the Wasserstein GAN Gulrajani et al. (2017) (with bi-lipchitz constraint on the critic), and the hyperspherical VAE Davidson et al. (018)) For the VAE, we use a two dimensional Gaussian prior Pe (z). such that = NNO, /2). The noise injected the GAN is drawn from a two dimensional uniform distribution p2)),, such that 2; ~ (0, 1), = 1, For the spherical VAE, we use a latent dimension of D 2, which highlights the dimension mismatch issue that occurs with a spherical prior. This is a benefit of VDAE, even if we choose D > d the latent embedding will still only be locally d dimensional. We use the same architecture for all networks which consists of one hidden layer with 512 neurons, activation function for all networks are tanh. In Fig. 2 we present 300 generated samples, by displaying them on a seatter plot with coordinates corresponding to their latent dimensions and Z2.
6.2 DATA GENERATION FROM UNIFORMLY SAMPLED MANIFOLDS
In this series of experiments, we visualize the results of the sampling procedure in Algorithm 2 on three synthetic manifolds. As discussed in 4.2 we randomly select initial seed point, then
7

---

Under review as a conference paper at ICLR 2020
Figure 3: An example of distributions reconstructed from a random walk on My (via Algorithm 2). given single seed point drawn from X. (Bottom): An example of single burst (2t [z|2). The distributions are loop (left), sphere (middle), and the Stanford bunny (right).
recursively sample from (=(x'(>) [x) many times simulate random walk on the manifold. In the top row of Fig. 3 we highlight the location of the initial seed point, take 20 steps of the random walk, and display the resulting generated points three learned manifolds. Clearly after large number of resampling iterations, the algorithm continues to generate points on the manifold, and the distribution of sampled points converges to a uniform stationary distribution on the manifold. Moreover, this stationary distribution is reached very quickly. In the bottom row of the same Fig, 3 we show po (a' (a:) by sampling large number of points sampled from the single seed point. can be seen, single step of (o covers large part of the latent space. The architecture also uses one hidden layer of 512 neurons and tanh activations.
6.3 CLUSTER CONDITIONAL SAMPLING
In this section, deal with the problem of generating samples from data with multiple clusters in an unsupervised fashion (i.e. no priori knowledge of the cluster structure). Clustered data creates problem for many generative models, as the topology of the latent space (i.e. normal distribution) differs from the topology of the data space with multiple clusters.
In our first experiment, show that method capable of generating lar cluster given an input point from that cluster. This generation is done in an unsupervised fashion, which is different setting from the approach of conditional VAEs Sohn al. (2015) that require training labels. We demonstrate this property on MNIST in Figure 4 and show that the newly gen- erated points after short diffusion time remain in the equivalent class to the seeded image. Here the architecture is standard fully convolutional architecture. Details can be found in Appendix A.4
points from a particu-
2
3
333
3
8
8
8
8
7
9
9
2222
33
5
3
8
8
8
8
7 9
9
9
2222
3 3 3 5
8 8
8 8
4 9
7
9
2222
3
3
3
3
8
8
8
8
9
9
9
Figure 4: An example of cluster conditional sampling with our method, given a seed point (top left of each image grid). The DVAE is able produce examples via the random walk that stay approximately within the cluster of the seed point, without any supervised knowledge of the cluster.
The problem of addressing difference in topologies between the latent space of generative model and the output data has been acknowledged in recent works about rejection sampling (Azadi et al. 20188 Turner et al. 2018). Rejection sampling of neural networks consists of generating a large collection of samples using standard GAN, and then designing probabilistic algorithm to decide in post-hoc fashion whether the points were truly in the support the data distribution p(r).
In the following experiment, compare the standard example in the generative model literature. The data consists of nine bounded spherical densities with significant minimal separation, lying on 5 x 5 grid. A standard GAN VAE struggles to avoid generating points in the gaps between
8

---

Under review as a conference paper at ICLR 2020
Figure 5: Comparison between GAN, DRS-GAN, and our samples on a x 5 Gaussian grid. GAN and DRS-GAN samples taken from Azadi et al. (2018). Shown from left-right are Original, GAN, DRS-GAN, and our method.
these densities, and thus requires the post-sampling rejection analysis. On the other hand, our model creates latent space that separates each of these clusters into their features and only generates points that exist in the neighborhood of training data. Figure [5] clearly shows that this results in significantly fewer points generated the gaps between clusters, as well as eliminating the need to generate additional points that are not in final generated set. Our VDAE architecture here uses one hidden layer of 512 neurons and tanh activations. GAN and DRS ORS-GAN architectures are as described in Azadi et al. 2018).
Table 1: Mean and standard deviation of the local bi-Lipschitz constant, local to k-nearest neighbor- hoods on MNIST where 3, 5, 10, 100, 1000. Lower is better.
Method
k=3
5
10
100
1000
GAN
2.24 + 0.35
2.32
0.29
2.5 = 0.34
2.8 + 0.42
3.11 0..44
VAE
8.63 + 2.53
8.93
+ 2.55
9.17 + 2.59
9.51 + 2.64
9.78 + 2.6
SVAE
47.2 + 19.1
50.3
+ 19.0
52.6 - 19.1
55.2
+ 19.5
58.5 19.4
VDAE
1.92 + 0.5
2.05 + 0.49
2.22 = 0.50
2.64 = 0.52
2.87 = 0.516
6.4 EMPIRICAL EVALUATION OF THE LOCAL B1 BI-LIPSCHITZ MEASURE
Here we describe a practical method for computing the local bi-Lipschitz property, then use it to evaluate several methods the MNIST dataset. Let Z and X be metric spaces and f Z + X. We define, for each z E Z and E N. the function bilipı(2):
dx dx(f()) SK.V UZAN2
bilipx(2)
min K s.t. S
dz(2,z")
where Z := f- is the latent embedding of our dataset X 5 dx and dz are metries on and Z. and Uz.1 is the k-nearest neighborhood of Intuitively, increasing values of K can be thought of as an increasing tendency of the learned map to stretch or compress regions of space. By analyzing various statistics of the local bi- bi-Lipschitz measure evaluated at all points of a latent space Z. can gain insight into how well- behavee a homeomorphism f is. In Table we report the mean and standard deviation, over 10 runs, of the local bi-Lipschitz property for several methods trained the MNIST dataset.
The comparison is between the Wassertein GAN (WGAN), the VAE, the hyperspherical VAE (SVAE), and our method. We use standard architectures prescribed by their respective papers to train the methods. For method we use single 500 unit hidden layer network architecture with ReLU nonlincarities for both the encoder and decoder.
By constraining our latent space to be the diffusion embedding of the data, our method finds mapping that automatically enjoys the homeomorphic properties of an ideal mapping, and this is reflected in the low values of the local bi-Lipschitz constant. Conversely, other methods do not consider the topology of the data in the prior distribution. This is especially appparent in the VAE
Foor VAF, SVAF, and our method, these are the means of the posterior distributions. For GAN it is points drawn from the ((0 1) prior.

---

Under review as a conference paper at ICLR 2020
and SVAE, which must generate from the entirety of the input distribution X since they minimize a reconstruction loss. Interestingly, the mode collapse tendency of GANs alleviate the pathology of but this
the bi- bi-Lipschitz constant by allowing the GAN to focus on subset of the distribution comes at the cost, of course, of collapsing to a few modes of the dataset. Our method is able to reconstruct the entirety of X while simultaneously maintaining low local bi-Lipschitz constant.
REFERENCES
Alexander A. Alemi, Ben Poole, Ian Fischer, Joshua V. Dillon, Rif A. Saurous, and Kevin Murphy. An information-theoretie analysis of deep latent-variabl variable models. CoRR, abs/1711.00464, 2017. abs/ 00464
Samanch Azadi, Catherine Olsson, Trevor Darrell, Ian Goodfellow, and Augustus Odena. Discrim- inator rejection sampling. arXiv preprint //Xv:/8//0006788 2018.
Claus Bahlmann. Directional features in online handwriting recognition. Pattern Recognition, 39 (1):115-125, 2006.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in neural information processing systems, pp. 585-591, 2002.
Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, 21(1):5-30, 2006.
Tim Davidson, Luca Falorsi, Nicola De Cao, Thomas Kipf, and Jakub Tomczak. Hyperspheri- cal variational auto-encoders, arXiv preprint arXiv:1804.000 2018.
Charles Fefferman, Sanjoy Mitter, and Hariharan Narayanan. Testing the manifold hypothesis. Journal of the American Mathematical Society, 29(4))983-1049, 2016.
Nicholas Fisher, Toby Lewis, and Brian JJ Embleton. Statistical analysis of spherical data. Cam- bridge university press, 1993.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems (NIPS), volume 27, pp. 2672-2680, 2014.
lan J. Goodfellow. NIPS 2016 tutorial: Generative adversarial networks. CORR, bos//701.0016))
2017. URL hett:://arxiv.orr/abbss.e.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Im- proved training of wasserstein gans. In Advances Neural Information Processing Systems, pp- 5767-5777, 2017.
Thomas Hamelryck, John T Kent, and Anders Krogh. Sampling realistic protein conformations using local structural bias. PLoS Computational Biology, 2(9):e131, 2006.
Junxian He, Daniel Spokoyny, Graham Neubig, and Taylor Berg-Kirkpatrick. Lagging inference networks and posterior collapse variational autoencoders. CoRR, abs/1901.05534, 2019. URL
ptttp://arxive owg. abs 0tabs//900 110191111111 00534
Matthew D Hoffman, David M Blei, Chong Wang. and John Paisley. Stochastic variational infer- ence. The Journal of Machine Learning Research, 14(1):1303-1377 2013.
Peter W Jones, Mauro Maggioni, and Raanan Schul. Manifold parametrizations by eigenfunctions of the laplacian and heat kernels. Proceedings of the National Academy of Sciences, 105(6): 1803-1808, 2008.
Michael Jordan, Zoubin Ghahramani, Tommi S Jaakkola, and Lawrence K Saul. An introduction to variational methods for graphical models. Machine learning, (7(2):183-251 1999.
Diederik Kingma and Max Welling. 1312:6 2013.
Auto-encoding variational bayes.
arXiv preprint
10

---

Under review as a conference paper at ICLR 2020
NC Krieger Lassen, D Juul Jensen, and Knut Conradsen. On the statistical analysis of orientation data. Acta Crystallographica Section A: Foundations of Crystallography, 50(6):741-748, 1994.
Roy R Lederman and Ronen Talmon. Learning the geometry of common latent variables using
alternaiigg-diffusion Applied and Computational Harmonic Analysis, 44(3):509-536, 2018.
Kantilal Varichand Mardia. Statistics of directional data. Academic press, 2014.
Gal Mishne, Uri Shaham, Alexander Cloninger, and Israel Cohen. Diffusion nets. Applied and Computational Harmonic Analysis, 2017.
Hariharan Narayanan and Sanjoy Mitter. Sample complexity of testing the manifold hypothesis. In Advances in Neural Information Processing Systems, pp. 1786-1794, 2010.
David Peel, William J Whiten, and Geoffrey J McLachlan. Fitting mixtures of kent distributions to aid in joint set identification. Journal of the American Statistical Association, 96(453):56633, 2001.
Ali Razavi, Aäron van den Oord, Ben Poole, and Oriol Vinyals. Preventing posterior collapse with delta-vaes. CoRR, abs/1901. 103416, 2019. URLptttp://arxi http://axxx...rr/a//////// 03416
Luis A. Pérez Rey, Vlado Menkovski, and Jacobus W. Portegies, Diffusion variational autocncoders.
CoRR, abs/1901.08991, 2019. URL
Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embed- ding. science, 290(5500):2323 2000.
Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Nonlinear component analysis as kernel eigenvalue problem. Neural computation, 10(5):1299-1311 1319, 1998.
Uri Shaham, Alexander Cloninger, and Ronald Coifman. Provable approximation properties for deep neural networks. Applied and Computational Harmonic Analysis, 44(3):537-557, 2018:
Uri Shaham, Kelly Stanton, Henry Li, Boaz Nadler, Ronen Basri, and Yuval Kluger. Spectralnet: Spectral clustering using deep neural networks, arXiv preprint arXiv:1801.0153 00150887...00.. 2018b.
Amit Singer and Ronald R Coifman. Non-linear independent component analysis with diffusion maps. Applied and Computational Harmonic Analysis, 25(2):226-235 2008
Kihyuk Sohn, Honglak Lee, and Xinchen Yan. Learning structured output representation using deep conditional generative models. Advances neural information processing systems, pp- 3483-3491 2015.
Jakub M Tomezak and Max Welling. Vae with a vampprior. arXiv preprint 1705v:1705.07/11 2017.
Ryan Turner, Jane Hung, Yunus Saatci, and Jason Yosinski. Metropolis-hastingg generative adver- sarial networks. arXiv preprint 181 2018.
Martin Wainwright, Michael I Jordan, al. Graphical models, exponential families, and variational inference. Foundations and Trends(R) in Machine Learning, 1(1-2):1-305, 2008
Jiacheng Xu and Greg Durrett. Spherical latent spaces for stable variational autoencoders. arXiv preprint arXiv: 1808. 10805, 2018
Shengjia Zhao, Jiaming Song, and Stefano Ermon. Infovae: Information maximizing variational au- toencoders. CoRR, abs/ 1 706.020666 2017. URL WtRLhttp: http:///awwww....o////////..... 02262

---

Under review as a conference paper at ICLR 2020
A
APPENDIX
A.1 DERIVATION OF LOCAL EVIDENCE LOWER BOUND (EQ.
4
We begin with taking the log of the random walk transition likelihood,
log (0 ax) log
(A.1)
((²))
= log
pa(2' x))(=1
((2)) de'
(A.2)
po 2.) p(z'(2)) (x)
log
E (
(A.3)
g(21)
log p(=1(x))
2 Eg p logpo(x'1 [2,,))) 2)] + E wele
(A.4)
q(2))
2 Eerr(()") [log po (x'12' 12,1===)) + D D [11==)))(=)
(A.5)
where g(=") is an arbitrary distribution. We let g(=') to be the conditional distribution ((>'(zr). Furthermore, we make the simplifying assumption that po(a') po(2'12'), then we obtain
Eq. logro(<'(23) 2 - DI (1s (=<(o"==)llpoo="(l))) + Berngs(e" log po (x'1=')
(A.6)
A.2 RESULTS JONES AL.
2008
To state the result in Jones et al. (2008), we need the following set-up:
(C1) M is a d-dimensional smooth compact manifold, possibly having boundary, equipped with smooth (at least C²) Riemannian metric g;
We denote the geodesic distance by dmM, and the geodesic ball centering at x with radius r by (M( Under (C1), for each point æ E M, there exists (x) which is the inradius, that is, is the largest number s.t. (M, r) is contained M.
Let AM be the Laplacian-Beltrane operator on M with Neumann boundary condition, which is self-adjoint on (M,, p), μ being the Riemannian volume given by g. Suppose that M is re-scaled to have volume 1. The next condition need concerns the spectrum of the manifold Laplacian
(C2) AM has discrete spectrum, and the eigenvalues do S A1 S satisfy the Weyl's estimate, i.c. exists constant C' which only depends M s.t.
Ii X3 s TH CT
Let 3 be the eigenfunction associated with X3. (biby form an orthonormal bases of L3M p)) The last condition is
(C3) The heat kernel (defined by the heat equation MM) has the spectral representation as
20
Kg (x v)
Dis (z)))))))
j=0
Theorem 3 (Theorem Jones et al. (2008), simplified version). Under the above setting and assume (C1)-(C2), then there are positive constants 6ı, C22 C3 which only depend on M and g. s.t. for any x M, (2(2) being the inradius, there are d eigenfinctions of A "h.,... Vig which collectively give a mapping v M Rdd by
(z(x)= = (v), (x). ,1)(
satisfying that Vy. v' E B(I,
(2T (M S (w) V S -o
That is, W is bi Lipschizt on the neighborhood Bxx, (x))(())) with the Lipschitz constants indicated as above. The subscript x in V, emphasizes that the indices "., ,ja
may depend on x.
12

---

Under review as a conference paper at ICLR 2020
A.3 PROOFS
The proof of Theorem 1 is actually simple extension of the following theo- rem, Theorem which needs to proved for each individual extrinsic coordinate Xx. hence the additional factor of coming from the L2 norm of m functions.
Proof of Theorem 7
D
Theorem 4. Let M C IRm be a smooth d-dimensional manifold, ((M) C IR be the diffusion map for D 2 d large enough to have subset of coordinates that are locally bi- bi-Lipschitz. Let one
of the m extrinsic coordinates of the manifold be denoted X (()(z) for x E M. Then there exists sparsely-connecee
ReLU network IN, with M nodes in the first layer, SdN nodes in the second layer, and 2N nodes in the third layer, such that
CN
| - (xxlllE)(((MM) S
(A.7)
where Cg depends on how sparsely X (1b(x)))o; can be represented terms of the ReLUU wavelet frame on each neighborhood U, and CM on the curvature and dimension of the manifold M.
Proof of Theorem The proof borrows from the main theorem of Shaham al. (018a). We adopt this notation and summarize the changes in the proof here. For a full description of the theory and guarantees for neural networks on manifolds, see Shaham et al. (2018a). Let CM be the number of neighborhoods U; B (x 5) n .M needed to cover M such that Væ. E U.. (1 e)| ||||ar- yll (M v) S (1 + +){lær yll- Here, we choose = min "i x
where 8M is the largest 6 that
preserves locally Euclidean neighborhoods and x=1 p is the smallest value from Jones et al. (2008)
such that every neighborhood U, has a bi-Lipschitz set of diffusion coordinates.
Because of the locally bi-Lipschitz guarantee from Jones et al. (2008), we know for each U, there exists an equivalent neighborhood (U:) in the diffusion map space, where vb(x) (dh, (I), .... (x)]. Note that the choice of these d coordinates depends on the neighborhood U,. Moreover, we know the Euclidean distance on (U,)) locally bi-Lipschitz w.r.t d. on U.
First, we note that as in Shaham al. (2018a). the first layer of neural network capable of using 4D units to select the subset of coordinates (zx) from (xx) for x E U4 and zeroing out the other D d coordinates with ReLU bump functions. Then we can define X (x(()) = (()(x)) on U,.
Now to apply the theorem from Shaham et al. (0188), must establish that X U, ((U)) + I can be written efficiently in terms of ReLU functions. Because of the manifold and diffusion metrics being bi- Lipschitz,, we know a minimum that Ø is invertible on (U;). Because of this invertibiliiyy we will slightly abuse notation and refer to X (1((x)) X (z), where this is understood to be the extrinsic coordinate of the manifold at the point æ that cooresponds to (xx). we also know that Vx, E U.,
(x((()) (((())) = (x(x) - X(v)
max (X(=)lld(z v) =EU;
max:eu,
VX(x)]] [|](()) - +())l..
where (x) is understood to be the gradient of (2) at the point M. This means X (((()) is Lipschitz function w.r.t. (2x). Because X (x(x)) Lipschitz continuous, it can be approximated by step functions on a ball of radius 2 to an error that is at most max.ct; [VVX())]l This means the 1-c [XX(=)] (2- +2 2-14).. This fact, along maximum ReLU wavelet coefficient is less than max 1-c
with the fact that (U,)) is compact, gives the fact that on (U.), set of ReLU wavelet coefficients in él. And from Shaham al. 2a), on a local patch the function is expressible terms of
ReLU wavelet coefficients in ET, then there is an approximation rate of 1 for N ReLU wavelet terms.
JN
13

---

Under review as a conference paper at ICLR 2020
Proof of Theorem 2 We borrow from Singer & Coifman (2008) to prove the following result. Given that the bulk of the distribution q lies inside (U',,) we can consider only the action fN on (U,))) rather than distance on the diffusion coordinates (the metric on the input space), we can use the results from Singer & Coifman (2008) and say that on (Uu))) the output covariance matrix is characterized by the Jacobian of the function fN mapping from Euclidean space (on the diffusion coordinates) to the output space, the point 20. So the covariance of the data lying insize (U(2))) is Jzo E.T with an 50.
the whole space. Because the geodesic
U is bi-Lipschitz w.r.. the Euclidean
(cc) perturbation for the fact that fraction of the data lies outside (U,,.).
The effective rank of being at most d comes from the locally bi bi-Lipschitz property. We know X (vbxz) only depends on the coordinates vxxx) as in the proof of Theorem | which implies fx (x))) satisfies a similarly property if fN fully learned X (#(x)). Thus, while J E RmXD, it is at most rank d, which means JE.J" at most rank d as well.
A.4 EXPERIMENT ARCHITECTURES
A.4.1 CLUSTER CONDITIONAL SAMPLING WITH MNIST
We use the following encoder architecture:
Conv2D(chameel==64, strides=(I,1), kernel=4)
Con strides=(1,1), (tttaaammeedso.44.ttrsssss..... kernel=4)
MaxPoolingg2D(poool size=2)
Conv2DDcchameel==64, (11) kernel=4)
Conn22Dcchammelss44..trdddde kernel=4)
MaxPoolnn2D(ppoossie==2))
Dense(512, 12, 'relu')
Dense(10, 'linear')
and the following decoder architecture: We use the following decoder architecture:
Dense(7 7, 'relu')
Conn22TTanppoeechaaeess66,, strides=(1,1), kernel=4)
Cann27Traaspssschammllddd... strides=(1,1), kernel=4)
UpSSmmiing2D(poolsizzz=)))
CowvDDTraaspoeschannddo66.. (ttiiiilsss..ssddddss(...... kernel=4)
Cown220ranngpseehhaneessdd,, strides=(1,1), kemne==4)
14


Reviews:
[{"review_id": "ryefctiqqH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "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: In this paper, a diffusion-based VAE is proposed. The authors introduced a non-linear dimension reduction method, diffusion map to standard VAE to encode neighborhood manifold information into the latent space before encoding. They proposed a lower-bound objective, similar to original VAE for content generation. \n\nPros: 1) A new VAE method is proposed to incorporate local manifold information into the latent space. 2) A sufficient condition to measure the consensus between latent and input data distributions. 3) Three empirical studies on the visualization of generated images. \n\nCons: \n1) The writing could be significantly improved. There are a bunch of grammar errors and confusing notations. For example, “with many default priors the posterior/likelihood pair q(z|x)/p(x|z) can be viewed as an approximate homeomorphism” ->  “with many default priors,  the posterior/likelihood pair q(z|x)/p(x|z) that can be viewed as an approximate homeomorphism”. “In this paper address issues in variational inference and manifold learning” -> “In this paper, we address issues in variational inference ….”. “feedfoward pass” -> “feedforward” …. In algorithm 1, “X is a random batch from X”. Conditional probability are mixed with joint probabilities, “p(y|x) = p(x,y)”. I suggest the authors do careful proofreading.\n\n2) The novelty in this paper is limited.  The diffusion VAE was proposed in Rey’19 https://arxiv.org/abs/1901.08991 with a similar random walk procedure with transition kernels on the manifold of input. However, the authors neither did any comparison with it nor provided convincing advantages over them. \n\n3) The authors claimed the standard VAE has too many assumptions on the priors, likelihood, and posteriors. However, their framework also assumed Gaussian distribution on posteriors and likelihood, only eliminating the prior distribution, but at the expense of introducing an assumed kernel and eigendecomposition approximation. \n\n3) The experiments are very limited, containing only 3 visualization results of 3 image generation tasks. The Fig 2 is difficult to read and interpret. How about the log-likelihood estimates from your approach compared with others? ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of 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 at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HyeY1E_y9B", "reviewer": "AnonReviewer1", "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 paper proposes a new generative model for unsupervised learning, based on a diffusion random walk principle inspired by the manifold learning literature. The basic idea is to (probabilistically) map points to a latent space, perform a random walk in that space, and then map back to the original space again. Learning of the suitable maps is achieved by casting the problem in a variational inference framework.\n\nThe paper is generally well-written, and clearly states out its goals and motivation. Sections 1 - 3 in particular give a nice overview of the broader context of the paper, and its aim of borrowing ideas from manifold learning and variational autoencoders. The particular aim on using concepts from manifold learning to avoid mode collapse - corresponding to the underlying homeomorphism losing its bijectivity - is in particular intriguing.\n\nThe method itself is intuitive at a high level, although I did have some difficulty with Section 4:\n- in 4.1, one begins by considering the local evidence. This requires drawing a point from U_x, which is defined to a be set. I presume this means one draws uniformly from this set?\n- Eqn 3 does not apparently have the same structure as Eqn 2. In particular, the first term in (2) is a function of x, but for (3) it is not a function of x'. How does conditioning affect the ELBO?\n- I was not sure how to interpret the statement that pθ(x'|x) ≈ ψ^{-1}(q(z'|x)). Do you mean the distribution is strongly concentrated around this value? Note also an extra \"]\" in the latter.\n- Eqn 5 should presumably be an equality? Also, it was not clear what the d in |.|_d^2 means, and why one does not use ||.||^2.\n- At a higher level, given that x' ~ U_x originally, why do we now draw x' ~ p(x'|x)?\n- Arriving at 4.2, it was not clear what \"The sampling procedure\" refers to, i.e., which of the steps in 4.1 it is seeking to specify or augment. It would be useful to clearly lay out the objective function that is being optimised, and how this section fits into that.\n- In 4.3, it seemed as if the discussion of the neighbourhood reconstruction error would be better placed in 4.1 itself. It appears to be a justification of the already-derived Eqn 5.\n- Algorithm 2, is there a need to introduce Z_t? It is a bit confusing that, e.g., Z_1 is first written to in iteration 1 by g(Z_0, ε), and then by ψ(X_1) in the second iteration.\n\nThe authors also claim a contribution to be the identification of a principled measure to identify mismatch between latent and data distributions. This \"bi-Lipschitz\" property is only introduced in Sec 5.1, and the discussion is not too approachable to someone unfamiliar with the area. In particular:\n- it is not clear how precisely the discussion in this section relates to the VDAE algorithm described in the previous section.\n- precisely what quantity we are to compute so as to verify this condition remains elusive. The abstract and introduction made me expect that the property is practically verifiable, but it was not clear from this section whether it is so.\n- the conclusion or key takeaway of this subsection was unclear. I gather that Jones et al. established the existence of a neighbourhood wherein one can define a bi-Lipschitz mapping to R^d for suitable d. But how does this relate to latent and data space mismatch?\n\nThe experiments show that the proposed method can generate meaningful samples for synthetic manifold data, as well as on the MNIST dataset. I would've preferred more discussion of the results in Sec 4.1. I also was hoping for a clearer illustration of mode-collapse problems on standard benchmarks for GANs, with comparison of results to, e.g., those of Wasserstein-GANs (beyond those in Sec 6.1) or other proposals that aim to mitigate mode collapse.\n\nMinor comments:\n- Fig 1, the text in the middle panel is hard to read in black and white.\n- SpectralNet is mentioned a few times but never formally introduced.\n- notationally, Section 4 is a little heavy. I would suggest considering to omit the subscript θ's in the function ψ and its inverse.\n- when mentioning the \"reparametrisation trick\", please provide a citation.\n- what is \\mathbb{X} in Theorem 2?\n- \"completementary\" -> \"complementary\"\n- \" rejection sampling Azadi et al. (2018); Turner et al. (2018).\" -> \" rejection sampling (Azadi et al. 2018; Turner et al. 2018).\"\n- some form of Conclusion would be appropriate.", "extra_scores": {"experience_assessment": "I do not know much about 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": {}}, {"review_id": "BkgOaj6RKr", "reviewer": "AnonReviewer3", "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": "** Summary\nThe paper studies the problem of density estimation and learning accurate generative models. The authors start from the observation that this problem has been approaches either using variational inference models, that scale very well but whose approximations may lead to degenerate results in practice, and diffusion maps, that scale poorly but are very effective in capturing the underlying data manifold. From here, the authors propose integrating the notion of random walk from diffusion maps into VAEs to avoid degenerate conditions. The proposed method is first defined in its generality, a practical implementation is presented, theoretical guarantees are provided, and empirical evidence of its effectiveness is reported.\n\n** Evaluation\nThe starting point of the paper seems very solid: diffusion maps are capturing the geometry of data very effectively and bringing some of those characteristics into the more scalable approach of VAE is an interesting approach. In the proposed method, this translates into introducing a learned diffusion map from manifold to an Euclidean space into the inference part. As a result, the lower bound optimized by the method now contains local information about the accuracy of the one-step random walk. How this can be translated into a practical implementation is also convincing. My main concern is that the overall method is now approximating many different elements in the original formulation, such as the diffusion map, its inverse, and the covariance of the random walk. Although theory seems to support that as these approximation become more accurate the overall result is reliable, in practice I wonder how they could combine and deteriorate the final result.\n\nThe empirical validation is relatively simple but in my opinion it provides enough insights about the advantages of the proposed method compared to VAEs and GANs. More solid and extensive evaluation is definitely needed in the future to have a more thorough comparison and a more careful assessment of the limits of the proposed method, but at this stage, I think the evaluation is sufficient.", "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 did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to train latent-variable models (VAEs) based on diffusion maps on the data-manifold. While this is an interesting idea, there are substantial problems with the current draft regarding clarity, novelty and scalability. In its current form, it is unlikely that the proposed model will have  a substantial impact on the community.
Decision: Reject