arXiv CSopen access

Measuring Distortion in the Empty Regions of Dimensionality Reduction Scatterplots with the Gap Index

Measuring Distortion in the Empty Regions of Dimensionality Reduction Scatterplots with the Gap Index Jaume Ros

Triangulation

, Alessio Arleo

Deformation

, and Fernando Paulovich

Aggregation

Visualization

arXiv:2607.28324v1 [cs.LG] 30 Jul 2026

Lower is better

Figure 1: Overview of the computation of the Gap Index. Firstly, the projection is decomposed into triangles, which are then matched to their corresponding counterparts in high-dimensional space, and a deformation value is computed for each. The result can be aggregated into a single scalar quantifying the overall distortion, or overlaid on the scatterplot in order to see the distortion; the empty areas are colored with a divergent scale from blue (compression) to red (stretch), with yellow indicating no distortion. Abstract—Quality metrics play a crucial role in the proper use of dimensionality reduction projections for visual analysis of highdimensional data. They quantify the degree of distortion of a projection compared to the high-dimensional data and provide a reliable indication of how confident users can be in the structures they see in the resulting layouts. However, most popular metrics focus on capturing direct relationships between points (e.g., distances or neighborhoods) while neglecting distortions in empty areas of the layout, even though these often compose visually relevant features of a 2D layout. In this paper, we introduce the Gap Index (GI), a quality metric for 2D projections that captures visual distortion by measuring spatial distortion in empty areas of a projection. It does so by decomposing the space into empty triangles, which are then compared to their high-dimensional counterparts to compute the deformation. This per-triangle deformation can be aggregated into a single scalar value or overlaid on a projection to visualize regional distortion patterns. Results show that, contrary to popular quality metrics, the GI is sensitive to small structural deformations that have high visual impact. It is also fast to compute and interpretable. Index Terms—Dimensionality reduction, quality metric

1

I NTRODUCTION

Dimensionality Reduction (DR) plays a crucial role in the analysis of high-dimensional data. By projecting the data points into a twodimensional space, the data can be visualized as a scatterplot, enabling a variety of visual analytics tasks [32]. However, unless the original data lies on a two-dimensional manifold, any DR projection will necessarily entail some distortion. This can take the form of a loss of information about the high-dimensional structure that cannot be displayed in 2D, and the appearance of spurious patterns in the plot that are not present in the original data. Although this effect is known to DR experts, measuring the reliability of the projection is crucial for improving confidence in the visual analysis insights [31]. Quality metrics serve to quantify the distortion introduced by the DR process. There are numerous examples that specialize in capturing specific properties or distortions in the data [14, 24]. They are an essential part of any analysis that leverages DR. Without measuring the quality of the projection, it is more difficult to “trust” the patterns displayed by (and absent from) the projection. Additionally, quality metrics can support visual analysis by providing feedback on which regions of the

• Jaume Ros, Alessio Arleo, and Fernando Paulovich are with Eindhoven University of Technology. E-mail: {j.ros.alonso | a.arleo | f.paulovich}@tue.nl . Manuscript received xx xxx. 202x; accepted xx xxx. 202x. Date of Publication xx xxx. 202x; date of current version xx xxx. 202x. For information on obtaining reprints of this article, please send e-mail to: [email protected]. Digital Object Identifier: xx.xxxx/TVCG.202x.xxxxxxx

projection have experienced higher degrees of distortion [25]. While widely used by DR practitioners, common quality metrics are not necessarily sensitive to changes that have a high visual impact. Indeed, recent literature raised awareness about cases where a significant distortion in the visual layout is not properly captured by quality metrics [26]; this can lead to overconfidence in the analysis of the projection. An example of such an issue is presented in Fig. 2. The plane dataset consists of 2k points randomly distributed on a plane and embedded in 3D space. Compared to the PCA projection [18], which captures the plane perfectly, a local technique such as t-distributed Stochastic Neighbor Embedding (t-SNE) [52] (with a perplexity value of 30) generates spurious patterns, a well-known and expected outcome [58]. This distortion has a high visual impact and can mislead visual analysis; however, it is minimal in terms of per-point structural preservation, and common metrics such as scale-normalized stress [48] (from now on referred simply as “stress”) and trustworthiness [53], reported in Fig. 2, struggle to capture it. Machado et al. [26] argue that standard quality metrics are built on relatively simple approaches with limited scope (e.g., comparing pairwise distances or per-point neighborhoods) and thus cannot capture the richer patterns that humans might see in a projection, such as class clusters and their visual separation. This raises the need to develop quality metrics that better correlate with the human perception of projections. Although the problem of assessing the quality of cluster separation in a projection has already been widely studied (see Sec. 2.2), less work has been done to measure that of empty regions, which inherently define clusters and other patterns important for visual analytics tasks [1, 10]. Indeed, the Gestalt law of proximity [56] states that groups of points placed close together are perceptually and pre-attentively grouped (in

(a) PCA Stress (↓): 0 Trustworthiness (↑): 1

(b) t-SNE Stress (↓): 0.0764 Trustworthiness (↑): 0.9993

Figure 2: Projections of the plane dataset with PCA and t-SNE. Common quality metrics such as stress (lower is better) and trustworthiness (higher is better) barely distinguish them, despite significant visual differences.

the case of DR, perceived to share a common set of abstract features not directly visualized [32]). Since groups and patterns of points are defined by the empty gaps in the projection (or lack thereof) [33,39,44], it is important to ensure that they are adequately displayed. In this paper, we address this issue by presenting the Gap Index (GI), a quality metric that quantifies projection distortion from a visual analysis perspective, with an explicit focus on the reliability of visible gaps in the layout. Contrary to popular quality metrics that compute distortion per-point (and later averaged to quantify the whole layout), the GI focuses on capturing the distortion of the empty areas between points. This makes the metric operate on a local scale and be sensitive to visually salient distortions, while capturing global distortion with a behavior similar to stress. To compute the distortions, the GI partitions the 2D projection into triangles and computes their deformation by comparing them with their high-dimensional counterparts. The set of per-triangle deformation measures can be aggregated into a single scalar value or displayed in the scatterplot to visualize distortion by region. The metric can be efficiently computed in 𝑂 (𝑁 log 𝑁) time, making it fast to run even for large datasets, and does not require explicit coordinates of the original points, as long as a set of triangular pairwise distances is provided. The core ideas of the GI were previously described by Ros et al. [41]; in this paper, we revisit and extend them. Additionally, we provide detailed use cases for the GI and comparisons with other popular quality metrics. Our contributions are the following: (1) we identify limitations in the usage of common quality metrics for visual analysis, and we propose a novel perspective for evaluating the quality of DR projections; (2) we introduce the GI, a quality metric that measures the distortion in the visual features of a scatterplot; and (3) we present a collection of artificial and real datasets used to benchmark the behavior of the GI alongside other popular quality metrics. An open-source Python implementation of the GI, along with code to reproduce the results presented in this paper, is available online [43]. 2 BACKGROUND AND R ELATED W ORK In this section, we introduce background concepts and previous work that will help readers follow the rest of the discussion in the paper. 2.1 Evaluating DR projections Quality metrics for DR, also known as distortion measures, compute how faithful a low-dimensional projection (usually 2D) is as a representation of the original high-dimensional data, following different criteria in terms of which type of high-dimensional structures are aimed to be preserved [14]. The application of quality metrics is twofold. Firstly, they are used as an objective function in DR techniques to find the optimal projection of the high-dimensional data according to that criterion [13, 30, 54]; secondly, DR practitioners use them to assess the quality of the final result. In this paper, we focus mainly on the latter.

With the exception of DR methods that provide an explicit mapping to Cartesian coordinates, such as PCA, the absolute positions of points in the 2D layout carry no information; only relative positions with respect to other points are relevant, and scatterplots are typically displayed without orthogonal axes and other frames of reference [32]. For the same reason, quality metrics are generally invariant to a rigid transformation of the projection. Another possible transformation of the layout is uniform scaling by a factor 𝛼. Since users tend to ignore scaling during visual analysis, it is generally desired that quality metrics also be invariant to this transformation (scale-invariant, sometimes referred to as normalized), although this is not always the case [48]. Scale-invariant metrics tend to be bounded within a certain range (typically [0, 1]), making them easier to interpret [32]; the GI is one such metric. 2.2

Standard quality metrics

