The Projection Becomes the Hidden Graph

From Scatter Plot to Evidence Layer

The paper is Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph, arXiv:2607.08746 [cs.LG]. The arXiv record lists Duen Horng Chau, Donghao Ren, Fred Hohman, and Dominik Moritz as authors, with submission on July 9, 2026 and cross-listings in cs.AI, cs.DS, and cs.HC. The arXiv HTML version lists Apple affiliations, and the arXiv comment points to an Embedding Atlas code and demo page.

Before UMAP gives us a two-dimensional picture, it constructs a weighted directed k-nearest-neighbor graph in the original high-dimensional space. That graph encodes local manifold structure before the layout algorithm compresses, bends, and overlaps it for display. The paper argues that the graph should not be discarded as plumbing.

This matters for the Church's usual concern with interfaces that become facts. A scatter plot of embeddings can be used to inspect a dataset, audit a model family, cluster user behavior, or decide which examples deserve human review. If only the picture travels into the meeting deck, the evidence has already been flattened. The issue sits next to embedding-world interfaces, outlier labor forecasts, and visual default priors.

What the Paper Recovers

The authors apply ordinary graph algorithms to UMAP's internal kNN graph instead of only analyzing the final projection. Their framing is practical rather than mystical. PageRank identifies representative points. k-core decomposition separates dense core regions from sparse peripheries. Clustering coefficient finds tight local neighborhoods whose neighbors are also mutually connected.

Those are three different questions. Which examples should stand for the dataset? Which regions are central rather than marginal? Which local pockets are unusually cohesive? A two-dimensional plot can gesture toward those answers, but the graph gives auditable measures.

The paper also makes implementation less exotic than it first sounds. It reuses the kNN arrays that UMAP already computes: neighbor indices and raw distances. PageRank uses UMAP-style membership strengths as edge weights. k-core and clustering coefficient use the unweighted directed graph. The reported complexity is O(nkT), O(nk), and O(nk^2), respectively.

Three Questions for the Graph

PageRank is the exemplar question. The paper reports that PageRank-selected points have stronger class-balance behavior than k-medoids in the evaluated setting and remain competitive or complementary on representativeness and downstream classification checks. The governance reading is not that PageRank is the new universal curator. It is that exemplar selection should name the graph, weights, parameter k, baseline, and downstream test.

k-core is the center-periphery question. The authors compute coreness by in-degree because every node in the UMAP graph has exactly k outgoing edges. In the MNIST run with k=15, coreness ranges from 0 to 8; about 65 percent of points sit in middle shells 4 to 6, while about 3 percent are peripheral. On Fashion MNIST, the paper reports 18 percent in the outermost shell. HDBSCAN tells a different story: nearly all points receive cluster labels with less than 1 percent noise, and membership probabilities are nearly uniform across coreness shells, with Spearman correlations near zero in the reported comparisons. In the authors' terms, the methods answer different questions: which group versus where in the group.

Clustering coefficient is the micro-neighborhood question. The paper reports that the top 5 percent of points by clustering coefficient have mean neighborhood label purity of 0.98 on MNIST and 0.94 on Fashion MNIST, compared with random same-size samples of 0.90 plus or minus 0.004 and 0.84 plus or minus 0.005 over 100 runs. The strongest-looking cluster may be too coarse, while a small local knot may be the better inspection unit.

What the Results Change

The paper's runtime evidence also changes the default excuse. On MNIST with 60,000 points and k=15, the authors report 0.8 seconds for PageRank, 0.6 seconds for k-core, and 0.7 seconds for clustering coefficient on a MacBook Pro with an M4 Max and 64 GB RAM. Re-deriving membership strengths adds 0.9 seconds. For this benchmark class, keeping the hidden graph is not an expensive ritual.

The stronger institutional point is that the graph can be reviewed independently of the layout. A reviewer can ask whether high-PageRank examples overrepresent a class, whether peripheral points are being dismissed as noise, whether cohesive micro-neighborhoods reveal duplicates, and whether a projected cluster survives when the graph metric changes.

Limits and Governance

The limits are real. The evaluation centers on MNIST and Fashion MNIST. Those benchmarks are not the same as messy production embeddings, multimodal surveillance features, clinical records, customer-service logs, or social graphs. The authors name future domains such as single-cell genomics and audio, which should be tested rather than assumed.

There is also a communications risk. Graph scores can become ornamental certainty if exported without context. A core number, PageRank value, or clustering coefficient is not a moral status. It is a measurement under a selected preprocessing pipeline, metric, UMAP configuration, neighborhood size, graph construction rule, and algorithm implementation.

So the institutional rule should be narrow: when a UMAP projection is used to justify a decision or prioritize review, preserve the pre-projection graph and expose the graph-derived alternatives. Do not let the picture become the only memory of the analysis.

The Receipt

A projection receipt should name the source embeddings, data exclusions, preprocessing, distance metric, UMAP version, n_neighbors or k, min_dist, random seed, internal neighbor indices, raw distances, membership-strength computation, graph directionality, graph algorithm, score version, selected exemplars, core-shell thresholds, clustering-coefficient thresholds, HDBSCAN or k-medoids comparison, benchmark split, hardware, software, reviewer notes, and any human decision made from the plot.

The Spiralist reading is simple: the scatter plot is not the dataset's face. It is the visible skin of a graph we are usually throwing away.

Sources

• Duen Horng Chau, Donghao Ren, Fred Hohman, and Dominik Moritz, Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph, arXiv:2607.08746 [cs.LG], submitted July 9, 2026.
• arXiv experimental HTML for Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph, checked for abstract, affiliations, graph construction, PageRank, k-core decomposition, clustering coefficient, MNIST and Fashion MNIST evaluation, implementation cost, discussion, and limitations.
• arXiv API record for arXiv:2607.08746, checked for title, authors, subject categories, submission date, code/demo comment, and version metadata.
• Embedding Atlas demo, checked as the code/demo URL named in the arXiv record.

Return to Blog