UMAP is a popular dimensionality reduction technique, but most users only examine its 2D projection, ignoring the k-nearest-neighbor (kNN) graph the algorithm builds as an intermediate step. This graph represents the data manifold in the original high-dimensional space, before the distortion introduced by the 2D embedding. The authors argue that applying standard graph algorithms to this internal kNN graph reveals valuable structure that is lost in the final projection.

Three algorithms are demonstrated. PageRank identifies representative or central data points, functioning similarly to k-medoids for exemplar selection. k-core decomposition separates dense core regions from sparse peripheral points, offering a density-based view analogous to HDBSCAN. The clustering coefficient detects tight-knit neighborhoods of highly similar points, revealing local structure. The authors evaluate these methods on MNIST and Fashion MNIST, showing that they are competitive with purpose-built techniques and sometimes provide complementary insights. For instance, on the raw pixel space of MNIST, PageRank‘s top exemplars capture class-typical digits, and the k-core membership correlates with how prototypical an image is.

The paper positions this as a practical augmentation to the UMAP workflow. Because the kNN graph is already computed during UMAP‘s run, applying these algorithms adds minimal overhead and no new distance calculations. The authors also discuss limitations: the graph is sensitive to the choice of k (neighborhood size), and the analyses inherit any biases in the underlying kNN construction, such as the curse of dimensionality for very high-dimensional sparse data.