The graphs ecosystem

gdalle · May 26, 2023, 8:54pm

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:

List existing packages to allow comparison
Redesign the core interface to make it more usable
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
Graphs.jl	JuliaGraphs	jpfairbanks	Core interface
SimpleGraphs.jl	-	scheinerman	Alternative interface
SimpleGraphConverter.jl	-	scheinerman	Conversion to and from Graphs.jl
Laplacians.jl	-	danspielman	Graphs as sparse matrices

Metadata

Name	Organization	Maintainers	Focus
SimpleWeightedGraphs.jl	JuliaGraphs	gdalle	Edge weights
MetaGraphsNext.jl	JuliaGraphs	gdalle	Vertex labels, vertex and edge metadata
MetaGraphs.jl	JuliaGraphs	mbesancon	Vertex labels, vertex and edge metadata
AttributeGraphs.jl	UniStuttgart-IKR	filchristou	Vertex and edge metadata
DataGraphs.jl	-	mtfishman	Vertex and edge metadata
MetaDataGraphs.jl	-	gdalle	Vertex labels, vertex and edge metadata
SimpleValueGraphs.jl	-	simonschoelly	Vertex and edge metadata
Erdos.jl	-	CarloLucibello	Vertex and edge metadata
Graft.jl	-	Pranav Thulasiram Bhat	Vertex and edge metadata
StorageGraphs.jl	-	SebastianM-C	Vertex and edge metadata
LabelledGraphs.jl	IITiS PAN	Konrad Jałowiecki	Vertex labels, vertex and edge metadata
NamedGraphs.jl	-	mtfishman	Vertex labels
StenoGraphs.jl	-	aaronpeikert	Vertex and edge metadata
IndexedGraphs.jl	-	stecrotti	Edge metadata
SMDGraphs.jl	JuliaSpaceMissionDesign	Michele Ceresoli	Vertex labels / metadata

Specific fields

Name	Organization	Maintainers	Focus
SpatialGraphs.jl	Circuitscape	vlandau	Spatial locations for vertices
EmbeddedGraphs.jl	PIK-ICoNe	Paul Schultz	Graphs in 2D spaces
AtomGraphs.jl	Chemellia	rkurchin	Molecules as graphs
TextGraphs.jl	-	fargolo	Text as graphs

Multiplicity

Name	Organization	Maintainers	Focus
Multigraphs.jl	QuantumBFS	ChenZhao44	Edges with multiplicity
WrappedMultiGraphs.jl	UniStuttgart-IKR	filchristou	Edges with multiplicity
HyperGraphs.jl	-	Léo Diaz	Graphs with higher-order edges
SimpleHypergraphs.jl	-	pszufe	Graphs with higher-order edges

Structure

Name	Organization	Maintainers	Focus
NestedGraphs.jl	UniStuttgart-IKR	filchristou	Overlapping subgraphs
MultiLayerGraphs.jl	JuliaGraphs	InPhyT	Several stacked layers
SimpleGraphRepresentations.jl	-	scheinerman	Graphs with specific structure
ChordalGraph.jl	-	wangjie212	Chordal graphs
SpecialGraphs.jl	JuliaGraphs	mbesancon	Structure encoded in type
DirectedAcyclicGraphs.jl	-	guyvdb	Directed graphs without loops
PeriodicGraphs.jl	-	Liozou	Repeating graph structures
GridGraphs.jl	-	gdalle	Graphs on a 2D grid

Efficiency / safety

Name	Organization	Maintainers	Focus
StaticGraphs.jl	JuliaGraphs	Seth Bromberger	Immutable graphs
ImplicitGraphs.jl	-	scheinerman	Dynamically generated graphs
BoundedDegreeGraphs.jl	-	SteffenPL	No allocations with limited neighbors
VertexSafeGraphs.jl	-	mbesancon	Stable vertex indices

Linear algebra

Name	Organization	Maintainers	Focus	Comp.	Reg.	Act.
SuiteSparseGraphBLAS.jl	JuliaSparse	Wimmerer	Linear algebra for graphs
MatrixNetworks.jl	JuliaGraphs	nassarhuda	Graphs as matrices

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

CameronBieganek · May 29, 2023, 2:31pm

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.

gdalle · May 29, 2023, 5:41pm

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

gdalle · May 30, 2023, 5:48am

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

gdalle · May 30, 2023, 5:49am

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

jar1 · May 30, 2023, 5:52am

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”.

SteffenPL · May 30, 2023, 6:35am

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 ]
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.

aaronpeikert · May 30, 2023, 9:50am

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!

gdalle · May 31, 2023, 4:58am

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

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 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.

jar1 · May 31, 2023, 6:02am

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

gdalle · May 31, 2023, 6:21am

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

filchristou · May 31, 2023, 6:29am

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.

gdalle · May 31, 2023, 6:39am

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
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 )

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.

etienne_dg · May 31, 2023, 7:04am

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)

gdalle · May 31, 2023, 1:28pm

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?

gdalle · May 31, 2023, 7:31pm

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

SebastianM-C · May 31, 2023, 11:25pm

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
I’m not sure what should I do with the package, as I’m not sure if there’s anyone interested in using it.

gdalle · June 1, 2023, 5:02am

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

mtfishman · July 18, 2023, 11:57am

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.

gdalle · July 18, 2023, 12:46pm

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

Name	Organization	Maintainers	Focus	Comp.	Reg.	Act.
LightGraphs.jl	-	Seth Bromberger	Predecessor of Graphs.jl
OldGraphs.jl	JuliaAttic	Dahua Lin	Old package with the same name as Graphs.jl