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 of the paper 'Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph', published in 2026, discuss a new approach to utilizing the internal k-nearest-neighbor (kNN) graph constructed by UMAP, which is often overlooked during typical workflows. This graph preserves the data manifold in its high-dimensional space before distortion caused by UMAP's 2D projection. The authors demonstrate that applying standard graph algorithms like PageRank, k-core decomposition, and clustering coefficient analysis to this graph can enhance data understanding and even compete with or complement purpose-built methods.

What the Document Says

• The internal kNN graph constructed by UMAP is often overlooked during typical workflows.
• This graph encodes the data manifold in its original high-dimensional space before distortion caused by UMAP's 2D projection.
• Standard graph algorithms (PageRank, k-core decomposition, clustering coefficient) applied to this graph enhance data sensemaking.
• These graph-based analyses are practical and competitive with or complementary to purpose-built methods for exemplar selection, density-based clustering etc.
• The authors demonstrate these findings on MNIST and Fashion MNIST datasets.

Key Concepts Mentioned

• UMAP
• k-nearest-neighbor (kNN) graph
• data manifold
• PageRank
• k-core decomposition
• clustering coefficient
• exemplar selection
• density-based clustering

Claims Made by the Document

• The internal kNN graph constructed by UMAP encodes the data manifold in its original high-dimensional space before distortion.
• Standard graph algorithms applied to this graph enhance data sensemaking.
• These graph-based analyses are practical and competitive with or complementary to purpose-built methods.

Evidence Used

• The authors demonstrate these findings on MNIST and Fashion MNIST datasets.

Methods / Approach

• Standard graph algorithms (PageRank, k-core decomposition, clustering coefficient)

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).