Quality metrics generally aim to measure how well the structure of the original data is preserved in the projection. There exists a multitude of metrics, each focusing on different properties of the data structure. A common taxonomy divides them by their target structural granularity, where metrics can be considered global, local, and cluster-level [14]. In the following, we provide relevant examples of popular quality metrics; for a more complete discussion of global and local metrics, we refer the reader to the survey by Nonato and Aupetit [32]. Global metrics quantify distortion by measuring the preservation of distances between all points. Stress metrics compute the square difference of pairwise distances between the original and projected points and are the most common type of quality metric in this category. There exist multiple variations of it [30], such as raw stress [50], Kruskal stress [22], Sammon stress [45], and scale-normalized stress [48]. Unless otherwise specified, throughout this paper, we use scale-normalized stress as the preferred type of stress measure. A popular alternative to stress is correlation-based metrics, such as Shepard goodness [7], which computes the Spearman rank correlation of the Shepard diagram [17] (i.e., the correlation between the set of pairwise distances in high- and low-dimensional spaces), or the correlation coefficient [9]. On the other hand, local metrics operate in the neighborhood of each point and measure, element-wise, the number of neighbors in the original data which are no longer neighbors in the projection (missing neighbors), and the number of neighbors in the projection which are not actually neighbors in the original data (false neighbors) [32]. Trustworthiness and continuity [53] are two well-known metrics in this category; they measure the degree to which false and missing neighbors occur for each point. Smooth neighborhood preservation [35] measures both the number of neighbors preserved and their change in distance. Lee and Verleysen [24] review some of the most popular quality metrics in this category. Finally, cluster-level metrics measure the preservation of cluster structures between the original and projected data; examples are steadiness and cohesiveness [15]. It should be noted that the metrics listed in this section are unsupervised since they do not make use of external information, such as class labels. There exists a broad collection of supervised metrics, especially of cluster-level granularity, that make use of labeled data, such as distance consistency [47], neighborhood hit [36], and GONG [4]; however, these are intended mainly to be used in supervised tasks (e.g., projecting data in order to maximize class separation [55]), rather than visual analysis of the data. The previous taxonomy is based on metrics that measure distortion from the placement of the points. The GI operates differently, accounting for distortion in the gaps of the projection; therefore, it cannot be clearly classified into any of the previous categories. From a distortion-per-point perspective, the GI behaves, on the one hand, as a local metric, since the position of a point only affects the quality values of the triangles incident to it; on the other hand, it captures distortion between points that are arbitrarily far away, as long as they are separated by empty space, which only global metrics measure. The foundational idea for the GI was first proposed by Warnking et al. [57], who introduced the concept of triangulating the 2D pro-

jection and computing the compression ratio for each triangle. Later, Aupetit [3] further formalized the method into a measure of local distortion for each triangle; however, this approach was intended primarily as a tool to visualize compressed and stretched regions of a projection. With the GI, we develop it into a full projection quality metric, including a normalization of the areas to ensure scale invariance, and an aggregation of all local values into a single scalar while taking into account the relative importance of each. 2.3 What the user sees vs. what the user should see The distortions in the projection, with regard to visual analysis, are typically described as having two forms [32]: data structures in the high-dimensional space that are not observable in the projection, and structures and patterns visible in the projection that do not exist in the original data. This distinction plays an important role in visual analysis, since it captures two different phenomena that users might want to check separately: “are there features in the data that are not visible?”, and “are the visible features real?”. In the context of neighborhood preservation, this is sometimes expressed with the duality of missing neighbors and false neighbors, presented in the previous section. Most quality metrics do not distinguish between the two; instead, they compare the high-dimensional space and its projection simultaneously (e.g., stress compares both sets of pairwise distances). However, there are metrics that take this distinction into account and come in two dual forms, each capturing one type of deformation. A well-known example is trustworthiness and continuity [53], which measure the preservation of local neighborhoods across spaces. Steadiness and cohesiveness [15] follow the same approach at the cluster level. The GI uses a similar approach but focuses primarily on assessing the projection’s veracity. As such, it captures simultaneously (1) whether gaps in the layout are also gaps in the original data, and (2) whether non-gaps in the layout are also non-gaps in the original data. 2.4 Visualizing distortion in the plot Quality metrics typically produce a single scalar value that quantifies the total distortion of a projection. While this is convenient for numerically comparing projections, it offers limited detail for the visual analysis of 2D projections. However, most metrics allow one to compute the distortion for each individual point. Rather than averaging to quantify the quality of the whole projection, one can visually analyze the local data; this allows users to see which regions of the scatterplot are better preserved and which have experienced greater distortion. This approach provides more detailed information about the distortion observed in the data, but it also poses challenges for visualization. The easiest and most common method is to color the points of the projected layout according to a specific scalar quality metric [11, 31]. However, this approach can suffer from scalability issues, as layouts must ensure that all individual points remain legible and often require space-filling techniques [28] or binning [34]. More advanced approaches use interactivity to enhance the analysis of the visualization [12, 28]. Aupetit [3] proposed the idea of displaying per-point quality information in the background of a scatterplot by coloring the Voronoi cell of each point according to its quality. This was further developed in the CheckViz method [25], which uses a 2D color map to encode two types of distortion simultaneously. The authors argue that a colored background provides contextual information about the foreground while avoiding perceptual side effects produced by coloring the points. However, they acknowledge two shortcomings: first, larger Voronoi cells around isolated points are more visible, creating an area bias; second, this visualization can mislead the user into inferring that the background color quantifies deformation in the empty space itself, whereas it only displays information about the point. Notice that both of these issues do not affect our approach, since we color empty areas according to the distortion measured on the empty areas themselves. 3 M ETHODOLOGY In this section, we provide intuition and formalize the Gap Index (GI) as a quality metric, including its computation and visualization overlaid on a DR scatterplot. In addition to the main proposed approach, we

also provide alternatives for each step of the computation, which DR practitioners may find useful for tuning the GI to explore different types of distortion. To set notation, let X = {𝑥𝑖 ∈ R𝑞 | 1 ≤ 𝑖 ≤ 𝑁 } be a projection of a set of 𝑁 high-dimensional points X̂ = {𝑥ˆ𝑖 ∈ R𝐷 | 1 ≤ 𝑖 ≤ 𝑁 }, with 𝐷 > 𝑞 (in the context of visual analysis, 𝑞 = 2). A quality metric is a function Q (X, X̂) → R that quantifies the degree of structural preservation of X with respect to X̂. Among the various structural distortions introduced by a DR technique, the GI focuses on measuring the distortion of layout gaps or empty spaces, in terms of stretching or compression, relative to the complete layout. It does so by comparing the proportion of space that the regions in X use, compared to the same regions in X̂. 3.1

Overview of the GI

The computation of the GI given X and X̂ follows a modular structure, as shown in Fig. 1: first, a triangulation of the points is constructed on the projection, partitioning X into a set of triangles T (X) = {𝑡 1 , 𝑡2 , . . . , 𝑡 𝑚 }. Subsequently, we compute the deformation of each triangle 𝑡 𝑖 , by relating it to the triangle 𝑡ˆ𝑖 formed by the same three points in X̂; finally, the user can choose to perform an aggregation step, to obtain a single scalar value Q (X, X̂) quantifying the overall distortion of the projection, or to visualize the distorted regions on top of the scatterplot. These steps are detailed in the following subsections. We make no assumptions about the projection technique, except that it produces a 2D configuration of data points (X). The GI is intended primarily to be used with two-dimensional projections, which is the most common scenario in the use of DR for visual analysis of highdimensional data; however, in Sec. 6 we discuss its possible use to evaluate projections of higher dimensionality. Additionally, the GI only requires pairwise triangular distances between the original points X̂, rather than explicit coordinates for each point. 3.2

Triangulation

The GI, rather than focusing on individual points, operates on the empty spaces, or gaps, in the 2D projection. Thus, the first step is to subdivide the visual space into smaller regions for which to compute the distortion. We propose to decompose it into triangles defined by the projected points, motivated by multiple factors: (1) a triangle is a simple primitive, which simplifies computations; (2) any triangle defined by three points in X will have a corresponding triangle in the original space, possibly with zero area, defined by the corresponding points in X̂ (this is not the case with primitives of higher order, such as quads, since unless the points are planar in high-dimensional space, their areas are ill-defined); (3) trigonometric operations allow one to compute properties of a triangle defined only by the lengths of its edges, which is needed if X̂ is given simply as a set of distances, rather than explicit high-dimensional Euclidean coordinates; finally, (4) there exist simple and well-known methods to decompose the 2D space into a set of triangles. Our method of choice for this step is the Delaunay triangulation, a widely used and well-studied triangulation technique [8]. It decomposes the 2D space into triangles with the layout points as vertices. These triangles are non-overlapping and empty, and they cover the full convex hull of the projected points, which we consider the total visual space of a projection. Moreover, it maximizes the minimum angle among all triangles, avoiding thin triangles that can cause numerical instability [5]. The Delaunay triangulation also offers computational advantages, since efficient algorithms exist to compute it from a set of 2D points in 𝑂 (𝑁 log 𝑁) time [5], and the number of triangles generated is on the order of 𝑂 (𝑁) [46]. Since the complexity of the entire GI is dominated by the triangulation, this makes the GI fast to compute as a metric. Finally, given a set of points, this approach is nonparametric and has a unique solution, assuming that degenerate cases such as cocircular points are resolved deterministically, making the GI also a deterministic metric.

