Community call - 2024.01.25

DaggerGraphs

• https://github.com/JuliaParallel/Dagger.jl/pull/448
• Huge graphs with partitioned structure and metadata
• Merge is close thanks to @jpsamaroo
• Order of magnitude: hundreds of millions of nodes (simulate a megalopolis)
• Partitioned / distributed across several workers
• Make it general purpose: conform to the Graphs.jl interface
• Other interfaces to add that may not make sense for other use cases
• Design decisions to discuss
• Situation vis-à-vis graph metadata?
• User can provide the partition number for each vertex, but there are built-in partitioning mechanisms
• @mtfishman has also been developing a partitioned graph type, see Metis.jl and KaHyPar.jl for algorithms
• Just one data structure in DaggerGraphs, containing both vertex names and metadata and weights
• What data gets distributed and what data gets cached? Is it worth caching neighborhoods?
• Louvain and Leiden algorithms are not bad
• @gdalle will have two interns on parallel graph algorithms

Start with the linked Dagger.jl pull request #448 and the discussion of the Graphs.jl interface, then compare the referenced Metis.jl and KaHyPar.jl approaches. The issue does not name implementation files or tests; done would require an agreed design for the partitioned graph data structure, metadata, distribution, caching, and algorithms.