leiden algorithm run time is much longer than the louvain algorithm

[Liripo]

Leiden algorithm run 16 mins,but louvain algorithm only run 30s.

> bench::bench_time({
   object <- FindClusters(object,
      algorithm = 4,
      method = "igraph",
      resolution = 0.8
  )
 })
process    real 
  1.16m  16.64m 

louvain algorithm

> bench::bench_time({
   object <- FindClusters(object,
    algorithm = 1,
    method = "igraph",
    resolution = 0.8
   )
 })
process    real 
  6.21s  30.26s

And my object has 40,000 cells. Is this normal？

[alanocallaghan]

This isn't really an expected result, see for example https://www.nature.com/articles/s41598-019-41695-z/
where Leiden is found to be much faster than Louvain.

It may be because Louvain is implemented directly in C++ (here: https://github.com/satijalab/seurat/blob/4e868fcde49dc0a3df47f94f5fb54a421bfdf7bc/src/ModularityOptimizer.cpp)
while Leiden uses a python module via reticulate (here:

seurat/R/clustering.R

Lines 1627 to 1716 in c463873

	# Run Leiden clustering algorithm
	#
	# Implements the Leiden clustering algorithm in R using reticulate
	# to run the Python version. Requires the python "leidenalg" and "igraph" modules
	# to be installed. Returns a vector of partition indices.
	#
	# @param adj_mat An adjacency matrix or SNN matrix
	# @param partition.type Type of partition to use for Leiden algorithm.
	# Defaults to RBConfigurationVertexPartition. Options include: ModularityVertexPartition,
	# RBERVertexPartition, CPMVertexPartition, MutableVertexPartition,
	# SignificanceVertexPartition, SurpriseVertexPartition (see the Leiden python
	# module documentation for more details)
	# @param initial.membership,node.sizes Parameters to pass to the Python leidenalg function.
	# @param resolution.parameter A parameter controlling the coarseness of the clusters
	# for Leiden algorithm. Higher values lead to more clusters. (defaults to 1.0 for
	# partition types that accept a resolution parameter)
	# @param random.seed Seed of the random number generator
	# @param n.iter Maximal number of iterations per random start
	#
	# @keywords graph network igraph mvtnorm simulation
	#
	#' @importFrom leiden leiden
	#' @importFrom reticulate py_module_available
	#' @importFrom igraph graph_from_adjacency_matrix graph_from_adj_list
	#
	# @author Tom Kelly
	#
	# @export
	#
	RunLeiden <- function(
	object,
	method = c("matrix", "igraph"),
	partition.type = c(
	'RBConfigurationVertexPartition',
	'ModularityVertexPartition',
	'RBERVertexPartition',
	'CPMVertexPartition',
	'MutableVertexPartition',
	'SignificanceVertexPartition',
	'SurpriseVertexPartition'
	),
	initial.membership = NULL,
	node.sizes = NULL,
	resolution.parameter = 1,
	random.seed = 0,
	n.iter = 10
	) {
	if (!py_module_available(module = 'leidenalg')) {
	stop(
	"Cannot find Leiden algorithm, please install through pip (e.g. pip install leidenalg).",
	call. = FALSE
	)
	}
	switch(
	EXPR = method,
	"matrix" = {
	input <- as(object = object, Class = "matrix")
	},
	"igraph" = {
	input <- if (inherits(x = object, what = 'list')) {
	graph_from_adj_list(adjlist = object)
	} else if (inherits(x = object, what = c('dgCMatrix', 'matrix', 'Matrix'))) {
	if (inherits(x = object, what = 'Graph')) {
	object <- as.sparse(x = object)
	}
	graph_from_adjacency_matrix(adjmatrix = object, weighted = TRUE)
	} else if (inherits(x = object, what = 'igraph')) {
	object
	} else {
	stop(
	"Method for Leiden not found for class", class(x = object),
	call. = FALSE
	)
	}
	},
	stop("Method for Leiden must be either 'matrix' or igraph'")
	)
	#run leiden from CRAN package (calls python with reticulate)
	partition <- leiden(
	object = input,
	partition_type = partition.type,
	initial_membership = initial.membership,
	weights = NULL,
	node_sizes = node.sizes,
	resolution_parameter = resolution.parameter,
	seed = random.seed,
	n_iterations = n.iter
	)
	return(partition)
	}

)

[samuel-marsh]

Just chiming in as note I have also experienced this and echoing @alanocallaghan that was my guess as well since Seurat implementation calls Leiden package which sends things to reticulate and into python.

Leiden authors note there are a couple packages which include some part of python leidenalg functionality but none are complete (https://github.com/vtraag/leidenalg#usage).

It would appear though that Cole Trapnell’s lab implementation (https://cran.rstudio.com/web/packages/leidenbase/index.html) might get closest for speed as it aims to implement in C/C++. I haven’t dug entirely into functionality and whether or not that could be used here but thought I’d mention.

Best,
Sam

P.S. @mojaveazure hope you don’t mind but tagging here to see if Seurat team has experienced this or discussed potential changes?

[mojaveazure]

This slowdown is likely because we're using Leiden/reticulate to call the Python implementation of leiden rather than using an R-native implementation. We haven't looked into any of the R/C++ implementations as

• we last looked at this in early 2021
• all currently R-native leiden implementations are relatively new
• we require any and all dependencies, including suggested ones, to be on CRAN or Bioconductor
• we just don't have the bandwidth to continually evaluate new clustering methods

If anyone would like to investigate whether or not Leidenbase or leidenAlg (Kharchenko lab) are indeed faster than Leiden/reticulate and make a PR to support one of those R-native packages, we would be happy to include it. However, our focus at this time is on other priorities

[samuel-marsh]

Thanks so much for insight and totally understand from dev perspective. Don’t know that I have bandwidth to look into PR either but maybe some time in new year I’ll come back around unless someone else does first.

Thanks again!
Sam

[alanocallaghan]

They're both substantially faster, but the Trapnell group one (leidenbase) seems faster and much better documented

library("leidenbase")
library("leidenAlg")
library("leiden")
library("igraph")

fpath <- system.file('testdata', 'igraph_n1500_edgelist.txt.gz', package='leidenbase')
zfp <- gzfile(fpath)
igraph <- read_graph(file = zfp, format='edgelist')

microbenchmark::microbenchmark(leiden.community(igraph), leiden_find_partition(igraph), leiden(igraph))
# Unit: milliseconds
#                           expr         min          lq        mean      median
#       leiden.community(igraph)    52.98505    55.16530    63.16430    55.95267
#  leiden_find_partition(igraph)    29.22238    30.54163    39.15174    37.57693
#                 leiden(igraph) 17140.52418 20671.12398 21172.11517 21128.94100
#           uq         max neval cld
#     75.38524    80.10432    10  a 
#     40.30238    56.91094    10  a 
#  22268.67866 24597.89747    10   b