The graphs ecosystem

Hey everyone,

The very fruitful discussion on fixing package fragmentation started from a remark I made on Slack about graphs, which is why I’m asking the community for ideas and support.

In my opinion, the most important things we can do (by order of priority) are:

  1. List existing packages to allow comparison
  2. Redesign the core interface to make it more usable
  3. Ensure reliability of the main packages for the long term

What follows is a brief summary of each item, but feel free to suggest more! Sorry in advance for the long post.


1. Existing packages

At this stage, the JuliaGraphs organization is recognized as the main place to look for graph-related Julia code. But that doesn’t mean it is the only place you can find such code! Incoming users are often confused about the competing standards, and there are easy fixes.

My proposal would be to add external packages to the JuliaGraphs website, so I’ve started a list. Please help me complete it, and tag your friends who develop graphs packages in secret!
For the purposes of this list, I’m excluding packages related to reading / writing / plotting graphs, as well as optimization algorithms, to concentrate only on data structures.

The list

  • “Organization”: does it belong to a GitHub organization?
  • “Maintainer”: who is listed first on the GitHub contributors list?
  • “Focus”: what does the package do?
  • “Comp(atible)”: does it have Graphs.jl in its dependencies?
  • “Reg(istered)”: does it belong to the general registry?
  • “Act(ive)”: has there been at least one commit to main in 2023 (I know it’s arbitrary)?

Last update of the list: 31-05-2023

Main interfaces
Name Organization Maintainers Focus Comp. Reg. Act.
Graphs.jl JuliaGraphs jpfairbanks Core interface :white_check_mark: :white_check_mark: :white_check_mark:
SimpleGraphs.jl - scheinerman Alternative interface :white_check_mark: :white_check_mark: :white_check_mark:
SimpleGraphConverter.jl - scheinerman Conversion to and from Graphs.jl :white_check_mark: :white_check_mark: :x:
Laplacians.jl - danspielman Graphs as sparse matrices :x: :white_check_mark: :white_check_mark:
Metadata
Name Organization Maintainers Focus Comp. Reg. Act.
SimpleWeightedGraphs.jl JuliaGraphs gdalle Edge weights :white_check_mark: :white_check_mark: :white_check_mark:
MetaGraphsNext.jl JuliaGraphs gdalle Vertex labels, vertex and edge metadata :white_check_mark: :white_check_mark: :white_check_mark:
MetaGraphs.jl JuliaGraphs mbesancon Vertex labels, vertex and edge metadata :white_check_mark: :white_check_mark: :white_check_mark:
AttributeGraphs.jl UniStuttgart-IKR filchristou Vertex and edge metadata :white_check_mark: :white_check_mark: :white_check_mark:
DataGraphs.jl - mtfishman Vertex and edge metadata :white_check_mark: :white_check_mark: :white_check_mark:
MetaDataGraphs.jl - gdalle Vertex labels, vertex and edge metadata :white_check_mark: :white_check_mark: :x:
SimpleValueGraphs.jl - simonschoelly Vertex and edge metadata :white_check_mark: :white_check_mark: :x:
Erdos.jl - CarloLucibello Vertex and edge metadata :white_check_mark: :white_check_mark: :x:
Graft.jl - Pranav Thulasiram Bhat Vertex and edge metadata :x: :x: :x:
StorageGraphs.jl - SebastianM-C Vertex and edge metadata :x: :white_check_mark: :x:
LabelledGraphs.jl IITiS PAN Konrad Jałowiecki Vertex labels, vertex and edge metadata :x: :white_check_mark: :x:
NamedGraphs.jl - mtfishman Vertex labels :white_check_mark: :white_check_mark: :white_check_mark:
StenoGraphs.jl - aaronpeikert Vertex and edge metadata :x: :white_check_mark: :white_check_mark:
IndexedGraphs.jl - stecrotti Edge metadata :white_check_mark: :white_check_mark: :white_check_mark:
SMDGraphs.jl JuliaSpaceMissionDesign Michele Ceresoli Vertex labels / metadata :white_check_mark: :white_check_mark: :white_check_mark:
Specific fields
Name Organization Maintainers Focus Comp. Reg. Act.
SpatialGraphs.jl Circuitscape vlandau Spatial locations for vertices :white_check_mark: :white_check_mark: :x:
EmbeddedGraphs.jl PIK-ICoNe Paul Schultz Graphs in 2D spaces :white_check_mark: :white_check_mark: :x:
AtomGraphs.jl Chemellia rkurchin Molecules as graphs :white_check_mark: :white_check_mark: :white_check_mark:
TextGraphs.jl - fargolo Text as graphs :white_check_mark: :x: :white_check_mark:
Multiplicity
Name Organization Maintainers Focus Comp. Reg. Act.
Multigraphs.jl QuantumBFS ChenZhao44 Edges with multiplicity :white_check_mark: :white_check_mark: :white_check_mark:
WrappedMultiGraphs.jl UniStuttgart-IKR filchristou Edges with multiplicity :white_check_mark: :white_check_mark: :white_check_mark:
HyperGraphs.jl - Léo Diaz Graphs with higher-order edges :x: :x: :white_check_mark:
SimpleHypergraphs.jl - pszufe Graphs with higher-order edges :white_check_mark: :white_check_mark: :white_check_mark:
Structure
Name Organization Maintainers Focus Comp. Reg. Act.
NestedGraphs.jl UniStuttgart-IKR filchristou Overlapping subgraphs :white_check_mark: :white_check_mark: :white_check_mark:
MultiLayerGraphs.jl JuliaGraphs InPhyT Several stacked layers :white_check_mark: :white_check_mark: :white_check_mark:
SimpleGraphRepresentations.jl - scheinerman Graphs with specific structure :x: :x: :x:
ChordalGraph.jl - wangjie212 Chordal graphs :white_check_mark: :white_check_mark: :x:
SpecialGraphs.jl JuliaGraphs mbesancon Structure encoded in type :x: :x: :x:
DirectedAcyclicGraphs.jl - guyvdb Directed graphs without loops :x: :white_check_mark: :x:
PeriodicGraphs.jl - Liozou Repeating graph structures :white_check_mark: :white_check_mark: :white_check_mark:
GridGraphs.jl - gdalle Graphs on a 2D grid :white_check_mark: :white_check_mark: :white_check_mark:
Efficiency / safety
Name Organization Maintainers Focus Comp. Reg. Act.
StaticGraphs.jl JuliaGraphs Seth Bromberger Immutable graphs :white_check_mark: :white_check_mark: :x:
ImplicitGraphs.jl - scheinerman Dynamically generated graphs :x: :white_check_mark: :white_check_mark:
BoundedDegreeGraphs.jl - SteffenPL No allocations with limited neighbors :white_check_mark: :white_check_mark: :white_check_mark:
VertexSafeGraphs.jl - mbesancon Stable vertex indices :x: :white_check_mark: :x:
Linear algebra
Name Organization Maintainers Focus Comp. Reg. Act.
SuiteSparseGraphBLAS.jl JuliaSparse Wimmerer Linear algebra for graphs :x: :white_check_mark: :x:
MatrixNetworks.jl JuliaGraphs nassarhuda Graphs as matrices :x: :white_check_mark: :x:
Archives
Name Organization Maintainers Focus Comp. Reg. Act.
LightGraphs.jl - Seth Bromberger Predecessor of Graphs.jl :x: :white_check_mark: :x:
OldGraphs.jl JuliaAttic Dahua Lin Old package with the same name as Graphs.jl :x: :white_check_mark: :x:

