Making the input type of leiden algorithm generic

[johandahlberg]

Hi!

I am working in a project where we use the Leiden implementation of graspologic to processes some rather large graphs (in the order of magnitude of tens of millions of edges and nodes). We are able to represent our node ids as unsigned 64bit integers, and I noticed that graspologic uses strings internally to represent the nodes.

I am rather a novice when it comes to Rust, but I did a quick try to see if I could change Edge to be a struct like this:

pub struct Edge<T> {
    pub source: T,
    pub target: T,
    pub weight: f64,
}

And use that throughout the code. For my use-case this improved runtime by ~30% and lowered the memory usage by ~20%, when I passed a list of integers instead of strings to the method. Since for us running the Leiden can take hours, cutting the runtime by a third would be a rather big win.

I am wondering if you would be interested in a PR introducing these changes into graspologic-native. If so I can clean up my work a bit and submit a PR for your consideration.

/Johan Dahlberg

[daxpryce]

This is probably a fine way to look into this - the reason we stuck on str (or even String, I can't recall) was because we needed a fixed type from Python, and I did not want to write a leiden_str and leiden_int symbols. The main problem is in the interplay between python and leiden here.

Anyway, even if that's true we can still genericize the Edge & Network such that they still create the same compact network, and just force the python bindings to only use the leiden<str>(...) versions (which we may need to hardcode in the delegator). But then when you're using the rust only version from the non-crates.io-crate (I really wish I had started publishing those :| ), you could use a u64 or usize or whatever as the type.

Anyway, share your branch as soon as you'd like and I'll try to help as I can! I don't have a ton of time to support the release and verify it works with our downstream users (like https://github.com/microsoft/graphrag), but if you wanted to help me speed up these releases you could also take a look at adding an integration test in github workflows that a: uses the <currently built version of graspologic-native> and b: <pulls graphrag & graspologic and makes sure it doesn't explode>.

And I can do that too if it turns out to be too much!

[daxpryce]

@johandahlberg I added a few more items in #56 and #57 - the latter specifically will change the contract such that we always use a csr matrix (ideally from sprs, jettisoning CompactNetwork entirely), and updating LabeledNetwork to be a genericized Edge / EdgeList -> sparse matrix builder.

All of this would require #56 to actually work, but if it did, we could support a better experience across the board - for rust users only, for python users, etc.

[daxpryce]

Neither of #56 or #57 should stop you from this specific enhancement though

[johandahlberg]

Hey @daxpryce!

Sorry for taking so long to get back to you. These past two weeks have been rather hectic.

Your suggestions on going directly for support of sparse matrices should be very much in line with out use-case, so if we could do that it would be great. I hope to be able to spend some time looking into this, closer to the summer , and I will get back to you here with any ideas/implementations I might be able to suggest.