3.3 Triangle deformation The previous step produces a set of triangles T (X) = {𝑡 1 , 𝑡2 , . . . , 𝑡 𝑚 }. Each triangle 𝑡 𝑖 ∈ T (X) is defined by three vertices, which are points in X. We can then consider the corresponding triangle 𝑡ˆ𝑖 in the original space formed by the same three points in X̂ and measure its deformation in the projection. Our suggested approach is to compare the relative areas of each triangle. Let 𝐴(𝑡𝑖 ) denote the area of triangle 𝑖 in X, and 𝐴( 𝑡ˆ𝑖 ) the area of the corresponding triangle in X̂. Let 𝐴′ (𝑡𝑖 ) and 𝐴′ ( 𝑡ˆ𝑖 ) be the relative areas of each triangle: 𝐴′ (𝑡𝑖 ) = Í

𝐴(𝑡 𝑖 ) , 𝑗 𝐴(𝑡 𝑗 )

𝐴′ ( 𝑡ˆ𝑖 ) = Í

𝐴( 𝑡ˆ𝑖 ) . 𝑗 𝐴( 𝑡ˆ𝑗 )

(1)

Relative areas compare the proportion of the total space taken by each triangle, which is easier to interpret than their raw values. This also ensures that the metric is scale-invariant, which is a desirable property for metrics intended to capture visual distortions, as motivated in Sec. 2.1 and discussed in Sec. 5. We then define the deformation of a triangle 𝑡𝑖 as 𝐷 (𝑡 𝑖 , 𝑡ˆ𝑖 ) =

𝐴′ (𝑡𝑖 ) − 𝐴′ ( 𝑡ˆ𝑖 ) , 𝑚𝑎𝑥( 𝐴′ (𝑡𝑖 ), 𝐴′ ( 𝑡ˆ𝑖 ))

(2)

where the denominator ensures that the value is in the range [−1, 1], with positive values of 𝐷 (𝑡 𝑖 , 𝑡ˆ𝑖 ) meaning that the relative size of triangle 𝑡 𝑖 is bigger than in the original space, indicating a stretching in the visual space. Conversely, negative values of 𝐷 (𝑡𝑖 , 𝑡ˆ𝑖 ) indicate that the region has been compressed in the projection. This formulation is similar to the one proposed by Aupetit [3], the main differences being the use of relative rather than raw areas, and that we compute a single deformation value instead of two separate ones for compression and stretch. Note that even if there are no explicit Euclidean coordinates for high-dimensional points, one can compute the area of the triangle only from the distances between points using Heron’s formula: √︁ 𝐴(𝑎, 𝑏, 𝑐) = 𝑠 · (𝑠 − 𝑎) · (𝑠 − 𝑏) · (𝑠 − 𝑐) (3) where 𝑎, 𝑏, and 𝑐 are the edge lengths of the triangle (i.e., the distances between the three high-dimensional points) and 𝑠 = (𝑎 + 𝑏 + 𝑐)/2. The distances are assumed to fulfill the triangular inequality (otherwise 𝐴(𝑎, 𝑏, 𝑐) will result in a complex value); this assumption is reasonable, since a set of non-triangular distances cannot be meaningfully projected in 2D space seeking to preserve the distances or any similarity (e.g., the t-SNE probabilities) derived from it. Since extremely thin triangles can pose precision problems during the computation of the area, we recommend clipping the result beyond a tolerance value (e.g., 10−6 ) and considering the area as 0 (if 𝐴(𝑡 𝑖 ) = 𝐴( 𝑡ˆ𝑖 ) = 0, then 𝐷 (𝑡𝑖 , 𝑡ˆ𝑖 ) = 0 by convention); however, it should be noted that there exist alternative formulations for Eq. (3) that are numerically more stable to compute with floating-point precision [19]. Computing the area of 𝑡ˆ𝑖 through distances, rather than highdimensional Euclidean coordinates, has the advantage of allowing the use of different distance functions, reflected in the values of 𝑎, 𝑏, and 𝑐. If one uses a DR technique that optimizes for the preservation of non-Euclidean distances (e.g., Isomap [49], which uses geodesic distances in a nearest-neighbors graph), it is advisable to use that function also in the computation of 𝐴( 𝑡ˆ𝑖 ), as it will make the metric more coherent with the projection [51]. While in this paper we only consider Euclidean distances for the computation of 𝐴( 𝑡ˆ𝑖 ), users should be aware of its limitations [2], which affect all quality metrics that rely on distances (such as stress, trustworthiness and continuity, or cluster-based metrics). Particularly for the GI, this can result in all triangles in the original space of high-dimensionality having a similar area, and the metric correlating with the density of the points in 2D. In such cases, alternatives to the distance metric that are more meaningful in a space of high-dimensionality, such as the 𝐿 1 distance, could be preferred. 3.4 Aggregation To compute a single scalar metric that quantifies the overall distortion of the projection, we aggregate all triangle deformation values. Since

(a) COIL20 dataset – PCA projection

(b) Fashion MNIST dataset – t-SNE projection

Figure 3: Visualization of the GI on two projections. Red indicates a stretch of the space; blue, a compression; and yellow, no distortion.

not all triangles in T (X) are equally relevant to the global result, we propose using a weighted average of their values. A triangle is considered relevant if it has a large relative area in X, in X̂, or both, since those are the ones that encode the largest and most salient gaps, whether in the projection or in the original space; thus, we weight the deformation of a triangle 𝐷 (𝑡𝑖 , 𝑡ˆ𝑖 ) by 𝑤 𝑖 = max( 𝐴′ (𝑡 𝑖 ), 𝐴′ ( 𝑡ˆ𝑖 )). This gives the final GI value of a projection X of a set of high-dimensional points X̂: 𝐺 𝐼 (X, X̂) = Í

1

∑︁

𝑤 𝑖 𝐷 (𝑡 𝑖 , 𝑡ˆ𝑖 ) ,

(4)

𝑡𝑖 ∈ T (X) 𝑤 𝑖 𝑡 ∈ T (X) 𝑖

where T (X) is the set of triangles from the triangulation of X, and 𝑡ˆ𝑖 is the corresponding high-dimensional triangle to 𝑡 𝑖 . 𝐷 (𝑡 𝑖 , 𝑡ˆ𝑖 ) ∈ [−1, 1] is the triangle deformation value as defined in Eq. (2); notice the absolute sign, since here we only care about the magnitude of the deformation, and opposite deformations should not cancel each other. The weights 𝑤 𝑖 = max( 𝐴′ (𝑡𝑖 ), 𝐴′ ( 𝑡ˆ𝑖 )) ensure that larger triangles have a greater influence on the final value. Indeed, a large triangle in X represents a salient gap in the projection, which should have an important contribution to the total value (positive if the gap exists in X̂, and negative if it does not); likewise, large deformation values for large triangles in X̂ correspond to important gaps in the original space, and the total quality should be heavily penalized if they are not visible in the 2D layout. 𝑤 𝑖 is only small when both 𝐴′ (𝑡𝑖 ) and 𝐴′ ( 𝑡ˆ𝑖 ) are small; these are triangles that have little visual relevance. Other choices of 𝑤 𝑖 are possible and serve to capture different types of distortion. One could consider using 𝑤 𝑖 = 𝐴′ (𝑡𝑖 ), which focuses only on capturing whether the gaps in X exist in X̂; conversely, 𝑤 𝑖 = 𝐴′ ( 𝑡ˆ𝑖 ) will capture whether the gaps in X̂ are well represented in X. 3.5 Visualizing the GI As mentioned in Sec. 2.4, visualizing the distortion on top of a scatterplot is useful for conveying local distortions, allowing users to see patterns and region-specific distortions that would be obscured when aggregated into a single scalar, as in Eq. (4). Contrary to previous common quality metrics, which compute perpoint distortion and rely on space-filling techniques to color the background of the scatterplot, the GI measures the distortion of the empty visual space; thus, the values 𝐷 (𝑡𝑖 , 𝑡ˆ𝑖 ) can be naturally displayed and interpreted as background. Since the Delaunay triangulation will cover the entire convex hull of the 2D layout without any overlap, the most natural method of displaying the GI is to color the triangles according to their distortion value 𝐷 (𝑡𝑖 , 𝑡ˆ𝑖 ). This is shown in Fig. 3. We use a divergent red-yellow-blue color scheme to encode the two opposite distortions: red indicates a stretch (the triangle has a larger relative area than in X̂), and blue indicates a compression (the triangle has a smaller relative area than in X̂). Yellow indicates no distortion; we use yellow rather than white to ensure that it remains distinguishable against a white background. Looking at Fig. 3, a shortcoming of this approach becomes evident: the triangles distract from the visualization of the overall distortion,