A few remarks

On the positive side:

  • I’m amazed at the productivity and creativity of this community
  • A sizeable portion abides by the Graphs.jl interface

On the negative side:

  • There are plenty of registered but inactive packages, which means good discoverable names go to waste
  • The proliferation of standards, especially for metadata, is concerning

2. Core interface

If we want the Graphs.jl interface to be even more widely accepted, we have to make it better. This starts with a more generic approach, which would make it easier to handle metadata or multigraphs. The question of vertex and edge indexing is therefore central.

You’re more than welcome to contribute to the discussion, either here or on GitHub.

A few relevant issues

We also have to make sure that all algorithms implemented in the code and satellite package respect the interface specifications and do not make additional assumptions. As far as I can tell, this is not necessarily the case.


3. Long term reliability

As all open source developers know, taking care of such a vast ecosystem takes a lot of effort. I really think the community we’ve built around graphs has a great deal to offer in terms of performance and flexibility, but to succeed it would need:

  • More guidance and discussions (like this one), to focus contributions on a few key packages instead of wasting time and energy
  • More packages joining the organization as a way of diluting the workload
  • More reactivity from maintainers (including me), to tackle issues and merge PRs
  • More financial and human resources, ie. people who are actually paid to work on the ecosystem

I plan to recruit a half-time master’s student in the fall to start working on these issues. I was too late for the JSoC / GSoC calls, but as I understand there are others who got projects accepted in this general area (aurorarossi at least).
On the long term, it would be great if we could secure some funding for the JuliaGraphs organization.
I’m just a junior postdoc, but if anyone has ideas of grants we could apply to, let me know! I would love to make this open source mission a sizeable portion of my work, along with more theoretical research projects (I’m currently exploring graph neural networks, ping CarloLucibello).


