Matrix factorisation and the interpretation of geodesic distance
Authors: Nick Whiteley
Annie Gray
Patrick Rubin-Delanchy
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph
covariance matrix
nonlinear dimension reduction
manifold
embedding
matrix factorisation
Isomap

Abstract: Given a graph or similarity matrix, we consider the problem of recovering a notion of true distance between the nodes, and so their true positions. We show that this can be accomplished in two steps: matrix factorisation, followed by nonlinear dimension reduction. This combination is effective because the point cloud obtained in the first step lives close to a manifold in which latent distance is encoded as geodesic distance. Hence, a nonlinear dimension reduction tool, approximating geodesic distance, can recover the latent positions, up to a simple transformation. We give a detailed account of the case where spectral embedding is used, followed by Isomap, and provide encouraging experimental evidence for other combinations of techniques.

Matrix factorisation and the interpretation of geodesic distance
Nick Whiteley
Annie Gray University of Bristol
University of Bristol
nick. nick. www.reeeeyybrrrstoo....ooo
annie grayybrrstotooccoom. ac
Patrick Rubin-Delanchy
University of Bristol
patrick.rubin donriicki.iiiidddddadooootto... uk
Abstract
Given a graph or similarity matrix, we consider the problem recovering a notion of true distance between the nodes, and their positions. We show that this can be accomplished in two steps: matrix factorisation, followed by nonlinear dimension reduction. This combination is effective because the point cloud obtained in the first step lives close to manifold in which latent distance is encoded geodesic distance. Hence, nonlinear dimension reduction tool, approximating geodesic distance, can recover the latent positions, up to simple transformation. We give detailed account of the case where spectral embedding is used, followed by Isomap, and provide encouraging experimental evidence for other combinations of techniques.
Introduction
Assume observe, given as the result of computational procedure, data in the form of symmetric matrix E gxxx which we relate to unobserved vectors Zi...., Zn E C Rd. where d d n. by
A - f(z, EE, Isisisn.
(1)
for some real-valued symmetric function f which will be called kernel, and matrix of unobserved perturbations, [Raxn, As illustrative examples, A could be the observed adjacency matrix of graph with n vertices, similarity matrix associated with items, or some matrix-valued estimator of covariance or correlation between n variates.
Broadly stated, our goal is to recover Zi.... Zn given A, up to identifiability constraints. We seek method to perform this recovery which can be implemented in practice without any knowledge of f. nor of any explicit statistical model for A, and to which we can plug in various matrix-types, be it adjacency, similarity, covariance, or other.
At face value, this may seem rather a lot to ask. Without assumptions, neither f. the Z, 's nor even d are identifiable (44]. However, under quite general assumptions, we will show that practical solution is provided by the key combination of two procedures: i) matrix factorisation of A, such as spectral embedding, followed by ii) nonlinear dimension reduction, such as Isomap 577
This combination effective because of the following facts, only the first of which already known. The matrix factorisation step approximates high-dimensional images of the Z, 's living near d- dimensional manifold 45 Under regularity and non-degeneracy assumptions on the kerne,, which for our analysis is taken to be positive definite, geodesic distance in this manifold equals Euclidean
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

geodesic distance on 2, up to simple transformations of the coordinates, for example scaling. Thus dimension reduction technique which approximates in-manifold geodesic distances can be expected to recover the 7,'s "s up to simple transformation. If those assumptions fail, as they must with real data, we may still find that those approximate geodesic distances are useful because they reflect a geometry implicit in the kernel.
There are many works which address recovery of the Zí's when one does consider a particular matrix-type, an explicit statistical model, and/or specific form for f. When A is an adjacency matrix and fZ, Zj) is the probability of an edge between nodes and j. the construct (I) is a latent position model 22 and various scenarios have been studied: Z is a sphere and f (xr, y) is function of (æ, y) [Q: estimation by graph distance when (z. y) is a function of || - y/l [T]: spectral estimation when f(z, y) is a possibly indefinite inner-product [53 155
12 46; inference under a logistic model via MCMC [22] or variational approximation 48 The case where 2 is a discrete set of points
53 g [4] and references therein; by contrast the methods we propose are directed at the case where
corresponds to the very widely studied stochastic block model [23], see [5] 33 44
continuous.
The opposite problem of estimating f. with Z; unknown but assumed uniform on [0, 1]. is known as
graphon estimation [9].
Concerning the case when A is a covariance matrix, Latent Variable Gaussian Process models use fZ,,, Z,) to define the population covariance between the ith and jih variates under a hierarchical model. When fzz y) (z. y). this reduces to a latent variable optimisation counterpart of Probabilistic PCA [88] and the maximum likelihood estimate of the Z, 's is obtained from the eigendecompooition of the empirical covariance matrix, which in our setting could be A. When f is nonlinear, but fixed e.g. to Radial Basis Function kernel, gradient and variational techniques are See the same references for onward connections to kernel PCA 50
B1 B0 5
available 31 30 59
Our contribution and precursors. The general practice of using dimensionality reduction and geodesic distance to extract latent features from data is common in data science and machine-learning. Examples arise in genomics [8 neuroscience [K). speech analysis [2 21 and cyber-security M. What sets our work apart from these contributions is that we establish new rigorous basis for this practice.
has been understood for several years that the high-dimensional embedding obtained by matrix 34
62 32). However, it was only recently observed that the embedding must therefore concentrate about a low dimensional set, in the Hausdorff sense 25 Our key mathematical contribution is to describe the topology and geometry of this set, proving it is a topological manifold and establishing how in-manifold geodesic distance is related geodesic distance in Z. Riemannian geometry underlying kernels was sketched in 7 but without consideration of geodesic distances or rigorous proofs, and not in the context of was an inspiration to us, suggesting Isomap as a tool for amalysing spectral embeddings, under latent structure model in which Z is a one-dimensional curve in Id and f is the inner product. A key feature of our problem setup is that is unknown, in which case the manifold is not available in closed form and typically lives in an infinite-dimensionn space. To our knowledge, we are the first to show why spectral embedding followed by Isomap might recover the true Z s, or useful transformation thereof, in general.
factorisation can be related via feature map to the Z, of model ① 26
15
56
latent position estimation. The work [3] 5
We complement our mathematical results with experimental evidence, obtained from both simu- lated and real data, suggesting that alternative combinations of matrixxfactorisaaion and dimension- reduction techniques work too. For the former, we consider the popular node2vec (20 algorithm,
likelihood-barn approach for graphs said to perform matrix factorisation implicitly 4 [4]] For the
latter, we consider the popular t-SNE 37 and UMAP (39 algorithms. As predicted by the theory, direct low-dimensional matrix factorisation, whether using spectral embedding or node2vec. is less successful.
2 Proposed methods and their rationale
2.1 Spectral embedding, as estimating d(Z))
In our mathematical setup (precise details come later) the kernel f will nonnegative definite and will be the associated Mercer feature map. It is well known that each point o(Z,) then lives in an

---

X
M
X,
o(Zi)
Z.
Z3
A
X
2
X
8,
((2))
Figure I: Illustration of theory in the case d 1. Our analysis reveals how geodesic distance, along M, between Φ (Zi) and ZZz), is related to geodesic distance, along Z, between Zi and Zj.
infinite-dimensee Hilbert space, which will be denoted Eg. and the inner-product (Ø(Z,), o(2))) in this space equals f(Z,, 2z).
The spectral embedding procedure. For n, define the p-dimensional spectral embedding of A to be X [X1,-.., x=, U| RTxp, where [S] Rexp is diagonal matrix containing the absolute values of the p largest eigenvalues of A, by magnitude, and Ü R=*P is a matrix containing corresponding orthonormal eigenvectors, in the same order. The R packages irlba and RSpectra provide fast solutions which can exploit sparse inputs.
One should think of X; approximating the vector of first p components of (( denoted (2.). up to orthogonal transformation, and this can be formalised to a greater or lesser extent depending on what assumptions are made. There are several situations, e.g. f any polynomial 45, the cosine kernel used in Section 4.1 the Pegree-corrected model, in which only the first Po (say) components of (6-) are nonzero, where typically Po 2 If, after n reaches Po. we embed into p Po dimensions, then with denoting the Euclidean norm, we have [18]
29 or mixee--mmbership [ stochastic block
QQX; (p.)l Op iE .E.......
(log n) n1/2
max
for universal constant > orthogonal matrix Q under regularity assumptions the Z,'s, and E (that Z; are i.i.d. (Z,, Z,) has finite expectation, and the perturbations E are independent and centered with exponential tails). This encompasses the case where A is binary, for example graph adjacency matrix 36 46 Similar results are available in the cases where A is a Laplacian
146 40 covariance matrix 17 The methods of this paper based, in practice, the distances
IX JX
X, which are invariant to orthogonal transformation and so for the purposes of validating X, ~ p Z4) (Z;)l the presence Q is immaterial.
For X, to converge to o( (2) more generally, we must let its dimension p grow with n and, at least given the present state of literature, accept weaker consistency results, for example, convergence in Wasserstein distance between QX,,.. QX,, and (Z1), op (Z,) 32 Uniform consistency results, in the style of Q are also available for indefinite 46). bipartite, and directed graphs [25)].
These are left for future work because of the complications of Q no longer being orthogonal.
Rank selection. real data, where n is typically fixed, there no 'best' way of selecting p, as discussed for example in 12). The method of [65], based on profile-likeliood, provides popular, practical choice, taking as input the spectrum of A, and is implemented the package igraph.
2.2 Isomap, as estimating Z,
We propose recover Zi...., Zn through the following procedure.

---

Algorithm 1 Isomap procedure
input p-dimensional points XI,..., Xx
1: Compute the neighhourhood graph of radius e: weighted graph connecting and j. with weight
||xX-
- X,,,, if ||XX, - -x, e
2: Compute the matrix of shortest paths on the neighbourhood graph, DM E R=x
3: Apply classical multidimensional scaling (CMDS) to DM into IRd return d-dimensional points Zi....,2 Zn
Theorem below establishes, under general assumptions, that M = = (2) is a topological manifold of Hausdorff dimension exactly that of Z (as opposed to upper bound (5)).. It also proposes "change of metric', often trivial, under which a path on and its image on M have the same length.
This result explains how 2,,..., Zn can estimate Zi..... Zn First, think of path from X; to X; on the neighbourhood graph as a noisy, discrete version of some corresponding continuous path from ((,)) to o(Z)) on M. The length the first (the sum the weights of the edges) is approximately equal to the length of the second if measured in the standard metrie: infinitesmal step from x to xr + da has length (dx, dx) By inversion of Φ we can trace a third path, taking us from Z, to Zj Z. But to make its length agree with the first two, we must pick non-standard metrie: an infinitesmal step from = to + dz must be regarded to have length (dz, Hgdz)1/² v dz H2dz, where
821
i,j E dl.....d...
Or(0)
(5.z)
The exciting news for practical purposes is that, through elementary calculus, we might establish that H. is constant in (e.g. if f is translation translation-invariant) if f is just a function of Euclidean distance). In the latter case, if 2 is convex, is not too difficult to see that the length of the shortest path, from o(Zz)
even proportional to the identity (e.g.
(Z,) on M, must be proportional to the Euclidean distance between Z; and Z,. Thus, the matrix of shortest paths obtained by Isomap (Step 2) approximates the matrix of Euclidean distances between the Z, (up to scaling), from which the Zi themselves can be recovered (Step 3), up to scaling, rotation, and translation. Of course, we have taken few liberties in this argument, such assuming positive. We will address these rigorously in the next section.
be invertible and dz H2dz to be
Dimension and radius selection. For visualisation in our examples will pick d = 1 or d 2. For other applications, d can be estimated the approximate rank of D.M after double-centering 600, e.g. via (65) again. In practice, we suggest picking c just large enough for the neighbourhood graph to be connected or, if the data have outliers, a fixed quantile (such as 5%) of DMM removing nodes outside the largest connected component. The same recommendations apply if the k-nearest neighbour graph is used instead of the e-neighbourhood graph.
3 Theory
3.1 Setup and assumptions
The usual inner-product and Euclidean norm on gd are denoted (:--) and || 1|. Eg is the set of x = (x (2) ...JT E RN such that ||>||| == (E (2) < cc. For x, y E 62 (x, v)2 = A- r (h) (k), With d 2 1, let 2 be a compact subset of Rd, and let 2 be a closed ball in Rd centered the origin, such that 2 c Σ. Let f Z 2 R be a symmetric, continuous, nonfegative-definte function.
By Mercer's Theorem, e.g., (5T, Thm 4.49], there exist nonnegative real numbers (Ax) and functions (ux)221 with each uy 2 > R, which are orthonormal with respect to the inner product (uj, ux) + f uy (x)uu (z)dr and such that
8
f(x, v)
E Az Z 1=1
(3)

---

where the convergence is absolute and uniform. For I E Z let 6(x)
[x|/2z un (x) 2 (2))) ....T R The image of Z by o is denoted M. Observe from that for any z 3, f(z.y) = (o(x), o(y))2 l 1 = (a, and the latter is finite for any
E since f is continuous and compact, hence M C E2.
The following definitions are standard in metric geometry [6.. For any a, b E f2, a path in M with end-points a, b is continuous function 7 : [0.
M such that "o and 7n b. With n 2
a non-decreasing sequence to.... in such that to = 0 and bn = 1. is called a partition. Given a path y and partition P = (to..... ) define x(7,
Ek=1 ll. 7 112- The length of (w.r.t. || 21) is ((7) == supp x(y, P), where the supremum is over all possible partitions. The geodesic distance in M between and is defined be the infimum of ((7) over all paths ? in M
with end-points a, b. D denotes geodesic distance in M between (Zz)) and Z- Similarly path 17 in Z with end-points 2, y is continuous function r7 : [0, 1] + 2 such that 770 I, m y. and with (n7, P) == Σk-1 Im,. Mtt-1 the length of 17 (w.r.t || (I) is ((7) = supp X(7, P). D denotes geodesic distance in Z between Zi and Zj. If 2 is convex, D = 12 - Zj|l- Assumption 1. For all x. y E with x # y, there exists a E such that [(x a) # sV, a).
Assumption 2. f is C on and for every E Z, the matrix H. is positive definite.
Assumption | is used to show á injective. Assumption has various implications, loosely speaking it ensures a non-degenerate relationship between path-length in M and path-length in Z. Concerning our general setup, if f is not required to be nonnegative definite, but is still symmetric, then a representation formula like ① is available under e.g. trace-class assumptions 45 It is of interest to generalise our results to that scenario but technical complications are involved, so we leave it for future research.
3.2 Path-lengths in M and in Z
Theorem 1. Let assumptions D and 2 hold. Then & a bi-Lipschitz homeomorphismm between Z and
M. Let a, b be any two points in M such that there exists path in M with end-point b of finite length. Let y be any such path and define n [0, + by T}t == o (nc). Then 1j is a path in Z with ((1) < co. For any >> O there exists partition Pe such that for any partition P (lo..... .,)
satisfying Pe P.
((7) Σ (Tx
E(Ts
12
Thc-11 Ho (Me
1/2 Mh2-1)
S.
(4)
If and n are continuously differentiable, the following two equalities hold:
(()) - Hiellade - S.' (ite Hy (ii. 122 dt.
(5)
The proof is in the appendix. In the terminology of differential geometry. the collection of inner- products (Ir 3) + (ar, H.y), indexed by E Z, constitute Riemannian metric on Z, see e.g. [4 Ch.1 and p. 121] for background, and the right hand side of (5) is the length of the path in with respect to this Riemannian metric. The theorem tells us that finding geodesic distance in M, i.c. minimising ((7) with respect to for fixed end-points say = o(2,), = o(2,). is equivalent to minimizing path-length in Z between end-points ø (a) = Z,, (b) = Zy under the Riemannian metric. In section 3.3 we will show how, for various classes of kernels, this minimisation can be performed in closed form leading to explicit relationships between D and D In Section 3.3 we focus on (5) rather than 4 only for ease of exposition, it is shown in the appendix that exactly the same conclusions can be derived directly from 4 To avoid repetition Assumption | will be taken to hold throughout section 3.3 without further mention.
3.3 Geodesic distance in M and in 2
Translation invariant kernels. Suppose Z C Rd is compact and convex, and f(x, y) = g(r y) where g : R2 -> I. C2, In this situation H, constant in z, and equal to the Hessian of -9 evaluated at the origin. The positive-defintte part of Assumption i therefore satisfied if and only if
5

---

9 has local maximum at the origin. We now use Theorem I to find geodesic distance in M between generic points a, E .M for this class of conslation-invarian kernels. To do this we obtain lower bound on !(7) over all paths in M with end-points b, then show there exists such path whose length achieves this lower bound.
Let G VA where VAVT is the eigendecomposition of the Hessian of -9 evaluated the origin, so H = GGG for all z. Then from 5 for a generic path y in M with end-points a, b,
1(7) = [/² (ine, H 11)) di 301=
- 1/' (in. GG ( 1 di S/ ||G ||GTTill Id
1/2
(6)
> =11/** G T dt - |-|[TT S." nnde = | (m - no)ll = | 1
where the inequality is due to the triangle inequality for the || norm. The right-most term in is independent of y, other than through the end-points a, b. To see there exists a path whose length equals this lower bound, take
ie == (a) ((a)+113 (0)
LE [0,
(8)
which is well-defined as path in 2, since for this class of kernels 2 is assumed convex. With Te = (T),) ), 7 is clearly path in M.. Differentiating îie w.r.t. ( and substituting into (6) shows ((5) = G
(b) o (a]]l. as required. The following proposition summarises conclusions in the case that a = ((Z,) and b = <(2)), for any Z, Zz.
Proposition 1. If Z compact and convex, and (xx y) - g(x y) where g +R is C2 and has local maximum at the origin, then D is equal Euclidean distance between Zr and Zz, up to their linear transformation by GT. In the particular case where g(x v) = h([1 yll?) with (0) < O, we have D & 2 = 12 Z,1l.
Inner-product kernels. Suppose 2 {u E IRd ||||| = 1} and f(x, v) = (x where : R- + R is C2 and such that (1) > 0. In this case H. = g'(1)I g"(1)zz" and by g( v)) on the sphere is desitive-definite iif
result of 177. any kernel of the form fxr g(z) -n= a,æ" for some nonnegative (an)n20. implying g"(1) 2 O. Assumption 2 then holds. To derive the geodesic distance in M, first write out (5) for a generic path y in M with end-points
a. b:
[/[ (/.. H 1h) 1/ dt dt= f ('''DI)) + mx)l))
1/2
I(T) ((1)=
dt.
(9)
Since 2 is a radius-1 sphere centered at the origin we must have || 1 for all t, so d
0 2 az lm = ar (7o,
(),, Therefore the r.h.s. of 2 is in fact equal to g g((1)1/2 fo Melldd. This is minimised over all possible paths 7j in 2 with end-points o (-)))) when 17 shortest (with respect to Euclidean distance) circular are in 2, in which fo || arccos (a)) (b)). Thus we have:
d
Proposition 2. 1 = {x Rdd || = 13 and f(x, - g((x,, v)) where g R + i C2 and such that g((1) 0, then D = g = arccos (7i, Zz)-
Additive kernels. Suppose 2 is the Cartesian product of intervals 2, = [c_ ,,,,,,thh ,,,t, 1= 1, 1,..., d and
f(z, v) Σ (f))( (()), x (z) ... _(d]), where each a 0 and each fa positive- where
definite and C For this class of kernels H, is diagonal with H a4 ayt (20)) 200)
0²
(+) is the ith element of the vector z. The positive-defintt part of Assumption thus holds if these diagonal elements are strictly positive for all E Z.
Let us introduce the vector of monotonically increasing transformations:
(1)
8 f
1/2
(>2) = (x()) ... (T
v)(2 = a,
1/2
dg, (E.5)
(10)
or
6

---

b)
1.5
Appro goodgle -oodooc--ssnnn distance
Anbilenn distrnoe
0.6
0.0
-05
n-400
Figure 2: Simulated data example. a) Spectral embedding (first 3 dimensions). b) comparison of latent, approximate geodesic, and ambient distance and c) latent position recovery in the dense regime by spectral embedding followed by Isomap for increasing n. To aid visualisation, all plots in c) display subset 100 estimated positions corresponding to true positions on a sub-grid which common across Estimated positions are coloured according to their true y-coordinate.
and write the vector of corresponding inverse transformations vi-1, For generic path y in M with end-points o, and as usual f)- = s0 ((x), define & = vp()). Then:
1(7) = //' (/.. H 1n) dt {'² ll
(11)
1./0 & ad - Coll 11 (b) s (a)ll
(12)
where the second and last equalities hold due to the definition of Ge. and o denotes elementwise composition. The quantity || o x- (0b( 1 (- (a)ll is thus lower bound on path-length 1(>) for any path y in M with end-points a, b. To see that there exists path whose length achieves this lower bound, and hence that it is the geodesic distance in M between a, b, define 7 == & + where & s (a) + tlu (b) v o= (a)). Differentiating & w.r.t. t and substituting into 11] yields ((5) l a (b) v Φ (a)ll. as required. Our conclusions in the case that a di (1
and o(z)) summarised by:
Proposition 3. If Z is the Cartesian product of d intervals Z, C i- d, and f(x, v)
Ei= (z) ()) where for each as > 0, ft is positive definite and C², and 0z( (2.z)
o²
0 for all E Z,, then D'A is equal to the Euclidean distance between Z, and Zz up to their coordinatewise-monon
transformation by w. If 0z(3)8y(3)
is positive constant over all (2,2)
E Z, and over all i 1, 1,...,d d, then D D 1| Z₁
4
Experiments
4.1 Simulated data: latent position network model
This section shows the theory work in pedagogical example, where A is an adjacency matrix. Consider an undirected random graph following a latent position model with kernel f(x, y) = Pn (c0s((x(1) - y( + cos(x(() - (() + 2), operating on IR2 x R2, Here, the sequence Pn. sparsity factor which will either be constant, Pn. = 1, shrinking to zero sufficiently slowly.

---

reflecting dense (degree grows linearly) and sparse (degree grows sublinearly) regimes respectively. The kernel is clearly translation-invan invariant, satisfies Assumptions [add and has finite rank. p 5. The true latent positions Z,; E RR. are deterministic and equally spaced points grid over the region 2 = [- π + 0.25, ग - 0.25] [-> ग + 0.25, _ - 0.25], this range chosen to give valid probabilities and an interesting bottleneck in the 2-dimensional manifold M. From Proposition | the geodesic distance between ((Z)) and @ ((2)) on M is equal to the Euclidean distance between Z, and 3j. up to scaling, specifically DM = 22/2.
Focusing first the dense regime, for each 100, 400, 1600, 6400, we simulate graph, and its into p 5 dimensions. The first three dimensions of this embedding are shown in Figure 4) and we see that the points gather about a two-dimensional, curved, manifold. To approximate geodesic distance, we compute a neighbourhood graph of radius e from Xi..... &n. choosing e as small as possible subject to maintaining a connected graph. Figure (b) shows that approximated geodesic distances roughly agree with the true Euclidean distances in latent space Z (up to the predicted scaling of 1/2), whereas there is significant distortion between ambient and latent distance (IIX; Xyll versus 2| Z, |I). Finally, we recover the estimated latent positions in R2 using Isomap, which we align with the original by Procrustes (orthogonal transformation with scaling), in Figure 2 As the theory predicts, the recovery error vanishes as n increases.
spectral embedding _i.... X,,
In the appendix, we perform the same experiment in a sparse regime, n&,,, = w(log" n), chosen to ensure the spectral embedding is still consistent, and the recovery enror still shrinks, but more slowly. We also implement other related approaches: UMAP, 1-SNE applied to spectral embedding, node2vec directly into two dimensions and node2vec in five dimensions followed by Isomap (Figure D We use default configurations for all other hyperparameters. Together, the results support the central recommendation of this paper: to use matrix factorisation (e.g. spectral embedding, node2vec), followed by nonlinear dimension reduction (c.g. Isomap, UMAP, t-SNE).
4.2 Real data: the global flight network
(with license details therein) of the crowdsourced OpenSky dataset. Six undirected graphs are extracted, for the months November 2019 to April 2020, connecting any two airports in the world for which at least single flight was recorded (n 10, 000 airports in each). For each graph the adjacency matrix A is spectrally embedded into = 10 dimensions, degree-corrected by spherical projection 35
For this example, we use a publically available, clean version [52]
33 40
after which we apply
Isomap with c chosen as the 5% distance quantile.
The dimension was chosen as a loose upper bound on the dimension estimate returned by the method of [65] on any of the individual graphs, as to facilitate comparison we prefer to use the same dimension throughout (e.g. to avoid artificial differences in variance) and so follow the recommendation of [12] to err on the large side (experiments with different choices of p are in the appendix). In the degree- correction step we aim to remove network effects related to "airport popularity" (e.g. population, cconomic and airport size), after which geographic distance might be expected to be the principal factor deciding whether there should be a flight between two airports. Therefore, after applying Isomap, we might hope that 2, could estimate the geographical location of airport i. The experiments take a few hours on a standard desktop (and the same is loose upper bound on compute time for the other experiments in the paper).
The embedding for January is shown in Figures b))-b), before and after Isomap. Both recover real geographic features, notably the relative positioning of London, Paris, Madrid, Lisbon, Rome. However, the embedding of the US is warped, and only after using Isomap do we see New York and Los Angeles correctly positioned at opposite extremes of the country. As further confirmation, Figures cdd show the results restricted to North America, with the points coloured by latitude and longitude. For this continent, the accuracy of longitude recovery is particularly striking.
In line with the recommendation overestimate p 122, one obtains similar figure using p 20 before applying Isomap (Figure I0 appendix), whereas the corresponding figure with p = is too poor show.
In the appendix, the embeddings of all six months are shown, aligned using two-dimensional Procrustes, showing an important structural change in April. A statistical analysis of inter-continental
8

---

geodesic distances suggests the change reflects severe flight restrictions in South America and Africa, the beginning COVID-19 pandemic (the 1 11th March 2020 according to the WHO).
SE, first two dimensions (Jan 20)
b) SE Isomap (Jan 20)
AP
coloured longltude
Now York
Los
Los Angeles
Figure 3: Visualisation of the global flight network, January 2020. a) Spectral embedding. b) spectral embedding followed by Isomap, colours indicating continents (NA = North America, EU = Europe, Asia, AF Africa, OC Oceania), c-d) the same restricted North America, showing only the airports within the continent's s 5%-95% inter-quantile range of longitude and latitude, colours indicating the longitude (c) and latitude (d) of the airports.
4.3 Real data: correlations between daily temperatures around the globe
In this example A is correlation matrix and we demonstrate a simple model-checking diagnostic informed by our theory. The raw data consist of average temperatures over each day, for several thousand days, recorded in cities around the globe. These data are open source, originate from Berkeley Earth [1 and the particular data set analyzed is from [ We used open source latitude and longitude data from 4 See those references for license details. Removing cities and dates for which data are missing yields temperature time-series of 1450 common days for each of the 2211 cities. is the matrix of Pearson correlation coefficients between the n time-series.
Figure 4b) shows the spectral embedding of A, with 2 and points coloured by the latitude of the corresponding cities. Two visual features are striking: the concentration of points around a curved manifold, and correspondence between latitude and location on the manifold. Figure 4b) shows latitude against estimated latent positions from Isomap using the k-nearest neighbour graph with k = 200, which is roughly 10% of and with d = 1. A clear monotone relationship appears. Our theoretical results can explain this phenomenon. Notice that when
1, the additive structure the kernel in Proposition 3 disappears. Hence Proposition 3 shows that in the case d 1, for any kemel

---

a)
b)
50
0.5
50
0
-0.5
-50
-50
-150
-50
100
150
00.
0.5
Figure 4: Temperature correlation example. a) Locations in degrees latitude and longitude cities where temperatures were recorded, b) spectral embedding with p = 2, c) latitude of each city (vertical axis) against estimated latent position (horizontal axis) when d = 1. In all plots, points are coloured by latitude of the corresponding cities.
(meeting the basic requirements of section 3.1 including Assumptions and of course) D is equal Euclidean distance between Z; and Zj up their monotone transformation by d defined in (TO). In turn, this implies that if A did actually follow the model (I for some f and some "true" latent positions Zi.... Zn which we had access, we should observe a monotone relationship between those true latent positions and the estimated positions 2i...., 2n from Isomap.
The empirical monotonicity in Figure 4e) thus can be interpreted as indicating latitudes of the cities are plausible as "true" latent positions underlying the correlation matrix A, without having specify anything in practice about f. In further analysis (appendix) no such empirical monotone relationship found between longitude and estimated latent position; this indicates longitude does not influence the correlations captured in A. A possible explanation is the daily averaging of temperatures in the underlying data: correlations between these average temperatures may be insensitive to longitude due to the rotation of the earth.
5 Conclusion
Our research shows how cntrix-ffactorisation and dimension-reductio can work together to reveal the true positions of objects based only pairwise similarities such as connections correlations. For the sake of exposition and reproducibility, we have used public datasets which can be interpreted without specialist domain knowledge, but the methods are potentially relevant any scientific application involving large similarity matrices. Thinking about societal impact, our results highlight the depth of information in principle available about individuals, given network metadata, and hope to raise awareness of these potential issues of privacy.
Concerning the limitations of the methods we have discussed, the bound in indicates that should be "large" in order for QX, to approximate op (Z:) well. also has impact on the performance of Isomap: heuristically one needs a high density and a large number of points on or near the manifold to get good estimate of the geodesic distance. Thus the methods we propose are likely to perform poorly when n is small, corresponding e.g. to graph with small number of vertices.
On the other hand, in applications involving large networks or matrices (e.g. cyber-security, rec- ommender systems), the data encountered are often sparse. This is good news for computational feasibility but bad news for statistical accuracy. In particular, for graph, 2 can only be expected to hold under logarithmically growing degree, the information-theorete limit below which no algorithm obtain asymptotically exact embeddings [5]. What this means in practice (as illustrated in our numerical results for the simulated data example in the appendix) that the manifold may be very hard to distinguish, even for a large graph. Missing data may have similarly negative impact on discerning manifold structure. There could be substantial estimation gains in better integrating the factorisation and manifold estimation steps to overcome these difficulties.
Another limitation is that our theory restricts attention to the case of positive-definite kernels. When A is say correlation or covariance matrix the positive-definite assumption on the kernel is of course natural, but when A say an adjacency matrix, it is less natural assumption. The implications of removing the positive-definite assumption are the subject of ongoing research.
10

---

Funding Transparency Statement
Nick Whiteley and Patrick Rubin-Delanchy's research was supported by Turing Fellowships from the Alan Turing Institute. Annie Gray's research was supported by a studentship from Compass, the EPSRC Centre for Doctoral Training in Computational Statistics and Data Science.
References
[1] Berkeley Earth. http://berrkeeeyearbbccoo org Accessed: 2021-05-27.
[2]
Countries slammed their borders shut stop coronavirus. but is doing any good?
(countries-sl too
hatp://rinn--------------------- ---------nna--o--oo any-
Accessed: 2021-05-20.
[3] Climate change: Earth surface temperature data.
https:/ /wwp:///wwwww.... kaggle.g................k....... com/
http:p/arrrrauuaaee---er-aaaaere 2021-05-27.
Accessed:
[4] Simplemaps free entire world database.
httpe///sippDeaaps.cc//rreerrree free- conntry-ciiiieess cities Accessed: 2021-05-27.
[5] Emmanuel Abbe. Community detection and stochastic block models: recent developments, The Journal of Machine Learning Research, 18(1):6446-66 6,31,65511221 2017.
[6] Edoardo M Airoldi, David M Blei, Stephen Fienberg, and Eric P Xing. Mixed membership stochastic blockmodels. Journal of Machine Learning Research, 9(Se)):198 1981-0014, 2008.
[7] Shun-ichi Amari and Si Wu. Improving support vector machine classifiers by modifying kernel functions. Neural Networks, 1((6):783-789 1999.
[8] Arash A Amini, Aiyou Chen, Peter J Bickel, and Elizaveta Levina. Pseudo-likelihood methods for community detection in large sparse networks. Annals of Statistics, 41(4):2097-2122, 2013.
[9] Thomas Anglade, Christophe Denis, and Thierry Berthier. A novel embedding-based framework improving the User and Entity Behav- ior Analysis. working paper preprint, October 2019. URL. http::ttttsttttt
fr/hal-0231600
[10] Ernesto Araya Valdivia and De Castro Yohann. Latent distance estimation for random geo- metric graphs. H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019. URL /tt/ httpssnnurippi http://saar.rrs..c.ppp////////// pdf
[11] Ery crias-Castro, Antoine Channarond, Bruno Pelletier, and Nicolas Verzelen. On the estimation of latent distances using graph distances. Electronic Journal of Statistics. 15(1):722 - 747, 2021. doi: 10.1214/21-EJSS188 1001 URL httph::t//o.oiii. htt:///iiooor///// 10
[12] Avanti Athreya, Donniell E Fishkind, Minh Tang, Carey E Priebe, Youngser Park, Joshua Vogelstein, Keith Levin, Vince Lyzinski, and Yichen Qin. Statistical inference on random dot product graphs: a survey. The Journal of Machine Learning Research, 18 18(1):8933-8484, 2017.
[13] Avanti Athreya, Minh Tang, Youngser Park, and Carey E Priebe. On estimation and inference in latent structure random graphs. Statistical Science, 36( (1(())68-88)) 88, 2021.
[14] Peter Bickel, David Choi, Xiangyu Chang, and Hai Zhang. Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels. Annals of Statistics, 41 (4):1922-1943, 2013.
[15] Béla Bollobás, Svante Janson, and Oliver Riordan. The phase transition in inhomogencous random graphs. Random Structures & Algorithms, 31(1):3-122, 2007.
[16] Dmitri Burago. A course in metric geometry, volume 33. American Mathematical Soc., 2001.

---

[17] Joshua Cape, Minh Tang, and Carey E Priebe. The two-to-infinity norn and singular subspace geometry with applications to high-dimensional statisties. The Annals of Statistics, 47(5): 2405-2439, 2019.
[18] Ian Gallagher, Andrew Jones, Anna Bertiger, Carey Priebe, and Patrick Rubin-Delanchy. Spectral embedding of weighted graphs. arXiv preprint arXiv:1910.05534 2019.
[19] Chao Gao, Yu Lu, and Harrison Zhou. Rate-optimal graphon estimation. Annals of Statistics, 43(6):2624-2652, 2015.
[20] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864, 2016.
[21] Souleiman Hasan and Edward Curry. Word re-embedding via manifold dimensionality retention. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 321-326, 2017.
[22] Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches to social network analysis. Journal of the American Statistical Association, 97(460):1000-0999 2002.
[23] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.
[24] Svante Janson and Sofia Olhede. Can smooth graphons in several dimensions be represented by smooth graphons on [0, 1]? arXiv preprint arXiv:2101.07587 2021.
[25] Andrew Jones and Patrick Rubin-Delanchy. The multilayer random dot product graph. arXiv preprint arXiv:20077 2020.
[26] Olav Kallenberg. On the representation theorem for exchangeable arrays. Journal of Multivariate Analysis, 30(1):3371554 1989.
[27] Purushottam Kar and Harish Karnick. Random feature maps for dot product kernels. In Artificial intelligence and statistics, pages 583-591. PMLLR, PMLR, 2012.
[28] Zahi N. Karam and William M. Campbell. Interspeech 2010, pages 2742-272 2745, 2010. doi: 10.21437/hnterspeech.200 2010-720
for speaker recognition, In Proc.
[29] Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical Review E, 200,0010107,,1..1.,
[30] Neil Lawrence and Aapo Hyvärinen. Probabilistic non-linear principal component analysis with Gaussian process latent variable models. Journal of machine learning research, 6(11), 2005.
[31] Neil D Lawrence. Gaussian process latent variable models for visualisation of high dimensional data. In Nips, volume 2, page 5. Citeseer, 2003.
[32] Jing Lei. Network representation using graph root distributions. The Annals of Statistics, 49(2): 745-768, 2021.
[33] Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. Ann. Statist., 43(1):215-231 2015. ISSN 0090-5364, doi: 10.1214/14-A0S1222 URL
https://doi.. http::////ooooo///....o :ttp:///...o.......11/////////// A0S1274
[34] Lászlö Lovász. Large networks and graph limits. American Mathematical Society Colloquium Publications, volume 60. Amer. Math. Soc. Providence, RI, 2012.
[35] Vince Lyzinski, Daniel L. Sussman, Minh Tang, Avanti Athreya, and Carey E. Priebe. Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding. Electron. J. Stat., 8(2):295- 2014. doi: 10.1214/14-FJS975 URL, http::ttt::///ett :/doi. org/10...000 1214/
14 EJJ9788
12

---

[36] Vince Lyzinski, Minh Tang, Avanti Athreya, Youngser Park, and Carey E Priebe. Community detection and classification in hierarchical stochastic blockmodels. IEEE Transactions on Network Science and Engineering, 4(1): 2017.
[37] Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of machine learning research, 9(No)):2579 2605, 2008.
[38] Ashot Margaryan, Daniel Lawson, Martin Sikora, Fernando Racimo, Simon Rasmussen, Ida Moltke, Lara M Cassidy, Emil Jørsboe, Andrés Ingason, Mikkel W Pedersen, et al. Population genomics of the viking world. Nature, 585(7825) 2020.
[39] Leland McInnes, John Healy, and James Melville. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv: /802.03/002.3346.,, 2018.
[40] Alexander Modell and Patrick Rubin-Delanchy. Spectral clustering under degree heterogeneity: a case for the random walk Laplacian. arXiv preprint arXiv:2 102200050. 2021.
[41] Peter Petersen. Riemannian geometry, volume 171 of Graduate Texts in Mathematics. Springer, 2006.
[42] Carey E Priebe, Youngser Park, Joshua T Vogelstein, John M Conroy, Vince Lyzinski, Minh Tang, Avanti Athreya, Joshua Cape, and Eric Bridgeford. On two-truths phenomenon in spectral graph clustering. Proceedings of the National Academy of Sciences, 16(13):5995-6000 2019.
[43] Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Tang. Network embedding as matrix factorization: Unifying Deepwalk, LINE, PTE, and node2vec. In Proceedings of the eleventh ACM international conference on web search and data mining, pages 459-467, 2018.
[44] Karl Rohe, Sourav Chatterjee, and Bin Yu. Spectral clustering and the high-dimensional stochastic blockmodel. Annuls of Statistics, 39(4) 2011.
[45] Patrick Rubin-Delanchy. Manifold structure in graph embeddings. In Proceedings of the Thirty-fourth Conference on Neural Information Processing Systems, 2020.
[46] Patrick Kubin-Delanchh Joshua Cape, Minh Tang, and Carey E Priehe. A statistical inter- pretation of spectral embedding: the generalised random dot product graph. arXiv preprint arXiv:170..05506, 2020.
[47] Walter Rudin. Principles of mathematical analysix, volume 3. McGraw-hill New York, 1976.
[48] Michael Townsheno and Thomas Brendan Murphy. Variational bayesian inference for the latent position cluster model for network data. Computational Statistics & Data Analysis, 57(1):661-671, 2013.
[49] Francesco Sanna Passino, Nicholas Heard, and Patrick Rubin-Delanchy. Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel. arXiv preprint arXiv:2011.04553 2020.
[50] Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Nonlinear component analysis as kernel eigenvalue problem. Neural computation, 1299)1129,,31,, 1998.
[51] Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008
[52] Martin Strohmeier, Xavier Olive, Jannis Lübbe, Matthias Schäfer, and Vincent Lenders. Crowd- sourced air traffic data from the opensky network 2019-2020. Earth System Science Data, 13 (2):357-366, 2021.
[53] Daniel Sussman, Minh Tang, Donniell Fishkind, and Carey Priebe. A consistent adjacency spectral embedding for stochastic blockmodel graphs. Journal of the American Statistical Association, 1114999)1119-1122 2012.
[54] Wilson Sutherland, Introduction to metric and topological spaces. Oxford University Press, 2009.
13

---

[55] Minh Tang and Carey E Priebe. Limit theorems for eigenvectors of the normalized laplacian for random graphs. The Annals of Statistics, 46(5):2360-244) 2415, 2018.
[56] Minh Tang, Daniel L Sussman, and Carey Priebe. Universally consistent vertex classification for latent positions graphs. The Annals of Statistics, 41(3):1406-144 2013.
[57] Joshua B Tenenbaum, Vin De Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500))2319-233,, 2000.
[58] Michael E Tipping and Christopher M Bishop. Probabilistic principal component analysis. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 0L(3):611-622 1999.
[59] Michalis Titsias and Neil Lawrence. Bayesian Gaussian process latent variable model. In Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, pages 844-851. JMLR Workshop and Conference Proceedings, 2010.
[60] Warren Torgerson. Multidimensional scaling: I. Theory and method. Psychometrika, 17(4):
401-419, 1952.
[61] Michael W Trosset, Mingyue Gao, Minh Tang, and Carey E Priebe. Learning 1-dimensional submanifolds for subsequent inference on random dot product graphs. arXiv preprint arXiv:2004.07348, 2020.
[62] Jiaming Xu. Rates of convergence of spectral methods for graphon estimation. In International Conference on Machine Learning, pages 5433-5442. PMLR, 2018.
[63] Abubakar Yamin, Michael Dayan, Letizia Squarcina, Paolo Brambilla, Vittorio Murino, V Di- wadkar, and Diego Sona. Comparison of brain connectomes using geodesic distance on manifold: A twins study. In 2019 IEEE 16th International Symposium on Biomedical Imaging (ISBI 2019), pages 1797-1800. IEEE, 2019.
[64] Yichi Zhang and Minh Tang. Consistency of random-waad -wak based network embedding algorithms. arXiv preprint arXiv:2101.07354, 2021.
[65] Mu Zhu and Ali Ghodsi. Automatic dimensionality selection from the scree plot via the use of profile likelihood. Computational Statistics Data Analysis, 51(2):918 99000,99,,, 2006.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Abstract and Section [
(b) Did you descrihe the limitations of your work? [Yes] See Sections 2. and 3.1
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section 5
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section and Appendix A
(b) Did you include complete proof' of all theoretical results? [Yes] See Section 3.3 and Appendix A
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See Section and https:///gituutt com/ anni manieggry52// /grp/p//
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section f
14

---

(c) Did you report error bars (e.g., with respect to the random seed after running ex- periments multiple times)? [Yes] For Section 4.1 "set.seed(123) has been used and supplementary figures for Section 4.2 in the Appendix report enror bars.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 4.2
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See Section for data and we list all R packages used in Appendix B
(b) Did you mention the license of the assets? [Yes] For details on licenses of data see
Sections 4.2
4.3 and for packages see Appendix
(c) Did you include any new assets either the supplemental material or as URL? [Yes] https://github. www//om///a//c hammm/annggaa22//gmrer.
(d) Did you discuss whether and how consent was obtained from people whose data you're you're using/curating? [Yes] All datasets used are public datasets.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "opMEHFySzpO", "reviewer": "Reviewer_VpEa", "summary": "This paper considers the problem of finding the latent variables $Z$ given noisy observations of $f(Z_i, Z_j)$ with unknown $f$, and suggests applying matrix factorization (e.g. spectral embedding) + nonlinear dimension reduction (e.g. isomap). It shows mathematically that under some assumptions on the kernel $f$, finding geodesic distance in the manifold (which the matrix factorization step approximates) is equivalent to finding the geodesic distance in the original latent space. Experiments on simulated and real-world data are provided.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper seems sufficiently different from the cited works [12] and [57], and appears to be the first to provide theoretical analysis with general kernel $f$ and continuous variables $Z$. This work could be an important step to more rigorously understanding why nonlinear dimensionality reduction methods work so well in practice.\n\nThe main question I have is regarding the air traffic data experiment. Why should LA and NY be far from each other in the embedding space? Is the hypothesis that the latent variable $Z_i$ is the geographical location of city $i$? Since there are a lot of other factors (e.g. population, economic size, airport size) that go into deciding whether there should be a flight between two cities, one could even argue that LA and NY as two coastal hubs should be close to each other in an embedding space. Also, how are we meant to interpret the structures in Figure 3 c? For example, what does it mean for points to be spread out vs. clumped? What are the clusters within North America?\n\nThis paper is written clearly and easy to follow, but I have a few clarification questions:\n- Typo in Theorem 1, \"Let $a$, $b$ any two points\" -> \"Let $a$, $b$ be any two points\".\n- In page 2 last sentence, a graph adjacency matrix is not necessarily sparse.\n- Is the norm in (2) and the following paragraph the l2 norm?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "hGN9_6NB0Vd", "reviewer": "Reviewer_MXyX", "summary": "This paper considers the problem of sensing a notion of the true distance between nodes of a \nnetwork. This allows to estimate the true position of these nodes up to pairwise scaling. The \ncradle of this approach is essentially organized into two steps: a) compute a matrix factorization \nof the matrix associated with the graph, i.e., spectral embedding, and b) perform a nonlinear \ndimensionality reduction step. The main observation, subject to necessary conditions, is that \nEuclidean distances of the spectral embeddings agree with geodesic distances between the \ngraph nodes. Numerical experiments provide evidence that the proposed approach works.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "-) The paper is relatively well-written, although some improvements in written English would \nbe welcome (also, the authors use the word \"between\" too often). \n\n-) The theory appears to be correct; at least up to the part I could confidently follow it. Moreover, \nmost concepts discussed in the paper are clear, and previous work is mentioned.\n\n-) One think I missed is comparison with other methods. Is the case that no other methods \ncan solve these problems? Euclidean distance to geodesic distance mappings are a well \nstudied topic. \n\n-) Other applications can be found in:\nhttps://www.isca-speech.org/archive/archive_papers/interspeech_2010/i10_2742.pdf\nhttps://arxiv.org/pdf/1902.01395.pdf\n\nWhat is new compared to those viewpoints?\n\n-) It is my impression that the new approach need a few parameters to have the proper \nvalues in order to work. How the value of hyperparameters (e.g., dimension of spectral \nembeddings) affects the performance of the proposed approach for the real datasets? \nHow about other methods?\n\n-) Line 109: did you mean to say \"Wasserstein distance\"?\n\n-) Line 112: \"legitimately\" is a rather strange word in this context. Please rephrase.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "8oZszLo_BWQ", "reviewer": "Reviewer_5XMg", "summary": "The manuscript shows that by combining matrix factorisation with dimension reductions, one is able to reconstruct data (up to some invariances) by only considering a kernelised set. The main contribution is to show an explicit relation between the geodesic distances in the manifold that supports the kernelised data, and the distance of the original data set with respect to a Riemannian metric.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results themselves are interesting and open up possibilities for further research and applications. As this is a mainly theoretical paper, the experiments are not as important as the theoretical results and does not detract that much from the quality of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "These results are supplemented by experiments on both synthetic data, and two real datasets. The experiments are not incredibly in depth and it is hard to say exactly how \"good\" they are. I can appreciate the lack of benchmarks here, but if possible it would be nice to see some sort of comparison or discussion of the quality of the results.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "1-6WWONXTbZ", "reviewer": "Reviewer_2QqF", "summary": "The paper considers the problem of recovering a notion of distance between the nodes of a graph. The authors write their main problem very abstractly and provide an excellent description of particular A's, f's, and Z_i's that are of interest in a wide range of applications. The main contribution is to prove that a low-dimensional embedding is related to a topological manifold.  In this regard, it is a follow-up to results by Rubin-Delanchy in [21] from 2020.  The paper seems to be well written, though I was not able to follow all the technical details in the supplementary material as it is pretty far from my expertise.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors start with problem statement (1) but later make a few more assumptions on f (e.g., pos. def., f is C^2, Hessian is pos. def., and a non-degeneracy condition). I think the authors will want to notify the readers at least that those assumptions are coming.  The authors mentioned that it is technically challenging to extend their results to the case when f is symmetric but not positive definite. What are the issues there? One issue is that the eigenvalue decomposition (a.k.a. Mercer expansion for pos. def. functions) is no longer uniformly and absolutely convergent to f.  I am under the impression that if one assumes that f has a little more regularity (e.g., Lipschitz continuous in both variables separately), one can keep the uniform and absolutely convergent properties for symmetric f. I am not aware of a particular reference, though, but Schmidt, Weyl, Smithies, Hammerstein, and Brown were interested in this. \n\nTheorem 1 is an excellent result that tells us that finding the geodesic distance in M is equivalent to minimizing path-lengths in Z under the Riemannian metric.  Section 3.3 is welcomed as it shows the potential use of that connection. Can the authors add a comment on why f needs to be C^2? \n\nThe practical applications also look impressive as a non-expert in the field of spectral embedding. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "While the authors did make assumptions and the methodology does have limitations, the authors did not address the consequences of these limitations in terms of the potential applications. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper revisits the problem of recovering positions of points given the similarity information. It proposes to do: first, a spectral embedding and second, a nor linear embedding to obtain the positions. As reviewers note, the interesting contributions are in connecting the geometry between spectral approximations (X) and true embeddings (Z). Overall, the theory and experiments are interesting. A minor comment, currently, the paper assumes that A is fully known and the theory goes through. What happens A is partially known (akin to recovering positions from partial similarity information). What kinds of consistency results are required for the approximations to succeed? 

Decision: Accept (Poster)