Paper by Erik D. Demaine

Reference:

Erik Demaine, Adam Hesterberg, Frederic Koehler, Jayson Lynch, and John Urschel, “Multidimensional Scaling: Approximation and Complexity”, in Proceedings of the 38th International Conference on Machine Learning (ICML 2021), edited by Meila, Marina and Zhang, Tong, Proceedings of Machine Learning Research, volume 139, July 18–24, 2021, pages 2568–2578.

BibTeX

@InProceedings{KamadaKawai_ICML2021,
  AUTHOR        = {Erik Demaine and Adam Hesterberg and Frederic Koehler and Jayson Lynch and John Urschel},
  TITLE         = {Multidimensional Scaling: Approximation and Complexity},
  BOOKTITLE     = {Proceedings of the 38th International Conference on Machine Learning (ICML 2021)},
  bookurl       = {https://icml.cc/Conferences/2021},
  PAGES         = {2568--2578},
  YEAR          = 2021,
  EDITOR        = {Meila, Marina and Zhang, Tong},
  VOLUME        = 139,
  SERIES        = {Proceedings of Machine Learning Research},
  MONTH         = {July 18--24},

  length        = {11 pages},
  dblp          = {https://dblp.org/rec/conf/icml/DemaineHKLU21},
  ee            = {http://proceedings.mlr.press/v139/demaine21a.html},
  comments      = {The <A HREF="long.pdf">long paper</A> (22 pages) and <A HREF="kamada_kawai_code.ipynb">code</A> are supplementary materials. <P> This paper and supplementary materials are also available from <A HREF="https://proceedings.mlr.press/v139/demaine21a.html">PMLR</A>. <P> The full paper is also available as <A HREF="https://arxiv.org/abs/2109.11505">arXiv:2109.11505</A>.},
}

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.

Comments:

The long paper (22 pages) and code are supplementary materials.

This paper and supplementary materials are also available from PMLR.

The full paper is also available as arXiv:2109.11505.

Length:

The paper is 11 pages.

Availability:

The paper is available in PDF (2384k).

See information on file formats.

[Google Scholar search]