🤖 machine learning

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

This paper demonstrates that applying standard graph algorithms, such as PageRank, k-core decomposition, and clustering coefficient analysis, to the internal k-nearest-neighbor graph constructed by UMAP provides a powerful, complementary approach for high-dimensional data sensemaking that often matches or surpasses purpose-built methods.

Original authors: Duen Horng Chau, Donghao Ren, Fred Hohman, Dominik Moritz

Published 2026-07-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Duen Horng Chau, Donghao Ren, Fred Hohman, Dominik Moritz

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, messy box of 60,000 photos—some are handwritten numbers, others are pictures of clothes like bags, shirts, and shoes. You want to see the patterns, so you use a super-smart tool called UMAP to squish this 3D (or even higher-dimensional) chaos down onto a flat 2D piece of paper.

Usually, people stop right there. They look at the pretty 2D scatter plot, squint at the dots, and say, "Okay, I see a cluster of bags here." But this paper argues that UMAP is actually throwing away its best secret weapon the moment it draws that picture.

Before UMAP squishes the data onto the paper, it builds a hidden kNN graph. Think of this graph as a massive, invisible web of friendships. In this web, every photo has exactly 15 friends (its "k-nearest neighbors") that it thinks are most similar to it. But here's the twist: while every photo chooses 15 friends, not every photo gets chosen by 15 others. Some photos are so weird or unique that almost no one picks them as a friend. Others are so "average" or "prototypical" that hundreds of other photos nominate them as their best match.

The authors say: "Don't throw away this web! It's actually more honest than the 2D picture." They tested three cool ways to play with this web to understand the data better than the 2D picture ever could.

1. The "Most Popular Kid" (PageRank)

The Question: Which photos are the true "representatives" of their group?
The Old Way: People usually pick the photo closest to the center of a blob on the 2D map. But the 2D map is distorted! A stretched-out blob might have a "center" that doesn't actually look like a real photo.
The New Way: The authors used an algorithm called PageRank (the same one Google used to rank websites). In this web, a photo gets a high score not just because many people picked it, but because other popular photos picked it.
The Result:

The top-scoring photos looked like the perfect, textbook examples of a class (like a classic "6" or a standard messenger bag).
The lowest-scoring photos were the weird, atypical ones.
The Proof: When they picked 200 top photos to represent the whole dataset, these PageRank picks were way better at balancing the classes than the old method (k-medoids). The old method kept picking too many photos from the messy, spread-out groups, while PageRank picked a fair mix.
How sure are they? Very. They ran this on 60,000 images and found the results were stable even when they changed the number of friends from 5 to 100. The rankings stayed almost the same (correlation around 0.95).

2. The "Core vs. The Edge" (k-Core Decomposition)

The Question: Which photos are the "heart" of a group, and which are just hanging out on the fringes?
The Old Way: Tools like HDBSCAN give you a simple label: "This is a bag." But it doesn't tell you if that bag is a classic bag or a weird, fuzzy bag that barely fits the definition.
The New Way: The authors used k-core decomposition. Imagine peeling an onion. You keep removing the photos that have the fewest incoming nominations (the least popular ones). The ones left at the very center are the "core."
The Result:

They found that the "core" photos were the most self-similar and consistent. For example, in the "1" category of handwritten numbers, the core was only perfect "1"s.
In the "bag" category, the core revealed distinct sub-groups: messenger bags, waist packs, and heavy textures. The 2D map just showed a big, blurry blob of "bags," but the graph peeled it open to show the layers.
The Proof: They compared this to HDBSCAN. HDBSCAN was great at saying "Is this a bag?" but terrible at saying "How central is this bag?" The graph method gave a graduated scale of "coreness" that the old tools missed.

3. The "Secret Club" (Clustering Coefficient)

The Question: Are there tiny, super-tight groups of photos that look exactly like each other?
The Old Way: Looking at the 2D map, a group of "6"s might look like one big, solid mass.
The New Way: The Clustering Coefficient looks for "triangles" in the web. If Photo A thinks Photo B is a friend, and Photo B thinks Photo C is a friend, does Photo A also think Photo C is a friend? If yes, that's a tight-knit clique.
The Result:

This method found "micro-neighborhoods" of photos that shared very specific styles. For the number "6," it isolated groups based on tiny details: some had a big loop, some were tilted, some had a specific curve.
The Proof: The top 5% of photos with the highest "clique-ness" had a 98% purity rate (meaning almost all their neighbors were the same type). This is much higher than picking random photos.

The Bottom Line

The paper doesn't say the 2D picture is useless. It just says it's incomplete. By keeping the hidden web of friendships (the kNN graph) and running these standard graph algorithms on it, you get a much clearer, more honest view of your data.

How confident are they?
They tested this on two massive, standard datasets (MNIST and Fashion MNIST) with 60,000 images each. The results were fast (running in under a second on a laptop) and the math held up against the best existing tools. They suggest this approach works for other similar tools too, but they only proved it on these specific image sets. They aren't claiming it solves every data problem, but they are pretty sure it's a much better way to "sensemake" than just staring at the 2D dots.

Technical Summary: Dimensionality Reduction Meets Network Science

Problem Statement

