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

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.

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. Another 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. I 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.

Questions

I have a couple of questions related to real/complex values. In line 99. why real/imaginary-valued dissimilarity when in the next line it reads $D\in \mathbb{R}^{n \times n}$ ? In equation (3). Then $X$ is complex (since $\sqrt{\Lambda}$ is). Because in the problem formulation you are looking for real embeddings. Also 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? Somehow 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}$? Something like the Generalized RDPG in "A statistical interpretation of spectral embedding: the generalised random dot product graph" by Rubin-Delanchy et al. In line 303: "all dataset are non-metric", but then in Table 1 there's a column indicating wether the dataset is metric. Minor comments: - In equation (1), use \left( \right) - Line 259: "The we ask"

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

Although there is no specific section for this, some limitations are commented on throughout the manuscript.

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)

Strengths

1. Neuc-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. 2. Neuc-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. 3. Neuc-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. The 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. 2. Some 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. 3. The 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. 4. The 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.

Questions

1. How 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? 2. How 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? 3. To 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? 4. How 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?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

See weakness

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.

Strengths

1. the error analysis seems solid. 2. the topic is important which can extend to non-Euclidean MDS 3. 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. 2. 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. 3. Line 137 you claim X can be recovered from B, however this is not precise. 4. the formatting can be improved, for example the fontsize Table 3 can be reduced and figure 3 can be better.

Questions

What is the advantage of Neuc-MDS over Neuc-MDS+ or the opposite direction? From the experiments, I didn't find difference.

Rating

4

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

NA

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: 1. It generalizes the inner product to more general symmetric bilinear forms, allowing the use of both positive and negative eigenvalues of dissimilarity matrices. 2. 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. 3. The authors provide theoretical analysis of the error and prove optimality in minimizing lower bounds of STRESS. 4. They introduce two algorithms: Neuc-MDS and an advanced version Neuc-MDS+. 5. Theoretical analysis is provided for the asymptotic behavior of classical MDS and Neuc-MDS on random symmetric matrices. 6. Experimental results on 10 diverse datasets show that Neuc-MDS and Neuc-MDS+ outperform previous methods on STRESS and average distortion metrics. 7. The proposed methods resolve the "dimensionality paradox" issue of classical MDS, where increasing dimensions can lead to worse performance. 8. The approach is applicable to both image and text data, and can handle various non-Euclidean dissimilarity measures. 9. The paper provides detailed proofs, algorithm descriptions, and experimental results in the appendices. Overall, 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.

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: 1. 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. 2. 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. 3. 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. 4. 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. 5. 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. 6. 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? 7. 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?

Questions

See above.

Rating

7

Confidence

5

Soundness

4

Presentation

3

Contribution

3

Limitations

not applicable.