Applying graph algorithms to UMAP's internal kNN graph enhances data sensemaking

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.

The authors demonstrate how standard graph algorithms applied to this internal representation enhance data sensemaking:

• PageRank identifies representative data points.
• k-core decomposition reveals dense core regions versus sparse periphery.
• Clustering coefficient detects tight-knit neighborhoods with highly-similar data points.

Through quantitative and qualitative evaluation on MNIST and Fashion MNIST, the study shows that these graph-based analyses are not only practical but also competitive with or complementary to purpose-built methods like k-medoids for exemplar selection and HDBSCAN for density-based clustering.