scverse / scverse/scanpy

Investigate our neighbors algorithm choice

Open
#4,131 15 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Area - Topology 🍩
Dominant language
Python
Stars
2.6k
Forks
779
Avg merge
1d 4h
Merged PRs (30d)
27

Description

Right now, we are relying on the underlying implementation in umap for our neighbors calculation due to (potentially outdated) matintainability/usability concerns of almost every other library. We use PyNNDescent currently AFAICT:

https://github.com/scverse/scanpy/blob/bb4e605fd59263516f0c97d4bff7783f5fcfa541/src/scanpy/neighbors/__init__.py#L658-L665

in absence of a transformer but I think this should be reconsidered.

https://github.com/nmslib/hnswlib seems to be maintained if not amazingly documented
https://github.com/meilisearch/arroy lacks python bindings but looks to be maintained
https://github.com/facebookresearch/faiss seems to be maintained but like the first option lacks documentation it seems
https://github.com/zilliztech/pyglass top performer on https://ann-benchmarks.com/index.html#algorithms

Overall, we need to make a reasonable judgement about the speed-accuracy-maintainability tradeoff and try to figure out if we should make this change for our users.

See https://ann-benchmarks.com/index.html as well

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the neighbors implementation in src/scanpy/neighbors/init.py around lines 658-665, then review the linked PyNNDescent usage and candidate libraries. Compare speed, accuracy, documentation, maintenance, and Python integration using the ann-benchmarks reference. Done means a justified recommendation and a clear decision about whether Scanpy should change its neighbors implementation.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
bioinformatics, machine-learning, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.