Principle:Rapidsai Cuml UMAP Development Tooling

Knowledge Sources	McInnes et al. 2018 - UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction cuML UMAP Documentation
Domains	Machine_Learning, Software_Engineering, Manifold_Learning
Last Updated	2026-02-08 12:00 GMT

Overview

UMAP development tooling provides debugging runners, quality metrics computation, and web-based visualization for comparing GPU-accelerated UMAP implementations against reference implementations, enabling systematic identification and diagnosis of numerical or algorithmic discrepancies.

Description

UMAP (Uniform Manifold Approximation and Projection) is a complex manifold learning algorithm with multiple interdependent stages: k-nearest neighbor graph construction, fuzzy simplicial set computation, spectral initialization, and stochastic gradient descent embedding. When implementing a GPU-accelerated version, subtle numerical differences at any stage can cascade into significantly different final embeddings. Development tooling addresses this challenge by providing infrastructure for stage-by-stage comparison and quality assessment.

Debug Runner: The debug runner executes the UMAP pipeline in a decomposed, stage-by-stage fashion for both the reference (CPU) implementation and the GPU implementation. At each stage, intermediate results are captured and compared:

1. KNN Graph Construction: Builds k-nearest neighbor graphs using both cuVS (GPU) and the reference UMAP nearest neighbor search, then compares the resulting neighbor indices and distances.
2. Fuzzy Simplicial Set: Computes the weighted graph from KNN results using both implementations and compares the resulting sparse matrices.
3. Spectral Initialization: Computes the initial low-dimensional layout via spectral embedding and compares initializations.
4. Simplicial Set Embedding: Runs the SGD optimization from the same initialization and compares final embeddings.

The runner accepts configurable parameters (number of neighbors, number of epochs, learning rate, minimum distance, metric) and processes multiple toy datasets (blobs, Swiss roll, circles, moons, digits, random data) to cover different data geometries.

Metrics Evaluation: A suite of quantitative metrics assesses the quality of each UMAP stage:

• KNN Metrics: Average neighbor recall (fraction of shared neighbors between two KNN graphs) and mean absolute distance error between corresponding neighbor distances.
• Fuzzy Simplicial Set Metrics: Jaccard similarity of non-zero entries, mean absolute difference of edge weights, Frobenius norm of the difference matrix, and trustworthiness score of the weighted graph.
• Embedding Metrics: Trustworthiness (how well local neighborhoods are preserved), Procrustes alignment error (rigid alignment followed by residual measurement), geodesic distance correlation (Pearson and Spearman correlation between graph distances in high-dimensional and low-dimensional spaces).

Web Results Visualization: An HTML report generator creates interactive web pages using Plotly for visual inspection of results. The report includes:

• Scatter plots of original data (PCA-projected to 2D), spectral initializations, and final embeddings.
• Side-by-side comparison panels when both reference and GPU results are available.
• Tabulated metric summaries for each dataset and stage.

Usage

UMAP development tooling is used when:

• Developing or modifying the GPU UMAP implementation and needing to verify correctness against the reference.
• Diagnosing quality regressions after code changes by isolating which pipeline stage introduced the discrepancy.
• Evaluating the impact of algorithmic changes (e.g., different KNN algorithms, initialization strategies) on embedding quality.
• Generating visual reports for code review or documentation of implementation fidelity.
• Benchmarking GPU vs. CPU UMAP across different dataset characteristics.

Theoretical Basis

Trustworthiness:

$T(k)=1-\frac{2}{nk(2n-3k-1)}\sum _{i=1}^n\sum _{j\in U_k(i)}(r(i,j)-k)$

where $U_k(i)$ is the set of points that are in the k-nearest neighbors in the low-dimensional embedding but not in the high-dimensional space, and $r(i,j)$ is the rank of point $j$ among the neighbors of $i$ in the high-dimensional space.

Procrustes Alignment Error:

1. Center both embeddings: E_a = E_a - mean(E_a), E_b = E_b - mean(E_b)
2. Scale to unit variance
3. Find optimal rotation: R = argmin_R ||E_a - E_b * R||_F
   via SVD of E_a^T E_b = U S V^T, R = V U^T
4. Error = ||E_a - E_b * R||_F

KNN Recall:

$\text{recall}(k)=\frac{1}{n}\sum _{i=1}^n\frac{|N_k^A(i)\cap N_k^B(i)|}{k}$

where $N_k^A(i)$ and $N_k^B(i)$ are the k-nearest neighbor sets from implementations A and B.

Geodesic Distance Correlation: The Pearson and Spearman correlations between pairwise shortest-path distances in the high-dimensional KNN graph and Euclidean distances in the low-dimensional embedding measure how well the global structure is preserved.

Related Pages

Implemented By

• Implementation:Rapidsai_Cuml_UMAP_Debug_Runner
• Implementation:Rapidsai_Cuml_UMAP_Metrics
• Implementation:Rapidsai_Cuml_UMAP_Web_Results