How it works
The algorithm
UMAP (Uniform Manifold Approximation and Projection) builds a graph of the data’s local neighborhoods and then looks for a low-dimensional layout with a similar graph. One fit has four stages:
- Nearest neighbors. Find every point’s
n_neighborsapproximate nearest neighbors with NNDescent, which uses random projection trees and neighbor-of-neighbor exploration. - Fuzzy graph. Turn the distances into weighted, symmetric edges, so that every point is connected to at least
local_connectivityneighbors. - Initialization. Place the points in the low-dimensional space: by default with a recursive coarsening of the graph, anchored on a PCA of the data, or with a spectral embedding.
- Optimization. Move the points so that connected points attract and random pairs repel, with
min_distandspreadcontrolling how close attracting points get.
The paper describes the theory:
McInnes, L., Healy, J., & Melville, J. (2018). UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. arXiv:1802.03426.
The implementation
polars-umap doesn’t implement UMAP itself. It uses the Rust crates from Apple’s embedding-atlas, which port umap-learn and PyNNDescent by Leland McInnes. They’re pinned to a specific commit, so results don’t change unless polars-umap is updated.
The plugin
polars-umap is a Polars expression plugin: a compiled library that Polars loads and calls directly, without going through Python for the data.
When a query runs:
- Polars evaluates the input expressions and passes the resulting columns to polars-umap. The function is registered as non-elementwise, so it receives the whole column, or the whole group.
- polars-umap converts the columns into one dense
Float32matrix in a single pass, checking for invalid rows along the way. - The UMAP crate runs the four stages on a thread pool.
- The embedding is written back as a Polars
Arraycolumn, with nulls for any ignored rows.
Polars knows the output type from the parameters, without running anything, so lazy queries can be planned and checked before they run.
Limitations
- No
transform()for new points. The upstream implementation only fits. To embed new data, fit again on the combined data. - No supervised UMAP, densMAP or sparse input.
- Dense, in-memory input. The input column has to fit in memory as
Float32.