Multidimensional Scaling in the Poincare Disk

Abstract—Multidimensional scaling (MDS) is a class of projective algorithms traditionally used to produce two-or three-dimensional visualizations of datasets consisting of multidimensional objects or interobject distances. Re-cently, metric MDS has been applied to the problems of graph embedding for the purpose of approximate encoding of edge or path costs using node coordinates in metric space. Several authors have also pointed out that for data with an inherent hierarchical structure, hyperbolic target space may be a more suitable choice for accurate embedding than Euclidean space. In this paper we present the theory and the implementation details of MDS-PD, a metric MDS algorithm designed specifically for the Poincaré disk model of the hyperbolic plane. Our construction is based on an approximate hyperbolic line search and exemplifies some of the particulars that need to be addressed when applying iterative optimization methods in a hyperbolic space model. MDS-PD can be used both as a visualization tool and as an embedding algorithm. We provide several examples to illustrate the utility of MDS-PD. Index Terms—dimensionality reduction, hyperbolic em-bedding, hyperbolic MDS, network graph, steepest descent, visualization