Skip to main content

Nearest neighbors

Find approximate nearest neighbors with NNDescent, and run UMAP on a precomputed graph.

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)
pixelsdigitnn
array[f64, 64]i64struct[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())
)
shape: (1, 1)
same_digit
f64
0.981914

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%}"
'recall@10: 99.6%'

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.