🤖 machine learning

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

This paper introduces the Gap Index, a fast and interpretable quality metric for dimensionality reduction scatterplots that uniquely measures visual distortion in empty regions by comparing spatial deformations of empty triangles against their high-dimensional counterparts, addressing a key limitation of existing metrics that focus solely on point relationships.

Original authors: Jaume Ros, Alessio Arleo, Fernando Paulovich

Published 2026-07-31

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Jaume Ros, Alessio Arleo, Fernando Paulovich

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a cartographer trying to draw a map of a giant, invisible, multi-dimensional city on a flat piece of paper. This is the daily challenge of Dimensionality Reduction, a branch of data science where computers take complex, high-dimensional information (like thousands of features describing a single object) and squish it down into a simple 2D scatterplot so humans can actually see it. The goal is to keep the "neighborhoods" intact: if two points are close together in the high-dimensional city, they should stay close on your paper map. If they are far apart, they should stay far.

But here's the catch: you can't perfectly flatten a 3D sphere onto a 2D sheet without tearing or stretching it. Just like how a map of the world distorts the size of Greenland or the shape of Antarctica, these computer-generated maps inevitably warp the data. To trust what we see, scientists use "quality metrics"—mathematical rulers that measure how much the map has been distorted. For a long time, these rulers only checked the distance between the dots (the data points) themselves. They asked, "Are these two dots still neighbors?" But they largely ignored the empty white space between the dots. Yet, in visual analysis, that empty space is just as important as the dots; it's the silence between the notes that defines the music, the gaps that tell us where one group ends and another begins.

This paper introduces a new way to measure that distortion, called the Gap Index (GI). The authors, Jaume Ros, Alessio Arleo, and Fernando Paulovich, argue that the old rulers are missing the big picture. They found that standard metrics often give a "clean bill of health" to maps that look visually chaotic and misleading to the human eye. To fix this, they developed a method that treats the empty spaces on the map as the main characters. Instead of just measuring the dots, they slice the entire empty space between the dots into triangles and check if those triangles have been stretched or squashed compared to their original shape in the high-dimensional world.

The core finding is that the Gap Index is much more sensitive to visual tricks than previous tools. In their tests, they showed that a popular technique called t-SNE (which is great at separating clusters) can create fake-looking gaps and spurious patterns that look like distinct groups but are actually just artifacts of the math. Standard metrics like "stress" or "trustworthiness" barely noticed this, reporting the map as nearly perfect. The Gap Index, however, immediately flagged these empty areas as highly distorted, coloring them red to show where the map was stretched and blue where it was compressed. The authors suggest that by focusing on these "gaps," the GI provides a more honest report card for visual analysis, helping users spot when a pretty picture is actually hiding a distorted reality. They also showed that this new metric is fast to compute, working efficiently even on large datasets, and can be overlaid directly onto the scatterplot to give a heat-map style view of exactly where the distortion is happening.

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

Problem Statement
Dimensionality Reduction (DR) is essential for visualizing high-dimensional data, yet all projections entail distortion unless the data lies on a 2D manifold. While quality metrics exist to quantify this distortion, current popular metrics (e.g., stress, trustworthiness, continuity) primarily focus on the preservation of relationships between data points, such as pairwise distances or neighborhoods. These metrics often fail to capture distortions in the "empty regions" or gaps between points. However, these empty spaces are visually critical; they define the separation between clusters and the overall structure perceived by users. Consequently, metrics may report high quality (low distortion) even when a projection creates spurious patterns or misleading separations in the empty space, leading to overconfidence in visual analysis.

Methodology: The Gap Index (GI)
The authors introduce the Gap Index (GI), a quality metric designed to quantify distortion specifically within the empty areas of a 2D projection. The GI operates by decomposing the visual space into triangles and comparing their deformation against the high-dimensional space. The computation follows a modular pipeline:

Triangulation: The 2D projection is partitioned into a set of non-overlapping triangles using Delaunay triangulation. This method is chosen for its computational efficiency ( $O(N \log N)$ ), its ability to cover the convex hull of the data, and its property of avoiding thin, numerically unstable triangles.
Triangle Deformation: For each triangle $t_i$ $t_{i}$ in the 2D projection, the corresponding triangle $\hat{t}_i$ $\hat{t}_{i}$ is identified in the high-dimensional space using the same three vertices. The deformation is calculated by comparing the relative areas of these triangles.
- Relative area is defined as the triangle's area divided by the sum of all triangle areas in the respective space. This normalization ensures the metric is scale-invariant.
- The deformation value $D(t_i, \hat{t}_i)$ is computed as the difference between the relative areas, normalized by the maximum of the two. This yields a value in $[-1, 1]$ , where positive values indicate stretching (the gap is larger in 2D than in high-D) and negative values indicate compression.
- Crucially, the area of the high-dimensional triangle can be computed using only pairwise distances (via Heron's formula), meaning the GI does not require explicit high-dimensional coordinates, only a distance matrix.
Aggregation: To produce a single scalar metric, the GI aggregates the absolute deformation values of all triangles using a weighted average. The weight $w_i$ for each triangle is the maximum of its relative area in the 2D space or the high-dimensional space. This ensures that large, visually salient gaps (whether in the projection or the original data) have a greater influence on the final score.
Visualization: The GI can be overlaid on the scatterplot by coloring the triangles according to their deformation values. A divergent color map (blue for compression, red for stretching, yellow for no distortion) visualizes regional distortion. To mitigate visual noise from triangle boundaries, the authors propose applying a Gaussian blur to the background.

Key Contributions

Identification of Limitations: The paper highlights that standard quality metrics are insensitive to structural deformations in empty regions that have high visual impact, potentially misleading analysts.
Novel Metric Proposal: The authors introduce the Gap Index, a metric that shifts the focus from point-to-point relationships to the distortion of the empty spaces (gaps) between points.
Benchmarking and Implementation: The paper provides a collection of artificial and real datasets to benchmark the GI against popular metrics (stress, trustworthiness, continuity, steadiness, cohesiveness). An open-source Python implementation is provided to reproduce the results.

Results
The evaluation demonstrates that the GI is sensitive to distortions that other metrics miss:

Sensitivity to Visual Artifacts: In the "plane dataset" experiment (points randomly distributed on a 2D plane embedded in 3D), PCA produces a perfect projection (GI = 0), while t-SNE creates spurious cluster-like gaps. While stress and trustworthiness report minimal distortion for t-SNE, the GI correctly identifies the significant visual distortion caused by the artificial gaps.
Interpretability: In synthetic datasets (e.g., a 3D cube with a missing face), the GI visualization clearly highlights where empty space has been stretched or compressed, allowing users to infer the original high-dimensional structure (e.g., identifying that a large red area in the projection corresponds to a missing face in the 3D object).
Performance: The GI is computationally efficient, dominated by the $O(N \log N)$ complexity of the Delaunay triangulation, making it suitable for large datasets.

Significance and Claims
The paper claims that the Gap Index offers a necessary complement to existing quality metrics by addressing a blind spot in visual analysis: the reliability of empty regions. By focusing on the gaps that define clusters and patterns, the GI provides a more holistic view of projection quality that aligns better with human perception. The authors assert that the GI is fast to compute, interpretable, and capable of detecting small structural deformations that have high visual impact, which are often overlooked by point-centric metrics. The work revisits and extends previous concepts of triangulating projections, formalizing them into a normalized, aggregated quality metric suitable for both scalar evaluation and regional visualization.

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

More like this