scverse
improve sc.pp.neighbors parameter docs
Dear, Seurat embed cells in a graph structure - for example a K-nearest neighbor (KNN) graph, with edges drawn between cells with similar gene expression patterns, and then attempt to partition this graph into highly interconnected ‘quasi-cliques’ or ‘communities’. A KNN graph is first constructed based on the euclidean distance in PCA space, and refine the edge weights between any two cells based on the shared overlap in their local neighborhoods (Jaccard similarity). Does Scanpy uses Jaccard similarity to cluster too?
From my understanding, Seurat uses the Louvain algorithm to maximize modularity on their KNN where edge weights are Jaccard similarity between the relevant nodes' neighbors.
Scanpy is largely similar by default, though the nearest neighbors are found by UMAP's method, and all edge weights are 1. There's a boolean flag to use edge weights if you'd like (use_weights), which uses the weights from the adjacency matrix found in: adata.uns["neighbors"]["connectivities"].
If you'd like to know more, I'd recommend looking at the docs for sc.pp.neighbors, sc.tl.louvain, and the clustering tutorials.
I assume UMAP uses a number of top PCs as input as well, no? And do you know if distances are calculated only on 2 UMAP components, or if more are used?
Part of the UMAP computation is creating an approximate KNN graph. Scanpy uses that part of the UMAP package to create it's neighborhood graph. UMAP uses whatever distance metric and feature space the user specifies for finding neighbors. Scanpy uses euclidean distance in PCA space as the default for finding neighbors, but that can be changed.
I hope that's more clear.
So the method='umap' has nothing to do with using UMAP dimensionality reduction as a distance metric, but instead only refers to a KNN-graph implementation? It seems to me that making a KNN-graph from the Euclidean distances should be easy.
Yeah, that sounds right.
It's super easy to code, you'd just need to calculate all pairwise distances which is ~O(n^2), and similar for memory. To get around that there's a number of approximate nearest neighbors methods.
I'm not too sure what the assumptions are behind each method though. @falexwolf, any reason in particular you've chosen UMAP's method for the KNN calculation?
I'm not to sure what the assumptions are behind each method though. @falexwolf, any reason in particular you've chosen UMAP's method for the KNN calculation?
It's highly competitive in terms of speed and accuracy with other libraries (https://github.com/erikbern/ann-benchmarks, pynndescent is what umap uses, wasn't available at the time for Scanpy), it's a lot easier to install than everything else, and the result has been shown to harmonize well with UMAP, which I expected would become the canonical way of visualizing things.
Thanks for the explanation! I had no idea this was an important bottleneck. I always assumed all distances are calculated... that shows how little I think about optimization ^^.
On another note, it might be a little confusing to see method='umap' as a parameter. I would have immediately assumed that umap is used as a distance metric. But maybe that's me being too lazy to read as well.
Is this documented with this level of clarity anywhere else, other than in this thread?
I had the same intuition when coming across methods as "umap".
(https://github.com/erikbern/ann-benchmarks, pynndescent is what umap uses, wasn't available at the time for Scanpy)
Is pynndescent is available now to scanpy? If so, can we update the documentation and "method" parameter options for sc.pp.neighbors? Wording such as "The neighbor search efficiency of this heavily relies on UMAP" could be potentially misleading. Thanks.
Good point, method should really have cleaner docs. Anyone up for making a PR?
