Community call - 2024.01.25

[gdalle]

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

[gdalle]

GraphsInterfaceChecker

• https://github.com/gdalle/GraphsInterfaceChecker.jl
• Tried on on DGraphs: helped find bugs, easy to set up
• Should be a standalone registered package?
  • specific dependency on Interfaces.jl
  • tests several downstream dependencies
• Should be kept with Graphs.jl?
• Things to add to the checker?
  • specify vertex type and link it with return types (https://github.com/gdalle/GraphsInterfaceChecker.jl/issues/6)

[gdalle]

Metadata and weights

• Should weights be separated from metadata?
• At the moment:
  • no standard for metadata
  • only access to the whole weights(g) matrix
• Need for various types of metadata storage but single access interface would make sense
• Example from TensorNetworks (@mtfishman): weights are implicit functions of the tensors associated with each vertex
• Metadata can be really huge
• https://github.com/JuliaGraphs/GraphsBase.jl/issues/14
• Named graphs are different from meta graphs: adding labels is different from adding data
• The current API for weights(g) returns ones everywhere for SimpleGraphs because it assumes the edge exists
• We would need more work to call has_edge every time a weight is queried
• In DaggerGraphs, metadata is the central thing and weights can be computed from it
• Weights can be any data type, not just numbers

[gdalle]

Graph views

• Partitions are linked to views of a graph (https://github.com/JuliaGraphs/GraphsBase.jl/issues/8)
• When you take a view, do you relabel?
• Can you reuse the same memory?
• @filchristou has done it in NestedGraphs.jl (partition = subgraphs)
• @pszufe has also done it with SimpleHyperGraphs.jl
• Needs a way to collapse a view into its own separate memory

[gdalle]

Side algorithm packages

• GraphsFlows, GraphsMatching, CommunityDetection will disappear
• GraphsOptim.jl will contain the algorithms that need mathematical programming solvers
• All the other combinatorial algorithms go to Graphs.jl

[gdalle]

Review

• Struggling with the weight of reviews
• Feel free to contribute even if you don't have merge rights
• What should be the standard? Do we need to read the paper every time?
• Benchmarks and tests compared to paper are a good bar
• If it's 1000 lines, don't include even if correct because too complex?
• Who's writing the PR also matters
• We need to make sure that the code will be maintained
• Should we add more features and more mess?
• Maybe complex functions should live in another package
• Graphs v2.0 would give us more control

[gdalle]

Testing

• Testing graph algorithms is hard: if we give too easy instances we miss bugs
• For min cut very often the best cut is a single vertex https://github.com/JuliaGraphs/Graphs.jl/pull/325
• Each algorithm needs a specific class of graphs to be tested / benchmarked properly
• Example: ABCD graphs for graph partitioning (https://arxiv.org/abs/2203.01480) with ABCDGraphGenerator.jl