UMAP's Hidden Graph: Treating the Discarded kNN Structure as First-Class Analysis

Paper: 2607.08746 Authors: Duen Horng Chau, Donghao Ren, Fred Hohman, Dominik Moritz Categories: cs.LG, cs.AI, cs.DS, cs.HC

The Gap

UMAP is one of the most popular dimensionality reduction tools in the modern ML toolkit. Everyone uses it the same way: throw high-dimensional data in, get a 2D scatterplot out, stare at it. But here’s the thing most practitioners don’t realize—UMAP internally constructs a k-nearest-neighbor graph that faithfully encodes the data manifold in the original high-dimensional space. This graph is the backbone of the whole algorithm, and the moment the 2D embedding appears, the graph is tossed in the trash.

The 2D projection introduces well-documented distortions: clusters can merge or split artificially, relative distances warp, and local neighborhoods get scrambled. Prior approaches to mitigate this (e.g., densMAP, parametric UMAP adjustments) focus on improving the projection itself. Meanwhile, purpose-built tools like HDBSCAN, k-medoids, or DBSCAN are used separately for density analysis, exemplar selection, and clustering—each requiring its own setup, parameters, and pipeline. Nobody thought to ask: what if we just use the graph UMAP already built?

                     UMAP builds kNN
                     graph internally
                            |
                            v
  Problem: Users only --> 2D embedding: projections distort
  look at the projection   distances, merge/split clusters
                            |
                            v
  Assumption: The kNN graph preserves manifold structure
  in the original high-D space, BEFORE distortion
                            |
                            v
  Method: Apply standard graph algorithms
  PageRank --> exemplar selection
  k-core   --> density core vs periphery
  clust.coef --> tight-knit neighborhoods
                            |
                            v
  Evidence: On MNIST and Fashion-MNIST,
  competitive with k-medoids, HDBSCAN,
  and other purpose-built methods
                            |
                            v
  Conclusion: The discarded graph is a rich,
  underexploited representation for sensemaking

The Increment

One sentence: Before this paper, UMAP’s kNN graph was invisible infrastructure; after this paper, it’s a free, ready-made analytical substrate that anyone already running UMAP can tap into with three lines of graph-algorithm code.

Core Mechanism

UMAP’s pipeline has two phases that are usually conflated. Phase one constructs a weighted kNN graph in the original high-dimensional space—each data point is connected to its k nearest neighbors, with edge weights reflecting local distance. Phase two optimizes a low-dimensional embedding to approximate the topology of that graph. This paper’s core move is to decouple the two: take the output of phase one (the graph) and treat it as a standalone analytical object.

The analysis applies three classic graph algorithms, each answering a different sensemaking question. PageRank, originally designed for ranking web pages, propagates “importance” through the graph: points connected to many well-connected points get high scores, surfacing representative exemplars. k-core decomposition peels away peripheral nodes layer by layer: the k-core is the maximal subgraph where every node has at least k neighbors within the subgraph, revealing the dense structural core. Clustering coefficient measures, for each node, the fraction of its neighbors that are also neighbors of each other—high values indicate tight-knit communities where data points are mutually similar.

  UMAP Pipeline (decoupled)
  ========================

  High-D Data  --->  [kNN Graph Builder]
                             |
                    +--------+--------+
                    |                 |
                    v                 v
           [Discard?]         [Analyze Graph]
             (old way)              |
                            +-------+-------+
                            |       |       |
                            v       v       v
                        PageRank  k-core  Clust.Coef
                            |       |       |
                            v       v       v
                        Exemplars Density Cohesion

Structural Metaphor: Think of a city’s road network.

When a cartographer draws a simplified tourist map of a sprawling city, they’re forced to distort distances—some neighborhoods get compressed, others stretched, and the map looks cleaner than reality. Most people only look at this tourist map (the 2D UMAP embedding). But the cartographer actually drove every road to make that map, and kept a detailed log of which buildings are connected to which via the shortest routes (the kNN graph). That road-network log is the real treasure.

• PageRank is like identifying the major intersections where the most traffic flows through—the city’s central hubs that represent the character of their surrounding area.
• k-core decomposition is like distinguishing the dense downtown core (where every block connects to many others) from the sprawling outer suburbs (where streets peter out into dead ends).
• Clustering coefficient is like finding the cozy village squares where every surrounding house is a neighbor of every other—a tight-knit community where everyone knows everyone.

Without this road network, you’re stuck interpreting a distorted map. With it, you understand the city’s actual structure.

Key Concepts

