[FEA]: Implement spectral_ordering

[adsharma]

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

Critical (currently preventing usage)

Please provide a clear description of problem this feature solves

networkx implements a spectral_ordering algorithm that's useful for some applications. I couldn't find a GPU accelerated variant in cugraph.

I see two spectral clustering algorithms, which are not the same.

Describe your ideal solution

Implement a cugraph equivalent of nx.spectral_ordering()

Describe any alternatives you have considered

Used the CPU variant. It was slow.

Additional context

No response

Code of Conduct

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

[adsharma]

Some research on why existing spectral clustering algorithms in cugraph are insufficient:

https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.5.023006

[adsharma]

Extracted networkx code for easier testing:

https://github.com/adsharma/nx-spectral-ordering

Here's my attempt to speed it up:
adsharma/nx-spectral-ordering@6bb1373

Runs an algorithm copied from cupy.dev (link in the commit), but fails functional testing. Needs more debug.

Also I heard that cuSparse has a PCG solver. Not sure how to invoke it from python.

[adsharma]

Modified the networkx PCG solver to use cupy. It works, but is not faster.

https://github.com/adsharma/nx-spectral-ordering/compare/f2073213a8984e2db4816f1cfa21d61fd0402531..7104b1d74139875bab500652b316d1e6ad06995b

Still interested in exploring if cuSparse PCG solver is a better solution.

[ChuckHastings]

Thanks for your interest and for the links to the relevant research. This looks like a very useful algorithm to add to our library.

While we support an existing spectral clustering algorithm today, we have not yet identified the update path for the spectral clustering algorithm (it's currently a legacy implementation using an older data structure). I will add this to our list of algorithms we would like to explore, but I'm not sure when we will get to it on our road map.

[adsharma]

I wrote a PCG solver using triton. It's not very fast, but seems to pass correctness tests.

This branch has the networkx code modified to use the PCG solver.

Leaving it here as a reference for the next person looking to implement this algorithm in cugraph.