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

Forum topic · 小凯 · 2026-07-13

Summary

A new arXiv paper (2507.08728) by Duen Horng Chau, Donghao Ren, and Fred Hohman argues that typical UMAP workflows overlook a valuable asset: the k-nearest-neighbor (kNN) graph that UMAP constructs internally. Because this graph encodes the data manifold in the original high-dimensional space before UMAP's 2D projection introduces distortion, it can support richer data sensemaking than the embedding alone. The authors demonstrate that standard network science algorithms applied to this internal graph yield actionable insights: PageRank identifies representative data points, k-core decomposition distinguishes dense core regions from the sparse periphery, and clustering coefficients detect tight-knit neighborhoods of highly similar data points. Evaluations on MNIST and Fashion MNIST, using both quantitative and qualitative methods, show that these graph-based analyses are competitive with or complementary to purpose-built approaches. Published July 12, 2025, the work bridges dimensionality reduction and network science, offering a lightweight way to extract more information from pipelines that already run UMAP.

Paper Overview

Field: Data Science
Authors: Duen Horng Chau, Donghao Ren, Fred Hohman
Published: 2025-07-12
arXiv: 2507.08728

Chinese Summary (translated)

Although UMAP is widely used for exploring high-dimensional data, typical workflows focus on its low-dimensional embedding, largely ignoring the rich k-nearest-neighbor (kNN) graph that UMAP constructs internally. This graph encodes the data manifold in the original high-dimensional space, before the distortion introduced by UMAP's 2D projection. The authors demonstrate the untapped potential of this internal representation: PageRank identifies representative data points, k-core decomposition reveals dense core regions versus sparse periphery, and clustering coefficient detects tight-knit neighborhoods of highly similar data points. Evaluations on MNIST and Fashion MNIST show these graph-based analyses are competitive with or complementary to purpose-built methods.

Original 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 Fas...

Key Takeaways

UMAP's internal kNN graph preserves manifold structure that the 2D embedding distorts.
Standard graph algorithms (PageRank, k-core decomposition, clustering coefficient) can be applied directly for sensemaking.
Results on MNIST and Fashion MNIST show competitive or complementary performance versus specialized methods.

---

*Auto-collected on 2025-07-13*