The Shape of Data: Intrinsic Distance for Data Distributions
Authors: Anton Tsitsulin
Marina Munkhoeva
Davide Mottin
Panagiotis Karras
Alex Bronstein
Ivan Oseledets
Emmanuel Mueller
Venue:  (2020)
Keywords: Deep Learning
Generative Models
Nonlinear Dimensionality Reduction
Manifold Learning
Similarity and Distance Learning
Spectral Methods

Abstract: The ability to represent and compare machine learning models is crucial in order to quantify subtle model changes, evaluate generative models, and gather insights on neural network architectures. Existing techniques for comparing data distributions focus on global data properties such as mean and covariance; in that sense, they are extrinsic and uni-scale. We develop a first-of-its-kind intrinsic and multi-scale method for characterizing and comparing data manifolds, using a lower-bound of the spectral variant of the Gromov-Wasserstein inter-manifold distance, which compares all data moments. In a thorough experimental study, we demonstrate that our method effectively discerns the structure of data manifolds even on unaligned data of different dimensionalities; moreover, we showcase its efficacy in evaluating the quality of generative models.

Published as a conference paper at ICLR 2020
THE SHAPE OF DATA: INTRINSIC DISTANCE FOR DATA DISTRIBUTIONS
Anton Tsitsulin" of
Marina Munkhoeva"
Davide Mottin
Panagiotis Karras
Alex Bronstein
Ivan Oseledets
Emmanuel Müller
ABSTRACT
The ability to represent and compare machine learning models crucial in order to quantify subtle model changes, evaluate generative models, and gather insights on neural network architectures. Existing techniques for comparing data distributions focus global data properties such are extrinsic and uni-scale. We develop a first-of iiss-innd intrinsic and multi-scale method for characterizing and comparing data manifolds, using lower-bound of the spectral Cromov--asserssee data moments. In a thorough experimental study, demonstrate that our method effectively discerns the structure of data manifolds even on unaligned data of different dimensionality, and showcase its efficacy in evaluating the quality generative models.
and covariance; in that sense, they
inter-manifold distance, which compares all
INTRODUCTION
The geometric properties of neural networks provide insights about their internals (Morcos et al., 2018: Wang et al., 2018) and help researchers the design of more robust models (Arjovsky et al., 2017: Binkowski al., 2018). 8). Generative models comparison of distributions. As generative models aim to reproduce the true data distribution P. by means of the model distribution F (z; θ), more delicate evaluation procedures are needed. Oftentimes, we wish to compare data lying in entirely different spaces, for example to track model evolution or compare models having different representation space.
natural example of the need for geometric
In order to evaluate the performance of generative models, past research has proposed several extrinsic evaluation measures, most notably the Fréchet (Heusel et al., 2017) and Kernel (Binkowski et al., 2018) Inception Distances (FID and KID). Such measures only reflect the first two three moments distributions, meaning they can be insensitive to global structural problems. We showcase this inadvertence in Figure 1: here FID and KID are insensitive to the global structure of the data distribution. Besides, FID and KID are based only on extrinsic properties they are unable to compare unaligned data manifolds.
Figure 1: Two distributions having the same first 3 moments, meaning FID and KID scores close to 0.
In this paper, we start out from the observation that models capturing the multi-scale nature of the data manifold by utilizing higher distribution moment matching, such as MMD-GAN (Li et al., 2017) and Sphere-GAN (Park& & Kwon, 2019), perform consistently better than their single-scale counterparts. On the other hand, using extrinsic information can be misleading, as dependent on factors external to the data, such representation. To address this drawback, we propose IMD, an Intrinsic Multi-scale Distance, that is able compare distributions using only intrinsic information about the data, and provide an efficient approximation thereof that renders computational complexity nearly linear. We demonstrate that IMD effectively quantifies difference in data distributions in three distinct application scenarios: comparing word vectors in languages with unaligned vocabularies, tracking dynamics of intermediate neural network representatiionn,, and evaluating generative models.
'Equal contribution. Contact tsitsulinng in@bit..... wnw-unninnnnn -bono. de, marina munkhoeva@skoltoch. University of Bonn SSkoltech
8 Aarhus University Techhion

---

