Multidimensional Scaling: Approximation and Complexity

Erik D. Demaine, Adam Hesterberg, Frederic Koehler, Jayson Lynch, John C. Urschel

Abstract

Metric Multidimensional Scaling (MDS) is a classical method for generating meaningful low-dimensional embeddings of high-dimensional data. Despite its ubiquity in statistics, machine learning, and graph drawing—most notably via the Kamada-Kawai force-directed method—the theoretical landscape of MDS has remained largely unexplored due to the highly non-convex nature of its objective function. This paper addresses this gap by proving that minimizing the Kamada-Kawai objective is NP-hard. Furthermore, we present a provable approximation algorithm (a PTAS) for low-diameter graphs and supplement these theoretical findings with experiments that demonstrate the efficacy of combining greedy approximation with gradient-based refinement.

Introduction

Metric Multidimensional Scaling (mMDS) seeks to embed high-dimensional points into a lower-dimensional space (typically $\mathbb{R}^2$ or $\mathbb{R}^3$) while preserving pairwise distances. In the context of graph drawing, this is frequently implemented using the Kamada-Kawai (KK) objective, which treats edges as physical springs with an energy function defined by the difference between graph distances and Euclidean distances in the embedding.

While tools like Graphviz utilize this method daily, practitioners often rely on local search heuristics such as gradient descent or stress majorization. These methods are prone to getting trapped in local minima. Until now, the computational complexity of finding a global minimum for the KK objective was unknown, and no algorithms existed with provable guarantees for global optimization.

Complexity and Structural Analysis

The research establishes two primary theoretical pillars: the hardness of the problem and the structural properties of optimal embeddings.

NP-Hardness

The authors prove that minimizing the Kamada-Kawai objective is NP-hard, even in the simplest case of 1D embeddings and for graphs with very small diameters. This result is achieved through a reduction from a restricted version of Max All-Equal 3SAT. Crucially, the proof extends to a "gap" version of the problem, ruling out the existence of a Fully Polynomial-Time Randomized Approximation Scheme (FPRAS) unless P=NP.

Structural Lemmas

To facilitate the design of an approximation algorithm, the paper provides two key structural insights:

  1. Energy Lower Bound: For graphs with a low diameter, the minimum energy of the embedding is shown to be at least $\Omega(n^2)$. This provides a scale for the additive error in the approximation scheme.
  2. Diameter Upper Bound: The authors prove that an optimal embedding is "contractive" in a sense; its diameter is bounded by $O(D \log \log D)$, where $D$ is the diameter of the input graph. This ensures that the search space for an optimal layout does not expand infinitely.

The KKScheme Algorithm

Leveraging techniques from the Dense Constraint Satisfaction Problem (CSP) literature, the authors introduce KKScheme. This algorithm utilizes a discretization argument—creating an $\epsilon$-net of the bounded embedding space—and a greedy selection process to find an approximate global minimum.

For fixed dimensions $r$ and graph diameter $D$, KKScheme functions as a Polynomial-Time Approximation Scheme (PTAS), achieving an additive error of $\epsilon n^2$. This is particularly significant for "small-world" networks, where the diameter $D$ is small, making the problem theoretically tractable for many real-world social and biological datasets.

Experimental Evaluation

The authors tested their approach against standard benchmarks, including Watts-Strogatz synthetic graphs, the 3elt graph, and the Davis Southern Women Network.

Key Findings:

  • Hybrid Optimization: While the PTAS is theoretically sound, its constant factors can be high. However, using the greedy approximation as a "warm-start" for gradient descent yielded superior results. In the Davis Southern Women experiment, this "Greedy + Grad" approach achieved a normalized objective value of 0.0498, outperforming pure Gradient Descent (0.0515) and pure Greedy (0.0588).
  • Community Recovery: When applied to Stochastic Block Models (SBM), the MDS embeddings successfully recovered latent community structures. The resulting visualizations were often clearer than those produced by standard spectral (Laplacian) embeddings.
  • Robustness: The algorithm maintained performance across various topologies, including geometric graphs like the dodecahedron and cubic lattices.

Conclusion and Future Work

This work provides the first rigorous complexity analysis of the Kamada-Kawai objective, proving its NP-hardness while offering a provable approximation path for low-diameter graphs. The results suggest that the "small-world" property of real-world networks is not just a social phenomenon but a structural advantage that makes MDS more tractable.

Future research directions include narrowing the gap in the diameter conjecture—specifically proving whether the bound is a simpler $O(D)$—and investigating whether gradient descent with random restarts can formally match the guarantees provided by the greedy approximation scheme.

Summary updated

Abstract

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.
BibTeX
@inproceedings{demaine2021multidimensional,
  author = {Erik D. Demaine and Adam Hesterberg and Frederic Koehler and Jayson Lynch and John C. Urschel},
  title = {{Multidimensional Scaling: Approximation and Complexity}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=rFMnAgnRkr},
}
Figure