Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph

Source

• Source name: arXiv
• Source kind: paper
• Authors / organization: Duen Horng Chau, Donghao Ren, Fred Hohman, Dominik Moritz
• Venue: arXiv: cs.LG
• Published: 2026-07-09
• Collected: 2026-07-10
• URL: http://arxiv.org/abs/2607.08746v1
• PDF: https://arxiv.org/pdf/2607.08746v1
• DOI: UNKNOWN

Plain-Language Brief

The authors explore the potential of using the internal k-nearest-neighbor (kNN) graph constructed by UMAP, a popular tool for exploring high-dimensional data. They demonstrate that standard graph algorithms like PageRank, k-core decomposition, and clustering coefficient can enhance data sensemaking in this graph, providing insights that are competitive or complementary to purpose-built methods.

What the Document Says

• UMAP is a tool for exploring high-dimensional data, but its internal kNN graph is often overlooked. This graph encodes the data manifold in the original high-dimensional space before distortion by UMAP's 2D projection.
• Standard graph algorithms like PageRank, k-core decomposition, and clustering coefficient can be applied to this graph for data sensemaking.
• PageRank identifies representative data points, k-core decomposition reveals dense core regions versus sparse periphery, and clustering coefficient detects tight-knit neighborhoods with similar data points.
• These graph-based analyses are practical and competitive or complementary to purpose-built methods like k-medoids for exemplar selection and HDBSCAN for density-based clustering.
• The authors provide quantitative and qualitative evaluation on MNIST and Fashion MNIST datasets.

Key Concepts Mentioned

• UMAP
• k-nearest-neighbor (kNN) graph
• PageRank
• k-core decomposition
• clustering coefficient
• MNIST
• Fashion MNIST

Claims Made by the Document

• Standard graph algorithms can enhance data sensemaking on UMAP's kNN graph.
• These graph-based analyses are practical and competitive or complementary to purpose-built methods.

Evidence Used

• Demonstration of standard graph algorithms on UMAP's kNN graph
• Quantitative and qualitative evaluation on MNIST and Fashion MNIST

Methods / Approach

UNKNOWN

Limitations Stated by the Authors

UNKNOWN

Limitations Noted by the Agent

Agent interpretation — not from the source.

UNKNOWN

Open Questions

UNKNOWN

Notes for Future Q&A

May include interpretation. Labeled where it does.

UNKNOWN

Raw Abstract / Excerpt

While UMAP is widely used for exploring high-dimensional data, typical workflows focus on its lower-dimensional embedding, largely overlooking the rich k-nearest-neighbor (kNN) graph that UMAP constructs internally. This graph encodes the data manifold in its original high-dimensional space, before the distortion that UMAP's 2D projection introduces. We demonstrate the untapped potential of this internal representation, showing how standard graph algorithms applied to this graph enhance data sensemaking: (1) PageRank identifies representative data points, (2) k-core decomposition reveals dense core regions versus sparse periphery, and (3) clustering coefficient detects tight-knit neighborhoods with highly-similar data points. Through quantitative and qualitative evaluation on MNIST and Fashion MNIST, we show that these graph-based analyses are not only practical but also competitive with or complementary to purpose-built methods (e.g., k-medoids for exemplar selection, HDBSCAN for density-based clustering).