search

neo4j / graph-data-science

Source code for the Neo4j Graph Data Science library of graph algorithms.
https://neo4j.com/docs/graph-data-science/current/
Other
621 stars 160 forks source link

[Feature Request] Optimize for Constant Potts Model in Leiden/Louvain #238

Closed RuneBlaze closed 1 year ago

RuneBlaze commented 1 year ago

Is your feature request related to a problem? Please describe.

Not really. It should be a general improvement. AFAIK, the Leiden algorithm in GDS optimizes for modularity, which suffers from the resolution limit. To avoid this, the current "off-the-shelf" Leiden optimizes for the Constant Potts Model (CPM) instead. GDS cannot optimize for CPM yet, which is a potential problem.

Describe the solution you would like

Implement a switch in the API to optimize for CPM instead of modularity, and modify the code to allow optimizing for CPM inside the Leiden (perhaps also Louvain?) implementation. To be honest, I am a CS grad student working on community detection looking to pad my resume + get more familiar with neo4j during my winter break, so I am very interested in taking a stab at implementing this. Any chance I can try working on it on the Leiden code?

Describe alternatives you have considered Not that I know of.

Additional context

IoannisPanagiotas commented 1 year ago

Hi @RuneBlaze,

Thank you for the interest in our library!

We did briefly discuss supporting CPM score while implementing Leiden, but we haven't done any work on this yet.

You are of course more than welcome to give it a try yourself. I would suggest starting with Leiden as well.

If you do end up giving it a try, you can open a pull request with your fixes, which we will then have a look at and give some feedback.

Let me know if you have any questions about our existing implementation.

Best regards, Ioannis.

RuneBlaze commented 1 year ago

Thanks! Sorry if I sounded too ahead of myself -- I will study the code and see if I can work on Leiden optimizing for CPM.

(Also feel free to close the issue if that's the convention. I will slowly work on a PR this month, and I will definitely let you know of any questions that I cannot resolve myself!)

Best, Baqiao

IoannisPanagiotas commented 1 year ago

No worries and no pressure :)

We will keep CPM in mind for the next time to focus on Leiden. If by then, there have been any updates from your side, that's wonderful! Otherwise it's totally fine ^^

I will close this issue now. Do feel free to re-open again, if there are any things you might have questions about :)