HNSW index build reproducibility - use single thread instead

[hsuknowledge]

Hello. Based on these notes you left for RcppHNSW[1][2], I suggest switching to single thread for the hnsw_build step and only that step [3].

Here's my test log messages. The number of graph edges fluctuates if and only if the index building function uses multi threading. It and the ultimate umap result become reproducible if I fix n_threads = 1 in using hnsw_build.

22:09:34 Commencing optimization for 500 epochs, with 17984770 positive edges using 20 threads

umap2() messages

22:08:09 Using HNSW for nearest neighbor search
22:08:09 UMAP embedding parameters a = 0.9922 b = 1.112
22:08:09 Setting random seed 1
22:08:09 Read 107723 rows and found 489 numeric columns
22:08:09 Building HNSW index with metric 'l2' ef = 200 M = 16 using 1 threads
22:09:12 Finished building index
22:09:12 Searching HNSW index with ef = 100 and 20 threads
22:09:17 Finished searching
22:09:17 Commencing smooth kNN distance calibration using 20 threads with target n_neighbors = 100
22:09:21 Initializing from normalized Laplacian + noise (using RSpectra)
22:09:29 Range-scaling initial input columns to 0-10
22:09:34 Commencing optimization for 500 epochs, with 17984770 positive edges using 20 threads
22:09:34 Using rng type: pcg
Using method 'umap'
Optimizing with Adam alpha = 1 beta1 = 0.5 beta2 = 0.9 eps = 1e-07
0%   10   20   30   40   50   60   70   80   90   100%
[----|----|----|----|----|----|----|----|----|----|
**************************************************|
22:09:39 Optimization finished

[1] jlmelville/rcpphnsw@6c54753

[2] jlmelville/rcpphnsw#23

[3]

uwot/R/nn_hnsw.R

Line 18 in 3b7c889

n_threads = n_threads,

[jlmelville]

Thank you for the report. I'll need to think this one over. Although the default batch-based optimization in umap2 does make things more stable, I think for better reproducibility you will probably need to set n_threads = 1 anyway.

A workaround is to build the neighbor graph outside of umap2 and pass the results to the nn_method parameter.

[hsuknowledge]

I have not touched the batch = TRUE setting, believing that patch is necessary for reproducibilty in the optimization step. What I found that cannot be controlled with seed was before optimization, the log telling different number of graph edges each time, driving a slight shift on the umap with each recalculation. As soon as I fixed the index-building function to use 1 thread, still using 20 threads to hnsw_search(), the reported number of graph edges became consistent across two runs, and I can't notice a change in the plot result.

[jianshu93]

I think it is because the multi-threading HNSW lib is not equivalent to single-threaded one, which does not make any sense because parallelization should not change anything, just speed. HNSW with the same parameter should always converge to the same graph no matter single or multiple-threading. Thread-safety/data race is a big concern here. I would recommend the Rust HNSW (https://crates.io/crates/hnsw_rs), same speed, but rerproducible across runs in multi-threaded case (although a R interface might be needed)

[jlmelville]

hnswlib says that addItems is thread-safe so I will have to investigate more. Could be an issue with RcppHNSW.

[jianshu93]

With openMP parallel for in the multi-threaded version of hnswlib, it should be consistent with single-threaded version. The code is in the python binding part though. Not sure how it was handled in RcppHNSW.-Jianshu

[hsuknowledge]

A workaround is to build the neighbor graph outside of umap2 and pass the results to the nn_method parameter.

Thank you for the advice. I now use findKNN() from BiocNeighbors with their default KmknnParam to find the exact knn and notice that their naming convention is list(index, distance), not list(idx, dist). Still, I'm glad the documentation states it clearly so it's not bad at all.

[jlmelville]

Coming back to this, the Python bindings are also not deterministic, so that cleans up that mystery. add_items is thread safe but in the sense that the resulting index will be in a valid state, not that you get the same state on each run.

I may add a parameter to control the number of index-building threads.

I will also probably allow the nn_method to use index and distance as names for compatibility with BiocNeighbors (but not in this issue).

[jlmelville]

Added a n_build_threads parameter, which should be set with n_build_threads = 1 with nn_method = "hnsw" if you are seeking determinism. On master now, will be in the next release whenever that is.