Figure 4: Visualization of the GI on a t-SNE projection of the fashion MNIST dataset with different levels of background smoothing. From left to right, the blur levels are: 𝜎 = 0, 𝜎 = 10, 𝜎 = 20, 𝜎 = 40. (a) Cube dataset – PCA projection GI value: 0.755

despite them bearing no connection to the data beyond being a particular subdivision of the 2D space. Even though edge lines are not drawn, the hard boundaries between adjacent areas make the underlying triangulation easily visible; moreover, thin, elongated triangles, which generally have small area and thus contribute little to the final value, can be visually salient, complicating the visual analysis of the distortion. While directly observing the triangles can be useful for a more detailed understanding of the individual deformation values, users seeking a general assessment of the projection distortion might prefer a less detailed view. To overcome this issue, we propose to smooth the colored background, as shown in Fig. 4. This ensures that the main distortion patterns remain visible, while the boundaries between individual triangles are softened. In our example, we consider a uniform Gaussian blur with a user-defined standard deviation 𝜎 to control the degree of smoothing. Higher levels of blur provide a coarser picture of the local distortion, while lower levels are useful for showing more specific details, as illustrated in Fig. 4; the level of blur is left to the user. 4

R ESULTS

In this section, we report examples of using the GI across different datasets, compare its behavior to other popular quality metrics, and test its properties under varying conditions. Firstly, we show the use of the GI in two controlled DR scenarios to illustrate how to interpret the results of the metric. We then quantitatively compare it to other popular quality metrics and qualitatively compare it with alternatives to visualize local distortion. Then, we test the scalability of the GI (again, comparing it to other metrics) and the stability of the Delaunay triangulation. Finally, we explore a practical use case in the DR literature by evaluating a projection of protein data with the GI. We compare the GI to other popular quality metrics from different categories: scale-normalized stress [48] (referred to here simply as “stress”), trustworthiness and continuity [53], and steadiness and cohesiveness [15], which are global, local, and cluster-level metrics, respectively. We include only the results we consider most relevant, but we encourage interested readers to consult the supplementary material for a more extensive collection of results, including plots of all projections. As mentioned in the introduction, the code for the GI and scripts to reproduce these results are publicly available online [43]. For the other quality metrics, as well as the CheckViz visualization technique, we use the implementation from ZADU [14]; the only exception is during the scalability test (Sec. 4.4), where we used an adapted implementation of stress and trustworthiness from Espadoto et al. [7], since we found it to be faster and less resource-intensive. 4.1

Interpreting the GI

We use two DR projections of synthetic 3D datasets to showcase the use of the GI and familiarize the reader with the interpretation of the results. The projections, colored according to the GI, are shown in Fig. 5. The cube dataset consists of a set of 1k points randomly distributed along 5 sides of a 3D cube. Figure 5a shows its PCA projection, where the aggregated GI has a final value of 0.755, indicating a highly distorted projection; upon visual inspection, this is evident. Four of its filled sides have been collapsed into a square with a high density of points on the outline, while the interior of the square is filled with the points of the remaining non-empty face. Although the points in this fifth face

(b) Clusters dataset – t-SNE projection GI value: 0.482

Figure 5: Visualization of the GI on projections of two different datasets: (a) an empty 3D cube with a missing face; (b) five equally-sized clusters randomly positioned in 3D space.

are well positioned (since rigid projections, such as PCA, will never “stretch” the data), the empty space between them is disproportionately high compared to the rest of the dataset, spanning almost the entire visual space, whereas in the original 3D manifold it is only a fifth of the surface area; thus, this is shown as a stretched area (red) and heavily penalizes the value of the GI. The four remaining faces are collapsed into lines, giving the impression of dense areas. Figure 5b shows a t-SNE projection of the clusters dataset, which consists of 5 clusters randomly positioned in 3D space; clusters consist of 100 points each, normally distributed, and with the same variance. As expected, t-SNE correctly separates the clusters, but, being a local technique, the space between clusters is distorted [58]; the GI has a value of 0.482, indicating substantial distortion. Visualizing the distortion on top of the projection helps explain the reason for this value and infer information about the original 3D structure. We can see that the space between the top and leftmost clusters has been compressed, indicating they were originally farther apart; the opposite occurs for the other three clusters, where the space between them has increased, indicating they were originally closer. We invite the reader to check the original 3D data in the supplementary material and verify that this is indeed the case. 4.2

GI to quantify the overall distortion

In the previous paragraphs, alongside the visualization of the GI, we reported the aggregated value of the GI. Its main use is to compare different projections of the same dataset; in this case, it helps assess which projection is better and, to some extent, by how much. However, this single value is of too low granularity for users interested in analyzing the distortions in detail, who should prefer to visualize the metric on top of a scatterplot of the projection. An example is the plane dataset, which has already been introduced in Sec. 1, consisting of a set of 2k points placed randomly in a plane in 3D space (i.e., a uniform distribution in [0, 1] 2 placed in 3D space with a random rotation). Scatterplots of two projections of it are shown in Fig. 2. In Fig. 6, we show the visualization of the GI for the same two projections. The PCA projection captures all pairwise distances between points, yielding optimal values for all quality metrics. However, the t-SNE projection shows visible distortion, with gaps that define clusters of points and give the impression that the original data has an inherently complex structure. This visually salient distortion is barely captured by other quality metrics, as shown in Figs. 2 and 6 (more examples can be found in the supplementary material), but it is significantly penalized by the GI. Using the GI, a DR practitioner who encounters the two projections is able to confidently say that the t-SNE projection has important distortion; moreover, by visualizing the local distortions on top of the scatterplot, it becomes evident that the empty regions and dense clusters are artifacts of the DR method used to create the projection. For a more complex use case, we study the sphere dataset: a set of 5k points randomly placed inside a 200-dimensional hypersphere

Δ=0 (a) PCA Stress (↓): 0 Trustworthiness (↑): 1 Gap Index (↓): 0

Δ = 0.2

(b) t-SNE Stress (↓): 0.0764 Trustworthiness (↑): 0.9993 Gap Index (↓): 0.5118

Value

Figure 6: The two projections from Fig. 2 colored according to the GI. The PCA projection preserves all the gaps perfectly and thus has no distortion. The gaps on the tSNE projection are identified as a stretching of the space (red), while the clusters correspond to a compression (blue).

GI to visualize local distortion

Previous results compared quality metrics that capture the overall distortion of the projection as a single scalar value. However, another

1.0 0.8 0.6 0.4 0.2 0.0 0.000

Cohes. GI Cont. Trust. Stress Stead. 0.025

0.050

0.075

0.100

0.125

Stretch factor ( )

0.150

0.175

0.200

Figure 7: Behavior of multiple quality metrics at different levels of distortion of a mMDS projection of the sphere dataset. Top: scatterplots of the dataset at different values of Δ ∈ [0, 0.2]; middle: visualization of the distortion with the GI for each of the previous scatterplots; bottom: line chart showing the value of each quality metric as Δ increases. Notice the overlap between continuity and trustworthiness. Note that all five reported metrics are in [0, 1]: for stress and the GI, lower is better; for the rest, higher is better.

𝑝 = 20

Value