While UMAP is a dominant tool for visualizing high-dimensional data, standard analytical workflows typically treat the resulting 2D scatter plot as the sole artifact of interest. This approach discards the rich, intermediate k-nearest-neighbor (kNN) graph that UMAP constructs internally before projection. The authors argue that this graph encodes the data manifold's local geometry and connectivity in the original high-dimensional space more faithfully than the 2D layout, which inevitably introduces distortion. By ignoring this graph, analysts miss opportunities to perform sensemaking tasks—such as identifying representative points, analyzing density hierarchies, and detecting local cohesion—that are obscured in the 2D projection.

Methodology

The paper proposes elevating UMAP's internal kNN graph to a "first-class analytical resource" by applying standard network science algorithms directly to it, rather than to the 2D embedding. The methodology leverages the graph's specific structural properties: fixed out-degree $k$ , variable in-degree, and density-adaptive edge weights. Three specific algorithms are applied:

PageRank for Representative Selection:
- Mechanism: Instead of selecting exemplars based on geometric centroids in the distorted 2D space (which may fall in unrepresentative regions), the authors apply PageRank to the kNN graph.
- Logic: A node's score is amplified transitive-ly; a point ranks highly not just because many nodes point to it (high in-degree), but because those pointing nodes are themselves highly ranked. This identifies globally representative points that serve as "authorities" in the manifold.
- Implementation: Edge weights are derived from UMAP's density-adaptive membership strengths.
k-Core Decomposition for Density Hierarchy:
- Mechanism: The authors apply k-core decomposition to the graph to distinguish dense core regions from sparse peripheries.
- Logic: Unlike standard degree-based decomposition, which is limited by the fixed out-degree $k$ , this method decomposes based on in-degree alone. This produces a "coreness" score (0, 1, 2...) indicating how deeply embedded a node is within progressively denser, more interconnected subgraphs.
- Goal: To reveal graduated subgraph hierarchies and sub-categories within clusters that discrete clustering labels (e.g., from HDBSCAN) cannot capture.
Clustering Coefficient for Local Cohesion:
- Mechanism: The clustering coefficient (CC) is calculated for each node to measure the fraction of its neighbors that are also connected to each other.
- Logic: High CC indicates "tight-knit" micro-neighborhoods where points mutually consider each other as nearest neighbors.
- Goal: To detect semantically coherent micro-clusters (e.g., specific handwriting styles) that may appear as a monolithic mass in a 2D projection.

Key Contributions

The paper makes two primary contributions:

Conceptual Shift: It bridges dimensionality reduction and network science by treating UMAP's discarded kNN graph as a primary resource. This enables sensemaking that is complementary to 2D scatter plots, specifically addressing representativeness, density structure, and local cohesion.
Empirical Validation: Through quantitative and qualitative evaluations on MNIST and Fashion MNIST, the authors demonstrate that these graph-based methods are competitive with or superior to purpose-built methods:
- PageRank vs. k-medoids: PageRank-selected points achieve superior class balance (lower Jensen-Shannon divergence) compared to k-medoids, which tends to over-select from high-variance classes. While k-medoids slightly outperforms PageRank in representativeness at very small budgets, PageRank catches up rapidly and remains competitive in downstream SVM classification accuracy. Crucially, PageRank requires only a single global ranking computation, whereas k-medoids must be re-run for every budget size.
- k-Core vs. HDBSCAN: While HDBSCAN assigns discrete cluster labels, k-core decomposition reveals a graduated hierarchy of centrality within clusters. HDBSCAN membership probabilities showed near-zero correlation with coreness, confirming they answer different questions (group membership vs. position within the group).
- Clustering Coefficient: CC identifies distinct micro-neighborhoods (e.g., specific styles of the digit "6") that are topologically cohesive but may be visually indistinguishable in 2D.

Results

Stability: PageRank rankings are highly stable across a 20x range of neighborhood sizes ( $k=5$ to $100$), with mean Spearman rank correlations of ~0.95, indicating the selected representatives are not artifacts of a specific $k$ value.
Performance:
- Representativeness: PageRank rivals k-medoids in mean cosine distance to nearest representatives, especially as the selection budget increases.
- Class Balance: PageRank significantly outperforms k-medoids in maintaining the global class distribution (lower JSD), particularly at budgets $s \ge 200$ .
- Downstream Utility: SVM classifiers trained on PageRank-selected exemplars achieve accuracy within 2–3 percentage points of k-medoids on Fashion MNIST and are comparable on MNIST.
- Structural Insight: k-core decomposition successfully isolates sub-categories (e.g., messenger bags vs. waist packs within the "bag" class) by filtering for specific coreness thresholds. High CC values isolate consistent handwriting styles within the digit "6" cluster.

Significance and Claims

The authors claim that their work demonstrates the untapped potential of UMAP's internal representation. By retaining and analyzing the kNN graph, analysts can access structural information (centrality, connectivity hierarchy, local cohesion) that is lost or distorted in the 2D projection.

The paper positions these graph algorithms not as replacements for existing tools but as complementary methods that offer distinct advantages:

They provide a parameter-free (or stable) way to select representatives without optimizing a distance objective.
They offer a continuous hierarchy of density (via k-core) rather than discrete cluster assignments.
They are computationally efficient, running in under 1 second on 60,000 points by reusing UMAP's precomputed neighbor arrays.

The authors conclude that this perspective encourages the community to "look beyond the scatter plot and into the graph that made it," suggesting that this approach naturally extends to other dimensionality reduction methods that construct kNN graphs (e.g., TriMap, PaCMAP).