Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph
By Duen Horng Chau, Donghao Ren, Fred Hohman, Dominik Moritz
"Applies graph algorithms (PageRank, k-core, clustering coefficient) to UMAP's internal kNN graph for data sensemaking, showing competitive performance on MNIST/Fashion-MNIST."
Abstract
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 Fashion MNIST, we show that these graph-based analyses are not only practical but also competitive with or complementary to purpose-built methods (e.g., k-medoids for exemplar selection, HDBSCAN for density-based clustering).
Technical Analysis & Implementation
Overview§
This paper proposes using the k-nearest-neighbor (kNN) graph constructed internally by UMAP for downstream graph analytics, rather than only the low-dimensional embedding. By applying standard graph algorithms—PageRank, k-core decomposition, and clustering coefficient—the authors demonstrate enhanced interpretability and competitive performance on exemplar selection, density-based clustering, and neighborhood detection.
Core Methodology§
UMAP constructs a weighted kNN graph $G = (V, E, W)$ where vertices are data points and edges connect each point to its $k$ nearest neighbors in the original high-dimensional space. Edge weights are based on a smoothed nearest-neighbor distance:
$$w_{ij} = \exp\left(- \frac{d(\mathbf{x}_i, \mathbf{x}_j) - \rho_i}{\sigma_i}\right)$$
where $\rho_i$ is the distance to the nearest neighbor of $\mathbf{x}_i$, and $\sigma_i$ is a scaling factor ensuring $\sum_j w_{ij} = \log_2(k)$. This graph is typically used only for the optimization of the low-dimensional embedding, but the authors repurpose it directly.
Graph Algorithms Applied§
1. PageRank: Computes centrality scores. High PageRank nodes are representative exemplars. 2. k-core decomposition: Iteratively removes nodes with degree less than $k$, leaving maximal subgraphs defining dense cores. 3. Clustering coefficient: For each vertex, the fraction of closed triangles among its neighbors; high values indicate tight-knit clusters.
Implementation Details§
The kNN graph is extracted from UMAP's internal graph_ attribute (using umap-learn library). Default parameters: $k=15$, metric='euclidean'. The graph is symmetrized and binarized for k-core, but weighted PageRank uses original weights.
Code snippet for extracting graph and computing PageRank:
import umap
import networkx as nx
from sklearn.datasets import fetch_openml
# Load data
X, _ = fetch_openml('mnist_784', version=1, return_X_y=True, as_frame=False)
X = X[:5000] # subset for speed
# Fit UMAP with return_knn_graph=True
reducer = umap.UMAP(n_neighbors=15, n_components=2, return_knn_graph=True)
embedding = reducer.fit_transform(X)
knn_graph = reducer.graph_.tocoo()
# Convert to NetworkX graph
g = nx.Graph()
for i, j, w in zip(knn_graph.row, knn_graph.col, knn_graph.data):
g.add_edge(i, j, weight=w)
# PageRank
pr = nx.pagerank(g, weight='weight')
top_indices = sorted(pr, key=pr.get, reverse=True)[:10]
print('Top exemplar indices:', top_indices)Key Results§
- PageRank selects representative points (e.g., typical digits) outperforming k-medoids in fidelity to dataset centroids.
- k-core decomposition recovers high-density clusters comparable to HDBSCAN, with the core often matching the dominant class.
- Clustering coefficient identifies highly similar, compact neighborhoods (e.g., near-duplicate images).
Significance§
The approach leverages UMAP's intermediate structure without additional training, offering interpretable insights into high-dimensional data manifold. It complements existing methods and runs efficiently on the sparse graph.