of radius 1. The high intrinsic dimensionality of this dataset makes it difficult to project accurately to 2D, and some DR projections tend to create spurious clusters and gaps that, although visually salient, popular quality metrics cannot properly capture. We consider the projection by metric Multidimensional Scaling [22] (mMDS), shown in Fig. 7 for Δ = 0. It captures the circular shape of the data, with a higher density towards the edges due to the distance concentration effect in highdimensional space [37], and it does not show any spurious structure. We distort this initial projection by iteratively optimizing a random subset of 50 anchor points 𝑎 1 . . . 𝑎 50 and optimizing the rest of the 2D layout around them. This is done by displacing any other point 𝑏 ≠ 𝑎 𝑖 in the direction of 𝑎®𝑖 𝑏 by a certain amount Δ (Δ = 0 indicates no displacement; Δ = 1 moves point 𝑏 until its distance in X matches that in X̂). This type of distortion was studied before [42] and found to produce strong visual distortion not captured by popular quality metrics, even for high values of Δ. In the line chart in Fig. 7, the values of multiple quality metrics are shown as Δ (and thus distortion) increases. We see that for Δ = 0, most metrics agree on the existing level of distortion, since the data has already been projected from 200 to 2 dimensions. However, the surprising result occurs as the value of Δ increases, creating noticeable gaps in the layout, while most metrics remain constant. Only the GI is capable of capturing this effect, increasing from 0.444 for Δ = 0, to 0.745 for Δ = 0.2. Additionally, the distortion plots of Fig. 7 show that indeed the openings have been captured as a stretch of the empty space (red), while the clusters correspond to compressed areas (blue). Finally, Fig. 8 shows the GI behavior on t-SNE projections of the cube dataset (already introduced in Sec. 4.1, with its PCA projection shown in Fig. 5a). As the perplexity 𝑝 increases (between 𝑝 = 20 and 𝑝 = 300, at intervals of 5), the global structure of the data is better captured: with 𝑝 = 20, spurious patterns and gaps emerge, which are heavily penalized by the GI; for 𝑝 = 70 the cube appears “unfolded” in the 2D plane, with the GI mostly penalizing the gaps on the sides, corresponding to the cuts of the original 3D shape; finally, for 𝑝 = 300 the scatterplot presents a mostly uniform and structureless set of points, but visualizing the GI reveals how it maps to the original 3D shape, with some regions of points having been stretched, and other compressed. The comparison with other metrics in the line chart of Fig. 8 shows that only cohesiveness significantly captures the difference between projections, although its values are noisier. The outliers for 𝑝 = 240 and 𝑝 = 275 are due to a misplaced cluster in the layout (creating a distorted visual gap); these examples, along with additional studies from other datasets, can be found in the supplementary material. 4.3

Δ = 0.1

1.0 0.8 0.6 0.4 0.2 0.0

𝑝 = 70

𝑝 = 300

Trust. Cont. Stead. Cohes. GI Stress 50

100

150

Perplexity

200

250

300

Figure 8: Behavior of multiple quality metrics for t-SNE projections of the cube dataset, with increasing values of perplexity 𝑝 ∈ [20, 300]. Top: scatterplots of the dataset at different values of 𝑝; middle: visualization of the distortion with the GI for each of the previous scatterplots; bottom: line chart showing the value of each quality metric as 𝑝 increases. Notice the overlap between continuity and trustworthiness. Note that all five reported metrics are in [0, 1]: for stress and the GI, lower is better; for the rest, higher is better.

𝜂=0

Figure 9: Per-point stress of a t-SNE projection of the plane dataset visualized with different coloring approaches: (a) points, (b) Voronoi cells, (c) Delaunay triangles. Colors go from purple (lowest) to yellow (highest).

1.2 0.8 0.4 0.0

common scenario is to use them to visualize local distortion, as discussed in Sec. 2.4. As mentioned throughout the paper, most quality metrics are computed per-point, which makes local distortion in the empty space hard to interpret. In Fig. 9, we show three different strategies for visualizing local distortion. In this example, we use per-point stress, but note that this applies to any per-point scalar metric. In (a), points are colored according to the value of the metric; while this approach is common due to its simplicity and allows for visualizing regional patterns of distortion, users are not provided with any information about the distortion in the empty regions. In (b), the corresponding Voronoi cell of each point is colored according to its stress value; this approach, popularized by CheckViz [25], displays per-point distortion in the background, but suffers from differences in cell size (some points are more salient) and hard boundaries between cells in the middle of empty regions. In (c), Delaunay triangles are colored based on the average values of their three vertices; while patterns are smoother than in the Voronoi diagram, averaging the three vertex values can obscure the interpretation of the metric, especially for large triangles with vertices in distant clusters. Through these examples, the need for a metric that measures distortion in the empty space becomes evident. Not only is stress unable to correctly identify the local distortion patterns (compare with the GI plot on Fig. 6b), but any attempt to color the background according to a per-point metric can potentially mislead the user into interpreting it as a distortion of space. 4.4 Using the GI on large datasets When using DR in a practical setting, one can encounter large datasets with thousands to millions of points. In such cases, fast quality metrics are needed as they allow evaluation of the distortion of the projection in a reasonable time and without excessive computational resources. Table 1: Execution time (in seconds) for different quality metrics on PCA projections of datasets with an increasing size (defined by the number of points 𝑁 ). The experiments have been run on a mid-range laptop with an Intel Core i7-13700H CPU and 16 GiB of memory. The reported times are the average over 10 iterations. Missing values indicate that the metric could not be computed due to excessive memory requirements.

Metric Stress Trust. S&C GI

Plane 𝑁 = 2k 0.03 0.19 0.91 0.07

Sphere 𝑁 = 5k 0.88 1.95 45.69 0.19

Fiber (small) 𝑁 = 19k 4.39 21.9 0.72

Fiber (large) 𝑁 = 250k 9.75

Table 1 shows a comparison of execution time for different metrics as the size of the data increases. The plane and sphere datasets, which we consider medium-sized, were introduced in previous sections. To test the scalability of quality metrics on a large dataset, we used the fiber dataset [38], which consists of 250k brain-tracking fiber streamlines; the small version is a subset of labeled data from the big one. We limit our study to a dataset of this magnitude, as we are already unable to compute any of the other metrics to compare to the GI.

𝜂 = 0.005

1e 2

(c)

stress SD

(b)

GI SD

(a)

0.1 0.2 0.5 1.0 1.5 2.0

Noise amount ( x100)

2.0 1.5 1.0 0.5 0.0

𝜂 = 0.02

1e 3

0.1 0.2 0.5 1.0 1.5 2.0

Noise amount ( x100)

Figure 10: Boxplots of the standard deviation (SD) of the GI (left) and stress (right). Each bar corresponds to a level of noise 𝜂 ∈ [0.001, 0.02], computed over 18 × 3 different datasets. The SD has been computed over the values of each quality metric on 10 repetitions of the same layout with random noise. At the top, we include, as an example, t-SNE projections of the COIL20 dataset with different levels of noise.

Global metrics such as stress have complexity 𝑂 (𝑁 2 ) due to the need to compute all pairwise distances. Trustworthiness, a local metric, relies on nearest-neighbor queries; since acceleration structures such as kd-trees [27] are inefficient in high-dimensional spaces, a brute-force approach is used. Thus, these two types of metrics exhibit similar scalability and can be used on datasets with up to a few tens of thousands of points. Unsupervised cluster-level metrics rely on expensive clustering algorithms and exhibit the worst scalability among all the metrics tested. Steadiness and cohesiveness (S&C) use the same clustering result from HDBSCAN [29] and are therefore computed together. As mentioned in Sec. 3.2, the GI has a cost of 𝑂 (𝑁 log 𝑁) (𝑁 being the number of points in X), determined by the Delaunay triangulation. It shows the best scalability of all metrics tested, both in terms of execution time and memory usage; it achieved an average time under a second for the fiber (small) dataset and it was the only metric capable of processing the largest dataset with our available computational resources, in around 10 seconds and with a memory usage of less than 2 GiB. Thus, it is a viable option to evaluate the quality of projections with a large number of points, even when other metrics fail. 4.5

Evaluating the Delaunay triangulation

In Sec. 3.2, we motivated the use of the Delaunay triangulation. However, a consequence of this choice is that the final value of the GI is not continuous with respect to the placement of the points in X, since a small change can create a different triangulation, which in turn would produce different values of triangle deformation and change the final aggregated result. Note that this effect is also present in most local and cluster-level metrics that depend on discrete structures such as neighborhoods (e.g., trustworthiness and continuity) and clusters (e.g., steadiness and cohesiveness). Although the GI has shown stability in the controlled cases of Sec. 4.2, in this section we study its effect on more realistic examples. To this end, we have used the diverse set of 18 datasets from Espadoto et al. [7], which feature different data types, sizes (both the number of points and the number of dimensions), and other particularities. For each, we computed projections using PCA, t-SNE, and mMDS. Note that the orl dataset contained errors in the original publication, but these have been fixed prior to the computation of the results presented here. On each of the 18 × 3 projections, we measure the standard deviation of the GI value as we randomly jitter the points over 10 iterations. For comparison, we have run the same analysis with stress, which is differentiable with respect to the point positions, and thus we expect it to behave consistently in this test. Note that the 2D

