Investigate `networkit` (for `leiden` implementation)

[ilan-gold]

What kind of feature would you like to request?

Additional function parameters / changed functionality / changed defaults?

Please describe your wishes

https://networkit.github.io/dev-docs/python_api/community.html#networkit.community.ParallelLeiden

There seems to be a parallel Leiden algorithm which would be awesome! The library might have other cool things!

[ilan-gold]

networkit.ipynb

Both parallel algorithms (cugraph and networkit) run end-to-end in less than 1 minutes with networkit being dominated by graph creation time, a seemingly known issue in the repo (I couldn't get the direct-from-COO working).

Both produce non-deterministic results on account of parallelism.

Not sure I see a reason not to offer this as an alternative

[flying-sheep]

a seemingly known issue in the repo (I couldn't get the direct-from-COO working).

I can’t find an issue, do you have a link?

[ilan-gold]

I can’t find an issue, do you have a link?

There are a number of things about memory-usage in the repo, which I assumed was related, but I looked into it more and it boils down to these lines, as it turns out: https://github.com/networkit/networkit/blob/d11dfd228edfa0f91847be04e0753b0ca50a2059/networkit/graph.pyx#L462-L464 where they make a view using intp which can break your graph if it is not the matching data type. AFAICT, intp is a system default, which is generally int64 but your indices can be int32. I just made an issue, sorry for the noise: networkit/networkit#1413

Once I worked around this, the graph creation time halved, now the same overall time as RSC 🎊

[ilan-gold]

Strange, but:

with h5py.File('dbb5ad81-1713-4aee-8257-396fbabe7c6e.h5ad') as f:
    adjacency = ad.io.read_elem(f["obsp"]["connectivities"])
    adjacency_coo = adjacency.tocoo()
    g = GraphFromCoo(adjacency_coo, weighted=True)

works, but the leiden calculation then fails. The kernel just dies, so needs more investigating (same crash on the leiden calculation if you do GraphFromCoo((weights, (sources, targets))). It might OOM from the casting to int64, not exactly obvious to me what is going, but it could also be just another memory-view bug. Will need to investigate, but presumably nothing major.