Enough with the monologue. What do you think? Where should we go? How do we solve the Nebraska conundrum?

PS: Discourse limited me to 10 mentions, but feel free to add more among the usernames I couldn’t tag
@mbesancon @CarloLucibello @simonschoelly @jpfairbanks @viralbshah @aurorarossi @filchristou @etienne_dg @SuperGrobi @jlapeyre

52 Likes

Thanks for opening this discussion. I’ve been involved in some discussions around the interface in the past, but I haven’t kept up with the new issues. I’ll try to chime in on some of the new Github issues.

I agree that we need a more generic interface. I would like to see an interface that includes first-class support for vertex labels and graph metadata.

3 Likes

Clearly metadata is among the main gripes everywhere. I’ve been fiddling with a new API for MetaGraphsNext.jl, might be worth a look: voluntary Labels support · Issue #59 · JuliaGraphs/MetaGraphsNext.jl · GitHub

1 Like

Tagging some more package maintainers: @scheinerman @mtfishman @SebastianM-C @aaronpeikert @vlandau @rkurchin @fargolo @ChenZhao44 @pszufe @InPhyT

1 Like

@wangjie212 @guyvdb @Liozou @SteffenPL @rayegun @nassarhuda
There, I’m done!

Useless outsider thoughts here…

  • The API where you add a vertex and then check nv to see if it worked seems weird to me. Normally when I try a fallible operation, I expect a success or failure value, eg, Some(value) | nothing.

  • Currently graphs are integer indexed, and labels are a secondary thing. I would suggest considering generic index types as the primary indexing instead of “integers supplemented by labels”.

2 Likes

Wow, that’s a great list (I didn’t know about ImplicitGraphs, quite cool!)

I’m not really a graph theory guy. Therefore, some more outside thoughts:

  • It would be cool to have a set of performance benchmarks (to see which graph types fit which tasks). [I’m happy to work on that, actually, I kind of discovered recently that the `SimpleGraph` type is much faster than I initially thought :smiley: ]

  • It seems to me that in the discussions about metadata, several different aspects are mixed together, e.g., metadata per vertex, metadata per edge, and labeled vertices. Decoupling these tasks could maybe help, e.g. there could be three different abstract interfaces for each of the problems.

    • Not sure, but maybe one can learn from the metadata discussion for DataFrarames.
2 Likes

This is amazing work. Thanks for organizing the list. I really wish the Graphs.jl API wouldn’t be as complicated with metadata. From a data structure perspective, in StenoGraphs.jl, I mainly care about the metadata and have not yet linked it to Graphs.jl because it was simply too cumbersome. The combination of keeping track of metadata and indices outside of the graph data structure was simply to bug-prone and fragile. But I really want to integrate the package into the broader ecosystem!

4 Likes

Thank you all for chiming in, time for some answers! Let’s keep the discussion going :slight_smile:

For the basic Simple(Di)Graph this is actually what happens, but it is incoherent with the behavior of other mutating functions in the base language:

julia> a = [1]
1-element Vector{Int64}:
 1

julia> push!(a, 2)
2-element Vector{Int64}:
 1
 2

In addition, it seems to be a problem for multigraphs, as highlighted by @filchristou in this issue.

I’m not 100% sure but I think integer indices are an essential part of the performance of Graphs.jl, as opposed to networkx (in Python) where vertices can be arbitrary objects. It allows every algorithm to work with a common, memory-efficient format, and changing this throughout the ecosystem would be an extremely ambitious endeavor.

The solution I would favor is a graph type based on integers but where as many functions as possible can be called with labels too. A quick example from my current explorations in a branch of MetaGraphsNext.jl, which uses metaprogramming to generate code:

for op in (:has_vertex, :inneighbors, :outneighbors)
    op_labels = Symbol(op, :_labels)
    @eval function $op_labels(lmg::AbstractLabeledMetaGraph, li)
        i = get_vertex(lmg, li)
        return $op(lmg, i)
    end
end

This makes it easy to define a new function f_label for every function f, and then we only need a macro @labels that transforms f into f_label whenever we want. Something like:

macro labels(ex::Expr)
    if ex.head == :call
        f = ex.args[1]
        f_labels = Symbol(f, "_labels")
        ex_labels = Expr(ex.head, f_labels, esc.(ex.args[2:end])...)
        return ex_labels
    end
end

Once we have a solid interface, that will definitely be one of the main priorities! Beware, I’ll tag you again :smiling_face: And comparing with networkx and rustworkx would also be beneficial!

