Graph-based measures to assist user assessment of multidimensional projections

Multidimensional projections are valuable tools to generate visualizations that support exploratory analysis of a wide variety of complex high-dimensional data. However, projection mappings obtained from different techniques vary considerably, and users exploring the mappings or selecting between projection techniques still have limited assistance in their task. Current methods to assess projection quality fail to capture properties that are paramount to user interpretation, such as the capability of conveying class information, or the preservation of groups and neighborhoods from the original space. In this paper we propose a unifying framework to derive objective measures of the local behavior of projection mappings that support interpreting the mappings and comparing solutions regarding several properties. A quality value is computed for each data point, from which a single global value may be also assigned to the projection. Measures are computed from a recently introduced data graph model known as Extended Minimum Spanning Tree (EMST). Measurements of the topology of EMST graphs, built relative to the original and projected data representations, are scale independent and afford evaluation of multiple properties. We introduce measures of visual properties and of preservation of properties from the original space. They are targeted at (i) depicting class segregation capability; (ii) quantifying 'neighborhood purity' regarding classes; (iii) evaluating neighborhood preservation; and finally (iv) evaluating group preservation. We introduce the measures and illustrate how they can inform users about the local and global behavior of projection techniques considering multiple mappings of artificial and real data sets.