Leiden Clustering

### Describe the workflow you want to enable

The "Leiden" Clustering algorithm is considered one of the most powerful clustering algorithms, often outperforming competitors by a wide margin. 
The algorithm fulfils the inclusion criteria: its now 6 years old, has some 5200 citations. 

Currently, it is implemented in scanpy and cugraph where the latter includes a fast, gpu-enabled implementation. Due to its empirical performance, inclusion in scikit-learn would be a welcome addition for practitioners as it is vastly superior to most clustering algorithms currently included in scikit learn (on non-trivial datasets).

### Describe your proposed solution

I propose to include the Leiden algorithm as a clustering algorithm in scikit-learn.

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

[From Louvain to Leiden: guaranteeing well-connected communities](https://www.nature.com/articles/s41598-019-41695-z)

COMMENT:
Thanks for looking closer into this and also locating the relevant code snippet in our codebase!

> I am not familiar with the details of the umap-neighborhood-graph method. Would the pipeline you propose be similar to what we do with precomputed kNN distance graphs done in this example:
> https://scikit-learn.org/stable/auto_examples/neighbors/approximate_nearest_neighbors.html

yes. In the first step the graph/distance matrix would be computed (but no UMAP optimization since we only need the distance matrix that UMAP starts with) and then Leiden would run on this distance matrix.


> However, it's not clear to me what the input data passed to Leiden.fit looks like: it's called counts (suggesting integer data) and converted to a scipy.sparse matrix. It's doubly weird because I would have expected dense floating point features at this point.

The naming of the variable here is indeed problematic. Even though we called it counts, it contains 15 floats per data point, such that a sparse matrix makes sense. As I said, the naming here is misleading and we will fix it.


> UMAP connectivies from a mathematical point

That is indeed a little hard to find as almost all posts describing UMAP gloss over that part. On page 14/15 in https://arxiv.org/pdf/1802.03426 it is described that we define $\rho$ to be the (Euclidean) distance to the closest neighbor and $\sigma$ is then chosen such that when fitting an exponentially decaying curve, the probabilities sum up to $\log k$ where $k$ is the number of neighbors. So long story short: the proximities computed by the UMAP graph have exponential decay in Euclidean distance and the closest neighbor always has a proximity of 1. Since the whole thing is not necessarily symmetric, the edges $u=(a,b)$ and $v=(b,a)$ are then combined as $u+v-u\cdot v$, effectively computing the probability that at least one of the two edges exist.

Intuitively we use something like a fuzzy cover over the neighbors together with exponential decay for far-away points, emphasizing close neighbors.

Does this answer your questions on how the UMAP distance matrix and the Leiden algorithm would interact in a typical clustering setting?

Labels: New Feature, Needs Decision - Include Feature