[Question]: Usage of Graph Algorithms and Any Slowdowns?

[nv-rliu]

Hi there,

I'm interested in understanding if pennylane depends on any graph algorithms from its usage of NetworkX? If so,

• What algorithms are used for what purpose?
• What graph sizes are they being used with?
• Have users experienced any slowdowns or issues with algorithms provided by NetworkX? (Speed, algorithm availability, etc)

Furthermore, would users be interested in accelerated nx algorithms via a GPU backend? This would involve zero code change.

Any insight into this topic would be greatly appreciated! Thank you.

[mlxd]

Hi @nv-rliu thanks for dropping by. Right now we have had a few tie-ins to networkx in the past, but over the past 1-2 years we have mostly migrated to rustworkx for performance-critical graph methods. Most of our remaining networkx support is for simple structuring/representation conveniences. I can summarise below:

1. Where do we use NetworkxX/RustworkX

   • Defining quantum circuit depth by representing our quantum gates as nodes in a DAG, and calculating the longest path length:

     pennylane/pennylane/circuit_graph.py

     Line 23 in 64e226f

     import rustworkx as rx

   • Using graph coloring to identify commuting observables given a quantum Hamiltonian —

     pennylane/pennylane/pauli/grouping/group_observables.py

     Line 25 in 64e226f

     import rustworkx as rx

2. Why RustworkX and not NetworkX?

   • NX was historically too slow for our needs (shortest path, graph coloring) -- in many cases we had several orders of magnitude improvements to performance by switching out to the compiled backend.
   • Additionally, we use metis/kayhypar for partitioning, as NX didn’t support (at least at the time) the required functionality we wanted.
   • RX algorithms we are currently using include rustworkx.dag_longest_path_length, rustworkx.graph_greedy_color, and rustworkx.digraph_dijkstra_shortest_paths

3. Was NX too slow

   • For the above, yes. We found much better performance moving to rustworkx in our test cases. For some sample data, see the following points:
   • Using rustworkx instead of networkx for DAG shortest path: Replace NetworkX by RetworkX #1791 (comment)
   • Using rustworkx instead of networkx for graph-coloring: Improve implementation of group_observables #6043

The above are direct replacements of networkx with rustworkx in our stack, though if it is an easy opt-in for cuGraph acceleration via networkx, we can potentially consider introduction of an API layer supporting both packages as backends.

Assuming they are supported, can you share any data of mapping the above functions directly to the GPU through networkx?
Also, does there exist an upcoming feature roadmap of support that we could consider?
Anything else you'd like to know, or anything else you think may be useful for us?

Thanks again.

[nv-rliu]

Thanks for the insight! Yes, I agree NetworkX is great in many ways but speed at scale is not one of them.

My team and I have recently been working on promoting a GPU-accelerated backend for NetworkX, which allows you to greatly speed up graph algorithms at scale with GPUs, all with zero code change (sorry if this sounds too marketing, haha). This has been an ongoing collaboration with the NetworkX developers as well. (backends came out with the 3.0 release).

Pardon me but let me take a look at the times for those algorithms with different graph sizes.

[nv-rliu]

As far as feature roadmaps, we're currently reaching out to projects that could benefit from GPU accelerated NetworkX and gauging what algorithms they'd like to see added to the NetworkX dispatching mechanism.

[CatalinaAlbornoz]

That's great @nv-rliu !

We're getting some info on what our teams here would need. We'll get back to you on this next week.

Have a good weekend!