Neuc-MDS: Non-Euclidean Multidimensional Scaling Through Bilinear Forms

We sincerely thank you for your careful reading and valuable feedback. In the following we address the concerns.

• Regarding complex values

In Line 99, we apologize for the confusion. $D$ is the squared dissimilarity matrix in general. We will emphasize it in the revision.

Regarding 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.

In 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)$.

Regarding 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.

The 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.

In 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.

• Regarding interpretation of embeddings and visualization:

One 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.

Inspired 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.

We sincerely thank you for your careful reading and valuable feedback. In the following we address the concerns.

• Regarding Computation and Scalability

We 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.

• Regarding complexity of implementing Neuc-MDS

Our 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.

• Regarding comparison with other methods

We 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.

• Regarding Interpretation of dissimilarities

One 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.

• Regarding assumptions on dissimilarity matrices

We 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.

• Regarding Lorenzian distances and non-metric dissimilarities

Indeed 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? For 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.

[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.

• Regarding Random matrices

We 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.

We sincerely thank you for your careful reading and valuable feedback. In the following we address the concerns.

• Regarding the problem definition (Definition 3.1) and description

For 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$ (there was a typo in Definition 3.1 regarding the notation $\hat{D}_{i,j}$. we'll correct it in the revision).

When $A$ is the identity matrix, the bilinear form gives a classical inner product and the dissimilarity is the (squared) Euclidean distance. When $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$. In 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.

How 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$. The 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}))$.

• Regarding non-PSD A

One 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).

• Regarding Line 137

Thank 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.

• Regarding NeucMDS vs NeucMDS+

Theoretically, 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. Empirically, 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.

• Regarding formatting

We appreciate your comments on formatting and will address these issues in the revised version.

Dear Reviewer,

Thank you again for your constructive review. We appreciate your recognition of our error analysis and the importance of our topic.

We hope our detailed response has addressed your concerns regarding the construction and the non-PSD properties of the bilinear form matrix A, the comparison between Neuc-MDS and Neuc-MDS+, and the noted formatting issues. We will include these updates in the revision. Please also see our general response, where we summarize the key steps taken to address the concerns of all the reviewers.

As the deadline is approaching, if you feel that we have sufficiently addressed your concerns, we would greatly appreciate if you could update your score.

Best regards.

Thank you for your valuable feedback, we respond to your comments as follows.

• Computational Complexity

Thanks 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.

• Additional Experiments with t-SNE

In 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.

• Interpretability

Beyond 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.

• Negative Distances

We have discussions and provide two examples with references in the general response 2.

• Downstream Tasks

Exploring 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.

• Non-Euclidean Datasets

In 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.

In 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.

Please let us know if there is anything further we could help clarify. Thanks again for your time and efforts!

Thank you. I'll keep my score. I do think that there are more directions in which to push this line of research and I don't want to ding the authors for not writing an extensive long paper (or three or four more) at this time!