Neuc-MDS: Non-Euclidean Multidimensional Scaling Through Bilinear Forms
Authors: Chengyuan Deng
Jie Gao
Kevin Lu
Feng Luo
Hongbin Sun
Cheng Xin
Venue: NeurIPS 2024 poster (2024)
Keywords: multidimensional scaling
dimension reduction
non-Euclidean geometry
Primary area: learning_theory
TL;DR: We introduce Neuc-MDS, an extension of classical multidimensional scaling to the non-Euclidean non-metrical setting.

Abstract: We introduce \textbf{N}on-\textbf{Euc}lidean-\textbf{MDS} (Neuc-MDS), which extends Multidimensional Scaling (MDS) to generate outputs that can be non-Euclidean and non-metric. The main idea is to generalize the inner product to other symmetric bilinear forms to utilize the negative eigenvalues of dissimiliarity Gram matrices. Neuc-MDS efficiently optimizes the choice of (both positive and negative) eigenvalues of the dissimilarity Gram matrix to reduce STRESS, the sum of squared pairwise error. We provide an in-depth error analysis and proofs of the optimality in minimizing lower bounds of STRESS. We demonstrate Neuc-MDS's ability to address limitations of classical MDS raised by prior research, and test it on various synthetic and real-world datasets in comparison with both linear and non-linear dimension reduction methods.

Neuc-MDS: Non-Euclidean Multidimensional Scaling Through Bilinear Forms
Chengyuan Deng, Jic Gao, Kevin Lu, Fong Luo, Hongbin Sun, Cheng Xin"
Abstract
We introduce Multidinensional Scaling (MDS) that accommodates non-Euclidean and non-metric inputs. The main idea is to generalize the standard inner prod- uct to symmetric bilinear forms to utilize the negative eigenvalues of dissim- ilarity Gram matrices. Neuc-MDS efficiently optimizes the choice of (both positive and negative) cigenvalues of the dissimilarity Gram matrix to re- duce STRESS, the of squared pairwise error. We provide an in-depth error analysis and proofs of the optimality in minimizing lower bounds STRESS. We demonstrate Neuc-MDS's ability to address limitations of classical MDS raised by prior research, and test on various synthetic and real-world datasets in comparison with both linear and non-linear dimen- sion reduction methods.
(Neuc-MDS), extension of classical
1 Introduction
Many datasets in applications adopt dissimilarities that non-Euclidean and/or non- metric. Examples of such popular dissimilarity measures []9 7 include Minkowski distance (Lp), cosine similarity, Hamming, Jaccard, Mahalanobis, Chebyshev, and KL-divergence, Studies in psychology have long recognized that human perception of similarity is not metric 42 Further, dissimilarity matrices with negative entries (e.g.: cosine similarity, correlation, signed distance) have also been widely used in various problems. Negative inner product norms also have deep connections to hyperbolic spaces as well as the study of spacetime in special relativity theory.
In many machine learning practices, embedding in low dimensional vector space is often ex- plicitly or implicitly done within the data processing pipeline. Such embedding may already need consider more general dissimilarities. For example, one branch of graph learning adopts embedding in non- -on-Euclidcan spaces (e.g., hyperbolic spaces [ and machine learn- ing for physics model and data (AI4Sicence) needs consider more general inner product norms [2]] In transformer models 45 13 the attention mechanism can also be viewed as learning a general bilinear form on tokens. Despite the wide adoption of general dissim- ilarity measures in practice, theoretical study of embedding and dimension reduction for non- Eun-uucideen non-metric data appears to be still very limited.
In this paper we consider one of the most classical algorithms for data embedding and dimension reduction multidimennsonal scaling and develop non-Euclidean, non-metric version with thcoretical performance guarantee.
Background on MDS. Classical multidimensional scaling (cMDS) takes as input Eu- clideon distance matrir (EDM), i.e., a symmetric matrix /) E T where each entry is the squared Fuclidean distance between two points in Fuclidean space, and recovers the Fuclidean coordinates. Using a standard double centering trick, D can be turned into a
Rutgees University. (cd751.jg1555, k11660, fluo hongbin.sum cx122) @rutgers.
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

Gram matrix B = X"X where X encodes the Euclidean coordinates. For the purpose of producing a low-dimensional vector, classical MDS takes & eigenvectors corresponding to top & largest eigenvalues of the Gram matrix B. This minimizes the strain, the difference (Frobenius norm) terms of the Gram matrix.
When the input distance matrix is not a Euclidean distance matrix, this problem is called metric MDS []. Metric MDS considers the minimization of STRESS 2 defined as the sum of squared difference of pairwise embedding distances to the input dissimilarities. Min- imizing STRESS makes the problem be non-lincar and there no closed-form solution, though one can use either gradient descent or Newton's 's method 335 26. Nevertheless, in practice, cMDS is often applied for non- non- Euclidean distance matrix. In this case, the centered matrix B is no longer positive semi-definite. The common practice is keep the top positive eigenvalues and throw away the negative eigenvalues.
Two recent papers 41 88
pointed out that classical MDS produces suboptimal solutions on non-Euclidean distance matrix when considering STRESS. This is not surprise, since cMDS, minimizing strain, does not minimize STRESS. However, a more problematic issue is that when using more dimensions in cMDS (i.e., increasing k), the STRESS error first drops and then increases. We call this phenomena Dimensionality Parador. It is theoret- ically unsatisfactory and counter-intuitioe that embeddings by classical MDS using more dimensions could yield worse results.
The error analysis in BS sheds light on this issue. When the input matrix is Non-Euclidean the negative eigenvalues carry crucial information. cMDS, keeping only positive eigenvalues, is intrinsically biased - the more positive eigenvalues used the more it deviates from the input data. A real eradication of this issue must address the root cause, i.e., applying an algorithm meant for Euclidean geometry on non-Euclidean data.
Our Contributions. We extend multidimensional scaling to non-Euclidean geometry, by generalizing the dissimilarity function from the standard inner product (which defines Eu- clidean geometry) to the broader family of symmetric bilinear forms (u,,)) = u² AA, where the symmetric matrix A does not have to be positive semi-definite. For dimension reduction, we look for both a low dimensional vector representation and an associated bilinear form, that together approximate the input dissimilarity matrix with minimum STRESS error. Specifically, the key contributions are as follows:
We conduct an in-depth analysis STRESS error for any chosen subset of k < n eigen- values of the input centered dissimilarity matrix. We propose Neuc-MDS, an efficient algorithm that finds the best subset of eigenvalues to minimize a lower bound of STRESS.
Beyond the constraints of eigenvalue subsets, we extend our findings to the general linear combinations of eigenvalues. Our advanced algorithm, Neuc-MDS*, finds the best linear combination of cigenvalues to minimize the lower bound objective.
We provide thcoretical analysis for the asymptotic behavior of cMDS and Neuc-MDS on random symmetric matrices. First, both necessarily produce large STRESS if the target dimension k o(n) on completely unstructured data aggressive dimension reduction shall not be expected. Further, when k = (n), the STRESS of Neuc-MDS monotonically decreases to 0 while the STRESS of cMDS increases and eventually reaches a plateau.
Empirically evaluate Neuc-MDS and Neuo-MDS+ on ten diverse datasets encompass- ing different domains. The experiment results show that both methods substantially outperform previous baselines on STRESS and average distortion, and fully resolve the issuc of dimensionality paradoz in cMDS. Our codes are available on Githul??
2 Related Work
Our work is in the general family of similarity learning 25 3 with dimension reduction, going beyond metric learning and embedding. Due to the huge amount literature on this topic we only mention those that are most relevant.
httpe: //tp://bgttttcc//// wttp.///c///..1///55111
2

---