I agree that the labeling and metadata problems are more or less separated.

  • The former can be probably addressed with metaprogramming, as mentioned above, but other suggestions are welcome!
  • The latter encompasses vertex-, edge- and graph-level metadata, and I’m not sure it would make a lot of sense to separate these use cases? For instance, when computing the weight of an edge e=(u, v), in the most general case I might want to exploit the data linked to u, v, and e itself.

Trust me, we all do. My preference at the moment would be to define an abstract type (or trait) for graphs with metadata, à la AttributeGraphs.jl by @filchristou. Then we could provide one concrete implementation that relies on dictionaries, and let users come up with their own, more efficient subtypes if they want.
That would be similar to the AbstractGraph / SimpleGraph duo, and I think it would help a lot of people.

2 Likes

The API is different afaict because push! on arrays doesn’t fail, especially not silently.

Maybe not on Arrays from the base library, but on other subtypes of AbstractArray it might, yet we would still use push!?

Just to let you know that AttributeGraphs, NestedGraphs and WrappedMultiGraphs are already registered, if you would like to update the list entries. The way I see it AttributeGraphs would ideally be consumed by MetaGraphsNext, and WrappedMultiGraphs from the new Graphs.jl interface. When that happens I would be happy to archive them.
Although you intentionally skipped IO, we must say that GraphIO.jl deserves more attention as it looks deserted. With 1.9 we can finally solve the Requires.jl nightmare using package extensions. I also have some code in NestedGraphsIO.jl that should be ported there. I guess extending the package extensions dependencies shouldn’t be a problem now. I was intending to find some time before juliacon to make a PR to to put everything together. I hope it will get attention as generally interacting with GraphsIO.jl mainteners has been hard.

Thanks, I just did!

Thank you for your willingness to contribute to a single project, I think that’s exactly the approach we need to solve fragmentation in this case :muscle:
The way I see it, a new base Graphs library (GraphsBase.jl? GraphsCore.jl?) should emerge (as suggested by @CarloLucibello in this issue), with only:

  • an interface for graphs with and without metadata (including multigraphs)
  • tests for this interface
  • basic implementations of the interface (typically including MetaGraphsNext.jl)

Then Graphs.jl could be dedicated to combinatorial algorithms that satisfy this interface, and GraphsOptim.jl to those specific algorithms that require a (MI)LP solver (sorry @aurorarossi, I promise I’ll get to it someday :rofl:)

Indeed it looks like GraphIO.jl hasn’t seen any activity since the move from LightGraphs.jl to Graphs.jl (aka prehistoric times). And again, it could benefit from switching to a new redesigned interface, because storage of graphs with metadata is also a common request. If you want to contribute, we could add you to the org? Pinging @simonschoelly in case he knows more about this specific topic.

I think that would be very sad to restrict ourselves to integer vertices, because there is some implementation that need indexing that is not range based for performance purposes, notably when there is mutation involved. I opened a discussion for the 2.0 where I proposed an API which should be able to keep the current performances for SimpleGraphs while allowing more generic graph types. I am willing to make it happen, even if it needs a full rewrite of the library. I just started working on it as I now have a bit of time to spare. (but not that much until I defend my thesis)

4 Likes

Very awesome (and congrats on handing in your thesis manuscript!).
I’ll revisit that roadmap discussion this week to give some opinions, maybe we can also have a call about it once it stabilizes?

1 Like

Just discovered and added @danspielman’s Laplacians.jl, holy cow this is endless :rofl:

1 Like

My package is no longer active as I no longer actively need it and also because I realized that the performance scales pretty badly with the size of the graph. It would be nice to have a graph database in native julia, but that’s something far more complex than what I wrote on my own to organize my data for a conference :sweat_smile:
I’m not sure what should I do with the package, as I’m not sure if there’s anyone interested in using it.

1 Like

I think that speaks to a broader problem, which is that many experimental packages get added to the general registry instead of a LocalRegistry, and when they go unmaintained the name is taken but there is no way for naive users to know if it is safe to build upon. I should know, I’ve done that myself a few times ^^
Perhaps a good idea would be to mark it explicitly on the README and repo description? When I have time I’ll make a PR to every unmaintained repo adding one line to the README :smiling_imp:

1 Like

Thanks for making this nice summary @gdalle.

Should we (as in anyone interested in this topic) plan to meet up at some point during JuliaCon next week to discuss the graph ecosystem in Julia?

I would be interested in sharing my experience developing GitHub - mtfishman/NamedGraphs.jl: Extension of `Graphs.jl` to graphs with named vertices. and GitHub - mtfishman/DataGraphs.jl: A simple graph type with data on the vertices and edges. based around the Graphs.jl interface, and hearing about other work on vertex labels and metadata.

3 Likes

Unfortunately I won’t be there in Boston, but I’d be thrilled to attend via Zoom :slight_smile: