search

Qiskit / rustworkx

A high performance Python graph library implemented in Rust.
https://www.rustworkx.org
Apache License 2.0
1.13k stars 154 forks source link

Implementation of Louvain Algorithm #1141

Open jamesdbaker opened 8 months ago

jamesdbaker commented 8 months ago

The Louvain algorithm is commonly used to identify communities in graphs, and is present in other libraries/tools such as NetworkX and Neo4J.

It would be great if an implementation was available in RustworkX too.

IvanIsCoding commented 8 months ago

I think this is a good ask. Right not we have no community detection algorithms implemented, but this could be an effort like #315 to start implementing those.

Sometimes it is just a matter that no one asked for them before

jamestwebber commented 7 months ago

A general question: is the goal of rustworkx to include algorithms like this out-of-the-box, or would it be better to support third-party packages for things like this? I see that networkx includes Louvain now, but originally it was a separate package. Similarly leidenalg implements community-detection on igraph graphs.

One thing I don't know: how complicated is it to write a package that works with rustworkx graphs in a performant way (i.e. not going through python when possible)? One item on my ever-growing list of projects is to try to implement Leiden (or similar) in Rust in a way that's compatible with rustworkx, potentially using the underlying graph structures directly.

IvanIsCoding commented 7 months ago

Firstly, our goal is to expand the graph library. Most of the existing algorithms started like this, someone needed a specific algorithm and we eventually implemented it. There is a lot of upfront cost with implementation & testing for correctness, but once it is released generally our maintenance for algorithms has been pretty easy.

Secondly, using rustworkx from Python is easy, you can check some of the works citing our paper and Qiskit itself. Also, using rustworkx-core from Rust is also easy, that is the approach some of Qiskit Rust modules use.

However, using rustworkx from other Rust code is currently blocked and you can see some discussion in #663. My general suggestion would be to call graph.edge_list() or graph.weighted_edge_list() from a Python object in PyO3 and then rebuild a rustworkx-core graph or just use that data directly in your algorithm.

IvanIsCoding commented 7 months ago

One last thought: for leiden specifically, I think if you build upon petgraph and rustworkx-core it would make life simpler to port your own version to be included in rustworkx. And we would gladly merge & distribute it if you made a PR submitting it!

jpacold commented 4 months ago

I'm interested in taking this on if nobody has started on it.

traviscross commented 4 months ago

@jpacold: It seems the right place to start is probably to first make a PR upstream to petgraph with the new algorithm.

jpacold commented 4 months ago

So far all I have done is implement the modularity function (which the Louvain algorithm tries to maximize) in this branch.

Before going any further I wanted to check whether the architecture makes sense. The idea is to eventually put the full algorithm in, e.g., rustworkx-core/src/community/louvain.rs.

Some open questions:

tsitong commented 3 months ago

It seems that the developers of petgraph believe that these community detection algorithms should be offered as a separate package, plz see https://github.com/petgraph/petgraph/issues/185. However, I’m not sure if their opinion has changed.

IvanIsCoding commented 3 months ago

So far all I have done is implement the modularity function (which the Louvain algorithm tries to maximize) in this branch.

Before going any further I wanted to check whether the architecture makes sense. The idea is to eventually put the full algorithm in, e.g., rustworkx-core/src/community/louvain.rs.

Some open questions:

  • Is there a better way (in either rustworkx or petgraph) to specify a graph partition?
  • I agree that it would make sense to put this in petgraph, but will have to think a bit more about how to do that correctly. Among other things, the implementation I have now would need an architecture change in petgraph, since I'm using the num_traits crate to constrain the edge weight type.
  • Eventually, the pyo3 function(s) that wraps this will need to have a similar constraint on the input graph. I need to figure out how to do the type check at run time.

I completely missed this comment. Also, feel free to open a draft PR so that we can discuss. I will try to get a look at it.

IvanIsCoding commented 3 months ago

It seems that the developers of petgraph believe that these community detection algorithms should be offered as a separate package, plz see petgraph/petgraph#185. However, I’m not sure if their opinion has changed.

We can be the other crate to host the algorithm.

traviscross commented 3 months ago

I've asked over on the petgraph side whether the old answer is still accurate. I notice that they've recently been merging other new algorithms such as PageRank that seem not too dissimilar to this.