[FEA]: Add support for ForceAtlas2 layout

[JacksonDam]

Is this a new feature, an improvement, or a change to existing functionality?

New Feature

How would you describe the priority of this feature request

Low (would be nice)

Please provide a clear description of problem this feature solves

It would be great if nx-cugraph could include support for ForceAtlas2, so that it not necessary to use both NetworkX and cuGraph for visualising larger graphs with GPU acceleration.

As seen here: https://docs.rapids.ai/api/cugraph/stable/api_docs/api/cugraph/cugraph.force_atlas2/

Describe your ideal solution

A CUDA implementation of FA2 available via this backend.

Describe any alternatives you have considered

No response

Additional context

No response

Code of Conduct

• I agree to follow nx-cugraph's Code of Conduct
• I have searched the open feature requests and have found no duplicates for this feature request

[eriknw]

Thanks for the suggestion @JacksonDam! Good idea 👍

I think we should be able to get this into the next NetworkX release. It will require an update to NetworkX to make it a dispatchable function, but we can add it to nx-cugraph before that.

In your experience, are the cugraph and networkx APIs and implementations largely compatible? At a glance, they appear very similar:

• https://docs.rapids.ai/api/cugraph/stable/api_docs/api/cugraph/cugraph.force_atlas2/
• https://networkx.org/documentation/stable/reference/generated/networkx.drawing.layout.forceatlas2_layout.html

CC @rlratzel. It looks like this is a legacy implementation in cugraph, so we should update and wrap it with pylibcugraph instead. Tasks:

• dispatch in networkx Make forceatlas2_layout dispatchable networkx/networkx#7794
• expose force atlas2 via pylibcugraph
• add forceatlas2_layout to nx-cugraph

@JacksonDam please let us know if there are any other layout functions or algorithms that you would like added to nx-cugraph!

[JacksonDam]

In my experience the implementations are almost interchangeable, sharing broadly the same parameters with only a few differences (node_mass and dissuade_hubs are only on the nx version). The current cuGraph implementation, although it is almost plug-and-play 😃, also doesn't support disabling outbound_attraction_distribution iirc.

[eriknw]

Thanks for the summary! We'll be sure to add a note to the docstring for unsupported parameters. Are any of the unsupported parameters important to you?

[JacksonDam]

For me personally, the outbound_attraction_distribution being forced to True has prevented me from getting identical output to what nx.forceatlas2_layout would have given (at least I believe this was the only thing preventing identical output...).

[rlratzel]

Thanks @JacksonDam for the feature request. I agree with @eriknw on all points. @ChuckHastings @jnke2016 , any thoughts on adding FA2 to pylibcugraph?

I'm also quite interested in your use case for plotting larger graphs. I'm wondering if the call to nx.draw(G) will end up not scaling well, or are you also using a different plotting package other than Matplotlib?

[ChuckHastings]

We can certainly look at exposing this algorithm via PLC/pylibcugraph. We have the C++ tools to accomplish this, so it's just a matter of scheduling some time to do this.

[JacksonDam]

@rlratzel My use case is for visualising recommendation datasets (user-item interaction). I am doing the actual graph rendering through a web frontend (with SigmaJS, WebGL visualisation) which handles the scale (~500,000 edges) well, so there is no concern about nx.draw(G) potentially not scaling in my case. Due to the scale of graph I'm working with, cuGraph enables me to layout the graph before it is sent to the frontend in a reasonable time.

[nv-rliu]

@JacksonDam just curious, what's your intended use-case with a GPU accelerated ForceAtlas2?

[JacksonDam]

@JacksonDam just curious, what's your intended use-case with a GPU accelerated ForceAtlas2?

Hi there @nv-rliu! I am currently using the GPU accelerated implementation of FA2 in cuGraph to aid visualisation of large movie recommendation datasets such as MovieLens-1M and MovieLens-10M, for my undergraduate dissertation. Given that these datasets have millions of interactions (edges) this is currently the only way for me to get a feasible runtime for graph layout.

It would be a nice-to-have, but not essential for this to be implemented in nx-cugraph, so that my code can work only with NetworkX and NetworkX backends.

[nv-rliu]

Thank you for the insight!

[rlratzel]

@JacksonDam - not related to FA2, but relevant if you're interested: this blog also uses MovieLens data.