A

B

5 6

B.5

3 8

9 0 B.7

4

B.1

7

1 2 B.1

B.5

B.7

Figure 11: t-SNE projection of CNN embeddings of the MNIST dataset (1k instances for each class 0-9; 10k in total). (A) Scatterplot of the projection with points colored according to their label. (B) Corresponding GI visualization, with clusters 1, 5, and 7 enlarged at the bottom.

layouts have been uniformly scaled to [0, 1] 2 to ensure that noise of the same magnitude has a similar effect across all of them; since both the GI and stress are scale-invariant, this change has no effect on the final values of the metrics. We also include the projections of the 18 datasets with different DR methods, along with reported quality values of multiple metrics, in the supplementary material. The results are shown in the form of a boxplot in Fig. 10. As expected, the standard deviation increases with the noise level; however, it does so consistently and within reasonable values. The higher standard deviation values for the GI can also be attributed to its higher sensitivity to small visual changes compared to stress, as shown previously. 4.6

A practical use case for the GI

To complement the previous results, we present an example of the use of the GI in the context of explainable artificial intelligence (XAI). We trained a small convolutional neural network (CNN) to identify digits from the MNIST dataset [23] (28 × 28 grayscale images of handwritten digits); the model achieves an accuracy of 99%, but it remains a black box to users. A common XAI practice to gain insight into the behavior of the network is to visualize its latent states; since these are usually of high-dimensionality, DR techniques are used [40]. In our example, we consider a t-SNE projection of the last hidden layer of the CNN, which consists of 64-dimensional embeddings of the test instances; this is shown in Fig. 11A. In the supplementary material, we provide more information about the dataset, the architecture of the CNN, and additional results with alternative models and datasets. Figure 11A shows a scatterplot of the projection, with points colored according to their label. It is expected that a neural network with 99% accuracy will have well-separated embeddings in its last hidden layer, and the DR plot confirms this, presenting 10 distinct clusters, each corresponding to a single class (with some exceptions of misclassified instances). All clusters present a similar compact shape, and their global position is generally meaningless, as expected from a local technique (t-SNE with a perplexity value of 100). However, a more complete picture emerges when visualizing the GI of the projection (Fig. 11B). The first observation is that clusters are compressed, while the empty space between them is heavily stretched. This is common and expected for GI visualizations of local DR methods, such as t-SNE. Although experienced DR practitioners are likely aware of this behavior, it can

help avoid misuse of these techniques by less familiar users [16]. This large distortion of the empty space is heavily penalized when aggregating the GI, which results in a value of 0.81 (compared to a better 0.63 for mMDS, a global technique), yet t-SNE’s clearly separated clusters may still be preferred in many analytical tasks, and visualizing the GI can provide further insights to complement it. On a global scale, it provides some information about the positioning of the clusters. More intense red indicates that the distance between two clusters has been more stretched than other pairs; thus, we can infer that cluster pairs (5,8), (0,6), (0,8), or (4,9) are in reality closer than they appear in the t-SNE projection. This is reasonable, given the similar patterns of their handwritten shapes. In contrast, other pairs of clusters have been less stretched; examples are pairs (4,8) and (3,9). The GI also allows for the study of properties of specific regions; the enlarged clusters in Fig. 11, which correspond to labels 1, 5, and 7, serve as examples. The space between points in cluster 1 is mostly stretched, contrary to the others; this can be explained by t-SNE’s tendency to project all clusters at a similar density [58], and indicates that the embeddings of this cluster are actually more compact than what is being projected. The opposite happens with cluster 5, which is shown to be more compressed than others, indicating that the embeddings of its elements were originally more dispersed. Cluster 7 presents both types of distortion, yet the GI is still useful for analyzing the cluster’s shape and identifying which gaps are reliable and which have been distorted by the projection; this effect is also visible in cluster 9. These observations not only prevent users from drawing naïve wrong conclusions about the data (e.g., assuming that all clusters are similar in density), but also provide valuable information to support analysis of global and local structure (e.g., which gaps between and within clusters are reliable). Of course, the GI needs to be used in accordance with the analytical task at hand; if assessing the veracity of gaps is not a priority, other quality metrics might still be preferred. As with other quality metrics, the GI is necessary to quantify some types of distortion, but should not be used as a single criterion to quantify the total quality [26]. Moreover, in order to avoid misusing the GI, users should also be aware of its limitations, which are discussed in the next section. 5

D ISCUSSIONS AND L IMITATIONS

Using the GI beyond 2D projections. In this paper, we focus on the applicability of the GI to 2D layouts, which is the main use case for visual analysis of DR projections. However, it should be noted that it can also be computed for projections of higher dimension, since the Delaunay triangulation generalizes to higher dimensions [8] (although with an increased computational cost), and the volume of an 𝑛-dimensional simplex can be computed through the Cayley–Menger determinant [21]. For one-dimensional projections, the notion of triangulation becomes degenerate; one could still consider segmenting the 1D layout into 1-simplices (i.e., lines between adjacent points). Note that it would be different from stress, since the one-dimensional GI would only consider distances between adjacent points (i.e., gaps in the layout) rather than all possible pairs. All these cases, although theoretically possible, require further study of the impact on the metric’s interpretability, the types of distortion it could capture, and its visualization. Limitations of the triangle deformation approach. The triangle deformation function, defined in Eq. (2), is based on the comparison of relative triangle areas. This makes the values easily interpretable as local compression and stretch (e.g., a distortion value of 0.9 indicates that the original relative area is only 10% of the projected relative area). However, while this has proven sufficient in the examples shown previously, there are cases where the position of the points can be distorted without changing the relative areas between them, such as uniform stretching of the whole layout, exemplified in the mock example in Fig. 12a, which the current formulation of the GI cannot capture. One can consider alternative deformation functions, which could potentially capture more complex types of distortion. In Fig. 12b, we compare visualizations of the GI using relative areas and perimeters (additional examples are provided in the supplementary material). Although the results are consistent between the two approaches, the

does not provide any information as to where the visual distortion has occurred (compare it with the visualization in Fig. 6b).

(a)

(b)

Figure 12: (a) Example of two 2D layouts whose triangulations (drawn for reference) generate triangles with the same relative area, but different perimeters. (b) t-SNE projections of the cube dataset, visualized using the GI with deformations based on area (left) or perimeter (right).

perimeter is less prone to having thin triangles with GI values different from those of their neighbors, resulting in smoother overall visualizations. However, this comes at a cost of interpretability (the sum of perimeters depends on the specific triangulation and is meaningless in the context of the visual analysis) and stability (a change in triangulation will cause the sum of perimeters to be different, while the total area would remain constant). Other more complex deformation functions, possibly involving angle comparison, could be explored in future work. Another limitation is the requirement for triangular distances in the high-dimensional space. Indeed, if the distances do not satisfy the triangular inequality, the computation area (Eq. (3)) will be a complex value and the computation of the GI will fail. We consider this to be a reasonable limitation, since the projection of a set of non-triangular distances is an ill-defined problem (e.g., what should a projection of three points 𝑎, 𝑏, and 𝑐, look like if their pairwise distances are not triangular?); for the same reason, other quality metrics such as stress are meaningless in these situations. Relative vs raw areas. The GI is intended to analyze visual distortion; thus, we focus on how important a gap in the layout is relative to all the others, also making the metric scale-invariant. For this reason, in Sec. 3.2, we suggest computing the deformation based on the relative areas of triangles (𝐴′ (𝑡𝑖 ), 𝐴′ ( 𝑡ˆ𝑖 )), rather than the raw areas (𝐴(𝑡 𝑖 ), 𝐴( 𝑡ˆ𝑖 )). To show the effect of this choice, in Fig. 13, we show two examples of scatterplots colored according to the triangle deformation with raw areas.

(a) Cube dataset – PCA projection

(b) Plane dataset – t-SNE projection

Figure 13: Visualization of the GI using raw areas for two projections. Compare them to Figs. 5a and 6b, respectively.

PCA, being an orthogonal projection of the data, will never stretch the raw area values; only compression is possible. Indeed, the middle area of the projection is perfectly preserved, while the other four sides of the cube are compressed. Compare this to the default GI visualization, shown in Fig. 5a, where we consider the middle area to occupy disproportionately large space and to be stretched. Thus, when using DR projection that preserves distances (such as PCA or mMDS), using raw areas is a reasonable alternative that can produce more intuitive results. A limitation of using raw areas is that they are not scale-independent and can be meaningless when applied to projections that are not explicitly intended to preserve distances, such as t-SNE. Indeed, the t-SNE projection of the plane dataset is shown as completely stretched, which

