Warm-starting for Louvain, Leiden, etc.

[cfrankston728]

Possibly this is already doable with your framework, but it isn't immediately transparent to me. Rather than only a randomization, it would be great if iterative clustering methods could be seeded with specific initial cluster assignments. In sequential processing implementations for instance, this could greatly speed up convergence. For example, if a user has a very large graph, warm-starting a Leiden instance with the output of a faster Louvain assignment could be very beneficial.

leidenalg through igraph has the option to include initial assignments, but obviously for csr-native graphs, implementation of igraph-based processing suffers the significant overhead of format conversion.

[tbonald]

That's a great suggestion (not doable in the current framework).
We will work on it. Thanks.

[tbonald]

Hello,
I've just pushed an update on Develop, with custom initialization (sorry for the delay).
I will push on Master (new release) in the coming days.
Any suggestion is welcome!
Thanks.

[cfrankston728]

Wow that's great, thank you!
If interested, I do have another suggestion, which is to pre-coarsen and pre-sparsify the graph to speed up community detection even more. This might qualify more as heuristic decisions best left up to the user, and is something users could implement themselves (for example I have an implementation for my own work), but it could be a nice additional pre-packaged feature to include if it doesn't exist already.

[tbonald]

That's a great suggestion, thanks!
I've just pushed the update on Develop forcing aggregation first.
Not quite sure what you mean by pre-sparsification, however.

[cfrankston728]

Aggregation/pre-coarsening is helpful for reducing the number of vertices in the graph (I assume we both mean creating meta-nodes for nodes that are mutually each other's "nearest neighbor"---this can also be iterated more than once). Sparsification is removing the number of edges, so for instance, pruning "weak" edges. I think the way these operations are performed in practice tend to be more heuristic choices than something canonical.

For example, in my own workflow, I first pre-sparsify (prune weak edges) by specifying the K I want to keep for KNN. Then I create the meta-nodes (pre-coarsen). I iterate this a certain number of times, keeping track of how the node count changes, and adjusting K between coarsening steps by a scaling law accordingly, until I get sufficiently diminished returns (the graph is not compressible, i.e. the aggregation only reduces the number of nodes by a factor of 0.95 or something).

One could imagine many ways of achieving the same basic idea (compress the graph), so it's not clear that it should be something in your package per se because it's kind of a different pre-processing task.

I have a package within which I use your community detection, it could almost certainly be majorly refactored because this is research code and I am not a software engineer!
https://github.com/cfrankston728/data_graph/blob/main/data_graph/README.md

[tbonald]

Yes, it is not obvious how to sparsify a graph in a fast / canonical way. Note that Louvain can be sped up by increasing the parameter tol_optimization (e.g., to 0.1) to limit the number of iterations in the inner optimization loop.