I am working on breaking up the sparse graph that I have, and although I am pleased with the results that I have seen, it is currently too slow. The graph contains about 200,000 nodes, and scipy.sparse.linalg.eigsh takes about an hour. I tried using shift inversion mode and various initializations as well as linear spectral shift, but it still takes many hours on my i7-4770k. Are there any tricks for initialization or alternative algorithms that are faster for sparse graphs of a certain structure?
Part of my hope for this performance improvement is that nVidia has tests for some of its GPU approaches for similar graphs that run for seconds: https://devblogs.nvidia.com/parallelforall/fast-spectral-graph- partitioning- GPUs /
Of course, this is on the GPU, and not on the CPU, as I have now, but it seems like a huge gap for something that is not particularly parallelized (matrix-vector products). Maybe all of this, though - I'm trying to avoid adding a GPU dependency at the moment, but I can, if that's what I need.
source
share