Alternatives to the Delaunay triangulation. Prior to computing triangle deformations, one could consider alternative sets of triangles. In Sec. 3.2, we justified our choice of using the Delaunay triangulation, and its behavior has been validated in Sec. 4. But the GI can, in theory, be computed from any set of empty triangles in the projection, even if they overlap or do not cover the full 2D space. A possible alternative is to compute the GI using all empty triangles in X; however, this would be impractical to use beyond small datasets, since computing such a set has a cost linear to the number of empty triangles [6], which is on the order
of Θ(𝑁 2 ) [20] (with a worst case of 𝑁3 , 𝑁 being the number of points). A small example of how such a triangulation would look, as well as some numerical results, is provided in the supplementary material. Future work can explore more complex triangulation strategies, such as using empty triangles with certain properties of shape and size (e.g., discarding small or thin triangles) or computing triangles in highdimensional space. Open visualization challenges. Our suggested visualization approach assumes that the triangles occupy the full visual space (defined by the convex hull of the 2D layout) and do not overlap; this is guaranteed by the Delaunay triangulation, but using other sets of triangles, as suggested earlier, might require different visualization methods to handle transparency and other effects. Moreover, the current triangle deformation function maps the triangle color to a single divergent normalized scale; if users choose to explore other deformation approaches, this should be adapted (e.g., using a 2D color space [25] or showing different distortion types separately [3]). Although effective, the current simple approach can lead to the loss of important details, such as small areas in the scatterplot that affect the distortion. One such case is heavily compressed areas, which are barely visible in the raw colored triangulation and could be erased through blurring. However, this problem is more general than just blurring, as compressed areas, despite having the same weight in the final aggregated result as stretched ones, are less visible in the scatterplot. Computing an embedding using the GI. Given a metric that computes the visual quality of an arbitrary embedding, a natural question is whether one can compute an embedding that optimizes such a metric, and what its properties would be. Although the GI is fast to compute, its current form is not differentiable (due to the use of the Delaunay triangulation and the deformation and aggregation functions); one must then rely on derivative-free optimization methods, such as simulated annealing. Moreover, edge cases should be considered, such as the limitation of the current deformation function to distinguish some types of distortion (Fig. 12a), or degenerate cases like a 2D layout collapsed into a single line, where no triangles exist. Given these complexities, we leave the design of a DR method based on the GI as future work. 6 C ONCLUSION In this paper, we discussed the high perceptual impact of gaps in a 2D projection when visualized as a scatterplot, and the inability of standard quality metrics to meaningfully capture distortion in the layout’s empty spaces. To address this issue, we introduced the Gap Index (GI), a quality metric that measures the compression and stretch of empty regions in the projection. It does so by triangulating the 2D projection, relating each triangle to its high-dimensional counterpart to compute a triangle-distortion value, and finally aggregating all values into a single scalar. We also suggested an approach to visualize local distortion directly in the scatterplot, allowing users to gain richer insights into the specific distortions present in the layout. The running time of the GI is 𝑂 (𝑁 log 𝑁), making it a scalable option to compute the quality of projections of large datasets. Additionally, we presented quantitative and qualitative results to showcase its usage, compared it to other popular quality metrics, and analyzed its behavior. In the discussion, we highlighted some limitations of the technique and suggested potential directions for future research.

R EFERENCES [1] M. M. Abbas, M. Aupetit, M. Sedlmair, and H. Bensmail. Clustme: A visual quality measure for ranking monochrome scatterplots based on cluster patterns. Computer Graphics Forum, 38(3):225–236, 2019. doi: 10.1111/cgf.13684 1 [2] C. C. Aggarwal, A. Hinneburg, and D. A. Keim. On the surprising behavior of distance metrics in high dimensional space. In International conference on database theory, pp. 420–434. Springer, 2001. doi: 10. 1007/3-540-44503-X_27 4 [3] M. Aupetit. Visualizing distortions and recovering topology in continuous projection techniques. Neurocomputing, 70(7–9):1304–1330, Mar. 2007. doi: 10.1016/j.neucom.2006.11.018 3, 4, 9 [4] M. Aupetit and M. Sedlmair. SepMe: 2002 new visual separation measures. In 2016 IEEE Pacific Visualization Symposium (PacificVis), pp. 1–8, 2016. doi: 10.1109/PACIFICVIS.2016.7465244 2 [5] M. De Berg, O. Cheong, M. Van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications, chap. 9. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. doi: 10.1007/978-3-540-77974-2 3 [6] D. P. Dobkin, H. Edelsbrunner, and M. H. Overmars. Searching for empty convex polygons. In Proceedings of the Fourth Annual Symposium on Computational Geometry, SCG ’88, pp. 224–228. Association for Computing Machinery, New York, NY, USA, 1988. doi: 10.1145/73393. 73416 9 [7] M. Espadoto, R. M. Martins, A. Kerren, N. S. T. Hirata, and A. C. Telea. Toward a quantitative survey of dimension reduction techniques. IEEE Transactions on Visualization and Computer Graphics, 27(3):2153–2173, Mar. 2021. doi: 10.1109/TVCG.2019.2944182 2, 5, 7 [8] S. Fortune. Voronoi diagrams and delaunay triangulations. In Handbook of discrete and computational geometry, pp. 705–721. Chapman and Hall/CRC, 2017. doi: 10.1007/978-3-642-27848-8_507-1 3, 8 [9] X. Geng, D.-C. Zhan, and Z.-H. Zhou. Supervised nonlinear dimensionality reduction for visualization and classification. IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics), 35(6):1098–1107, Dec. 2005. doi: 10.1109/TSMCB.2005.850151 2 [10] J. Giesen, L. Kühne, and P. Lucas. Sclow plots: Visualizing empty space. Computer Graphics Forum, 36(3):145–155, June 2017. doi: 10.1111/cgf. 13175 1 [11] M. Hermann, A. Greß, and R. Klein. Interactive exploration of large event datasets in high energy physics. J. WSCG, 17(1-3):41–48, 2009. 3 [12] N. Heulot, M. Aupetit, and J.-D. Fekete. Proxilens: Interactive exploration of high-dimensional data using projections. EuroVis Workshop on Visual Analytics using Multidimensional Projections, p. 5 pages, 2013. doi: 10. 2312/PE.VAMP.VAMP2013.011-015 3 [13] F. Inaba, E. Salles, and T. Rauber. Kernel sammon map. In 2011 24th SIBGRAPI Conference on Graphics, Patterns and Images, pp. 329–336. IEEE, Alagoas, MaceiA, Brazil, Aug. 2011. doi: 10.1109/SIBGRAPI. 2011.22 2 [14] H. Jeon, A. Cho, J. Jang, S. Lee, J. Hyun, H.-K. Ko et al. ZADU: A python library for evaluating the reliability of dimensionality reduction embeddings. In 2023 IEEE Visualization and Visual Analytics (VIS), pp. 196–200. IEEE, Melbourne, Australia, Oct. 2023. doi: 10.1109/VIS54172. 2023.00048 1, 2, 5 [15] H. Jeon, H.-K. Ko, J. Jo, Y. Kim, and J. Seo. Measuring and explaining the inter-cluster reliability of multidimensional projections. IEEE Transactions on Visualization and Computer Graphics, 28(1):551–561, Jan. 2022. doi: 10.1109/TVCG.2021.3114833 2, 3, 5 [16] H. Jeon, J. Park, S. Shin, and J. Seo. Stop misusing t-SNE and UMAP for visual analytics, 2025. doi: 10.48550/arXiv.2506.08725 8 [17] P. Joia, F. V. Paulovich, D. Coimbra, J. A. Cuminato, and L. G. Nonato. Local affine multidimensional projection. IEEE Transactions on Visualization and Computer Graphics, 17(12):2563–2571, Dec. 2011. doi: 10. 1109/TVCG.2011.220 2 [18] I. Jolliffe. Principal component analysis. Encyclopedia of statistics in behavioral science, 2005. doi: 10.1007/b98835 1 [19] W. Kahan. Mathematics written in sand. In Proc. Joint Statistical Mtg. of the American Statistical Association, pp. 12–26, 1983. 4 [20] M. Katchalski and A. Meir. On empty triangles determined by points in the plane. Acta Mathematica Hungarica, 51(3):323–328, 1988. doi: 10. 1007/BF01903339 9 [21] A. Kock. Square-densities, and volume forms, 2021. doi: 10.48550/arXiv. 2012.06210 8 [22] J. B. Kruskal. Multidimensional scaling by optimizing goodness of fit to a

