Leiden Clustering produces too many clusters #3749
Comments
Intron7
added
? - Needs Triage
|
@Intron7 The way the Leiden algorithm works - the nodes in a graph move to form temporary clusters (similar to modularity optimization phase in Louvain algorithm) that maximize the modularity. Afterwards, in the nodes within each such temporary clusters are checked if they are strongly connected (according to Leiden algorithm). If not, then the nodes in a temporary clusters are not merged to from aggregated clusters. One can change the thresholds so that relatively weakly-connected nodes keep forming Leiden clusters. |
|
I know that Leiden and Louvain produce different clusterings. But when the number of Leiden clusters goes up from 50 to over 1000 from 23.04 to 23.06 I think there might be some unintentional changes. In my testing it looks like the issue has to do with |
|
|
|
Thank you for sharing nice plots. Could you try to run with smaller resolution? |
|
Here is the plot you asked for. The original Plot was taken at 0.6 resolution. now you can see for Leiden the resolution scaling and that it behaves very erratically. |
|
Here you can see that max_iter doesnt change the plot. My hunch is that the weights dont get updated and they stay the same so the algorithm stops prematurly |
|
Thank you for sharing additional plots. Is your dataset public? If so, we would like to run it on our end to figure out a bit more on it. |
|
https://github.com/Intron7/rapids_singlecell/blob/main/notebooks/demo_gpu-seuratv3.ipynb It's this notebook. I can also create the anndata object needed (with all the preprocessing done) and upload it to googledrive and provide the link |
|
It would be great if could upload kindly upload the data (that are input the Leiden algorithm) on google drive. I would like to run it locally. |
rlratzel
changed the title
|
I also have the same issue with my data that is separate. Solution for leiden clustering would be super helpful! |
|
@johnhickey22 - which version of cugraph are you using? |
|
@ChuckHastings - I am using 23.06.02 - let me know if you need anything else. |
|
@Intron7 |
|
You can already see this behaviour with The CPU version of Leiden gives me 9 Clusters. The Bug still exists in Rapids-23.08 |
|
Any update here - was it solved in another thread? Just wanted to check in, in case I missed something. Would love to integrate this into my analysis pipeline and just waiting for this clustering issue to be solved. Thanks! |
|
Hi, |
|
Hi, |
- Normalization factor was missing in the equation to decide if a node and a refined community is strongly connected inside their Louvain community. This PR adds that factor. - Disable random moves in the refinement phase. We plan to expose a flag to enable/disable random moves in a future PR. - Adds new function to flatten Leiden dendrogram as dendrogram flattening process needs additional info to unroll hierarchical leiden clustering Closes #3850 Closes #3749 Authors: - Naim (https://github.com/naimnv) - Alex Barghi (https://github.com/alexbarghi-nv) Approvers: - Chuck Hastings (https://github.com/ChuckHastings) - Seunghwa Kang (https://github.com/seunghwak) - Brad Rees (https://github.com/BradReesWork) URL: #3990
|
Looks good to me now |
|
@Intron7 Thank you for reporting. |
Version
23.06 - 23.06.02
Which installation method(s) does this occur on?
Conda
Describe the bug.
Leiden Clustering produces over 1000 Clusters. This is in contrast to 23.04 where I got around 30-40 for the same test dataset. Louvain Clustering give me 23 clusters.
Minimum reproducible example
def leiden( adata: AnnData, resolution: float = 1.0, n_iterations: int = 100, use_weights: bool = True, neighbors_key: Optional[int] = None, key_added: str = "leiden", ) -> None: """ Performs Leiden Clustering using cuGraph Parameters ---------- adata : annData object with 'neighbors' field. resolution A parameter value controlling the coarseness of the clustering. Higher values lead to more clusters. n_iterations This controls the maximum number of levels/iterations of the Louvain algorithm. When specified the algorithm will terminate after no more than the specified number of iterations. No error occurs when the algorithm terminates early in this manner. use_weights If `True`, edge weights from the graph are used in the computation (placing more emphasis on stronger edges). neighbors_key If not specified, `leiden` looks at `.obsp['connectivities']` for neighbors connectivities If specified, `leiden` looks at `.obsp['neighbors_key_ connectivities']` for neighbors connectivities key_added `adata.obs` key under which to add the cluster labels. """ # Adjacency graph if neighbors_key: adjacency = adata.obsp[neighbors_key + "_connectivities"] else: adjacency = adata.obsp["connectivities"] offsets = cudf.Series(adjacency.indptr) indices = cudf.Series(adjacency.indices) if use_weights: weights = cudf.Series(adjacency.data) else: weights = None g = Graph() g.from_cudf_adjlist(offsets, indices, weights) # Cluster leiden_parts, _ = culeiden(g, resolution=resolution, max_iter=n_iterations) # Format output groups = ( leiden_parts.to_pandas().sort_values("vertex")[["partition"]].to_numpy().ravel() ) adata.obs[key_added] = pd.Categorical( values=groups.astype("U"), categories=natsorted(map(str, np.unique(groups))), ) # store information on the clustering parameters adata.uns["leiden"] = {} adata.uns["leiden"]["params"] = dict( resolution=resolution, n_iterations=n_iterations, )Relevant log output
No response
Environment details
Other/Misc.
This happens on 4 tested systems with both 3090 and A100s
Code of Conduct
The text was updated successfully, but these errors were encountered: