The first thing UMAP does is find every point’s nearest neighbors. polars-umap exposes that step on its own: a Rust port of PyNNDescent, the approximate nearest neighbor search that umap-learn uses.
Finding neighbors
import polars_umap as pu
nn = digits.with_columns(nn=pl.col("pixels").umap.knn(k=5, random_state=0))
nn.head(3)
shape: (3, 3)| pixels | digit | nn |
|---|
| array[f64, 64] | i64 | struct[2] |
| [0.0, 0.0, … 0.0] | 0 | {[0, 877, … 1167],[0.0, 10.954452, … 13.2665]} |
| [0.0, 0.0, … 0.0] | 1 | {[1, 93, … 1050],[0.0, 14.247807, … 19.672316]} |
| [0.0, 0.0, … 0.0] | 2 | {[2, 57, … 115],[0.0, 17.435596, … 25.942244]} |
The result is a struct with two fields, both sorted by increasing distance:
indices: an Array(UInt32, k) of row numbers;
distances: an Array(Float32, k) of distances in the chosen metric.
As in PyNNDescent, every row counts as its own nearest neighbor: it’s usually first, at distance 0. Ask for k=6 to get five other rows.
Because the indices are row numbers, you can join information about the neighbors back in. For example, how often is a neighbor the same digit?
(
nn.with_row_index("row")
.select("row", "digit", neighbor=pl.col("nn").struct.field("indices").arr.to_list())
.explode("neighbor")
.filter(pl.col("neighbor") != pl.col("row"))
.join(
digits.with_row_index("neighbor").select("neighbor", neighbor_digit="digit"),
on="neighbor",
)
.select(same_digit=(pl.col("digit") == pl.col("neighbor_digit")).mean())
)
How approximate?
NNDescent trades a little accuracy for a lot of speed. Compared with an exact search:
from sklearn.neighbors import NearestNeighbors
k = 10
approx = np.asarray(
digits.select(pl.col("pixels").umap.knn(k=k, random_state=0).struct.field("indices"))
.to_series()
.to_list()
)
exact = NearestNeighbors(n_neighbors=k).fit(X).kneighbors(X, return_distance=False)
recall = np.mean([len(set(a) & set(e)) / k for a, e in zip(approx, exact)])
f"recall@{k}: {recall:.1%}"
When there are fewer rows than k, the search is exact and the missing neighbors are null.
UMAP on a precomputed graph
If you already have neighbors, for example from an exact search, a vector database or FAISS, pass them to umap_from_knn() and UMAP skips its own search. The original vectors aren’t needed:
dist, idx = NearestNeighbors(n_neighbors=15).fit(X).kneighbors(X)
graph = pl.DataFrame({"indices": idx, "distances": dist.astype(np.float32)})
graph.select(xy=pu.umap_from_knn("indices", "distances", random_state=0)).head(3)
shape: (3, 1)| xy |
|---|
| array[f32, 2] |
| [-4.64634, -1.344931] |
| [5.53124, 2.986445] |
| [7.111255, 2.451521] |
The graph can include each row itself (usually first, at distance 0) or leave it out. Every row needs the same number of neighbors. init="pca" isn’t available here, because it needs the vectors.