# Multidimensional Scaling: Approximation and Complexity

arXiv: https://arxiv.org/abs/2109.11505 · HTML: https://mlsanity.com/paper/2109.11505/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 44 references that are in the map.
- First posted on arXiv 23 Sep 2021.

## Builds on (most cited first, 6 of 6)

- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Clustering with t-SNE, provably](https://mlsanity.com/paper/1706.02582/) (2017)
- [An Analysis of the t-SNE Algorithm for Data Visualization](https://mlsanity.com/paper/1803.01768/) (2018)
- [Stochastic Gradient Descent Works Really Well for Stress Minimization](https://mlsanity.com/paper/2008.10376/) (2020)
- [Going for Speed: Sublinear Algorithms for Dense r-CSPs](https://mlsanity.com/paper/1407.7887/) (2014)

## Built on by (most cited first, 7 of 7)

- [A Normalized Bottleneck Distance on Persistence Diagrams and Homology Preservation under Dimension Reduction](https://mlsanity.com/paper/2306.06727/) (2023)
- [CoRe-GD: A Hierarchical Framework for Scalable Graph Visualization with GNNs](https://mlsanity.com/paper/2402.06706/) (2024)
- [DUPRE: Data Utility Prediction for Efficient Data Valuation](https://mlsanity.com/paper/2502.16152/) (2025)
- [Quantum circuit complexity and unsupervised machine learning of topological order](https://mlsanity.com/paper/2508.04486/) (2025)
- [Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams](https://mlsanity.com/paper/2311.17840/) (2023)
- [Forest-Guided Semantic Transport for Label-Supervised Manifold Alignment](https://mlsanity.com/paper/2602.00974/) (2026)
- [Leveraging Model Soups to Classify Intangible Cultural Heritage Images from the Mekong Delta](https://mlsanity.com/paper/2603.02181/) (2026)

## Abstract (arXiv)

Metric Multidimensional scaling (MDS) is a classical method for generating meaningful (non-linear) low-dimensional embeddings of high-dimensional data. MDS has a long history in the statistics, machine learning, and graph drawing communities. In particular, the Kamada-Kawai force-directed graph drawing method is equivalent to MDS and is one of the most popular ways in practice to embed graphs into low dimensions. Despite its ubiquity, our theoretical understanding of MDS remains limited as its objective function is highly non-convex. In this paper, we prove that minimizing the Kamada-Kawai objective is NP-hard and give a provable approximation algorithm for optimizing it, which in particular is a PTAS on low-diameter graphs. We supplement this result with experiments suggesting possible connections between our greedy approximation algorithm and gradient-based methods.