• k-Nearest Neighbor (kNN) Graph: Imagine you’re at a party with 500 people. For each person, you find the 15 people most similar to them (maybe by hobby, age, taste in music) and draw a line between them. That web of connections is a kNN graph. In UMAP, “similarity” is computed in the high-dimensional feature space. The graph doesn’t care about spatial layout—it only cares about *who is connected to whom. That’s why it survives the dimensional collapse into 2D.

• k-Core Decomposition: Start with the full graph. Remove every node that has fewer than k neighbors. Keep removing until no more such nodes exist. What remains is the k-core. Do this for increasing k, and you get a nested hierarchy: the 2-core is bigger and looser, the 10-core is smaller and denser. For data sensemaking, this tells you: “here’s the structural backbone of this dataset, and here’s the fluff on the edges.”

• Clustering Coefficient: Take a node. Look at its neighbors. Count how many pairs of those neighbors are also connected to each other. Divide by the total possible pairs. That fraction—between 0 and 1—is the clustering coefficient. A score of 1 means a perfect clique: everyone knows everyone. For data points, this means “this point lives in a neighborhood of highly mutual similarities”—a strong signal of a coherent local structure.

Framework Shift

Before (mainstream approach):
                                                    
  High-D Data --> UMAP --> 2D plot --> "look at it"
                                     
  Separately:  High-D Data --> HDBSCAN    --> clusters
                               k-medoids  --> exemplars
                               DBSCAN     --> density

After (this paper):

  High-D Data --> UMAP --> 2D plot  (visualization)
                       \-> kNN graph (structural analysis)
                                |
                          Graph algorithms
                          produce all three:
                          exemplars, density, cohesion

From “UMAP is a visualization tool” to “UMAP is a visualization tool AND a graph construction engine,” the core shift is recognizing that the graph UMAP builds is not a byproduct but a first-class analytical artifact.

Expert Assessment

Problem choice: This is a genuine observation hiding in plain sight. The UMAP kNN graph is almost universally ignored by practitioners, yet it encodes exactly the high-dimensional structure people are trying to understand. It’s not a grand theoretical gap, but it’s a practical blind spot with real consequences—people are building separate pipelines for clustering and exemplar selection when a free graph is already sitting in memory. The paper sits at the intersection of applied graph theory and practical ML tooling, which is a productive niche.

Method maturity: The insight is clever but the methods are not novel—PageRank is from 1998, k-core decomposition from the 1980s, clustering coefficient from Watts-Strogatz 1998. The contribution is the *application context, not the algorithms. One could argue this is more of a useful tutorial or position paper than a methods paper. There’s a simpler approach being overlooked: just running these algorithms and doing a proper user study to see if practitioners actually change their workflows.

Experimental integrity: The evaluation is on MNIST and Fashion-MNIST—clean, well-understood benchmarks that make everything look good. These are the “hello world” of evaluation datasets. The claim of being “competitive with or complementary to purpose-built methods” holds up on these benchmarks, but real-world datasets with noise, missing values, and ambiguous cluster structure would be a much stronger test. The baselines are fair (k-medoids for exemplars, HDBSCAN for clustering), but the paper doesn’t stress-test edge cases where the kNN graph might mislead (e.g., very high k, disconnected components, manifold holes).

Writing quality: The paper reads well and the motivation is clearly articulated. Where it cuts corners: the evaluation section could be significantly stronger. A deeper analysis of *when the graph-based approach fails, and a discussion of UMAP’s hyperparameter sensitivity (how does the kNN graph change with n_neighbors?), would elevate the whole piece. The related work could also better position itself against graph-based visualization literature (e.g., graph neural network projections, topology-based methods like MAPPER).

Verdict: weak accept — The observation is clean, actionable, and immediately useful to practitioners already using UMAP. But it leans heavily on existing algorithms rather than introducing new ones, and the evaluation is limited to toy datasets. It’s the kind of paper that earns citations from people who discover the trick and use it, rather than from people building on the methodology.

Takeaways

Three things a practitioner can steal right now:

1. Free exemplar selection: If you’re already running UMAP, call umap.graph_ (in the Python library) to get the kNN graph, then run PageRank on it. You get representative data points without training a separate k-medoids model. This works in a few lines of NetworkX code.

2. Density layering without clustering: k-core decomposition gives you a nested density hierarchy without choosing a clustering algorithm or its parameters. Use it to separate “core” data from “peripheral” or outlier-adjacent data before doing anything else.

3. The general principle: Whenever you use a tool that internally constructs a graph or tree (UMAP, hierarchical clustering, HDBSCAN), ask whether that internal structure has analytical value on its own. The intermediate representations that algorithms build are often richer than their final outputs.