MDS Family and Embedding in Euclidean Spaces, As one of the most useful em- bedding and dimension reduction techniques in practice, the MDS family has many vari- ants. Non-metric MDS 36 37 considers monotonically increasing function f on input dissimilarity and minimizes STRESS between {f(D:,) and embedded squared Fuclidean distances. Generalized multidinensional scaling (GMD) considers the target space as an arbitrary smooth surface G.. In addition, non-linear dimension reduction methods such as Isomap B9], Laplacian Eigenmaps 2. LLE [34, t-SNE 23 44 consider data points from a non-linear high-dimensional manifold and extract distances defined on the manifold. In all these methods, the points are still embedded in Euclidean spaces. Some of these meth- ods such as Isomap directly apply cMDS as the final step. If the dissimilarity is highly -on-Eucl,, can replace cMDS by Neuc-MDS to get performance improvement.
Dimension Reduction in Non-Euclidean Spaces. There is also prior work that finds embedding of manifold data in non- non-Euclidean spaces, e.g., a piece-wise connected man- and in hyperbolic spaces 15 13
ifold 50 5d on sphere [ 15
48
Very recently,
there is study of Johnson Lindenstrauss style dimension reduction for weighted Euclidean
space 30,, hyperbolic space [
as well as PCA S dimension-eeductte [6], and t-SNE in
hyperbolic space P0. Our dissimilarity function generalizes beyond hyperbolic distances.
3 Dimension Reduction with Bilinear Forms
Let P denote a dataset of size n. Let D E Rax" be the dissimilarity matrix of dataset P. Dij = Djs is real-valued symmetric dissimilarity measure between pair Pi.Pj E P, i jEj [n], and all diagonal entries Dú = =0 (i.e., D is a hollow matrix). D is the analog of squared Euclidean distance mairix in classical MDS. But here is not necessarily Fuclidean, may not be metric (e.g. violating triangle inequality) and may have negative entries. Our goal is to obtain (1) a low-dimensional vector representation for each element in P, and (2) function f that computes dissimilarity measure using the calculated low dimensional vectors. Since the input dissimilarities are not necessarily Euclidean nor a metric, we look for the function f beyond Euclidean distances, but stay within broader family of inner products or bilinear forms.
A bilinear form & on a vector space V is a function V - R which is linear in each variable when the other variable fixed. More precisely, $(au + u, w) = a (u, w²) + w) and o(w, ((w,au+r) au+ = ad(we, u) + +(w, v) for all u, U, w V and any scalar a. We only consider symmetric bilinear forms 4, i... 2(u, v) = L(v u). A bilinear form is positive definite (or positive semi-definite) if 4(u, u) > 0 for Vu of 0 (or 4(u, u) 2 0). Symmetric matrices and symmetric bilinear forms are two sides of a coin. Namely, fix a basis W = [wI..., w.. of the vector space, there is one-to-one correspondence between them. That is, A [#(w, wy)laxn is a symmetric matrix. Conversely, give a symmetric matrix A, one defines a symmetric bilinear form (u,, v) = Anw where uw is the coordinate vector u in the basis W.
Formally, we have the following problem definition.
Definition MunlEuecl Dimension Reduction). Given symmetric dissimilarity ma- tris D of dataset P of size n and a natural number k S n, find a collection of n k- dimensional vectors P = (fr. Pn : P. E R$) with bilinear form f: : R x R + R. f(u, v) = u² Av, such that the STRESS error ||D 1/ for the dissimilarity matriz D of P given by Dig- = f( is minimized.
3.1 MDS in the Lens of Bilinear Forms
A special case of a symmetric bilincar form is the standard inner product (.) on R". Indeed the inner product (u. v) = uTv is a symmetric positive definite bilinear form. The inner product of u - v and u is precisely the squared Euclidean distance ||u - v/|2. The Euclidean space R" equipped with the standard inner product. Thus metric geometry of Euclidean space is governed by the inner product. On the other hand, basic theorem of linear algebra states that a finite dimensional vector space equipped with a symmetric posilive definite bilinear form is isoetric to the Fuclidean space of the same dimension.
3

---

Thus geometry of a positive definite symmetric bilinear form, or symmetric positive definite matrices, is nothing but Euclidean geometry.
When represents the inner products of pairwise differences (i.e., squared Euclidean dis- tances) of n points P in IR4, D is called a Euclidean distance matrix (EDM). It can be shown that by taking B -DDCC, where C = 1 - 1,,17 is the centering matrix and 1, is vector of ones, one obtains the Gram matrix B X X where X is d dimensional matrix of the n coordinates of dimension d. The matrix B is symmetric positive semi-definite matrix. Thus using eigendeccomooitionn of B one can recover the coordinates X. This pro- cedure is classical multidimennsonaal scaling (cMDS) 40 Furthermore, if one would like to use k-dimension coordinates with < d, classical MDS suggests to take the eigenvectors corresponding to the & largest positive cigenvalues of the Gram matrix B. This minimizes the strain, the difference (Frobenius norm || (|x)) in terms of the Gram matrix.
X Xemds arg min || X X - - )|
-CDC
XEROXA
Now consider a general symmetric dissimilarity matrix D size n,, it naturally associates R" with symmetric bilinear form &. In many real-world situations, the dissimilarity matrix is not positive, nor negative definite, ie.. the bilinear form is indefinite. This means the intrinsic geometry (IR", ②) is non-Euclidean. The relationship between the Gram matrix and square distance matrix still holds for indefinite bilinear forms. See Appendix A
In practice, classical MDS is often the default choice matrix D is not an EDM, i.c., the centered matrix B = CDC is not positive semi- definite. Classical MDS, which simply drops negative cigenvalues of B to produce positive semi-definiteness does not respect the geometry well. Indeed, multiple researchers have observed suboptimal and counter-intuitive performance A1 38 may lead to increased STRESS error keeping more dimensions makes the approximation worse! On second thought, such results are not surprising. If the input data does not carry Euclidean geometry, forcing it through a procedure for Euclidean geometry is fundamentally problematic.
when the input dissimilarity
For example, increasing
Our main observation is that a vector space with an indefinite symmetric bilinear form has its own intrinsic geometry. This geometry, even though may not be metrical, carries the most accurate information about the dissimilarity matrix and the datasets. Suppose the centered matrix B = CCC has p positive eigenvalues and q > 0 negative eigenvalues. The associated indefinite bilinear form & has signature (p,4). One such example is
p++-
((,, v)
Σ U:U
Σ
i=pt1
The geometry of finite dimensional vector space with symmetric bilinear form of signature (p, q) where p. q > 0 much less developed compared to Euclidean geometry. When q = 1, this is the Minkowski geometry and is closely related to relativity theory in physics and hyperbolic gcometry [3 in mathematics. For general (p. q), one should probably abandon the notion of distance for indefinite spaces. Namely, the expression 4(u- V, v), even if it is positive, should not be considered as the square of the distance between two points u, U. According to [3 one calls / - U, u -a-v) v) the Lorenzian distance between u, v. Despite the term distance in the name, the Lorenzian distance does not satisfy triangle incquality in general.
3.2 Non-Euclidean MDS
We propose Non-Euclideon MDS, novel linear dimension reduction technique using bilinear forms. For a vector v, we use Diag(r) as the diagonal matrix with v along the main diagonal and zero everywhere clsc. For any given symmetric dissimilarity matrix D R let the cigen dccomposition of the centralization of D be given as follows:
-CDC/2 UNUT
(3)

---

where U E R=x* is the orthogonal matrix of eigenspace and A E R is the diagonal matrix A =: Diag(A) with eigenvalues X _ (A,...., An)", X 2 X2 .... An By using an algorithm that will be discussed in Section we will choose of the eigenvalues, represented by binary indicator vector w = (W1,-.- wn) E 10" with a value of (or 0) indicating the corresponding cigenvalue is chosen (or not chosen). Let
X = VA Diag(w) U² =: (X1, ;,n),
(4)
Note that VA contains complex numbers for non- non-PSD matrix D. Since w has only k non- zero values, we can drop the n - & zero rows in X (corresponding to the eigenvalues not selected) and have k-dimensional vector representation of the data. Now can derive dissimilaritics by defining
Drs - (X, (x) Xj), D DIS(X) = (Dis).
See 1 for details.
Algorithm 1: Non-Fuclidean Multidimensional Scaling
Input: n x dissimilarity matrix D, integer l S n.
Output: n matrix X of k-dim vectors
B == - where C' = I 11,1
Compute eigenvalue vector À and eigenvectors U of B: A A2, An)² with d 2 22 2- -.2 Ani
Compute the indicator vector of & selected eigenvalues w BV-Selection(,, k);
Compute X by VA Diag(w) U with k zero rows dropped;
In the description above, we allow the coordinates in X to take complex numbers, such that we can take Dr, to be the standard dot product of X, X3 with X, - Xy. Al- ternatively, we can keep X to take real coordinates, i.e., X v Diag(w)- U2 with A' AI,, A.,,.... (Aml).. Again we drop the n - k zero rows in X and take a bilinear form ((, u² Au, where A is k by k diagonal matrix, with the element at (i, to be (or -1) if the corresponding eigenvalue chosen is positive positive/negative /negative. Notice that the bilinear form takes precisely the format of (p. disttaae as in Equation (2).
We have a few remarks in place: First we are not throwing away the negative eigenvalues. As will be explained later we actually keep eigenvalues of largest magnitude and some could be negative. As a consequence D may have negative real values, which is expected as are moving away from Euclidean distances and input entries in may even start to be negative. Second, when D is FDM,, i.e., all eigenvalues classical MDS. Last, similar to cMDS, our method also starts with computing the eigenvalues of the Gram matrix. For large datasets, fast (approximation) algorithm for partial SVD can also be applied to our methods. For example, on n X symmetric matrices, using power methods one can iteratively compute partial SVD up k barges//smallest eigenvalues in Okn²). With randomness introduced, it can be reduced to O(log k n²) [8 277. For really large datasets, the dissimilarity matrix with size O(n²) might already be too large to be acquired or stored, one may extend MDS through local embedding methods like Landmark MDS [2] or Local MDS I0. This approach can also be applied to neuc-MDS to substantially speed up computation without suffering too much on performance (See
non-negative, Neuc-MDS reduces to
Section for empirical results).
4 Theoretical Results for Non-Enclidean MDS
To establish the foundation of theoretical analysis, we first analyze the STRESS error of Neuc-MDS and decompose it into three lerms. Next we show elficient algorithm that minimizes the first. two terms that dominate. Last, we examine Neuc-MDS and classical MDS on random Gaussian matrices.
5

---

4.1 Error Analysis
Inspired by the analysis of STRESS of classical MDS BIS we adopt similar approach and decompose the STRESS error into three terms. Let X E R" be the vector of all eigenvalues A (A1..... .,n)", X R" be the vector of all squared eigenvalues A (Ai.... X2. io - I, w be the indicator vector of dropped eigenvalues, to {0. 1)" and @ be the Hadamard product. We have the following result with proof in Appendix B
Theorem 2. It holds that || - D12 = C1 + C2 + C3, where
= 400 C2 = 4(w=>)² C3 = 2n @ ( A)l - C2/2.
Note that C1/4 is the sum of squared eigenvalues that are dropped, and C2/4 is the square of the sum of eigenvalues that are dropped. Individually, we minimize C1 by keeping eigenvalues large absolute value; and C2 by balancing the dropped eigenvalues such that
the summation has small magnitude. For term C3, from Equation 21 in Proof B we know 2.0 In 38 it is argued that if one takes the approximation (" O X)I for a random orthogonal matrix U, then C3 ~ Although is
T(U + U C
A) R
X)
empirically observed in B8 that C3 is roughly constant and hence negligible for optimization, there are some cases in our experiments in which C3 is not negligible.
In light of Theorem 2 we would like to approximately optimizing the STRESS by minimizing the lower bound C1 + Cz. which can be formulated as a quadratic integer programming
problem: Given set of n values L = {Ri} and a positive integer & >> 0, choose a k-subset S L such that
min SCC,JS =k
Σ AECiS
X2
(E A)² AEC'S
(5)
When Ay's are all positive, the best choice is to take the k largest eigenvalues of C, i.e., the cMDS' solution. However, with a mixture of positive and negative eigenvalues, taking the top & largest eigenvalues is no longer optimal specifically, error term is monotonically reduced but the second error term could start going up. In the following subsection, we discuss an optimal algorithm solve Equation (5).
& increases, the first
4.2 An Optimal Algorithm for Eigenvalue Selection
The optimization problem described in Equation (5) a special case of the family of quadratic integer programming problems. Though in general, quadratic integer program- ming is Na-hard [I] we show that this particular one is actually solvable in polynomial time. Formally, we have:
Thcorem 3. For the optimization problem defined in 5 there erits optimal solution with r largest positive values and s smallest negative values in L, + k. And, there is alggoortm that outputs optimal solution.
Our algorithm (2) is greedy and iteratively selects the eigenvalue with the highest absolute value. Specifically, let be the set of selected eigenvalucs and HS) be the sum of cigenvalues not selected. Initially = 0. In cach iteration, if HSS) < 0, select the negative cigenvalues remained of the greatest magnitude and add it to S: if H(S) > 0, pick the largest positive one. If (S)) O, pick the eigenvalue with the greatest magnitude. The complete proof of Theorem is delayed to Appendix C
4.3 Analysis Random Symmetric Matrices
Here, we analyze the important error term C1 + C2 in Theorem 2 for cMDS and Neuc-MDS when the input (centered) dissimilarity matrix is symmetric random matrix. Our analysis is ostablished upon Wigner's 's famous Semicirele Law 46, [47, which states the following.
Proposition 4 (Semicircle Law 47). Suppose B E R=*X is symmetric random matriz where every element is independently distributed with equal densities and second moments o². Let (B)(B) be the number of eigensalues of B that lie in the interval (a byn). Then the expected value (Saa,((B) of Sa, satisfies
F F(S,,b(B))
lim
440² r2dr.
(6)
12000
2 0

---

Algorithm 2: Eigenvalues Selection for Neuc-MDS
Input: L: sorted set of eigenvalues, integer k.
Output: eigenvalues 5 Initialize S =00, repeat.
Compute H(S) Exerrs
Select an eigenvalue X such that X (()) 2 0 and X has the largest. absolute value. Add X to S. until | k;
Our results are formally stated as follows with proof in Appendix D
Theorem 5. Suppose a random symmetric matrix B E |R where Baj is independently distributed with equal densities and second moments o², is taken as the centered matri 3 to classical MDS and Neuc-MDS, both selecting k eigenvalues with k I n. Let ec denote the C1 + C2 error for cMDS and eN for Neuc-MDS, we have:
1. when k = o(n), ec o² 4k² 1h), and EN n2 n 2. when k- = cn, with c c 1, eN = O. When 2 1/2, ec = 0.1801 1 n²0²
By Theorem Neuc-MDS has a strictly better C + C2 error than cMDS. Second, if we take | = < n [C], the term C₁ ExECys s X² is almost equal to Exec X² x n²o². Therefore the STRESS error of both classical MDS and Neuc-MDS cannot be very small if the target dimension k is o(n). Lastly, when k = en, with c c 1, eN is monotonically decrcasing and eventually reaches reaches a plateau at about 0.1801 n²o?. Notice that this error has an extra factor of compared the error for small k.
On the other hand, for cMDS, when e 2 1/2, eC
For real world data the Gram matrix is likely far from a random matrix. The analysis above points out that aggressive dimension reduction can be indeed only luxury for structured data, even we use inner products that are not limited to Euclidean distances. Second, any real world data carries some random measurement noise. When the scale of such random noise becomes non-negligible, STRESS error introduced by such noise cannot be small with aggressive dimension reduction. We would recommend practitioners examine the spectrum of cigenvalues to gain insights on the power or limit in reducing dimensions.
5 Beyond Binary Selection of Eigenvalues
Both cMDS and Neuc-MDS choose a subset of eigenvalues from the input Gram matrix. This be considered applying Diag(w) to the eigenvalue vector A (Equation 4 to filter some eigenvalues out. Such operators can viewed as a special case of more general low-rank linear maps T R + RD with rank(T)) = k
Here we consider new family of embeddings X UA1/2 with being rank-k diagonal matrix whose diagonal entries are given by some À E I²" with only k nonzero entries. Note that there always exists rank-k linear operator T such that X = T()). Then we ask if we can improve Meuc-MDS further with a rank-k linear map of X? This question can be answered by the following theorem:
Theorem 6. Given dissimilarity matrix D E Rax with eigenvalues A E R" of its Gram matria -CDC/2 = UAUT, for any rank-k (k S n) diagonal matria Á = Diag(A) with À E R" with & nonzero entries only on coordinates given by some inder k-set W S [n), let w = 1w E 13" be the indicator vector of W, and let D be the dissimilarity matrix reconstructed from X = A Then the STRESS error of D can be erpressed as:
3 'Here take B the centered matrix. Therefore the diagonal entries of B do not have to be Further, the distribution of centered matrix (ignoring the scaling factor) C'AC' the same as the distribution of ((A) plus an additional zero eigenvalue. Therefore, one can consider ((A) sampled from random matrices. When + they are asymptotically the same. See more discussion in the appendix (Lemma 12

---

| D1 = C1 + C2 + C3 with
O2 w T (2) + w A 4= + w Ao=A 2n|(U ())
6 0=
2
where == - X.
The first two terms, C + C2, as lower bound of the STRESS,
minimized as
4( X)2 Au A (2)
w X 1+k
with X to be X = N 1+k
(7)
Remark 7. Recall the decomposition of STRESS in Theorem the lower bound 4w X + 4(w²A)² X)2 = C + C2/kk + +1 S C22. Therefore, it has a better lower bound of STRESS compared to Neuc-MDS.
Theorem 6 provides constructive way to obtain the optimal À that (approximately) mini- mizes the STRESS error for a prefixed w which is determined by an indicator set W served nonzero entries on X. The next question how to find an optimal k-set W on which the optimal X has the lowest lower bound. Essentially, we need to solve the following optimization problem:
as the constraints
min Σ
{ x)²²
1 1+k
(8)
LiGW
eEW
Proposition 8. For the optimization problem ( there erits an optimal solution with largest positive values and s smallest negative values in C, r k. And, there an (())aalgriihhm that outputs the optimal solution.
The algorithm follows a similar greedy manner EV-SELECTION, with only one adjustment: in each step, compare the two marginal gains provided by the largest positive eigenvalue and the lowest negative eigenvalue among the remained ones, and choose the positive nnveeeggevvve eigenvalue of largest magnitude if the corresponding gain is smaller. We name the algorithm Neuc-MDS+, and present the complete algorithm with its correctness proof in Appendix
Experiments
This section presents experimental results of Neuc-MDS and Neuc-MDS+. First, we evaluate the performance on dissimilarity error of two proposed algorithms comparing with closely- related baselines three metrics: STRESS, distortion and additive error. Then we show that the dimensionality parador issue observed on cMDS fully resolved by Neuc-MDS and Neuc-MDS*.
Synthetic Data. We introduce two synthetic datasets: Rondom- Rondom-simpler and Euclidean- ball, both with non-Fuclidean dissimilarities. See details in Appendix F.T] On high level, suppose the dataset has size n, we construct Random-simpler such that. for each vertex, the first n coordinates virtually form simplex, while the last coordinate almost dominates the distances between the other points, which creates a large negative eigenvalue for the Gram matrix. The Euclidean- ball dataset (similarr to Delft's 's balls [1] considers n balls of different radii with the distance of two balls defined as the smallest distance of two points on the two respective balls. The dissimilarities by this definition no longer satisfy triangle inequality.
Real-world Data. We consider both genomics and image data. For genomics data, we include datasets from the Curatod Microarray Databasc (CuMiDa) 17. each indicating certain type of cancer. Following the practice mentioned in AB,. pairwise dissimilarities are generated with entropic affinity with the diagonal as zero. We also test three celebrated image datasels: MNIST, MaSHion-MNIST and CIFAR-10. The dissimilarity matrix for each
dataset captures 1000 images randomly sampled for each class. We use three measures in 88 to calculate the dissimilarities.
8

---

An essential guidance of our choice of datasets is the existence of substantial negative eigen- values. Otherwise, Neuc-MDS and cMDS are equivalent. Figure the eigenvalue distribution of the Renal dataset. shows the basic statistics of each dataset and the number of negative eigenvalues of the Gram matrix. All datasets are non-Fuclidean and non-metric.
Figure 1: Negative (red), positive (blue).
Table 1: Datasets used in experiments.
Elgenvalues Distribution Renal
Dataset
Size
[A < 0)
Classes
Metric
Simplex
1900
Ball
1000
887
N.A.
Brain
130
5d
5
20
Colorectal
194
Lenkemia
281
117
Romal
143
57
Fashion
1000
429
10
CIFAR 10
1000
399
10
Basclines. We inchude cMDS, Lower-MDS
38 and SMACOF (Scaling by MAjorizing
COmplicated Function) 24 rank, trace-zero, and positive semi-definite matrix. SMACOF minimizes STRESS using majorization and is of the best nonlinear optimization algorithms for MDS. All methods are deterministic therefore variance is not concerned.
basclines. Lower-MDS
3S
looks for symmetric, low-
Table 2: Evaluation Results STRESS.
Dataset
cMDS
Lower-MDS
Neuc-MDS
Neuc-MDS*
SMACOF
Random- Simplex
80.520
31.542
1.179
0.194
15.962
Euclidean Ball
36.975
17.303
1.196
1.351
4e6
Brain (50161)
2.894
0.289
0.046
0.045
0.081
Breast (45827)
2.822
0.423
0.029
0.029
0.078
Colorectal (44076)
1.464
0,221
0.017
0,026
0.036
Leukemia (28497)
2.958
0.624
0.078
0.096
0.005
Renal (53757)
0.490
0,090
0.026
0,036
0.017
MNIST
65.107
37.896
9.935
9.885
2.35e5
Mishion-MNIST
35.235
1.955
0,613
0,612
2,80e5
CIFAR10
26.598
1,276
0.858
0.850
1.63e5
Table 3: Evaluation Results Average Geometric Distortion.
Dataset
cMDS
Lower-MDS
Neuc-MDS
Neuc-MDS
-imple-
1.049
1.049
1.010
1.004
Euclidean Ball
1.046
1.041
1.013
1.017
Brain (50161)
8.160
42.705
5.809
6.941
Breast (45827)
6.988
31.081
6.205
6.295
Colorectal (41076)
23.938
34.587
20.234
22.475
Leukemia (28497)
6.551
32.214
7.032
6.749
Renal (58707)
21.709
38.282
19.680
21.223
MNIST
1.119
1.104
1.064
1.063
Fashion-MNIST MINITT
1.135
1.096
1.068
1.068
CIFAR10
1.129
1.109
1.121
1.118
Performance on Dissimilarity Error. In addition to STRESS as the primary metric, we also test the average distortion (i.e. multiplicative error) and scaled additive error on all datasets. For all metrics, a smaller value indicates a more favorable performance. Limited by space, we leave scaled additive error together with other observations in Appendix E With & as the target dimension, for synthetic datasets and images, we set & 100, genomics data, A 20. The details are presented in Table 2

---

The results show that in terms of STRESS, Neuc-MDD and Neuc-MDS* outperform cMDS and Lower-MDS consistently by a large margin. SMACOF has comparable performance with Neuc-MDS in couple data sets but can go out of bound in others. For average distortion, the genomics datasets differentiate different methods drastically while the rest datasets produce comparable results. Neuc-MDS+ occasionally gives slightly higher STRESS than Neuc-MDS. Recall that both methods focus on optimizing for a lower bound of STRESS (in Theorem 2 and Theorem G This shows that C3 may play a role in practice.
Neuc-MDS Addresses 'Dimensionality Paradox'. Dimensionality paradox of classical MDS refers to the observation that STRESS increases as the dimension goes up. When raising this concern, 38 proposes a Lower-MDS algorithm as mitigation. We show that Neuc-MDS and Neuc-MDS address this issue even better. For Lower-MDS the target dimension cannot be larger than the number of positive eigenvalues. Our methods do not have this limitation. Figure 2 simplex, cMDS has an increasing STRESS with STRESS keeps increasing. In contrast, DDwer-MDS converges promptly while Neuc-MDS and Heuc-MDS" achieve even lower STRESS. Results on other datasets are in Appendix E.4
shows STRESS on Random-simplex and Renal. In Random-
~ 100 then stops, and in Renal the
Comparing Stress on Rancom simplex Dataset
Comparing Strees Ronal Dataset
houc Stress
125
100
20
Lowven MDSG Streas
0.075
Lowse-MDS Strea
52
0.050
0.005
0.025
10
20
20
200
450
802
1000
100 120 140
Targtt
Figure 2: Neuc-MDS and Neue-MDS+ consistently produce lower STRESS on all dimensions. Lower-MDS has a shorter curve because the target dimension limited to be smaller than the number of positive eigenvalues.
Landmark MDS Landmark MDS 12 is a heuristic to speed up classical MDS. One chooses small number of landmarks and apply MDS on the landmarks first. The coordinates of the remaining points are obtained through a triangulation step with respect to the landmarks. We can use the same heuristic to speed up Neuc-MDS. On the randon-simplex dalaset, with only 25% points randomly chosen as landmarks the STRESS is only a factor of 1.0644 of the STRESS obtained by MDS. If use only 10% points landmarks, the final STRESS is only 1.0898 of the STRESS of Neuc-MDS. This shows that Neuc- MDS can also be significantly accelerated using the landmark idea, achieving nearly the same STRESS.
7 Discussion and Conclusion
This paper presents an extension of classical MDS to non-Euclidean non-metric settings. We would like to mention few future directions. Since step out of the domain of Euclidean embedding, both the input dissimilarity matrix and the one obtained after dimension reduc- tion can have negative values. Therefore if one would like to feed the output dissimilarity matrix to another data processing module that by default requires non-negative values, spe- cial care must be taken to address the negative values. In experiments, we discovered that Neuc-MDS* achioves similar stress as Neuc-MDS and produces much fewer negatives values in the putput dissimilarity matrix (Appendix E. How to effectively use such dissimilari- ties in downstream learning and inference tasks would be a major future work. Note that. the geometry of general bilinear forms is largely unexplored territory.
A Acknowledgments and Disclosure of Funding
The authors acknowledge funding support through NSF IIS-2229876, DMS 2220271, DMS- 2311064, CCF-2208663, CCF-2118953, and CRCNS-2207440.
'For the sake of clarity we scaled some results by a factor of 10 We did so on all methods to ensure did not engender bias on analysis. We provide the original results in Appendix E.3
10

---

References
[1] R. Beals, D. H. Krantz, and A. Tversky. Foundations of multidimensional scaling. Psychol. Rev., 75(2):127 142, Mar. 1968.
2 M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Newral Comput., 15(6):1373-1333 11376, June 2003.
[3 A. Bellet, A. Habrard, and M. Sebban. A survey on metric learning for feature vectors and structured data. arXiv 1306.6709, June 2013.
[4] I. Benjamini and Y. Makarychev. Dimension reduction for hyperbolic space. Proceedings
of the American Mathemalical Sociely, 137(2):695 698, 2009.
[5] M. Brand. Charting a manifold. In Proceedings of the 15th International Conference on Neural Information Processing Systems, volume 15, pages 985-992, 2002.
66] A. M. Bronstein, M. M. Bronstein, and R. Kimmel. Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching. Proc. Notl. Acad.
Sci. U. S. A., (03(5))1168-1111) Jan. 2006.
[7] S.-H. Cha. Comprehensive survey on distance /ittacc/similarity measures between probability density functions. Int. J. Math. Model. Meth. Appl. Sci., 144:3300-307 2007.
8 I. Chami, A. Gu, D. P. Nguyen, and C. Re. HoroPCA: Hyperbolic dimensionality reduc- tion via horospherical projections. In Proceedings of the 38th International Conference on Machine Learning, pages 1419-1429, 2021.
99] I. Chami, R. Ying, C. Ré, and J. Leskovec. Hyperbolic graph convolutional neural networks. Adv. Neural Inf. Process. Syst., 32:4869 4880, Dec. 2019.
[10] L. Chen and A. Buja. Local multidimensional scaling for nonlinear dimension reduction, graph drawing, and proximity analysis. J. Am. Stot. Assoc., 104(485):209-22 Mar. 2009.
[11] T. F. Cox and M. A. A. Cox. Multidimensional scaling on sphere. Communications in Statistics Theory and Methods, 20(9):2943-290) 2953, Jan. 1991.
[12] V. de Silva and J. B. Tenenbaum. Sparse multidimensional scaling using landmark points. Technical Report, Stanford University, 2004.
[13] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby. An image is worth 16x 16 words: Transformers for image recognition at scale. In Proceedings of the International Conference on Learning Representations, 2021.
[14] R. P. W. Duin and E. Pękalska, Non-Euclidean dissimilarities: Causes and informa- tiveness. In Structural, Syntactic, and Statistical Pottern Recognition, pages 324 333. Springer Berlin Heidelberg, 2010.
[15] A. Elad, Y. Keller, and R. Kimmel. Texture mapping via spherical aulti-dimensional scaling. In Scale Space and PDE Methods in Computer Vision, pages 443 455. Springer Berlin Heidelberg, 2005.
[66 X. Fan, C.-H. Yang, and B. C. Vemuri. Nested hyperbolic spaces for dimensionality reduction and hyperbolic NN design. In 2022 IEEE/CVE Conference on Computer Vision and Pattern Recognition (CVPR), pages 356 365, 2022.
[17] B. C. Feltes, F. B. Chandelier, B. T. Grisci, and M. Dorn. CuMiDa: an extensively curated microarray database for benchmarking and testing of machine learning ap- proaches in cancer research. Journal of Computational Biology, 26(4):37 386, 2019.
[18] G. H. Golub and C. F. Van Loan. Matrix Compulations. Johns Hopkins University Press, Feb. 2013.
11

---

[19] A. A. Goshtasby, Similarity and dissimilarity measures. In A. A. Goshtasby, editor, Im- age Registration: Principles, Tools and Methods, pages 7-66. Springer London, London, 2012.
[20] Y. Guo, H. Guo, and S. Yu. CO-SNE:
Dimensionality reduction and visualization for hyperbolic data. In 2022 IEEE/CVE Conference on Computer Vision and Pottern Recognition (CVPR), pages 11-20, 2022.
[21] T. Hayden and J. Wells. Approximation by matrices positive semidefinite on a subspace. Lincar Algebra and its Applications, 109:115-130, 1988.
[22] Y.-H. He and J. M. Pérez Ipiña. Machine-learning the classification of spacelimes. Phys. Lett. B, 832:137213, Sept. 2022.
[23] G. E. Hinton and S. Rowcis. Stochastic neighbor embodding. In Proceedings of the 15th International Conference on Neural Information Processing Systems, volume 15, page 857-864, 2002.
[24] R. A. Horn and C. R. Johnson. Topics in matriz analysis. Cambridge University Press, 1994.
[25] B. Kulis. Metric learning: A survey, Foundations and Trends()) in Machine Learning, 5(4):287-366 -642 2013.
[26] J. A. Lee and M. Verleysen. Nonlinear Dimensionality Reduction. Springer New York, 2007.
[27] M. W. Mahoney, Randomized Algorithms for Matrices and Data. Now Publishers, 2011.
[28] K. V. Mardia. Some properties of clasical multi-dimesional scaling, Commenications Statistics Theory and Methods, 7(13):1233 1241, Jan. 1978.
[29] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel,
P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2-2222--830, 2011.
[30] Pellizzoni, Moretti, and F. Silvestri. Dimensionality reduction on complex vector spaces for Euclidean distance with dynamic weights. arXiv 2212.06605, Dec. 2022.
[31] D. Pisinger. The quadratic knapsack problem-a survey. Discrete Appl. Math., 155(5):623366) 648, Mar. 2007.
[32] H.-D. Qi and X. Yuan. Computing the nearest Fuclidean distance matrix with low embedding dimensions. Math. Program., (5(1-2))33113 189,,,9 Oct 2014.
[33] J. G. Ratcliffe. Foundations of Hyperbolic Manifolds. Springer International Publishing, 2006.
[34] S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, (90(5500):2323 2326, 2000.
[35] J. W. Sammon. nonlinear mapping for data structure analysis. IEEE Trans. Comput., C-18(5):401-44 409, May 1969.
[36] R. N. Shepard. The analysis of proximities: Multidimensional scaling with an unknown distance function. I. Psychometrika, 27(2):125 140, June 1962.
[37] R. N. Shepard. The analysis of proximities: Multidimensional scaling with an unknown distance function. I1. Psychometrika, 27(3):219 246, Sept. 1962.
[38] R. Sonthalia, G. Van Buskirk, B. Raichel, and A. Gilbert. How can classical multidi- mensional scaling go wrong? In M. Ranzato, A. Beygekimer, Y. Dauphin, P. Liang, and W. Vaughan, editors, Advances in Neural Information Processing Systems, vol- ume 34, pages 12304-12315, 2021.
12

---

[39] J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319 2211992223,--2 2000.
[40] W. S. Torgerson. Multidimensional scaling: Theory and method. Psychometriku, 17(4):401 419, Dec. 1952.
[41] J. Tsang and R. Percira. Taking all positive cigenvoctors is suboptimal in classical multidimensional scaling. SIAM J. Optim., 26(44:2080-20) Jan. 2016.
[42] A. Tversky and I. Gati. Similarity, separability, and the triangle inequality. Psychol. Rev., 89(2):123 154, Mar. 1982.
[43] H. Van Assel, T. Vayer, R. Flamary, and N. Courty. SNEkhorn: Dimension reduction with symmetric entropic affinities. arXiv preprint arXiw:2305.1177 2023.
[44] L. der Maaten and G. Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9:2579 2605, 2008.
[45] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Systems, volume 30, page 6000-6010, 2017.
[46] E. P. Wigner. Characteristie vectors of bordered matrices with infinite dimensions. Annals of Mathematics, 62(3):548 564, 1955.
[47] E. P. Wigner. On the distribution of the roots of certain symmetric matrices. Annals of Mathematics, (7)23332 327, 1958.
[48] R. C. Wilson, E. R. Hancock, E. Pekalska, and R. P. W. Duin. Spherical and hyperbolic embeddings of data. IEEE Trans. Pattern Anal. Mach. Intell., 36(11):2255 226222255522222222222222 Nov. 2014.
[49] W. Xu, R. C. Wilson, and E. R. Hancock. Determining the cause of negative dissimilar- ity eigenvalues. In Compuler Analysis of Images and Pallerns, pages 589 597. Springer Berlin Heidelberg, 2011.
[50] Z. Zhang and H. Zha. Principal manifolds and nonlincar dimensionality reduction via tangent space alignment. SIAM Sci. Comput., 26(1):314 338, Jan. 2004.
13

---

A Hollow Matrices and Relationship Between Gram and Squared Distance Matrices
We will prove the following proposition relating hollow symmetric matrices and squared "distance" matrices.
Proposition 9. (1) Given any symmetric matric G == [ggglaxx, there enists a symmetric bilinear form (,) on R" and vectors U1, "i,--.9 Un such that Dij 0z).
[maglnns there exists a symmettrc bilinear form ()) on R" and vectors V1y... ... such that mij (vi - Uj - vz) for all i,j.
(2) Given any hollow symmetric matrix
Note that the hollow condition = 0 is necessary.
Proof. Part (1) is a well known fact from linear algebra. We take oi,..., to be the standard basis of R" From the symmetric matrix G, one defines the symmetric bilinear form by the formula (u, v) = u² Go and vice versa.
To see part (2), consider the centered symmetric matrix B = CMC where C = 1 is
n
the double centering matrix and J is the matrix whose entries 1. One can that its (i, (i,j)-th entry bi of matrix B is given by
1 Emma + mmy) +
1 n²
byj Myj
mgg
(9)
tm1
One can easily verify from the formula that the centering condition holds:
n
bas O. Σ
(10)
By part (1) of the proposition, one finds n vectors U) ... Un in IR" and a symmetric bilinear form () on R" such that -2by (V,, Uz). Now claim that myj (e, - Uyy Us Uz), i.e,
-2m.g = b + bوf 2b...
Indeed, by dropping the constant term + Eb Ei= mil in we have
bis + bjj 2bij
(11)
2
2
=M,;
mik
+ mnj
mkj
2m; +
(max + maj (12)
km
km
2mig.
(13)
The last step uses the fact that M is hollow matrix, i.e., mi =maa O.
In summary, call G = [(vi, vyyl the Gram matrir and M [(ve - Uj Us vy)i and the squared distance matrix of symmetric bilinear form (,)- Obviously, we can determine M from G by the formula, (w, Uy 14 uy) (0,, uz) + (U,, vz) 2((,, vz), i.e., my Nu+t955 2gi-- We can also recover the Gram matrix G from M from the double centering construction CMC if the center of the vectors U1 ... En is O, i.e., E is O. To see this, given squared distance matrix M associated to vectors Ul..., Una we can replace vs's by w for a fixed vector w without changing M. Now by taking w Em U; to be the center of
..... Un, we can normalize Σn U; 0. In this case, formula states that
(Us, vz))
Mij
1
Σ
(ma + mkj)
mkl-
(14)
2
2n km1
2n²
Rmm Iml
where mij (v: Uz vz))
14

---

B Proofs of Error Analysis of Non-Euclidean MDS
In this section, we want to prove our main Theorem G for the error analysis of STRESS error. Note that Theorem 2 is a special case of Theorem the case in MDS and Neuc-MDS with À given by X C w.
6 for A = O, which is exactly
Theorem 6. Given a dissimilarity matris D E R=x= with eigenvalues X E I of its Gram malrix -CDC/2 = UAU*, for any rank-k (k: S n) diagonal malria A (ia with À E R" with & nonzero entries only on coordinates given by some index k-sst W S [n], lel w == lw E {0, [0,1]" be the indicalor vector of W, and let D be the dissimilarity matrix reconstructed from X A1/2UT. Then the STRESS error of can be expressed as:
|| - D12: C₁ + C2 + C3 with
O2
c=:=4 4 w T X (2) w A (2)
C2 = 4 ww X w AA)2 - 2n|[UU (U)
==
2
where AA = x x. minimized
The first two terms, C1 + C2, as lower bound of the STRESS, is
4( A)2 K
- X with Ā to be X = n 1 k w
4 (2)
(7)
The proof will essentially follow the pipeline in 38 Our results and proofs can be viewed as an extension to more general family of problems. We first show that the STRESS error can be decomposed into three terms G + C2 + Cz. Then we analyze the approximate lower bound C1 + C2 and figure out the minimum.
We first introduce some notations and lemmas we need to use later. Recall that C = I - 1, is the centering matrix. First note the following fact: Lemma 10. The didimensoonal vector 1a is an eigenvector with eigenvalue 0 of the matrices CUU and 8
Proof. By definition of C -- 1, it is easy to check C1,,- O. Also by definitions of U and X we can get similar results.
As a corollary, we have the following lemma: Lemma 11. CC
Proof.
δ =
+ 1 Diag(G)
(15)
By Lemma 10 we have
(16)
By Lemma 10 again, we have
(17)
Let Q be a Householder reflector matrix defined as follows:
Q Q I T vo" with == [1. 1,1 vnj"
(18)
For any symmetric matrix A E Raxx, lei (AA) E ((( ((A) E 1-- (I-11E((A) given by QAQ through the following equation:
R be
((A) f(A)
QAQ =: [(A)) {(A)
(19)
We need the following properties of Q:
15

---

Lemma 12
32
For symmetrie matrix A, we have
CAC = Q (A)
(20)
Lemma 13
For any matrix M, we use diag(M) (M,,)) to denote the column vector of M 's diagonal entries. For symmetric hollow matrix A
21
38
[ 2S(A) E(A)
= vnQ diag (Q
((A)
Now we are ready to prove our main theorem.
Proof of Theorem
D = =1Q0- D)Q1
(21)
=1]((D) +(D) IE{(D) - 1 +2|1((D) (22)
For the first term:
[ - +D) 10
[1 (D)
01 @
0
0
by Lemma 12
-|CDC- - CDCI2
CDC -CCC
2
2
-CDC
by Lemma 11
=41
||3
(23)
2
=4|IU(A - KYUTP?
- x T (2
For the second term:
From = Tr(D - D) (r( -(D)) + (E(D) {(D)), we can get
- -(()) AA,)² 4 + w0 T
DAJ² (24)
For the third term:
By Lemma 13
2f(D)
((D)
0
VnQ diag Q
E(D)
0
0
2f(D)
VnQ diag Q
((D)
0
④
{(D)
0
Taking the difference and then using a theorem on diagonalization and the Hadamard prod- have:
uct from 24
2f
VnQ diag (o ((D) -
((D)-
(D)
0
C(D)-(())
0
0
by Lemma
12
= VnQ dCa (NC))
-2/nQ diag(U Diag(AA)UU)
-2V/QQUU & (A)A))
16

---

Therefore,
[[
2f(D) 2f(D) E(D) E(D) | 4n|1(U 4nl((( (A))
(25)
Finally, we have that
- f(D)) = 2n][(U BAIIUGUUE UU(A)) - -0a0li--a22-0 C
(26)
The above arguments prove the first part of the Theorem.
Now we want to analyze the lower bound of
C1 + C2 A|0"" + w (A)) + 4/00 A AA]2
(27)
Denote C= t X, Z w² AA. By the Cauchy Schwartz inequality, we know that
w² ( 2
DA)A. AA)
The equality obtained when AA has the same value on all coordinates of W. Now check that
w² (AA)(2) + 100 T A w"
AAj²
K. ( AA)² + +CC + Z)
1
7. (C + 7
(29)
k
1+ z² 2CZ C
(30)
k
C
(31)
1 I+ k 1+ C through the standard analysis
The last incquality achieves the lower bound with Z of univariate quadratic equations. Based the above arguments, have that
A
C 4w 4w (2)
(32)
1+
Since the lower bounds from the Cauchy Schwartz inequality and the univariate quadratic equation are all light, we can conclude that the final lower bound is tight and can be achieved with
w X
AA
x=
w
(33)
1 k
1 1+
This finishes the proof.
C Proofs of Eigenvalue Selection Algorithm
(Exeersss A) Note that this is the value we want to minimize (i.e., C1 + C2). Without loss of generality, we may assume that none of the chosen eigenvalues in S is 0, since it does nothing to change F(S).
Proof of Theorem 3 For any subset $ C C, define F(S)
We first prove the first claim of Theorem 3
Proof. First, show that optimal solution S of size k exists. Assume have some optimal solution of size less than k. Let E L \ S. Then we have:
F(SU (b}) - F(S) = (-6) + (I) - 6) - HSS) = (bH
(34)
Now is clear that if H(S) is 0, we can add any eigenvalue to and F(S) would not change. If H(S) is not 0, then adding an eigenvalue to S that matches the sign of HS)), would reduce F(S) and the opposite would increase F(S). We will continue make use of this fact. Adding eigenvalue that matches the sign of (S) is also always possible since
17

---

(S)) is the sum of the eigenvalues we are choosing from. Thus, we can just contimue to add eigenvalues S until it is of size k.
Next, assuming S is of size k, we show that it must be the one as described in Theorem We can prove this by contradiction. Without loss of generality, we may assume that S contains a positive eigenvalue b such that there exists some E C satisfying a > b. First, we observe that since S is optimal:
0 S F(S) \ {b]) - F(S) = 62 + (H(S) - H(S)² 2bH(S) - 262
(35)
which reduces to H()) 2 -b. Then, have:
(a) (b)) F(S) = (b² (bb
+
-)- (2b (36)
We know that b- a < 0 and b > 0, (()) 2 bb, so we get that the expression negative. Thus, S U {a} {b} has a lower value under F and contradicts our assumption that S is optimal.
Let S be the optimal solution from Theorem Let T be the solution obtained by EV- Selection. We will show that F(S) = FT)). We use contradiction again. Without loss of generality, assume that S has more positive eigenvalues than T. Now consider H(ST)). From a similar argument used in the proof of Theorem 3 (1), due to S S containing only positive cigenvalues, H(S n T) O. Now if HSS TT) 0, know that S \ T contains one eigenvalue,
otherwise, removing positive eigenvalue from S would decrease F(S). Then, we know that F(S) F(T) and that is contradiction. If HSS TT) > O, then have reached a contradiction in the definition of T because EV-Selection will only choose eigenvalues in T \ when all negative eigenvalues in T T S, Q, has been chosen. However, for all subsets of positive eigenvalues of T, H(P Q) > O, so no eigenvalue in T {\S S will ever be chosen by EV-Sclection.
Algorithm 3: Eigenvalue Selection for Generalized Neuc-MDS
Input: Sorted eigenvalues X, integer k. Output: Set S of selected eigenvalues
Let L be the
of all eigenvalues X, S=0
while |S| < Is do
T+ S arg MaX
T_ 5 arg max SEC
A ExECAT_ X2 [T-FF (EXECiT, 2)² poita (ExECiT_ 2)²
A2 EXECAT_ X2
if A < A2 then
5 5= T+
else
S T_
end
end
Proof of Proposition 8 For any subset S C, define F(S) Execrs X2 +
IsTI (Execys X) 2)² Note that this is the value want to minimize (i.e., C1+ 1 C2). Without loss of generality, we may assume that none of the chosen eigenvalues S 0, since it does nothing to change F(S).
We first prove the first claim in Proposition
Proof. First, we show that an optimal solution S of size k exists. Assume we have some
optimal solution of size less than k. Let L) S. Then we have:
2
F(S U (6)) F(S) (-b2)= +2 (H(S) 6)
SS| +1 H(S)
<
bH (37)
| +
18

---

Now it is clear that if (S) is O, adding any eigenvalue to S would not increase F(S). If (S)) is not 0, then adding an eigenvalue to S that matches the sign of (S)), would reduce F(S). We will continue to make use of this fact. Adding
eigenvalue that matches the sign of (S) is also always possible since (S) the sum of the eigenvalues we are choosing from. Thus, we can just continue to add eigenvalues to S until it is of size k.
Next, we will show there must be an S as described in Proposition S We can prove this by contradiction. Without loss of generality, we may assume some optimal S contains a positive cigenvalue such that there exists some a E L satisfying a b. We can directly observe since S is optimal
0 $ F(su \ (6)) - F(() -66 - dd)+ + ||| + ((H(S) + + - a)² H())
1
|S] + (b ((S( + 2)b + + (la+2H((S))
Since we know b-o a < O, we get that ([S)+2)) 2)b++ + SS|a + (S) S. First, for the case where it is equal to O, can just take out b and put in S still does not have the greatest positive eigenvalues, we can repeat our analysis and examine another candidate positive eigenvalue to be replaced. In the case that it is strictly negative, then we have H(S) < 0 since [S], b, a > 0. Then there must exist some negative eigenvalue e that has not been chosen and if we replace with in our analysis, we get that b - c > 0 and (|S) + 2)b + |S|c + (S) < 0 which gives F(SU(c) (b)) < F(S) which contradicts the optimality of S.
Let S be the optimal solution from Proposition g Let T be the solution obtained by ?? 3. We will show that F(S) F(T). Note that now that we know |S| = k, we now define
F F= FxExer x²+ k+1 (Execis 2) We use contradiction again. Without loss of generality, we assume that S has more positive eigenvalues than T. Let a be the largest eigenvalue in magnitude from T\S S. Let 7" be the set chosen by ?? right before choosing a. Then let b be the largest eigenvalue in S S". By definition of T, we know that:
0 2 F(T'U(a)) - F(T' U (b) = =0b - a²)+ + ++1
(H((T) - a)² - (H((T) - b)3)
=0b² - a²) +
(a (a b-
k + 1
Now let's compare that with:
1
F(SU {a} \ (b)) - F(S) =(b² a²) + k+1
(H(() + - a)² - (H(S) + 6 -)))
1
=(b² a²) + k (a (a-b)a + b b))
Now clearly H(S) SU {a) \ {b} = T, so we get F(S) F(T). In the case that H(S) b (T"). we also know that - b < 0, so we get F(SU(a) (b)) F(S) < U (a)) - F(T' (b)) < O.
H(T). In the case that H(S) + = HT),, we clearly have
That violates the fact. that S an optimal set, so we have a contradiction.
D Computations on Random Matrices
We compare the classical multidimensional scaling and our non-Euclidean multidimensional scaling under the random matrix context, and give the proof of Theorem 5
We start with a symmetric random matrix B E Raxn as Proposition 4 and want to select l eigenvalues by using the classical and non- non-Edcli multidimensional scaling.
We start with classical multidimensional scaling. To select the largest eigenvalues, we need to select all eigenvalues greater than (2 - r) / such that
k
20
VA02 - dd 2
1 aresin (1 - [t) π
_(1
-1- - r 1)
22 r.
r )388)
7
2
(2-r)0
π
19

---

There is not an explicit way to write r as function of k. For a fixed r, since we want to drop all eigenvalues smaller than (2 r) /no, we have 60
ExEcys (ExEcAs))² n² (ExEcis
A )2 n
-) + -IxE'xE A 1
=
Vn ni
(39)
(2-1)a
(2-r/a
n².
x² V402 dx + +n²
xV 40 x² xz2x²2
2Ta²
-2a
2To²
-2a
n²o
arcsin (1 )) + (1- 11- 2r - 2 r(1
2
-- -
16n 9T
1 }
2
For non-Fuclidean multidimensional scaling, to select the l eigenvalues with largest mag- nitude, we need to select all eigenvalues with magnitude greater than (2 - r) Vna such that
k:
20
(2-r)o
V -2ddx +
V x2dx)
2TO²
(2-1)0
-20
(40)
aresin - r
-1-
-1
π
For a fixed r, since we want drop all eigenvalues with magnitude smaller than (2 - r) /na, we have
eN ExEcAsd2= (ExEcisA)2
1
= = (ExECiS)
vn
n² 1
(2 (2-r)a
(41)
x² 2224022 402 -d
2T
-22-r)o
n² 02 aresin (1
2
/) + 2 (1
2
22 2r + - (1
2 r(1 7}
We first consider the case that == o(n), i.c. we want to reduce the dimension from n to a much smaller k. Under this assumption, is very small positive number. In the classical
case, by applying the Taylor series to equation (38 we get 2n ( Then we plug it
into equation (39 to get.
4k2
eg = n2on
n
Similarly, in the non non-Euclidean case, apply the Taylor series to equation
40
we get
r (3rk) 3. Then we plug into equation 41 get
4k
ex R3 n
m
This finishes the proof of Theorem 5 (1).
Now we turn to the case that k = en for a constant E [0. We first solve k in equations (38 and (40) get the corresponding r, then plug the r-values in equations 39 and 41 to get the corresponding eo and ex, respectively. Since equations (38) and 40 can not be solved explicitly, we can only get numerical values of eg and ex- For shown in Table For c [0.5, 1]. the classical
E (0. 0.5), numerical values of eg and multidimensional scaling stabilizes, with éc ze (0.5 + 0.1801 nnnno?? Meanwhile, the error eN for non-Eut -on-Euclidean multidimensional scaling decreases to zero increases to 1. More precisely, c = with very small > O, equations (40 and give
E RJ -
12
Some numerical values of ex with e E [0.5, are shown Table
This finishes the proof
of Theorem (2).
20

---

0.05
0.1
0.15
e
0.8432 + 0.0078
0.7322 + 0.0265
0.6513 + 0.0512
(N/(n'''")
0.8278
0.6864
0.5666
0.2
0.25
0.3
ec/(n'a")
0.5933 + 0.0785 m
0.5531 + 0.1055 n
0.5269 + 0. 1304 n
eN ex/(n'o") 0.4644
0.3771
0.3027
0.35
0.45
ca/(n'o²) ex/(n"o")
0.5112
0.1512
0.5033 + 0.1670 n
0.5004 + 0.1768
0.2397
0.1866
0.1425
Table 4: This table shows the error terms and of different choices of c 0.5) with k/n, normalized by dividing n²a²
0.5
0.55
0.6
0.65
0.7
eN (enn/nnn
0.1063
0.0770
0.0537
0.0358
0.0225
0.75
0.8
0.85
0.9
0.95
eN (n' (nnannna))
0.0130
0.0066
0.0028
0.0008
0.0001
Table 5: This table shows the error term eN of different choices of E [0.5, 1) with c = k/n, normalized by dividing n²'o2.
E More Details and Results on Experiments
In this appendix we fill the missing details in the experiment section. Our experiments are implemented with Intel Core 19 CPU of 32GB memory, GPU is required and the execution time is no longer than 30 seconds, In the rest of this section, we first introduce the generation process of synthetic datasets in Appendix E.T Next we define the evaluation metrics and perturbation approaches in Appendix E.2 More results on dissimilarities regarding the scaled additive error, negative distances and negative eigenvalues selected, are demonstrated in Appendix E.3 With respect to the dimensionality parador, we provide illustrations similar Figure on other datasets Appendix E.4
E.1 Synthetic Datasets Generation
The random-simpler dataset generated with the idea of creating a simplex with one added dimension that generates all of the variance in the the distances such that the added dimension corresponds with a negative eigenvalue. This way, we should have a dimension with large negative eigenvalue that impactful on the stress of the embedding.
Specifically, this dataset was generated with points x1,...Z1000: each point having 1000 dimensions. For each point T4, the first 100 coordinates were chosen uniformly randomly between 0 and .01. The next 899 coordinates were chosen uniformly randomly between and / 0.5 899. The last coordinate is x 0.3/1000. Then, the distance between æ; and xz was found in the following way:
100
1000 Σ
d(z,,
Σ (k)
(z,(k) - (b)))
where (k) is the kth coordinate of z;. The first 999 coordinates essentially form simplex, because selecting a large number of coordinates randomly from the same distribution causes all of the distances to converge to normal distribution with low variance. Thus, all of the distances between points using just the first 999 coordinates are very similar. Then, the last coordinate has "large" discrepancies between all of the points, causing most of the differences in the distances.
The Euclidean-ball metric was inspired by 40 The set of distances between objects in space does not. follow triangle inequality, so it becomes a non-euclidean dissimilarity measure. The particular dataset we generates the distances by first randomly selecting 1000 points
21

---

uniformly in a 10 dimensional hypercube of length 100. Each of these points is now the center of a ball. Then, for each ball, with probability 0.9, we select radius uniformly randomly bet ween 0 and 5. With probability 0.1, we let the radius be 0.8 times the distance between the center of this ball to the closest other ball. This closest other ball is based on the radius of the other ball if it has already been decided. The final distance matrix is just filled by the distances between the 1000 balls. In this way, we attempt to create some balls with large radius, so that the triangle inequality is heavily violated, therefore causing the dataset to deviate more from the Euclidean setting.
E.2 Evaluation and Perturbation Metrics
In addition to STRESS, our evaluation metric include scaled additive error and average geometric distortion. Scaled additive error by definition is allowing scaling of the distance matrix of our embedding before calculating stress. To do this, we first ran the embedding method (e.g., cMDS, Neuc-MDS, other methods) on the given dissimilarity squared ma- trix D to get the output dissimilarity squared matrix D. Then, we would flatten both D and D to vectors, and project D onto the line through D to get E. Then we calculate ||D - Ell to get scaled additive error. Clearly, this is equivalent to allowing scaling of D to find the minimum stress. For average geometric distortion, we again input D to get D, but this time, we evaluate the distortion of each dissimilarity by dividing entries of vD by entrics of VD. Since distortion is not well defined when dissimilarities become complex, we skip those. Then, with the remaining valid distortions, we scale the distortions so that there's an equal number of them greater than 1 and less than 1, then for those that remain less than 1, we take their reciprocal. Then, we finally take the geometric average of all of these distortions. In this way, we basically again allowed scaling of the dissimilarities to find the minimum possible average distortion.
Next, we had to decide on metrics to use for the image datasets. We took the following 3 metries from Rg For the first metric, the distance between two images is first finding the Euclidean distance between their coordinate reprosentations, and then adding Gaussian noise to the distances. Because the noise is added directly onto the distances, the end result is highly likely to be non-Euclidean. For the second metrie, we build a k nearest neighbor graph of the images based on their Euclidean distances. Since the end result is graph structure, the shorlest path distances are also highly likely to be non-Euclidean. For the third metric, we randomly removed entries from the coordinate representation of the images. Then, the distance between two images is decided by taking the Euclidean distance between coordinates that both images still included. Here, the Euclidean property breaks down again because triangle inequality would no longer have to hold. In Table 2 we choose the N--N metric with k 2. In the next Appendix section, we show results for higher and other metrics applicd to the image datascts. As for genomics datasets, we use the entropic affinities commonly used in t-SNE methods. The main idca to apply an adaptive kernel, whose bandwidth depends on parameter termed as perplexily, to pairwise data entries.
E.3 More Results on Dissimilarity Error
In addition to STRESS and average distortion already reported in Table 2 we further show the third metric: scaled additive error as defined in Appendix E.2 Note that our algorithms may produce negative distances, we also report number of negative distances and number of negative eigenvalues selected. All original results (without scaling) on 10 datasets are demonstrated in Table [ Recall we mentioned the results in Table 2 contains some scaling on the synthetic data and images, we also provide the original values in Table 7
On scaled additive error, our proposed methods still consistently outperform cMDS and Lower-MDS considcrably. Thus, we have shown that on all motrics our methods yicld more favorable results. It is interesting to observe that Neuc-MDS* produces much fewer negative distances than Neuc-MDS, though the number of negalive eigenvalues selected are quite close. Further, two methods have similar performance on STRESS and other metries. Therefore in practice, if there is a considerable concern on negative distances, Neu should become a better choice.
22

---

Table 6: Original Evaluation Rosults All Datasets for Lower-MDS (L-MDS), Neuc-MDS (N-MDS) and Neuc-MDS* (N-MDS+). Metrics include scaled additive crror, number of negative distances and number of negative cigenvalues selected.
Dataset
Sealed Additive Error
# Nog Distances
# Nog À Selected
cMDS
L-MDS
N-MDS
N-MDS*
N-MDS
N-MDS*
N-MDS
N-MDS+
Randon-slmplex
17758
17760
3415
1392
8
Euclidean-ban ball
14909
13093
3132
3631
798
523
90
87
Brain (60161)
0.131
0.132
0.063
0.062
5539
1081
8
Breast (45827)
0.039
0.039
0.016
0.015
9024
136
8
Colorectal (44076)
0.027
0.027
0.012
0.011
12011
1910
6
8
Lenkemia (28497)
0.031
0.031
Renal (53757)
0.018
0.018
0.013
0.014
6650
713
7
9
MNIST
7592
6126
3148
3.135
1006
08
42
43
Fashion- MNIST
2.472
41
CIFARIO
3880
3564
2870
2.842
2968
201
43
44
Table Original Evaluation Results on All Datasets. Metries include STRESS and average geometric distortion
Dataset
STRESS
Average Geometric Distortion
cMDS
L-MDS
N-MDS
N-MDS*
L.MDS
N-MDS
N-MDS+
Random-simplex
28.376
17.760
3.433
1.392
1.049
1.041
1.010
1.004
Euclidean-ball
19.229
13.154
3.346
3.676
1.046
1.041
1.013
1.017
Bruin (50161)
0.170
0.068
8.160
Breast (45827)
0.168
0.065
0.017
0.017
6,988
31.081
6.205
6.295
Colorectal (44076)
0.121
0.047
0.013
0.016
23.938
34.587
20.234
22,475
Lenkemia (28497)
0.172
0.079
0.028
0.031
6.551
32.214
7.032
6.749
Renal (53757)
0.070
0,030
0.016
0.019
21.709
38 282
19.680
21.223
MNIST
25.516
6.156
3.152
3.144
1.119
1.104
1.064
1.063
Fashion- MNIST
18.771
4.422
2.475
2.473
1.135
1.096
1.068
1.068
CIFARIO 16.309
3.572
2.930
2.916
1.129
1.109
1.121
1.118
Qungaring Terze:
Camparie Stren Seast Detare
Compor Scen on Octeedia beteet
Our purtoy Stree Leite Delree
5.30
Comparing Stats Bill Detser
Contal T0 SUNEE MUST Detasit
Canos State Faction Ms Oatast
CC CCtaar Sheas CBAR3 Detuer
1991
4108
lear ICC0
Figure 3: Dimensionality Paradox on Eight Datasets.
Until now all results reported on images are using kNN metric with k to produce non-Euclidcan dissimilaritics. There could be other perturbation for the same purpose, as mentioned in Appendix E.2, We further lest with 10 and the other two metrics: adding noise and random removal on the STRESS. We add noise sampled from Gaussian distri- bution with variance as the maximum instance-wise difference scaled by 500; For random removal, we skip 50 images for each. The results are shown in Table
23

---

Table 8: Evaluation Results Image Datasets with other perturbation metrics.
Dataset
STRESS
# Neg diesances
# Neg
Selected
cMDS
L-MDS
N-MDS
N-MD8
N-MDS
N-MDS
N-MDS
N-MDS
MNIST (A 10)
10080
1979
1827
1830
554
63
42
41
Fashion (R 10)
10249
2112
1936
1915
403
84
CIPARIO
1881
MNIST (noise)
1.497e9
1.499e9
1.497e9
1.140e9
Fushion (moise)
4.81
4. 130+9
3.382-9
3.327v0
14
CIFAR1O (noise)
2.303e10
2.116e9
2.303c9
1.848e9
MNIST (milssing)
3.281c8
1.010e8
3.281c8
1.010e8
Faehion (misiing)
5.165e8
1.726e8
5.165e8
1.726e8
(missing)
2.132e9
6.736e8
2.13229
0.766e8
E.4 More Results Dimensionality Paradox
The purpose this section is to show the consistent performance Neuc-MDS and Neuc- MDS+ all datasets, with respect to mitigating the dimensionality paradox issue. There- fore, in addition to Figure 2 we provide the same plots for other datascts, and the pa- rameters all follow the main setup. Figure gives clear illustration that Neuc-MDS and Nouc-MDS* always have lower STRESS than cMDS and Lower-MDS as dimension grows.
24

---

F
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We propose generalization of classical multidimensionall scaling to handle -u--uucideann non-metric data. We presented both a new algorithm, theo- retical proofs on its performance, and experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, in- cluding the contributions made in the paper and important assumptions and limitations. A No or NA answer this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discussed the limitation (and future work) of the proposed ap- proach. These include: 1) developing downstream data analysis for using non- Euclidean non-metrics data. 2) speeding up the algorithm for extremely large data (e.g., by developing landmark based non-Fuclidean MDS algorithms). Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noise- less settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be vio- lated in practice and what the implications would be.
The huts should reflect on the scope of the claims made, e.g., if the approach was only tested results often depend on implicit assumptions, which should be articulated.
few datasets with few runs. In general, empirical
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech- to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algo- rithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't. acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in
25

---

favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assump- tions and a complete (and correct) proof?
Answer:
[Yes]
Justification: Please refer to the theorem statements. We included all proofs in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the thcorems, formulas, and proofs in the paper should be numbered and cross-reforenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be com- plemented by formal proofs provided in appendix supplemental material. Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provided all details of our experiments in the Appendix. We also shared our code using an anonymous Github repository. See the footnote on Page 2.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible
verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution primarily a new model architecture, the paper should describe the architecture clearly and fully.
26

---

(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path reproducing or verilying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provided all details of our experiments the Appendix. We also shared our code using anonymous Github repository. See the footnote Page 2.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.
for more details.
While we encourage the release code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including codc, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submis- sion guidelines htttps///hssss.cccuubb////////// for more details.
The authors should provide instructions on data access and preparation, in- cluding how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code per- mitted.
6. Experimental Setting/Details
Docs the paper specify all the training and test details (c.g., data splits, hyperparameters, how they were chosen, type optimizer, etc.) necessary to un- derstand the results?
Question:
Answer: [Yes]
Justification: We provided all details and paramcters used in our experiments in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
27

---

The full details can be provided either with the code, in appendix, or as sup- plemental material.
7. Experiment Statistical Significance
Question: Does the paper report bars suitably and correctly defined other appropriale information about the statistical siguificance of the experiments?
Answer: [Yes]
Justification: Since our algorithm and benchmark algorithms are deterministic, all experimental results are deterministic once the imput data is fixed. We mentioned this in Table 2
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" the results are accompanicd by error bars, confidence intervals, or statistical signifieance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/tess split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g,, Normally distributed errors).
Tt should be clear whether the error bar is the standard deviation the stan- dard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96%
CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of exccution) needed reproduce the experiments?
Answer: [Yes]
Justification:
We included in the appendix computer resources
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the lype of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more com- pute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:://harrrppccc/ooooo/hhheeha
Answer:
[Yes]
Justification: N/A
28

---

Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethies.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and neg- ative societal impacts of the work performed?
Answer: [Yes]
Justification: We included a short paragraph of broader societal impacts of the work at the end of the appendix.
Guidelines:
The answer NA means that there no socictal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness con- siderations (e.g., deployment technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security consider- ations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, optimizing neural networks could enable people to train models that generate Deepfakes faster.
not needed to point out that generic algorithm for
The authors should consider possible harms that could arise when the technol- ogy is being used intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative socictal impacts, the authors could also discuss possible mitigation stralegies (e.g,, gated release of models, providing defenses in ad- dition attacks, mechanisms for moniloring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for sponsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled by requiring that users adhere to usage guidelines or restrictions to access the model implementing safety filters.
of the model, for example
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
29

---

We recognize that providing effective safeguards is challenging, and many pa- pers do require this, but we encourage authors take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Ye]]
Justification: We cited software packages used in the paper. No licensed data was used in the experiments.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e-g., CC-BY 4.0) should be included for each asset. For scraped data from a particular souree (c.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcodee thwode.ccoo.ooooooooooooooee datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out the asset's creators.
13. New Assets
Question: Are new assets introdueed in the paper well documented and is the documentation provided alongside the assets?
Answer:
[Yes]
Justification:
Documentation is supplied logether with the code.
Guidelines:
The answer NA means that the paper does not release new assels. Rescarchers should communicate the details of the datasct caaase//cooi code /ooeeel as part of their submissions via structured templates. This includes details about train- ing, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
30

---

Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor rescarch with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between insti- tutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "qldLAJRRMe", "reviewer": "Reviewer_wzYh", "summary": "This paper introduces Non-Euclidean Multidimensional Scaling (Neuc-MDS), an extension of classical Multidimensional Scaling (MDS) that can handle non-Euclidean and non-metric data. The key ideas and contributions are:\n\n1. It generalizes the inner product to more general symmetric bilinear forms, allowing the use of both positive and negative eigenvalues of dissimilarity matrices.\n\n2. Neuc-MDS efficiently optimizes the choice of eigenvalues to minimize STRESS (sum of squared pairwise errors). The authors set up the problem as a quadratic integer program but show that it has an optimal solution and that it can be found in a greedy fashion.\n\n3. The authors provide theoretical analysis of the error and prove optimality in minimizing lower bounds of STRESS.\n\n4. They introduce two algorithms: Neuc-MDS and an advanced version Neuc-MDS+.\n\n5. Theoretical analysis is provided for the asymptotic behavior of classical MDS and Neuc-MDS on random symmetric matrices.\n\n6. Experimental results on 10 diverse datasets show that Neuc-MDS and Neuc-MDS+ outperform previous methods on STRESS and average distortion metrics.\n\n7. The proposed methods resolve the \"dimensionality paradox\" issue of classical MDS, where increasing dimensions can lead to worse performance.\n\n8. The approach is applicable to both image and text data, and can handle various non-Euclidean dissimilarity measures.\n\n9. The paper provides detailed proofs, algorithm descriptions, and experimental results in the appendices.\n\nOverall, this work extends MDS to non-Euclidean spaces, providing both theoretical guarantees and practical improvements over existing methods for dimension reduction and data embedding tasks.", "questions": "See above.", "limitations": "not applicable.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper is well-written and it clearly outlines the problem and the solution. The analysis is non-trivial and the experiments are thorough.", "weaknesses": "While the paper presents a novel approach with several strengths, there are a few potential weaknesses or limitations that can be identified:\n\n1. Computational complexity: For large datasets, the method may still be computationally intensive, as it requires eigendecomposition of the full dissimilarity matrix. While the authors mention the possibility of using approximation algorithms for partial SVD, they don't provide detailed analysis or experiments on very large-scale datasets.\n\n2. Limited comparison with non-linear methods: The paper primarily compares Neuc-MDS with classical MDS and other linear dimension reduction techniques. A comparison with popular non-linear methods like t-SNE or UMAP could provide more context on its performance relative to the state-of-the-art in dimension reduction.\n\n3. Interpretability: The use of general bilinear forms, while mathematically elegant, may make the resulting embeddings less interpretable compared to Euclidean embeddings, especially for domain experts not familiar with non-Euclidean geometries.\n\n4. Downstream tasks: The paper focuses on the quality of the embedding itself (via STRESS and distortion metrics) but doesn't extensively explore how these embeddings perform in downstream machine learning tasks compared to other methods.\n\n5. Negative distances: The method can produce negative distances, which may be problematic for some applications or require special handling in downstream tasks. While this is mentioned, strategies for dealing with negative distances are not fully explored nor is the impact on \"real\" data sets discussed.\n\n6. A discussion of just how non-Euclidean \"standard\" data sets are would be useful. Is this problem of non-Euclidean distances a substantial one or not? \n\n7. This brings me to a more detailed discussion of the experiments: I'd be interested in seeing a quasi-synthetic example of a real data set with non-Euclidean distances used (say, graph distances from a nearest neighbor graph). What impact does that make on the results?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback, we respond to your comments as follows.\n\n- Computational Complexity\n\nThanks for raising the concern. One-line argument is both Neuc-MDS and classical MDS run in $O(n^3)$ time due to eigen decomposition, therefore, no extra cost asymptotically. We also have more ideas on reducing the runtime, please refer to general response 1.\n\n- Additional Experiments with t-SNE\n\nIn the submission we mainly focused on linear embeddings and compare with other MDS variants, to evaluate the impact of moving beyond Euclidean geometry. Some non-linear dimension reduction methods such as Isomap use MDS as intermediate steps. The submission already included another non-linear method: Smacof. We also run experiments with t-SNE on all datasets, and find that Neuc-MDS outperform others in terms of STRESS. Please refer the results in general response 3.\n\n- Interpretability\n\nBeyond the routine use of classical MDS for embedding and visual inspection of the input dataset, these dimension reduction methods also have many applications, simply to reduce the size of the representation needed. For such types of applications, Neuc-MDS can be a good alternative when the input dissimilarity is non-Euclidean. \n\n- Negative Distances\n\nWe have discussions and provide two examples with references in the general response 2.\n\n- Downstream Tasks\n\nExploring how non-Euclidean dimension reduction can benefit downstream applications is an important next step. We are very keen in exploring along this direction further, which is one of the important future directions.\n\n- Non-Euclidean Datasets\n\nIn our simulation section, we tested on two generated datasets that carry non-Euclidean distances. The first one is a random distance matrix (called Random-Simplex), and the second one takes minimum distance between Euclidean balls (called Euclidean-ball). Details of the two datasets can be found in Appendix E.1. Xu, Wilson and Hancock [49] have suggested two sources of non-Euclidean non-metric distances, random noises and extended objects, which correspond precisely to these two datasets. The Euclidean ball dataset suggests a general source of non-Euclidean distances coming from distances of families of data points, where the distance of two sets $A$ and $B$ is defined as the Hausdorff distance $\\min_{a\\in A, b\\in B} d(a, b)$. Such distances are not Euclidean and are not always a metric. \n\nIn addition, the datasets we used from CuMiDa and image data set use dissimilarity values that are non-Euclidean, as can be seen from the negative eigenvalues in Figure 1 and Table 1. More discussion on this can be found in Appendix E.2.\n\nPlease let us know if there is anything further we could help clarify. Thanks again for your time and efforts!", "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": "", "extra_scores": {}}, {"review_id": "VtDyjc8lft", "reviewer": "Reviewer_3cJU", "summary": "The authors introduce Non-Euclidean-MDS (Neuc-MDS), an extension of Multidimensional Scaling (MDS) that accommodates non-Euclidean and non-metric outputs, efficiently optimizes the choice of (both positive and negative) eigenvalues of the dissimilarity Gram matrix to reduce STRESS. The results seem to be promising and the error analysis looks solid.", "questions": "What is the advantage of Neuc-MDS over Neuc-MDS+ or the opposite direction? From the experiments, I didn't find difference.", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. the error analysis seems solid.\n2. the topic is important which can extend to non-Euclidean MDS\n3. the experiments look promising", "weaknesses": "1. The overall writing is not easy to follow, for example from line 119-131, your statement is long, but I am still confused how to construct A. Apparently if A is Identity matrix, it degenerates into traditional one. Your contribution is to say A doesn't need to be Identity or even PSD, but how to construct A remains unknown to me.\n2. I don't agree that A can be non-PSD, in which case the inner product of v with itself can be negative, I feel wired.\n3. Line 137 you claim X can be recovered from B, however this is not precise. \n4. the formatting can be improved, for example the fontsize Table 3 can be reduced and figure 3 can be better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your careful reading and valuable feedback. In the following we address the concerns.\n\n- ### Regarding the problem definition (Definition 3.1) and description \nFor a generic bilinear form $f_A(u, v)=u^T A v$, consider the induced dissimilarity $D_A(p_i,p_j):=f_A(p_i-p_j, p_i-p_j)$ between two points $p_i,p_j$ in $\\mathbb{R}^n$\n(there was a typo in Definition 3.1 regarding the notation $\\hat{D}_{i,j}$. we'll correct it in the revision). \n\nWhen $A$ is the identity matrix, the bilinear form gives a classical inner product and the dissimilarity is the (squared) Euclidean distance. \nWhen $A$ is a PSD, the vector space with this bilinear form can be mapped isometrically to an Euclidean space through the eigen-decomposition of $A$. \nIn general, our paper focuses on looking for a bilinear form $f_{\\hat{A}}$ defined by a low-rank $\\hat{A}$ to approximate the bilinear form $f_{A}$ (or its induced dissimilarity $D_A$) of the underlying space of the given data. \n\nHow to construct the low-rank $\\hat{A}$ or dissimilarity matrix $\\hat{D}$ is the main task of this paper (Algorithm 1). We construct $\\hat{A}$ together with embeddings implicitly in our $\\hat{D}$. To see that, based on the relation between dissimilarities and bilinear forms (gram matrices), we have $\\hat{X}^T\\hat{A}\\hat{X}=-C\\hat{D}C/2=U{diag({\\lambda}\\odot {w})}U^T$. \nThe last equality is given by the eigen-decomposition with $U$ being the matrix of real eigenvectors, and ${w}$ indicating the selection of our algorithm on the eigenvalues ${\\lambda}$. Then for $\\hat{X}=\\sqrt{diag({|\\lambda|}\\odot {w})}U^T$, the bilinear form $\\hat{A}=diag(sign({\\lambda}))$. \n\n- ### Regarding non-PSD A\nOne of the main motivations of this work is based on some initial observations of importance of studying non-PSD bilinear forms which appeared in several research domains, and we believe it will benefit the machine learning community in general. We give more discussion in the general response (2).\n\n- ### Regarding Line 137\nThank you for pointing out and yes, in general, we would say one instance of X (under some isometric transformations) realizing the distance matrix can be recovered by the algorithm (or more precisely, under some generic assumption, X is unique up to UXP where U is an orthogonal matrix, P is the matrix corresponding to the orthogonal projection from $\\mathbb{R}^n$ to the subspace $\\{x=(a_1, ...., a_n)\\mid \\sum_i a_i =0\\}$). We would clarify it in the revision.\n\n- ### Regarding NeucMDS vs NeucMDS+\nTheoretically, both Neuc-MDS and Neuc-MDS+ look for a diagonal matrix of $\\lambda'$ with at most $k$ non-zero entries to reconstruct a low rank dissimilarity matrix $D'$. Neuc-MDS uses $\\lambda'$ by choosing at most $k$ non-zero eigenvalues from the input Gram matrix, while Neuc-MDS+ allows $\\lambda'$ with arbitrary $k$ non-zero values -- or a general rank-$k$ linear transformation of the eigenvalues of the input Gram matrix. Thus Neuc-MDS+ looks for the optimal value in a larger domain. \nEmpirically, we realize that both Neuc-MDS and Neuc-MDS+ give smaller STRESS values but the number of negative distances using Neuc-MDS+ is significantly fewer. Due to space limit the experiments are in Table 5 of Appendix E.3.\n\n- ### Regarding formatting\nWe appreciate your comments on formatting and will address these issues in the revised version.", "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": "", "extra_scores": {}}, {"review_id": "NOeriUKavJ", "reviewer": "Reviewer_RtpY", "summary": "The paper introduces Neuc-MDS, a novel extension of classical Multidimensional Scaling (MDS) designed to handle non-Euclidean and non-metric dissimilarities in datasets. The goal is to create accurate low-dimensional embeddings while minimizing the STRESS (sum of squared pairwise error)", "questions": "1.\tHow does Neuc-MDS perform on extremely large datasets compared to cMDS and other dimensionality reduction methods in terms of runtime and memory usage? Are there specific strategies or heuristics recommended for choosing the subset of eigenvalues in very large-scale applications to balance between computational efficiency and accuracy?\n2.\tHow do the negative eigenvalues impact the interpretability of the resulting low-dimensional embeddings in practical applications, such as in visualization or clustering? What are the recommended practices for handling and interpreting dissimilarity matrices with negative entries generated by Neuc-MDS in downstream tasks?\n3.\tTo what extent do the theoretical guarantees of Neuc-MDS hold for real-world datasets that do not conform to the random matrix assumptions used in the analysis?\n4.\tHow does Neuc-MDS compare with other non-linear dimensionality reduction methods (e.g., t-SNE, UMAP) in preserving the global and local structure of non-Euclidean datasets?", "limitations": "See weakness", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tNeuc-MDS extends the concept of the inner product to a broader class of symmetric bilinear forms, allowing the incorporation of both positive and negative eigenvalues from the dissimilarity Gram matrix. This generalization helps capture the underlying structure of non-Euclidean data more effectively than classical MDS, which typically discards negative eigenvalues.\n2.\tNeuc-MDS is specifically designed to handle non-Euclidean and non-metric dissimilarities, making it versatile for a wide range of applications where traditional MDS falls short. The method is backed by a thorough theoretical analysis, providing guarantees for minimizing STRESS. This includes a detailed decomposition of the STRESS error and the demonstration of optimality in eigenvalue selection.\n3.\tNeuc-MDS is capable of working with a variety of dissimilarity measures that are commonly used in practice but are not Euclidean, such as cosine similarity, Hamming distance, and Jaccard index. This broadens its applicability to different fields and types of data.", "weaknesses": "1.\tThe theoretical guarantees provided by Neuc-MDS are based on certain assumptions about the data and dissimilarity matrices. If these conditions are not met in practice, the performance and guarantees may not hold.\n2.\tSome theoretical results rely on properties of random matrices (e.g., Wigner's Semicircle Law). The applicability of these results to structured or real-world datasets, which may not exhibit such random properties, is unclear. The use of Lorenzian distance or other non-standard measures may not satisfy traditional distance properties (e.g., triangle inequality), potentially leading to confusion or misinterpretation in applications that rely on classical distance metrics.\n3.\tThe algorithm involves eigenvalue decomposition and optimization over eigenvalue selections, which can be computationally intensive for large datasets. The scalability of Neuc-MDS, especially for very large datasets, may pose a practical challenge.\n4.\tThe implementation of Neuc-MDS involves several complex steps, including eigenvalue selection and optimization. This complexity may hinder its adoption by practitioners who require straightforward and easily implementable solutions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your careful reading and valuable feedback. In the following we address the concerns.\n\n- ### Regarding Computation and Scalability\nWe discuss the computational complexity and provide more ideas (e.g. using ideas similar to landmark MDS) on reducing the runtime for very large datasets in the general response (1). Basically, these concerns have been addressed by previous work.\n\n- ### Regarding complexity of implementing Neuc-MDS\nOur algorithm, compared to MDS, differs only in the way that eigenvalues are chosen. This algorithm is a simple greedy algorithm (Algorithm 2), that is both easy to understand and to implement, with linear running time in the number of eigenvalues to choose. We respectfully disagree that this is complex and thus not practical for implementation. We have also shared our code through the link in the paper for anyone who'd like to try it out. \n\n- ### Regarding comparison with other methods\nWe compare with two non-linear methods: Smacof and t-SNE and provide the results in the general response (3). Neuc-MDS still outperforms those non-linear methods on non-Euclidean datasets, which implies that the issue raised from the non-Euclidean properties of the underlying spaces of datasets cannot be easily solved by non-linearity. \n\n- ### Regarding Interpretation of dissimilarities\nOne idea for the interpretation of the non-Euclidean distances is that the dissimilarities are metric distances between two sets of points. One way to view this is that each data element is actually a distribution with some uncertainty. The non-Euclidean distance actually penalizes such uncertainty. This is our ongoing work, which will likely to be a separate follow up paper.\n\n- ### Regarding assumptions on dissimilarity matrices \nWe remark that our assumptions on the input dissimilarity matrices are very general, especially compared to the Euclidean distance assumption in classical MDS and a lot of machine learning settings. That gives our methods potential to be applied to more general situations like non-Euclidean geometry or graphs. Also, our algorithm for choosing eigenvalues minimizes the error terms C1+C2, which is always a lower bound of STRESS=C1+C2+C3 (since C3 is non-negative). This does not depend on any assumption on the input data.\n\n- ### Regarding Lorenzian distances and non-metric dissimilarities \nIndeed many machine learning applications use metric distances or even only Euclidean distances, thus making it an (arguably) `comfort zone'. At the same time, many dissimilarity measures including Minkowski distance (Lp), cosine similarity, Hamming, Jaccard, Mahalanobis, Chebyshev, and KL-divergence are not Euclidean and sometimes even not a metric. Real world examples of genome data set [17] used in the experiments are also non-Euclidean. When such dissimilarities have their respective applications and are indeed used in practice (possibly more than anticipated), it is necessary to study such dissimilarities under dimension reduction. It is common if we look at the scientific history where scientists step outside comfort zone and ask -- what is beyond this assumption?\nFor the same reason, we have different views regarding that the use of non-metric distances potentially leading to confusion or misinterpretation. We hold an optimistic view that broadening our study of dissimilarity beyond Euclidean distances can bring us new opportunities and our work can be helpful in this direction.\n\n[17] B. C. Feltes, et al., CuMiDa: an extensively curated microarray database for benchmarking and testing of machine learning approaches in cancer research. Journal of Computational Biology, 26(4):376–386, 2019.\n\n- ### Regarding Random matrices\nWe fully agree that real world data is unlikely to generate a fully random matrix. In addition, we would like to add two interesting implications of this theoretical study. First, Euclidean distances support aggressive dimension reduction as evidenced by the Johnson Lindenstrauss Lemma (from $n$ dimensional space to $O(\\frac{1}{\\varepsilon^2}\\log n)$ dimensional space with $1+\\varepsilon$ distortion). The analysis for a random symmetric matrix points out that aggressive dimension reduction is indeed a luxury for Euclidean or other structured data, even if we use inner products that are not limited to Euclidean distances. Second, any real world data carries some measurement noise. When the scale of such random noise becomes non-negligible, STRESS error introduced by such noise cannot be small with aggressive dimension reduction. We would recommend practitioners to examine the spectrum of eigenvalues to gain insights on the power or limit in reducing dimensions.", "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": "", "extra_scores": {}}, {"review_id": "jspsRqxLWz", "reviewer": "Reviewer_EWdH", "summary": "In this paper, the authors propose a variant of MDS that is able to deal with data with a non-Euclidean structure. The main idea is to generalize the inner product to a bilinear form, hence admitting some relationships corresponding to \"negative eigenvalues,\" interpreted as in an inner product form $u^TAv$. Although a closed-form solution is not possible, the authors optimize over a lower bound. The paper ends with empirical evaluations both on synthetic and real data, with promising results.", "questions": "I have a couple of questions related to real/complex values.\n\nIn line 99. why real/imaginary-valued dissimilarity when in the next line it reads $D\\in \\mathbb{R}^{n \\times n}$ ?\n\nIn equation (3). Then $X$ is complex (since $\\sqrt{\\Lambda}$ is). Because in the problem formulation you are looking for real embeddings.\n\nAlso related to that. If $X$ is complex, in the equation at the end of that page (page 4), shouldn't it be the complex conjugate instead of only the transpose?\n\nSomehow related to these last two points. Does it make sense to include the sign of the eigenvalue in Diag(w) (and therefore $w$ can have values in $\\{0,1,-1\\}$, and the (squared root) absolute value of the eigenvalues in $\\sqrt{\\Lambda}$?\nSomething like the Generalized RDPG in \"A statistical interpretation of spectral embedding: the generalised random dot product graph\" by Rubin-Delanchy et al.\n\nIn line 303:  \"all dataset are non-metric\", but then in Table 1 there's a column indicating wether the dataset is metric.\n\nMinor comments:\n- In equation (1), use \\left( \\right)\n- Line 259:  \"The we ask\"", "limitations": "Although there is no specific section for this, some limitations are commented on throughout the manuscript.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written in general. The introduction and motivation are very clear. Although most of the bounds and some ideas are already in [38], the idea of including negative eigenvalues and its implementation is interesting.\n\nAnother strength is the availability of the code.", "weaknesses": "The introduction and problem definition are quite detailed (which is good), but I think that some of these facts may be considered well-known, like basic linear algebra facts. This could be used to include more specific material with the page restriction.\n\nI also think that the experimental section needs a subsection to interpret the embeddings. Throughout the paper (and supplementary material) there are numerical results reported, but the embeddings are never plotted. At least for some toy example.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your careful reading and valuable feedback. In the following we address the concerns.\n\n- ### Regarding complex values\nIn Line 99, we apologize for the confusion. $D$ is the squared dissimilarity matrix in general. We will emphasize it in the revision.   \n\nRegarding the complex (pure imaginary) entries in $X$, first we want to clarify that, these imaginary entries do not lie in traditional complex plane as one would expect. The reason is that the inner product (bilinear form) we use here is not the same as the traditional complex inner product (taking conjugate) defined for a complex plane.  Therefore, the geometric meaning is totally different. This also partially answers the question why we could not use the complex conjugate in the equation at the end of page 4. The complex conjugate will produce a wrong dissimilarity matrix which cannot reconstruct the original one. \n\nIn the old version paper, we allow complex values in $X$ in order to simplify the mathematic expressions (the sign of eigenvalues will be absorbed). However, as observed now, we found it brings more confusion. In the revised vision later, we would only use real valued X together with a signed diagonal matrix $A=sign(\\lambda)$. More precisely,  let $X=\\sqrt{diag{|\\lambda|\\odot w}} \\cdot U^T$, and then use bilinear form $f(u, v)=u^TAv$ with the matrix $A$ as a diagonal matrix with $k$ non-zero values in $\\{+1, -1\\}$, with the sign matching the sign of the eigenvalues selected in $w$. Then $\\hat{D}_{ij}=f(X_i-X_j, X_i-X_j)=(X_i-X_j)^TA(X_i-X_j)$. \n\nRegarding the sign and absolute eigenvalues, yes, it contains important information. For our distance reconstruction tasks, we weighted eigenvectors by the square root of eigenvalues, together with signed diagonal matrix of eigenvalues. In other applications, there are different ways to combine these information. \n\nThe referenced paper of the work regarding Generalized RDPG is very interesting and highly related to our work. In general, our settings work for any symmetric dissimilarity (hollow) matrices, and one important motivation is to study the graph or network structure which is usually far from Euclidean geometry. One example mentioned in that paper about stochastic block models with cross-block probability higher than in-block probability,  $B_{1,2} > B_{1,1}, B_{2,2}$, might be highly related to the hyberbolic geometry which is one of our motivating examples to study the general bilinear form with both positive and negative eigenvalues. Also, the way of visualization and interpretations of negative eigenvalues also inspire us a lot. We believe the study in that paper could be a good example and support of our work. We will include some discussions in the revised version.\n\nIn line 303, there is a typo. It should be “all dataset are non-Euclidean or non-metric”. Non-metric means the dissimilarity matrix even does not satisfy triangle inequality. Sorry for the confusion and we will make it clear in the revision.\n\n- ### Regarding interpretation of embeddings and visualization:\nOne idea for the interpretation of the non-Euclidean distances is that the dissimilarities are metric distances between two sets of points. One way to view this is that each data element is actually a distribution with some uncertainty. The non-Euclidean distance actually penalizes such uncertainty. This is our ongoing work, which will likely to be a separate follow up paper. \n\nInspired by the referenced work, we also plot some 2-dimensional neudMDS embeddings of word embeddings from a Bert model trained for some text classification tasks. The plots include positive-positive, positive-negative, and negative-negative eigenvectors of the neucMDS. See the attached file in general response.", "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": "", "extra_scores": {}}]

Author rebuttal:
We appreciate the efforts by reviewers and would like to clarify a few questions and answer to raised concerns. We are glad that this submission has been found to be:

- Well-written (Reviewer wzYh, EWdH)

- Showing solid/thorough experimental results (all reviewers)

- Accompanied with convincing theoretical analysis (Reviewer wzYh, 3cJU, RtpY) 

- With codes are publicly available (Reviewer EWdH). 

We would like to first respond to general concerns and then independent reviews. The common issues include (1) Computational complexity, (2) Practicality of the output distances and (3) Experiments on non-linear methods.

- ### Computational Complexity

Recall that Neuc-MDS has exactly the same running time as classical MDS, which is $O(n^3)$ due to eigen-decomposition, therefore, no extra cost asymptotically.

In addition, from Line 173-183, we included some suggestions of reducing running time by computing only the $k$ eigenvalues and eigenvectors needed. 

On top of that, for extremely large datasets, we can use landmark version of non-Euclidean MDS. Landmark MDS [1] is a heuristic to speed up classical MDS. We choose $h$ landmarks and apply MDS on the landmarks first. The coordinates of the remaining points are obtained through a triangulation step with respect to the landmarks. We can use the same heuristic to speed up Neuc-MDS. We ran some additional tests with landmark Neuc-MDS on our random-simplex dataset and got the following results. If we use only 25\% points randomly chosen as landmarks the STRESS is only a factor of $1.0644$ of the STRESS obtained by Neuc-MDS. If we use only 10\% points as landmarks, the final STRESS is only $1.0898$ of the STRESS of Neuc-MDS. This shows that Neuc-MDS can also be significantly accelerated using the landmark idea, achieving nearly the same STRESS. 

[1] Vin de Silva, et al. Sparse multidimensional scaling, using landmark points.

- ### Practicality of Output Distances

Squared dissimilarity matrices with negative entries do appear in a number of popular mathematical models. We present two examples here. 

1. In elementary plane geometry,
the power of a point $P$ relative to a circle (center $O$, radius $r$) is $|PO|^2-r^2$, introduced by Jakob Steiner, reflects the relative distance of a given point from a given circle. It is positive outside the circle (squared tangential distance) and negative inside (negative squared distance to a point $S$ on the circle where $PSO$ forms a right triangle).
The power of a point leads to a natural structure power diagram -- Voronoi diagram of circles. It is a planar convex subdivision where inside the cell of a circle $c$, all points have power distance to $c$ to be the smallest compared to other circles. The power diagram is a fundamental notion in computational geometry with applications of data structures and algorithms for a collection of disks [2], that serve as foundation to many problems in computational biology --- molecules are often modeled as spheres. It is related to semi-discrete optimal transportation [3], fluid dynamics [5], capacitated clustering [4] and area-preserving mapping in machine learning [6], and early universe reconstruction. 

[2] H. Imai, et al. Voronoi diagram in the Laguerre geometry and its applications.

[3] F. Aurenhammer, et al. Minkowski-Type Theorems and Least-Squares Clustering.

[4] C. Ni, et al. Capacitated Kinetic Clustering in Mobile Networks by Optimal Transportation Theory.

[5] B. L\'{e}vy,  Partial optimal transport for a constant-volume Lagrangian mesh with free boundaries. 

[6] Na Lei, et al. A Geometric View of Optimal Transportation and Generative Model''.

2. Negative inner product norms have deep connections to the study of spacetime with special relativity. The Lorentzian $n$-space is an inner product space on $\mathbb{R}^n$ together with a non-PSD Lorentzian inner product norm: $|x|=-x^2_0 + x_1^2+\cdots + x^2_{n-1}$. The $n$-dimensional Lorentzian space is naturally classified into types based on the sign of the squared norm: spacelike (positive), timelike (negative) and lightlike (zero). The collection of all timelike vectors lie in the open subset formed by the interior of the light cone. For two similarly directed (both forward or backward in time) time-like vectors triangle inequality works in the opposite direction. Four-dimensional Lorentzian space is called the Minkowski space and forms the basis of special relativity. Furthermore, the collection of vectors in $\mathbb{R}^{n+1}$ with Lorentzian inner product of $-1$ has imaginary Lorentzian length and is precisely the hyperboloid model of the hyperbolic $n$-space $\mathbb{H}^n$ [7]. Along this line there are two potential directions of research. 

First, with the increasing adoption of embedding in non-Euclidean spaces (e.g., hyperbolic spaces [8]) in machine learning models, we expect that non-Euclidean norms will find more applications. The second promising direction is in machine learning for physics model and data (AI4Sicence), see [9] for an example on the use of a feed-forward neural network for Petrov's classification of spacetimes.

[7] Ratcliffe, J. G. Foundations of Hyperbolic Manifolds.

[8] I. Chami, et al. Hyperbolic Graph Convolutional Neural Networks.

[9] Y. He, et al. Machine-Learning the Classification of Spacetimes.

We acknowledge that current machine learning practices predominantly take distances to be at least a metric space. The authors believe that it is necessary and the right time to expand our scope and consider non-Euclidean measures. This paper is making one step in this direction. 

- ### Experiments on Non-linear Methods and visualization
We compare Neuc-MDS with t-SNE, a popular non-linear method. In the submission we compared with Smacof, also a non-linear method. Neuc-MDS outperforms other methods.
We also plot some 2-dimensional neudMDS embeddings of word-embeddings from a pretrained BERT model for a text classification task.  See results in the attached pdf.

Meta-review: This paper proposes Non-Euclidean Multidimensional Scaling (Neuc-MDS) as an extension of classical Multidimensional Scaling (MDS), which can handle non-Euclidean and non-metric data. The idea is interesting and would be helpful. The weaknesses of the work are the computational complexity and the comparison with other non-linear methods.
Decision: Accept (poster)