nonmetric hypothesis. Psychometrika, 29(1):1–27, 1964. 2, 6 [23] Y. LeCun, C. Cortes, and C. Burges. MNIST handwritten digit database. ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist, 2, 2010. 8 [24] J. A. Lee and M. Verleysen. Quality assessment of dimensionality reduction: Rank-based criteria. Neurocomputing, 72(7–9):1431–1443, Mar. 2009. doi: 10.1016/j.neucom.2008.12.017 1, 2 [25] S. Lespinats and M. Aupetit. CheckViz: Sanity check and topological clues for linear and non-linear mappings. Computer Graphics Forum, 30(1):113–125, Mar. 2011. doi: 10.1111/j.1467-8659.2010.01835.x 1, 3, 7, 9 [26] A. Machado, M. Behrisch, and A. Telea. Necessary but not sufficient: Limitations of projection quality metrics. Computer Graphics Forum, p. e70101, May 2025. doi: 10.1111/cgf.70101 1, 8 [27] S. Maneewongvatana and D. M. Mount. Analysis of approximate nearest neighbor searching with clustered point sets, 1999. doi: 10.48550/arXiv. cs/9901013 7 [28] R. M. Martins, D. B. Coimbra, R. Minghim, and A. Telea. Visual analysis of dimensionality reduction quality for parameterized projections. Computers & Graphics, 41:26–42, June 2014. doi: 10.1016/j.cag.2014.01.006 3 [29] L. McInnes and J. Healy. Accelerated hierarchical density based clustering. In 2017 IEEE international conference on data mining workshops (ICDMW), pp. 33–42. IEEE, 2017. doi: 10.1109/ICDMW.2017.12 7 [30] A. Mead. Review of the development of multidimensional scaling methods. Journal of the Royal Statistical Society. Series D (The Statistician), 41(1):27–39, 1992. doi: 10.2307/2348634 2 [31] B. Mokbel, W. Lueks, A. Gisbrecht, and B. Hammer. Visualizing the quality of dimensionality reduction. Neurocomputing, 112:109–123, 2013. doi: 10.1016/j.neucom.2012.11.046 1, 3 [32] L. G. Nonato and M. Aupetit. Multidimensional projection for visual analytics: Linking techniques with distortions, tasks, and layout enrichment. IEEE Transactions on Visualization and Computer Graphics, 25(8):2650–2673, Aug. 2019. doi: 10.1109/TVCG.2018.2846735 1, 2, 3 [33] J. O’Callaghan. Human perception of homogeneous dot patterns. Perception, 3(1):33–45, 1974. doi: 10.1068/p030033 2 [34] A. A. Orlov, T. N. Akhmetshin, D. Horvath, G. Marcou, and A. Varnek. From high dimensions to human insight: Exploring dimensionality reduction for chemical space visualization. Molecular Informatics, 44(1):e202400265, 2025. doi: 10.1002/minf.202400265 3 [35] P. Pagliosa, F. V. Paulovich, R. Minghim, H. Levkowitz, and L. G. Nonato. Projection inspector: Assessment and synthesis of multidimensional projections. Neurocomputing, 150:599–610, Feb. 2015. doi: 10.1016/j.neucom.2014.07.072 2 [36] F. Paulovich, L. Nonato, R. Minghim, and H. Levkowitz. Least square projection: A fast high-precision multidimensional projection technique and its application to document mapping. IEEE Transactions on Visualization and Computer Graphics, 14(3):564–575, May 2008. doi: 10.1109/TVCG. 2007.70443 2 [37] D. Peng, Z. Gui, and H. Wu. Interpreting the curse of dimensionality from distance concentration and manifold effect, 2025. doi: 10.48550/arXiv. 2401.00422 6 [38] J. Poco, D. M. Eler, F. V. Paulovich, and R. Minghim. Employing 2D projections for fast visual exploration of large fiber tracking data. Computer Graphics Forum, 31(3pt2):1075–1084, June 2012. doi: 10.1111/j. 1467-8659.2012.03100.x 7 [39] G. J. Quadri and P. Rosen. Modeling the influence of visual density on cluster perception in scatterplots using topology. IEEE Transactions on Visualization and Computer Graphics, 27(2):1829–1839, 2021. doi: 10. 1109/TVCG.2020.3030365 2 [40] P. E. Rauber, S. G. Fadel, A. X. Falcão, and A. C. Telea. Visualizing the hidden activity of artificial neural networks. IEEE Transactions on Visualization and Computer Graphics, 23(1):101–110, 2017. doi: 10. 1109/TVCG.2016.2598838 8 [41] J. Ros, A. Arleo, and F. Paulovich. Mind the gaps: Measuring visual artifacts in dimensionality reduction, 2025. doi: 10.48550/arXiv.2511. 14544 2 [42] J. Ros, A. Arleo, and F. Paulovich. Enhanced force-scheme: A fast and accurate global dimensionality reduction method. Computers & Graphics, 135:104536, 2026. doi: 10.1016/j.cag.2026.104536 6 [43] J. Ros, A. Arleo, and F. Paulovich. Gap Index source code. https: //codeberg.org/jros/gap-index, 2026. 2, 5 [44] Y. Sadahiro. Cluster perception in the distribution of point objects. Carto-

graphica, 34(1):49–62, 1997. doi: 10.3138/Y308-2422-8615-1233 2 [45] J. W. Sammon. A nonlinear mapping for data structure analysis. IEEE Transactions on computers, 100(5):401–409, 1969. doi: 10.1109/T-C. 1969.222678 2 [46] R. Seidel. The upper bound theorem for polytopes: an easy proof of its asymptotic version. Computational Geometry, 5(2):115–116, Sept. 1995. doi: 10.1016/0925-7721(95)00013-Y 3 [47] M. Sips, B. Neubert, J. P. Lewis, and P. Hanrahan. Selecting good views of high-dimensional data using class consistency. Computer Graphics Forum, 28(3):831–838, 2009. doi: 10.1111/j.1467-8659.2009.01467.x 2 [48] K. Smelser, J. Miller, and S. Kobourov. “normalized stress” is not normalized: How to interpret stress correctly. In 2024 IEEE Evaluation and Beyond-Methodological Approaches for Visualization (BELIV), pp. 41–50. IEEE, 2024. doi: 10.1109/BELIV64461.2024.00010 1, 2, 5 [49] J. B. Tenenbaum, V. D. Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, Dec. 2000. doi: 10.1126/science.290.5500.2319 4 [50] W. S. Torgerson. Multidimensional scaling: I. theory and method. Psychometrika, 17(4):401–419, 1952. doi: 10.1007/BF02288916 2 [51] F. S. Tsai. A visualization metric for dimensionality reduction. Expert Systems with Applications, 39(2):1747–1752, Feb. 2012. doi: 10.1016/j. eswa.2011.08.080 4 [52] L. van der Maaten and G. Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9(86):2579–2605, 2008. 1 [53] J. Venna and S. Kaski. Local multidimensional scaling. Neural Networks, 19(6–7):889–899, July 2006. doi: 10.1016/j.neunet.2006.05.014 1, 2, 3, 5 [54] J. Venna, J. Peltonen, K. Nybo, H. Aidos, and S. Kaski. Information retrieval perspective to nonlinear dimensionality reduction for data visualization. Journal of Machine Learning Research, 11:451–490, Mar. 2010. doi: doi/10.5555/1756006.1756019 2 [55] Y. Wang, K. Feng, X. Chu, J. Zhang, C.-W. Fu, M. Sedlmair et al. A perception-driven approach to supervised dimensionality reduction for visualization. IEEE Transactions on Visualization and Computer Graphics, 24(5):1828–1840, 2018. doi: 10.1109/TVCG.2017.2701829 2 [56] C. Ware. Chapter six - static and moving patterns. In C. Ware, ed., Information Visualization (Third Edition), Interactive Technologies, pp. 179–237. Morgan Kaufmann, Boston, third edition ed., 2013. doi: 10. 1016/B978-0-12-381464-7.00006-5 1 [57] J. Warnking, M. Dojat, A. Guérin-Dugué, C. Delon-Martin, S. Olympieff, N. Richard et al. fMRI retinotopic mapping—step by step. NeuroImage, 17(4):1665–1683, 2002. doi: 10.1006/nimg.2002.1304 2 [58] M. Wattenberg, F. Viégas, and I. Johnson. How to use t-SNE effectively. Distill, 2016. doi: 10.23915/distill.00002 1, 5, 8