Published as a conference paper at ICLR 2020
2
RELATED WORK
The geometric perspective on data is ubiquitous in machine learning. Geometric techniques enhance unsupervised and remi-supervised learning, generative and discriminative models (Belkin & Niyogi, 2002: Arjovsky et al., 2017; Mémoli, 2011). We outline the applications of the proposed manifold comparison technique and highlight the geometric intuition along the way.
2.1 GENERATIVE MODEL EVALUATION
Past research has explored many different directions for the evaluation of generative models. Setting aside models that ignore the true data distribution, such the Inception Score (Salimans et al., 2016) and GILBO (Alemi & Fischer, 2018), we discuss most relevant geometric ideas below; we refer the reader to Borji (2019) for comprchensive survey.
Critic model-based metrics. Classifier two-sample tests (C2ST) (Lopez-Paz & Oquab, 2017) aim assess whether two samples came from the same distribution by means of auxiliary classifier. This idea is reminiscent of the GAN discriminator network (Goodfellow et al., 2014): if is possible to train a model that distinguishes between samples from the model and the data distributions, follows that these distributions are not entirely similar. The convergence process of the GAN-like diseriminator (Arjovsky et al., 2017; Binkowski et al., 2018) lends itself creating a family of metrics based on training discriminative classifier (Im et al., 2018). Still, training a separate critic model often computationally prohibitive and requires careful specification. Besides, if the critic model is a neural network, the resulting metric lacks interpretability and training stability.
Many advanced GAN models such as Wasserstein, MMD, Sobolev and Spherical GANs impose different constraints the function class et al., 2018; Mrouch et al., 2018; Park & Kwon, 2019). Higher-order moment matching (Bińkowski al., 2018; Park & Kwon, 2019) enhances GAN performance, enabling GANs to capture multi-scale data properties, while multi-scale noise ameliorates GAN convergence problems (Jenni & Favaro, 2019). Still, no feasible multi-scale GAN evaluation metric has been proposed to date.
stabilize training (Arjovsky et al., 2017; Binkowski
Positional distribution comparison. In certain settings, it is acceptable to assign zero probability mass to the real data points (Odena et al., 2018). In effect, metrics that estimate distribution's location and dispersion provide useful input for generative model evaluations. For instance, the Fréchet Inception Distance (FID) (Heusel al., 2017) computes the Wasserstein-2 (i.e., Fréchet) distance between distributions approximated with Gaussians, using only the estimated mean and covariance matrices; the Kernel Inception Distance (KID) (Binkowski et al., 2018) computes a polynomial kernel k(r, y) = (2x y + 1)3 and measures the associated Kernel Maximum Mean Discrepancy (kernel MMD). Unlike FID, KID has an unbiased estimator (Gretton et al., 2012; Binkowski et al., 2018). However, even while such methods, based limited number of moments, may be computationally inexpensive, they only provide a rudimentary characterization of distributions from geometric viewpoint.
Intrinsic geometric measures. The Geometry Score (Khrulkov & Oseledets, 2018) characterizes distributions in terms of their estimated persistent homology, which roughly corresponds to the number of holes in manifold. Still, the Geometry Score assesses distributions merely in terms of their global geometry. this work, we aim to provide a multi-scale geometric assessment.
2.2 SIMILARITIES OF NEURAL NETWORK REPRESENTATIONS
Learning how representations evolve during training or across initializations provides pathway to the interpretability of neural networks (Raghu et al., 2017). Still, state-of-the-an methods for comparing representations of neural networks (Kornblith et al., 2019; Morcos et al., 2018: Wang al., 2018) consider only linear projections. The intrinsic nature of IMD renders appropriate for the task of comparing neural network representations, which can only rely on intrinsic information.
Yin & Shen (2018) introduced the Pairwise Inner Product (PIP) loss, unnormalized covariance error between sets, as a dissimilarity metric between word2vec embedding spaces with common vocabulary. We show in Section 4.2 how IMD is applicable this comparison task too.
2

---

Published as a conference paper at ICLR 2020
3 MULTI-SCALE INTRINSIC DISTANCE
At the core of deep learning lies the manifold hypothesis, which states that high-dimensional data, such as images or text, lie on a low-dimensional manifold (Narayanan & Mitter, 2010; Belkin & Niyogi, 2002: 2007). We aim provide theoretically motivated comparison of data manifolds based on rich intrinsic information. Our target measure should have the following properties:
intrinsic it is invariant to isometric transformations of the manifold, c.g. translations or rotations. multi-scale - it captures both local and global information.
We expose our method starting out with heat kernels, which admit a notion of manifold metric and can be used to sower-bount the distance between manifolds.
3.1 HEAT KERNELS ON MANIFOLDS AND GRAPHS
Based on the heat equation, the heat kernel captures all the information about a manifold's intrinsic geometry (Sun al., 2009). Given the Laplace- Beltrrmm operator (LBO) A x on a manifold X, the heat equation is By of the heat equation at point x X' if satisfies both the heat equation and the Dirac condition u(t,2² x²) + 8(x' x) as t > 0+ We assume the Dirichlet boundary condition u(t, x) = 0 for all t and x E O.Y. The heat kernel kx X' x''xx x + RtJ is the unique solution of the heat equation; while heat kernels can be defined on hyperbolic spaces and other exotic geometries, we restrict our exposition to Euclidean spaces X' = R, on which the heat kernel is defined as:
2 = Ax xuu for u: IR+ + IR+, A smooth function u is a fundamental solution
(2, = (4Tt)4² exp (-
|| (-11--
1'113 4t
(1)
For a compact X' including submanifolds of TRd, the heat kernel admits the expansion ky x. Lizoe e --x- 6o (z)), where A and o, are the i-th eigenvalue and eigenvector of Axx For 0+ according to Varadhan's ' lemma, the heat kernel approximates geodesic distances. Importantly for our purposes, the Heat kernel is multi-seale: for a local domain D with Dirichlet condition, the localized heat kernel k (z, x², t) is a good approximation of kx (z, x², f) if either (i) D is arbitrarily small and is small enough, or (ii) is for arbitrarily large and D is big enough. Formally,
Definition 1 Multi-scale property (Grigor'yan yan, 2006: Sun al., 2009) (i) For any smooth and relatively compact domain D C X, lime ko (x = kx (x, t) (ii) For any t E R and any x, E Dr localized heat kernel kD, (x. x', t) < kD, (z, x², t) Df C D2. Moreover, if (Dn) is expanding and exhausting sequence U Dj = X' and D;-1 C D; then lim kD. (I, F kx (I, x', () for any L.
Heat kernels are also defined for graphs in terms of their Laplacian matrices. An undirected graph a pair G = (V, E), where V (Wi...., vn). n = [V,, the set of vertices and C (V V) the set of edges. The adjacency matrix of is n x n matrix A having Aij = 1 if (i,j) E E and Ag otherwise. The normalized graph Laplacian is the matrix L I-I AD where D is the diagonal matrix in which entry D., holds the degree of node i, i.c. D = j== Ay. Since the Laplacian matrix is symmetric, its eigenvectors .1,..., On. are real and orthonormal. Thus, it factorized as = A T, where A a diagonal matrix with the sorted eigenvalues X S .... ...3 An and & is the orthonormal matrix +- = (ø1..... @n) having the eigenvectors of L as its columns. The heat kernel on graph is also given by the solution the heat equation on graph, which requires an eigendecomposition of its Laplacian: H, = clc = th -t -E: et T10,.
A useful invariant of the heat kemne is the heat kernel trace hktx : X X B + RJ. defined by diagonal restriction as ht) = fx (x x, t)dx= = Ei e A,t or. in the discrete case, citt(()) = Tr(H,) = Σ, e -th, Heat kernels traces (HKTs) have been successfully applied to the analysis of 3D shapes (Sun et al., 2009) and graphs (Tsitsulin et al., 2018). The HKT contains all the information in the graph's 's spectrum, both local and global, as the eigenvalues A can be inferred therefrom (Mémoli, 2011, I, Remark 4.8). For example, if there are c connected components in the graph, then lim hkt c()) c.
3

---

Published as a conference paper at ICLR 2020
3.2 CONVERGENCE TO THE LAPLACC--ELTRAMI OPERATOR
An important property of graph Laplacians is that it is possible to construct a graph among points sampled from manifold X' such that the spectral properties of its Laplacian resemble those of the Saplace-Beltramy operator on X. Belkin and Niyogi (Belkin & Niyogi, 2002) proposed such construction, the point cloud Laplacian, which is used for dimensionality reduction in a technique called Laplacian eigenmaps. Convergence to the LBO has been proven for various definitions of the graph Laplacian, including the one we use (Belkin & Niyogi, 2007; Hein et al., 2007; Coifman & Lafon, 2006; Ting et al., 2010). We recite the convergence results for the point cloud Laplacian from Belkin & Niyogi (2007):
Theorem Let Nh, and o',, be the ith eigenvalue and eigenvector, respectively, of the point cloud Laplacian L let di and oi be the 7th eigenvalue and eigenvector of the LBO A. Then, there exists in + O such that
lim X Xi
lim 11 - Φz 0il12 =0 n n-000
Still, the point cloud Laplacian involves the creation of an O(n²) matrix; for the sake of scalability, (kNN) graph by ooncosstruttion (i.e., based on bidirectional &NN
we use the relationships among points), whose Laplacian converges to the LBO for data with sufficiently high intrinsic dimension (Ting et al., 2010). As for the choice k. a random geometric kNN graph is connected when & > log n/lug 0.5139 log n (Balister al., 2005); k 5 yields connected graphs for all sample sizes we tested.
3.3 SPECTRAL SEOMOOV-ASSERSTEN DISTANCE
Even while is multi-scale metric on manifolds, the heat kernel can be spectrally approximated by finite graphs constructed from points sampled from these manifolds. In order to construct metric between manifolds, Mémoli (2011) suggests an ppaimallranssoortthhoor--- distance between Riemannian manifolds based on
"meta-distance":
spectral definition of the Cromov-Wassersterr matching the heat kernels at all scales. The cost of matching a pair of points (z, x') on manifold M to pair of points (y. y') manifold A at scale is given by their heat kernels kM, ky:
[(æ, y, x y t) (z, 2', (rr /)
The distance between the manifolds is then defined in terms of the infimal measure coupling
dcw(M,N) inf sup 2((++(-t) ||T ([(()))))
# =>0
where the infimum is sought over all measures i on M W marginalizing to the standard measures on M and N. For finite spaces, μ is a doubly-stochastic matrix. This distance is lower-bounded (Mémoli, 2011) in terms of the respective heat kernel traces as:
(M,,N) 2 supe- 2(t+e"1) (t) - ht)
(2)
e>0
This lower bound is the scaled Trco distance between the heal trace signatures hkl and hklty- The scaling factor e 22(++ 1) favors medium-scale differences, meaning that this lower bound is not sensitive to local perturbations. The maximum of the scaling factor occurs at = 1, and more than 1 10-8 of the function mass lies between 0.1 and 10.
3.4 HEAT TRACE ESTIMATION
Calculating the heat trace signature efficiently and accurately is challenge on large graph as it involves computing a trace of a large matrix exponential, i.e. (E)) naive approach would be to eigendecomposition exp(-tL) Recent work (Tsitsulin et al., 2018) suggested using either truncated Taylor expansion or linear interpolation of the interloping eigenvalues, however, both techniques are quite coarse. To combine
& exp(-tA) which is infeasible for large n.
4

---

Published as a conference paper at ICLR 2020
accuracy and speed, we use the Stochastic Lanczos Quadrature (SLQ) (Ubaru al., 2017; Golub & Meurant, 2009). This method combines the Hutchinson trace estimator (Hutchinson, 1989; Adams et al., 2018) and the Lanczos algorithm for eigenvalues. We aim to estimate the trace of matrix function with a Hutchinson estimator:
Tr(f(C)) = (v f(C)v)
v. f(C)v.
(3)
Thg
where the function interest f(-) = exp(-) and v, are Tay random vectors drawn from a distribution p(v) with zero mean and unit variance. A typical choice for p(v) is Rademacher standard normal distribution. In practice, there is little difference, although theory Rademacher has less variance, but Gaussian requires less random vectors (Avron & Toledo, 2011).
To estimate the quadratic form V. f(C),, in (3) with a symmetric real-valued matrix and a smooth function f. we plug in the eigendecomposition = Φ T rewrite the outcome as a Riemann-Sticlije integral and apply the m-point Gauss quadrature rule (Golub & Welsch, 1969);
v. f(C)v, = of = Σ f()))=3 = S" f(t)du(t) Σ wwf(Os):
(4)
where H, =1 v:ly and (tt) is piecewise constant function defined follows
0,
ift < Am if s if = X t
m(t)
and 0g are the quadrature's nodes and w/ are the corresponding weights. We obtain we and 0g with the m--tep Lanczos algorithm (Golub & Meurant, 2009), which we describe succinetly.
Given the symmetric matrix C and arbitrary starting unit-vector qo. the m-step Lanczos algorithm computes an x m matrix Q = [qo, 91.......... tridiagonal symmetric matrix T, such that Q CQ T. The columns of Q constitute orthonormal basis for the Krylov subspace K. that spans vectors (4o. Lqo. m vector is given as a polynomial C applicd to the initial vector qo: q: = p. p.( These Lanczos polynomials are orthogonal with respect to the integral measure μ(t). As orthogonal polynomials satisfy the three term recurrence relation, we obtain Pk+1 as a combination of ps and px-1- The tridiagonal matrix storing the coefficients of such combinations, called the Jacobi matrix J, is exactly the tridiagonal symmetric matrix T. A classic result tells us that the nodes 8, and the weights wa of the Gauss quadrature the eigenvalues of T, Au. and the squared first components of its normalized eigenvectors, Th. respectively (see Golub & Welsch (1969); Wilf (1962); Golub & Meurant (2009)). Thereby, setting qo va, the estimate for the quadratic form becomes:
with orthogonal columns and an
[ {o each qi
v, f(C)v Σ (Dv))) Th = Uo = = up:
b =
A
T UAU
(5)
Applying (5) over n. random vectors in the Hutchinson trace estimator (3) yields the SLQ estimate:
m
Tr(S(C)) RJ
Σ (TH) ((x
-r.
(6)
The
We derive error bounds for the estimator based on the Lanezos approximation of the matrix exponential, and show that even few Lanczos steps, i.c., m = 10. are sufficient for an accurate approximation of the quadratic form. However, the trace estimation error is theoretically dominated by the етror of the Hutchinson estimator, e.g. for Gaussian p(v) the bound on the number of samples to guarantee that the probability of the relative error exceeding is at most is - (2 (Roosta-Khorasan
& Ascher, 2015). Although, in practice, we observe performance much better than the bound suggests. Hutchinson error implies nearing accuracy roughly 10 with n. 2 10k random vectors, however, with as much n, = 100 the error is already 10 Thus, values of m = 10 and n, = 100 all experiments in Section 4. Please see Appendix A for full derivations and figures.
default
5

---

Published as a conference paper at ICLR 2020
150
pl
IMD
d
Change wrt. Simple
bu
10
100
he
5
English
50
simple
Figure 2: (a) IMD distances between language pairs for unaligned Wikipedia word embeddings and (b) distances from the simple English Wikipedia visualized for IMD, FID, and KID. We consider 16 languages:
Polish, Russian, Greek, Hungarian, Turkish, Arabic, Hebrew, English, Simple English, Swedish, German, Spanish, Dutch, Portugese, Vietnamese, and Waray-Waray.
3.5 PUTTING IMD TOGETHER
We employ the heretofore described advances in differential geometry and numerical linear algebra to create IMD (Multi-Scale Intrinsic Distance), fast, intrinsic method to lower-bound the spectral
distance between manifolds.
Algorithm IMD algorithm.
We describe the overall computation of IMD in Algorithm 1. Given data samples in Rd, we build àNN graph G by OR-construction such that its Laplacian spectrum approximates the one of the Beplace-Beltrami operator of the underlying manifold (Ting et al., 2010), and then compute h))
function IMDESC(X)
G <- kNN X)
L <- Laplacian inciinn( (G))
return 1 = s1g (C, 8, nw))
Eee-xit & r. We compare heat traces in the spirit of Equation (2), i.e., lhkte, (t) hkta, (t)l for
function IMDIST(X, Y)
hktx + IMDist(Xi XX
hkty + IMDist(Y)
(0.1, 10) sampled from a logarithmically spaced grid.
return supe- 2(14+ 1hkt - hkty/
Constructing exact ANN graphs is an (dn?) operation; however, approximation algorithms take near-linear time Odn! (+) (Dong et al., 2011; Aumüller et al., 2019). In practice, with approximate &NN graph construction (Dong al., 2011), computational time is low while result variance is similar to the exact case. The m-step Lanczos algorithm on a sparse n x n kNN Laplacian L with one starting vector has (knm) complexity, where kn is the number of nonzero elements in L. The symmetric tridiagonal matrix cigendecomposition incurs an additional (m log m) (Coakley & Rokhlin, 2013). We apply this algorithm over n, starting vectors, yielding a complexity of Onn,(m log + kmmn)). with constant k = 5 and m = 10 by default. In effect, IMD's time complexity stands between those of two common GAN evaluation methods: KID, which is (dn?) and FID, which is (dd + dn). The time complexity of Geometry Score is unspecified in Khrulkov & Oseledets (2018), yet in Section 4.6 we show that its runtime grows exponentially in sample size.
EXPERIMENTS
We evaluate IMD on the ability compare intermediate representations of machine learning models. For instance, in a recommender system we could detect whether problem is related to the representation or the the classifier in the end of a pipeline. In this section, we show the effectiveness of our intrinsic measure on multiple tasks and show how our intrinsic distance can provide insights beyond previously proposed extrinsic measures.
Summary of experiments. We examine the ability of IMD to measure several aspects of difference among data manifolds. We first consider a task from unsupervised machine translation with unaligned word embeddings and show that IMD captures correlations among language kinship (affinity or genealogical relationships). Second, we showcase how IMD handles data coming from data sources of unequal dimensionalities. Third, we study how IMD highlights differences among image data representations across initializations and through training process of neural networks.
Our code available open-source: https: / / wwt.ttub.com. f imd.

---

Published as a conference paper at ICLR 2020
4.1 COMPARING UNALIGNED LANGUAGE MANIFOLDS
The problem of unaligned representations is particularly severe in the domain of natural language processing as the vocabulary is rarely comparable across different languages or even different documents. We employ IMD measure the relative closeness of pairs of languages based on the word embeddings with different vocabularies. Figure 2 (a) shows heatmap of pairwise IMD scores. IMD detects similar languages (Slavic, Semitic, Romanic, etc.) despite the lack of ground truth vocabulary alignment. On the other hand, Figure 11 in Appendix C shows that FID and KID, are not able to distinguish the intrinsic language-specific structure word embeddings. Detailed description and setting of the experiment can be found in Appendix C.
4.2 OPTIMIZING DIMENSIONALITY OF WORD EMBEDDINGS
IMD
PIP
Comparing data having different dimensionality is cumbersome, even when representations are aligned. We juxtapose IMD by PIP loss (Yin Shen, 2018) which allows the comparison of aligned representations To this end, we measure IMD distance between English word embeddings of varying dimensions. Figure shows the heatmap of the scores between sets of word vectors of different dimensionalities. Closer dimensionalities have lower distance scores for both metrics. However, IMD better highlights gradual change of the size of word vectors, e.g. word vectors of size and are clearly closer to each other than embeddings of size and 16 in terms of IMD, which is not true for PIP.
-10-6
4g
16
32
64
128
138
for word embeddings.
25
512
128
256
Figure 3: Comparison of IMD and PIP loss on
word embeddings of different dimension. IMD detects subtle changes in the dimensionality.
4.3 TRACKING THE EVOLUTION OF IMAGE MANIFOLDS
Next, we employ IMD to inspect the internal dynamics of neural networks. We investigate the stability of output layer manifolds across random initializations. We train 10 instances of the VGG-16 (Simonyan & Zisserman, 2015) network using different weight initializations on the CIFAR-10 and CIFAR-100 datasets. We compare the average IMD scores across representations in each network layer relative to the last layer. As Figure 4 (left) shows, for both CIFAR-10 and CIFAR-100, the convolutional layers exhibit similar behavior; IMD shows that consequent layers do not monotonically contribute the separation of image representations, but start to do so after initial feature extraction stage comprised of 4 convolutional blocks. low variance across the 10 networks trained from different random initializations indicates stability in the network structure.
IMD relative to the last layer
600
80
CIFAR-IO, VGG-I6 16
CIFAR-I00, 100, VGG-16
60
400
CIFAR-10, VGG-16
Accuracy
CIFAR-10L, VGG-16
40
CIFAR-I0, ResNes-2
200
CIEAR 100, ResNet 20
20
0
0
10
10
20
30
40
50
60
Convolutional layer no.
Epach no.
Figure 4: (left) IMD score across convolutional layers of the VGG-16 network on CIFAR-10 and 100 datasets: (right) training progression in terms of accuracy (dotted) and IMD (solid) on CIFAR- and CIFAR-100 datasets for VGG-16 and ResNet-20, with respect to VGG-16.

---

Published as a conference paper at ICLR 2020
Table 1: IMD agrees with KID and FID across varying datasets for GAN evaluation.
MNIST
FashionMNIST
CIFARIO
CelebA
Metric
WGAN
WGAN-GP
WGAN
WGAN-GP
WGAN
WGAN-GP
WGAN
WGAN-GP
TMD
57.74 =
10.77 +
118.14
13.45 +
18.10
10.84 +
10.11
2.84 +
0.47
0.42
0.52
0.54
0.36
0.42
0.33
0.31
KID X 10
47.26 =
5.53 + 119.93
25.49 +
93.89
59.59 = 217.28
92.71 +
0.07
0.03
0.14
0.07
0.09
0.09
0.14
0.08
FID
31.75
8.95 + 152.44 +
35.31 +
101.43
80.65 + 205.63 +
85.55 +
0.07
0.03
0.12
0.07
0.09
0.09
0.09
0.08
We now examine the last network layers during training with different initializations. Figure (right) plots the VGGI6 validation errors and IMD scores relative to the final layer representations of two pretrained networks, VGGI6 itself with last layer dimension d 512 and ResNet-20 with d = 64 and ~50 times less parameters. We observe that even in such unaligned spaces, IMD correctly identifies the convergence point of the networks. Surprisingly, we find that, in terms of IMD, VGG- 16 representations progress towards not only the VGG- 16 final layer, but the ResNet-20 final layer representation as well; this result suggests that these networks of distinct architectures share similar final structures.
4.4 EVALUATING GENERATIVE MODELS
We now move on to apply IMD evaluation of generative models. First, we evaluate the sensitivity of IMD, FID, and KID simple image transformations as a proxy to more intricate artifacts of modern generative models. from the CIFAR-I0 training set, and measure the distance to the original data manifold, averaging outcomes over 100 subsamples of 10k images each.
Metric relative to MNIST
1.5
progressively blur images
MNIST
0.5
CIFAR100
To enable comparison across methods, we normalize each distance measure such that the distance between CIFAR-10 and MNIST is 1. Figure reports the results different levels of Gaussian blur. We additionally report the normalized distance to the CIFAR- 100 training set (dashed lines R.....)) FID and KID quickly drift away from the original distribution and match MNIST, a dataset of completely different nature. Contrariwise, IMD is more robust to noise and follows the datasets structure, as the relationships between objects remain mostly unaffected on low blur levels. Moreover, with both FID and KID, low noise (a 1) applied to CIFAR- 10 suffices to exceed the distance of CIFAR- 100, which is similar to CIFAR-10. 10. IMD is much more robust, exceeding that distance only with o = 2.
2
3
Gaussian blur level o
Figure 5: FID, KID and IMD on the CIFAR-10 dataset with Gaussian blur.
Next, we turn our attention the sample-based evaluation of generative models. train the WGAN (Arjovsky et al., 2017) and WGAN-GP (Gulrajani et al., 2017) models on four
litt:: with ER normalization
We then
10a
MNIST
CIFAR10
CelebA
datasets: MNIST, FashionMNIST. CIFARIO and
CelebA. We sample 10k samples, Y. from each
10a
GAN. We then uniformly subsample 10k images from the corresponding original dataset, X, and compute the IMD, KID and FID scores between X and Y.
10-2
Table 1 reports the average measure and its 99% confidence interval across 100 runs. IMD, as well as both FID and KID, reflect the fact that WGAN-GP a more expressive model. We provide details on architecture, training, and generated samples in Appendix C. Additionally, in Appendix we demonstrate superiority of IMD synthetic data.
10"
10
10a
Figure 6:
Plotting the normalized heat trace allows interpretation of medium- and global-scale structure of datasets. Best viewed in color.
8

---

Published as a conference paper at ICLR 2020
IMD (exact)
IMD (approx.)
FID
KID
GS
Metric relative to 10 samples
2.5
Execution time, seconds
10a
ml uin rimi 101
2
10
1.5
10a
10
0.5
10a
104
10
103.5
10
5 10
Number of samples
Number of samples
Figure 7: Stability and scalability experiment: (left) stability of FID, KID and IMD wrt. sample size on CIFAR-10 10 and CIFAR-100 dataset; (right) scalability of FID, KID and IMD wrt. sample size synthetic datasets.
4.5 INTERPRETING IMD
To understand how IMD operates, we investigate the behavior of heat kernel traces of different datasets that are normalized by null model. Tsitsulin et al. (2018) proposed normalization by the heat kernel trace an empty graph, which amounts to taking the average, rather than the sum, of the original heat kernel diagonal. However, this normalization is not appropriate null model it ignores graph connectivity. We propose a heat kernel normalization by expected heat kernel of an Erdōs-Rede Rényi graph (further details in the Appendix D).
Figure depicts the obtained normalized hkt,, for all datasets we work with. We average results over 100 subsamples of 10k images each. For 10, i.e., at medium scale, CelebA is most different from the random graph, while for large-scale t values, which capture global community structure, (t) reflects the approximate number of clusters in the data. Surprisingly, CIFAR-100 comes close to CIFAR-10 for large values; we have found that this is due to the fact that the pre-trained Inception network does not separate the CIFAR-100 data classes well enough. We conclude that the heat kernel trace interpretable we normalize with an appropriate null model.
4.6 VERIFYING STABILITY AND SCALABILITY OF IMD
In addition to the complexity analysis in Section 3.5, we assess the scaling and sample stability of IMD. Since IMD, like FID, lower bound to optimal transport-based metric, we cannot hope for an unbiased estimator. However, we empirically verify, in Figure 7 (left), that IMD does not diverge too much with increased sample size. Most remarkably, we observe that IMD with approximate &NN (Dong et al., 2011) !) does not induce additional variance, while it diverges slightly further than the exact version as the number of samples grows.
In terms of scalability, Figure 7 (right) shows that the theoretical complexity is supported in practice. Using approximate ANN, we break the O(n²) performance of KID. FID's time complexity appears constant, as its runtime is dominated by the (dd) matrix square root operation. Geometry score (GS) fails to perform scalably, as its runtime grows exponentially. Due to this prohibitive computational cost, we eschew other comparison with GS. Furthermore, as IMD distance is computed through a low-dimensional heat trace representation of the manifold, we can store HKT for future comparisons, thereby enhancing performance in the of many-to-man comparisons.
DISCUSSION AND FUTURE WORK
We introduced IMD, geometry-groundee first-ofitt-kind intrinsic multi-scale method for comparing unaligned manifolds, which we approximate efficiently with guarantees, utilizing the Stochastic Lanczos Quadrature. We have shown the expressiveness of IMD in quantifying the change of data representations in NLP and image processing, evaluating generative models, and in the study of neural network representations. Since IMD allows comparing diverse manifolds, its applicability is not limited to the tasks we have evaluated, while it paves the way to the development of even more expressive techniques founded geometric insights.

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGEMENTS
This work was partially funded by the Ministry of Science and Education of Russian Federation as a part of Mega Grant Research Project 14.756.31.0001. Ivan Oseledets would like thank Huawei for the support of his research.
REFERENCES
Ryan P Adams, Jeffrey Pennington, Matthew Johnson, Jamie Smith, Yaniv Ovadia, Brian Patton, and James Saunderson. Estimating the spectral density of large implicit matrices. arXiv preprint 2018.
Alexander A. Alemi and Ian Fischer. GILBO: One metric measure them all. In NeurIPS, 2018.
Martín Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In ICML, 2017. 1, 2,
Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. ANN-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 2019. 6
Haim Avron and Sivan Toledo. Randomized algorithms for estimating the trace of an implicit symmetrie positive semi-definite matrix. Journal of the ACM (JACM), 2011. 5
Paul Balister, Béla Bollobás, Amites Sarkar, and Mark Walters. k-nearest-neighhour graphs. Advances in Applied Probability, 2005.
Connectivity random
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In NIPS, 2002. 2, 3, 4
Mikhail Belkin and Partha Niyogi. Convergence of laplacian eigenmaps. In NIPS, pp. 129-136, 2007. 3,4
Mikolaj Binkowski, Dougal J Sutherland, Michael Arbel, and Arthur Gretton. Demystifying MMD gans. In ICLR, 2018. 1,2
Ali Borji. Pros and cons of gan evaluation measures. Computer Vision and Image Understanding, 179:41-65 65, 2019. 2
Fan Chung, Linyuan Lu, and Van Vu. The spectra of random graphs with given expected degrees. Internet Mathematics, 2004. 16
Ed S. Coakley and Vladimir Rokhlin. A fast divide-and and---quee algorithm for computing the spectra of real symmetric tridiagonal matrices. Applied and Computational Harmonic Analysis, 34(3): 379 414, 2013. 6
Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic
analysis, 2006. 4
Amin Coja-Oghlan. On the laplacian eigenvalues of g(n, p). Combinatorics, Probability and Computing, 2007. 15
Wei Dong, Charikar Moses, and Kai Li. Efficient k-nearest neighbor graph construction for generic similarity measures. In WwW, 2011.
Gene H Golub and Gérard Meurant. Matrices, moments and quadrature with applications. Princeton University Press, 2009.
Gene H Golub and John H Welsch. Calculation of gauss quadrature rules. computation, 1969.
Mathematics of
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. NIPS, pp. 2672-2680, 2014. 2
10

---

Published as a conference paper at ICLR 2020
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander J. Smola. A kernel two-sample test. Journal of Machine Learning Research, 13:723-773, 2012. 2
Alexander Grigor' yan. Heat kernels weighted manifolds and applications. In Contemp. Math., pp. 93-191. AMS, 2006.
Ishaan Gulrajani, Faruk Ahmed, Martín Arjovsky, Vincent Dumoulin, and Aaron C. Courville. Improved training of wasserstein GANs. In NIPS, 2017. 8
Matthias Hein, Jean-Yves Audibert, and Ulrike von Luxburg. Graph laplacians and their convergence random neighhorhood graphs. Journal of Machine Learning Research, 2007.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by a two time-scale update rule converge to a local nash equilibrium. In NIPS, 2017. 1,2
Marlis Hochbruck and Christian Lubich. On krylov subspace approximations to the matrix exponential operator. SIAM Journal Numerical Analysis, 1997. 13
MF Hutchinson. A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. Communications in Statisiies-imulation and Computation, 185-11055 1989. 5
Daniel Jiwoong Im, He Ma, Graham Taylor, and Kristin Branson. Quantitatively evaluating GANs with divergences proposed for training. In ICLR, 2018.
Simon Jenni and Paolo Favaro. On stabilizing generative adversarial training with noise. In CVPR, 2019. 2
Valentin Khrulkov and Ivan V. Oseledets. Geometry score: A method for comparing generative adversarial networks. ICML, 2018. 2,
Simon Korblithh, Mohammad Norouzi, Honglak Lee, and Geoffrey Hinton. Similarity of neural network representations revisited. In ICML, 2019. 2
Chun-Liang Li, Wei-Cheng Chang, Yu Cheng, Yiming Yang. and Barnabás Póczos. MMD GAN: Towards deeper understanding of moment matching network. In NIPS, 2017. 1
David Lopez- Paz and Maxime Oquab. Revisiting classifier two-sample tests. In ICLR, 2017. 2
Facundo Mémoli. A spectral notion of gromov wassertesn distance and related methods. Applied and Computational Harmonic Analysis, 2011. 3,
Ari Morcos, Maithra Raghu, and Samy Bengio. Insights on representational similarity in neural networks with canonical correlation. In NeurlPS, 2018. 1,2
Youssef Mrouch, Chun-Liang Li, Tom Sercu, Anant Raj, and Yu Cheng. Sobolev GAN. In ICLR, 2018. 2
Hariharan Narayanan and Sanjoy Mitter. Sample complexity of testing the manifold hypothesis. In
NIPS, 2010. 3
Augustus Odena, Jacob Buckman, Catherine Olsson, Tom B. Brown, Christopher Olah, Colin A. Raffel, and lan J. Goodfellow. Is generator conditioning causally related to GAN performance? In ICML, 2018. 2
Sung Woo Park and Junseok Kwon. Sphere generative adversarial network based geometric moment matching. In CVPR, 2019. 1
Maithra Raghu, Justin Gilmer, Jason Yosinski, and Jascha Sohl-Dickstein. SVCCA: Singular vector canonical correlation analysis for deep learning dynamics and interpretabilityy In NIPS, 2017. 2
Radim Rehüřek and Petr Sojka. Software Framework for Topic Modelling with Large Corpora. In Proceedings of the LREC 2010 Workshop New Challenges for NLP Frameworks, 2010. 15
11

---

Published as a conference paper at ICLR 2020
and Uri Ascher. Improved bounds on sample size for implicit matrix trace Farbod Foundations of Computational Mathematics, 2015. 5, 14
estimators.
Tim Salimans, Ian J. Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen.
Improved techniques for training GANs. In NIPS, 2016. 2
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. CoRR, abs/1 1556, 2015. 7
Jian Sun, Maks Ovsjanikov, and Leonidas Guibas. A concise and provably informative multi-scale signature based on heat diffusion. In Computer graphics Wiley Online Library, 2009. 3
Daniel Ting, Ling Huang, and Michael Jordan. An analysis of the convergence of graph laplacians. In ICML, 2010. 4, 6
Anton Tsitsulin, Davide Mottin, Panagiotis Karras, Alexander M. Bronstein, and Emmanuel Müller. NetLSD: Hearing the shape of graph. In KDD, 2018. 3, 4, 9, 16
Shashanka Ubaru, Jie Chen, and Yousef Saad. Fast estimation of tr(f(a)) via stochastic lanczos quadrature. SIAM Journal on Matrix Analysis and Applications, 2017. 5, 13
Liwei Wang. Lunjia Hu, Jiayuan Gu, Zhiqiang Hu, Yue Wu, Kun He, and John Hopcroft. Towards understanding learning representations: To what extent do different neural networks learn the same representation. In Advances in Neural Information Processing Systems, 2018. 1,2
Herbert S Wilf. Mathematics for the physical sciences. 1962.
Zi Yin and Yuanyuan Shen. On the dimensionality of word embedding. In Advances in Neural Information Processing Systems, pp. 887-898, 2018. 2,
12

---

Published as a conference paper at ICLR 2020
APPENDIX
TRACE ESTIMATION ERROR BOUNDS
We will use the error of the Lanezos approximation of the action of the matrix exponential f(C)== exp 12 v to estimate the error of the trace. We first rewrite quadratic form under convenient form,
summation in the trace approximation
v(Cvv Σ = = - ((AA)) o a = k==
(7)
k=0
Because the Krylov subspace Kn (n, v) is built on top of vector v with Q as an orthogonal basis of Km (C, (). i.e. qo = and 1 qi for E (I...., 1), the following holds
f(Cvv ~v Qf(T)e = f(T)e
(8)
Thus, the error in quadratic form estimate v f(C)v exactly the error of Lanezos approximation f(C)v s Qf(T)) To obtain the error bounds, we use the Theorem 2 in Hochbruck & Lubich (1997), which we recite below.
Theorem Let C be real symmetric positive semi-definits matrix with eigemvalues in the interval [0,4p) Then the error in the m-step Lanczos approximation of exp 12 v, iee. 6m exp 12 Qm exp -tmm-mmm eill. is bounded in the following ways:
10c 10e-m² (ieem3/150 m²/(5pt)
A S m < 2pt
(9a)
6m <
10(pt)-1e e ept
m 2 2pt
(9b)
Since unit vector, thanks to Boanch--BBnykkovsky Sannakkosky-Schwarzz the eтror of the quadratic form approximation by the error of the exp -f approximation, i.c. |v [ [(C)v - (S(AAUUTeT e s eee v Qm exp= e = 6m-
Schwarz inequality, we can upper-bound
Following the argumentation in Ubaru et al. (2017), we obtain a condition on the number of Lanczos steps m by setting Cm S [min (A), where fmi (A) the minimum value of f on [Aminn Amaz) We now derive the absolute error between the Hutchinson estimate of Equation (3) and the SLQ of Equation (6):
Ry
Tr., (f(C)) -
T [f(()v. Σ c f(T i=1
ny
i=1
v.
n1
7
mcm
where ( is the tridiagonal matrix obtained with Lanczos algorithm with starting vector v,.
Tra f(C) - r| & nem I nE Finally, we formulate SLQ as an (c, estimator,
マ smin (A) S Tr(S(C),
(10)
TT(S(C)) Tr,, (F(()) < E |n(roen
1- 8 Pr
Tr(S(E)- Trn. (m(()) + Tr.,, (S(2)) -/ (
((([C))) + + +
< Pr
TT(f(C)) r se TIF(ON)
< Pr
13

---

Published as a conference paper at ICLR 2020
For the normalized Laplacian L, the minimum eigenvalue is 0 and fmin = exp(0) = hence Cm I 2. and the eigenvalue interval has = 0.5. We can thus derive the appropriate number of Lanczos steps to achieve error e,
20c 20emmi mmmmm/10 ((2.5t)
221 S St m 21
(Ila)
<
0.5el m
401 le e-0.5t
(11b)
m
Figure 8 shows the tightness of the bound for the approximation of the matrix exponential action on vector v, 6m = || exp(-IC) Qm exp(-(Tm)er We can see that for most of the temperatures I, very few Lanczos steps are sufficient, i.e. we can set m 10. However, the error from the Hutchinson estimator dominates the overall error. Figure shows the error of trace estimation does not change with and for Rademacher p(v). the bound on the number of random & samples is ny 2 & log(2/0)) (Roosta-Khorasar Ascher, 2015). Employing 10k vectors results in the error bound of roughly 10 10-2. In practice, we observe the performance much better than given by the bound,
(= 0.1
5.06
10.0
2.575
7.525
Matvec approximation error, Cm
10
10-7
0.1 is around 10-3 In case of
10-13
10-10
see Figure
5
10
15
20
One particular benefit of small m value is that we do not have to worry about the orthogonality loss in the Lanczos algorithm which often undermines its convergence. Since we do only a few Lanczos iterations. the rounding errors hardly accumulate causing little burden in terms of orthogonality loss between the basis vectors of the Krylov subspace.
Number of Lanczos steps,
Figure 8: Errors (solid) and error bounds (dotted) for the approximation of matrix exponential action with varying temperature t.
0.1 +-=1
t 2 2 t= 10 ... bound
10"
Relative trace approximation enror,
10
10-6
10 9
5
20
10
10a
104
Number of Lanczos steps, m
Number of random vectors, Th
Figure 9: Trace estimation errors (solid) and error bounds (dotted) for: (left) the number of Lanezos steps m with fixed number of random vectors 100; (righr) the number of random vectors Hutchinson estimator with fixed number of Lanczos steps m 10. Lines correspond to varying temperatures l.
14

---

Published as a conference paper at ICLR 2020
B VARIANCE REDUCTION
We reduce variance of the randomized estimator through control variates. The idea is to use Taylor expansion substitute part of the trace estimate with its easily computed precise value,
Tr(exp(-tD)) = =lq exp(-t() - (I -I-+C+ C
CC2
)
+ Tr(I - -
(12)
2
L² )
1 1211611
= slq exp( exp(-tt) (C) (I (I-tC- +c
+ + Tr(-tt))
(13)
c² | - tn +
1-115112
- slqq exp( tc] + slg |c
slg
[ 2
(14)
2
where we use the fact that || v TTr(c" C) and that the trace of normalized Laplacian equal to n. does reduce the variance of the trace estimate for smaller temperatures S
To obtain this advantage over the whole range of t, we utilize the following variance reduction form:
Tr(exp(-1L)) a slq (ex((-tC) (I- at -I-olf) n(1 at);
(15)
where there exists an alpha that is optimal for every t, namely setting a = 1/ exp(t). We can see the variance reduction that comes from this procedure in the Figure 12.
C EXPERIMENTS DISCUSSION
Here we include additional results that did not find their way to the main paper body.
C.I FID AND KID FAIL TO FIND STRUCTURE UNALIGNED CORPORA
Figure shows the matrix of distances for FID and KID aligned and colored in the same way as Figure (a). FID and KII) can not find meaningful structure in the data in the same way as IMD as they rely on extrinsic data properties.
C.2 WORD EMBEDDING EXPERIMENT DETAILS.
We use gensim (Rehūfek & Sojka, 2010) learn word vectors on the latest Wikipedia corpus snapshot on 16 languages: Polish, Russian, Greek, Hungarian, Turkish, Arabic, Hebrew, English, Simple English, Swedish, German, Spanish, Dutch, Portugese, Vietnamese, and Karay-Waray We then compute FID, KID and IMD scores on all the pairs, we average 100 runs for the heatmap figures For the different dimensionality experiment, learn vectors on the English Wikipedia of sizes equal to the powers of from to 512. After that we compute IMD and covariance error, i.e. normalized PIP loss, between the pairs of sizes to generate the heatmap figure 3.
metric
good GAN
bad GAN
FID
0.00529 1
0.00627 +
0.00070
0.00076
KID
0.00172 +
0.00259 +
0.00073
0.00077
IMD
9.02059 +
14.0732 +
1.5195
2.1706
C.3 VANILLA GAN ON TORUS
Figure 10:
Bad GAN produces
We provide an additional experiment clearly showing the case where IMD is superior to its main competitors, FID and KID. We train two vanilla GANs on the points of a 3D torus. The bad GAN fails to learn the topology of the dataset it tries to mimic, yet previous metrics cannot detect this fact. IMD, on the contrary, can tell the difference. Figure 10 shows the points sampled from the GAN with some of the points inside the hole. KID and FID confidence intervals overlap for good and bad GANs, meanwhile IMD scores are clearly distinct from each other.
samples inside the torus hole (red). FID and KID cannot detect such behaviour.
C.4 NORMALIZATION DETAILS
For the purpose of normalizing IMD, we need to approximate that graph eigenvalues. Coja-Oghlan (2007) proved that λ₁ ed 1/2 < d2 Xn I 1 + ed. for the core of the graph for some
15

---

Published as a conference paper at ICLR 2020
650
0.5
lu
4u
he
400
hc
peple
Ample
0.25
Au
de
200
smmple
FID
KID
Figure 11: FID and KID are not able to capture language affinity from unaligned word2vec embeddings.
constant c. We have empirically found that c = provides a tight approximation for random graphs.
That coincides with analysis Chung et al. (2004), who proved that A, (1 + o(1))2d if dmin >> logog" even though in our case dmin = = k. We thus estimate the spectrum of a random Rédōs graph as growing linearly between A = - 2d and A, = =1 + 2d which corresponds to the underlying manifold being two-dimensional (Tsitsulin al., 2018).
EXPERIMENTAL SETTINGS
single server with NVIDIA V100 GPU with 16Gb memory and x 20 Intel E5-2698 v4 CPU. For the experiment
We train all models
10-
Standard variation,
10-2 2
summarized in Table in the Section 4.1 we train WGAN and WGAN-GP models 4 datasets: MNIST, FashionMNIST, CIFAR10 and CelebA and sample 10k samples, Y, from each of the GANs. We uniformly subsample 10k images from the original datasets, X. and compute the IMD, KID and FID scores between X and Y. We report the mean well as the 99% confidence interval across 100 runs.
10
original SEQ
10
SLQ variince reduction
10-1
100
10
Temperature,
Below we report the architectures, hyperparameters Figure 12: Variance of the trace estimate. and generated samples of the models used for the experiments. We train each of the GANs for 200 epochs MNIST, FMNIST and 100 and for 50 epochs on CclebA dataset. For WGAN we use RMSprop optimizer with learning rate of 5 10-5, For WGAN-GP we use Adam optimizer with learning rate of 10- B1 0.9, B2 0.999.
GRAPH EXAMPLE
Figure 13 provides visual proof that the 5NN graph reflects the underlying manifold structure of the CIFAR-10 dataset. Clusters in the graph exactly correspond CIFAR- 10 classes.
Figure 13: CIFAR-10 graph colored with
true class labels.
16

---

Published as a conference paper at ICLR 2020
3
7
0
7
5
5
6
J
2
5 8
9
5
7
7
8
2
7
0
0
(
8
9
0
9
3
9
O
8
4
O
4
/
5
6
4
0
O
3
5
4
2
p
D
J
0
3
4
4
2
3
3
5 /
/
5
D
4
7
0
4
?
y
3
9
0 0
5
0
/
3
1
5
3
7
0
/
Q
O
5
7
3
9
6 1
7
2
8
5
Figure 14: MNIST samples (left: WGAN, right: WGAN-GP)
Figure 15: FNSST samples (left: WGAN, right: WGAN-GP)
Figure 16: CIFAR-10 samples (left: WGAN, right: WGAN-GP)
Figure 17: CelebA samples (left: WGAN, right: WGAN-GP)
17

---

Published as a conference paper at ICLR 2020
MNIST WGAN
ConvGenerator
"latent_to_featuree Sequential
(0): linear (in_features-100, cut_features-512, bias-True)
(1): ReLU()
(features_tt to i : Sequential
(0): ConvTranspose2d (128, 64, kernel_sizer (4, 4)
stride- 2), padding=(1, 1)) (1): ReLU()
(2): (6 eps=1e-05, momentum=0.1, 1, affine-Irue)
(3): ConvTranspose2d (64, 32, ternel_size= 4),
stride= 2), padding= 1)) (4): ReLU()
(5): (3,, eps=le-05, momentum=0.1, affine=True)
(6): ConvTranspose2d (32, 16, kernel_sizes (4, 4),
stride= 2), padding= 11)
(7): ReIl(
(8) (166 eps-le-05, momentum-0.11 1, affine-True)
(9): ConvTranspose2d (16, 1, kernel_size-(0) (4, 4),
stride= 2), padding= (1, 11)
(10): : Sigmoid()
ConvDiscriminator iimage_toffetturer Sequential
(0): Conv2d 16, kernel_size- (4, 4), stride- (2, 2), padding- (1, 1))
(1): LeakyReLU (negative_slop=00.2)
(2) (onv2d 32, kernel_gize=14, 4), stride= (2, 2), padding= (2, 11)
(3) LeakyReLU [1
(5) LeakyReLU (negative_slope=0..2) 4), stride= (2, 2), padding= (1, 1))
(4): (32, 64, kernel_
(6): (64, 128, kernel_size-14, 4), stride- (2, 2), padding (1, 1))
(7): $igmeid()
(features_te (Features_to_praa) Sequential
(0): Linear (f__araurste cut_features=1, bias=True)
(1): Sigmoid()
18

---

Published as a conference paper at ICLR 2020
MNIST WGAN-GP, FMNIST (WGAN, WGAN-GP)
MMISTGemerator(
(block1) Sequential
( (2 (256, 128, kernel_size=(5 5), stride= (1, 1
(1) RcLU (inplace)
(block2) Sequential
(0) ConvTranspose2d (128, 64, kernel_size- (5, 5), stride-(1, 1))
(1): (inplaae)
(deconv_ out): ConvIransposee2l66, 1, Barnel_sized (8, 8), stride= (2, 21
(preprocess): Sequential
(0): Linear (in features=128, out #006 bias=True)
(1): ReLU (inplacee)
(sigmoid); Sigmoid()
MNISDDiscriminatorr
(main): Sequential
(0): (onv2d 64, kernel_size=(5, 5), stride= (2, 2), padding= (2, 2)
(1) (ipplaee
(2) Conv2d 128, kernel_size- 5), stride- (2, 2), padding- (2, 2))
(3) RelW(npaacc))
(4): (128, 256, kernel_size- (5, 5), stride- (2, 2), padding (2, 2))
(5): (inplace)
(output): Linear (00_ out ftt_feeuuees_,, bias=True)
CIFAR-10 (WGAN, WGAN-GP)
CIFARGenerator (preprocess): S
(0): Linear (infeeerrrat,,,, fut_feaaures=4096, bias-1rue)
(1): BatchNormId eps-le-05, momentum-0.1, affine-True)
(2): (inplace)
(block1) Sequential
(0) CenvIranspose22d255 128, kernel_size= (2, 2), stride= 2))
(1): (128, eps-1c-05, momentum=0.1, affino-True)
(2): (inplace)
(block2) Sequential
(0) ConvTranspose2d (128, 64, gernel_size-to (2, 2), stride- 2))
(1): BatchNorm2d (64, eps-le-05, momentum-Q.1, affine-True)
(2) ReLU (inplac))
(deconv : ; ConTTranspose2d 3, kernel size= (2, 2), stride= (2, 2)
(tanh): Tanh
CIFARDiscrininettor
(main): Sequential
(0): Conv2d 64, kernel_size= 3), stride= (2, 2), padding= (,, 1))
(1) LeakyReLU
(2) (64, 128, kernel_size=(3, 3), stride= (2, 2), padding= 1))
(3) :
(4) (128, 256, kernel_size- 3), stride- (2, 2), padding- (1, 1))
(5): LeakyRelU hegativee_slge=00.011
(linear): Linear (in features=4096, out features=l, bias=True)
19

---

Published as a conference paper at ICLR 2020
CelebA (WGAN, WGAN-GP)
CelcbaGenerator(
(preprocess): Sequential
(0): minear (1__fearurres- cut_features--192 bias-True)
(1): BatchNormld(8199, eps-le-05, momentum-0.1, affine-True)
(2) (enU(inplaac)
(block1): Sequential
(0): ConvTranspose22112,, 256, ternel_size= (5, 5), stride= (2, 2),
padding- (2, 2), output_paadiin- 1), bias-False) (1): B2tchNorm2dd256, eps-1e-05, momentum=0.1, affine-Irue)
(2): ReLU (inplace)
(block2) Sequential
(0): CenvTranspose2d (256, 128, kernel_size= (5, 5), stride- (2, 2)
padding= (2, 2), putput_ppadding((1 1), bias=False)
(1): BatchNorm2d(128, eps=1e-05, momentum=0.1, aftine=True)
(2) (inplan)
(bl ock3) Sequential
(0): Con/Transpose2d (128, 64, kernel_size- (5, 5), stride- (2, 2),
padding= (2, 2) output tertuut_padding-((( (1, 1), bias=False)
(1): (5, eps=le-05, momentum=0.1, affine=True)
(2) (inplace)
(deconv_cut); ConvTranspos22d164, kernel_size=(5, (5, 5), stride= (2, 2)
padding= (2, 2), output_padding- (1, 1)) (tanh): Tanh
CelebaDiscriminator
(main): Sequential
(0): Conv2d 64, size= 5), stride= (2, 2), padding= (2, 2)
(1): LeakyReLU [negative_slope=0.001
(2) (64, 128, kernel_size-15, 5), stride- (2, 2), padding- (2, 2))
(3): LeakyReLU hegpyeeeWe
(4) Conv 256, kernei_size= 5), stride= (2, 2), padding= (2, 2))
(5):
(6): (256 512, kernel_size=15, 5), stride= (2, 2), padding= (2, 2)
(7): LeakyReLU wwwgative_sllpeeo....
(8): (512, 1, kernel_
4), stride= (1, 1))
20


Reviews:
[{"review_id": "SylsznxZcB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Define/explain data manifold: in the abstract, ``data moments\" suggests the data is treated as random variables; the authors could explain more on how they make the connection between random variables and manifolds \n2. introduction: include an example of ``models having different representation space\" \n3. introduction: elaborate more on ``unaligned data manifolds\" \n4. introduction: the distinction between ``intrinsic\" and ``extrinsic\" can be made more explicit; as currently written, the difference between ``extrinsic\"/``multi-scale\"/``utilizing higher moments\" isn't clear \n5. the authors mentioned the hypothesis that high-dimensional data lies on a low-dimensional manifold, but in (3.1) they only considered $\\mathbb{R}^d$ without justifying this restriction \n6. (3.1) ``$u(t, \\cdot) \\to \\delta(\\cdot -x)$\" change the dot to a variable \n7. (3.1) ``$u(t, x) = 0 \\forall x \\in \\partial X$ and for all $t$\" change to ``for all $t$ and $x \\in \\partial X$ \n8. equation 1, write ``we restrict our exposition to Euclidean spaces $X = \\mathbb{R}^d$\" and remove ``$\\forall x, x' \\in \\mathbb{R}^d, t \\in \\mathbb{R}^+$\" \n9.  (3.1) the phrase ``a compact X including $\\mathbb{R}^d$\" is confusing\n    as $\\mathbb{R}^d$ is not compact under Euclidean topology \n10.  (3.1) ``for a local domain with Dirichlet condition $D$\" change to ``for a local domain $D$ with Dirichlet condition\" \n11.  (3.1) ``Definition 1\" is more of a proposition/theorem. \n12.  (3.1) notation: in the body paragraph the authors use $k(x, x', t)$ but in ``definition 1\" they used $k(x, y, t)$ \n13. (3.1) ``$c$ disconnected components\" to ``$c$ connected components\" \n14. (3.1) the authors could elaborate more about how HKT contains all the information in the graph's spectrum. Currently, they only stated the limit equal to the number of connected components. \n15. Github code is helpful but it would be better if they can include an algorithm section\n16. A figure of the architecture could be included under the ``putting IMD together\" section ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HklyYEYltS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "IMD is a lower bound to Gromov-Wasserstein distance. Which implies that when IMD is small, this does not guarantee that GW will be small. It is interesting how large can be that gap (and when typically the gap increases).\nThe term e{−2(t+t^−1)} in the definitions of GW and IMD, obviously imposes some \"scale\" for both manifolds M and N, so it is hard to call IMD multi-scale.\n\nExperiments with language affinities are not convincing to me. How is armenian and hebrew are close, or hungarian and turkish (if \"el\" is greek, then greek, hungarian and turkish are close somehow?).\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "HJxW01GvYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper propose a novel way to measure similarity between datasets, which e.g. is useful to determine if samples from a generative model resembles a test dataset. The approach is presented as an efficient numerical algorithm for working with diffusion on data manifolds.\n\nI am very much in doubt about this paper as there are too many aspects of the work I do not (currently) understand. I suspect that the underlying idea is solid, but in its current form I cannot recommend publication of the paper.\n\nDetailed questions and comments:\n\n*) It seems that the focus is on GANs and related models that do not come with a likelihood. In my reading, the practical problem that the paper address is model comparison in models that do not have a likelihood. Is that correct? If so, I am left to wonder why models with a likelihood a not discussed, and why the such models aren't included in the experiments? Wouldn't the likelihood be a sensible baseline?\n\n*) The term \"multi-scale\" is not defined until page 3. I'd recommend defining this term much more early or avoid its use until its defined.\n\n*) I found the geometric exposition to be rather confusing. In Sec. 3.1 emphasis seem to initially be on Euclidean diffusion, and at some point emphasis changes to diffusion on graphs. Sometimes the paper seem focused on diffusion on general manifolds. I found this exposition to be rather chaotic, and I suspect that this is the root cause of me not understanding many aspects of the work.\n\n*) In Sec. 3.2 the notion of diffusion *on* manifolds is discussed. At some point (not quite clear to me when) the results of this discussion is applied to diffusion *between* manifolds. I don't quite understand what it means to diffuse between manifolds. I would have appreciated a more explicit exposition here.\n\n*) In the concluding remarks it is stated that IMD provides guarantees. Which guarantees are that?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a way to measure dataset similarities. Reviewers all agree that this method is novel and interesting. A few questions initially raised by reviewers regarding models with and without likelihood, geometric exposition, and guarantees around GW, are promptly answered by authors, which raised the score to all weak accept. 

Decision: Accept (Poster)