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 considering the addition of Leiden clustering!

> do you consider that each row in X is a node connected to all other nodes with a strength that relates to the inverse of the distances?
Typically, Leiden Clustering is used in conjunction with a nearest-neighbor graph which also serves as the basis of umap - essentially for the (typically) 15 nearest neighbors it stores distances based on a t-distribution-kernel. While Leiden itself is defined on arbitrary graphs and the paper does not comment on it explicitly, it is mostly used in conjunction with umap's neighborhood graph from which umap would start to create a lower-dimensional embedding (the first step is fully deterministic).

> how would you fit the Louvain clustering algorithm to the scikit-learn API?
I would suggest to include the creation of the neighborhood graph into the "fit" function while allowing to input a weighted graph's adjacency too. I believe that while the idea of modularity is defined on a graph, the overall algorithm is typically referred to as a clustering algorithm and could be interpreted as such.  

> wouldn't a graph processing library such as networkx better suited for this algorithm

The implementation from scanpy treats it as a clustering algorithm and describes it as such, for cugraph it is included in a graph library without the direct connection. 
From my experience, the combination of the umap-neighborhood-graph and leiden-modularity-clustering really works well across datasets and would be a welcome addition to the set of clustering algorithms. I would not like to hide it in networkx as it would not be used that way.

> How do you compare clustering results for the applications you have in mind? In particular, do you have references that compare the results of clustering algorithm implemented in scikit-learn to Leiden clustering?

In our experiments, we used ARI to compare clustering quality, see top-left corner.
<img width="791" height="124" alt="Image" src="https://github.com/user-attachments/assets/1514eb83-1f4c-472f-a72a-85e98a2d5aa0" />
On higher-dimensional datasets, especially ones that are a little noisy, Leiden is one of very few algorithms with quite good performance throughout, for example in our preprint: https://arxiv.org/pdf/2503.15582 (page 7 for a table with ARI values and page 17 for a figure with more algorithms). I can look for other sources if desired, but this should already give an orientation.

Labels: New Feature, Needs Decision - Include Feature