Working well with LightGraphs.jl

[TransGirlCodes]

Hi JuliaComputing,

My name's Ben and I work on BioJulia, right now my efforts are focused on getting Evolutionary Genetics and Phylogenetics modules for Bio.jl. The phylogenetic module is getting written now to take advantage of LightGraphs.jl and I was wondering how easy it would be to enable Gunrock.jl and LightGraphs.jl to work seamlessly together, say passing LightGraphs graphs to Gunrock methods, and whether you guys would be interested in this or had opinions on what it would require? I think it could give the Phylogenetics module we're working on a real boost compared to other libraries in other languages.

Best, Ben.

[ViralBShah]

Cc @ranjanan @jowens

[jowens]

Gunrock team is happy to answer issues!

[ViralBShah]

I think this is easily possible, and @ranjanan can say when this can be made available.

[ranjanan]

@Ward9250 I have implemented LightGraphs support in a branch RA/lg on this repo. Please do check it out and let me know if it's alright. This currently supports only undirected graphs, and I should work with the Gunrock team to see expand upon the C API and include not only directed graphs, but also bring the full capabilities of Gunrock.

[jpfairbanks]

I just looked at that branch. It looks like that integration is at the level of converting an LG graph to a SparseMatrixCSC. Would you want a deeper integration where algorithms defined in LG in terms of some primitives work on graphs stored on the GPU?

This would be a good trial for the interface and a test of how far we can push algorithms working on diverse backing data structures.

[jowens]

Kindly note the new GPU Open Data Analytics Initiative (https://news.developer.nvidia.com/goai-gpu-open-analytics-initiative/) that hopes to define good interchange formats. It's focused more on dense formats today (rather than the sparseness we need for graphs) but we are enthusiastic about it.

[sbromberger]

Just found this thread. One thing you might want to look at is our new(ish) SimpleWeightedGraphs.jl package. The underlying data structure for a SWG is a sparse matrix:

mutable struct SimpleWeightedGraph{T<:Integer, U<:Real} <: AbstractSimpleWeightedGraph
    weights::SparseMatrixCSC{U, T} # indexed by [dst, src]
end

Perhaps we can leverage that somehow?

[jpfairbanks]

Is there any utility in storing the graph as an edge list in a Dataframe/GPUdataframe? Is the conversion time to CSR/CSC still going to dominate? Copying a CSC matrix to the GPU should still be faster than converting the adjacency list.

[ranjanan]

@sbromberger Thanks for linking me to your package. I haven't quite shown this package enough love for a while. Maybe I will benchmark soon and update the chart.

[jowens]

@jpfairbanks this is exactly the kind of discussion that GOAI is having in terms of interoperability. Current efforts are focused on dense data like DataFrames. An edge list is not really amenable to representation in DataFrames, particularly for scale-free graphs. Something like CSR as the interchange format for sparse data makes more sense, I think.

[jpfairbanks]

Well edge list in a dataframe with a multindex is very similar to CSR right?

You have to put it in SQL terms you have the table select src,dst,weight from edgetable ORDER BY src,dst ASC If you make a multiindex on src,dst then you get a CSR like representation. Are you thinking of some other problem with edge lists?

[jowens]

My guess is that CSR would be denser in terms of actual bytes used, as well as being more amenable for GPU parallelization. Translating to matrix nomenclature, I think you're talking about using "COO" format as the sparse format? (In Gunrock we input things on the CPU in COO -- MatrixMarket is COO, I think -- but we convert to CSR for any computation.)